På Quantum Speedups för Nonconvex Optimization via Quantum Tunneling Walks

På Quantum Speedups för Nonconvex Optimization via Quantum Tunneling Walks

Tidsstämpel: 2 juni 2023 8:23
Källnod: 2694596

Yizhou Liu1, Weijie J. Su2och Tongyang Li3,4

1Institutionen för teknisk mekanik, Tsinghua University, 100084 Peking, Kina
2Institutionen för statistik och datavetenskap, University of Pennsylvania
3Center on Frontiers of Computing Studies, Peking University, 100871 Beijing, Kina
4School of Computer Science, Peking University, 100871 Peking, Kina

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Klassiska algoritmer är ofta inte effektiva för att lösa icke-konvexa optimeringsproblem där lokala minima är åtskilda av höga barriärer. I det här dokumentet utforskar vi möjliga kvanthastigheter för icke-konvex optimering genom att utnyttja den $globala$ effekten av kvanttunnelering. Specifikt introducerar vi en kvantalgoritm som kallas quantum tunneling walk (QTW) och tillämpar den på icke-konvexa problem där lokala minima är ungefär globala minima. Vi visar att QTW uppnår kvanthastigheter över klassiska stokastiska gradientnedgångar (SGD) när barriärerna mellan olika lokala minima är höga men tunna och minima är platta. Baserat på denna observation konstruerar vi ett specifikt dubbelbrunnslandskap, där klassiska algoritmer inte effektivt kan träffa ett mål väl medvetet om det andra, men QTW kan när de ges korrekta initiala tillstånd nära den kända brunnen. Slutligen bekräftar vi våra resultat med numeriska experiment.

[Inbäddat innehåll]

Populär sammanfattning

Klassiska algoritmer är ofta inte effektiva för att lösa icke-konvexa optimeringsproblem där lokala minima är åtskilda av höga barriärer. I det här dokumentet utforskar vi möjliga kvanthastigheter för icke-konvex optimering genom att utnyttja den globala effekten av kvanttunnling. Specifikt introducerar vi en kvantalgoritm som kallas quantum tunneling walk (QTW) och tillämpar den på icke-konvexa problem där lokala minima är ungefär globala minima. Vi visar att QTW uppnår kvanthastigheter över klassiska stokastiska gradientnedgångar (SGD) när barriärerna mellan olika lokala minima är höga men tunna och minima är platta. Baserat på denna observation konstruerar vi ett specifikt dubbelbrunnslandskap, där klassiska algoritmer inte effektivt kan träffa ett mål väl medvetet om det andra, men QTW kan när de ges korrekta initiala tillstånd nära den kända brunnen. Slutligen bekräftar vi våra resultat med numeriska experiment.

► BibTeX-data

► Referenser

[1] Zeyuan Allen-Zhu och Yuanzhi Li. Neon2: Hitta lokala minima via första ordningens orakel. I Advances in Neural Information Processing Systems, sidorna 3716–3726, 2018. URL http://​/​papers.neurips.cc/​paper/​7629-neon2-finding-local-minima-via-first-order-oracles. pdf. arXiv:1711.06673.
arXiv: 1711.06673
http://​/​papers.neurips.cc/​paper/​7629-neon2-finding-local-minima-via-first-order-oracles.pdf

[2] Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade och Matus Telgarsky. Tensorupplösningar för inlärning av latenta variabelmodeller. Journal of machine learning research, 15: 2773–2832, 2014. URL https://​/​jmlr.org/​papers/​volume15/​anandkumar14b/​. arXiv:1210.7559v4.
arXiv: 1210.7559v4
https://​/​jmlr.org/​papers/​volume15/​anandkumar14b/​

[3] Ben Andrews och Julie Clutterbuck. Bevis på den grundläggande gapförmodan. Journal of the American Mathematical Society, 24 (3): 899–916, 2011. ISSN 08940347, 10886834. URL http://​/​www.jstor.org/​stable/​23072145. arXiv:1006.1686.
arXiv: 1006.1686
http: / / www.jstor.org/ stabil / 23072145

[4] Joran van Apeldoorn och András Gilyén. Förbättringar i kvant-SDP-lösning med applikationer. I Proceedings of the 46th International Colloquium on Automata, Languages ​​and Programming, volym 132 av Leibniz International Proceedings in Informatics (LIPIcs), sidorna 99:1–99:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. 10.4230/​LIPIcs.ICALP.2019.99. arXiv:1804.05058.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.99
arXiv: 1804.05058

[5] Joran van Apeldoorn, András Gilyén, Sander Gribling och Ronald de Wolf. Quantum SDP-lösare: Bättre övre och nedre gränser. I handlingar av det 58:e årliga symposiet om grunderna för datavetenskap. IEEE, 2017. 10.1109/​FOCS.2017.44. arXiv:1705.01843.
https: / / doi.org/ 10.1109 / FOCS.2017.44
arXiv: 1705.01843

[6] Joran van Apeldoorn, András Gilyén, Sander Gribling och Ronald de Wolf. Konvex optimering med kvantorakel. Quantum, 4: 220, 2020. 10.22331/​q-2020-01-13-220. arXiv:1809.00643.
https:/​/​doi.org/​10.22331/​q-2020-01-13-220
arXiv: 1809.00643

