Stochastic Recursive Gradient Algorithm for Nonconvex Optimization

Abstract

In this paper, we study and analyze the mini-batch version of StochAstic Recursive grAdient algoritHm (SARAH), a method employing the stochastic recursive gradient, for solving empirical loss minimization for the case of nonconvex losses. We provide a sublinear convergence rate (to stationary points) for general nonconvex functions and a linear convergence rate for gradient dominated functions, both of which have some advantages compared to other modern stochastic gradient algorithms for nonconvex losses.

References in corpus (3)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Stochastic Variance Reduction for Nonconvex Optimization
• Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter

Cited by in corpus (30)

• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Learning the Globally Optimal Distributed LQ Regulator
• ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization
• Stochastic AUC Maximization with Deep Neural Networks
• Momentum-Based Variance Reduction in Non-Convex SGD
• SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
• Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates
• Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexity
• One Sample Stochastic Frank-Wolfe
• Quantized Frank-Wolfe: Faster Optimization, Lower Communication, and Projection Free
• Momentum Schemes with Stochastic Variance Reduction for Nonconvex Composite Optimization
• History-Gradient Aided Batch Size Adaptation for Variance Reduced Algorithms
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learning
• Stochastic Trust Region Methods with Trust Region Radius Depending on Probabilistic Models
• Variance reduction for Riemannian non-convex optimization with batch size adaptation
• On the Acceleration of L-BFGS with Second-Order Information and Stochastic Batches
• Momentum with Variance Reduction for Nonconvex Composition Optimization
• Variance-Reduced Off-Policy Memory-Efficient Policy Search
• Escape saddle points faster on manifolds via perturbed Riemannian stochastic recursive gradient
• Accelerating Mini-batch SARAH by Step Size Rules
• Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent
• Random-reshuffled SARAH does not need a full gradient computations
• Faster Stochastic Quasi-Newton Methods
• Characterization of Excess Risk for Locally Strongly Convex Population Risk
• Faster Perturbed Stochastic Gradient Methods for Finding Local Minima
• DTN: A Learning Rate Scheme with Convergence Rate of $\mathcal{O}(1/t)$ for SGD
• Scalable Projection-Free Optimization
• Stochastic Approximation for Online Tensorial Independent Component Analysis