SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms

Abstract

SARAH and SPIDER are two recently developed stochastic variance-reduced algorithms, and SPIDER has been shown to achieve a near-optimal first-order oracle complexity in smooth nonconvex optimization. However, SPIDER uses an accuracy-dependent stepsize that slows down the convergence in practice, and cannot handle objective functions that involve nonsmooth regularizers. In this paper, we propose SpiderBoost as an improved scheme, which allows to use a much larger constant-level stepsize while maintaining the same near-optimal oracle complexity, and can be extended with proximal mapping to handle composite optimization (which is nonsmooth and nonconvex) with provable convergence guarantee. In particular, we show that proximal SpiderBoost achieves an oracle complexity of $\mathcal{O}(\min \{n^{1/2}{\epsilon }^{-2},{\epsilon }^{-3}\})$ in composite nonconvex optimization, improving the state-of-the-art result by a factor of $\mathcal{O}(\min \{n^{1/6},{\epsilon }^{-1/3}\})$. We further develop a novel momentum scheme to accelerate SpiderBoost for composite optimization, which achieves the near-optimal oracle complexity in theory and substantial improvement in experiments.

arXiv commentAppear in NeurIPS 2019

References in corpus (15)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Stochastic Variance Reduction for Nonconvex Optimization
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Variance Reduction for Faster Non-Convex Optimization
• A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• Convergence Analysis of Proximal Gradient with Momentum for Nonconvex Optimization
• R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
• Characterization of Gradient Dominance and Regularity Conditions for Neural Networks
• ASVRG: Accelerated Proximal SVRG
• Faster Stochastic Alternating Direction Method of Multipliers for Nonconvex Optimization
• Non-asymptotic Analysis of Stochastic Methods for Non-Smooth Non-Convex Regularized Problems
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity

Cited by in corpus (15)

• R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
• Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
• Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexity
• Momentum Schemes with Stochastic Variance Reduction for Nonconvex Composite Optimization
• ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation
• SPRING: A fast stochastic proximal alternating method for non-smooth non-convex optimization
• On Biased Stochastic Gradient Estimation
• Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifold
• FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning
• A General Family of Stochastic Proximal Gradient Methods for Deep Learning
• ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
• Some Limit Properties of Markov Chains Induced by Stochastic Recursive Algorithms
• The perturbed prox-preconditioned spider algorithm: non-asymptotic convergence bounds