[7] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B. Buckley, David A. Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Benjamin Chiaro , Roberto Collins, William Courtney, Sean Demura, Andrew Dunsworth, Edward Farhi, Austin Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Rob Graff, Steve Habegger, Matthew P. Harrigan, Alan Ho, Sabrina Hong, Trent Huang, William J Huggins, Lev Ioffe, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Seon Kim, Paul V. Klimov, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Mike Lindmark, Erik Lucero, Orion Martin, John M. Martinis, Jarrod R. McClean, Matt McEwen, Anthony Megrant, Xiao Mi, Masoud Mohseni, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Hartmut Neven, Murphy Yuezhen Niu, Thomas E. O'Brien, Eric Ostby, Andre Petukhov, Harald Putterman, Chris Quintana, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Doug Strain, Kevin J. Sung, Marco Szalay , Tyler Y. Takeshita, Amit Vainsencher, Theodore White, Nathan Wiebe, Z. Jamie Yao, Ping Yeh och Adam Zalcman. Hartree-Fock på en supraledande kvantdator. Science, 369 (6507): 1084–1089, 2020. 10.1126/​science.abb9811. URL https://​science.sciencemag.org/​content/​369/​6507/​1084.abstract. arXiv:2004.04174.
https: / / doi.org/ 10.1126 / science.abb9811
arXiv: 2004.04174
https://​science.sciencemag.org/​content/​369/​6507/​1084.abstract

[8] Yosi Atia och Shantanav Chakraborty. Förbättrade övre gränser för träfftider för kvantvandringar. Physical Review A, 104: 032215, sep 2021. ISSN 2469-9934. 10.1103/​physreva.104.032215. URL http://​dx.doi.org/​10.1103/​PhysRevA.104.032215. arXiv:2005.04062v5.
https: / ⠀ </ ⠀ <doi.org/†<10.1103 / ⠀ <physreva.104.032215
arXiv: 2005.04062v5

[9] Carlo Baldassi och Riccardo Zecchina. Effektivitet av quantum kontra klassisk glödgning i icke-konvexa inlärningsproblem. Proceedings of the National Academy of Sciences, 115 (7): 1457–1462, jan 2018. ISSN 1091-6490. 10.1073/​pnas.1711456115. URL http://​dx.doi.org/​10.1073/​pnas.1711456115. arXiv:1706.08470.
https: / / doi.org/ 10.1073 / pnas.1711456115
arXiv: 1706.08470

[10] Charles H. Bennett, Ethan Bernstein, Gilles Brassard och Umesh Vazirani. Styrkor och svagheter med kvantberäkning. SIAM Journal on Computing, 26 (5): 1510–1523, 1997. 10.1137/​S0097539796300933. URL https://​/​doi.org/​10.1137/​S0097539796300933. arXiv:quant-ph/​9701001.
https: / / doi.org/ 10.1137 / S0097539796300933
arXiv: kvant-ph / 9701001

[11] Michael Betancourt, Michael I. Jordan och Ashia C Wilson. Om symplektisk optimering, 2018. arXiv:1802.03653.
arXiv: 1802.03653

[12] Sergio Boixo och Rolando D. Somma. Nödvändigt villkor för den kvantadiabatiska approximationen. Physical Review A, 81 (3): 032308, 2010. 10.1103/​PhysRevA.81.032308. URL https://​journals.aps.org/​pra/​abstract/​10.1103/​PhysRevA.81.032308. arXiv:0911.1362.
https: / / doi.org/ 10.1103 / PhysRevA.81.032308
arXiv: 0911.1362

[13] Fernando GSL Brandão och Krysta Svore. Quantum speed-ups för semidefinite programmering. I Proceedings of the 58th Annual Symposium on Foundations of Computer Science, sidorna 415–426, 2017. 10.1109/​FOCS.2017.45. arXiv:1609.05537.
https: / / doi.org/ 10.1109 / FOCS.2017.45
arXiv: 1609.05537

[14] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore och Xiaodi Wu. Quantum SDP-lösare: Stora hastigheter, optimalitet och tillämpningar för kvantinlärning. I Proceedings of the 46th International Colloquium on Automata, Languages ​​and Programming, volym 132 av Leibniz International Proceedings in Informatics (LIPIcs), sidorna 27:1–27:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. 10.4230/​LIPIcs.ICALP.2019.27. arXiv:1710.02581.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.27
arXiv: 1710.02581

[15] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li och Xiaodi Wu. Kvantalgoritmer och nedre gränser för konvex optimering. Quantum, 4: 221, 2020. 10.22331/​q-2020-01-13-221. arXiv:1809.01731.
https:/​/​doi.org/​10.22331/​q-2020-01-13-221
arXiv: 1809.01731

[16] Shantanav Chakraborty, Kyle Luh och Jérémie Roland. Hur snabbt blandas kvantvandringar? Physical Review Letters, 124: 050501, feb 2020. 10.1103/​PhysRevLett.124.050501. URL https://​/​link.aps.org/​doi/​10.1103/​PhysRevLett.124.050501. arXiv:2001.06305v1.
https: / / doi.org/ 10.1103 / PhysRevLett.124.050501
arXiv: 2001.06305v1

