A fast randomized incremental gradient method for decentralized non-convex optimization
arXiv:2011.03853
Abstract
We study decentralized non-convex finite-sum minimization problems described over a network of nodes, where each node possesses a local batch of data samples. In this context, we analyze a single-timescale randomized incremental gradient method, called GT-SAGA. GT-SAGA is computationally efficient as it evaluates one component gradient per node per iteration and achieves provably fast and robust performance by leveraging node-level variance reduction and network-level gradient tracking. For general smooth non-convex problems, we show the almost sure and mean-squared convergence of GT-SAGA to a first-order stationary point and further describe regimes of practical significance where it outperforms the existing approaches and achieves a network topology-independent iteration complexity respectively. When the global function satisfies the Polyak-Lojaciewisz condition, we show that GT-SAGA exhibits linear convergence to an optimal solution in expectation and describe regimes of practical interest where the performance is network topology-independent and improves upon the existing methods. Numerical experiments are included to highlight the main convergence aspects of GT-SAGA in non-convex settings.
arXiv commentAccepted in IEEE Transactions on Automatic Control
References in corpus (15)
- Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
- 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
- D: Decentralized Training over Decentralized Data
- DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
- Stochastic Gradient Push for Distributed Deep Learning
- Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
- An improved convergence analysis for decentralized online stochastic non-convex optimization
- Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis
- On the Influence of Bias-Correction on Distributed Stochastic Optimization
- A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
- Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization
- Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach
- Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
- Fast decentralized non-convex finite-sum optimization with recursive variance reduction