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、在数据并行性下的近端梯度以及在模型并行性下的坐标下降，当掉队者被视为纠删码时，它们都会收敛到原始问题的近似或精确解，收敛结果是确定性的，并且与掉队分布的尾部行为无关，本研究还提出了一种用于大规模数据编码的高效机制，以及证明了用等角紧框架作为编码矩阵的理想性质，并与未编码、异步和数据复制策略进行了比较。

分布式优化和学习中的迟滞者减缓冗余技术

Redundancy Techniques for Straggler Mitigation in Distributed  Optimization and Learning

In this paper we give a new construction of parametric families of complex
Hadamard matrices of square orders, and connect them to equiangular tight
frames. The results presented here generalize some of the recent ideas of
Bodmann et al. and extend the list of known equiangular tight frames. In
particular, a (36,21) frame coming from a nontrivial cube root signature matrix
is obtained for the first time.

本文介绍了复哈达玛矩阵的参数化家族的新构造，并将它们与等角紧框架联系起来，所得结果推广了 Bodmann 等人的一些最新思想，扩展了已知等角紧框架的列表。特别地，首次得到了一种（36，21）框架，来自于一个非平凡的立方根签名矩阵。

复合哈达玛矩阵和等角紧框架

Complex Hadamard matrices and Equiangular Tight Frames

We provide a new method for constructing equiangular tight frames (ETFs). The
construction is valid in both the real and complex settings, and shows that
many of the few previously-known examples of ETFs are but the first
representatives of infinite families of such frames. It provides great freedom
in terms of the frame's size and redundancy. This method also explicitly
constructs the frame vectors in their native domain, as opposed to implicitly
defining them via their Gram matrix. Moreover, in this domain, the frame
vectors are very sparse. The construction is extremely simple: a tensor-like
combination of a Steiner system and a regular simplex. This simplicity permits
us to resolve an open question regarding ETFs and the restricted isometry
property (RIP): we show that the RIP behavior of some ETFs is unfortunately no
better than their coherence indicates.

简单张量组合的方法构造了一些 ETF 的无穷种族，在其本地域中构建向量，ETF 的 RIP 行为不如其连贯性好。