[17] Pratik Chaudhari och Stefano Soatto. Stokastisk gradientnedstigning utför variationsslutledning, konvergerar för att begränsa cykler för djupa nätverk. Under 2018 Information Theory and Applications Workshop (ITA), sidorna 1–10, 2018. 10.1109/​ITA.2018.8503224. arXiv:1710.11029v2.
https://doi.org/ 10.1109/ITA.2018.8503224
arXiv: 1710.11029v2

[18] Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann och Daniel A. Spielman. Exponentiell algoritmisk hastighetsökning med en kvantvandring. I Proceedings of the Thirty-Femth Annual ACM Symposium on Theory of Computing, STOC '03, sid 59–68, New York, NY, USA, 2003. Association for Computing Machinery. ISBN 1581136749. 10.1145/​780542.780552. URL https://​/​doi.org/​10.1145/​780542.780552. arXiv:quant-ph/​0209131v2.
https: / / doi.org/ 10.1145 / 780542.780552
arXiv: quant-ph / 0209131v2

[19] Andrew M. Childs, Jin-Peng Liu och Aaron Ostrander. Högprecisions kvantalgoritmer för partiella differentialekvationer. Quantum, 5: 574, nov 2021. ISSN 2521-327X. 10.22331/​q-2021-11-10-574. URL http://​dx.doi.org/​10.22331/​q-2021-11-10-574. arXiv:2002.07868.
https:/​/​doi.org/​10.22331/​q-2021-11-10-574
arXiv: 2002.07868

[20] Pierre Comon, Xavier Luciani och André LF De Almeida. Tensornedbrytningar, omväxlande minsta kvadrater och andra berättelser. Journal of Chemometrics, 23: 393–405, augusti 2009. 10.1002/​cem.1236. URL https://​/​hal.archives-ouvertes.fr/​hal-00410057.
https://​/​doi.org/​10.1002/​cem.1236
https: / / hal.archives-ouvertes.fr/ hal-00410057

[21] Pedro CS Costa, Stephen Jordan och Aaron Ostrander. Kvantalgoritm för att simulera vågekvationen. Physical Review A, 99: 012323, jan 2019. 10.1103/​PhysRevA.99.012323. URL https://​/​link.aps.org/​doi/​10.1103/​PhysRevA.99.012323. arXiv:1711.05394.
https: / / doi.org/ 10.1103 / PhysRevA.99.012323
arXiv: 1711.05394

[22] Christopher Criscitiello och Nicolas Boumal. Negativ krökning hindrar acceleration för geodesiskt konvex optimering, även med exakta första ordningens orakel, 2021. arXiv:2111.13263.
arXiv: 2111.13263

[23] Elizabeth Crosson och Aram W. Harrow. Simulerad kvantglödgning kan vara exponentiellt snabbare än klassisk simulerad glödgning. 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), sidorna 714–723. IEEE, okt 2016. 10.1109/​focs.2016.81. URL http://​dx.doi.org/​10.1109/​FOCS.2016.81. arXiv:1601.03030.
https: / / doi.org/ 10.1109 / focs.2016.81
arXiv: 1601.03030

[24] Mouez Dimassi och Johannes Sjöstrand. Spektral asymptotik i den semi-klassiska gränsen. London Mathematical Society föreläsningsanteckningsserie. Cambridge University Press, 1999. 10.1017/​CBO9780511662195.
https: / / doi.org/ 10.1017 / CBO9780511662195

[25] Felix Draxler, Kambis Veschgini, Manfred Salmhofer och Fred Hamprecht. I princip inga hinder i det neurala nätverkets energilandskap. I International Conference on Machine Learning, sidorna 1309–1318. PMLR, 2018. URL http://​/​proceedings.mlr.press/​v80/​draxler18a.html. arXiv:1803.00885.
arXiv: 1803.00885
http://​/​proceedings.mlr.press/​v80/​draxler18a.html

[26] Runyao Duan. Kvantadiabatisk teorem återbesökt, 2020. arXiv:2003.03063v1.
arXiv: 2003.03063v1

[27] John Duchi, Elad Hazan och Yoram Singer. Adaptiva subgradientmetoder för onlineinlärning och stokastisk optimering. Journal of Machine Learning Research, 12 (61): 2121–2159, 2011. URL https://​/​www.jmlr.org/​papers/​volume12/​duchi11a/​duchi11a.pdf.
https://​/​www.jmlr.org/​papers/​volume12/​duchi11a/​duchi11a.pdf

[28] Sepehr Ebadi, Tout T. Wang, Harry Levine, Alexander Keesling, Giulia Semeghini, Ahmed Omran, Dolev Bluvstein, Rhine Samajdar, Hannes Pichler, Wen Wei Ho, Soonwon Choi, Subir Sachdev, Markus Greiner, Vladan Vuletić och Mikhail D. Lukin . Kvantfaser av materia på en programmerbar kvantsimulator med 256 atomer. Nature, 595 (7866): 227–232, 2021. 10.1038/​s41586-021-03582-4. URL https://www.nature.com/​articles/​s41586-021-03582-4.
https:/​/​doi.org/​10.1038/​s41586-021-03582-4
https: / / www.nature.com/ articles / s41586-021-03582-4

