Fast Stochastic Methods for Nonsmooth Nonconvex Optimization

Abstract

We analyze stochastic algorithms for optimizing nonconvex, nonsmooth finite-sum problems, where the nonconvex part is smooth and the nonsmooth part is convex. Surprisingly, unlike the smooth case, our knowledge of this fundamental problem is very limited. For example, it is not known whether the proximal stochastic gradient method with constant minibatch converges to a stationary point. To tackle this issue, we develop fast stochastic algorithms that provably converge to a stationary point for constant minibatches. Furthermore, using a variant of these algorithms, we show provably faster convergence than batch proximal gradient descent. Finally, we prove global linear convergence rate for an interesting subclass of nonsmooth nonconvex functions, that subsumes several recent works. This paper builds upon our recent series of papers on fast stochastic methods for smooth nonconvex optimization [22, 23], with a novel analysis for nonconvex and nonsmooth functions.

References in corpus (6)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Stochastic Variance Reduction for Nonconvex Optimization
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• A Lower Bound for the Optimization of Finite Sums
• Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
• Fast Incremental Method for Nonconvex Optimization

Cited by in corpus (14)

• Non-convex Optimization for Machine Learning
• A SMART Stochastic Algorithm for Nonconvex Optimization with Applications to Robust Machine Learning
• Zeroth-order Asynchronous Doubly Stochastic Algorithm with Variance Reduction
• Mini-Batch Stochastic ADMMs for Nonconvex Nonsmooth Optimization
• Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis
• On Biased Stochastic Gradient Estimation
• A Convergence Analysis for A Class of Practical Variance-Reduction Stochastic Gradient MCMC
• Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity
• Stochastic Trust Region Methods with Trust Region Radius Depending on Probabilistic Models
• Distributed Asynchronous Dual Free Stochastic Dual Coordinate Ascent
• Submodular Norms with Applications To Online Facility Location and Stochastic Probing
• Linear convergence of SDCA in statistical estimation
• SAGA and Restricted Strong Convexity
• Training L1-Regularized Models with Orthant-Wise Passive Descent Algorithms