Efficient Randomized Subspace Embeddings for Distributed Optimization under a Communication Budget. (arXiv:2103.07578v4 [cs.LG] UPDATED)

We study first-order optimization algorithms under the constraint that the
descent direction is quantized using a pre-specified budget of $R$-bits per
dimension, where $R \in (0 ,\infty)$. We propose computationally efficient
optimization algorithms with convergence rates matching the
information-theoretic performance lower bounds for: (i) Smooth and
Strongly-Convex objectives with access to an Exact Gradient oracle, as well as
(ii) General Convex and Non-Smooth objectives with access to a Noisy
Subgradient oracle. The crux of these algorithms is a polynomial complexity …

arxiv budget communication distributed lg optimization