Quantum Speedups for Minimax Optimization and Beyond

Thanks for your helpful comments and recognition on our work.

To weakness 1:

For the convex-concave minimax problems, the lower bound for zeroth-order algorithms are even unknown for classical algorithms.

For the non-convex minimization problems, some negative results claim that there is no quantum speed-up for higher-order methods when the dimension is large, i.e. the best dependency is $\epsilon^{-2/3}$ even with second-order oracles. The lower bound for this is also unknown even for classical algorithms.

We will discuss this in our revision and leave it as an interesting future work.

To weakness 2:

We will add a more detailed literature review regarding classical minimax optimization in the revision.

Thanks for your helpful comments and recognition in our work.

To question 1:

This method can indeed solve the minimax problems with degenerate saddle point. Both Theorem 4.2 and Theorem 4.4 require only convex-concave assumptions on the objective, which allows the existence of degenerate saddle point.

To question 2:

Thanks for pointing this out, loading this problem takes $\mathcal{O}(d)$, but only at a very few iterations. The total query complexity is $\mathcal{O}(d+d^{2/3}\epsilon^{-2/3})$ where the $\mathcal{O}(d)$ factor is only an addition term and can be omitted when $d$ is small $(d\leq \epsilon^{-2})$.

To question 3:

We do not use amplitude encoding for the real-valued inputs. Instead, we encode these values into the computational basis using a fixed-precision binary representation, analogous to how floating-point numbers are handled in classical computing.

This approach is standard in the analysis of quantum algorithms, just as it is for classical algorithms designed for classical electronic computers. Classical computers also operate on finite-precision representations of real numbers. Notice that, we assume that the value oracle of $f$ has an error $\epsilon_0$, which is intended to account for such sources of imprecision, including the truncation errors that arise from this finite-precision encoding.

For the sake of clarity and notational convenience, we present our analysis assuming the optimization occurs over the real numbers. This is also a common practice in the quantum optimization literature, with the implicit understanding that any practical implementation would rely on a suitable finite-precision encoding. This simplification does not pose a problem for the validity of our algorithm.

Thanks for your helpful comments.

To weakness 1:

For convex-concave minimax problems, the state-of-the-art classical algorithm requires $\mathcal{O}(d\epsilon^{-1})$ queries to find an $\epsilon$-saddle point, exhibiting a complexity that is linear in both $d$ and $\epsilon^{-1}$. In contrast, our algorithm (HAQZO+, Algorithm 4) can solve this problem with a query complexity that is sublinear in both $d$ and $\epsilon^{-1}$.

For non-convex minimization problems, our algorithm (QCNM, Algorithm 6) with query complexity of $\mathcal{O}(d+d^{1/2}\epsilon^{-3/2})$demonstrates at least a quadratic speedup on the dependency of dimension upon the prior zeroth-order cubic-regularized-Newton methods $\mathcal{O}(d^2+d^{3/2}\epsilon^{-3/2})$.

To weakness 2:

We consider the case where the query complexity dominates the computation complexity of the algorithm, which is a natural setting in both classical and quantum optimization. For example, considering the generalized linear model such that $f(x)=h(A^{\top}x)$ where $A\in R^{d\times n}$, the complexity of one query is at least $nd$, which can be much larger than the gate complexity if $n\gg d$. Our algorithm achieves meaningful quantum speedups under such a setting, typically when the dimension is not too large.

To weakness 3:

For the convex-concave minimax problems, the lower bound for zeroth-order algorithms are even unknown for classical algorithms.

For the non-convex minimization problems, some negative results claim that there are no-quantum speed-up for higher-order methods when the dimension is large [A], i.e. the best dependency is $\epsilon^{-2/3}$ even for algorithms with second-order oracles. The lower bound for $d$ is also unknown even for classicla algorithms.

We will discuss this in our revision and leave it as an interesting future work.

[A]. Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions. ICML, 2023.

To Question 1 (typos and writing)：

Thanks for pointing out this, we will modify them in the revision.

To Question 2:

We give explanations about the novelty in this paper below.

From the quantum mechanism perspective, we give the first analytitcal results on the query complexity for estimating Hessian-vector products and Hessian with an arbitrary desired accuracy $\epsilon$, which are important oracles in quantum optimization.

