Finite-sum smooth optimization with SARAH

DOI10.1007/S10589-022-00375-XMaRDI QIDQ2149950zbMATH OpenOpenAlexFDO

Authors Lam M. Nguyen, Marten van Dijk, Dzung T. Phan, Phuong Ha Nguyen, Tsui-Wei Weng, Jayant Kalagnanam

Publication date 27 June 2022

Published in Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.07648

zbMATH Keywords

smoothvariance reductionstochastic algorithmconvexnon-convexfinite-sum

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

Abstract: The total complexity (measured as the total number of gradient computations) of a stochastic first-order optimization algorithm that finds a first-order stationary point of a finite-sum smooth nonconvex objective function $F(w)=frac1nsu{m}_{i=1}^n{f}_i(w)$ has been proven to be at least $Omega(sqrtn/epsilon)$ for $nleqmathcalO(epsilo{n}^{-2})$ where $epsilon$ denotes the attained accuracy $mathbbE[|ablaF(ildew){|}^2]leqepsilon$ for the outputted approximation $ildew$ (Fang et al., 2018). In this paper, we provide a convergence analysis for a slightly modified version of the SARAH algorithm (Nguyen et al., 2017a;b) and achieve total complexity that matches the lower-bound worst case complexity in (Fang et al., 2018) up to a constant factor when $nleqmathcalO(epsilo{n}^{-2})$ for nonconvex problems. For convex optimization, we propose SARAH++ with sublinear convergence for general convex and linear convergence for strongly convex problems; and we provide a practical version for which numerical experiments on various datasets show an improved performance.

Recommendations

• Inexact SARAH algorithm for stochastic optimization
• Smooth Optimization with Approximate Gradient
• Smooth Optimization Methods for Minimax Problems
• A smooth method for the finite minimax problem
• Solving semi-infinite programs by smoothing projected gradient method
• A smoothing iterative method for the finite minimax problem
• Smoothing accelerated algorithm for constrained nonsmooth convex optimization problems
• A Stochastic Smoothing Algorithm for Semidefinite Programming
• Smooth over-parameterized solvers for non-smooth structured optimization
• Smoothing augmented Lagrangian method for nonsmooth constrained optimization problems

Cites work

• scientific article; zbMATH DE number 7255141 (Why is no real title available?)
• A Stochastic Approximation Method
• Adaptive subgradient methods for online learning and stochastic optimization
• Inexact SARAH algorithm for stochastic optimization
• Introductory lectures on convex optimization. A basic course.
• Minimizing finite sums with the stochastic average gradient
• New Convergence Aspects of Stochastic Gradient Algorithms
• Optimization methods for large-scale machine learning
• Stochastic dual coordinate ascent methods for regularized loss minimization

Cited in

(9)

• Adaptivity of stochastic gradient methods for nonconvex optimization
• DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization
• A Convergence Study of SGD-Type Methods for Stochastic Optimization
• Accelerating mini-batch SARAH by step size rules
• Stochastic variance-reduced majorization-minimization algorithms
• Fast decentralized nonconvex finite-sum optimization with recursive variance reduction
• A stochastic extra-step quasi-Newton method for nonsmooth nonconvex optimization
• Inexact SARAH algorithm for stochastic optimization
• Stochastic gradient methods with preconditioned updates

Describes a project that uses

Uses Software

• SpiderBoost
• Saga
• ProxSARAH
• Adam
• AdaGrad
• LIBSVM

This page was built for publication: Finite-sum smooth optimization with SARAH

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2149950)