We consider distributed optimization over a d-dimensional space, where K remote clients send coded gradient estimates over an additive Gaussian Multiple Access Channel (MAC) with noise variance$\sigma _{z}^{2}$. Furthermore, the codewords from the clients must satisfy the average power constraint P, resulting in a signal-to-noise ratio (SNR) of$KP/\sigma _{z}^{2}$. In this paper, we study the fundamental limits imposed by MAC on the convergence rate of any distributed optimization algorithm and design optimal communication schemes to achieve these limits. Our first result is a lower bound for the convergence rate, showing that communicating over a MAC imposes a slowdown of$\sqrt {d/\frac {1}{2}\log (1+\mathtt {SNR})}$on any protocol compared to the centralized setting. Next, we design a computationally tractable digital communication scheme that matches the lower bound to a logarithmic factor in K when combined with a projected stochastic gradient descent algorithm. At the heart of our communication scheme is carefully combining several compression and modulation ideas such as quantizing along random bases, Wyner-Ziv compression, modulo-lattice decoding, and amplitude shift keying. We also show that analog schemes, which are popular due to their ease of implementation, can give close to optimal convergence rates at low SNR but experience a slowdown of roughly$\sqrt {d}$at high SNR.

Communication efficient distributed mean estimation is an important primitive that arises in many distributed learning and optimization scenarios such as federated learning. Without any probabilistic assumptions on the underlying data, we study the problem of distributed mean estimation where the server has access to side information. We proposeWyner-Ziv estimators, which are communication and computationally efficient and near-optimal when an upper bound for the distance between the side information and the data is known. As a corollary, we also show that our algorithms provide efficient schemes for the classic Wyner-Ziv problem in information theory. In a different direction, when there is no knowledge assumed about the distance between side information and the data, we present an alternative Wyner-Ziv estimator that uses correlated sampling. This latter setting offersuniversal recovery guarantees, and perhaps will be of interest in practice when the number of users is large and keeping track of the distances between the data and the side information may not be possible. With this mean estimator at our disposal, we revisit basic problems in decentralized optimization and compression where our Wyner-Ziv estimator yields algorithms with almost optimal performance. First, we consider the problem of communication constrained distributed optimization and provide an algorithm which attains the optimal convergence rate by exploiting the fact that the gradient estimates are close to each other. Specifically, the gradient compression scheme in our algorithm first uses half of the parties to form side information and then uses our Wyner-Ziv estimator to compress the remaining half of the gradient estimates. Finally, we apply our Wynzer-Ziv estimators to the classic Wyner-Ziv compression problem in information theory to get compression schemes that are computationally efficient and are almost optimal under much more relaxed assumptions than the standard probabilistic setting.

We consider distributed optimization over a d-dimensional space, where K remote clients send coded gradient estimates over an additive Gaussian Multiple Access Channel (MAC) with noise variance $\sigma _z^2$. Furthermore, the codewords from the K clients must satisfy the average power constraint of P, resulting in a signal-to-noise ratio (SNR) of $KP/\sigma _z^2$. In this paper, we study the fundamental limits imposed by MAC on the convergence rate of any distributed optimization algorithm and design optimal communication schemes to achieve these limits. Our first result is a lower bound for the convergence rate showing that compared to the centralized setting, communicating over a MAC imposes a slowdown of $\sqrt {d/\frac{1}{2}\log (1 + {\text{SNR}})}$ on any protocol. Next, we design a computationally tractable digital communication scheme that matches the lower bound to a logarithmic factor in K when combined with a projected stochastic gradient descent algorithm. At the heart of our communication scheme is a careful combination of several compression and modulation ideas such as quantizing along random bases, Wyner-Ziv compression, modulo-lattice decoding, and amplitude shift keying. We also show that analog coding schemes, which are popular due to their ease of implementation, can give close to optimal convergence rates at low SNR but experience a slowdown of roughly $\sqrt d$ at high SNR.

Consider distributed optimization of smooth convex functions over ℝdwhere K independent clients can provide estimates of the gradient. Assume that all the gradient estimates are within Euclidean distance σ of the true gradient and that each oracle’s output must be compressed to r bits. For this problem, in the centralized setting with one client, the optimal convergence rate using T iterations is known to be roughly $\sqrt {{\sigma ^2}/T} $. We show that in the distributed setting the optimal convergence rate for large K is roughly $\sqrt {{\sigma ^2}/T} \cdot \sqrt {d/Kr} $. Our main contribution is an algorithm which attains this rate by exploiting the fact that the gradient estimates are close to each other. Specifically, our gradient compression scheme first uses half of the parties to form side information and then uses a Wyner-Ziv compression scheme to compress the remaining half of the gradient estimates.

We consider convex optimization on a$d$dimensional space where coded gradients are sent over an additive Gaussian noise channel with variance$\sigma^{2}$. The codewords satisfy an average power constraint$P$, resulting in the signal-to-noise ratio (SNR) of$P/\sigma^{2}$. Many schemes have been proposed for this problem, termed over-the-air optimization, in recent years. We present lower and upper bounds for the convergence rates for over-the-air optimization. Our first result is a lower bound for the convergence rate showing that any code must slowdown the convergence rate by a factor of roughly$\sqrt{d/\log(1+\text{SNR})}$. Next, we consider a popular class of schemes called analog coding, where a linear function of the gradient is sent. We show that a simple scaled transmission analog coding scheme results in a slowdown in convergence rate by a factor of$\sqrt{d(1+1/\text{SNR})}$. This matches the previous lower bound up to constant factors for low SNR, making the scaled transmission scheme optimal at low SNR. However, we show that this slowdown is necessary for any analog coding scheme. In particular, a slowdown in convergence by a factor of$\sqrt{d}$remains even when SNR tends to infinity, a clear shortcoming of analog coding schemes at high SNR. Remarkably, we present a simple quantize-and-modulate scheme that uses Amplitude Shift Keying and almost attains the optimal convergence rate at all SNRs.

We consider universal quantization with side information for Gaussian observations, where the side information is a noisy version of the sender’s observation with an unknown noise variance. We propose a universally rate optimal and practical quantization scheme for all values of unknown noise variance. Our scheme is interactive, uses Polar lattices from prior work, and proceeds by checking in each round if a reliable estimate has been formed. In particular, our scheme is based on a structural decomposition of the underlying auxiliaries so that even when recovery fails in a round, the parties agree on a common "reference point" that is closer than the previous one.

We present a novel successive cancellation list (SCL) decoding method for the polar codes based on the mutual-information values of the bit-channels. At short-to-medium blocklengths, only a certain fraction of the bit-channels get polarized. Usually the mutual-information values for the bit- channels are computed for the construction of the code. Using these available mutual-information values, we identify the information bits exhibiting full polarization and having high channel reliability. In the proposed mutual- information-based SCL (MI-SCL) decoder, only one emanating path is considered for such bits. This results in the reduction of the width of the decoding tree. Simulation results confirm the impressive performance of the MI-SCL decoder specially with concatenated cyclic redundancy check codes.