Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss

The paper considers a convex optimization problem where the function to be minimized is the maximum of $N$ convex Lipschitz functions. The paper presents a quantum algorithm which finds an $\epsilon$-good solution using $\tilde{O}(\sqrt{N}\epsilon^{-5/3} + \epsilon^{-8/3})$ queries. The paper complements the algorithmic result with a lower bound showing that the dependence on $N$ is optimal up to logarithmic factors.

The paper builds on the classical algorithm of Carmon et. al. which is based on the Ball optimization acceleration technique, and then identifies parts where a quadratic quantum speedup can be applied.

The paper studies the question of minimizing the maximum of N convex Lipschitz loss functions f1, f2,...,fN. It is known that you can do so with O(N eps^{-2/3} + eps^{-8/3}) queries. The paper here studies a quantum version of the problem and achieve a complexity that is sqrt{N} eps^{-5/3} + eps^{-8/3}. While the eps-dependence is slightly worse, the dependence on N has improved by a quadratic factor.

The main idea is to take a classical algorithm for the problem and modify one of the key-steps to exploit quantum advantage. Specifically, the authors exploit the fact that the classical algorithm uses a regularized ball optimization oracle (BROO) which is similar to a Gibbs sampling problem. The latter is known to have a quantum advantage and exploiting the better algorithms for that gives the final result.

This paper designs new quantum algorithm for the problem of minimizing the maximum of $N$ convex functions with near optimal quantum query complexity.

Given $f_1,\ldots, f_N$ convex and $L$-Lipschitz functions from $\mathbb{R}^d$ to $\mathbb{R}$. The function $F_{max}(x)$ is defined as: $F_{max}(x)$ = ${max}_{i} \\{f_i(x)\\}$.

The goal is to find an $x*$ so that $F_{max}(x*) - inf_{x} F_{max}(x) \leq \epsilon$.

This is a fundamental optimization task and substantial research has gone in identifying the number of oracle queries required (say to $f_i$s and its gradients - called the first order oracle) as a function of both $N$ -- the number of functions, and $\epsilon$ -- the error parameter. Tight results have been established (matching upper and lower bounds in the number of queries) in the literature for some regimes of parameters (especially for $\epsilon \geq 1/\sqrt{N}$). However, these prior research only focused on 'classical queries.' In this paper the authors consider 'quantum query complexity' of the problem. It is well established that in general quantum query algorithms can get a quadratic speed up over classical query algorithm. The present paper extends that to the above described minimizing-the-maximum-loss problem.

The paper establishes an upper bound of $\tilde{O}(\sqrt{N} \epsilon^{-5/3} + \epsilon^{-8/3})$ and a lower bound of $\tilde{\Omega}(\sqrt{N}\epsilon^{-2/3})$ on the number of quantum queries required for solving the problem.

Thus with respect to $N$, the established results are optimal. But there is a gap in upper and lower bounds in terms of $\epsilon$. Closing this gap, the authors pose as a natural open question. The quantum oracle model they use is what is typically seen in the literature and is called the zeroth-order oracle in the optimization terminology.

The paper presents an improved quantum algorithm for minimizing the maximal loss of $N$ convex functions, the key idea is quantum Gibbs sampling subroutine that improves the classical subroutine.

The paper studies the problem of minimizing the loss of $N$ convex functions, i.e., $\min_{x} \max_{i \in [N]}f_{i}(x)$ for convex functions $f_{1}, \ldots, f_{N}$ given gradient oracle. The best classical algorithm for finding $\epsilon$-approximate solution is given by [Carmon et al. 2021] with $O(N\epsilon^{-2/3} +\epsilon^{-8/3})$ queries, which is known to be optimal in the low accuracy regime $\epsilon \geq 1/\sqrt{N}$. The idea is to approximate the maximal loss with softmax function and use the improved ball optimization oracle [Carmon et al. 2020].

The paper studies quantum algorithms and the algorithm is equipped with zero-th order quantum oracle (it can be used to obtain gradient oracle) and improve the bound to $O(\sqrt{N}\epsilon^{-5/3} +\epsilon^{-8/3})$. It also gives a lower bound saying $\Omega(\sqrt{N}\epsilon^{-2/3})$ queries are necessary for finding $\epsilon$-approximate solution.

The main idea of the algorithm is an improved estimation of the gradient, which in turns boils down to improved quantum Gibbs sampling procedure (note the gradient draws from a distribution, which requires $N$ queries, but quantum algorithm could take advantage and only needs $\sqrt{N}$ queries)

We thank all reviewers for their thoughtful consideration of our paper. We appreciate your generally positive recognition of our contributions and helpful suggestions for further improvements. Here we address some common questions that arose in multiple reviews.

