Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss
Authors: Hao Wang
Chenyi Zhang
Tongyang Li
Venue: ICLR 2024 poster (2024)
Keywords: Quantum Algorithms
Quantum Query Complexity
Convex Optimization
Minimizing Loss
Primary area: optimization
TL;DR: We conduct a systematic study of quantum algorithms and lower bounds for minimizing the maximum of $N$ convex, Lipschitz functions.

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\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 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 $\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.

Published as a conference paper at ICLR 2024
NEAR-OPTIMAL QUANTUM ALGORITHM FOR MINIMIZ- ING THE MAXIMAL LOss
Hao Wang"
Chenyi Zhang
School EECS
Computer Science Department
Peking University
Stanford University Stanford, CA 94305, USA
Beijing, China
www.://wwgaassuuuu....oo edu. cn
chenyiz@starford.edd
Tongyang Li
Center on Frontiers Computing Studies
School of Computer Science
Peking University Beijing, China tongyangli@pku edu.cn
ABSTRACT
The problem minimizing the maximum of N convex, Lipschitz functions plays significant roles in optimization and machine learning. It has series of results, with the most recent one requiring O + c-/33 queries to a first-order oracle to compute an c-suboptimal point. On the other hand, quantum algorithms for optimization are rapidly advancing with speedups shown many important this paper, we conduct a systematic study for quantum algorithms and lower bounds for minimizing the maximum of N convex, Lips- chitz functions. On one hand, we develop quantum algorithms with an improved complexity bound of Ö(VNe -5/3 + 8/3) On the other hand, we prove that quantum algorithms must take 9²( Ne 2233) queries to first order quantum oracle, showing that dependence on N is optimal up to poly-logarithmie factors.
optimization problems.
5/3
INTRODUCTION
Consider the problem of minimizing the maximum of N convex functions .,,..,, I'v where each f:: Rd IR is convex and L-L-ipshitz. Our goal is to find point v, satisfying
Finax Fmax
inf F Finax (x) Sc xERd
for some target accuracy e, where
F Fmax
(z)
max f((.). sE[N]
(2)
This problem has wide applications in machine learning and optimization. Specifically, characterizes the problem of minimizing the maximum of loss functions in supervised learning. For instance, in support vector machines (SVMs), f.'s 's are loss functions representing the negative margin the th data point (Vapnik 1999; Clarkson et al. 2012: Hazan al. 2011 Li et al., 2019). Furthermore, minimizing the maximum loss classification provides advantageous effects on training speed and generalization (Shalev-Shward & Wexler 2016). In optimization, it falls into the category of robust optimization (Beyer & Sendhofi] 2007 Ben Tal et al. 2009) that studies optimization of the worst-case objective. As concrete example, Fmax (I) maxpEA> EieNN) f((x) is an instance
"Equal contribution.
"Thoughout this paper, Ô omits loly-logariihmic factors, i.c., Ō(f) O(f poly(log f)).

---

Published as a conference paper at ICLR 2024
of distributionally robust optimization (Delage & Ye 2010 Ben- Tal et al. 2013) with the uncertain set being the whole set A N of probability distributions with cardinality N.
Given these motivations, Problem [ has been extensively studied in previous literature. In particular, it is known that it can be solved by subgradient method using O(E 22 iterations, c.g., sec Nesterov (2018). In each iteration, however, N queries leads to an overall query complexity of order O(Nc-?). Furthermore, Carmon
needed to compute the exact subgradient, which
Carmoon et al.
( (2021) proposed
an algorithm based on the ball optimization acceleration scheme (Carmon et al.) 2020b that uses O(Ne-2/3 + -8/3) subgradient queries. Carmon al. (2021) ) also proved S2(Ne 2/3) lower bound on the number of subgradient queries via the "chain construction" technique in optimization Guzmán & Nemirovski [2015]
lower bounds (Carmon et al. [2020a] Diakonikolas & Guzmán 2019/Guzmáá
Nemirovski & Yudin 1983] Woodworth & Srebro (016). indicating that their algorithm is optimal to a poly-logarihmmic factor the parameter regime where N c²
On the other hand, quantum computing has been rapidly advancing technology in recent years. The main motivation of studying quantum computing is its potential solving problems significantly faster than the classical counterparts. The most famous example is Shor's is algorithm [Shor] (1999) for factoring integers in polynomial time with high success probability on quantum computers. In optimization theory, various quantum algorithms for optimization problems have been developed,
providing quantum speedups for semidefinite programs (Brandão & Svore 2017 Brandão et al.
2019 van Apeldoom & Gilyén 2019 van Apeldoorn al., 2020) Kerenidis & Prakash 2020
Augustino et al. (021). convex optimization (Chakrabarti et al. [0200] van Apeldoorn et al.
2020).
nonconvex optimization (Liu et al. 2022. Gong et al. 2022|Chhle et [ et al.
2021
etc. Conversely, quantum lower bounds on convex optimization (Garg et al. [021] Garg et al.
2021
and nonconvex optimization (Zhang & Li. 2023) are also established. However, the problem of minimizing the maximum of functions is widely open in quantum computing at the moment.
Contributions. In this paper, we conduct systematic study of quantum algorithms and lower bounds for minimizing the maximum of N convex and Lipschitz functions fI,...,JN, In particular, we assume the access to the following quantum zeroth- oracle:
O, (t) (x) lw) |t) |x) by + f((z))
where 1.) denotes input or output register that allow queries in quantum superpositions, the essence of speedups from quantum algorithms. Specifically, a quantum algorithm can choose Fi....,2y E Rd y1....; E IR, and e E CN such that ΣN |e:12 1, and applies the quantum oracle as follows:
O, Σ
c 12) ( 1vn)
Σ cs (2) (ay) ly: + {((x))
2=1
If we measure this quantum state, with probability |c,/2 the third register gives yi + fz()). This oracle is a standard assumption by quantum algorithms for optimization, see c.g. Chakrabarti et al. (2020); van Apeldoom al. (2020); Liu et al. (2022);(Gong et al. (2022) Zhang al. (2021). More introductions to notations and definitions of quantum computing are given in Section 2]
Theorem 1 (Main theorem). There is a quantum algorithm (Algorithm 11 that oulputs an x. satisfying
Eq. 4 with probability at least 2/3 using Ö(VNe 65/3 + -8/3) queries to the Or in Eq. (3) On the other hand, such quantum algorithms must take Si(NNe 2/3) queries O, Theorem 4).
Compared to the state-of-the-art classical algorithm for minimizing the maximum of convex and Lipschitz functions, we achieve quadratic quantum speedup in the number of functions N. On the other hand, our quantum lower bound Q2( /Ne 2/3) establishes the near-optimality of our quantum algorithm in N. See Table I for more detailed comparisons.
Techniques. Our quantum algorithm follows the scheme of Carmon et al. (2021) while we achieve quantum speedup by leveraging quantum samples. As a starting point, classical algorithms (Carmon et al. 2021; Nesterov] 2005) proceed by considering the so-called "softmax" approximation of the maximum, defined as
Mxx)
)
F Famax, (x) e' log
Σ exp [E[N]
(5)
2 log N'
2

---

Published as a conference paper at ICLR 2024
Table 1: Summary of results on minimizing the maximum of N convex, Lipschitz functions accuracy c.
Reference
Method
Oracle
Upper hound
Lower bound
Nesterov 2018
Subgradient method
Classical First Order
O(Ne ")
Carmon et al. 2021
Ball optimization accelcration
Classical First-Order
OnNe + 619)
this work
Ball optimization accelcration
Quantum Zeroth-Orake
Öl 5/3 w/4 8/3)
M(VNe 2/3)
with quantum sampling
Note that the choice of e' here promises that solution 2, of
F Fsmax, (I++)
inf acRd
(ssmax.(()) S 2
(6)
will automatically satisfy
4 (see Lemma 4). Our algorithm has two stages:
Implement regularized ball optimization oracle (BROO) of Fsmax, that when query at x returns an (approximate) minimizer of Famax, in a ball of radius r around x; and then
Find an approximate minimum of Famax,e using ball optimization oracle via a ball optimiza- tion algorithm (Carmon al. 2020b
Here, the ball optimization algorithm in Carmon et al. (2020b) is variant of the Monteiro- -Saiitr acceleration (Bubeck et al., 2019; Bullins 2020
Gasnikov et al. 2019 Monteiro Svaiter 2013) and
can minimize / to accuracy using Ô (r 273
queries to the BROO, Carmon et al. (202) showed
that BROO for Fsmax, can be implemented by considering instead a "softened" function
cli(a/fe
(.(x)= Σ p,E' AE[N]
Jele)- G()
P4 EJEIN el(la)/e
where e' = e/(2 22/221ogg log N). which shares the same minimizer as F Fsmax.r and has a finite sum structure enables stochastic gradient methods. In their implementation, the main bottleneck for N arises from the sampling step of the distribution ps. To obtain T samples, the algorithm requires precomputing all Pi..... PN. which takes ((NN classical queries and cannot be further accelerated in the classical setting. However, this task shares a similar formula with the Gibbs sampling problem, which exhibits quantum speedups (Bouland et al. 2023 Gao et al. 2023). Building on this intuition, we demonstrate that BROO can be executed using just O(VN) queries to the quantum oracle O, defined in (3). Our quantum algorithm begins by preparing T copies of the quantum state >: /P: (i). The first step involves identifying the K largest P; values and corresponding indices, which can be accomplished with only /NT queries to the quantum oracle O,, in contrast to the classical case's 's query complexity of ((N). This quadratic speedup in N contributes our overall quantum speedup.
From a high-level perspective, quantum speedups optimization algorithms have been mainly investigated in gradient descent methods (Liu et al. [2022] Gong al. 2022 Zhang al.) 202 cutting plane methods (Chakrabarti et al.] 20200 van Apeldoorn et al. 2020). interior point meth-
ods (Kerenidis& & Prakash| 2020; Augustino et al. 2021). etc., but quantum algorithms based trust
region methods are widely open. Our result can be seen as a first attempt for quantum algorithms using trust region methods with speedup.
We establish our quantum lower bound for minimizing the maximal loss by applying a quantum progress control method the classical hard instance described in Carmon et al. (2021). The quantum progress control method, initially introduced in Garg et al. (2021). has been widely used in proving quantum lower bounds for optimization problems, including non-smooth convex op- timization (Garg et al.) 2021), smooth convex optimization (Garg et al., (02I). and (stochastic) non-convex optimization (Zhang & Li 2023). This method is analogous to the classical progress control technique employed in proving classical lower bounds for optimization problems (Carmon) ctt al., 2020al Arjevani et al. 2020 2022, Bubeck et al., 2019), and is based on demonstrating that any algorithm attempting to solve the optimization problem must acquire a sufficient amount of information through an adaptive "chain structure". This chain structure is well-established concept in classical optimization lower bound proofs, seen in prior works such (Carmon et al.) 2020a]] Nemirovski & Yudin 1983 Woodworth & Srebro 2016 Guzmán & Nemirovski 2015 Diakonikka
& Guzmán 2019).
3

