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 (35)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning with Non-IID Data
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Optimal Distributed Online Prediction using Mini-Batches
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Federated Optimization in Heterogeneous Networks
• Sparsified SGD with Memory
• Don't Use Large Mini-Batches, Use Local SGD
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• Communication Compression for Decentralized Training
• D${}^2$: Decentralized Training over Decentralized Data
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Stochastic Gradient Push for Distributed Deep Learning
• Communication Complexity of Distributed Convex Learning and Optimization
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
• Is Local SGD Better than Minibatch SGD?
• Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
• Tighter Theory for Local SGD on Identical and Heterogeneous Data
• MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling
• Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs
• Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks
• $\text{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression
• Communication trade-offs for synchronized distributed SGD with large step size
• New Convergence Aspects of Stochastic Gradient Algorithms
• FedDANE: A Federated Newton-Type Method
• Overlap Local-SGD: An Algorithmic Approach to Hide Communication Delays in Distributed SGD

Cited by in corpus (61)

• UVeQFed: Universal Vector Quantization for Federated Learning
• Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
• Federated Multi-Task Learning under a Mixture of Distributions
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• 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
• Federated Learning with Superquantile Aggregation for Heterogeneous Data
• MARINA: Faster Non-Convex Distributed Learning with Compression
• Device Heterogeneity in Federated Learning: A Superquantile Approach
• Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization
• What Do We Mean by Generalization in Federated Learning?
• Local SGD With a Communication Overhead Depending Only on the Number of Workers
• Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD
• Federated Composite Optimization
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• Federated Face Recognition
• Faster Non-Convex Federated Learning via Global and Local Momentum
• Local SGD: Unified Theory and New Efficient Methods
• On Communication Compression for Distributed Optimization on Heterogeneous Data
• 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
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks
• Multi-Level Local SGD for Heterogeneous Hierarchical Networks
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• Cross-Gradient Aggregation for Decentralized Learning from Non-IID data
• Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• Optimal Complexity in Decentralized Training
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity
• Robust Federated Learning by Mixture of Experts
• ResIST: Layer-Wise Decomposition of ResNets for Distributed Training
• Statistical Estimation and Inference via Local SGD in Federated Learning
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond
• Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping
• Parallel and Distributed algorithms for ML problems
• Local Methods with Adaptivity via Scaling
• Over-the-Air Decentralized Federated Learning
• Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning
• Local SGD for Near-Quadratic Problems: Improving Convergence under Unconstrained Noise Conditions
• ${\text{A}}^2{\text{CiD}}^2$: Accelerating Asynchronous Communication in Decentralized Deep Learning
• Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications
• A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning
• Communication Efficient Generalized Tensor Factorization for Decentralized Healthcare Networks
• Decentralized Composite Optimization in Stochastic Networks: A Dual Averaging Approach with Linear Convergence