Random-reshuffled SARAH does not need a full gradient computations

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.

20 pages, 2 algorithms, 5 figures, 3 tables

References in corpus (8)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• Random Reshuffling: Simple Analysis with Vast Improvements
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation
• An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite Nonconvex Optimization
• SAGA with Arbitrary Sampling
• Random Reshuffling with Variance Reduction: New Analysis and Better Rates