Built on

Cong Fang, Zhouchen Lin, and Tong Zhang, Sharp analysis for nonconvex SGD escaping from saddle points , Conference on Learning Theory, pp. 1192–1234, 2019, arXiv:1902.00247
Original
1902
Earlier work this paper cites.
András Gilyén and Tongyang Li, Distributional property testing in a quantum world , 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020, arXiv:1902.00814
Original
1902
Earlier work this paper cites.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I. Jordan, On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points , Journal of the ACM (JACM) 68
Original
1902
Earlier work this paper cites.
Zhize Li, SSRGD: Simple stochastic recursive gradient descent for escaping saddle points , Advances in Neural Information Processing Systems 32
Original
1904
Earlier work this paper cites.
Rong Ge, Zhize Li, Weiyao Wang, and Xiang Wang, Stabilized SVRG: Simple variance reduction for nonconvex optimization , Conference on Learning Theory, pp. 1394–1448, PMLR, 2019, arXiv:1905.00529
Original
1905
Earlier work this paper cites.
Sébastien Bubeck, Qijia Jiang, Yin-Tat Lee, Yuanzhi Li, and Aaron Sidford, Complexity of highly parallel non-smooth convex optimization , Advances in neural information processing systems 32
Original
1906
Earlier work this paper cites.
Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu, Quantum algorithm for estimating volumes of convex bodies , ACM Transactions on Quantum Computing 4
Original
1908
Earlier work this paper cites.
Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth, Lower bounds for non-convex stochastic optimization , Mathematical Programming (2022), 1–50, arXiv:1912.02365
Original
1912
Earlier work this paper cites.
Arkadij Semenovi 𝐯 \mathbf{v} c Nemirovskij and David Borisovich Yudin, Problem complexity and method efficiency in optimization , 1983
1983
Earlier work this paper cites.
Katta G. Murty and Santosh N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming , Mathematical Programming: Series A and B 39
1987
Earlier work this paper cites.
Boris T. Polyak, Introduction to optimization. Optimization software , Inc., Publications Division, New York 1
1987
Earlier work this paper cites.
Arkadi Nemirovski, Efficient methods in convex programming , Lecture notes (1994)
1994
Earlier work this paper cites.
A. Yu. Kitaev, Quantum measurements and the Abelian stabilizer problem , (1995), arXiv:quant-ph/9511026
1995
Earlier work this paper cites.
Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, Quantum amplitude amplification and estimation , Contemporary Mathematics 305
2002
Earlier work this paper cites.
Yurii Nesterov, Introductory lectures on convex optimization: A basic course , vol. 87, Springer Science & Business Media, 2003
2003
Earlier work this paper cites.
Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong, An improved cutting plane method for convex optimization, convex-concave games, and its applications , Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 944–953, 2020, arXiv:2004.04250
Original
2004
Earlier work this paper cites.
Stephen P. Jordan, Fast quantum algorithm for numerical gradient estimation , Physical Review Letters 95
2005
Earlier work this paper cites.
Yurii Nesterov and Boris T. Polyak, Cubic regularization of Newton method and its global performance , Mathematical Programming 108
2006
Earlier work this paper cites.
Shai Shalev-Shwartz, Online learning: Theory, algorithms, and applications , Hebrew University, 2007
2007
Earlier work this paper cites.
Chenyi Zhang, Jiaqi Leng, and Tongyang Li, Quantum algorithms for escaping from saddle points , Quantum 5
Original
2007
Earlier work this paper cites.
Stephen Boyd and Almir Mutapcic, Stochastic subgradient methods , Lecture Notes for EE364b, Stanford University (2008), 97
2008
Earlier work this paper cites.
Trevor Hastie, Robert Tibshirani, Jerome H. Friedman, and Jerome H. Friedman, The elements of statistical learning: Data mining, inference, and prediction , vol. 2, Springer, 2009
2009
Earlier work this paper cites.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro, Robust stochastic approximation approach to stochastic programming , SIAM Journal on optimization 19
2009
Earlier work this paper cites.
Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif, No quantum speedup over gradient descent for non-smooth convex optimization , 2020, arXiv:2010.01801
Original
2010
Earlier work this paper cites.
Dong An, Noah Linden, Jin-Peng Liu, Ashley Montanaro, Changpeng Shao, and Jiasu Wang, Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance , Quantum 5
Original
2012
Earlier work this paper cites.
John C. Duchi, Peter L. Bartlett, and Martin J. Wainwright, Randomized smoothing for stochastic optimization , SIAM Journal on Optimization 22
2012
Earlier work this paper cites.
Guanghui Lan, An optimal method for stochastic composite optimization , Mathematical Programming 133
2012
Earlier work this paper cites.
Saeed Ghadimi and Guanghui Lan, Stochastic first-and zeroth-order methods for nonconvex stochastic programming , SIAM Journal on Optimization 23
2013
Earlier work this paper cites.
Rie Johnson and Tong Zhang, Accelerating stochastic gradient descent using predictive variance reduction , Advances in neural information processing systems 26
2013
Earlier work this paper cites.

