Encoded distributed optimization
Authors:
- 1 June 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2890-2894
Abstract
Today, many real-world machine learning and data analytics problems are of a scale that requires distributed optimization; unlike in centralized computing, these systems are vulnerable to network and node failures. Recently, coding-theoretic ideas have been applied to mitigate node failures in such distributed computing networks. Relaxing the exact recovery requirement of such techniques, we propose a novel approach for adding redundancy in large-scale convex optimization problems, making solvers more robust against sudden and persistent node failures and loss of data. This is done by linearly encoding the data variables; all other aspects the computation operate as usual. We show that under moderate amounts of redundancy, it is possible to recover a close approximation to the solution under node failures. In particular, we show that encoding with (equiangular) tight frames result in bounded objective error, and obtain an explicit error bound for a specific construction that uses Paley graphs. We also demonstrate the performance of the proposed technique for three specific machine learning problems, (two using real world datasets) namely ridge regression, binary support vector machine, and low-rank approximation.Keywords
This publication has 13 references indexed in Scilit:
- Encoded distributed optimization2017
- Speeding up distributed machine learning using codes2016
- Randomized Sketches of Convex Programs With Sharp GuaranteesIEEE Transactions on Information Theory, 2015
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse ProblemsSIAM Journal on Imaging Sciences, 2009
- MapReduceCommunications of the ACM, 2008
- Decoding by Linear ProgrammingIEEE Transactions on Information Theory, 2005
- Optimal frames for erasuresLinear Algebra and its Applications, 2004
- Equal-Norm Tight Frames with ErasuresAdvances in Computational Mathematics, 2003
- Ten Lectures on Wavelets1992
- Lower bounds on the maximum cross correlation of signals (Corresp.)IEEE Transactions on Information Theory, 1974