Fast incremental method for smooth nonconvex optimization

Sashank J. Reddi; Suvrit Sra; Barnabás Póczos; Alex Smola

doi:10.1109/CDC.2016.7798553

Fast incremental method for smooth nonconvex optimization

Sashank J. Reddi, Suvrit Sra, Barnabás Póczos, Alex Smola

Publikation: Beitrag in Buch/Bericht/Konferenzband › Konferenzbeitrag › Begutachtung

44 Zitate (Scopus)

Abstract

We analyze a fast incremental aggregated gradient method for optimizing nonconvex problems of the form minΣ_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.

Originalsprache	Englisch
Titel	2016 IEEE 55th Conference on Decision and Control, CDC 2016
Herausgeber (Verlag)	Institute of Electrical and Electronics Engineers Inc.
Seiten	1971-1977
Seitenumfang	7
ISBN (elektronisch)	9781509018376
DOIs	https://doi.org/10.1109/CDC.2016.7798553
Publikationsstatus	Veröffentlicht - 27 Dez. 2016
Extern publiziert	Ja
Veranstaltung	55th IEEE Conference on Decision and Control, CDC 2016 - Las Vegas, USA/Vereinigte Staaten Dauer: 12 Dez. 2016 → 14 Dez. 2016

Publikationsreihe

Name	2016 IEEE 55th Conference on Decision and Control, CDC 2016

Konferenz

Konferenz	55th IEEE Conference on Decision and Control, CDC 2016
Land/Gebiet	USA/Vereinigte Staaten
Ort	Las Vegas
Zeitraum	12/12/16 → 14/12/16

Zugriff auf Dokument

10.1109/CDC.2016.7798553

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

Dieses zitieren

@inproceedings{9018f6037e5540739cdeb51036ba86bb,

title = "Fast incremental method for smooth nonconvex optimization",

abstract = "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.",

author = "Reddi, {Sashank J.} and Suvrit Sra and Barnab{\'a}s P{\'o}czos and Alex Smola",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 55th IEEE Conference on Decision and Control, CDC 2016 ; Conference date: 12-12-2016 Through 14-12-2016",

year = "2016",

month = dec,

day = "27",

doi = "10.1109/CDC.2016.7798553",

language = "English",

series = "2016 IEEE 55th Conference on Decision and Control, CDC 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1971--1977",

booktitle = "2016 IEEE 55th Conference on Decision and Control, CDC 2016",

}

Reddi, SJ, Sra, S, Póczos, B & Smola, A 2016, Fast incremental method for smooth nonconvex optimization. in 2016 IEEE 55th Conference on Decision and Control, CDC 2016., 7798553, 2016 IEEE 55th Conference on Decision and Control, CDC 2016, Institute of Electrical and Electronics Engineers Inc., S. 1971-1977, 55th IEEE Conference on Decision and Control, CDC 2016, Las Vegas, USA/Vereinigte Staaten, 12/12/16. https://doi.org/10.1109/CDC.2016.7798553

Fast incremental method for smooth nonconvex optimization. / Reddi, Sashank J.; Sra, Suvrit; Póczos, Barnabás et al.
2016 IEEE 55th Conference on Decision and Control, CDC 2016. Institute of Electrical and Electronics Engineers Inc., 2016. S. 1971-1977 7798553 (2016 IEEE 55th Conference on Decision and Control, CDC 2016).

Publikation: Beitrag in Buch/Bericht/Konferenzband › Konferenzbeitrag › Begutachtung

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

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 -

Fast incremental method for smooth nonconvex optimization

Abstract

Publikationsreihe

Konferenz

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Dieses zitieren