Similar

Aaron Defazio, Francis Bach, and Simon Lacoste-Julien, Saga: A fast incremental gradient method with support for non-strongly convex composite objectives , Advances in neural information processing systems 27
2014
Cited alongside, same era.
Shai Shalev-Shwartz and Shai Ben-David, Understanding machine learning: From theory to algorithms , Cambridge university press, 2014
2014
Cited alongside, same era.
Jose H. Blanchet and Peter W. Glynn, Unbiased Monte Carlo for optimization and functions of expectations via multi-level randomization , 2015 Winter Simulation Conference (WSC), pp. 3656–3667, IEEE, 2015
2015
Cited alongside, same era.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan, Escaping from saddle points – online stochastic gradient for tensor decomposition , Proceedings of the 28th Conference on Learning Theory, Proceedings of Machine Learning Research, vol. 40, pp. 797–842, 2015, arXiv:1503.02101
Original
2015
Cited alongside, same era.

Then

Mingrui Liu, Zhe Li, Xiaoyu Wang, Jinfeng Yi, and Tianbao Yang, Adaptive negative curvature descent with applications in non-convex optimization , Advances in Neural Information Processing Systems 31
2018
Later among the works it cites.
Yaodong Yu, Pan Xu, and Quanquan Gu, Third-order smoothness helps: Faster stochastic optimization algorithms for finding local minima , Advances in Neural Information Processing Systems (2018), 4530–4540
2018
Later among the works it cites.
Xiao Zhang, Lingxiao Wang, Yaodong Yu, and Quanquan Gu, A primal-dual analysis of global optimality in nonconvex low-rank matrix recovery , International Conference on Machine Learning, pp. 5862–5871, PMLR, 2018
2018
Later among the works it cites.
Dongruo Zhou, Pan Xu, and Quanquan Gu, Stochastic variance-reduced cubic regularized Newton methods , International Conference on Machine Learning, pp. 5990–5999, PMLR, 2018, arXiv:1802.04796
Original
2018
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2023

Quantum speedups for stochastic optimization

Sidford, Aaron, Zhang, Chenyi

Understand

We consider the problem of minimizing a continuous function given quantum access to a stochastic gradient oracle.

We provide two new methods for the special case of minimizing a Lipschitz convex function.
Each method obtains a dimension versus accuracy trade-off which is provably unachievable classically and we prove that one method is asymptotically optimal in low-dimensional settings.
Additionally, we provide quantum algorithms for computing a critical point of a smooth non-convex function at rates not known to be achievable classically.

Built on

