https://m2.mtmt.hu/ hun 2026-10-23 16:50 BookChapter 35749169 APPROVED true Conference code: 200372 Export Date: 10 February 2025 Funding details: Peking University, PKU Funding details: National Natural Science Foundation of China, NSFC, 62372006, 92365117 Funding text 1: We thank Adam Bouland, Tudor Giurgica-Tiron, and Aaron Sidford for helpful discussions. CZ was supported in part by the Shoucheng Zhang Graduate Fellowship. TL was supported by the National Natural Science Foundation of China (Grant Numbers 62372006 and 92365117), and a startup fund from Peking University. 0 false 2025-02-28T12:35:16.177+0000 2025-02-27T22:16:15.954+0000 2025-02-10T10:57:23.044+0000 true 10084481 Toroczkai Annamária /api/admin/10084481 Admin Toroczkai Annamária (idézők, admin) true 2025-02-28T12:34:02.321+0000 2025-02-28T12:34:02.321+0000 false false true 31 31 /api/publicationtype/31 PublicationType Egyéb konferenciaközlemény 4 true 31 BookChapter true 10000197 Conference paper true 31 31 /api/publicationtype/31 PublicationType Egyéb konferenciaközlemény 4 true 31 BookChapter /api/subtype/10000197 Konferenciaközlemény SubType Konferenciaközlemény (Egyéb konferenciaközlemény) 452 true 10000197 true 1 /api/category/1 Category Tudományos true 1 Wang, H. & & 2024 The problem of minimizing the maximum of N convex, Lipschitz functions plays significant roles in optimization and machine learning. It has a series of results, with the most recent one requiring O(Nϵ−2/3 + ϵ−8/3) queries to a first-order oracle to compute an ϵ-suboptimal point. On the other hand, quantum algorithms for optimization are rapidly advancing with speedups shown on many important optimization problems. In this paper, we conduct a systematic study for quantum algorithms and lower bounds for minimizing the maximum of N convex, Lipschitz functions. On one hand, we develop quantum algorithms with an improved complexity bound of Õ(√Nϵ−5/3 + ϵ−8/3). On the other hand, we prove that quantum algorithms must take Ω̃(√Nϵ−2/3) queries to a first order quantum oracle, showing that our dependence on N is optimal up to poly-logarithmic factors. © 2024 12th International Conference on Learning Representations, ICLR 2024. All rights reserved. 2025 true true true false NONE 2025-02-28 false 0 0 0 0 0 0 0 0 0 0 0 0 2 2 false false false false 2025-05-28T21:16:15.832+0000 1 14 0 3 0 true true 10002 English /api/language/10002 Angol Language Angol true 2 false true 26946994 IDENTICAL /api/publicationidentifier/26946994 https://openreview.net/group?id=ICLR.cc/2024/Conference#tab-accept-oral https://openreview.net/group?id=ICLR.cc/2024/Conference#tab-accept-oral PublicationIdentifier Egyéb URL: https://openreview.net/group?id=ICLR.cc/2024/Conference#tab-accept-oral true 40 Other URL @@@ /api/publicationsource/40 Egyéb URL PlainSource Egyéb URL true true 10006 /api/publicationsourcetype/10006 PublicationSourceType Link true true 40 true false true 27812562 IDENTICAL /api/publicationidentifier/27812562 https://iclr.cc/Conferences/2024 https://iclr.cc/Conferences/2024 PublicationIdentifier Egyéb URL: https://iclr.cc/Conferences/2024 true 40 Other URL @@@ /api/publicationsource/40 Egyéb URL PlainSource Egyéb URL true true 10006 /api/publicationsourcetype/10006 PublicationSourceType Link true true 40 true false /api/publication/35178194 12th International Conference on Learning Representations, ICLR 2024. (2024) true true 32 32 /api/publicationtype/32 PublicationType Egyéb konferenciakötet 6 true 32 Book false 35178194 false true true false Book 2024 true 1 /api/category/1 Category Tudományos true 1 false Language 10002 /api/language/10002 Angol Angol English true 2 true PersonAuthorship 123222606 /api/authorship/123222606 Wang, H. 1 0.33333334 true false false Wang H. true false false AuthorshipType 1 /api/authorshiptype/1 Szerző 0 true 0 true false true PersonAuthorship 123222607 /api/authorship/123222607 Zhang, C. 2 0.33333334 false false false Zhang C. true false false AuthorshipType 1 /api/authorshiptype/1 Szerző 0 true 0 true false true PersonAuthorship 123222608 /api/authorship/123222608 Li, T. 3 0.33333334 false true false Li T. true false false AuthorshipType 1 /api/authorshiptype/1 Szerző 0 true 0 true false true PublicationIdentifier 28373443 /api/publicationidentifier/28373443 Scopus: 85200598050 PlainSource 3 /api/publicationsource/3 Scopus PublicationSourceType 10003 /api/publicationsourcetype/10003 Indexelő adatbázis false true true Scopus http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-@@@ true true 3 true 85200598050 http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85200598050 false true Keyword 1007771 /api/keyword/1007771 Quantum Theory true 1007771 true Keyword 1051858 /api/keyword/1051858 LIPSCHITZ FUNCTIONS true 1051858 true Keyword 1069279 /api/keyword/1069279 Optimisations true 1069279 true Keyword 1072827 /api/keyword/1072827 Machine-learning true 1072827 true Keyword 1072927 /api/keyword/1072927 Optimization problems true 1072927 true Keyword 1072950 /api/keyword/1072950 Complexity bounds true 1072950 true Keyword 1104983 /api/keyword/1104983 Systematic study true 1104983 true Keyword 1324956 /api/keyword/1324956 quantum algorithms true 1324956 true Keyword 1670717 /api/keyword/1670717 First order true true Keyword 1786627 /api/keyword/1786627 Near-optimal true true Keyword 2373622 /api/keyword/2373622 Low bound true true Reference 63212577 /api/reference/63212577 1. Jordan, Stephen P., Fast quantum algorithm for numerical gradient estimation (2005) Physical Review Letters, 95 (5), p. 050501 1 false true Reference 63212544 /api/reference/63212544 2. Allen-Zhu, Zeyuan, Katyusha: The first direct acceleration of stochastic gradient methods (2017) The Journal of Machine Learning Research, 18 (1), pp. 8194-8244 2 false true Reference 63212545 /api/reference/63212545 3. Arjevani, Yossi, Carmon, Yair, Duchi, John C., Foster, Dylan J., Sekhari, Ayush, Sridharan, Karthik, Second-order information in non-convex stochastic optimization: Power and limitations (2020) Conference on Learning Theory, pp. 242-299. , PMLR 3 false true Reference 63212546 /api/reference/63212546 4. Arjevani, Yossi, Carmon, Yair, Duchi, John C., Foster, Dylan J., Srebro, Nathan, Woodworth, Blake, Lower bounds for non-convex stochastic optimization (2022) Mathematical Programming, pp. 1-50 4 false true Reference 63212547 /api/reference/63212547 5. Augustino, Brandon, Nannicini, Giacomo, Terlaky, Tamás, Zuluaga, Luis F., (2021) Quantum interior point methods for semidefinite optimization 5 false true Reference 63212548 /api/reference/63212548 6. Ben-Tal, Aharon, Ghaoui, Laurent El, Nemirovski, Arkadi, (2009) Robust optimization, 28. , Princeton University Press 6 false true Reference 63212549 /api/reference/63212549 7. Ben-Tal, Aharon, Hertog, Dick Den, De Waegenaere, Anja, Melenberg, Bertrand, Rennen, Gijs, Robust solutions of optimization problems affected by uncertain probabilities (2013) Management Science, 59 (2), pp. 341-357 7 false true Reference 63212550 /api/reference/63212550 8. Beyer, Hans-Georg, Sendhoff, Bernhard, Robust optimization-a comprehensive survey (2007) Computer Methods in Applied Mechanics and Engineering, 196 (33-34), pp. 3190-3218 8 false true Reference 63212551 /api/reference/63212551 9. Bouland, Adam, Getachew, Yosheb, Jin, Yujia, Sidford, Aaron, Tian, Kevin, (2023) Quantum speedups for zero-sum games via improved dynamic gibbs sampling 9 false true Reference 63212552 /api/reference/63212552 10. Brandão, Fernando G.S.L., Svore, Krysta M., Quantum speed-ups for solving semidefinite programs (2017) 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 415-426. , IEEE 10 false true Reference 63212553 /api/reference/63212553 11. Brandão, Fernando G.S.L., Kalev, Amir, Li, Tongyang, Yen-Yu Lin, Cedric, Svore, Krysta M., Wu, Xiaodi, Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning (2019) Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 1-27:14. , 27: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik 11 false true Reference 63212554 /api/reference/63212554 12. Brassard, Gilles, Høyer, Peter, Mosca, Michele, Tapp, Alain, Quantum amplitude amplification and estimation (2002) Contemporary Mathematics, 305, pp. 53-74 12 false true Reference 63212555 /api/reference/63212555 13. Bubeck, Sébastien, Jiang, Qijia, Lee, Yin-Tat, Li, Yuanzhi, Sidford, Aaron, Complexity of highly parallel non-smooth convex optimization (2019) Advances in Neural Information Processing Systems, 32 13 false true Reference 63212556 /api/reference/63212556 14. Bullins, Brian, Highly smooth minimization of non-smooth problems (2020) Conference on Learning Theory, pp. 988-1030. , PMLR 14 false true Reference 63212557 /api/reference/63212557 15. Carmon, Yair, Duchi, John C., Hinder, Oliver, Sidford, Aaron, Lower bounds for finding stationary points I (2020) Mathematical Programming, 184 (1), pp. 71-120 15 false true Reference 63212558 /api/reference/63212558 16. Carmon, Yair, Jambulapati, Arun, Jiang, Qijia, Jin, Yujia, Lee, Yin Tat, Sidford, Aaron, Tian, Kevin, Acceleration with a ball optimization oracle (2020) Advances in Neural Information Processing Systems, 33, pp. 19052-19063 16 false true Reference 63212559 /api/reference/63212559 17. Carmon, Yair, Jambulapati, Arun, Jin, Yujia, Sidford, Aaron, Thinking inside the ball: Near-optimal minimization of the maximal loss (2021) Conference on Learning Theory, pp. 866-882. , PMLR 17 false true Reference 63212560 /api/reference/63212560 18. Chakrabarti, Shouvanik, Childs, Andrew M., Li, Tongyang, Wu, Xiaodi, Quantum algorithms and lower bounds for convex optimization (2020) Quantum, 4, p. 221 18 false true Reference 63212561 /api/reference/63212561 19. Childs, Andrew M., Leng, Jiaqi, Li, Tongyang, Liu, Jin-Peng, Zhang, Chenyi, Quantum simulation of real-space dynamics (2022) Quantum, 6, p. 680 19 false true Reference 63212562 /api/reference/63212562 20. Clarkson, Kenneth L., Hazan, Elad, Woodruff, David P., Sublinear optimization for machine learning (2012) Journal of the ACM (JACM), 59 (5), pp. 1-49 20 false true Reference 63212563 /api/reference/63212563 21. Cornelissen, Arjan, Hamoudi, Yassine, Jerbi, Sofiene, Near-optimal quantum algorithms for multivariate mean estimation (2022) Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 33-43 21 false true Reference 63212564 /api/reference/63212564 22. Delage, Erick, Ye, Yinyu, Distributionally robust optimization under moment uncertainty with application to data-driven problems (2010) Operations Research, 58 (3), pp. 595-612 22 false true Reference 63212565 /api/reference/63212565 23. Diakonikolas, Jelena, Guzmán, Cristóbal, Lower bounds for parallel and randomized convex optimization (2019) Conference on Learning Theory, pp. 1132-1157. , PMLR 23 false true Reference 63212566 /api/reference/63212566 24. Dürr, Christoph, Heiligman, Mark, HOyer, Peter, Mhalla, Mehdi, Quantum query complexity of some graph problems (2006) SIAM Journal on Computing, 35 (6), pp. 1310-1328. , https://doi.org/10.1137%2F050644719, jan 24 false true Reference 63212567 /api/reference/63212567 25. Gao, Minbo, Ji, Zhengfeng, Li, Tongyang, Wang, Qisheng, (2023) Logarithmic-regret quantum learning algorithms for zero-sum games 25 false true Reference 63212568 /api/reference/63212568 26. Garg, Ankit, Kothari, Robin, Netrapalli, Praneeth, Sherif, Suhail, No quantum speedup over gradient descent for non-smooth convex optimization (2021) 12th Innovations in Theoretical Computer Science Conference 26 false true Reference 63212569 /api/reference/63212569 27. Garg, Ankit, Kothari, Robin, Netrapalli, Praneeth, Sherif, Suhail, Near-optimal lower bounds for convex optimization for all orders of smoothness (2021) Advances in Neural Information Processing Systems, 34, pp. 29874-29884 27 false true Reference 63212570 /api/reference/63212570 28. Gasnikov, Alexander, Dvurechensky, Pavel, Gorbunov, Eduard, Vorontsova, Evgeniya, Selikhanovych, Daniil, Uribe, César A, Jiang, Bo, Bubeck, Sébastien, Near optimal methods for minimizing convex functions with lipschitz p-th derivatives (2019) Conference on Learning Theory, pp. 1392-1393. , PMLR 28 false true Reference 63212571 /api/reference/63212571 29. Gong, Weiyuan, Zhang, Chenyi, Li, Tongyang, (2022) Robustness of quantum algorithms for nonconvex optimization 29 false true Reference 63212572 /api/reference/63212572 30. Grover, Lov, Rudolph, Terry, (2002) Creating superpositions that correspond to efficiently integrable probability distributions 30 false true Reference 63212573 /api/reference/63212573 31. Guzmán, Cristóbal, Nemirovski, Arkadi, On lower complexity bounds for large-scale smooth convex optimization (2015) Journal of Complexity, 31 (1), pp. 1-14 31 false true Reference 63212574 /api/reference/63212574 32. Hamoudi, Yassine, Preparing many copies of a quantum state in the black-box model (2022) Physical Review A, 105 (6), p. 062440 32 false true Reference 63212575 /api/reference/63212575 33. Hazan, Elad, Kale, Satyen, Beyond the Regret Minimization Barrier: Optimal Algorithms for Stochastic Strongly-Convex Optimization (2014) Journal of Machine Learning Research, 15 (71), pp. 2489-2512. , http://jmlr.org/papers/v15/hazan14a.html 33 false true Reference 63212576 /api/reference/63212576 34. Hazan, Elad, Koren, Tomer, Srebro, Nati, Beating SGD: Learning SVMs in sublinear time (2011) Advances in Neural Information Processing Systems, 24 34 false true Reference 63212578 /api/reference/63212578 35. Kaye, Phillip, Mosca, Michele, Quantum networks for generating arbitrary quantum states (2001) Optical Fiber Communication Conference and International Conference on Quantum Information, p. PB28. , https://opg.optica.org/abstract.cfm?URI=ICQI-2001-PB28, Optica Publishing Group 35 false true Reference 63212579 /api/reference/63212579 36. Kerenidis, Iordanis, Prakash, Anupam, A quantum interior point method for LPs and SDPs (2020) ACM Transactions on Quantum Computing, 1 (1), pp. 1-32 36 false true Reference 63212580 /api/reference/63212580 37. Li, Tongyang, Chakrabarti, Shouvanik, Wu, Xiaodi, Sublinear quantum algorithms for training linear and kernel-based classifiers (2019) International Conference on Machine Learning, pp. 3815-3824. , PMLR 37 false true Reference 63212581 /api/reference/63212581 38. Liu, Yizhou, Su, Weijie J., Li, Tongyang, (2022) On quantum speedups for nonconvex optimization via quantum tunneling walks 38 false true Reference 63212582 /api/reference/63212582 39. Monteiro, Renato DC, Svaiter, Benar Fux, An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods (2013) SIAM Journal on Optimization, 23 (2), pp. 1092-1125 39 false true Reference 63212583 /api/reference/63212583 40. Nemirovski, Arkadi Semenovič, Yudin, David Borisovich, (1983) Problem complexity and method efficiency in optimization, , Wiley-Interscience 40 false true Reference 63212584 /api/reference/63212584 41. Nesterov, Y., Smooth minimization of non-smooth functions (2005) Mathematical programming, 103, pp. 127-152 41 false true Reference 63212585 /api/reference/63212585 42. Nesterov, Yurii, (2018) Lectures on convex optimization, 137. , Springer 42 false true Reference 63212586 /api/reference/63212586 43. Shalev-Shwartz, Shai, Wexler, Yonatan, Minimizing the maximal loss: How and why (2016) International Conference on Machine Learning, pp. 793-801. , PMLR 43 false true Reference 63212587 /api/reference/63212587 44. Shor, Peter W., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer (1999) SIAM Review, 41 (2), pp. 303-332 44 false true Reference 63212588 /api/reference/63212588 45. van Apeldoorn, Joran, Gilyén, András, Improvements in quantum sdp-solving with applications (2019) 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), , Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik 45 false true Reference 63212589 /api/reference/63212589 46. van Apeldoorn, Joran, Gilyén, András, Gribling, Sander, de Wolf, Ronald, Convex optimization using quantum oracles (2020) Quantum, 4, p. 220 46 false true Reference 63212590 /api/reference/63212590 47. van Apeldoorn, Joran, Gilyén, András, Gribling, Sander, de Wolf, Ronald, Quantum SDP-solvers: Better upper and lower bounds (2020) Quantum, 4, p. 230 47 false true Reference 63212591 /api/reference/63212591 48. Vapnik, Vladimir N., An overview of statistical learning theory (1999) IEEE Transactions on Neural Networks, 10 (5), pp. 988-999 48 false true Reference 63212592 /api/reference/63212592 49. Woodworth, Blake E., Srebro, Nati, Tight complexity bounds for optimizing composite objectives (2016) Advances in Neural Information Processing Systems, 29 49 false true Reference 63212593 /api/reference/63212593 50. Zalka, Christof, Simulating quantum systems on a quantum computer (1998) Proceedings of the Royal Society of London Series A: Mathematical, Physical and Engineering Sciences, 454 (1969), pp. 313-322 50 false true Reference 63212594 /api/reference/63212594 51. Zhang, Chenyi, Li, Tongyang, Quantum lower bounds for finding stationary points of nonconvex functions (2023) International Conference on Machine Learning. PMLR 51 false true Reference 63212595 /api/reference/63212595 52. Zhang, Chenyi, Leng, Jiaqi, Li, Tongyang, Quantum algorithms for escaping from saddle points (2021) Quantum, 5, p. 529 52 false true /api/publication/35749169 Wang H. et al. NEAR-OPTIMAL QUANTUM ALGORITHM FOR MINIMIZING THE MAXIMAL LOSS. (2024) Megjelent: 12th International Conference on Learning Representations, ICLR 2024 p. &<div class="BookChapter Publication long-list"> <div class="authors"> <img title="Idézőközlemény" style="float: left" src="/frontend/resources/grid/publication-citation-icon.png"> <div class="autype autype0"> <span class="author-name" >Wang H. </span> ;&nbsp;&nbsp;&nbsp; <span class="author-name" >Zhang C. </span> ;&nbsp;&nbsp;&nbsp; <span class="author-name" >Li T. </span> </div> </div> <div class="title"><a href="/gui2/?mode=browse&params=publication;35749169" target="_blank">NEAR-OPTIMAL QUANTUM ALGORITHM FOR MINIMIZING THE MAXIMAL LOSS</a></div> <div class="InBook"><div class="chapter-in">In:</div> <div class="authors"> </div> <div class="booktitle"><a href="/gui2/?mode=browse&params=publication;35178194" target="_blank">12th International Conference on Learning Representations, ICLR 2024 </a></div> <div class="conference"> Konferencia helye, ideje: <span class="conference-date">2024.05.07. - 2024.05.11.</span> </div> : <span class="publishers">International Conference on Learning Representations, ICLR</span>, <span class="page"> p. &. </span> <span class="year">(2024)</span> </div> <div class="pub-footer"> <span class="language" xmlns="http://www.w3.org/1999/html">Nyelv: Angol | </span> <span class="identifiers"> <span class="id identifier oa_none" title="none"> <a style="color:black" title="85200598050" target="_blank" href="http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85200598050"> Scopus </a> </span> </span> <span class="bookchapter-ids">Befoglaló link(ek):</span> <span class="identifiers"> <span class="id identifier oa_none" title="none"> <a style="color:blue" title="https://openreview.net/group?id=ICLR.cc/2024/Conference#tab-accept-oral" target="_blank" href="https://openreview.net/group?id=ICLR.cc/2024/Conference#tab-accept-oral"> Egyéb URL </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:blue" title="https://iclr.cc/Conferences/2024" target="_blank" href="https://iclr.cc/Conferences/2024"> Egyéb URL </a> </span> </span> <div class="publication-citation"> <a target="_blank" href="/api/publication?cond=citations.related;eq;35749169&sort=publishedYear,desc&sort=title"> Idézett közlemények száma: 2 </a> </div> <div class="mtid"><span class="long-pub-mtid">Közlemény: 35749169</span> | <span class="status-data status-APPROVED"> Nyilvános </span> <span class="long-book-mtid">Befoglaló: 35178194</span> Idéző | <span class="type-subtype">Egyéb konferenciaközlemény ( Konferenciaközlemény ) </span> | <span class="pub-category">Tudományos</span> | <span class="publication-sourceOfData">Scopus</span> </div> <div class="lastModified">Utolsó módosítás: 2025.02.27. 23:16 Szakonyi Erzsebet (RAMKI admin 4) </div> <pre class="comment" style="margin-top: 0; margin-bottom: 0;"><u>Megjegyzés</u>: Conference code: 200372 Export Date: 10 February 2025 Funding details: Peking University, PKU Funding details: National Natural Science Foundation of China, NSFC, 62372006, 92365117 Funding text 1: We thank Adam Bouland, Tudor Giurgica-Tiron, and Aaron Sidford for helpful discussions. CZ was supporte...</pre> </div> </div>