A Caltech Library Service

Achieving the fundamental convergence-communication tradeoff with Differentially Quantized Gradient Descent

Lin, Chung-Yi and Kostina, Victoria and Hassibi, Babak (2020) Achieving the fundamental convergence-communication tradeoff with Differentially Quantized Gradient Descent. . (Unpublished)

[img] PDF (8 May 2020) - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The problem of reducing the communication cost in distributed training through gradient quantization is considered. For gradient descent on smooth and strongly convex objective functions on R^n, we characterize the fundamental rate function-the minimum achievable linear convergence rate for a given number of bits per dimension n. We propose Differentially Quantized Gradient Descent, a quantization algorithm with error compensation, and prove that it achieves the rate function as n goes to infinity. In contrast, the naive quantizer that compresses the current gradient directly fails to achieve that optimal tradeoff. Experimental results on both simulated and real-world least-squares problems confirm our theoretical analysis.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Kostina, Victoria0000-0002-2406-7440
Additional Information:We would like to thank Dr. Himanshu Tyagi for pointing out related works on the convergence communication tradeoff (Mayekar and Tyagi, 2019, 2020) and Dr. Vincent Tan for bringing up a known result on the worst-case convergence rate of unquantized GD (de Klerk et al., 2017) to our attention. This work was supported in part by the National Science Foundation (NSF) under grants CCF-1751356, CNS-0932428, CCF-1018927, CCF-1423663 and CCF-1409204, by a grant from Qualcomm Inc., by NASAs Jet Propulsion Laboratory through the President and Directors Fund, and by King Abdullah University of Science and Technology.
Funding AgencyGrant Number
JPL President and Director's FundUNSPECIFIED
King Abdullah University of Science and Technology (KAUST)UNSPECIFIED
Subject Keywords:Quantized gradient descent, distributed optimization, error compensation, informationtheoretic tradeoff, rate function, federated learning
Record Number:CaltechAUTHORS:20200214-105624458
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:101308
Deposited By: George Porter
Deposited On:14 Feb 2020 19:18
Last Modified:09 Nov 2020 22:40

Repository Staff Only: item control page