Distributed Inexact Successive Convex Approximation ADMM: Analysis-Part I
arXiv:1907.08969
Abstract
In this two-part work, we propose an algorithmic framework for solving non-convex problems whose objective function is the sum of a number of smooth component functions plus a convex (possibly non-smooth) or/and smooth (possibly non-convex) regularization function. The proposed algorithm incorporates ideas from several existing approaches such as alternate direction method of multipliers (ADMM), successive convex approximation (SCA), distributed and asynchronous algorithms, and inexact gradient methods. Different from a number of existing approaches, however, the proposed framework is flexible enough to incorporate a class of non-convex objective functions, allow distributed operation with and without a fusion center, and include variance reduced methods as special cases. Remarkably, the proposed algorithms are robust to uncertainties arising from random, deterministic, and adversarial sources. The part I of the paper develops two variants of the algorithm under very mild assumptions and establishes first-order convergence rate guarantees. The proof developed here allows for generic errors and delays, paving the way for different variance-reduced, asynchronous, and stochastic implementations, outlined and evaluated in part II.
References in corpus (17)
- QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
- A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
- Parallel and Distributed Methods for Nonconvex Optimization--Part II: Applications
- Convex Optimization for Big Data
- Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
- Asynchronous Distributed ADMM for Large-Scale Optimization- Part I: Algorithm and Convergence Analysis
- Gradient Sparsification for Communication-Efficient Distributed Optimization
- Stochastic Successive Convex Approximation for Non-Convex Constrained Stochastic Optimization
- A Parallel Stochastic Approximation Method for Nonconvex Multi-Agent Optimization Problems
- Optimization with First-Order Surrogate Functions
- Parallel Successive Convex Approximation for Nonsmooth Nonconvex Optimization
- Asynchronous Stochastic Gradient Descent with Variance Reduction for Non-Convex Optimization
- Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization
- Analysis of Biased Stochastic Gradient Descent Using Sequential Semidefinite Programs
- Variance Reduction for Distributed Stochastic Gradient Descent
- A convergence framework for inexact nonconvex and nonsmooth algorithms and its applications to several iterations
- Generalized Stochastic Frank-Wolfe Algorithm with Stochastic "Substitute" Gradient for Structured Convex Optimization