Local SGD for Near-Quadratic Problems: Improving Convergence under Unconstrained Noise Conditions

Abstract

Distributed optimization plays an important role in modern large-scale machine learning and data processing systems by optimizing the utilization of computational resources. One of the classical and popular approaches is Local Stochastic Gradient Descent (Local SGD), characterized by multiple local updates before averaging, which is particularly useful in distributed environments to reduce communication bottlenecks and improve scalability. A typical feature of this method is the dependence on the frequency of communications. But in the case of a quadratic target function with homogeneous data distribution over all devices, the influence of frequency of communications vanishes. As a natural consequence, subsequent studies include the assumption of a Lipschitz Hessian, as this indicates the similarity of the optimized function to a quadratic one to some extent. However, in order to extend the completeness of the Local SGD theory and unlock its potential, in this paper we abandon the Lipschitz Hessian assumption by introducing a new concept of $\text{approximate quadraticity}$. This assumption gives a new perspective on problems that have near quadratic properties. In addition, existing theoretical analyses of Local SGD often assume bounded variance. We, in turn, consider the unbounded noise condition, which allows us to broaden the class of studied problems.

arXiv comment33 pages, 1 algorithm, 3 figures, 2 tables

References in corpus (21)

• Deep Learning with Differential Privacy
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Federated Optimization in Heterogeneous Networks
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Variance Reduced Local SGD with Lower Communication Complexity
• Parallel SGD: When does averaging help?
• SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum
• Tighter Theory for Local SGD on Identical and Heterogeneous Data
• Federated Accelerated Stochastic Gradient Descent
• Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization
• Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexity
• Distributed Saddle-Point Problems Under Similarity
• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective
• Local SGD: Unified Theory and New Efficient Methods
• ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!
• Communication-efficient SGD: From Local SGD to One-Shot Averaging
• Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities
• Local Methods with Adaptivity via Scaling