تقرير
Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss
| العنوان: | Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss |
|---|---|
| المؤلفون: | Wang, Hao, Zhang, Chenyi, Li, Tongyang |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics Quantum Physics |
| مصطلحات موضوعية: | Quantum Physics, Computer Science - Data Structures and Algorithms, Mathematics - Optimization and Control |
| الوصف: | 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\epsilon^{-2/3} + \epsilon^{-8/3})$ queries to a first-order oracle to compute an $\epsilon$-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 $\tilde{O}(\sqrt{N}\epsilon^{-5/3} + \epsilon^{-8/3})$. On the other hand, we prove that quantum algorithms must take $\tilde{\Omega}(\sqrt{N}\epsilon^{-2/3})$ queries to a first order quantum oracle, showing that our dependence on $N$ is optimal up to poly-logarithmic factors. Comment: 22 pages, 1 figure, To appear in The Twelfth International Conference on Learning Representations (ICLR 2024) |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2402.12745 |
| رقم الأكسشن: | edsarx.2402.12745 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |