TY - GEN
T1 - Fast incremental method for smooth nonconvex optimization
AU - Reddi, Sashank J.
AU - Sra, Suvrit
AU - Póczos, Barnabás
AU - Smola, Alex
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/12/27
Y1 - 2016/12/27
N2 - We analyze a fast incremental aggregated gradient method for optimizing nonconvex problems of the form minΣi fi(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.
AB - We analyze a fast incremental aggregated gradient method for optimizing nonconvex problems of the form minΣi fi(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.
UR - http://www.scopus.com/inward/record.url?scp=85010764243&partnerID=8YFLogxK
U2 - 10.1109/CDC.2016.7798553
DO - 10.1109/CDC.2016.7798553
M3 - Conference contribution
AN - SCOPUS:85010764243
T3 - 2016 IEEE 55th Conference on Decision and Control, CDC 2016
SP - 1971
EP - 1977
BT - 2016 IEEE 55th Conference on Decision and Control, CDC 2016
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 55th IEEE Conference on Decision and Control, CDC 2016
Y2 - 12 December 2016 through 14 December 2016
ER -