Fast Stochastic Methods for Nonsmooth Nonconvex Optimization

By Sashank J. Reddi, Suvrit Sra, Barnab'as P'oczos, Alex Smola. 2016

54 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition (2016, methodology): “It is also possible to analyze stochastic proximal-gradient algorithms, and indeed Reddi et al. (2016c) use the proximal-PL inequality to analyze finite-sum methods in the proximal stochastic case. We also note that Zhang (2016) has recently analyzed cyclic coordinate descent for convex functions sa”
A Generic Approach for Escaping Saddle points (2017, background): “[26, 27, 28] proved faster convergence 248 rates that ensure the same optimality criteria in O(n+n/ (2)), which is an order n faster than GD.”
Fast incremental method for smooth nonconvex optimization (2016, methodology): “As a sequel to this paper, we now have extension to proximal nonsmooth nonconvex VR and stochastic Frank-Wolfe VR methods [21], [22].”
Adaptive Methods for Nonconvex Optimization (2018, methodology): “Stochastic methods have also been employed in nonconvex finite-sum problems where stronger results can be shown [41, 24, 26, 27].”
Stochastic Frank-Wolfe methods for nonconvex optimization (2016, methodology): “Such an assumption is common to all Frank-Wolfe methods.”
Non-convex Optimization for Machine Learning (2017, methodology): “The work of Reddi et al. [2016] shows how variance reduction techniques may be exploited to ensure -convergence to a first-order stationary point xt (effectively a saddle point) where we have ∥∥f(xt)∥∥2 ≤ , in no more than O (1/ ) iterations of stochastic mini-batch gradient descent even when the ob”