SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient

Abstract

In this paper, we propose a StochAstic Recursive grAdient algoritHm (SARAH), as well as its practical variant SARAH+, as a novel approach to the finite-sum minimization problems. Different from the vanilla SGD and other modern stochastic methods such as SVRG, S2GD, SAG and SAGA, SARAH admits a simple recursive framework for updating stochastic gradient estimates; when comparing to SAG/SAGA, SARAH does not require a storage of past gradients. The linear convergence rate of SARAH is proven under strong convexity assumption. We also prove a linear convergence rate (in the strongly convex case) for an inner loop of SARAH, the property that SVRG does not possess. Numerical experiments demonstrate the efficiency of our algorithm.

References in corpus (1)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets

Cited by in corpus (20)

• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• Stochastic, Distributed and Federated Optimization for Machine Learning
• R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
• A Stochastic Alternating Direction Method of Multipliers for Non-smooth and Non-convex Optimization
• Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD
• SGD_Tucker: A Novel Stochastic Optimization Strategy for Parallel Sparse Tucker Decomposition
• Stochastic Algorithms for Self-consistent Calculations of Electronic Structures
• Adaptive Stochastic Optimization
• Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method
• SGDLibrary: A MATLAB library for stochastic gradient descent algorithms
• Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models
• Stochastic variance reduced multiplicative update for nonnegative matrix factorization
• Distributed Stochastic Non-Convex Optimization: Momentum-Based Variance Reduction
• Memory Augmented Optimizers for Deep Learning
• Larger is Better: The Effect of Learning Rates Enjoyed by Stochastic Optimization with Progressive Variance Reduction
• Projected Semi-Stochastic Gradient Descent Method with Mini-Batch Scheme under Weak Strong Convexity Assumption
• Optimal Analysis of Method with Batching for Monotone Stochastic Finite-Sum Variational Inequalities
• Flexible numerical optimization with ensmallen
• Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning