Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization

Abstract

Large scale distributed optimization has become the default tool for the training of supervised machine learning models with a large number of parameters and training data. Recent advancements in the field provide several mechanisms for speeding up the training, including {\em compressed communication}, {\em variance reduction} and {\em acceleration}. However, none of these methods is capable of exploiting the inherently rich data-dependent smoothness structure of the local losses beyond standard smoothness constants. In this paper, we argue that when training supervised models, {\em smoothness matrices} -- information-rich generalizations of the ubiquitous smoothness constants -- can and should be exploited for further dramatic gains, both in theory and practice. In order to further alleviate the communication burden inherent in distributed optimization, we propose a novel communication sparsification strategy that can take full advantage of the smoothness matrices associated with local losses. To showcase the power of this tool, we describe how our sparsification technique can be adapted to three distributed optimization algorithms -- DCGD, DIANA and ADIANA -- yielding significant savings in terms of communication complexity. The new methods always outperform the baselines, often dramatically so.

arXiv comment59 pages, 5 figues, 6 tables

References in corpus (12)

• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• Error Feedback Fixes SignSGD and other Gradient Compression Schemes
• DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
• Distributed Delayed Stochastic Optimization
• Distributed Learning with Compressed Gradient Differences
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Natural Compression for Distributed Deep Learning
• On Biased Compression for Distributed Learning
• Distributed learning with compressed gradients
• One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods
• Error Compensated Distributed SGD Can Be Accelerated

Cited by in corpus (2)

• Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques
• Det-CGD: Compressed Gradient Descent with Matrix Stepsizes for Non-Convex Optimization