Random-reshuffled SARAH does not need full gradient computations

DOI10.1007/S11590-023-02081-XMaRDI QIDQ6204201zbMATH OpenOpenAlexFDO

Authors Aleksandr Beznosikov, M. Takáč

Publication date 27 March 2024

Published in Optimization Letters (Search for Journal in Brave)

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

zbMATH Keywords

convex optimizationfinite-sum problemsstochastic optimizationvariance reduction

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Abstract: The StochAstic Recursive grAdient algoritHm (SARAH) algorithm is a variance reduced variant of the Stochastic Gradient Descent (SGD) algorithm that needs a gradient of the objective function from time to time. In this paper, we remove the necessity of a full gradient computation. This is achieved by using a randomized reshuffling strategy and aggregating stochastic gradients obtained in each epoch. The aggregated stochastic gradients serve as an estimate of a full gradient in the SARAH algorithm. We provide a theoretical analysis of the proposed approach and conclude the paper with numerical experiments that demonstrate the efficiency of this approach.

Recommendations

• Inexact SARAH algorithm for stochastic optimization
• Why random reshuffling beats stochastic gradient descent
• A linearly convergent stochastic recursive gradient method for convex optimization
• Accelerating mini-batch SARAH by step size rules

Cites work

• A Stochastic Approximation Method
• Accelerating mini-batch SARAH by step size rules
• scientific article; zbMATH DE number 4063877 (Why is no real title available?)
• scientific article; zbMATH DE number 7626722 (Why is no real title available?)
• Incremental majorization-minimization optimization with application to large-scale machine learning
• Inexact SARAH algorithm for stochastic optimization
• Katyusha: the first direct acceleration of stochastic gradient methods
• Linear convergence of cyclic SAGA
• Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
• Minimizing finite sums with the stochastic average gradient
• New Convergence Aspects of Stochastic Gradient Algorithms
• On the Convergence Rate of Incremental Aggregated Gradient Algorithms
• Optimization for deep learning: an overview
• Optimization methods for large-scale machine learning
• Parallel stochastic gradient algorithms for large-scale matrix completion
• Pegasos: primal estimated sub-gradient solver for SVM
• Stochastic Learning Under Random Reshuffling With Constant Step-Sizes
• Surpassing gradient descent provably: a cyclic incremental method with linear convergence rate
• Understanding machine learning. From theory to algorithms
• User-friendly tail bounds for sums of random matrices
• Variance-Reduced Stochastic Learning Under Random Reshuffling

Cited in

(2)

• An adaptive stochastic gradient algorithm based on FISTA for convex optimization
• Adjusted shuffling SARAH: advancing complexity analysis via dynamic gradient weighting

This page was built for publication: Random-reshuffled SARAH does not need full gradient computations

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