Besides the above, we emphasize that another important contribution of our paper is that our algorithm is the first one to allow both inexactness of Hessian and gradient oracles to solve the minimax problems, which is more general than the prior classical Hessian-aware algorithm frameworks [9, 27]. To achieve this, our algorithm requires novel design on the regularization term $\lambda_t$ and techniques to bound the errors from both quantum gradient and Hessian estimations.

From the perspective of theoretical results, our algorithm demonstrates quantum speedup on general (strongly)-convex-(strongly)-concave minimax problems. Furthermore, the idea of accelerating classical algorithms by quantum Hessian estimation is new to quantum optimization, which is of independent research interest and can be used to solve other optimization problems. For example, the presented QCNM (Algorithm 6) is even faster than existing quantum algorithms when $d\leq \epsilon^{-1/4}$ for non-convex problems.

To limitations:

Please refer to our response to weakness 3 and question 2 respectively.

Thanks for the clarification! I have no more questions. By the way, I think it will be clearer if the $O(d)$ additive term appears explicitly in the main text, maybe in the theorem or footnote.

Thanks for your helpful comments.

To weakness 1:

Thanks for pointing out this, we will update the query complexity of HAQZO+ (Algorithm 4), Restart-HAQZO+, and QCNM to $\mathcal{O}(d+d^{2/3}\epsilon^{-2/3})$, $\mathcal{O}(d+d^{2/3}(L_2/\mu)^{2/3})$, and $\mathcal{O}(d+d^{1/2}\epsilon^{-3/2})$ respectively. The $\mathcal{O}(d)$ factor is only an addition term and can be omitted when $d$ is small ($d\leq \epsilon^{-2}$ for convex-concave problem and $d\leq \epsilon^{-3}$ for non-convex problem).

To weakness 2:

We agree that our algorithm for estimating the Hessian-vector and full Hessian is an application of Jordan’s gradient estimation. However, we kindly disagree that this impacts the contribution of this work.

There are no analytical results for estimating the Hessian by quantum function value oracles before. Our work is the first to study the query complexity for estimating the Hessian with an arbitrary desired accuracy $\epsilon$. We believe these oracles perform important roles in quantum optimization.

In addition, our contribution is not limited to the construction of quantum Hessian evaluation oracles, but also lies on how to efficiently use such oracles to demonstrate over classical algorithms and the existing quantum algorithms (please refer to our answer to question 1).

To question 1:

For the minimization problem, the complexity of QCNM aligns with the complexity of First-order CNM in [11].

For the minimax problem, there are no corresponding classical algorithms with first-order input that achieve the same query complexity. Unlike FO-CRN [11] for non-convex optimization, our algorithms (HAQZO, HAQZO+) conduct an extra-gradient step, which incurs additional error from the inexact gradient. This require both novel algorithm design, i.e, the choice of the regularziation term $\lambda_t$, and careful analysis to control the error from the gradient and Hessian estimator. To the best-of-our-knowledge, such Hessian-aware algorithms with zeroth-order or first-order oracles have not been considered under classical settings before.

To question 2:

There are no dimension-independent quantum algorithms for minimax problems with a function value oracle. It is possible to design a dimention-free quantum algorithm for minimax problems by using an evaluation oracle on extra-gradient method or optimistic gradient descent ascent method. It is also a very interesting future work to design algorithms with complexity interpolate between dimension-free algorithm and HAQZO/HAQZO+.

To question 3:

Thanks for pointing out the paper. We did not discuss this paper in the current version because we focus on the results for both classical and quantum algorithms with zeroth-order oracles (in Table 3), while this recent paper uses the first-order oracle. We will discuss it in the revision.

Thanks for your clarification and your recoginition in our technical contribution. The facts and observation in your post are absolutely correct and we are very happy to present the classical gradient algorithm explicitly in the revision.

W’d like to add some additional comments on your claims.

