CaltechAUTHORS
  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) https://resolver.caltech.edu/CaltechAUTHORS:20200214-105624458

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

697Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200214-105624458

Abstract

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
http://arxiv.org/abs/2002.02508arXivDiscussion Paper
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
NSFCCF-1751356
NSFCNS-0932428
NSFCCF-1018927
NSFCCF-1423663
NSFCCF-1409204
Qualcomm Inc.UNSPECIFIED
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:https://resolver.caltech.edu/CaltechAUTHORS:20200214-105624458
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:101308
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:14 Feb 2020 19:18
Last Modified:09 Nov 2020 22:40

Repository Staff Only: item control page