Cong Fang, Zhouchen Lin, and Tong Zhang, Sharp analysis for nonconvex SGD escaping from saddle points , Conference on Learning Theory, pp. 1192–1234, 2019, arXiv:1902.00247
Original
1902
Earlier work this paper cites.
András Gilyén and Tongyang Li, Distributional property testing in a quantum world , 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020, arXiv:1902.00814
Original
1902
Earlier work this paper cites.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I. Jordan, On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points , Journal of the ACM (JACM) 68
Original
1902
Earlier work this paper cites.
Zhize Li, SSRGD: Simple stochastic recursive gradient descent for escaping saddle points , Advances in Neural Information Processing Systems 32
Original
1904
Earlier work this paper cites.
Rong Ge, Zhize Li, Weiyao Wang, and Xiang Wang, Stabilized SVRG: Simple variance reduction for nonconvex optimization , Conference on Learning Theory, pp. 1394–1448, PMLR, 2019, arXiv:1905.00529
Original
1905
Earlier work this paper cites.
Sébastien Bubeck, Qijia Jiang, Yin-Tat Lee, Yuanzhi Li, and Aaron Sidford, Complexity of highly parallel non-smooth convex optimization , Advances in neural information processing systems 32
Original
1906
Earlier work this paper cites.
Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu, Quantum algorithm for estimating volumes of convex bodies , ACM Transactions on Quantum Computing 4
Original
1908
Earlier work this paper cites.
Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth, Lower bounds for non-convex stochastic optimization , Mathematical Programming (2022), 1–50, arXiv:1912.02365
Original
1912
Earlier work this paper cites.
Arkadij Semenovi 𝐯 \mathbf{v} c Nemirovskij and David Borisovich Yudin, Problem complexity and method efficiency in optimization , 1983
1983
Earlier work this paper cites.
Katta G. Murty and Santosh N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming , Mathematical Programming: Series A and B 39
1987
Earlier work this paper cites.
Boris T. Polyak, Introduction to optimization. Optimization software , Inc., Publications Division, New York 1
1987
Earlier work this paper cites.
Arkadi Nemirovski, Efficient methods in convex programming , Lecture notes (1994)
1994
Earlier work this paper cites.
A. Yu. Kitaev, Quantum measurements and the Abelian stabilizer problem , (1995), arXiv:quant-ph/9511026
1995
Earlier work this paper cites.
Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, Quantum amplitude amplification and estimation , Contemporary Mathematics 305
2002
Earlier work this paper cites.
Yurii Nesterov, Introductory lectures on convex optimization: A basic course , vol. 87, Springer Science & Business Media, 2003
2003
Earlier work this paper cites.
Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong, An improved cutting plane method for convex optimization, convex-concave games, and its applications , Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 944–953, 2020, arXiv:2004.04250
Original
2004
Earlier work this paper cites.
Stephen P. Jordan, Fast quantum algorithm for numerical gradient estimation , Physical Review Letters 95
2005
Earlier work this paper cites.
Yurii Nesterov and Boris T. Polyak, Cubic regularization of Newton method and its global performance , Mathematical Programming 108
2006
Earlier work this paper cites.
Shai Shalev-Shwartz, Online learning: Theory, algorithms, and applications , Hebrew University, 2007
2007
Earlier work this paper cites.
Chenyi Zhang, Jiaqi Leng, and Tongyang Li, Quantum algorithms for escaping from saddle points , Quantum 5
Original
2007
Earlier work this paper cites.
Stephen Boyd and Almir Mutapcic, Stochastic subgradient methods , Lecture Notes for EE364b, Stanford University (2008), 97
2008
Earlier work this paper cites.
Trevor Hastie, Robert Tibshirani, Jerome H. Friedman, and Jerome H. Friedman, The elements of statistical learning: Data mining, inference, and prediction , vol. 2, Springer, 2009
2009
Earlier work this paper cites.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro, Robust stochastic approximation approach to stochastic programming , SIAM Journal on optimization 19
2009
Earlier work this paper cites.
Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif, No quantum speedup over gradient descent for non-smooth convex optimization , 2020, arXiv:2010.01801
Original
2010
Earlier work this paper cites.
Dong An, Noah Linden, Jin-Peng Liu, Ashley Montanaro, Changpeng Shao, and Jiasu Wang, Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance , Quantum 5
Original
2012
Earlier work this paper cites.
John C. Duchi, Peter L. Bartlett, and Martin J. Wainwright, Randomized smoothing for stochastic optimization , SIAM Journal on Optimization 22
2012
Earlier work this paper cites.
Guanghui Lan, An optimal method for stochastic composite optimization , Mathematical Programming 133
2012
Earlier work this paper cites.
Saeed Ghadimi and Guanghui Lan, Stochastic first-and zeroth-order methods for nonconvex stochastic programming , SIAM Journal on Optimization 23
2013
Earlier work this paper cites.
Rie Johnson and Tong Zhang, Accelerating stochastic gradient descent using predictive variance reduction , Advances in neural information processing systems 26
2013
Earlier work this paper cites.

