{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T14:36:25Z","timestamp":1778337385935,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055464","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T20:27:45Z","timestamp":1497558465000},"page":"1195-1199","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":58,"title":["Finding approximate local minima faster than gradient descent"],"prefix":"10.1145","author":[{"given":"Naman","family":"Agarwal","sequence":"first","affiliation":[{"name":"Princeton University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zeyuan","family":"Allen-Zhu","sequence":"additional","affiliation":[{"name":"IAS, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Brian","family":"Bullins","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elad","family":"Hazan","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tengyu","family":"Ma","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"Naman Agarwal Brian Bullins and Elad Hazan. Second order stochastic optimization for machine learning in linear time. arXiv preprint arXiv:1602.03943 2016.  Naman Agarwal Brian Bullins and Elad Hazan. Second order stochastic optimization for machine learning in linear time. arXiv preprint arXiv:1602.03943 2016."},{"key":"e_1_3_2_2_2_1","unstructured":"Zeyuan Allen-Zhu. Natasha: Faster Stochastic Non-Convex Optimization via Strongly Non-Convex Parameter. ArXiv e-prints abs\/1702.00763 February 2017.  Zeyuan Allen-Zhu. Natasha: Faster Stochastic Non-Convex Optimization via Strongly Non-Convex Parameter. ArXiv e-prints abs\/1702.00763 February 2017."},{"key":"e_1_3_2_2_3_1","volume-title":"ICML","author":"Allen-Zhu Zeyuan","year":"2016"},{"key":"e_1_3_2_2_4_1","unstructured":"Afonso S Bandeira Nicolas Boumal and Vladislav Voroninski. On the low-rank approach for semidefinite programs arising in synchronization and community detection. arXiv preprint arXiv:1602.04426 2016.  Afonso S Bandeira Nicolas Boumal and Vladislav Voroninski. On the low-rank approach for semidefinite programs arising in synchronization and community detection. arXiv preprint arXiv:1602.04426 2016."},{"key":"e_1_3_2_2_5_1","unstructured":"S. Bhojanapalli B. Neyshabur and N. Srebro. Global Optimality of Local Search for Low Rank Matrix Recovery. ArXiv e-prints May 2016.  S. Bhojanapalli B. Neyshabur and N. Srebro. Global Optimality of Local Search for Low Rank Matrix Recovery. ArXiv e-prints May 2016."},{"key":"e_1_3_2_2_6_1","unstructured":"Yair Carmon John C. Duchi Oliver Hinder and Aaron Sidford. Accelerated methods for non-convex optimization. arXiv preprint 1611.00756 2016.  Yair Carmon John C. Duchi Oliver Hinder and Aaron Sidford. Accelerated methods for non-convex optimization. arXiv preprint 1611.00756 2016."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1966622.1966624"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055464"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0337-y"},{"key":"e_1_3_2_2_10_1","volume-title":"AISTATS","author":"Choromanska Anna","year":"2015"},{"key":"e_1_3_2_2_11_1","first-page":"2941","volume-title":"Advances in neural information processing systems","author":"Dauphin Yann N","year":"2014"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2021068"},{"key":"e_1_3_2_2_13_1","unstructured":"Dan Garber and Elad Hazan. Fast and simple PCA via convex optimization. ArXiv e-prints September 2015.  Dan Garber and Elad Hazan. Fast and simple PCA via convex optimization. ArXiv e-prints September 2015."},{"key":"e_1_3_2_2_14_1","volume-title":"ICML","author":"Garber Dan","year":"2016"},{"key":"e_1_3_2_2_15_1","unstructured":"Rong Ge Furong Huang Chi Jin and Yang Yuan. Escaping from saddle points\u2014 online stochastic gradient for tensor decomposition. arXiv:1503.02101 2015.  Rong Ge Furong Huang Chi Jin and Yang Yuan. Escaping from saddle points\u2014 online stochastic gradient for tensor decomposition. arXiv:1503.02101 2015."},{"key":"e_1_3_2_2_16_1","volume-title":"Proceedings of the 28th Annual Conference on Learning Theory, COLT 2015","author":"Ge Rong","year":"2015"},{"key":"e_1_3_2_2_17_1","first-page":"842","volume-title":"Proceedings of The 28th Conference on Learning Theory, COLT 2015","author":"Ge Rong","year":"2015"},{"key":"e_1_3_2_2_18_1","unstructured":"Rong Ge Jason Lee and Tengyu Ma. Matrix Completion has No Spurious Local Minimum. ArXiv e-prints May 2016.  Rong Ge Jason Lee and Tengyu Ma. Matrix Completion has No Spurious Local Minimum. ArXiv e-prints May 2016."},{"key":"e_1_3_2_2_19_1","unstructured":"Rong Ge and Tengyu Ma. On the optimization landscape of tensor decompositions 2016.  Rong Ge and Tengyu Ma. On the optimization landscape of tensor decompositions 2016."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0871-8"},{"key":"e_1_3_2_2_21_1","unstructured":"I. J. Goodfellow O. Vinyals and A. M. Saxe. Qualitatively characterizing neural network optimization problems. ArXiv e-prints December 2014.  I. J. Goodfellow O. Vinyals and A. M. Saxe. Qualitatively characterizing neural network optimization problems. ArXiv e-prints December 2014."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0933-y"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512329"},{"key":"e_1_3_2_2_24_1","first-page":"1257","volume-title":"Proceedings of the 29th Conference on Learning Theory, COLT 2016","author":"Lee Jason D.","year":"2016"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592948"},{"key":"e_1_3_2_2_26_1","first-page":"547","volume-title":"Doklady AN SSSR (translated as Soviet Mathematics Doklady)","author":"Nesterov Yurii","year":"1983"},{"key":"e_1_3_2_2_27_1","volume-title":"Kluwer Academic Publishers","author":"Nesterov Yurii","year":"2004"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/3112681.3113165"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1994.6.1.147"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"crossref","unstructured":"Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics pages 400\u2013407 1951.  Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics pages 400\u2013407 1951.","DOI":"10.1214\/aoms\/1177729586"},{"key":"e_1_3_2_2_31_1","unstructured":"Mark Schmidt Nicolas Le Roux and Francis Bach. Minimizing finite sums with the stochastic average gradient. arXiv preprint arXiv:1309.2388 pages 1\u201345 2013.  Mark Schmidt Nicolas Le Roux and Francis Bach. Minimizing finite sums with the stochastic average gradient. arXiv preprint arXiv:1309.2388 pages 1\u201345 2013."},{"key":"e_1_3_2_2_32_1","unstructured":"Preliminary version appeared in NIPS 2012.  Preliminary version appeared in NIPS 2012."},{"key":"e_1_3_2_2_33_1","unstructured":"Jonathan Richard Shewchuk. An introduction to the conjugate gradient method without the agonizing pain 1994.  Jonathan Richard Shewchuk. An introduction to the conjugate gradient method without the agonizing pain 1994."},{"key":"e_1_3_2_2_34_1","unstructured":"Abstract 1 Introduction 1.1 Related Work 1.2 Our Techniques 2 Preliminaries and Main Theorem 2.1 Main Results 3 Our Fast Cubic Regularization Algorithm 4 Further Details References  Abstract 1 Introduction 1.1 Related Work 1.2 Our Techniques 2 Preliminaries and Main Theorem 2.1 Main Results 3 Our Fast Cubic Regularization Algorithm 4 Further Details References"}],"event":{"name":"STOC '17: Symposium on Theory of Computing","location":"Montreal Canada","acronym":"STOC '17","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055464","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055464","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:19Z","timestamp":1750217779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055464"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":34,"alternative-id":["10.1145\/3055399.3055464","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055464","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}