Surpassing gradient descent provably: a cyclic incremental method with linear convergence rate
From MaRDI portal
Abstract: Recently, there has been growing interest in developing optimization methods for solving large-scale machine learning problems. Most of these problems boil down to the problem of minimizing an average of a finite set of smooth and strongly convex functions where the number of functions is large. Gradient descent method (GD) is successful in minimizing convex problems at a fast linear rate; however, it is not applicable to the considered large-scale optimization setting because of the high computational complexity. Incremental methods resolve this drawback of gradient methods by replacing the required gradient for the descent direction with an incremental gradient approximation. They operate by evaluating one gradient per iteration and executing the average of the available gradients as a gradient approximate. Although, incremental methods reduce the computational cost of GD, their convergence rates do not justify their advantage relative to GD in terms of the total number of gradient evaluations until convergence. In this paper, we introduce a Double Incremental Aggregated Gradient method (DIAG) that computes the gradient of only one function at each iteration, which is chosen based on a cyclic scheme, and uses the aggregated average gradient of all the functions to approximate the full gradient. The iterates of the proposed DIAG method uses averages of both iterates and gradients in oppose to classic incremental methods that utilize gradient averages but do not utilize iterate averages. We prove that not only the proposed DIAG method converges linearly to the optimal solution, but also its linear convergence factor justifies the advantage of incremental methods on GD. In particular, we prove that the worst case performance of DIAG is better than the worst case performance of GD.
Recommendations
- On the Convergence Rate of Incremental Aggregated Gradient Algorithms
- Incremental proximal methods for large scale convex optimization
- IQN: an incremental quasi-Newton method with local superlinear convergence rate
- Convergence rate of incremental gradient and incremental Newton methods
- Accelerating incremental gradient optimization with curvature information
Cites work
- A Convergent Incremental Gradient Method with a Constant Step Size
- A New Class of Incremental Gradient Methods for Least Squares Problems
- A proximal stochastic gradient method with progressive variance reduction
- A Randomized Incremental Subgradient Method for Distributed Optimization in Networked Systems
- A Stochastic Approximation Method
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- An Incremental Gradient(-Projection) Method with Momentum Term and Adaptive Stepsize Rule
- Diffusion Least-Mean Squares Over Adaptive Networks: Formulation and Performance Analysis
- Distributed control of robotic networks: a mathematical approach to motion coordination algorithms.
- DSA: decentralized double stochastic averaging gradient algorithm
- Ergodic Stochastic Optimization Algorithms for Wireless Communication and Networking
- Global convergence rate of proximal incremental aggregated gradient methods
- scientific article; zbMATH DE number 194139 (Why is no real title available?)
- Incremental majorization-minimization optimization with application to large-scale machine learning
- Incremental proximal methods for large scale convex optimization
- Incremental stochastic subgradient algorithms for convex optimization
- Incremental subgradient methods for nondifferentiable optimization
- Incrementally updated gradient methods for constrained and regularized optimization
- Introductory lectures on convex optimization. A basic course.
- Large-scale machine learning with stochastic gradient descent
- Minimizing finite sums with the stochastic average gradient
- On the Convergence Rate of Incremental Aggregated Gradient Algorithms
- On‐line learning for very large data sets
- Stochastic dual coordinate ascent methods for regularized loss minimization
Cited in
(16)- Solving composite fixed point problems with block updates
- Variable smoothing incremental aggregated gradient method for nonsmooth nonconvex regularized optimization
- Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
- Accelerating incremental gradient optimization with curvature information
- Linear convergence of cyclic SAGA
- A class of parallel doubly stochastic algorithms for large-scale learning
- A distributed flexible delay-tolerant proximal gradient algorithm
- IQN: an incremental quasi-Newton method with local superlinear convergence rate
- Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity
- Proximal variable smoothing method for three-composite nonconvex nonsmooth minimization with a linear operator
- Random-reshuffled SARAH does not need full gradient computations
- SPIRAL: a superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization
- The geometry of monotone operator splitting methods
- Speeding up L-BFGS by direct approximation of the inverse Hessian matrix
- 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: Surpassing gradient descent provably: a cyclic incremental method with linear convergence rate
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4641666)