• For the claim 1, Lemma 4.3 studies a general update framework (8) with inexact gradient and inexact Hessian which do not differentiate the quantum or classical queries. This allows us to derive a classical upper bound of $\mathcal{O}(d+d^{2/3}\epsilon^{-2/3})$ gradient queries quickly.
• For the claim 2, one major difference between the classical and quantum algorithm is that the measurement on the quantum estimation oracle leads to a high probablity bound in quantum algorithms instead of a deterministic bound in classical algorithms. We need to upper bound the fail probability at every quantum estimation of the gradient and Hessian oracles to fulfill the desired probablity bound. This motivates us to present a quantum estimation oracle for the Hessian, so that one can control the fail probability of accessing a Hessian directly. Take Algorithm 4 for example, we set the parameters in quantum estimation oracles for the Hessian, gradient at the Newton step, and gradient at the extra-gradient step as $\delta/3T$ in line 4, 7, 11 respectively, so that the fail probability of the Algorithm 4 can be bounded by $T\*3\*\delta/3T=\delta$.
• In addition, it is common to conduct such a Hessian-estimation oracle eplicitly in classical optimization methods. For example, [Lemma 3, A] and [Lemma 3.1, 11] present a first-order (gradient) and zeroth-order implementation of the Hessian explicitly and estimate the approximation error. Hence, we think it is natural and proper to also present such a quantum estimation of Hessian explicitly.

[A]. A cubic regularization of Newton’s method with finite difference Hessian approximations. Numerical Algorithms, 2022

Thanks for your helpful comments.

To weakness 1:

Our algorithm for estimating the Hessian-vector and full Hessian is an application of Jordan’s gradient estimation. However, we kindly disagree that this impacts the contribution of this work.

There are no analytical results for estimating the Hessian by quantum function value oracles before. Our work is the first to study the query complexity for estimating the Hessian with an arbitrary desired accuracy $\epsilon$. We believe these oracles perform important roles in quantum optimization.

In addition, our contribution is not limited to the construction of quantum Hessian evaluation oracles, but also lies on how to efficiently use such oracles to demonstrate over classical algorithms and the existing quantum algorithms (please refer to our response to limitation 1).

To weakness 2:

The state-of-the-art classical algorithm requires $\mathcal{O}(d\epsilon^{-1})$ queries to find an $\epsilon$-saddle point, exhibiting a complexity that is linear in both $d$ and $\epsilon^{-1}$. In contrast, our algorithm (HAQZO+, Algorithm 4) can solve this problem with a query complexity that is sublinear in both $d$ and $\epsilon^{-1}$.

A crucial contribution of our work is that the quantum speedup is achieved with respect to both $d$ and $\epsilon^{-1}$. This marks a significant advance, as previous quantum works in this area typically only provide speedups in the dimension $d$. We therefore believe our work offers a key conceptual contribution beyond the concrete improvement in query complexity.

To weakness 3 and question 1

We consider the case where the query complexity dominates the computation complexity of the algorithm, which is a natural setting in both classical and quantum optimization. For example, considering the generalized linear model such that $f(x)=h(A^{\top}x)$ where $A\in R^{d\times n}$, the complexity of one query is at least $nd$, which can be much larger than the gate complexity if $n\gg d$. Our algorithm achieves meaningful quantum speedups under such a setting, typically when the dimension is not too large.

The inexact cubic step is indeed computed classically. This is permissible as any classical computation can, in principle, be performed on a quantum computer. The quantum speedup we present is not negated by this classical step. The primary computational bottleneck in many applications is the function value query, especially when the function evaluation is handled by a complex subroutine. In such scenarios, query complexity serves as a crucial proxy for overall computational efficiency.

Furthermore, we respectfully disagree with the assertion that the presence of classical computation steps precludes a "genuine" quantum speedup. For example, fundamental arithmetic operations, such as addition and multiplication, do not have quantum speedups. These operations are essentially performed classically within quantum algorithms. However, invoking classical arithmetic operations in quantum algorithms is not recognized as weakening the quantum speedup in general. Our position is that quantum advantage can be assessed based on the query complexity for the specific problem at hand. The optimization of the computational aspects, separate from the queries, falls within the domain of quantum compilation and quantum circuit design.

To question 2:

We first respectfully point out that the state-of-the-art classical algorithm takes $\mathcal{O}(d\epsilon^{-1})$ query complexity to find the $\epsilon$-saddle point, which is linear in both $d$ and $\epsilon^{-1}$.

