  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.
