Minimizing finite sums with the stochastic average gradient
From MaRDI portal
Publication:517295
Abstract: We propose the stochastic average gradient (SAG) method for optimizing the sum of a finite number of smooth convex functions. Like stochastic gradient (SG) methods, the SAG method's iteration cost is independent of the number of terms in the sum. However, by incorporating a memory of previous gradient values the SAG method achieves a faster convergence rate than black-box SG methods. The convergence rate is improved from O(1/k^{1/2}) to O(1/k) in general, and when the sum is strongly-convex the convergence rate is improved from the sub-linear O(1/k) to a linear convergence rate of the form O(p^k) for p extless{} 1. Further, in many cases the convergence rate of the new method is also faster than black-box deterministic gradient methods, in terms of the number of gradient evaluations. Numerical experiments indicate that the new algorithm often dramatically outperforms existing SG and deterministic gradient methods, and that the performance may be further improved through the use of non-uniform sampling strategies.
Recommendations
- Semi-stochastic coordinate descent
- Stochastic quasi-gradient methods: variance reduction via Jacobian sketching
- A proximal stochastic gradient method with progressive variance reduction
- Lp and almost sure rates of convergence of averaged stochastic gradient algorithms: locally strongly convex objective
- Convergence rate of incremental subgradient algorithms
Cites work
- A Convergent Incremental Gradient Method with a Constant Step Size
- A modified finite Newton method for fast solution of large scale linear SVMs
- A New Class of Incremental Gradient Methods for Least Squares Problems
- A nonlinear GMRES optimization algorithm for canonical tensor decomposition
- A proximal stochastic gradient method with progressive variance reduction
- A randomized Kaczmarz algorithm with exponential convergence
- A Stochastic Approximation Method
- Accelerated Stochastic Approximation
- Accelerated Stochastic Approximation
- Acceleration of Stochastic Approximation by Averaging
- Adaptive subgradient methods for online learning and stochastic optimization
- An Incremental Gradient(-Projection) Method with Momentum Term and Adaptive Stepsize Rule
- Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization
- Convergence rate of incremental subgradient algorithms
- Dual averaging methods for regularized stochastic learning and online optimization
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Exponentiated gradient algorithms for conditional random fields and max-margin Markov networks
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 1972910 (Why is no real title available?)
- scientific article; zbMATH DE number 2117879 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Hybrid deterministic-stochastic methods for data fitting
- Incremental gradient algorithms with stepsizes bounded away from zero
- Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization
- Introductory lectures on convex optimization. A basic course.
- Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization. II: Shrinking procedures and optimal algorithms
- Pegasos: primal estimated sub-gradient solver for SVM
- Primal-dual subgradient methods for convex problems
- Robust Stochastic Approximation Approach to Stochastic Programming
- Semi-stochastic coordinate descent
- SGD-QN: careful quasi-Newton stochastic gradient descent
- Smooth minimization of non-smooth functions
- Stochastic dual coordinate ascent methods for regularized loss minimization
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
Cited in
(only showing first 100 items - show all)- Stochastic accelerated alternating direction method of multipliers with importance sampling
- Inexact proximal stochastic gradient method for convex composite optimization
- On variance reduction for stochastic smooth convex optimization with multiplicative noise
- Stochastic gradient descent with Polyak's learning rate
- Convergence of stochastic proximal gradient algorithm
- Point process estimation with Mirror Prox algorithms
- Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute gradient for structured convex optimization
- Analysis of biased stochastic gradient descent using sequential semidefinite programs
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- Convergence rates for optimised adaptive importance samplers
- Randomized smoothing variance reduction method for large-scale non-smooth convex optimization
- Stochastic quasi-gradient methods: variance reduction via Jacobian sketching
- Relative utility bounds for empirically optimal portfolios
- Multivariate goodness-of-fit tests based on Wasserstein distance
- Fast and safe: accelerated gradient methods with optimality certificates and underestimate sequences
- A stochastic primal-dual method for optimization with conditional value at risk constraints
- On the regularization effect of stochastic gradient descent applied to least-squares
- Stochastic DCA for minimizing a large sum of DC functions with application to multi-class logistic regression
- Analysis of stochastic gradient descent in continuous time
- Fast incremental expectation maximization for finite-sum optimization: nonasymptotic convergence
- Fully asynchronous policy evaluation in distributed reinforcement learning over networks
- The recursive variational Gaussian approximation (R-VGA)
- Variable metric proximal stochastic variance reduced gradient methods for nonconvex nonsmooth optimization
- Multi-agent reinforcement learning: a selective overview of theories and algorithms
- SABRINA: a stochastic subspace majorization-minimization algorithm
- A hierarchically low-rank optimal transport dissimilarity measure for structured data
- A stochastic first-order trust-region method with inexact restoration for finite-sum minimization
- Accelerating variance-reduced stochastic gradient methods
- A hybrid stochastic optimization framework for composite nonconvex optimization
- Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
- A stochastic extra-step quasi-Newton method for nonsmooth nonconvex optimization
- Finite-sum smooth optimization with SARAH
- Accelerating incremental gradient optimization with curvature information
- The multiproximal linearization method for convex composite problems
- Linear convergence of cyclic SAGA
- Bi-fidelity stochastic gradient descent for structural optimization under uncertainty
- Why random reshuffling beats stochastic gradient descent
- A linearly convergent stochastic recursive gradient method for convex optimization
- Leveraged least trimmed absolute deviations
- Improved SVRG for finite sum structure optimization with application to binary classification
- Accelerated proximal incremental algorithm schemes for non-strongly convex functions
- A stochastic trust region method for unconstrained optimization problems
- Provable accelerated gradient method for nonconvex low rank optimization
- Deep relaxation: partial differential equations for optimizing deep neural networks
- Convergence rates of accelerated proximal gradient algorithms under independent noise
- Generalized forward-backward splitting with penalization for monotone inclusion problems
- An accelerated variance reducing stochastic method with Douglas-Rachford splitting
- Minimizing robust estimates of sums of parameterized functions
- Improving kernel online learning with a snapshot memory
- Cocoercivity, smoothness and bias in variance-reduced stochastic gradient methods
- Optimal non-asymptotic analysis of the Ruppert-Polyak averaging stochastic algorithm
- Variance reduction for root-finding problems
- Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functions
- On the asymptotic rate of convergence of stochastic Newton algorithms and their weighted averaged versions
- Adaptive sampling for incremental optimization using stochastic gradient descent
- Hybrid deterministic-stochastic methods for data fitting
- Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression
- An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
- Catalyst acceleration for first-order convex optimization: from theory to practice
- Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification
- Adaptive sampling strategies for stochastic optimization
- A stochastic variance reduction method for PCA by an exact penalty approach
- Optimizing adaptive importance sampling by stochastic approximation
- Semi-stochastic coordinate descent
- Batched Stochastic Gradient Descent with Weighted Sampling
- Convergence rate analysis of projected stochastic subgradient method using conjugate gradient-like direction
- Multilevel stochastic gradient methods for nested composition optimization
- Parsimonious online learning with kernels via sparse projections in function space
- Optimal rates for multi-pass stochastic gradient methods
- Distributed stochastic variance reduced gradient methods by sampling extra data with replacement
- Surpassing gradient descent provably: a cyclic incremental method with linear convergence rate
- Optimization methods for large-scale machine learning
- The Averaged Kaczmarz Iteration for Solving Inverse Problems
- Random gradient extrapolation for distributed and stochastic optimization
- Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications
- scientific article; zbMATH DE number 1928800 (Why is no real title available?)
- GADMM: fast and communication efficient framework for distributed machine learning
- scientific article; zbMATH DE number 7255141 (Why is no real title available?)
- A class of parallel doubly stochastic algorithms for large-scale learning
- Nesterov's acceleration for approximate Newton
- A data efficient and feasible level set method for stochastic convex optimization with expectation constraints
- Proximal-like incremental aggregated gradient method with linear convergence under Bregman distance growth conditions
- A randomized incremental primal-dual method for decentralized consensus optimization
- Approximate Newton methods
- L-SVRG and L-Katyusha with arbitrary sampling
- Incremental proximal gradient scheme with penalization for constrained composite convex optimization problems
- Stochastic average gradient algorithm for multirate FIR models with varying time delays using self-organizing maps
- PDE-constrained optimal control problems with uncertain parameters using SAGA
- A Stochastic Proximal Alternating Minimization for Nonsmooth and Nonconvex Optimization
- Some limit properties of Markov chains induced by recursive stochastic algorithms
- scientific article; zbMATH DE number 7626720 (Why is no real title available?)
- scientific article; zbMATH DE number 7625177 (Why is no real title available?)
- General framework for binary classification on top samples
- Quasi-Newton methods for machine learning: forget the past, just sample
- Stochastic learning approach for binary optimization: application to Bayesian optimal design of experiments
- Complexity Analysis of stochastic gradient methods for PDE-constrained optimal Control Problems with uncertain parameters
- Sketched Newton-Raphson
- On stochastic and deterministic quasi-Newton methods for nonstrongly convex optimization: asymptotic convergence and rate analysis
- Stochastic reformulations of linear systems: algorithms and convergence theory
- A Continuous-Time Analysis of Distributed Stochastic Gradient
This page was built for publication: Minimizing finite sums with the stochastic average gradient
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q517295)
