On the Convergence Rate of Incremental Aggregated Gradient Algorithms
From MaRDI portal
Abstract: Motivated by applications to distributed optimization over networks and large-scale data processing in machine learning, we analyze the deterministic incremental aggregated gradient method for minimizing a finite sum of smooth functions where the sum is strongly convex. This method processes the functions one at a time in a deterministic order and incorporates a memory of previous gradient values to accelerate convergence. Empirically it performs well in practice; however, no theoretical analysis with explicit rate results was previously given in the literature to our knowledge, in particular most of the recent efforts concentrated on the randomized versions. In this paper, we show that this deterministic algorithm has global linear convergence and characterize the convergence rate. We also consider an aggregated method with momentum and demonstrate its linear convergence. Our proofs rely on a careful choice of a Lyapunov function that offers insight into the algorithm's behavior and simplifies the proofs considerably.
Recommendations
- Global convergence rate of proximal incremental aggregated gradient methods
- Convergence rate of incremental subgradient algorithms
- Convergence rate of incremental gradient and incremental Newton methods
- On stochastic accelerated gradient with convergence rate
- On the rates of convergence of parallelized averaged stochastic gradient algorithms
- On the convergence of a block-coordinate incremental gradient method
- Inertial proximal incremental aggregated gradient method with linear convergence guarantees
- Convergence rates of an inertial gradient descent algorithm under growth and flatness conditions
- On the asymptotic convergence and acceleration of gradient methods
- Nonconvex proximal incremental aggregated gradient method with linear convergence
Cites work
- A Convergent Incremental Gradient Method with a Constant Step Size
- A globally convergent incremental Newton method
- An Incremental Gradient(-Projection) Method with Momentum Term and Adaptive Stepsize Rule
- Analysis and design of optimization algorithms via integral quadratic constraints
- Convergence rate of incremental gradient and incremental Newton methods
- Convex optimization algorithms
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 4164577 (Why is no real title available?)
- Incremental gradient algorithms with stepsizes bounded away from zero
- Incremental Least Squares Methods and the Extended Kalman Filter
- Incrementally updated gradient methods for constrained and regularized optimization
- Introductory lectures on convex optimization. A basic course.
- On‐line learning for very large data sets
- The incremental Gauss-Newton algorithm with adaptive stepsize rule
- Why random reshuffling beats stochastic gradient descent
Cited in
(50)- An aggregate and iterative disaggregate algorithm with proven optimality in machine learning
- On variance reduction for stochastic smooth convex optimization with multiplicative noise
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- Incremental without replacement sampling in nonconvex optimization
- Variable smoothing incremental aggregated gradient method for nonsmooth nonconvex regularized optimization
- Fully asynchronous policy evaluation in distributed reinforcement learning over networks
- Inertial proximal incremental aggregated gradient method with linear convergence guarantees
- An accelerated distributed gradient method with local memory
- On the convergence of a block-coordinate incremental gradient method
- On the convergence analysis of aggregated heavy-ball method
- Accelerating incremental gradient optimization with curvature information
- Linear convergence of primal-dual gradient methods and their performance in distributed optimization
- Linear convergence of cyclic SAGA
- An incremental aggregated proximal ADMM for linearly constrained nonconvex optimization with application to sparse logistic regression problems
- Primal-dual incremental gradient method for nonsmooth and convex optimization problems
- Communication-efficient algorithms for decentralized and stochastic optimization
- An inertial parallel and asynchronous forward-backward iteration for distributed convex optimization
- Non-asymptotic convergence analysis of inexact gradient methods for machine learning without strong convexity
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
- An incremental mirror descent subgradient algorithm with random sweeping and proximal step
- Distributed deterministic asynchronous algorithms in time-varying graphs through Dykstra splitting
- Global convergence rate of proximal incremental aggregated gradient methods
- Surpassing gradient descent provably: a cyclic incremental method with linear convergence rate
- Optimization methods for large-scale machine learning
- GADMM: fast and communication efficient framework for distributed machine learning
- Proximal-like incremental aggregated gradient method with linear convergence under Bregman distance growth conditions
- On stochastic and deterministic quasi-Newton methods for nonstrongly convex optimization: asymptotic convergence and rate analysis
- Convergence rate of incremental gradient and incremental Newton methods
- A Convergent Incremental Gradient Method with a Constant Step Size
- IQN: an incremental quasi-Newton method with local superlinear convergence rate
- Linear convergence of proximal incremental aggregated gradient method for nonconvex nonsmooth minimization problems
- A distributed accelerated optimization algorithm over time‐varying directed graphs with uncoordinated step‐sizes
- An asynchronous subgradient-proximal method for solving additive convex optimization problems
- A distributed proximal gradient method with time-varying delays for solving additive convex optimizations
- Proximal variable smoothing method for three-composite nonconvex nonsmooth minimization with a linear operator
- Heavy-ball-based optimal thresholding algorithms for sparse linear inverse problems
- Heavy-ball-based hard thresholding algorithms for sparse signal recovery
- Random-reshuffled SARAH does not need full gradient computations
- Stochastic subgradient algorithm for nonsmooth nonconvex optimization
- Incremental quasi-Newton algorithms for solving a nonconvex, nonsmooth, finite-sum optimization problem
- Convergence on thresholding-based algorithms for dictionary-sparse recovery
- Accelerated gradient methods with biased gradient estimates: risk sensitivity, high-probability guarantees, and large deviation bounds
- Select without fear: almost all minibatch schedules generalize optimally
- Hierarchically distributed optimization with a flexible and complexity-reducing algorithm
- Improved accelerated gradient algorithms with line search for smooth convex optimization problems
- Convergence of ease-controlled random reshuffling gradient algorithms under Lipschitz smoothness
- Speeding up L-BFGS by direct approximation of the inverse Hessian matrix
- Incremental Aggregation on the Grassmannian for Asynchronous Eigenspace Computation
- Adjusted shuffling SARAH: advancing complexity analysis via dynamic gradient weighting
- Convergence rates of subgradient methods for quasi-convex optimization problems
This page was built for publication: On the Convergence Rate of Incremental Aggregated Gradient Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5266533)
