Stochastic cubic regularization for fast nonconvex optimization

Nilesh Tripuraneni; Mitchell Stern; Chi Jin; Jeffrey Regier; Michael I. Jordan

Stochastic cubic regularization for fast nonconvex optimization

Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, Michael I. Jordan

Research output: Contribution to journal › Conference article › peer-review

Abstract

This paper proposes a stochastic variant of a classic algorithm-the cubic-regularized Newton method [Nesterov and Polyak, 2006]. The proposed algorithm efficiently escapes saddle points and finds approximate local minima for general smooth, nonconvex functions in only Õ(^3.5) stochastic gradient and stochastic Hessian-vector product evaluations. The latter can be computed as efficiently as stochastic gradients. This improves upon the Õ(⁴) rate of stochastic gradient descent. Our rate matches the best-known result for finding local minima without requiring any delicate acceleration or variance-reduction techniques.

Original language	English (US)
Pages (from-to)	2899-2908
Number of pages	10
Journal	Advances in Neural Information Processing Systems
Volume	2018-December
State	Published - 2018
Externally published	Yes
Event	32nd Conference on Neural Information Processing Systems, NeurIPS 2018 - Montreal, Canada Duration: Dec 2 2018 → Dec 8 2018

All Science Journal Classification (ASJC) codes

Computer Networks and Communications
Information Systems
Signal Processing

Cite this

@article{be4da0b5fa3a49b8bb8bd19d7d57cf8d,

title = "Stochastic cubic regularization for fast nonconvex optimization",

abstract = "This paper proposes a stochastic variant of a classic algorithm-the cubic-regularized Newton method [Nesterov and Polyak, 2006]. The proposed algorithm efficiently escapes saddle points and finds approximate local minima for general smooth, nonconvex functions in only {\~O}(3.5) stochastic gradient and stochastic Hessian-vector product evaluations. The latter can be computed as efficiently as stochastic gradients. This improves upon the {\~O}(4) rate of stochastic gradient descent. Our rate matches the best-known result for finding local minima without requiring any delicate acceleration or variance-reduction techniques.",

author = "Nilesh Tripuraneni and Mitchell Stern and Chi Jin and Jeffrey Regier and Jordan, \{Michael I.\}",

note = "Publisher Copyright: {\textcopyright} 2018 Curran Associates Inc.All rights reserved.; 32nd Conference on Neural Information Processing Systems, NeurIPS 2018 ; Conference date: 02-12-2018 Through 08-12-2018",

year = "2018",

language = "English (US)",

volume = "2018-December",

pages = "2899--2908",

journal = "Advances in Neural Information Processing Systems",

issn = "1049-5258",

publisher = "Neural information processing systems foundation",

}

TY - JOUR

T1 - Stochastic cubic regularization for fast nonconvex optimization

AU - Tripuraneni, Nilesh

AU - Stern, Mitchell

AU - Jin, Chi

AU - Regier, Jeffrey

AU - Jordan, Michael I.

PY - 2018

Y1 - 2018

N2 - This paper proposes a stochastic variant of a classic algorithm-the cubic-regularized Newton method [Nesterov and Polyak, 2006]. The proposed algorithm efficiently escapes saddle points and finds approximate local minima for general smooth, nonconvex functions in only Õ(3.5) stochastic gradient and stochastic Hessian-vector product evaluations. The latter can be computed as efficiently as stochastic gradients. This improves upon the Õ(4) rate of stochastic gradient descent. Our rate matches the best-known result for finding local minima without requiring any delicate acceleration or variance-reduction techniques.

AB - This paper proposes a stochastic variant of a classic algorithm-the cubic-regularized Newton method [Nesterov and Polyak, 2006]. The proposed algorithm efficiently escapes saddle points and finds approximate local minima for general smooth, nonconvex functions in only Õ(3.5) stochastic gradient and stochastic Hessian-vector product evaluations. The latter can be computed as efficiently as stochastic gradients. This improves upon the Õ(4) rate of stochastic gradient descent. Our rate matches the best-known result for finding local minima without requiring any delicate acceleration or variance-reduction techniques.

UR - https://www.scopus.com/pages/publications/85064841037

UR - https://www.scopus.com/inward/citedby.url?scp=85064841037&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85064841037

SN - 1049-5258

VL - 2018-December

SP - 2899

EP - 2908

JO - Advances in Neural Information Processing Systems

JF - Advances in Neural Information Processing Systems

T2 - 32nd Conference on Neural Information Processing Systems, NeurIPS 2018

Y2 - 2 December 2018 through 8 December 2018

ER -

Stochastic cubic regularization for fast nonconvex optimization

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this