Random gradient extrapolation for distributed and stochastic optimization
From MaRDI portal
Abstract: In this paper, we consider a class of finite-sum convex optimization problems defined over a distributed multiagent network with agents connected to a central server. In particular, the objective function consists of the average of () smooth components associated with each network agent together with a strongly convex term. Our major contribution is to develop a new randomized incremental gradient algorithm, namely random gradient extrapolation method (RGEM), which does not require any exact gradient evaluation even for the initial point, but can achieve the optimal complexity bound in terms of the total number of gradient evaluations of component functions to solve the finite-sum problems. Furthermore, we demonstrate that for stochastic finite-sum optimization problems, RGEM maintains the optimal complexity (up to a certain logarithmic factor) in terms of the number of stochastic gradient computations, but attains an complexity in terms of communication rounds (each round involves only one agent). It is worth noting that the former bound is independent of the number of agents , while the latter one only linearly depends on or even for ill-conditioned problems. To the best of our knowledge, this is the first time that these complexity bounds have been obtained for distributed and stochastic optimization problems. Moreover, our algorithms were developed based on a novel dual perspective of Nesterov's accelerated gradient method.
Recommendations
- An optimal randomized incremental gradient method
- Accelerated Stochastic Algorithms for Nonconvex Finite-Sum and Multiblock Optimization
- A randomized incremental primal-dual method for decentralized consensus optimization
- Revisiting EXTRA for Smooth Distributed Optimization
- Communication-efficient algorithms for decentralized and stochastic optimization
Cites work
- A Convergent Incremental Gradient Method with a Constant Step Size
- A proximal stochastic gradient method with progressive variance reduction
- A randomized Kaczmarz algorithm with exponential convergence
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization
- An iterative row-action method for interval convex programming
- An optimal method for stochastic composite optimization
- Bregman Monotone Optimization Algorithms
- EXTRA: an exact first-order algorithm for decentralized consensus optimization
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- Interior Gradient and Proximal Methods for Convex and Conic Optimization
- Introductory lectures on convex optimization. A basic course.
- Katyusha: the first direct acceleration of stochastic gradient methods
- Minimizing finite sums with the stochastic average gradient
- Optimal distributed online prediction using mini-batches
- Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
- Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization. II: Shrinking procedures and optimal algorithms
- Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
- Proximal Minimization Methods with Generalized Bregman Functions
- Robust Stochastic Approximation Approach to Stochastic Programming
- Stochastic Dual Averaging for Decentralized Online Optimization on Time-Varying Communication Graphs
- Stochastic dual coordinate ascent methods for regularized loss minimization
Cited in
(24)- Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems
- Numerical methods for the resource allocation problem in a computer network
- A two-level distributed algorithm for nonconvex constrained optimization
- Revisiting EXTRA for Smooth Distributed Optimization
- Distributed Stochastic Optimization via Matrix Exponential Learning
- Exact Diffusion for Distributed Optimization and Learning—Part I: Algorithm Development
- Distributed stochastic variance reduced gradient methods by sampling extra data with replacement
- A randomized incremental primal-dual method for decentralized consensus optimization
- Convergence Rates of Distributed Gradient Methods Under Random Quantization: A Stochastic Approximation Approach
- On the convergence of stochastic primal-dual hybrid gradient
- Simple and optimal methods for stochastic variational inequalities. I: Operator extrapolation
- Estimate sequences for stochastic composite optimization: variance reduction, acceleration, and robustness to noise
- Inexact model: a framework for optimization and variational inequalities
- Gradient-free federated learning methods with l₁ and l₂-randomization for non-smooth convex stochastic optimization problems
- Improving the Transient Times for Distributed Stochastic Gradient Methods
- Proximal stochastic recursive momentum algorithm for nonsmooth nonconvex optimization problems
- Recent theoretical advances in decentralized distributed convex optimization
- Perseus: a simple and optimal high-order method for variational inequalities
- Decentralized stochastic subgradient projection optimization algorithms over random networks
- Accelerated stochastic approximation with state-dependent noise
- Review of mathematical optimization in federated learning
- Optimal methods for convex nested stochastic composite optimization
- General inertial proximal gradient method with gradient extrapolation for nonconvex nonsmooth optimization problems
- An accelerated variance reduced extra-point approach to finite-sum hemivariational inequality problem
This page was built for publication: Random gradient extrapolation for distributed and stochastic optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4687240)
