Fast Incremental Method for Nonconvex Optimization

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

45 citations recorded by the source corpus.

We analyze a fast incremental aggregated gradient method for optimizing nonconvex problems of the form $\min_x \sum_i f_i(x)$. Specifically, we analyze the SAGA algorithm within an Incremental First-order Oracle framework, and show that it converges to a stationary point provably faster than both gradient descent and stochastic gradient descent. We also discuss a Polyak's special class of nonconvex problems for which SAGA converges at a linear rate to the global optimum. Finally, we analyze the practically valuable regularized and minibatch variants of SAGA. To our knowledge, this paper presents the first analysis of fast convergence for an incremental aggregated gradient method for nonconvex problems.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition

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 Computer Vision and Pattern Recognition

Citations in the corpus

Prox-PDA: The Proximal Primal-Dual Algorithm for Fast Distributed Nonconvex Optimization and Learning Over Networks (2017, methodology): “, 2013), and SVRG (Johnson & Zhang, 2013) for convex problems, and (Reddi et al., 2016; Allen-Zhu & Hazan, 2016; Hajinezhad et al., 2016b; Rahimpour et al., 2016) for nonconvex problems.”
Fast Stochastic Methods for Nonsmooth Nonconvex Optimization (2016, methodology): “Theorem (Informal).”
Non-convex Finite-Sum Optimization Via SCSG Methods (2017, background): “Then same phenomenon has also been observed in [26, 27, 4] when b j = 1 and B j = n .”
Stochastic Variance-Reduced Policy Gradient (2018, methodology): “In this scenario, f is typically required to be L -smooth, i.e., (cid:13)(cid:13) ∇ f ( θ Again, SVRG achieves the same rate as FG (Reddi et al., 2016a), which is O ( 1 T ) in this case (Nesterov, 2013).”
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].”
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.”
Stochastic Frank-Wolfe methods for nonconvex optimization (2016, background): “Despite the remarkable success of Fw approaches in the convex setting, including stochastic problems (Hazan and Luo, 2016), their applicability and non-asymptotic convergence for nonconvex optimization is largely unstudied.”