{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T20:29:51Z","timestamp":1792787391442,"version":"4.5.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,2,24]],"date-time":"2021-02-24T00:00:00Z","timestamp":1614124800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Mathematical Data Science program of the Office of Naval Research","award":["N00014-18-1-2764"],"award-info":[{"award-number":["N00014-18-1-2764"]}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1704656"],"award-info":[{"award-number":["CCF-1704656"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,4,30]]},"abstract":"<jats:p>\n                    Gradient descent (GD) and stochastic gradient descent (SGD) are the workhorses of large-scale machine learning. While classical theory focused on analyzing the performance of these methods in\n                    <jats:italic>convex<\/jats:italic>\n                    optimization problems, the most notable successes in machine learning have involved\n                    <jats:italic>nonconvex<\/jats:italic>\n                    optimization, and a gap has arisen between theory and practice. Indeed, traditional analyses of GD and SGD show that both algorithms converge to stationary points efficiently. But these analyses do not take into account the possibility of converging to saddle points. More recent theory has shown that GD and SGD can avoid saddle points, but the dependence on dimension in these analyses is polynomial. For modern machine learning, where the dimension can be in the millions, such dependence would be catastrophic. We analyze perturbed versions of GD and SGD and show that they are truly efficient\u2014their dimension dependence is only polylogarithmic. Indeed, these algorithms converge to second-order stationary points in essentially the same time as they take to converge to classical first-order stationary points.\n                  <\/jats:p>","DOI":"10.1145\/3418526","type":"journal-article","created":{"date-parts":[[2021,2,24]],"date-time":"2021-02-24T06:14:47Z","timestamp":1614147287000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":73,"title":["On Nonconvex Optimization for Machine Learning"],"prefix":"10.1145","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2865-5610","authenticated-orcid":false,"given":"Chi","family":"Jin","sequence":"first","affiliation":[{"name":"University of California, Berkeley, California, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Praneeth","family":"Netrapalli","sequence":"additional","affiliation":[{"name":"Microsoft Research, Bengaluru, Karnataka, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rong","family":"Ge","sequence":"additional","affiliation":[{"name":"Duke University, North Carolina, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sham M.","family":"Kakade","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, Washington, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael I.","family":"Jordan","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, California, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,2,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055464"},{"key":"e_1_2_1_2_1","unstructured":"Zeyuan Allen-Zhu. 2018. Natasha 2: Faster non-convex optimization than SGD. In Advances in Neural Information Processing Systems. 2680--2691.  Zeyuan Allen-Zhu. 2018. Natasha 2: Faster non-convex optimization than SGD. In Advances in Neural Information Processing Systems. 2680--2691."},{"key":"e_1_2_1_3_1","unstructured":"Zeyuan Allen-Zhu and Yuanzhi Li. 2018. Neon2: Finding local minima via first-order oracles. In Advances in Neural Information Processing Systems. 3716--3726.  Zeyuan Allen-Zhu and Yuanzhi Li. 2018. Neon2: Finding local minima via first-order oracles. In Advances in Neural Information Processing Systems. 3716--3726."},{"key":"e_1_2_1_4_1","volume-title":"Conference on Learning Theory. 81--102","author":"Anandkumar Animashree","year":"2016","unstructured":"Animashree Anandkumar and Rong Ge . 2016 . Efficient approaches for escaping higher-order saddle points in non-convex optimization . In Conference on Learning Theory. 81--102 . Animashree Anandkumar and Rong Ge. 2016. Efficient approaches for escaping higher-order saddle points in non-convex optimization. In Conference on Learning Theory. 81--102."},{"key":"e_1_2_1_5_1","volume-title":"Conference on Learning Theory.","author":"Arjevani Yossi","year":"2020","unstructured":"Yossi Arjevani , Yair Carmon , John C Duchi , Dylan J Foster , Ayush Sekhari , and Karthik Sridharan . 2020 . Second-order information in non-convex stochastic optimization: Power and limitations . In Conference on Learning Theory. Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridharan. 2020. Second-order information in non-convex stochastic optimization: Power and limitations. In Conference on Learning Theory."},{"key":"e_1_2_1_6_1","volume-title":"Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv:1912.02365","author":"Arjevani Yossi","year":"2019","unstructured":"Yossi Arjevani , Yair Carmon , John C. Duchi , Dylan J. Foster , Nathan Srebro , and Blake Woodworth . 2019. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv:1912.02365 ( 2019 ). Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. 2019. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv:1912.02365 (2019)."},{"key":"e_1_2_1_7_1","volume-title":"Conference on Learning Theory. 361--382","author":"Bandeira Afonso S.","year":"2016","unstructured":"Afonso S. Bandeira , Nicolas Boumal , and Vladislav Voroninski . 2016 . On the low-rank approach for semidefinite programs arising in synchronization and community detection . In Conference on Learning Theory. 361--382 . Afonso S. Bandeira, Nicolas Boumal, and Vladislav Voroninski. 2016. On the low-rank approach for semidefinite programs arising in synchronization and community detection. In Conference on Learning Theory. 361--382."},{"key":"e_1_2_1_8_1","unstructured":"Srinadh Bhojanapalli Behnam Neyshabur and Nati Srebro. 2016. Global optimality of local search for low rank matrix recovery. In Advances in Neural Information Processing Systems. 3873--3881.  Srinadh Bhojanapalli Behnam Neyshabur and Nati Srebro. 2016. Global optimality of local search for low rank matrix recovery. In Advances in Neural Information Processing Systems. 3873--3881."},{"key":"e_1_2_1_9_1","unstructured":"Nicolas Boumal Vlad Voroninski and Afonso Bandeira. 2016. The non-convex Burer-Monteiro approach works on smooth semidefinite programs. In Advances in Neural Information Processing Systems. 2757--2765.  Nicolas Boumal Vlad Voroninski and Afonso Bandeira. 2016. The non-convex Burer-Monteiro approach works on smooth semidefinite programs. In Advances in Neural Information Processing Systems. 2757--2765."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4171\/JEMS\/14"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1113898"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1114296"},{"key":"e_1_2_1_13_1","volume-title":"Lower bounds for finding stationary points I. Mathematical Programming","author":"Carmon Yair","year":"2019","unstructured":"Yair Carmon , John C. Duchi , Oliver Hinder , and Aaron Sidford . 2019. Lower bounds for finding stationary points I. Mathematical Programming ( 2019 ). Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. 2019. Lower bounds for finding stationary points I. Mathematical Programming (2019)."},{"key":"e_1_2_1_14_1","volume-title":"Lower bounds for finding stationary points II: First-order methods. Mathematical Programming","author":"Carmon Yair","year":"2019","unstructured":"Yair Carmon , John C. Duchi , Oliver Hinder , and Aaron Sidford . 2019. Lower bounds for finding stationary points II: First-order methods. Mathematical Programming ( 2019 ). Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. 2019. Lower bounds for finding stationary points II: First-order methods. Mathematical Programming (2019)."},{"key":"e_1_2_1_15_1","volume-title":"M\u00e9thode g\u00e9n\u00e9rale pour la r\u00e9solution des syst\u00e9mes d\u2019\u00e9quations simultanees. C. R. Acad. Sci. Paris","author":"Cauchy Louis Augustin","year":"1847","unstructured":"Louis Augustin Cauchy . 1847. M\u00e9thode g\u00e9n\u00e9rale pour la r\u00e9solution des syst\u00e9mes d\u2019\u00e9quations simultanees. C. R. Acad. Sci. Paris ( 1847 ). Louis Augustin Cauchy. 1847. M\u00e9thode g\u00e9n\u00e9rale pour la r\u00e9solution des syst\u00e9mes d\u2019\u00e9quations simultanees. C. R. Acad. Sci. Paris (1847)."},{"key":"e_1_2_1_16_1","volume-title":"International Conference on Artificial Intelligence and Statistics (AISTATS).","author":"Choromanska Anna","year":"2015","unstructured":"Anna Choromanska , Mikael Henaff , Michael Mathieu , G\u00e9rard Ben Arous , and Yann LeCun . 2015 . The loss surface of multilayer networks . In International Conference on Artificial Intelligence and Statistics (AISTATS). Anna Choromanska, Mikael Henaff, Michael Mathieu, G\u00e9rard Ben Arous, and Yann LeCun. 2015. The loss surface of multilayer networks. In International Conference on Artificial Intelligence and Statistics (AISTATS)."},{"key":"e_1_2_1_17_1","volume-title":"A trust region algorithm with a worst-case iteration complexity of O(&epsi;&minus;3\/2) for nonconvex optimization. Mathematical Programming","author":"Curtis Frank E","year":"2014","unstructured":"Frank E Curtis , Daniel P Robinson , and Mohammadreza Samadi . 2014. A trust region algorithm with a worst-case iteration complexity of O(&epsi;&minus;3\/2) for nonconvex optimization. Mathematical Programming ( 2014 ), 1--32. Frank E Curtis, Daniel P Robinson, and Mohammadreza Samadi. 2014. A trust region algorithm with a worst-case iteration complexity of O(&epsi;&minus;3\/2) for nonconvex optimization. Mathematical Programming (2014), 1--32."},{"key":"e_1_2_1_18_1","volume-title":"International Conference on Machine Learning.","author":"Daneshmand Hadi","year":"2018","unstructured":"Hadi Daneshmand , Jonas Kohler , Aurelien Lucchi , and Thomas Hofmann . 2018 . Escaping saddles with stochastic gradients . In International Conference on Machine Learning. Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, and Thomas Hofmann. 2018. Escaping saddles with stochastic gradients. In International Conference on Machine Learning."},{"key":"e_1_2_1_19_1","unstructured":"Simon S Du Chi Jin Jason D Lee Michael I Jordan Aarti Singh and Barnabas Poczos. 2017. Gradient descent can take exponential time to escape saddle points. In Advances in Neural Information Processing Systems. 1067--1077.  Simon S Du Chi Jin Jason D Lee Michael I Jordan Aarti Singh and Barnabas Poczos. 2017. Gradient descent can take exponential time to escape saddle points. In Advances in Neural Information Processing Systems. 1067--1077."},{"key":"e_1_2_1_20_1","volume-title":"Zhouchen Lin, and Tong Zhang.","author":"Fang Cong","year":"2018","unstructured":"Cong Fang , Chris Junchi Li , Zhouchen Lin, and Tong Zhang. 2018 . Spider : Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems . 687--697. Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. 2018. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems. 687--697."},{"key":"e_1_2_1_21_1","volume-title":"Sharp analysis for nonconvex SGD escaping from saddle points. arXiv preprint arXiv:1902.00247","author":"Fang Cong","year":"2019","unstructured":"Cong Fang , Zhouchen Lin , and Tong Zhang . 2019. Sharp analysis for nonconvex SGD escaping from saddle points. arXiv preprint arXiv:1902.00247 ( 2019 ). Cong Fang, Zhouchen Lin, and Tong Zhang. 2019. Sharp analysis for nonconvex SGD escaping from saddle points. arXiv preprint arXiv:1902.00247 (2019)."},{"key":"e_1_2_1_22_1","volume-title":"Conference on Computational Learning Theory (COLT).","author":"Ge Rong","year":"2015","unstructured":"Rong Ge , Furong Huang , Chi Jin , and Yang Yuan . 2015 . Escaping from saddle points\u2014Online stochastic gradient for tensor decomposition . In Conference on Computational Learning Theory (COLT). Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. 2015. Escaping from saddle points\u2014Online stochastic gradient for tensor decomposition. In Conference on Computational Learning Theory (COLT)."},{"key":"e_1_2_1_23_1","volume-title":"International Conference on Machine Learning (ICML).","author":"Ge Rong","year":"2017","unstructured":"Rong Ge , Chi Jin , and Yi Zheng . 2017 . No spurious local minima in nonconvex low rank problems: A unified geometric analysis . In International Conference on Machine Learning (ICML). Rong Ge, Chi Jin, and Yi Zheng. 2017. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning (ICML)."},{"key":"e_1_2_1_24_1","unstructured":"Rong Ge Jason D. Lee and Tengyu Ma. 2016. Matrix completion has no spurious local minimum. In Advances in Neural Information Processing Systems. 2973--2981.  Rong Ge Jason D. Lee and Tengyu Ma. 2016. Matrix completion has no spurious local minimum. In Advances in Neural Information Processing Systems. 2973--2981."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/120880811"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488693"},{"key":"e_1_2_1_27_1","volume-title":"International Conference on Machine Learning (ICML).","author":"Jin Chi","unstructured":"Chi Jin , Rong Ge , Praneeth Netrapalli , Sham M. Kakade , and Michael I. Jordan . 2017. How to escape saddle points efficiently . In International Conference on Machine Learning (ICML). Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael I. Jordan. 2017. How to escape saddle points efficiently. In International Conference on Machine Learning (ICML)."},{"key":"e_1_2_1_28_1","volume-title":"Jordan","author":"Jin Chi","year":"2019","unstructured":"Chi Jin , Praneeth Netrapalli , Rong Ge , Sham M. Kakade , and Michael I . Jordan . 2019 . A short note on concentration inequalities for random vectors with subGaussian norm. arXiv preprint arXiv:1902.03736 (2019). Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M. Kakade, and Michael I. Jordan. 2019. A short note on concentration inequalities for random vectors with subGaussian norm. arXiv preprint arXiv:1902.03736 (2019)."},{"key":"e_1_2_1_29_1","volume-title":"Conference of Learning Theory (COLT).","author":"Jin Chi","unstructured":"Chi Jin , Praneeth Netrapalli , and Michael I. Jordan . 2018. Accelerated gradient descent escapes saddle points faster than gradient descent . In Conference of Learning Theory (COLT). Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. 2018. Accelerated gradient descent escapes saddle points faster than gradient descent. In Conference of Learning Theory (COLT)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1255-7"},{"key":"e_1_2_1_31_1","volume-title":"Conference on Learning Theory. 1246--1257","author":"Lee Jason D","year":"2016","unstructured":"Jason D Lee , Max Simchowitz , Michael I Jordan , and Benjamin Recht . 2016 . Gradient descent only converges to minimizers . In Conference on Learning Theory. 1246--1257 . Jason D Lee, Max Simchowitz, Michael I Jordan, and Benjamin Recht. 2016. Gradient descent only converges to minimizers. In Conference on Learning Theory. 1246--1257."},{"key":"e_1_2_1_32_1","volume-title":"Jordan","author":"Lei Lihua","year":"2018","unstructured":"Lihua Lei , Cheng Ju , Jianbo Chen , and Michael I . Jordan . 2018 . Finding approximate local minima faster than gradient descent. In Advances in Neural Information Processing (NIPS) 31. Curran Associates, Red Hook, NY. Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I. Jordan. 2018. Finding approximate local minima faster than gradient descent. In Advances in Neural Information Processing (NIPS) 31. Curran Associates, Red Hook, NY."},{"key":"e_1_2_1_33_1","volume-title":"The power of normalization: Faster evasion of saddle points. arXiv preprint arXiv:1611.04831","author":"Levy Kfir Y.","year":"2016","unstructured":"Kfir Y. Levy . 2016. The power of normalization: Faster evasion of saddle points. arXiv preprint arXiv:1611.04831 ( 2016 ). Kfir Y. Levy. 2016. The power of normalization: Faster evasion of saddle points. arXiv preprint arXiv:1611.04831 (2016)."},{"key":"e_1_2_1_34_1","volume-title":"Conference on Learning Theory (COLT). 1476--1515","author":"Mei Song","unstructured":"Song Mei , Theodor Misiakiewicz , Andrea Montanari , and Roberto I. Oliveira . 2017. Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality . In Conference on Learning Theory (COLT). 1476--1515 . Song Mei, Theodor Misiakiewicz, Andrea Montanari, and Roberto I. Oliveira. 2017. Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality. In Conference on Learning Theory (COLT). 1476--1515."},{"key":"e_1_2_1_35_1","volume-title":"Problem Complexity and Method Efficiency in Pptimization","author":"Nemirovskii Arkadii","unstructured":"Arkadii Nemirovskii and David Borisovich Yudin . 1983. Problem Complexity and Method Efficiency in Pptimization . Wiley . Arkadii Nemirovskii and David Borisovich Yudin. 1983. Problem Complexity and Method Efficiency in Pptimization. Wiley."},{"key":"e_1_2_1_36_1","first-page":"372","article-title":"A method of solving a convex programming problem with convergence rate O (1\/k2)","volume":"27","author":"Nesterov Yurii","year":"1983","unstructured":"Yurii Nesterov . 1983 . A method of solving a convex programming problem with convergence rate O (1\/k2) . Soviet Mathematics Doklady 27 (1983), 372 -- 376 . Yurii Nesterov. 1983. A method of solving a convex programming problem with convergence rate O (1\/k2). Soviet Mathematics Doklady 27 (1983), 372--376.","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_2_1_37_1","volume-title":"Introductory Lectures on Convex Programming Volume I: Basic Course","author":"Nesterov Yurii","unstructured":"Yurii Nesterov . 1998. Introductory Lectures on Convex Programming Volume I: Basic Course . Springer . Yurii Nesterov. 1998. Introductory Lectures on Convex Programming Volume I: Basic Course. Springer."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3216-0_17"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/3112681.3113165"},{"key":"e_1_2_1_40_1","unstructured":"Praneeth Netrapalli UN Niranjan Sujay Sanghavi Animashree Anandkumar and Prateek Jain. 2014. Non-convex robust PCA. In Advances in Neural Information Processing Systems. 1107--1115.  Praneeth Netrapalli UN Niranjan Sujay Sanghavi Animashree Anandkumar and Prateek Jain. 2014. Non-convex robust PCA. In Advances in Neural Information Processing Systems. 1107--1115."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(63)90382-3"},{"key":"e_1_2_1_42_1","volume-title":"Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in Neural Information Processing Systems. 693--701.","author":"Recht Benjamin","year":"2011","unstructured":"Benjamin Recht , Christopher Re , Stephen Wright , and Feng Niu . 2011 . Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in Neural Information Processing Systems. 693--701. Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. 2011. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in Neural Information Processing Systems. 693--701."},{"key":"e_1_2_1_43_1","volume-title":"International Conference on Artificial Intelligence and Statistics. 1233--1242","author":"Reddi Sashank","year":"2018","unstructured":"Sashank Reddi , Manzil Zaheer , Suvrit Sra , Barnabas Poczos , Francis Bach , Ruslan Salakhutdinov , and Alex Smola . 2018 . A generic approach for escaping saddle points . In International Conference on Artificial Intelligence and Statistics. 1233--1242 . Sashank Reddi, Manzil Zaheer, Suvrit Sra, Barnabas Poczos, Francis Bach, Ruslan Salakhutdinov, and Alex Smola. 2018. A generic approach for escaping saddle points. In International Conference on Artificial Intelligence and Statistics. 1233--1242."},{"key":"e_1_2_1_44_1","volume-title":"A stochastic approximation method. Annals of Mathematical Statistics","author":"Robbins Herbert","year":"1951","unstructured":"Herbert Robbins and Sutton Monro . 1951. A stochastic approximation method. Annals of Mathematical Statistics ( 1951 ), 400--407. Herbert Robbins and Sutton Monro. 1951. A stochastic approximation method. Annals of Mathematical Statistics (1951), 400--407."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.2307\/3318418"},{"key":"e_1_2_1_46_1","first-page":"1","article-title":"CoCoA: A general framework for communication-efficient distributed optimization","volume":"18","author":"Smith Virginia","year":"2018","unstructured":"Virginia Smith , Simone Forte , Chenxin Ma , Martin Takac , Michael I. Jordan , and Martin Jaggi . 2018 . CoCoA: A general framework for communication-efficient distributed optimization . Journal of Machine Learning Research 18 (2018), 1 -- 49 . Virginia Smith, Simone Forte, Chenxin Ma, Martin Takac, Michael I. Jordan, and Martin Jaggi. 2018. CoCoA: A general framework for communication-efficient distributed optimization. Journal of Machine Learning Research 18 (2018), 1--49.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_47_1","volume-title":"Complete dictionary recovery over the sphere I: Overview and the geometric picture","author":"Sun Ju","year":"2016","unstructured":"Ju Sun , Qing Qu , and John Wright . 2016. Complete dictionary recovery over the sphere I: Overview and the geometric picture . IEEE Transactions on Information Theory ( 2016 ). Ju Sun, Qing Qu, and John Wright. 2016. Complete dictionary recovery over the sphere I: Overview and the geometric picture. IEEE Transactions on Information Theory (2016)."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2016.7541725"},{"key":"e_1_2_1_49_1","unstructured":"Nilesh Tripuraneni Mitchell Stern Chi Jin Jeffrey Regier and Michael I Jordan. 2018. Stochastic cubic regularization for fast nonconvex optimization. In Advances in Neural Information Processing Systems. 2904--2913.  Nilesh Tripuraneni Mitchell Stern Chi Jin Jeffrey Regier and Michael I Jordan. 2018. Stochastic cubic regularization for fast nonconvex optimization. In Advances in Neural Information Processing Systems. 2904--2913."},{"key":"e_1_2_1_50_1","unstructured":"Yi Xu Jing Rong and Tianbao Yang. 2018. First-order stochastic algorithms for escaping from saddle points in almost linear time. In Advances in Neural Information Processing Systems. 5535--5545.  Yi Xu Jing Rong and Tianbao Yang. 2018. First-order stochastic algorithms for escaping from saddle points in almost linear time. In Advances in Neural Information Processing Systems. 5535--5545."},{"key":"e_1_2_1_51_1","volume-title":"Conference of Learning Theory (COLT).","author":"Zhang Yuchen","year":"2018","unstructured":"Yuchen Zhang , Percy Liang , and Moses Charikar . 2018 . A hitting time analysis of stochastic gradient Langevin dynamics . In Conference of Learning Theory (COLT). Yuchen Zhang, Percy Liang, and Moses Charikar. 2018. A hitting time analysis of stochastic gradient Langevin dynamics. In Conference of Learning Theory (COLT)."},{"key":"e_1_2_1_52_1","volume-title":"Duchi","author":"Zhang Yuchen","year":"2012","unstructured":"Yuchen Zhang , Martin J. Wainwright , and John C . Duchi . 2012 . Communication-efficient algorithms for statistical optimization. In Advances in Neural Information Processing Systems . 1502--1510. Yuchen Zhang, Martin J. Wainwright, and John C. Duchi. 2012. Communication-efficient algorithms for statistical optimization. In Advances in Neural Information Processing Systems. 1502--1510."},{"key":"e_1_2_1_53_1","volume-title":"International Conference on Artificial Intelligence and Statistics. 3980--3990","author":"Zhou Dongruo","year":"2020","unstructured":"Dongruo Zhou and Quanquan Gu . 2020 . Stochastic recursive variance-reduced cubic regularization methods . In International Conference on Artificial Intelligence and Statistics. 3980--3990 . Dongruo Zhou and Quanquan Gu. 2020. Stochastic recursive variance-reduced cubic regularization methods. In International Conference on Artificial Intelligence and Statistics. 3980--3990."},{"key":"e_1_2_1_54_1","volume-title":"Finding local minima via stochastic nested variance reduction. arXiv preprint arXiv:1806.08782","author":"Zhou Dongruo","year":"2018","unstructured":"Dongruo Zhou , Pan Xu , and Quanquan Gu. 2018. Finding local minima via stochastic nested variance reduction. arXiv preprint arXiv:1806.08782 ( 2018 ). Dongruo Zhou, Pan Xu, and Quanquan Gu. 2018. Finding local minima via stochastic nested variance reduction. arXiv preprint arXiv:1806.08782 (2018)."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3418526","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3418526","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3418526","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:02:27Z","timestamp":1750183347000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3418526"}},"subtitle":["Gradients, Stochasticity, and Saddle Points"],"short-title":[],"issued":{"date-parts":[[2021,2,24]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4,30]]}},"alternative-id":["10.1145\/3418526"],"URL":"https:\/\/doi.org\/10.1145\/3418526","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,24]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}