An improved convergence analysis for decentralized online stochastic non-convex optimization

Abstract

In this paper, we study decentralized online stochastic non-convex optimization over a network of nodes. Integrating a technique called gradient tracking in decentralized stochastic gradient descent, we show that the resulting algorithm, GT-DSGD, enjoys certain desirable characteristics towards minimizing a sum of smooth non-convex functions. In particular, for general smooth non-convex functions, we establish non-asymptotic characterizations of GT-DSGD and derive the conditions under which it achieves network-independent performances that match the centralized minibatch SGD. In contrast, the existing results suggest that GT-DSGD is always network-dependent and is therefore strictly worse than the centralized minibatch SGD. When the global non-convex function additionally satisfies the Polyak-Lojasiewics (PL) condition, we establish the linear convergence of GT-DSGD up to a steady-state error with appropriate constant step-sizes. Moreover, under stochastic approximation step-sizes, we establish, for the first time, the optimal global sublinear convergence rate on almost every sample path, in addition to the asymptotically optimal sublinear rate in expectation. Since strongly convex functions are a special case of the functions satisfying the PL condition, our results are not only immediately applicable but also improve the currently known best convergence rates and their dependence on problem parameters.

References in corpus (17)

• Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
• Harnessing Smoothness to Accelerate Distributed Optimization
• Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• A linear algorithm for optimization over directed graphs with geometric convergence
• Convergence Rate Analysis of Distributed Gossip (Linear Parameter) Estimation: Fundamental Limits and Tradeoffs
• D${}^2$: Decentralized Training over Decentralized Data
• Stochastic Gradient Push for Distributed Deep Learning
• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions
• Decentralized Stochastic Gradient Tracking for Non-convex Empirical Risk Minimization
• Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
• Distributed Learning in Non-Convex Environments -- Part II: Polynomial Escape from Saddle-Points

Cited by in corpus (19)

• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning
• Decentralized Stochastic Gradient Tracking for Non-convex Empirical Risk Minimization
• BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning
• Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD
• Fast decentralized non-convex finite-sum optimization with recursive variance reduction
• Distributed Learning over Networks with Graph-Attention-Based Personalization
• A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization
• A Stochastic Proximal Gradient Framework for Decentralized Non-Convex Composite Optimization: Topology-Independent Sample Complexity and Communication Efficiency
• Improving the Transient Times for Distributed Stochastic Gradient Methods
• Distributed Nonconvex Optimization: Gradient-free Iterations and $\epsilon$-Globally Optimal Solution
• A fast randomized incremental gradient method for decentralized non-convex optimization
• Accelerating Gossip SGD with Periodic Global Averaging
• A general framework for decentralized optimization with first-order methods
• Optimal Complexity in Decentralized Training
• Heavy-Tail Phenomenon in Decentralized SGD
• An Empirical Study on Compressed Decentralized Stochastic Gradient Algorithms with Overparameterized Models
• CO-DEFEND: Continuous Decentralized Federated Learning for Secure DoH-Based Threat Detection
• Asymptotic Properties of $\mathcal{S}$-$\mathcal{A}\mathcal{B}$ Method with Diminishing Stepsize