Our results demonstrate a query complexity of $\mathcal{O}(d+d^{2/3}\epsilon^{-2/3})$, which improve the dependency on both $d$ and $\epsilon^{-1}$ from linear to sublinear. This means that our algorithm always has a quantum advantage over classical algorithms.

It is a very interesting future work to show larger quantum speedups, and we believe that the quantum Hessian oracle given in this work is important to achieve this.

To question 3:

The Gap() function is defined in Definition 1 (line 104-lin 107), we will emphasize this in the revision.

To minor typos/formatting issues:

Thanks for your careful review, we will modify them in the revision.

The $f^{\*}$ defined in line 244 should be modified to $f\^*\triangleq \min\_{z}f(z)$.

To limitation 1:

We kindly argue that our technical contribution is limited and would like to emphasize the parts that the reviewer may have overlooked.

Firstly, our algorithms for solving minimax problems are novel. Directly integrating the quantum estimation into the classical algorithms leads to additional errors from the inexact gradient/Hessian oracles and the extra-gradient step. We overcome this issue by adjusting the regularization term $\lambda_t$ and carefully setting the quantum estimation error. To the best-of-our-knowledge, even under classical settings, there are no results that allow the inexactness in both gradient and Hessian to solve the minimax problems.

Secondly, the quantum Hessian estimation is a natural generalization of Jordan’s gradient estimation method and offers important oracles in quantum optimization. It can not only provide quantum speedup over classical algorithms, but also further accelerates the quantum algorithms. Fot example, our proposed QCNM method demonstrated a further acceleration upon the state-of-the-art quantum algorithms when $d\leq \epsilon^{-1/4}$.

To limitation 2:

Please refer to our response to weakness 2 and question 2.

I thank the authors for their kind explanation, which has addressed some of my concerns. Based on their rebuttal and discussions with other reviewers, I have updated my score. My additional comments are as follows:

1. If I understand correctly, from the discussion between the authors and Reviewer mnz2, one can obtain a quantum zeroth-order algorithm with query complexity $d + d^{2/3}\epsilon^{-2/3}$, which is comparable with the algorithm presented in this work (using quantum Hessian estimation). This is certainly an interesting and arguably stronger result. However, it also suggests that the role of quantum Hessian estimation is diminished and appears more like a corollary of Jordan's algorithm.

2. That said, I still stand by my original assessment that the quantum speedup in this paper is rather marginal. The proposed quantum algorithm requires fault-tolerant quantum hardware, and in practice, the sub-quadratic speedup presented here is unlikely to be realized due to the overhead of quantum error correction.

Thanks for your reply and updating your score. We would like to add the following clarification on your comments.

1. In our discussion with Reveiwer mnz2, we focus on if the quantum Hessian oracle should be presented explicitly instead of obtaining a new algorithm. In fact, if we write the quantum Hessian estimator in Algorithm 4 by calling Algorithm 2 and 3 explicitly, then we can obtain a algorithm with $\mathcal{O}(d+d^{2/3}\epsilon^{-2/3})$ with only the estimation of gradient. This is not a new algorithm, but only a different presentation of the algorirthm in this work. We kindly argue that the quantum Hessian estimation should be constructed explicitly in our response to Reviewer mnz2 for the following two reasons.

• The construction of the quantum Hessian estimation allows us to bound the fail probability easily so that one can obtain a high probablity bound directly.

• In classical optimization work, it is very popular to construct a Hessian estimation explicitly by gradient or function value oracles and use such an estimation to simplify their algorithms. Hence, we also think it is also proper to construct a quantum Hessian estimation explicitly.

2. In our minimax optimization, we obtain a sub-quadratic speedup, but on both the parameter $d$ and $\epsilon^{-1}$, which we believe is not marginal. For the non-convex minimization problem, our algorithm exhibits a complexity of $\mathcal{O}(d+d^{1/2}\epsilon^{-3/2})$, which is at least a quadratic speedup on the dependency of dimension upon the prior zeroth-order cubic-regularized-Newton methods $\mathcal{O}(d^2+d^{3/2}\epsilon^{-3/2})$. As compared to the prior quantum algorthm, such a speedup comes from ultilizing the quantum estimation of Hessian, which again motivates us to construct such an oracle explicitly.