[29] Cong Fang, Chris Junchi Li, Zhouchen Lin och Tong Zhang. Spindel: Nästan optimal icke-konvex optimering via stokastisk vägintegrerad differentialskattare. In Advances in Neural Information Processing Systems, sidorna 689–699, 2018. URL https://​/​dl.acm.org/​doi/​abs/​10.5555/​3326943.3327007. arXiv:1807.01695.
arXiv: 1807.01695
https: / / dl.acm.org/ doi / abs / 10.5555 / 3326943.3327007

[30] Cong Fang, Zhouchen Lin och Tong Zhang. Skarp analys för icke-konvex SGD som flyr från sadelpunkter. I Conference on Learning Theory, sidorna 1192–1234, 2019. URL http://​/​proceedings.mlr.press/​v99/​fang19a.html. arXiv:1902.00247.
arXiv: 1902.00247
http://​/​proceedings.mlr.press/​v99/​fang19a.html

[31] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren och Daniel Preda. En kvantadiabatisk evolutionsalgoritm tillämpad på slumpmässiga instanser av ett NP-komplett problem. Science, 292 (5516): 472–475, apr 2001. ISSN 1095-9203. 10.1126/​science.1057726. URL http://​dx.doi.org/​10.1126/​science.1057726. arXiv:quant-ph/​0104129.
https: / / doi.org/ 10.1126 / science.1057726
arXiv: kvant-ph / 0104129

[32] AB Finnila, MA Gomez, C. Sebenik, C. Stenson och JD Doll. Quantum annealing: En ny metod för att minimera flerdimensionella funktioner. Chemical Physics Letters, 219 (5-6): 343–348, Mar 1994. ISSN 0009-2614. 10.1016/​0009-2614(94)00117-0. URL http://​dx.doi.org/​10.1016/​0009-2614(94)00117-0. arXiv:chem-ph/​9404003.
https:/​/​doi.org/​10.1016/​0009-2614(94)00117-0
arXiv:chem-ph/9404003

[33] Mauger François. Symplectic leap frog scheme, 2020. URL https://​/​www.mathworks.com/​matlabcentral/​fileexchange/​38652-symplectic-leap-frog-scheme. https: /​/​www.mathworks.com /​matlabcentral /​fileexchange /​38652-symplectic-leap-frog-scheme.
https://www.mathworks.com/ matlabcentral/fileexchange/38652-symplectic-språng-groda-schema

[34] Alan Frieze, Mark Jerrum och Ravi Kannan. Att lära sig linjära transformationer. I Proceedings of 37th Conference on Foundations of Computer Science, sidorna 359–368, 1996. 10.1109/​SFCS.1996.548495.
https: / / doi.org/ 10.1109 / SFCS.1996.548495

[35] Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry Vetrov och Andrew Gordon Wilson. Förlustytor, lägesanslutning och snabb sammansättning av DNN. In Advances in Neural Information Processing Systems, sidorna 8803–8812, 2018. URL https://​/​dl.acm.org/​doi/​abs/​10.5555/​3327546.3327556. arXiv:1802.10026.
arXiv: 1802.10026
https: / / dl.acm.org/ doi / abs / 10.5555 / 3327546.3327556

[36] Rong Ge och Tengyu Ma. Om optimeringslandskapet för tensornedbrytningar. Matematisk programmering, sidorna 1–47, 2020. ISSN 1436-4646. 10.1007/​s10107-020-01579-x. URL https://​/​doi.org/​10.1007/​s10107-020-01579-x. arXiv:1706.05598v1.
https: / / doi.org/ 10.1007 / s10107-020-01579-x
arXiv: 1706.05598v1

[37] Rong Ge, Furong Huang, Chi Jin och Yang Yuan. Att fly från sadelpunkter – online stokastisk gradient för tensornedbrytning. I Proceedings of the 28th Conference on Learning Theory, volym 40 av Proceedings of Machine Learning Research, sidorna 797–842, 2015. URL http://​/​proceedings.mlr.press/​v40/​Ge15. arXiv:1503.02101.
arXiv: 1503.02101
http://​/​proceedings.mlr.press/​v40/​Ge15

[38] Rong Ge, Jason D. Lee och Tengyu Ma. Matriskomplettering har inget falskt lokalt minimum. I Advances in Neural Information Processing Systems, sidorna 2981–2989, 2016. URL https://​/​dl.acm.org/​doi/​abs/​10.5555/​3157382.3157431. arXiv:1605.07272.
arXiv: 1605.07272
https: / / dl.acm.org/ doi / abs / 10.5555 / 3157382.3157431

