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.

arXiv comment20 pages, 2 algorithms, 5 figures, 3 tables

References in corpus (15)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• User-friendly tail bounds for sums of random matrices
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• On the Convergence Rate of Incremental Aggregated Gradient Algorithms
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• Better Theory for SGD in the Nonconvex World
• Random Reshuffling: Simple Analysis with Vast Improvements
• Stochastic Learning under Random Reshuffling with Constant Step-sizes
• A Unified Convergence Analysis for Shuffling-Type Gradient Methods
• 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
• Linear Convergence of Cyclic SAGA
• Random Reshuffling with Variance Reduction: New Analysis and Better Rates