Similar

Aaron Defazio, Francis Bach, and Simon Lacoste-Julien, Saga: A fast incremental gradient method with support for non-strongly convex composite objectives , Advances in neural information processing systems 27
2014
Cited alongside, same era.
Shai Shalev-Shwartz and Shai Ben-David, Understanding machine learning: From theory to algorithms , Cambridge university press, 2014
2014
Cited alongside, same era.
Jose H. Blanchet and Peter W. Glynn, Unbiased Monte Carlo for optimization and functions of expectations via multi-level randomization , 2015 Winter Simulation Conference (WSC), pp. 3656–3667, IEEE, 2015
2015
Cited alongside, same era.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan, Escaping from saddle points – online stochastic gradient for tensor decomposition , Proceedings of the 28th Conference on Learning Theory, Proceedings of Machine Learning Research, vol. 40, pp. 797–842, 2015, arXiv:1503.02101
Original
2015
Cited alongside, same era.

Then

Mingrui Liu, Zhe Li, Xiaoyu Wang, Jinfeng Yi, and Tianbao Yang, Adaptive negative curvature descent with applications in non-convex optimization , Advances in Neural Information Processing Systems 31
2018
Later among the works it cites.
Yaodong Yu, Pan Xu, and Quanquan Gu, Third-order smoothness helps: Faster stochastic optimization algorithms for finding local minima , Advances in Neural Information Processing Systems (2018), 4530–4540
2018
Later among the works it cites.
Xiao Zhang, Lingxiao Wang, Yaodong Yu, and Quanquan Gu, A primal-dual analysis of global optimality in nonconvex low-rank matrix recovery , International Conference on Machine Learning, pp. 5862–5871, PMLR, 2018
2018
Later among the works it cites.
Dongruo Zhou, Pan Xu, and Quanquan Gu, Stochastic variance-reduced cubic regularized Newton methods , International Conference on Machine Learning, pp. 5990–5999, PMLR, 2018, arXiv:1802.04796
Original
2018
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Michael B. Giles, Multilevel Monte Carlo methods , Acta Numerica 24

2015

Cited alongside, same era.

Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong, A faster cutting plane method and its implications for combinatorial and convex optimization , 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 1049–1065, IEEE, 2015, arXiv:1508.04874

Original

2015

Cited alongside, same era.

Ashley Montanaro, Quantum speedup of Monte Carlo methods , Proceedings of the Royal Society A 471

Original

2015

Cited alongside, same era.

Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro, Global optimality of local search for low rank matrix recovery , Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 3880–3888, 2016, arXiv:1605.07221

Original

2016

Cited alongside, same era.

Rong Ge, Jason D. Lee, and Tengyu Ma, Matrix completion has no spurious local minimum , Advances in Neural Information Processing Systems, pp. 2981–2989, 2016, arXiv:1605.07272

Original

2016

Cited alongside, same era.

Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma, Finding approximate local minima faster than gradient descent , Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1195–1199, 2017, arXiv:1611.01146

Original

2017

Cited alongside, same era.

Zeyuan Allen-Zhu, Katyusha: The first direct acceleration of stochastic gradient methods , The Journal of Machine Learning Research 18

Original

2017

Cited alongside, same era.

Ernesto G. Birgin, J. L. Gardenghi, José Mario Martínez, Sandra Augusta Santos, and Ph. L. Toint, Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models , Mathematical Programming 163

2017

Cited alongside, same era.

Fernando G.S.L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu, Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning , Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 27:1–27:14, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019, arXiv:1710.02581

Original

2019