Quantization using Side-Information for Distributed Optimization: Theory and Practice

Abstract

This thesis aims to systematically study the role of side-information for different problems arising in distributed quantization and optimization. In the first part of the thesis, we study a universal version of the classic Wyner-Ziv problem from information theory, where the side-information is a noisy version of the sender’s Gaussian observations with noise variance unknown to the sender. For this problem, we develop a universally rate-optimal and practical quantization scheme based on Polar codes for all values of unknown noise variance. In the second part of the thesis, we study the efficacy of the Wyner-Ziv compression strategy for gradient compression for distributed first-order smooth optimization. We begin by establishing an information-theoretic lower bound on optimization accuracy when only finite precision gradients are used. Also, we develop quantizers for the gradient compression, which match the aforementioned lower bound when used with the standard first-order optimization algorithms. Finally, we study the fundamental limits of distributed optimization over wireless channels. We begin with a setting where a server is optimizing an objective function using only one client, and the client supplies gradient estimates over a white Gaussian channel. We provide fundamental limits on optimization accuracy when only a finite number of channel uses are permitted. We then extend our study to the multiple clients setting where all the clients communicate their gradient estimates over a multiple-access channel. For this case, too, we establish an information-theoretic lower bound on the optimization accuracy for a given number of channel uses and develop a computationally tractable communication scheme that optimally adapts to the channel conditions. Our scheme involves constructing a side-information by exploiting the closeness among the clients’ distributions and then leveraging that to enhance the overall performance.