@inproceedings{545e3346948c40c49dc99f74ed6d164d,

title = "Finding approximate local minima faster than gradient descent",

abstract = "We design a non-convex second-order optimization algorithm that is guaranteed to return an approximate local minimum in time which scales linearly in the underlying dimension and the number of training examples. The time complexity of our algorithm to find an approximate local minimum is even faster than that of gradient descent to find a critical point. Our algorithm applies to a general class of optimization problems including training a neural network and other non-convex objectives arising in machine learning.",

keywords = "Cubic regularization, Deep learning, Non-convex optimization, Second-order optimization",

author = "Naman Agarwal and Zeyuan Allen-Zhu and Brian Bullins and Elad Hazan and Tengyu Ma",

note = "Funding Information: The full version of the paper is available at https://arxiv.org/abs/1611.01146. Z. Allen-Zhuis partially supported an NSF Grant, no. CCF-1412958, and a Microsoft Research Grant, no. 0518584. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of NSF or Microsoft.; 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 ; Conference date: 19-06-2017 Through 23-06-2017",

year = "2017",

month = jun,

day = "19",

doi = "10.1145/3055399.3055464",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "1195--1199",

editor = "Pierre McKenzie and Valerie King and Hamed Hatami",

booktitle = "STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing",

}