[39] Ming Gong, Shiyu Wang, Chen Zha, Ming-Cheng Chen, He-Liang Huang, Yulin Wu, Qingling Zhu, Youwei Zhao, Shaowei Li, Shaojun Guo, Haoran Qian, Yangsen Ye, Fusheng Chen, Chong Ying, Jiale Yu, Daojin Fan, Dachao Wu, Hong Su, Hui Deng, Hao Rong, Kaili Zhang, Sirui Cao, Jin Lin, Yu Xu, Lihua Sun, Cheng Guo, Na Li, Futian Liang, VM Bastidas, Kae Nemoto, WJ Munro, Yong-Heng Huo, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu och Jian-Wei Pan. Quantum går på en programmerbar tvådimensionell 62-qubit supraledande processor. Science, 372 (6545): 948–952, 2021. 10.1126/​science.abg7812. URL https://​science.sciencemag.org/​content/​372/​6545/​948.abstract. arXiv:2102.02573.
https://doi.org/ 10.1126/science.abg7812
arXiv: 2102.02573
https://​science.sciencemag.org/​content/​372/​6545/​948.abstract

[40] Stephen K. Gray och David E. Manolopoulos. Symplektiska integratörer skräddarsydda för den tidsberoende Schrödinger-ekvationen. The Journal of Chemical Physics, 104 (18): 7099–7112, 1996. 10.1063/​1.471428. URL https://doi.org/​10.1063/​1.471428.
https: / / doi.org/ 10.1063 / 1.471428

[41] Bernard Helffer. Semi-klassisk analys för Schrödinger-operatören och applikationer. Föreläsningsanteckningar i matematik. Springer, 1988. 10.1007/​BFb0078115.
https: / / doi.org/ 10.1007 / BFb0078115

[42] Bernard Helffer och Johannes Sjöstrand. Flera brunnar i den semi-klassiska gränsen I. Communications in Partial Differential Equations, 9 (4): 337–408, 1984. 10.1080/​03605308408820335.
https: / / doi.org/ 10.1080 / 03605308408820335

[43] Bernard Helffer och Johannes Sjöstrand. Flera brunnar i den semi-klassiska gränsen III – interaktion genom icke-resonanta brunnar. Mathematische Nachrichten, 124 (1): 263–313, 1985. https:/​/​doi.org/​10.1002/​mana.19851240117. URL https://​/​onlinelibrary.wiley.com/​doi/​abs/​10.1002/​mana.19851240117.
https: / / doi.org/ 10.1002 / mana.19851240117

[44] Sepp Hochreiter. Det försvinnande gradientproblemet under inlärning av återkommande neurala nät och problemlösningar. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 6 (02): 107–116, 1998. 10.1142/​S0218488598000094. URL https://​/​dl.acm.org/​doi/​abs/​10.1142/​S0218488598000094.
https: / / doi.org/ 10.1142 / S0218488598000094

[45] Aapo Hyvarinen. Snabb ICA för bullriga data med gaussiska moment. 1999 IEEE International Symposium on Circuits and Systems (ISCAS), volym 5, sidorna 57–61, 1999. 10.1109/​ISCAS.1999.777510.
https://​/​doi.org/​10.1109/​ISCAS.1999.777510

[46] Frédéric Hérau, Michael Hitrik och Johannes Sjöstrand. Tunneleffekt och symmetrier för operatörer av typen kramers–fokker–planck. Journal of the Institute of Mathematics of Jussieu, 10 (3): 567–634, 2011. 10.1017/​S1474748011000028.
https: / / doi.org/ 10.1017 / S1474748011000028

[47] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade och Michael I. Jordan. Hur man slipper sadelpunkter effektivt. I Proceedings of the 34th International Conference on Machine Learning, volym 70, sidorna 1724–1732, 2017. URL http://​/​proceedings.mlr.press/​v70/​jin17a. arXiv:1703.00887.
arXiv: 1703.00887
http://​/​proceedings.mlr.press/​v70/​jin17a

[48] Chi Jin, Lydia T. Liu, Rong Ge och Michael I. Jordan. På den empiriska riskens lokala minima. I Advances in Neural Information Processing Systems, volym 31, sid 4901–4910. Curran Associates, Inc., 2018. URL https://​/​proceedings.neurips.cc/​paper/​2018/​file/​da4902cb0bc38210839714ebdcf0efc3-Paper.pdf. arXiv:1803.09357.
arXiv: 1803.09357
https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​da4902cb0bc38210839714ebdcf0efc3-Paper.pdf

[49] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade och Michael I. Jordan. Om icke-konvex optimering för maskininlärning: Gradienter, stokasticitet och sadelpunkter. Journal of the ACM (JACM), 68 (2): 1–29, 2021. 10.1145/​3418526. URL https://​/​dl.acm.org/​doi/​abs/​10.1145/​3418526. arXiv:1902.04811.
https: / / doi.org/ 10.1145 / 3418526
arXiv: 1902.04811

[50] Michael I. Jordan. Dynamiska, symplektiska och stokastiska perspektiv på gradientbaserad optimering. I Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, sidorna 523–549. World Scientific, 2018. URL https://​/​doi.org/​10.1142/​9789813272880_0022.
https: / / doi.org/ 10.1142 / 9789813272880_0022

