Poster
Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss
Hao Wang · Chenyi Zhang · Tongyang Li
Halle B #312
Abstract:
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 of 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 ˜O(√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.
Chat is not available.