A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization

Abstract

We analyze stochastic gradient algorithms for optimizing nonconvex, nonsmooth finite-sum problems. In particular, the objective function is given by the summation of a differentiable (possibly nonconvex) component, together with a possibly non-differentiable but convex component. We propose a proximal stochastic gradient algorithm based on variance reduction, called ProxSVRG+. Our main contribution lies in the analysis of ProxSVRG+. It recovers several existing convergence results and improves/generalizes them (in terms of the number of stochastic gradient oracle calls and proximal oracle calls). In particular, ProxSVRG+ generalizes the best results given by the SCSG algorithm, recently proposed by [Lei et al., 2017] for the smooth nonconvex case. ProxSVRG+ is also more straightforward than SCSG and yields simpler analysis. Moreover, ProxSVRG+ outperforms the deterministic proximal gradient descent (ProxGD) for a wide range of minibatch sizes, which partially solves an open problem proposed in [Reddi et al., 2016b]. Also, ProxSVRG+ uses much less proximal oracle calls than ProxSVRG [Reddi et al., 2016b]. Moreover, for nonconvex functions satisfied Polyak-Łojasiewicz condition, we prove that ProxSVRG+ achieves a global linear convergence rate without restart unlike ProxSVRG. Thus, it can \emph{automatically} switch to the faster linear convergence in some regions as long as the objective function satisfies the PL condition locally in these regions. ProxSVRG+ also improves ProxGD and ProxSVRG/SAGA, and generalizes the results of SCSG in this case. Finally, we conduct several experiments and the experimental results are consistent with the theoretical results.

32nd Conference on Neural Information Processing Systems (NeurIPS 2018)

References in corpus (9)

• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Recovery Guarantees for One-hidden-layer Neural Networks
• Stochastic Nested Variance Reduction for Nonconvex Optimization
• Convergence Analysis of Proximal Gradient with Momentum for Nonconvex Optimization
• An optimal randomized incremental gradient method
• Global Convergence of Arbitrary-Block Gradient Methods for Generalized Polyak-Łojasiewicz Functions
• A SMART Stochastic Algorithm for Nonconvex Optimization with Applications to Robust Machine Learning

Cited by in corpus (24)

• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• Stochastic AUC Maximization with Deep Neural Networks
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation
• History-Gradient Aided Batch Size Adaptation for Variance Reduced Algorithms
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
• Provably Faster Algorithms for Bilevel Optimization
• Simple Stochastic Gradient Methods for Non-Smooth Non-Convex Regularized Optimization
• ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
• A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learning
• Stochastic Gradient Hamiltonian Monte Carlo with Variance Reduction for Bayesian Inference
• Asynchronous Optimization Methods for Efficient Training of Deep Neural Networks with Guarantees
• Variance Reduction on General Adaptive Stochastic Mirror Descent
• Half-Space Proximal Stochastic Gradient Method for Group-Sparsity Regularized Problem
• Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learning
• A Fast Anderson-Chebyshev Acceleration for Nonlinear Optimization
• Stochastic Proximal Methods for Non-Smooth Non-Convex Constrained Sparse Optimization
• Effective Proximal Methods for Non-convex Non-smooth Regularized Learning
• Why Does Multi-Epoch Training Help?
• A Theoretical Analysis of Learning with Noisily Labeled Data
• An Elementary Approach to Convergence Guarantees of Optimization Algorithms for Deep Networks