Performance of distributed optimization and learning systems is bottlenecked
by "straggler" nodes and slow communication links, which significantly delay
computation. We propose a distributed optimization framework where the dataset
is "encoded" to have an over-complete representation with built-in redundancy,
and the straggling nodes in the system are dynamically left out of the
computation at every iteration, whose loss is compensated by the embedded
redundancy. We show that oblivious application of several popular optimization
algorithms on encoded data, including gradient descent, L-BFGS, proximal
gradient under data parallelism, and coordinate descent under model
parallelism, converge to either approximate or exact solutions of the original
problem when stragglers are treated as erasures. These convergence results are
deterministic, i.e., they establish sample path convergence for arbitrary
sequences of delay patterns or distributions on the nodes, and are independent
of the tail behavior of the delay distribution. We demonstrate that equiangular
tight frames have desirable properties as encoding matrices, and propose
efficient mechanisms for encoding large-scale data. We implement the proposed
technique on Amazon EC2 clusters, and demonstrate its performance over several
learning problems, including matrix factorization, LASSO, ridge regression and
logistic regression, and compare the proposed method with uncoded,
asynchronous, and data replication strategies.

本文提出了一种分布式优化框架，通过将数据编码为过完备表示，并动态地在每次迭代中舍弃整个计算中的掉队节点，从而减少了延迟和通信传输的负担，结果表明在数据被编码的情况下，对于几种流行的优化算法，包括梯度下降、L-BFGS、在数据并行性下的近端梯度以及在模型并行性下的坐标下降，当掉队者被视为纠删码时，它们都会收敛到原始问题的近似或精确解，收敛结果是确定性的，并且与掉队分布的尾部行为无关，本研究还提出了一种用于大规模数据编码的高效机制，以及证明了用等角紧框架作为编码矩阵的理想性质，并与未编码、异步和数据复制策略进行了比较。