---

Published as a conference paper at ICLR 2024
The quantum progress control method proceeds by modeling any quantum algorithm as sequence of unitaries represented as
applied to the initial state 00), where O is the oracle encoding the information of f and Vi's are unitaries that are independent from f. Then, one can show that those queries can only learn the information and make progress along the chain structure in an adaptive manner. This ultimately leads to lower bound that scales in proportion to the length of the chain multiplied by the cost to make a unit progress along the chain.
In the majority of cases, the query cost of making a unit progress along the chain is just 1, see e.g.. Garg e.g..Garg al. (2021); b Garg et al. (202T). Nevertheless, there exists methods to incorporate more "hardness" into the chain by constructing hard instances where making progress along the chain requires solving subproblem. For example, the quantum stochastic lower bound for nonconvex optimization algorithm (Zhang & Li| (023) proceeds by applying a hard instance with a "chain structure" such that, at each point where any algorithm attempts to progress by one step of unit length along the chain, it is required to solve multivariate mean estimation problem, whose quantum lower bound given in Cornelissen al. 2022).
Our lower bound builds upon the same framework. In particular, we demonstrate that, at each point where a quantum algorithm attempts to progress by one step along the chain of the hard instance defined in described in Carmon et al. (2021), it has to solve an unstructured search problem. This intuition, however, cannot work straightforwardly. This arises from the fact that even the case of a completely random guess, any algorithm possesses success probability that is at least polynomially small for solving the unstructured search problem and progress by multiple steps along the chain. This success probability, although small, poses challenge to the progress control argument where the probability of making progress by multiple steps at once should be super-polynomially small.
We address this issue by introducing multi-round version of unstructured search problem. In this modified problem, each round's solution acts as a "key" that unlocks the next round, forcing it to solve these unstructured search problems adaptively. We demonstrate that for any quantum algorithm making a maximum of (NN) queries to this mulli-round unstructured search problem, its overall success probability in solving the entire multi-round problem. i.e., solve the unstructured search problem of each round, is only super-polynomially small. After establishing the lower bound for the multi-round unstructured search problem, we show that making progress along the chain for a given length is as hard as solving the multi-round unstructured search problem of the same number of rounds. Formally, we show that any quantum algorithm has to use ÿ (VVN queries to make Opoly log(1/e)) progress along chain of length Ω (e 2/3), giving our Ω /Nee -2/3) lower bound.
Open questions. Our paper leaves several natural open questions for future investigation:
Can we narrow even close the gap of order between the leading complexity term in our quantum algorithm and our quantum lower bound? Useful techniques might be found in quantum algorithms for Gibbs sampling (Bouland et al.) 2023] Gao al. 2023). but remains uncertain if we can reconcile the differences in the two settings.
It is shown in Carmon et al. 12221) that the smoothness of fa enable faster classical algorithms for minimizing the maximum loss, even in the case where the smoothness parameter is of order 1/c and all the f. are almost non-smooth. The intuition is that can apply the accelerated variance reduction method (Allen-Zhuj 2017) to implement the ball optimization oracle of Fssmax. if it is smooth, which contains mean estimation subroutine that cannot be directly improved by quantum algorithms (Cornelissen et al., 2022) Zhang & Li 2023). Hence, a natural question to ask if there exist quantum algorithms that can utilize the smoothness structure and provide better convergence rates.
PRELIMINARIES
Basic notations in quantum computing. Quantum mechanics can be formulated in the language of linear algebra. Specifically, we define the computational basis of the space Cd by (Œ1,...; E
4

---

Published as a conference paper at ICLR 2024
where é; (O...., 1,...,0) with the ith coordinate being 1 and other coordinates being 0. These basis vectors can be written by the Dirac notation, where we write é; as li), and write e as (i)-
A d-dimensional quantum state (b) = (Ui,.... .2) T is unit vector in C*, i.e. Ei=o lep 1. For each i, 02 is named the amplitude (1). If at least two amplitudes are nonzero, we say (o) is in superposition of the computational basis.
Tensor product of quantum states is their Kronecker product: Iu) E Ct and Iu) E Cd, then Ju) s (0) = (u1 th, M1 M1. thd, Hdz)) E C @ Ct,, (u) & (e) can be abbreviated as lu)le).
The basic element in classical computing is one bit. Following this pattern, the basic element in quantum computing is one qubit, which is a quantum state in C Formally, qubit state has the form a ()) + b|1; where a, b E C, |a|² + |6|2 1. Furthermore, an n-qubit state has the form (1)) @ (un), where each (e4) is qubit state for all i [n]. As result, n--ubit states form Hilbert space of dimension 2".
Calculations in quantum computing unitary transformations and can be stated in the circuit model where a q-qubit gate is a unitary matrix in C²*. Two-qubit quantum gates are universal, i.e. every n--ubit gate can be written as the product of a series of two-qubit gates. Therefore, the gate complexity quantum algorithm can be regarded as number of two-qubit gates.
Basic quantum algorithms. In our paper, we use the following quantum algorithms in previous works as basic building blocks of our quantum algorithm.
Proposition 1 (Top-K Maximum Finding Dürr et al. 2006 Theorem 4.2). Let K,N E N. S K I N, QuantumMaxin www.asiiinnniiin((Cccccmc N,
(0,1) and w E 1e There exists a quantum algorithm N,,, w, that outputs the positions of K largest entries in w with success probability at least 1 - 5. The algorithm performs OVKN log(1/8)) queries the following quantum oracle Ow that encodes w.
8 Proposition 2 (State Preparation Zalka 1998 Grover & Rudolph 2002 Kaye & Mosca 2001). Given integers N, T, a non-zero vector w E E with w 1 = 1 and a classical procedure that computes
Ow (t) (u) (2) wt)
Ei w.. Vi S j. there exists a quantum procedure quaatumSttaeePreparatiioo outputs the classical description of a quantum circuit 'D that satisfies 'D [0) - |w) = Σ. v (i).
T, w) that
Proposition (Amplitude Amplification Brassard al. 2002 Theorem 3). Let be a quantum circuit that prepares the state C (0) = vp (0) [0) + v1 P Φ1) 1) for some E [0, 1] and two unit states (0) 1 There exists a quantum algorithm tamplittueamlliiccaii.o..
that outputs the
state (6) by using O(1 vD) calls of C and Ci in expectation.
Proposition (Quantum Gradient Estimation Jordan 2005) Lemma 2.2). Given access to the quantum zeroth-order oracle O, defined in 3 there exists quantum algorithm QuantumGradientEaan wwweeenttttiiiiiii.i...... that outputs the gradient V f((z) using only one query to
Oj.
3 QUANTUM ALGORITHM FOR MINIMIZING THE MAXIMAL LOSS
In this section, we present our quantum algorithm for minimizing the maximal loss. Our approach builds upon the framework of (Carmon al. 2021 Algorithm 1), which proceeds by preparing a ball optimization oracle that can minimize the objective function in a very small region, and then optimize the objective function by using this oracle recursively.
particular, (Carmon al., 202T Algorithm 1) is variant of Carmon et al. (2020b) and utilizes the Monteiro-S Svaiter acceleration (Monteiro & Svaiter 2013). Notably, there has been series of work (Carmon et al.) 20206) 202T) on designing optimization algorithms following this framework, given that it natural in some problems where we can access the ball optimization oracle efficiently. Compared to (Carmon et al. [021 Algorithm
1), algorithm differs by critical observation that the bottleneck in the classic algorithm, mainly the sampling, can be sped up using a quantum subroutine based on Gibbs sampling.
As in Carmon et al. (2021), we consider the ball regularized optimization oracle (BROO), which is generalization from the stricter ball optimization oracle Carmon et al. (2020b). Formally, a BROO is defined as follows.
5

---

Published as a conference paper at ICLR 2024
Definition 1 (Carmon et al. 2021
Definition 1). We say that mapping Ox,5 is a Ball Regularized Optimization Oracle of radius r (r- (--BROO) f. for every query point ã, regularization parameter X and desired accuracy 6, it returns I Ox,6(ā) satisfying
x 0² 2
f(Ø)
1 - =| 2
min (EB.(
f(x)+ + 2 -
f(x)
(9)
The following result illustrates the convergence rate achieved by the classical ball optimization algorithm (Carmon et al. 2021, Algorithm 1) using BROO queries.
Proposition (BROO Acceleration Rephrased from Carmon et al. 2021 Theorem 1), Let f Fd + IR be convex and Lipsschit, and let z E R.. For any domain bound R > accuracy level
<> and initial point zo RRd, there exists a (classical) algorithm that returns a point x Te. satisfying f(x) min Bu(oo) f(z) S c/2 using at most
((
o
R
log
(10)
queries to an -BROO, in which r. e/2Ly log N. The algorithm also guarantees that the BROO
query parameters (X,0) satisfy Q2
S A O and 52 (xit
7.R
3.1 QUANTUM BROO IMPLEMENTATION OF F Fsmax,
In this subsection, we present a quantum algorithm (Algorithm Tp that implements a BROO given
access the oracle O, defined The query complexity of Algortt iis given Theorem 2
Algorithm 1: Quantum-Epoch-SSOne
on the exponentiated softmax
Input:
Functions fi...., fN. ball center ă, ball radius T., regularization strength X, smoothing parameter c', failure probability a
Parameters: Step size 7), = 1/(3)), domain size D₁ = G =[G//ogg(oog())///// and total iteration budget T
= 450
Output: Approximate minimizer of Te,, (and hence FA Famax,e) in (T))
Prepare 7' identical states (wb e / VEii(ty ehll)/e (i) using Algorithm 2
Initialize =| E B,, (Ø) arbitrarily, set h =1
while >>e(M] T, < do
for 1 = ,, Ta do
Sample E [N] by measuring the next unmeasured (b))
Call un inn to compute
V (z) V f((x) + A(x - F)
Oe = e f ( (x)
Update - t (3)n (att) (x mxr(t)
Let L 1+1
+ ElE(T)
Th
Update parameters Th+1 +- 2T,, Mh41 + mh/2, De+1 D4/V2. + k+1
10
11
return
Theorem 2. Let f1:J2,...,.5 l be Li-iisschitz funniichhittffnciions. Let E (0,1), c, > 0 and Tr
c/2T.g log N. For any T. Rdd and X & O(T,/ve)), with probability at least 1 20, Algorithm / outputs a valid r.- -BRROO response for Fsmax,e to query a with regularization and accuracy and has cost
which = 21ggoooolgggg(( logN))))())
(11)
Note that when implementing BROO essentially minimizing Famax, (xr) but instead
F sumaaxc (x) = FFsmax.e2 (z) + A/2 || 2 = e'log Σ
exp (ex((((==)1))
(12)
ME|M

---

Published as a conference paper at ICLR 2024
in which (x) 2/2 || =||² is regularized version of fa(z). We define its "softened"
function I- Te, (Eq. accordingly.
Classically, a BROO of Famax,e can be implemented by (Carmon et al. 2021 Algorithm 2) using Spooch-GGDPProy proposed in Hazan & Kale (014)) with the stochastic gradient oracle implemented by sampling first and evaluate the gradient of one of the ' This process is similar to stochastic gradient descent but introduces epochs, where intra-epoch mirror descent takes place. Additionally, projection is placed the end of each iteration such that the variance of the stochastic gradient can be limited and probability bounds can be obtained rather than expectation bounds.
In comparison, quantum algorithm (Algorithm is based the same framework, with critical change. Rather than sampling classically from the same distribution many times within each epoch, we derive quantum subroutine (Algorithm 2) that sped up this bottleneck exploiting quantum advantage on Gibbs sampling. Additionally, comparing to the classic algorithm, which requires first-order oracle to acquire gradient information, the proposed algorithm uses QuantumGradien iisttimioinn (Proposition 4) to efficiently estimate the gradient through quantum zeroth-order oracle.
Algorithm 2: Quantum sampling of the softmax distribution.
Input: Number of copies K, failure probability
Denote (f) ................................ JN (f))²_ Call QuantumMax wntttttumuamaFaaam iataaiimmmFFinn lmmmFinninn(( N, w, compute the set _ [ of the positions of largest entries in fz) with failure probability 8.
Compute h = minje fi(T) and
3 = (N-K) exxp(//))) +
Σ exp(fi(2)/e) iE
Denote w' =ww w'y) where
(exp(Fi()/(e)) i H
w =
E
ViE[N],
exp(h/ee)
$ H,
call QuantumSttaeerrppaaaiiittt T, w') to build a unitary D such that
exp( exp(f(())ee)
exp(h/e")
2 10)
(1)
2
Z
iEH
NEÉ H
Construct the circuit C, which first applies D to the output register, as represented in Figure K times and return the K output states.
Call httpll/ttddeppiiiiaataeoeo
In Line 4] the circuit C' is constructed from the unitary D in Line Amplitude amplification is then applied to prepare the state we need by More explanation of Algorithm 2 given in Appendix A The lemma below shows quantum speedup for producing multiple samples from the same distribution. Lemma 1. With probability least 6, Algorithm 2 on input K, produces samples from the probability distribution
exp (xp(f((F)ee)
1=
(13)
J ex)(e)
using O(VNK log(1/5)) queries to the quantum evaluation oracle U, defined in 3
We present the proof of this lemma in Appendix A, Next, we cite the result regarding the convergence rate of stochastic gradient method with projection for p-strongly convex functions.
Lemma 2 (Hazan & Kale 2014 Theorem 11). Let f: X - R be a p-strongly-conve objective function on a convex compact set X with minimizer T.. With an unbiased stochastic estimator with norm bounded by G, Spoch-SGD-Prr algorithm uses T stochastic gradient queries and finds an approximate minimizer ā satisfying with probability 1 -
G2 Loooologg(T)//
f(ū) f(x.) 50
(14)
μT
7

---

Published as a conference paper at ICLR 2024
Proof of Theorem 2
According to 7. the gradient of (x))(z) can be expressed as follows:
VI. (x)) Σ
(z)x).
(15)
Thus, we have R[gr] VT (.)z) Moreover, by Lemma the quantity e (x) [1r()) bounded by a constant G = ( Thus, Sr is a valid stochastic gradient.
Next, by applying Lemma 2 with 7' - (ogg minimizing point z. of r,A with suboptimality
Algorithm
outputs
[ XT
[x,( min I #ER"
(2) 50 log(log o/o)
(16)
6E
we can bound the suboptimality of z, on that Algorithm is valid BROO. The probability of Alggooii T failing is at most 20 considering either the Epoch-SGID fails (Lemma 2) or the quantum sampling fails (Lemma Tp.
With Lemma 5
F smmax.c by 3e 662 - 18/2, indicating
3.2 QUANTUM QUERY COMPLEXITY OF MINIMIZING THE MAXIMAL LOSS
With our BROO oracle implementation at hand, we present our main result in this section, which describes the quantum query complexity of minimizing the maximum loss.
Theorem Let f1, .2......................... fN be Lipsschht,, let x, be a minimizer of Fmax(x) [ fi fa( and assume [i x. R for given initial point zo and some R >> O. For any >> O, using the algorithm in Proposition 5 the BROO implementation for Famax. in Algorithm finds point with
suboptimality with probability at least and has computational cost
OKK0/3 log K K( log K + R/c)//) N)
(17)
in which K = Rlgg((//)
Proof. We use Proposition 5 allng with Theorem 2 on the minimization problem to prove both the correctness and the overall query complexity of the algorithm. In particular, using the guarantees in Proposition 5) we can see that the results of Theorem 2 applies directly since À S / Letting 7 be the bound of the total number of oracle queries in |Proposition 5] We could have
1/67' such that the probability Algoorti not failing throughout all the queries is at least 2/3. Thus, according PProposition the algorithm can output minimizing point x. for F Famaxe with suboptimality at most e/2. Thus, using Lemma 4. we conclude that x, is a solution to ① proving the correctness of the algorithm.
As for the query complexity, notice that from Proposition 5 the total number of calls to the BROO is
T=o 7-0((4) (4..Rlogg
2/3 log"
Ly L1 N
(18)
Using our implementation of the BROO oracle Un per BROO call is
Algorithm the total number of calls to the quantum
o (WN (LgRlogN)
N
L
LyRlog +
L log (1
log
(19)
in which we substitute 5 = Q(E/AR) and a= = -1/6T.
4 QUANTUM LOWER BOUND FOR MINIMIZING THE MAXIMUM LOSS
In this section, we establish quantum query lower bound to demonstrate the optimality of our algorithm in Section 3) with respect to N. Classically, the query lower bound for minimizing maximal loss established by progress control argument given Carmon et 2021). For any x E Rd they define a quantity progress as
prog, (z) max {i 2 1 |2d|| 2 23.
(20)
8

---

Published as a conference paper at ICLR 2024
Intuitively, the progress is the highest coordinate index that algorithm discovers when it reaches Following that, Carmon et al. (2021) extended the concept of robust zero chain introduced in Carmon et al. (2020a) to the setting of minimization of maximum loss.
Definition (Carmon et al. 2021 Definition 2). A sequence fI....,IN of functions fú: (R - R
is called an a-robust N -element zero-chain for all x E BB((),, all y in a neighborhood of x, and all E [N], we have
[(US)))) i <<p+1
proga (I) Sp f.( =
(((sst+1) (N(())))
i=p+1
(21)
i>p+1,
where for any y E TRu, V[Sn) denotes the vector whose first coordinates are identical to those of and the remained coordinates zero.
Carmon et al. (202T) demonstrates that, for a sequence of functions fI...., JN forming an a-robust N-element zero-chain with randomly permuted indices, a classical algorithm requires a lower bound of ((N) queries to increase the progress by 1 in expectation. Similarly, we show that it takes (( (NN) queries for quantum algorithm to make progress on an a-robust .Veeement zero-chain. Notably, the progress achieved after ? VV) quantum queries exhibits a sub-exponential tail, and the probability of achieving super-logarithmn progress is super-polynomee
small.
In this section, we first present in Section 4.1 a quantum analog of the progress control argument in Carmon et al. 2021 Finally, we introduce the main lower bound statement in Section 4.2
4.1 PROGRESS CONTROL ARGUMENT FOR QUANTUM ALGRRTHTM
We establish a quantum analog of the progress control argument given in Carmon et al. (202T). Following the notion of Garg et al. (2021) 1): Garg al. (202T) Zhang & Li (2023), represent any
quantum algorithm making k queries to the oracle Oj in the form of sequences of unitaries
Aquan [k] V2O,Va-110 ... V,V,O,V
(22)
applied to the initial state 10), followed by measurement. Similar to Carmon et al. 2022 Proposition 1), we prove the following result that no quantum algorithm can guess the final column of U make progress efficiently (proof deferred to Aoppppdi B.2).
Proposition Let 6, a E (0, 1) and let N,T e N with T N/2. Let {feheeN be an a-robust N- element zero-chain with domain IB (0). For d 2 T max(321 log(32v ), 321 log (4T (8). draw U uniformly from the set of d T orthogonal matrices, and draw II uniformly from the set of permutations of [N]. Let f((z) = fU z). For any t-query quantum algorithm Aquaalt) equipped with an oracle on 1 we have
denote Ie as its output. Then with probability at least
TVN
proga (U xx) <,
CK
in which C' is a constant and K = 4log T + log N +
4.2 THE LOWER BOUND STATEMENT
Finally, we present the main theorem of the lower bound argument.
Theorem 4. For any L,g, Tag. R > O, < min([Ty R, R²), N E N and E (0, 1), there exists a constant C such that, for any quantum algorithm A making less than C 22/3 log N/e queries to the oracle Oy defined in 3 and outputs a point Your there exists Lipischhtt and Ly--soothh functions (fi)eE with domain Bd (0) for d 2 T + max(327 (og(3//NT 32T3 log (4T such that
Pr
Piax (Faax(Foout
(Fout)
min F (x) (0)
5 3
(23)
Theorem 4 implies that the problem can only be solved by any quantum algorithm using 2 /Ne 2/3) queries. The proof is deferred to [Appendix B.3] but the idea of the proof is straightforward by combining Proposition and the hard instance defined in (22) in Appendix B.3

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
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 China (Grant Numbers 62372006 and 92365117), and startup fund from Peking University.
REFERENCES
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods, The Journal of Machine Learning Research, 18(1):8194) 19444444, 2017.
Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Ayush Sekhari, and Karthik Sridharan. Second-order information non-convex stochastic optimization: Power and limitations. In Conference Learning Theory, pp. 242-299. PMLR, 2020.
Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, pp. 1-50, 2022.
Brandon Augustino, Giacomo Nannicini, Tamás Terlaky, and Luis F. Zuluaga. Quantum interior point methods for semidefinite optimization, 2021.
Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust optimization, volume 28.
Princeton University Press, 2009.
Aharon Ben-Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2):31-335, 2013.
Hans-Georg Beyer and Bernhrr Sendhoff. Robust optimization-a comprehensive survey. Computer Methods in Applied Mechanics and Engineering, 196633-34):3190-3211 2007.
Adam Bouland, Yosheb Getachew, Yujia Jin, Aaron Sidford, and Kevin Tian. Quantum speedups for zero-sum games via improved dynamic gibbs sampling, 2023.
Fernando G.S.L. Brandão and Krysta M. Svore. Quantum speed-ups for solving semidefinite programs. In 2017 IEEE 58th Anmual Symposium on Foundations of Computer Science (FOCS), pp. 415 426. IEEE, 2017.
Fernando G.S.L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen- Lin, Krysta M. Svore, and Xiaodi Wu. Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, volume 132 of Leibniz, International Proceedings in Informatics (LIPles), pp. 27:1-27:14. Schloss
LeinnlLLeibiizZeettur fuer Informatik, 2019.
Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53-74, 2002.
Sébastien Bubeck, Qijia Jiang, Yin- Tat Lee, Yuanzhi Li, and Aaron Sidford. Complexity of highly parallel non-smooth convex optimization. In Advances Neural Information Processing Systems, volume 32, 2019.
Brian Bullins. Highly smooth minimization of non-smooth problems. In Conference on Learning Theory, pp. 988-1030. PMLR, 2020.
Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points I. Mathematical Programming, 184(1):71-120, 2020a.
Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian. Acceleration with a ball optimization oracle. Advances in Neural Information Processing Systems, 33: 13:19052-19063, 2020b.
10

---

Published as a conference paper at ICLR 2024
Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Thinking inside the ball: Near-optimal minimization of the maximal loss. In Conference on Learning Theory. pp. 06-882. PMLR, 2021.
Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization. Quantum, 4:221, 2020.
Andrew M. Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, and Chenyi Zhang, Quantum simulation of real-space dynamics. Quannum, 6:680, 2022.
Kenneth L. Clarkson, Elad Hazan, and David Woodruff. Sublinear optimization for machine learning. Journal of the ACM (JACM), 59(5): 2012.
Arjan Cornelissen, Yassine Hamoudi, and Sofiene Jerbi. Near-optimal quantum algorithms for multivariate mean estimation. In Proceedings of the 54th Anmual ACM SIGACT Symposium Theory of Computing, pp. 33-43, 2022.
Erick Delage and Yinyu Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations Research, 58(3):595-612, 2010.
Jelena Diakonikolas and Cristóbal Guzmán. Lower bounds for parallel and randomized convex optimization. In Conference on Learning Theory, pp. 1132-1157. PMLR, 2019.
Christoph Dürr, Mark Heiligman, Peter HOyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing, 3516):110--332, jan 2006. doi: 10.1 050644719. URL pttpps://ooi. org/10...gg1.... wtt.://r/o/..111111111111
Minbo Gao, Zhengfeng Ji, Tongyang Li, and Qisheng Wang. Logarithmic-regret quantum learning algorithms for zero-sum games, 2023.
Ankit Garg, Robin Kothari, Pranceth Netrapalli, and Suhail Sherif. No quantum speedup gradient descent for non-smooth convex optimization. In 12th Innovations in Theoretical Computer Science Conference, 2021.
Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. Near-optimal lower bounds for convex optimization for all orders of smoothness. Advances in Neural Information Processing Systems, 34:29874-29888 2021.
Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Se- likhanovych, César A Uribe, Bo Jiang. Haoyue Wang, Shuzhong Zhang, Sébastien Bubeck, et al. Near optimal methods for minimizing convex functions with lipschitz p-th derivatives. In Conference on Learning Theory, pp. 1392-1393. PMLR, 2019.
Weiyuan Gong, Chenyi Zhang, and Tongyang Li. Robustness of quantum algorithms for nonconvex optimization, 2022.
Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions, 2002.
Cristóbal Guzmán and Arkadi Nemirovski. On lower complexity bounds for large-scale smooth convex optimization. Journal of Complexity, 31(1):1-14, 2015.
Yassine Hamoudi. Preparing many copies of quantum state in the black-box model. Physical Review A, 105(6);062440, 2022.
Elad Hazan and Satyen Kale. Beyond the Regret Minimization Barrier: Optimal Algorithms for Stochastic Strongly-Conver Optimization. Journal of Machine Learning Research, 15(71):2489- 2512, 2014. URL httpp://m wwtp:oooo///ap...opreeeee 5/ www.aaaaannnaa 4a .ttml
Elad Hazan, Tomer Koren, and Nati Srebro. Beating SGD: Learning SVMs in sublincar time. In Advances in Neural Information Processing Systems, volume 24, 2011.
Stephen P. Jordan. Fast quantum algorithm for numerical gradient estimation. Physical Review Letters, 95(5)0050001, 2005.
11

---

Published as a conference paper at ICLR 2024
Phillip Kaye and Michele Mosca. Quantum networks for generating arbitrary quantum states. In Optical Fiber Communication Conference and Internationaa Conference on Quantum Information. pp. PB28. Optica Publishing Group, 2001. doi: 10.1164//CCQ12200.PP222 URLhtts:://on opt i ca
PPR28
lordanis Kerenidis and Anupam Prakash. A quantum interior point method for LPs and SDPs. ACM Transactions on Quantum Computing. 1(1):1-32, 2020.
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.
Yizhou Liu, Weijie J. Su, and Tongyang Li. On quantum speedups for nonconvex optimization via quantum tunneling walks, 2022.
Renato DC Monteiro and Benar Fux Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-orde methods. SIAM Journal on Optimization, 23(2):1092-1225, 2013.
Arkadi Semenovič Nemirovski and David Borisovich Yudin. Problem complexity and method efficiency in optimization. filey-Interscience 1983.
Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical programming, 103: 127-152, 2005.
Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
Shai Shalev-Shwartz and Yonatan Wexler. Minimizing the maximal loss: How and why. In International Conference on Machine Learning, pp. 793-801. PMLR, 2016.
Peter W. Shor. Polynomial algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review, 41(2)300--32, 1999.
Joran Apeldoom and András Gilyén. Improvements in quantum sdp-solving with applications. In 46th International Colloquium on Automata, Languages. and Programming (ICALP 2019). fuer Informatik, 2019.
Schloss Dagstuhl-LeiinizzZern
Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimization using quantum oracles. Quantum, 4:220, 2020.
Joran Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-solvers: Better upper and lower bounds. Quantum, 4:230, 2020.
Vladimir N. Vapnik. An overview of statistical learning theory. IEEE Transactions on Neural Networks, 1055):98-999, 1999.
Blake F. Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. In Advances in Neural Information Processing Systems, volume 29, 2016.
Christof Zalka. Simulating quantum systems quantum computer. Proceedings of the Royal Society of London Series A: Mathematical, Physical and Engineering Sciences, 454(1969):313- 322, 1998.
Chenyi Zhang and Tongyang Li. Quantum lower bounds for finding stationary points of nonconvex functions. In International Conference on Machine Learning. PMLR, 2023.
Chenyi Zhang, Jiaqi Leng, and Tongyang Li. Quantum algorithms for escaping from saddle points. Quantum, 5:529, 2021.
12

---

Published as a conference paper at ICLR 2024
A PROOF DETAILS OF OUR QUANTUM UPPER BOUND
First, we present the proof Lemma To prove this lemma, we would need modified version
of (Hamoudi, 2022. Theorem 3) given in Lemma
This circuit C' uses the unitary D we prepare in
(0) zot
Rot
Ox
(0) out
1 H
1 H
10)
Figure 1: Circuit C built from D, in which O₂ is a quantum oracle built from O, such that Os (b) (0) bt) efl(a)eee).
Algorithm as subroutine.
Lemma 3. Consider two integers S S N, real number E (0. 1) and quantum oracle Of
defined in (3). Let C denote quantum circuit obtained with Algorithh 2 on input K, 6, Oy that
correctly prepares the state
(0) = volu) 10) + / (1-PbbL)11
(24)
where (1b = -, IV EjE(M efi(E//e 12), p 2 K/N, and (eb1) is some unit state. The
algorithm performs O(VKN log(1/6)) queries O5. The circuit C performs queries to Oj.
returns correct set H, which occurs with proba- The circuit C depicted in Figure Oppeattes on four registers: rot and ind that contains a Boolean value, qry that contains real number, and out that contains an integer i [N]. The indicator gate Lи flips ind when out contains & H. Observe that the final state is C (0) [0) gry 10) ina ()) out.roe where
Proof. Suppose that DuanttumMax:iumiinnde
bility at least
16) out ww/Z (1) out 10) + 1111-WW W/Z [v'))uu 10)
(25)
in which W E, exp(f((z)/e)) and (w') is some state whose value is irrelevant. To bound the coefficient p- = W//2 Z, notice that by the definition of h, we must have exp(h/e') s W/K, or else
Σ, expppptr (f(()(e) W, which is contradiction. Consequently, obtain
Z
(N - K) exp(h/e') + Eieh exp(f((3)e))
N-K
K
N K
p p-
(26)
W
exp((((())
K
indicating that p Z K N
Next, bound the query complexity of the preparing of C. Notice that for unMaxiiuee
to succeed with probability at least 1- 5, needs to make O(VKN log(1/5)) queries to the oracle O, defined in 33. according to Proposition 1 Since all the remaining steps (Line 2 Line 4 in Algorithm 2) involve only classical computation, additional quantum queries required, the total number of quantum queries needed is D(VKN log(1/6)). O
Next, we present the proof of Lemma
Proof of Lemma | The result follows directly from Lemma 3 and Proposition Given that p 2 / /K/N, Ampli tudeAmplllll fi ficat ion requires only O O(v N/K) calls to C. Notice that each call to only costs two quantum calls, the cost for preparing K copied states OvNN)). Combining these costs with the cost for preparing C gives the result Le 1.
13

---

Published as a conference paper at ICLR 2024
Note that preparing D, we keep only the first K largest elements in the distribution to make that the coefficient /p before (bb) can be lower bounded. This ensures that the amplitude amplification algorithm can prepare K identical target states with the lowest total cost.
Next, we provide some classic results regarding E mas and Fsmaxx,c
Lemma 4. Given P Faxx and Famax, as defined in T2). If is an approximate minimizing point of F smaax. with suboptimality e/2, then Vx is also an approximate minimizing point of Fmax with suboptimality
Proof. The proof is straightforward given the fact that 0 S F F (x)) Finax (2) S c/2 (see Carmon al. 2020b Lemma 45). Thus, we have
(max(xx)) min (max((1a) = F Fmax((er) =ER*
min (
(27)
xE =g(o))
S F smax (xa)) (a)-
min Famax,e(x)) + 2
Se.
(28)
De RERR(Fo)
Lemma 5 (Rephrased from Carmon et al. [021 Lemma 1). Let fi...., JN each be Ly-Lisschitz and b.g smooohh gradients. For any c > 0, r S cé' [L., and X S cl,//r let C + ? 2) The exponentiated softmax L'c, satisfies the following properties for any I E R2.
FA s and ee,> have the same minimizer x in (T). Moreover, for every I E B, (T),
F Damax,(23) - F Fimax, (xx) & C(T - (z,)
(29)
Restricted to (T), (x)) = (x) is CT..--ipshitz, X/C strongly convex, and C(Lg + A L3fe) -smooth.
B PROOF DETAILS OF OUR QUANTUM LOWER BOUND
B.I WARMUP: QUANTUM LOWER BOUND FOR MULTI-ROUNDS UNSTRUCTURED SEARCH PROBLEM
First, we consider where the difficulty lies in minimizing the hard instance. Consider an algorithm that
tries to achieve prog, (UT x) = T on the "shuffled" version of J: Vz. f(x) = max J&(UT x), fn-1()) in which U is random rotation and II is random permutation.
Definition 3. Based on an a-robust N-element zero-chain, we define its shuffled version f(x) = max (x) such that for all x E RO), all y in neighborhood of x, and all E [N], we have
[n~1(0() V1sØ)) prog, u f(()) = Su-ic0(U vispt1))
IT 1p+1
(
(30)
(U MisH)
IT- ( p+1
in which is an arbitrary rotation and II is a permutation over [N].
In order make progress, the algorithm can either guess randomly (succeeds with minor probability) or use the oracle information. However, at first all of the gradients are 0 unless the algorithm queries fu(1). Then, II(2) needs to be discovered to uncover new gradient direction. Thus, the algorithm needs to sequentially discover IT(2).. ... IT(T) in order to find the with progress T, each of which is approximately an unstructured search problem requiring certain number of oracle queries.
From the structure of the hard instance, we see that the key of finding the minimum of an N-element zero chain is to find an x that has large prog, and an i that is the right direction (since on any other direction the oracle would only reveal information regarding the "shallower" fi's). Notice that this is essentially a multi-round version of the unstructured search problem where one need to sequentially search the Zp. ip 's such that prog, (Ip) p and ip II(p + 1). Thus, to establish quantum query lower bound for our problem, we begin by introducing the following variant of an unstructured search problem that has the same underlying structure as the Definition
14

---

Published as a conference paper at ICLR 2024
Problem 1 (Multi-rounds unstructured search problem). For some N, K 0 and d 2 10K In N, suppose there is a sequence of K numbers ai,...,aK E [N] and each number a, is associated 0 Define the search function
with a different "key" 8; which is d-bit string. Suppose
Faearch: [N] x [0. + 1) to be
8141,
if otherwise.
i E [K] such that a 0g and 8 = 8i,
Feearch (a, s) (0r
(31)
Intuitively, can discover the i + 1th key if and only we know the ith number a; and its corresponding key st. Suppose we have access to the following quantum oracle Osearch encoding the value of F seaarch:
Osearch [s) (0) + |s) (a) Feearch (a, 8))
(32)
the goal is to oulput sk-
We prove quantum query lower bound for Problem by first dividing the oracle Osearch into series of oracles. In particular, define of functions F(I) defined as
search bil where each 1=(3)
seearch is
F scarch (a, 8)
14+1, if ag and 8t Or
(33)
otherwise.
As see, each F())
search represents Fsearch in certain input domain. Moreover, define series search Ou encoding the values of F())
of quantum oracles (1)
F(K)
search
search.
(i)
(s) a) (0) - (s) la) p(())
(a, ()).)).
(34)
search
Then, one query to the oracle Owarch can be implemented using at most K queries to the oracles
((1) Ouarrch s.
O (k)
scarch The following lemma shows that, if the jth key s; is not fully discovered,
would be hard to further discover the next key 8,41 even given access to the oracle O(1 search
Lemma 6. For any quantum algorithm A making at most T VN /6 queries to the oracles (0()) )earch+
A= sourch -O ((TT)) search ... O (te)
search Vo.
(35)
for any 0 S K. if at any step of the algorithm the intermediate quantum state [b)) has in expectation at most ō overlap with (8k), ie.,
S 8, we have
1
E 86
|5 M
(36)
24/2
Proof. For any fixed value of a and sk+1. use |vt)) denote the quantum state at stage t. Similarly, use (V') to denote the quantum state stage t if any query to (()) search is replaced by identity operation, which can be expressed as
/ = (s M
(sx) (0 + /I - Ks 20P "
(37)
where ( represents the quantum state the second and the third register that can be written as
1+
Σ NE[N]
Be, (6) Irax),
(38)
where we reorganize the state with respect the second register, whose computational basis corre- sponds to all possible values of the N items.
Then for any value of ag, we have
(
|/DI| s (1sHI Σ BL.aul
(39)
15

---

Published as a conference paper at ICLR 2024
Consider taking expectation over 83 and ok, based our assumption that [s
M.Yl S 6, we have
8/
f-1
E S/
|
| - 26
Σ
Brabb
(40)
T=0
and
25t 5 VN
T -
| - 28
E
Br,axl
S
(41)
Sk Ogg
3
Since (V]) is irrelavant from 8k41, we derive that
E
K5
2 2-44/2
(42)
8k
which leads to
II 02: -81+1
(SK+1///
!|| - |/DI
+ E #k+1
155++1
S 24/2
(43)
Sk.0g
Lemma 7. For any K < 2d, any quantum algorithm making less than 6K queries to the oracle Qwearch defined in (32), there exists an instance ofoProm 7 sscch that the algorithmm fails solve Problem 1 with expected probability 1 2-K among all possible 8k, or equivalently, for any intermediate state (V) of the algorithm, we have
VN
B 52-K KK
E
(44)
Proof. We first prove quantum query lower bound for Problem with access to the oracles
(
search O (K)
search In particular, we consider any quantum algorithm A for Problem using
T V queries to O (I)
((0) search O search for some large enough constant C 2 1, it can be
expressed as
VT (1T--1) ((T-)))) ((6) search
search Vo (0).
(45)
search
Denote (Wout) to be its output quantum state. We use 6, to denote the expected overlap with (s;) among any intermediate stage of the algorithm. Then by Lemma have
6,41
S 3 2d/2
(46)
which leads to
1
1
E [V/s)) *x
(47)
3R 2d/2-1
2K
That is to say. any quantum algorithm making at most VN/6 queries to the oracles (
search ... search will fail find Sи with probability at least 2 Since the oracle O Osearch can be implemented using K queries to Oa) search O search:
((()
conclude that for any quantum algorithm making at most /N (6K) queries to Osearch, it fails to solve Problem with expected probability 1 2 2-K K among all possible sk.
(A8)
This result shows that quantum algorithms cannot do much better than classic algorithm when tackling a sequential structure where each step requires finding a new secret for the next direction. The only speedup in this case is the quadratic speedup brought by Grover's algorithm the unstructured search problem. Moreover, the error any quantum algorithm is exponential with the depth of the problem.
16

---

Published as a conference paper at ICLR 2024
B.2 PROOF OF PROPOSITIOO 6
From an oracle O,, we defined its "shuffled" version Oj for f Definition 3) where
Ofli) (z) = O, |I (I) (Tx) x)
(48)
in which randomly sampled permutation over [N] and U is randomly sampled rotation. According to the property of the zero chain, the subspace that we are interested in is the one in which progress is greater than expected. Formally speaking, we define
Pt = (x Bn( > f.(x, u.) a, E (T))
P. = = P.
(49)
To prove Proposiioosi 6) we begin by observing that making progress on an N-element zero-chain essentially solving the multi-round unstructured search problem (Problem I). In particular, Oj is the analog of Osaarch defined in (32), the p-th function after p; is the analog of the solution of the p-th round of the unstructured search problem, and the informative region of this function is the analog of the "key" in this round. Morcover, define the following "truncated" oracle O of Oj. be the
analog of the oracle (i)
search in Section B.1
0 (b) On -1- (
(50)
where O,, is the evaluation oracle for the i-th function ft. Based on this oracle, we prove the following result that an analog of Lemma
Lemma 8, For any quantum algorithum A making at most T v VN 6 queries to the oracles {
A= ---
0 Vo.
(51)
for any k- K, if at any step t of the algorishm the intermediate quantum state ()))) satisfies
E || (K)) ( 8
(52)
where P(j) denotes the projector onto the informative region of the j-th function fz. we have
5 + do2/2
IP (k- 1)) (+ N.U
E
S
(53)
3
Proof. We use ) denote the quantum state at stage t. Similarly, we use (M))) denote the quantum state at stage t if any query to (th)) replaced by identity operation, which can be expressed as
(V = |II (k)) ( || (k)) W/ + / IP((I- MX 12)
(54)
where PIII-((A:) (V) represents the quantum state in the second and the third register that can be written
((I) = Σ Bex (i) (o,,e)
(55)
(E(N]
where we reorganize the state with respect the second register, whose computational basis corre- sponds to all possible values in [N] Then we can derive that
w
< 21)P((T V
(56)
T=0
Consider taking expectation over II and U,, based on our assumption that we have
(.,)
s
IT.U
E Sk
|||
w
< 25
Σ
B II
10))
(57)
+=0
17

---

Published as a conference paper at ICLR 2024
and
2ôt 8
(
M - 26 Σ EI (0)
(58)
VN
3
Since V
is irrelavant from U and II, using known fact in the probability theory (see e.g.. Zhang
& Li 2023
Lemma 17)
Pr((2,, u} a) S 2e do212
(59)
we have
E 11.
(II (1)) wV - 2c 2 do
(60)
by which we conclude that
El|P(II- 1)) (
E | | + |I (R)) (1 |I
(61)
I1U
v + 2c dd²/2
(62)
3
The next lemma is analog of Lemma 7
//N Lemma 9. For any K S da² /4, any quantum algorithm making less than 6K queries to the orucle oj defined in (.).. for any intermediate state ( of the algorithm, we have
E II (K)) (K)) n1C
(1) 2
(63)
Proof. We first consider the case with access to the oracles 0 ..... ofk) In particular, we consider
any quantum algorithm A for Problem usiig T /N/6 queries O ,.... .
((K) for some large
enough constant C 2 1, it can be expressed as
-
(10) . Vo 10).
(64)
Denote Ivouut be its output quantum state. We use 5, to denote the expected value of [[P(III- (()) (V) among any intermediate stage of the algorithm. Then by Lemma we have
8(41 < 8;
+ 2e-daa da?/2
(65)
3
which leads
6K S 3R
+ 4e
-da
12 < 2
(66)
That is to say, any quantum algorithm making at most /N N/6 queries to the oracles 0
o K)
will fail to find with probability at least 1 - 2 K Since the oracle O, can be implemented using K queries to o()) ( (K) we can conclude that for any quantum algorithm making at most vN/(6K) queries to Of. any intermediate state (T) of the algorithm satisfies (63)
Lemma 10. Consider the unitary An with n queries O of the form
An = -OV.
(67)
in which n (N/((K) and K 4log T + log + 5. Then for any input state (W), we have
7(n) = E || An 10)
(68)
16VNT1
as long as the dimension d > 4K/a²
18

---

Published as a conference paper at ICLR 2024
Proof. Observe that achieve (n) by the summation of overlap given in Lemma 9 and an upper bound of the success probability random guesses. The first term is at most
2 2-k 32VNT4
(69)
by Lemma 9
Meanwhile, the second term is at most
T 26 T- do2
(70)
32V NT
by which we can conclude that
1
7(2)
(71)
16vNT1
Next, we state the fact that is fundamentally hard make progress by random guessing.
Lemma 11 (Cannot make progress through guessing). Let {u:)imı be a set fixed orthonormal vectors. Choose {u, J uniformly randomly such that Ju)e is orthonormal. Then
Vx E BR(O), Pr ur+I...Ur
(progar: 2 t) 2Te (d-T)/3-)33
(72)
in which of 1/443)22)
Proof. We use a standard union bound with some common facts to prove this lemma. First, using union bound we have
Pr Mr
(proga (1)
2) S
Pr((a, u,) 2 a)
(73)
(T Pr((x, u.) a
(74)
where the final equality is due to the symmetry among u, 's Next, using known fact in the probability
theory (see e.g., Zhang & Li]2023 Lemma 17) we have
Pr((x, u) 2 c) S de²/2 u
(75)
Considering that up-1,... ur sampled from d T dimention space orthogonal to the fixed vectors, we have
Pr uy
(proga (x) 2 t) < 27' (3-7)/3273
(76)
With these results at hand, we now articulate the proof technique for PProposiiion 6) The proof technique involves using a quantum hybrid such that is almost impossible for the last hybrid find the minimizing point. First, we introduce a truncated oracle
O (1) xx ly)
y + fn-+(0 (u x, un x x...u
u4 x, 0, ()).
(77)
Note that Ô, does not reveal any information about Ust Given a quantum algorithm A making < TVN/CK queries, the algorithm can be represented in the form
V,O,Va-1 -.Vo.
(78)
From this algorithm we could build & hybrids:
Ag = A VNNNICKO ... Ô10log rV V VNICK-I ".VViO,
A = V " Ów0lrr V ... 0101og Ō 11000or Vo:
(79)
Ag Olok logT - T VNNCK-I" 110 Vi
19

---

Published as a conference paper at ICLR 2024
Note that the difference between two consecutive hybrids A,-1 and A, is that VN/CK of the oracles o are changed to log Following the standard hybrid argument, in the subsequent lemmas demonstrate that the output of the sequence of unitaries (the difference between A, and A,-1) random input similar.
Lemma 12. For any L E (T - 1] and any S VN/CK for K 4log T + log N + 4, consider the following two sequences of unitaries.
A(n) = 1,.00O...,.--........
(80)
and
A.(m) V.V. ... Ô.Vo.
(81)
Given that d 2 T max
3277 log (127)), we have
5(n) = = || - A) 100100)
(82)
16VNT4
Proof.
We use induction to prove this lemma. For = 1, we have
(1, - o.) (v) [|] s 16vNT4
6(1) E
(83)
where the inequality follows from Lemma 11 Suppose the inequality à < vn. For n ñ + 1, by Lemma 10 we first have that
82
holds for Vn for some
E
p wa>ll
(84)
16V
Next, we have
E 11 [0)) ||] 8(A))
8(n) 8(1)
(85)
E || | |1]] + +((F) 16vN7*
(86)
in which inequality 86 is due to the fact that only with i > t can contribute to the expectation.
Lemma 13. Ifd 2 T 327 log 32 32 ffr for an N-element zero chain f we have
1
ElIl A. 10)19
(87)
16T4
Proof. From the definition of the hybrid unitaries A, Eq. 77).. we have
E[I[(A - - 10 [ILAVN//KK) A(VN/CK))
(88)
Thus, according to Lemma 12 the expectation is bounded by
1
B[I[(, A,-1) [0)13) 167
(89)
Equipped with Lemma 13 are ready to prove Proposition 6
Proof of Proposition 6 First, suppose that the quantum algorithm only makes at most T TVN 2CK² queries. in which K 4 log T + log N 4. According the construction of the hy- brid 79p. the last vector uy is never revealed. Thus, by Lemma 11 letting 2 T T max (327 log(32/NT*), 32T 3223 log (4T/ the last unitary in the hybrid can find an x with suffi- cient progress with probability at most 5/2.
20

---

Published as a conference paper at ICLR 2024
Next, we can bound the total variance distance between the distributions obtained by sampling Ao (0)
and Ax (0). By Lemma 13 and the Cauchy- Schwarz inequality, we have
[lk - Ao) 10) K
- A-1) 167
(90)
Now, applying Markov's inequality, can establish that
1
Pr [AA Ao) 10)1 > 47
(91)
4T
which indicates that the total variance distance can be bounded by summing up 1/())) + 1/(4)) = 1/(21") < 8/2, provided that T' 2 8-1 Combining these two parts allows us to upper bound the success probability by 8.
B.3 PROOF OF HEOREM 4
First of all, provide the hard instance use in the proof of the main theorem:
flT.N. (x) =
(()=))()))) Vont
Fig [[-1]]
i H T,
(92)
0
otherwise,
where we denote or 473/2 210]
1
/T' and vaae R + R is defined as
(0
| a $ | +a
(tae(t)
L (t a)²
2
[1] a 2
otherwise.
The properties of this hard instance f(r,N,() is given in the following lemma.
Lemma 14 (Carmon et al. 2021 Lemma 2). For every T, N E N and /' 2 0, such that S N, we have that
The hard instance (F.(T.N.)) IEN an oey-robust N-element zero-chain.
2. The function J.T.N.C is I-Lipschitz and E-smooth for every i [N].
3. For any x E Rd with prog(or)
(x) < T, the objective F(T.N.0) = max,e[N] f(T..N.) (x)
satisfies
f(T.N(())
(T..) 2 var 8TT3/2 (0)
min
2 min 8T3/22 32T3
Next, we present the detailed proof of Theorem 4 using Proposition 6 and the hard instance defined in
Proof of Theorem Theorem is direct result of Proposition 6|ddd the property of (92). Notice
that from Proposition 6 when d T max (327 ( 327's log (4T /8)) and T > the success probability of the quantum algorithm making at most T TVN/CC CV///-CO (4log T 1/2 log N + 4)2 queries discovering ur is at most 1/3. Set
max (( (
2/3
Lg
1/3
and L = I.g R/T.--
(93)
Note that under this setting we have that the lower bound number of queries is TV /C/C(4 According to the part 3 of Lemma 14 if the algorithm failed in
log N + 4)2 Ū(VNe discovering the th direction ur (i.e., proger (x)) < T), the suboptimality of the output minimizing
point is at least minf 873/2. 3274
C S c. Thus, we have
Pr
Fmax (Jout)
min Fmax (x) 2 E 5
(94)
ze xE
21


Reviews:
[{"review_id": "WQI7HyfIa5", "reviewer": "Reviewer_aSjj", "summary": "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.\n\nThe 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].\n\nThe 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.\n\nThe 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)", "questions": "I tried to understand Algorithm 2 (quantum sampling algorithm), but due to some time constraints, I did not fully understand it and I believe some better explanation should make the paper better.\n\nI understand that you first find the $K$ largest elements of the distribution, and then you set the probability of rest element equals the probability of the $K$-th element -- this changes the distribution. Do you need some rejection sampling procedure afterwards?\n(Is the answer is in figure 1? Then it would be better to move figure to the main paper).", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper gives improved quantum algorithm for a basic problem in convex optimization. The idea of using quantum Gibbs sampling for improve is interesting.", "weaknesses": "The major unsatisfactory point is the unmatched upper and lower bound.\n\nThe presentation is fine in general, but it could be improved (e.g. I found the English a bit awkward some time). Some detailed comments:\n\n(1) Page 1.  \"Nesterov (2018) showed ...\"  I believe it is an old result, not shown recently. Probably change it to something like \"it is known that .... e.g., see Nesterov (2018) \".\n\n(2) Page 4. \"named ket\" I don't think you need to name it. For quantum people, they know what's the notation means; for non-quantum people, it is not informative and it does not appear twice in the paper.\n\n(3) Line 5 in Algorithm 1. The subscription is confusing.\n\n(4) Page 8 \" given in Ref.  Carmon et al. (2021)\". Remove Ref.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "idSq67uRjG", "reviewer": "Reviewer_J3o2", "summary": "This paper designs new quantum algorithm for the problem of minimizing the maximum of $N$ convex functions with near optimal quantum query complexity. \n\nGiven $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)\\\\}$. \n\nThe goal is to find an $x*$ so that $F_{max}(x*) - inf_{x} F_{max}(x) \\leq \\epsilon$. \n\nThis 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.  \n\nThe 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. \n\nThus 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.", "questions": "It will be nice to further explain  the reason for the gap in upper and lower bounds, in particular in comparison with classical algorithms. Is the reason classical algorithm does better in $\\epsilon$ is because of more powerful (first order as opposed to zeroth order) oracle? Also, I am not clear what you mean by the statement \"However, as far as we know, ...\" the last sentence before Contributions. Probably it is good idea to make sure it is indeed open.  It is probably fine for smaller results in the paper, but for the main question you are considering, it is better to make sure that the status of the problem.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The strength is that the paper  reports progress on a fundamental and well-studied optimization task. It is natural to consider the question whether the speed up you get in other quantum search algorithms (such as in Grover's algorithm) can be lifted to the optimization literature also.  So in that sense, the results established are clean and informative.", "weaknesses": "A weakness is the originality. It appears that nothing very new is going on here and the results (at least with respect to $N$) are expected. Also, it is not optimal with respect to $\\epsilon$. In fact, known classical algorithms do better with respect to $\\epsilon$. So in that sense the picture is not complete, which the authors do not seem to address.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OyRwKq9Jq0", "reviewer": "Reviewer_ixEA", "summary": "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. \n\nThe 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.", "questions": "None.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper studies a natural problem in optimization and shows that quantum algorithms could do better.", "weaknesses": "A disadvantage is that the algorithm in a sense takes an existing classical algorithm and replaces a step in it with a suitable, known, quantum algorithm. So novelty is a bit low.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DZfZWfUhDu", "reviewer": "Reviewer_gKCY", "summary": "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.\n\nThe 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.", "questions": "The quadratic speedup is a recurring feature of quantum algorithms and in many cases the phenomenon at the core of the speedup is the same. The techniques described in this paper can perhaps be applied to other computational/optimization problems. I wonder if one can state a general meta-theorem of the form: \"For a wide class of computational/optimization problems, if we have a classical algorithm that solves it and which satisfy some properties, then we can find a corresponding quantum algorithm with a quadratic speedup\".", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The results of the paper are novel and interesting. Furthermore, the dependence of the number of queries of the algorithm that is presented in the paper on the number of functions $N$ is shown to be optimal up to logarithmic factors.\n\nI also find the paper to be generally well written.", "weaknesses": "There is still a gap between the query-complexity of the algorithm and the shown lower bound in terms of the dependence on $\\epsilon$, but this is not a significant weakness of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)