[51] Kenji Kawaguchi, Jiaoyang Huang och Leslie Pack Kaelbling. Varje lokalt minimivärde är det globala minimivärdet för inducerad modell i icke-konvex maskininlärning. Neural Computation, 31 (12): 2293–2323, 12 2019. ISSN 0899-7667. 10.1162/​neco_a_01234. URL https://​/​doi.org/​10.1162/​neco_a_01234. arXiv:1904.03673v3.
https://​/​doi.org/​10.1162/​neco_a_01234
arXiv: 1904.03673v3

[52] Diederik P. Kingma och Jimmy Ba. Adam: En metod för stokastisk optimering. I 3rd International Conference for Learning Representations, 2015. URL https://​/​openreview.net/​forum?id=8gmWwjFyLj. arXiv:1412.6980.
arXiv: 1412.6980
https://​/​openreview.net/​forum?id=8gmWwjFyLj

[53] Alexei Kitaev och William A. Webb. Vågfunktionsförberedelse och omsampling med hjälp av en kvantdator, 2008. arXiv:0801.0342.
arXiv: 0801.0342

[54] Bobby Kleinberg, Yuanzhi Li och Yang Yuan. En alternativ syn: När slipper SGD lokala minima? I International Conference on Machine Learning, sidorna 2698–2707. PMLR, 2018. URL http://​/​proceedings.mlr.press/​v80/​kleinberg18a.html. arXiv:1802.06175.
arXiv: 1802.06175
http://​/​proceedings.mlr.press/​v80/​kleinberg18a.html

[55] Guy Kornowski och Ohad Shamir. Oracle-komplexitet i ojämn icke-konvex optimering. In Advances in Neural Information Processing Systems, 2021. URL https://​/​openreview.net/​forum?id=aMZJBOiOOPg. arXiv:2104.06763v2.
arXiv: 2104.06763v2
https://​/​openreview.net/​forum?id=aMZJBOiOOPg

[56] Rohith Kuditipudi, Xiang Wang, Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Rong Ge och Sanjeev Arora. Förklara landskapsanslutningen till lågkostnadslösningar för flerskiktsnät. Advances in Neural Information Processing Systems, 32: 14601–14610, 2019. URL http://​/​papers.nips.cc/​paper/​9602-explaining-landscape-connectivity-of-low-cost-solutions-for- flerskiktsnät. arXiv:1906.06247.
arXiv: 1906.06247
http://​/​papers.nips.cc/​paper/​9602-explaining-landscape-connectivity-of-low-cost-solutions-for-multilayer-nets

[57] Harold J. Kushner och G. George Yin. Stochastic Approximation and Recursive Algorithms and Applications, volym 35. Springer Science & Business Media, 2003. 10.1007/​978-1-4471-4285-0_3.
https:/​/​doi.org/​10.1007/​978-1-4471-4285-0_3

[58] Keren Li, Shijie Wei, Pan Gao, Feihao Zhang, Zengrong Zhou, Tao Xin, Xiaoting Wang, Patrick Rebentrost och Guilu Long. Optimera en polynomfunktion på en kvantprocessor. npj Quantum Information, 7 (1): 1–7, 2021a. 10.1038/​s41534-020-00351-5. arXiv:1804.05231.
https:/​/​doi.org/​10.1038/​s41534-020-00351-5
arXiv: 1804.05231

[59] Zhiyuan Li, Sadhika Malladi och Sanjeev Arora. Om giltigheten av modellering av SGD med stokastiska differentialekvationer (SDE). In Advances in Neural Information Processing Systems, 2021b. URL https://​/​openreview.net/​forum?id=goEdyJ_nVQI. arXiv:2102.12470.
arXiv: 2102.12470
https://​/​openreview.net/​forum?id=goEdyJ_nVQI

[60] Guang Hao Low och Nathan Wiebe. Hamiltonsimulering i interaktionsbilden, 2019. URL https://​/​arxiv.org/​abs/​1805.00675v2. arXiv:1805.00675v2.
arXiv: 1805.00675v2

[61] Cong Ma, Kaizheng Wang, Yuejie Chi och Yuxin Chen. Implicit regularisering i icke-konvex statistisk uppskattning: Gradientnedstigning konvergerar linjärt för fasåtervinning och matriskomplettering. I International Conference on Machine Learning, sidorna 3345–3354. PMLR, 2018. URL http://​/​proceedings.mlr.press/​v80/​ma18c.html. arXiv:1711.10467.
arXiv: 1711.10467
http://​/​proceedings.mlr.press/​v80/​ma18c.html

[62] Tengyu Ma. Varför löser lokala metoder icke-konvexa problem?, sid 465–485. Cambridge University Press, 2021. 10.1017/​9781108637435.027. arXiv:2103.13462.
https: / / doi.org/ 10.1017 / 9781108637435.027
arXiv: 2103.13462

[63] Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion och Michael I. Jordan. Sampling kan vara snabbare än optimering. Proceedings of the National Academy of Sciences, 116 (42): 20881–20885, 2019. URL https://​/​www.pnas.org/​content/​116/​42/​20881.short. arXiv:.
https: / / doi.org/ 10.1073 / pnas.1820003116
https://​/​www.pnas.org/​content/​116/​42/​20881.short

