A Unified Theory of Decentralized SGD with Changing Topology and Local Updates

Abstract

Decentralized stochastic optimization methods have gained a lot of attention recently, mainly because of their cheap per iteration cost, data locality, and their communication-efficiency. In this paper we introduce a unified convergence analysis that covers a large variety of decentralized SGD methods which so far have required different intuitions, have different applications, and which have been developed separately in various communities. Our algorithmic framework covers local SGD updates and synchronous and pairwise gossip updates on adaptive network topology. We derive universal convergence rates for smooth (convex and non-convex) problems and the rates interpolate between the heterogeneous (non-identically distributed data) and iid-data settings, recovering linear convergence rates in many special cases, for instance for over-parametrized models. Our proofs rely on weak assumptions (typically improving over prior work in several aspects) and recover (and improve) the best known complexity results for a host of important scenarios, such as for instance coorperative SGD and federated averaging (local SGD).

References in corpus (8)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• Is Local SGD Better than Minibatch SGD?
• Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence
• Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs
• Communication trade-offs for synchronized distributed SGD with large step size
• FedDANE: A Federated Newton-Type Method
• Overlap Local-SGD: An Algorithmic Approach to Hide Communication Delays in Distributed SGD

Cited by in corpus (60)

• UVeQFed: Universal Vector Quantization for Federated Learning
• Federated Multi-Task Learning under a Mixture of Distributions
• Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
• Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies
• FedCluster: Boosting the Convergence of Federated Learning via Cluster-Cycling
• A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning
• Throughput-Optimal Topology Design for Cross-Silo Federated Learning
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data
• Federated Learning With Quantized Global Model Updates
• Federated Learning with Compression: Unified Analysis and Sharp Guarantees
• Recent theoretical advances in decentralized distributed convex optimization
• Consensus Control for Decentralized Deep Learning
• Federated Accelerated Stochastic Gradient Descent
• Device Heterogeneity in Federated Learning: A Superquantile Approach
• MARINA: Faster Non-Convex Distributed Learning with Compression
• Federated Learning with Superquantile Aggregation for Heterogeneous Data
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization
• Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning
• Local SGD With a Communication Overhead Depending Only on the Number of Workers
• What Do We Mean by Generalization in Federated Learning?
• Federated Composite Optimization
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD
• Federated Face Recognition
• Local SGD: Unified Theory and New Efficient Methods
• On Communication Compression for Distributed Optimization on Heterogeneous Data
• Faster Non-Convex Federated Learning via Global and Local Momentum
• TEE-based decentralized recommender systems: The raw data sharing redemption
• PowerGossip: Practical Low-Rank Communication Compression in Decentralized Deep Learning
• Communication-efficient SGD: From Local SGD to One-Shot Averaging
• RelaySum for Decentralized Deep Learning on Heterogeneous Data
• SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation
• Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data
• Taming GANs with Lookahead-Minmax
• Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• Multi-Level Local SGD for Heterogeneous Hierarchical Networks
• Cross-Gradient Aggregation for Decentralized Learning from Non-IID data
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity
• Optimal Complexity in Decentralized Training
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses
• Local Methods with Adaptivity via Scaling
• Statistical Estimation and Inference via Local SGD in Federated Learning
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond
• Robust Federated Learning by Mixture of Experts
• Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping
• Parallel and Distributed algorithms for ML problems
• ResIST: Layer-Wise Decomposition of ResNets for Distributed Training
• ${\text{A}}^2{\text{CiD}}^2$: Accelerating Asynchronous Communication in Decentralized Deep Learning
• Communication Efficient Generalized Tensor Factorization for Decentralized Healthcare Networks
• A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning
• Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications
• Decentralized Composite Optimization in Stochastic Networks: A Dual Averaging Approach with Linear Convergence
• Local SGD for Near-Quadratic Problems: Improving Convergence under Unconstrained Noise Conditions
• Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning
• Over-the-Air Decentralized Federated Learning