Inexact SARAH algorithm for stochastic optimization
From MaRDI portal
Abstract: We develop and analyze a variant of the SARAH algorithm, which does not require computation of the exact gradient. Thus this new method can be applied to general expectation minimization problems rather than only finite sum problems. While the original SARAH algorithm, as well as its predecessor, SVRG, require an exact gradient computation on each outer iteration, the inexact variant of SARAH (iSARAH), which we develop here, requires only stochastic gradient computed on a mini-batch of sufficient size. The proposed method combines variance reduction via sample size selection and iterative stochastic gradient updates. We analyze the convergence rate of the algorithms for strongly convex and non-strongly convex cases, under smooth assumption with appropriate mini-batch size selected for each case. We show that with an additional, reasonable, assumption iSARAH achieves the best known complexity among stochastic methods in the case of non-strongly convex stochastic functions.
Recommendations
- Finite-sum smooth optimization with SARAH
- A linearly convergent stochastic recursive gradient method for convex optimization
- Accelerating mini-batch SARAH by step size rules
- scientific article; zbMATH DE number 7255141
- Non-asymptotic convergence analysis of inexact gradient methods for machine learning without strong convexity
Cites work
- A stochastic line search method with expected complexity analysis
- Cubic regularization of Newton method and its global performance
- scientific article; zbMATH DE number 7255141 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- Minimizing finite sums with the stochastic average gradient
- Semi-stochastic coordinate descent
- Some methods of speeding up the convergence of iteration methods
Cited in
(13)- SABRINA: a stochastic subspace majorization-minimization algorithm
- A hybrid stochastic optimization framework for composite nonconvex optimization
- Accelerating mini-batch SARAH by step size rules
- Finite-sum smooth optimization with SARAH
- Accelerated stochastic variance reduction for a class of convex optimization problems
- Non-asymptotic convergence analysis of inexact gradient methods for machine learning without strong convexity
- Fast decentralized nonconvex finite-sum optimization with recursive variance reduction
- Adaptivity of stochastic gradient methods for nonconvex optimization
- Random-reshuffled SARAH does not need full gradient computations
- General inertial proximal stochastic variance reduction gradient for nonconvex nonsmooth optimization
- Non-asymptotic analysis of hybrid SPG for non-convex stochastic composite optimization
- Multi-iteration stochastic optimizers
- Adjusted shuffling SARAH: advancing complexity analysis via dynamic gradient weighting
This page was built for publication: Inexact SARAH algorithm for stochastic optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5859016)
