A Stochastic Proximal Gradient Framework for Decentralized Non-Convex Composite Optimization: Topology-Independent Sample Complexity and Communication Efficiency
arXiv:2110.01594
Abstract
Decentralized optimization is a promising parallel computation paradigm for large-scale data analytics and machine learning problems defined over a network of nodes. This paper is concerned with decentralized non-convex composite problems with population or empirical risk. In particular, the networked nodes are tasked to find an approximate stationary point of the average of local, smooth, possibly non-convex risk functions plus a possibly non-differentiable extended valued convex regularizer. Under this general formulation, we propose the first provably efficient, stochastic proximal gradient framework, called ProxGT. Specifically, we construct and analyze several instances of ProxGT that are tailored respectively for different problem classes of interest. Remarkably, we show that the sample complexities of these instances are network topology-independent and achieve linear speedups compared to that of the corresponding centralized optimal methods implemented on a single node.
References in corpus (19)
- Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
- Optimal algorithms for smooth and strongly convex distributed optimization in networks
- D: Decentralized Training over Decentralized Data
- 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
- Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems
- 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
- Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
- Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD
- Fast decentralized non-convex finite-sum optimization with recursive variance reduction
- An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite Nonconvex Optimization
- Improving the Transient Times for Distributed Stochastic Gradient Methods
- Decentralized Composite Optimization with Compression