[64] Peter A. Markowich och Cédric Villani. Om trenden till jämvikt för Fokker-Planck-ekvationen: ett samspel mellan fysik och funktionell analys. In Physics and Functional Analysis, Matematica Contemporanea (SBM) 19. Citeseer, 1999. URL http://​/​citeseerx.ist.psu.edu/​viewdoc/​summary?doi=10.1.1.35.2278.
http://​/​citeseerx.ist.psu.edu/​viewdoc/​summary?doi=10.1.1.35.2278

[65] Laurent Michel. Om små egenvärden hos Witten Laplacian. Ren och tillämpad analys, 1 (2): 149 – 206, 2019. 10.2140/​paa.2019.1.149. URL https://​/​doi.org/​10.2140/​paa.2019.1.149. arXiv:1702.01837.
https://​/​doi.org/​10.2140/​paa.2019.1.149
arXiv: 1702.01837

[66] Siddharth Muthukrishnan, Tameem Albash och Daniel A. Lidar. Tunnling och snabbare kvantoptimering för permutationssymmetriska problem. Physical Review X, 6: 031010, jul 2016. ISSN 2160-3308. 10.1103/​physrevx.6.031010. URL http://​dx.doi.org/​10.1103/​PhysRevX.6.031010. arXiv:1511.03910.
https: / / doi.org/ 10.1103 / physrevx.6.031010
arXiv: 1511.03910

[67] Quynh Nguyen. På uppkopplad undernivå sätts i djupinlärning. I International Conference on Machine Learning, sidorna 4790–4799. PMLR, 2019. URL http://​/​proceedings.mlr.press/​v97/​nguyen19a.html. arXiv:1901.07417.
arXiv: 1901.07417
http://​/​proceedings.mlr.press/​v97/​nguyen19a.html

[68] Michael A. Nielsen och Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. 10.1017 / CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

[69] Grigorios A. Pavliotis. Stokastiska processer och tillämpningar: diffusionsprocesser, Fokker-Planck och Langevins ekvationer, volym 60. Springer, 2014. 10.1007/​978-1-4939-1323-7.
https:/​/​doi.org/​10.1007/​978-1-4939-1323-7

[70] Qing Qu, Yuexiang Zhai, Xiao Li, Yuqian Zhang och Zhihui Zhu. Analys av optimeringslandskapen för överfullständig representationsinlärning, 2019. arXiv:1912.02427.
arXiv: 1912.02427

[71] Gianluca Rastelli. Semiklassisk formel för kvanttunneling i asymmetriska dubbelbrunnspotentialer. Physical Review A, 86: 012106, juli 2012. 10.1103/​PhysRevA.86.012106. URL https://​/​link.aps.org/​doi/​10.1103/​PhysRevA.86.012106. arXiv:1205.0366.
https: / / doi.org/ 10.1103 / PhysRevA.86.012106
arXiv: 1205.0366

[72] Arthur G. Rattew, Yue Sun, Pierre Minssen och Marco Pistoia. Den effektiva beredningen av normalfördelningar i kvantregister. Quantum, 5: 609, 2021. 10.22331/​q-2021-12-23-609. URL https://​/​quantum-journal.org/​papers/​q-2021-12-23-609/​. arXiv:2009.06601.
https:/​/​doi.org/​10.22331/​q-2021-12-23-609
arXiv: 2009.06601
https: / / quantum-journal.org/ papers / q-2021-12-23-609 /

[73] Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione och Seth Lloyd. Quantum gradient descent och Newtons metod för begränsad polynomoptimering. New Journal of Physics, 21 (7): 073023, 2019. 10.1088/​1367-2630/​ab2a9e. arXiv:1612.01789.
https:/​/​doi.org/​10.1088/​1367-2630/​ab2a9e
arXiv: 1612.01789

[74] Burak Şahinoğlu och Rolando D. Somma. Hamiltonsimulering i lågenergiunderrummet. npj Quantum Information, 7 (1): 1–5, 2021. 10.1038/​s41534-021-00451-w. URL https://​/​www.nature.com/​articles/​s41534-021-00451-w. arXiv:2006.02660.
https: / / doi.org/ 10.1038 / s41534-021-00451-w
arXiv: 2006.02660
https://​/​www.nature.com/​articles/​s41534-021-00451-w

[75] JM Schmidt, AN Cleland och John Clarke. Resonant tunnling i små strömförspända Josephson-korsningar. Physical Review B, 43: 229–238, jan 1991. 10.1103/​PhysRevB.43.229. URL https://​/​link.aps.org/​doi/​10.1103/​PhysRevB.43.229.
https: / / doi.org/ 10.1103 / PhysRevB.43.229

[76] Alexander Shevchenko och Marco Mondelli. Landskapsanslutning och avbrottsstabilitet för SGD-lösningar för överparameteriserade neurala nätverk. I International Conference on Machine Learning, sidorna 8773–8784. PMLR, 2020. URL http://​/​proceedings.mlr.press/​v119/​shevchenko20a.html. arXiv:1912.10095.
arXiv: 1912.10095
http://​/​proceedings.mlr.press/​v119/​shevchenko20a.html

