On the Convergence of SGD with Biased Gradients

Abstract

We analyze the complexity of biased stochastic gradient methods (SGD), where individual updates are corrupted by deterministic, i.e. biased error terms. We derive convergence results for smooth (non-convex) functions and give improved rates under the Polyak-Lojasiewicz condition. We quantify how the magnitude of the bias impacts the attainable accuracy and the convergence rates (sometimes leading to divergence). Our framework covers many applications where either only biased gradient updates are available, or preferred, over unbiased ones for performance reasons. For instance, in the domain of distributed learning, biased gradient compression techniques such as top-k compression have been proposed as a tool to alleviate the communication bottleneck and in derivative-free optimization, only biased gradient estimators can be queried. We discuss a few guiding examples that show the broad applicability of our analysis.

arXiv commentAccepted to ICML 2020 Workshop "Beyond First Order Methods in ML Systems", updated 2021

References in corpus (14)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
• Sparsified SGD with Memory
• Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
• Universal adversarial perturbations
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• On Biased Compression for Distributed Learning
• Stochastic Gradient Descent with Biased but Consistent Gradient Estimators
• Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning
• Efficient Greedy Coordinate Descent for Composite Problems

Cited by in corpus (7)

• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms
• SGD with Coordinate Sampling: Theory and Practice
• Learning Deep Neural Networks under Agnostic Corrupted Supervision
• Linear Speedup in Personalized Collaborative Learning
• Invexifying Regularization of Non-Linear Least-Squares Problems
• Masked Training of Neural Networks with Partial Gradients