Regarding the gap between the upper bound and lower bound in our paper, we would like to first note that our algorithm is easy to understand and implement. Additionally, the algorithm is near optimal in the sense that the dependency with respect to $N$ is indeed tight. From our understanding, the gap is not due to a weaker quantum zeroth-order oracle comparing to the classical first-order oracle since using Jordan's algorithm [1] we can still compute gradients from a quantum zeroth-order oracle. Instead, the gap is mainly due to the technique we use for the quantum speedup on sampling multiple times from the same distribution. Conceptually, the technique is making a trade-off between $N$ and $\epsilon$. Comparing to the classical algorithm where the sampling cost is $O(N)$, our sampling subroutine takes $\tilde{O}(\sqrt{NT})$ to prepare the samplings according to Lemma 3 in Appendix A, in which $T$ is the number of samples needed and is relevant to $\epsilon$. This is because our quantum algorithm needs to prepare $T$ independent quantum states using amplitude amplification in Line 5 of Algorithm 2, while classical algorithm directly computes the distribution and the number of samples is irrelevant to the cost. Although each sample only takes $\sqrt{N/T}$ queries according to Proposition 3 and Lemma 3, the repetitive preparation would cost $\tilde{O}(\sqrt{NT})$ in total. Notably, previous theory results on quantum machine learning focused more on speedups of dimension factors, even though the dependency on $\epsilon$ is potentially of higher order. For example:

Ref. [2] in ICML 2019 addressed linear classification and kernel-based classification problem for $n$ $d$-dimensional data points with quantum gate complexity $\tilde{O}(\sqrt{n}/\epsilon^{4}+\sqrt{d}/\epsilon^{8})$, whereas classically the bound is $\tilde{O}(n/\epsilon^{2}+d/\epsilon^{2})$.

Ref. [3] in ICML 2020 improved AdaBoost for learning a concept class $\mathcal{C}$ with VC-dimension $VC(\mathcal{C})$ from $\gamma$-weak learner to complexity $\tilde{O}(\sqrt{VC(\mathcal{C})}/\gamma^{11})$ in the quantum setting, whereas classically the bound is $\tilde{O}(VC(\mathcal{C})/\gamma^{4})$.

Ref. [4] in AAAI 2021 studied general $n\times d$ matrix games with quantum gate complexity $\tilde{O}(\sqrt{n}/\epsilon^{4}+\sqrt{d}/\epsilon^{7})$, whereas classically the bound is $\tilde{O}(n/\epsilon^{2}+d/\epsilon^{2})$.

Ref. [5, 6] in ICML 2023 and NeurIPS 2023 respectively gave quantum algorithms for $m\times n$ matrix zero-sum games with complexity $\tilde{O}(\sqrt{m+n}/\epsilon^{2.5})$, whereas classically the bound is $\tilde{O}((m+n)/\epsilon^{2})$.

We agree that reducing this gap stands as an interesting open question that is worth further exploring.

Reference

[1] Stephen P. Jordan. "Fast quantum algorithm for numerical gradient estimation." Physical Review Letters 95, no. 5 (2005): 050501.

[2] Tongyang Li, Shouvanik Chakrabarti, and Xiaodi Wu. "Sublinear quantum algorithms for training linear and kernel-based classifiers." In International Conference on Machine Learning, pp. 3815-3824. PMLR, 2019. arXiv:1904.02276

[3] Srinivasan Arunachalam and Reevu Maity. "Quantum boosting." In International Conference on Machine Learning, pp. 377-387. PMLR, 2020. arXiv:2002.05056

[4] Tongyang Li, Chunhao Wang, Shouvanik Chakrabarti, and Xiaodi Wu. "Sublinear classical and quantum algorithms for general matrix games." In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 10, pp. 8465-8473. 2021.

[5] Adam Bouland, Yosheb M. Getachew, Yujia Jin, Aaron Sidford, and Kevin Tian. "Quantum speedups for zero-sum games via improved dynamic Gibbs sampling." In International Conference on Machine Learning, pp. 2932-2952. PMLR, 2023. arXiv: 2301.03763

[6] Minbo Gao, Zhengfeng Ji, Tongyang Li, and Qisheng Wang. "Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games." To appear in the Conference on Neural Information Processing Systems, 2023. arXiv:2304.14197

The paper considers the problem of minimizing the maximum of $N$ convex Lipschitz function in the quantum oracle model of computation. The starting point for the work are the recent results by Carmon et al. using ball oracle acceleration to solve this problem to error $\epsilon > 0$ with oracle complexity $O(N/\epsilon^{2/3} + 1/\epsilon^{8/3})$ in the classical oracle model (the same paper provided an $\Omega(N/\epsilon^{2/3})$ oracle complexity lower bound).

The present paper makes a neat observation, which relates the regularized ball optimization oracle to the Gibbs sampling problem. Based on this observation, the paper leverages quantum Gibbs sampling to obtain the quantum speedup. The resulting quantum oracle complexity is $O(\sqrt{N}/\epsilon^{5/3} + 1/\epsilon^{8/3}),$ which is (quadratically) better in terms of the dependence on $N$ but worse in terms of the dependence on $1/\epsilon$ (this is not unusual for quantum speed ups in the oracle model of optimization). The paper also provides a quantum oracle lower bound $\Omega(\sqrt{N}/\epsilon^{2/3})$ and leaves open the possibility of reducing the dependence on $1/\epsilon$ in the upper bound.

Overall, the paper is presented well, the ideas are clear, and it is a solid result. Thus, I recommend acceptance.

Accept (poster)