Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization

2020/05/31 by Yangyang Xu, Xu, Yangyang, Xu, Yibo · 3 citations
Computer Science · Engineering · #65K05 #68Q25 #90C15 #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and ELM #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2006.00425

openalex publication_date 2020/05/31 · openalex created_date 2020/06/05 · openalex updated_date 2026/07/28

Abstract

Stochastic gradient methods (SGMs) have been extensively used for solving stochastic problems or large-scale machine learning problems. Recent works employ various techniques to improve the convergence rate of SGMs for both convex and nonconvex cases. Most of them require a large number of samples in some or all iterations of the improved SGMs. In this paper, we propose a new SGM, named PStorm, for solving nonconvex nonsmooth stochastic problems. With a momentum-based variance reduction technique, PStorm can achieve the optimal complexity result O(ε^-3) to produce a stochastic ε-stationary solution, if a mean-squared smoothness condition holds. Different from existing optimal methods, PStorm can achieve the O(ε^-3) result by using only one or O(1) samples in every update. With this property, PStorm can be applied to online learning problems that favor real-time decisions based on one or O(1) new observations. In addition, for large-scale machine learning problems, PStorm can generalize better by small-batch training than other optimal methods that require large-batch training and the vanilla SGM, as we demonstrate on training a sparse fully-connected neural network and a sparse convolutional neural network.

Citations

• A Stochastic Approximation Method
• Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
• Gradient-based learning applied to document recognition
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp\n Minima
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
• Learning Multiple Layers of Features from Tiny Images
• Parallel and distributed asynchronous adaptive stochastic gradient methods

Cited by

• DualHash: A Stochastic Primal-Dual Algorithm with Theoretical Guarantee for Deep Hashing
• A Proximal Stochastic Gradient Method with Adaptive Step Size and Variance Reduction for Convex Composite Optimization
• Compressed Decentralized Momentum Stochastic Gradient Methods for Nonconvex Optimization

Related

• Momentum Schemes with Stochastic Variance Reduction for Nonconvex Composite Optimization
• An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite Nonconvex Optimization
• ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization
• Stochastic Variance Reduction Gradient for a Non-convex Problem Using Graduated Optimization
• Momentum-Based Variance Reduction in Non-Convex SGD