[77] Bin Shi, Weijie J. Su och Michael I. Jordan. Om lärandehastigheter och Schrödinger-operatörer, 2020. arXiv:2004.06977.
arXiv: 2004.06977

[78] Bin Shi, Simon S. Du, Michael I. Jordan och Weijie J. Su. Förstå accelerationsfenomenet via högupplösta differentialekvationer. Matematisk programmering, sidorna 1–70, 2021. 10.1007/​s10107-021-01681-8. URL https://​/​doi.org/​10.1007/​s10107-021-01681-8. arXiv:1810.08907.
https:/​/​doi.org/​10.1007/​s10107-021-01681-8
arXiv: 1810.08907

[79] Weijie Su, Stephen Boyd och Emmanuel J. Candes. En differentialekvation för modellering av Nesterovs accelererade gradientmetod: Teori och insikter. The Journal of Machine Learning Research, 17 (1): 5312–5354, 2016. 10.5555/​2946645.3053435. URL https://​/​dl.acm.org/​doi/​abs/​10.5555/​2946645.3053435. arXiv:1503.01243.
https: / / doi.org/ 10.5555 / 2946645.3053435
arXiv: 1503.01243

[80] Ruoyu Sun. Optimering för djupt lärande: teori och algoritmer, 2019. arXiv:1912.08957.
arXiv: 1912.08957

[81] Kunal Talwar. Beräkningsseparationer mellan sampling och optimering. Advances in Neural Information Processing Systems, 32: 15023–15033, 2019. URL http://​/​papers.nips.cc/​paper/​9639-computational-separations-between-sampling-and-optimization. arXiv:1911.02074.
arXiv: 1911.02074
http://​/​papers.nips.cc/​paper/​9639-computational-separations-between-sampling-and-optimization

[82] Hao Tang, Xiao-Feng Lin, Zhen Feng, Jing-Yuan Chen, Jun Gao, Ke Sun, Chao-Yue Wang, Peng-Cheng Lai, Xiao-Yun Xu, Yao Wang, Lu-Feng Qiao, Ai-Lin Yang, och Xian-Min Jin. Experimentell tvådimensionell kvantvandring på ett fotoniskt chip. Science advances, 4 (5): eaat3174, 2018. 10.1126/​sciadv.aat3174. URL https://​/​www.science.org/​doi/​10.1126/​sciadv.aat3174. arXiv:1704.08242.
https: / / doi.org/ 10.1126 / sciadv.aat3174
arXiv: 1704.08242

[83] Cédric Villani. Hypocoercivity, volym 202 av Memoirs of the American Mathematical Society. American Mathematical Society, 2009. 10.1090/​S0065-9266-09-00567-5. arXiv:math/​0609050.
https:/​/​doi.org/​10.1090/​S0065-9266-09-00567-5
arXiv: math / 0609050

[84] Andre Wibisono, Ashia C. Wilson och Michael I. Jordan. Ett variationsperspektiv på accelererade metoder inom optimering. Proceedings of the National Academy of Sciences, 113 (47): E7351–E7358, 2016. 10.1073/​pnas.1614734113. URL https://​/​doi.org/​10.1073/​pnas.1614734113. arXiv:1603.04245.
https: / / doi.org/ 10.1073 / pnas.1614734113
arXiv: 1603.04245

[85] Chenyi Zhang och Tongyang Li. Undvik sadelpunkter med en enkel gradient-nedstigningsbaserad algoritm. In Advances in Neural Information Processing Systems, volym 34, 2021. URL https://​/​openreview.net/​forum?id=lEf52hTHq0Q. arXiv:2111.14069.
arXiv: 2111.14069
https://​/​openreview.net/​forum?id=lEf52hTHq0Q

[86] Chenyi Zhang, Jiaqi Leng och Tongyang Li. Kvantalgoritmer för att fly från sadelpunkter. Quantum, 5: 529, 2021a. 10.22331/​q-2021-08-20-529. arXiv:2007.10253.
https:/​/​doi.org/​10.22331/​q-2021-08-20-529
arXiv: 2007.10253

[87] Kaining Zhang, Min-Hsiu Hsieh, Liu Liu och Dacheng Tao. Kvantalgoritm för att hitta den negativa krökningsriktningen vid icke-konvex optimering, 2019. arXiv:1909.07622.
arXiv: 1909.07622

[88] Yuqian Zhang, Qing Qu och John Wright. Från symmetri till geometri: Tractable nonconvex problems, 2021b. arXiv:2007.06753.
arXiv: 2007.06753

Citerad av

[1] Weiyuan Gong, Chenyi Zhang och Tongyang Li, "Robustness of Quantum Algorithms for Nonconvex Optimization", arXiv: 2212.02548, (2022).

Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2023-06-02 12:31:17). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.

Det gick inte att hämta Crossref citerade data under senaste försöket 2023-06-02 12:31:15: Det gick inte att hämta citerade data för 10.22331 / q-2023-06-02-1030 från Crossref. Detta är normalt om DOI registrerades nyligen.

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.

Tidsstämpel:

Mer från Quantum Journal