Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits
Authors: Tongyang Li
Ruizhe Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Approximately convex functions
quantum computing
stochastic convex bandits
logarithmic regret

Abstract: We initiate the study of quantum algorithms for optimizing approximately convex functions. Given a convex set $\mathcal{K}\subseteq\mathbb{R}^{n}$ and a function $F\colon\mathbb{R}^{n}\to\mathbb{R}$ such that there exists a convex function $f\colon\mathcal{K}\to\mathbb{R}$ satisfying $\sup_{x\in\mathcal{K}}|F(x)-f(x)|\leq \epsilon/n$, our quantum algorithm finds an $x^{*}\in\mathcal{K}$ such that $F(x^{*})-\min_{x\in\mathcal{K}} F(x)\leq\epsilon$ using $\tilde{O}(n^{3})$ quantum evaluation queries to $F$. This achieves a polynomial quantum speedup compared to the best-known classical algorithms. As an application, we give a quantum algorithm for zeroth-order stochastic convex bandits with $\tilde{O}(n^{5}\log^{2} T)$ regret, an exponential speedup in $T$ compared to the classical $\Omega(\sqrt{T})$ lower bound. Technically, we achieve quantum speedup in $n$ by exploiting a quantum framework of simulated annealing and adopting a quantum version of the hit-and-run walk. Our speedup in $T$ for zeroth-order stochastic convex bandits is due to a quadratic quantum speedup in multiplicative error of mean estimation.

Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits
Tongyang Li
Ruizhe Zhang
Advanced Institute of Information Technology, Center on Frontiers of Computing Studies, and School of Computer Science,
Department of Computer Science
The University of Texas at Austin
ruizhe@utexas.cm edu
Peking University tongyangli@pku. edu. edu. cn
Abstract
We initiate the study of quantum algorithms for optimizing approximately convex functions. Given convex set K. C TR"h and function F: 1 IR such that there
exists a convex function f: IC + R satisfying sup,ek F(x) f(x)] S e/n, our quantum algorithm finds an x² K. such that F(x*) min,ek F(z)) S
using (n²) quantum evaluation queries tum speedup compared to the best-known classical algorithms. As an applica- tion, we give a quantum algorithm for zeroth-order stochastic convex bandits with Ón log" T) regret, an exponential speedup T compared to the classical ((VT) lower bound. Technically, we achieve quantum speedup n by exploiting a quantum framework of simulated annealing and adopting a quantum version of the hit-and-run walk. Our speedup in T for zeroth-order stochastic convex bandits is due quadratic quantum speedup in multiplicative error of mean estimation.
This achieves polynomial quan-
Introduction
Optimization theory is a central research topic in computer science, mathematics, operations re- search, etc. Currently, many efficient algorithms for optimizing convex functions have been pro- posed (see for instance [10]), but much less is known for nonconvex optimization. In this paper, we investigate polynomial-time algorithms for optimizing approximately convex functions. On the one hand, such algorithms enjoy robustness and cover many natural scenarios including stochastic convex optimization, empirical risk minimization, etc. On the other hand, approximately convex optimization paves the way of understanding nonconvex optimization in the general case.
Specifically, let KC C R be convex set. We call F: R -> IR as approximately convex function over K. if there is a convex function f: K. - IR such that
sup F(x) f(x) < c/n.
(1)
=E
Throughout the paper, we assume that is L-Lipschitz with respect foe norm, (f())=(() <
L|| y yl for any z. y E K. We assume that (2, 1) S K. C (2, R), i.e., the convex body K. contains the unit ball centered otherwise mentioned, we aim at algorithms with poly (log R) dependence in R.
and is contained by a ball of radius centered O. Unless
It is standard to assume the zeroth-order oracle of F, which returns the function value F(x) given an input x. As far as we know, the state-of-the-art algorithm for finding an x E I. such that F(x*)=
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

mingek F(x) S e with high probability was proposed by Belloni et al. [8], which takes (mn queries to the zeroth-order oracle. On the other hand, Ref. [34] proved that if the approximation least ((max(c/n, c//,////////////////// 2/ ///nn))), ), there exists function F which no algorithm can find point x" K such that F(x") - min F(x) I using poly(n, 1/c) queries to F. In other words, the c/n term in (1) is fundamental, and has been the standard assumption of studying approximately convex optimization in [8, 34).
error in (1)
Based on approximate convex functions, closely related scenario is stochastic convex functions, where we have a function F: Ik" + R such that
F(x) = f(x)+ c
Here /: 1 - RR is a convex function and eær is a Gab-Gasssian random variable with parameter o, i.e, R(exp(Aex)] S exp(o2>²/2) for any x. This implies that
Pr|lel 2 otl s e vt 1+20
(2)
Using this fact, Belloni al. [8] gave an algorithm for stochastic convex optimization with Ö(n (n75)/e) queries a zeroth-order oracle of F.
Contributions. In this paper, we conduct systemic study of quantum algorithms for optimiza- tion of approximately convex functions, with applications zeroth-order stochastic convex bandits. Quantum computing is rapidly advancing technology, the capability of quantum computers is dra- matically increasing and recently reached "quantum supremacy" by Google [6] and USTC [42]. In optimization theory, quantum advantages have been proven for semidefinite programs [3, 4, 11, 12), general convex optimization [5, 15], the escaping from saddle point problem in optimization [41], etc. Nevertheless, far we know, quantum algorithms for approximately convex optimization and stochastic convex optimization are widely open. In this paper, we consider these problems us- ing the quantum zeroth-order evaluation oracle Or, standard model used in previous quantum computing literature [5, 14, 15, 41]:
Oflæ, u) = lx, F(x) + v) Vo Vo E E.
Here 1-) is the Dirac notation, and preliminaries of quantum computing will be covered in Section 2. Intuitively, Eq. (3) can take inputs with form E C; (x,) & (0) where x; E R" Vi E [m] and E |ca = 1, and if we measure the outcome quantum state, we get Fxx;) with probability c.22. In particular, the quantum zeroth-order oracle allows the ability to query different locations in superposition, which is stronger than the classical counterpart (i.e., m 1). Nevertheless, if the classical zeroth-order oracle can be implemented by explicit arithmetic circuits, the quantum oracle in (3) can be implemented by quantum circuits of the same size up to logarithmic factors. As for stochastic convex functions, similar to (3), we assume the following oracle:
Ogl v) =1x>) { (ox(5))(()) + y E Vr BRERR
(4)
JEER
where for any x E R", 9=(E) follows sub-Gaussian distribution as in (2).
Our first result is quantum algorithm for optimizing approximately convex functions:
Theorem 1. With probability at least 0.9, we can find x E K. such that
F(x")
min F(x) Se sEK
(5)
using (n²) queries to the quantum evaluation oracle (3).
We remark that the sucess probability can be easily boosted up to 1- 8 for any 5 E (0, 1). by paying an extra log(1/5) factor in the quantum query complexity. Compared to the best-known classical re- sult by Belloni et al. [8] with query complexity (n5..)), we achieve a polynomial quantum speedup in terms of n. Technically, Belloni et al.' algorithm is based on the simulated annealing process and using the Hit-and-Ruu walk to generate samples in each stage. In this work, we give user-friendly
'The Ô and 52 notation omits poly-loga terms, ie.. Ö(g) O(g poly g)) and Ô(()) = [gg poly (log g)). Unless otherwise mentioned, both notations also omit poly 1/c) terms.

---

version of the quantum walk framework (Theorem 3) that can be applied very easily to obtain quan- tum speedup for the mixing of classical Markov chains. We then analyze the warmness and the overlap between adjacent Hit-and-Run walks in the simulated annealing process, showing that our quantum walk framework is applicable to each classical Hit-and- sampler. By implementing the random walk quantumly, we improve the query complexity of the sampling procedure from Ō(n²) to (nn (Theorem 4). We also design a non-destructive rounding procedure (Lemma 4) in each stage of the simulated annealing that simulates the classical rounding procedure [8] but will not destroy the quantum states of the quantum walks. Combining them together gives the O(n"))query -uuuey quantum algorithm for minimizing approximately convex function. Our result can also be ap- plied give an -query quantum algorithm for optimizing approximately convex functions with decreasing fluctuations.
See Section 3 for more details and the proof of Theorem 1.
Furthermore, to estimate the mean of random variable up to multiplicative error e, classical al- gorithms need to take 1/c² samples due to concentration inequalities such as Chernoff's s bound, whereas quantum algorithms can take roughly 1/c queries (see Proposition 1). As result, we obtain polynomial quantum speedup in both n and 1/c for stochastic convex optimization: Corollary 1.
With probubility least 0.8, we can find an x² E K. such that min =EK
f(x")
((
(6)
using Ö(n%/c queries to the quantum stochastic evaluation oracle (4).
We apply Corollary to solve the zeroth-order stochastic convex bandit problem, which is a widely studied bandit model (see e.g., [22, 24, 25]). The problem is defined as follows. Let IC C I be convex body and f: KC - [0, 1] be convex function. Here (0, 1) S K S (0, R). An online learner and environment interact alternatively over T rounds. In each round E [T]. the learner makes query to the quantum stochastic evaluation oracle (4), and returns a value 24 E K. as the current guess. The learner aims to minimize the regret
T R = E Σ
(((x)) - -((
where f =in f(z), xe
and the expectation is taken over randomness. The classical state-of-the-ard algorithm using a classical stochastic evaluation in each round achieves a regret bound of 0(n+55 VT) [25], and there a classical lower bound (nn/T) on the regret [19]. Here we prove:
Theorem 2. There is a quantum algorithm for which Rr = Ö(n log(T) log()))).
This achieves poly T)) regret for zeroth-order stochastic convex bandits, an exponential quan- tum advantage in terms of compared to classical zeroth-order stochastic convex bandits. As far as know, give the first quantum algorithms with poly-logarithmic regret bound on online learning problems. An independent work [37] gave quantum algorithms with poly-logarithe gret for multi-armed bandits and stochastic linear bandits, but these two types of bandits concern reward of discrete objects and linear functions, respectively, which are fundamentally different from the stochastic convex bandits study.
re-
To achieve this poly(log T') regret for zeroth-order stochastic convex bandits, we divide the T iter- ations into !log, T] intervals with doubling length 1, 1, 4,... We use the quantum queries from previous interval to run our quantum stochastic convex optimization algorithm and use the output as the guess for all iterations in the next interval. Since can achieve linear dependence in 1/c in Corollary 1, it can be calculated that the total regret in each iteration is at most Ö(n log(T R)), leading to our claim. The proof details are given in Section 4.
Open questions.
Our work raises several natural questions for future investigation:
Can we further improve the dimension dependence of our approximate convex optimization algorithm? The current quantum speedup mainly leverages the quantum hit-and-run walk; it is of general interest to understand whether we can gain quantum advantage other steps, whether the convergence analysis of the hit-and-run walk per se be improved.
3

---

Can we improve the dimension dependence of the regret of our zeroth-order stochastic convex bandits? It is natural check whether our n² term can be improved by quantizing the classical state-of-the-ar [25] and other recent works.
Can we give fast quantum algorithms for more general nonconvex optimization problems, or with poly-logarithmic regret for more general bandit problems?
Limitations and societal impacts. This work is purely theoretical. Researchers working the- oretical aspects of quantum computing and optimization theory may benefit from our results at the moment. the long term, once we have fault-tolerant quantum computers, our results can be ap- plied to approximate convex optimization and stochastic bandit scenarios arising in the real world. As far we are aware, our work does have negative societal impacts.
2 Preliminaries
2.1 Basics of quantum computing
We briefly introduce basic notations and concepts of quantum computing in this section. More details are covered standard textbooks, for instance [30].
Quantum computing can be formulated in terms of linear algebra. Specifically, the computational basis of space Cd can be denoted by , where é; (0, ... I, .,... ................................ 0) with the 7th entry being and other entries being O. These basis vectors are typically written by the Dirac notation, where we denote ē by {i) (called "ket"), and denote ह by {il (called "bra").
A d-dimensional quantum state is 22-norm unit vector in Cd e.g., lu) (m1...., ua) such that Σ; |0: 1. For each i, f2 is called the amplitude |t). The tensor product of quantum states their Kronecker product: if [u] E CCh and (v) E Cde, then
[u) (n) := (u1 v1, U2 ..., Ud, vdz)) E Cdi @ Cd.
We often omit the operator @ and simply write (u) (u) or ju, e) for being concise.
In general, the definition of quantum states be extended to continuous domain. For instance,
(u) = Jxn Ux (x)ddx
represents quantum state long fgn 12 1. To keep quantum states normalized in lg norm, operations in quantum computing are unitary transformations.
2.2 Classical and quantum walks
A classical Markov over the space Ω is a sequence of random variables {Xi such that for any
i and .o...., 2i E Q2
Pr[X, = x, Xo = zo. X;-1 = x;-1] Pr[X; = x; X xi-1]-
The Markov chain
be represented by its stochastic transition matrix P such that Σyea P(r, v) = for any x E Ω. A distribution æ is stationary it satisfies Exeo (((x))(rr))) y) = (B) for any y E Ω. A Markov chain is reversible if its stationary distribution satisfies the following detailed balance condition:
(x)) v) = ((y Vz,y EQ
The mixing time of Markov chain with initial distribution mo is the number of steps t ((c) E N such that the total variation distance between the time-t distribution and the stationary distribution most for any E (0, i.e,
(Pv(P'mp T) S e.
In quantum, we can also define the discrete-time quantum walk [36], which is a quantum-analogue of classical Markov chain. More precisely, we use quantum state to represent classical probability distribution:
(m)))EEE
(T)
Σ ren
[
In quantum walk, there are two operations:

---

Reflect: An operator R that reflects the quantum states with respect to the subspace span(la) Ieen, where (a) = Eyea PP(,, lv).
Swap: An operator S that swap the two quantum registers: S (ax) (b) (0) (a)..
Then, the quantum walk operator W defined as: W := So R. Intuitively, the first quantum register contains the current position of the random walk, and the second register contains the previous position. In each step of quantum walk, the R operator makes a superposition in the second register of the next step positions with amplitudes proportional to their transition probabilities. Then, the operator swaps the two quantum registers, using the first register to store the new positions and the second register store the old position. In this way, we complete one-step of the random walk coherently (in superposition).
The quantum advantage of the quantum walk comes from the spectrum of W. Note that the state of stationary distribution Eren V ((x (x)) (ı/) is invariant under W. In other words, it is an eigenvec- tor with eigenvalue (eigenphase 0). On the other hand, the other eigenvectors of W has eigenphase at least 28, where is the spectral gap" of the transition matrix P. Therefore, applying the quan- tum phase estimation algorithm using ((1/Vō) calls to W can distinguish the state corresponding to the stationary distribution and other eigenstates. See [17, 36, 38] for more details.
2.3 Hit-and-Rum walk
Hit-and-Rrn walk was introduced by R.L. Smith [35], and has long line of reserach [1, 7, 9, 16, 26-29, 40] for its mixing time and applications in sampling, optimization, and volume estimation. Intuitively, the Hit-and-Run walk is defined follows:
1. Pick a uniformly distributed random line & through the current point x.
2. Move a random point y along the line chosen from the restricted distribution Ty.
More specifically, let f R= + R be a logconcave distribution density. Then, the distribution induced by restricting f to the line is defined as follows:
f(x)d CSCL.
(S) ((x)d
The following lemma show the transition probability of the Hit-and- -un walk. Lemma 1 ([26)). Let f be the density of logconcave distribution. If the current point of Hit-and- Run is u, then the density function of the distribution of the next point x is
2
f(x)
fa(a)
TLT J4 (u, x)) x)| ul|n-I>
where nn
nn/2 [(1+n/2] and (1(u, x)) is the f-measure of the chord through and x.
3 Quantum Algorithm for Optimizing Approximately Convex Functions
We give a polynomial quantum speedup for minimizing an approximately convex functions using the quantum walk algorithm [36, 38). More specifically, we consider the quantum walk in continuous space.² 3 Let P denote the (column) stochastic transition density of reversible Markov chain, i.e.,
(((xv)dd Va R"
and let ((x) denote the density of the stationary distribution. Then, we can implement quantum walk unitary W (P)) such that its unique eigenvector with eigenvalue 1 (or equivalently eigenphase 0) is:
(
(x)
( dr,
The difference hetween the first and the second largest eigenvalues.
It can be naturally discretized as do in simulating Markov chain classical digital computers.
5

---

where :- Jg- VP(x, (t) dy mixes all the points that can be moved from with amplitudes proportional to the transition probabilities. This quantum state can be considered as coherent encoding of the classical distribution æ. The advantage of quantum walk comes from the fact that (PP) has phase gap v8, where is the spectral gap of P. Therefore, by the quantum phase estimation algorithm [23], quantum walk can achieve quadratic speedup in general, quantum walk algorithm can quadratically speedup the hitting time of classical Markov chain. For the mixing time, requires some additional complicated constraints on the Markov chain and distributions (see e.g., [2, 13, 31, 39]). Based on previous studies quantum walk mixing, propose the following user-friendly quantum walk framework:
Theorem 3 (User-friende) friendly quantum walk framework), Let Mo be the initial Markov chain with stationary distribution To, M1 be the target Markov chain with stationary distribution TT. Suppose Mo, M1 satisfy the following properties:
Mixing time: drv To, TT) S e and d TI, TT, TO) Sc
Warmness:
x(w) / = 0(1 and | = 0(1), where ||T/O||| San o(o)
γ (x)dxx
Overlap: ( SR. (z))) = 9(11)
Furthermore, suppose have access to a unitary U that prepares the initial state (To) Jz V To (2) (z) dz. Then, we can obtain state (T1) with || [Ta) (m)) lla S using
0 ( + log (1/e))
calls the quantum walk operators.
More details and proofs are deferred to Appendix A.
Next, we can use Theorem 3 to speed-up the best-known classical algorithm for optimizing approx- imately convex functions [8], which has the following three levels:
High level: Perform simulated annealing with K stages. At the i-th stage, the target
distribution Tg. has density & (z(z) e F(z)/T, where T; == (1 - (1-11//n))
Middle level: Use samples from Ty. to construct a linear transformation E,, rounding the distribution near-isotropic position.
Low level: Run the hit-and-run walk to evolve the distribution from Tg to T.
Here, each step of the hit-and-run walk picks a uniformly random direction at the current point, and then walks on the 1-dimensional chord intersected by the direction and I. with probability density proportional to the logconcave density. We formally state the hit-and-run walk in Algorithm 3.
We focus on speeding-up the Low level using Theorem 3. Hence, we need to show that Tg. and Tga satisfy the properties therein. First of all, has been proved in [8] that / 0(1) (Lemma 11). We prove the following lemma with proof deferred to Appendix C.1.
Lemma (Informal version Lemma 12). Let Tg. be distribution with density proportional to (x(x) (xsp--F(z)/T)) where F(x) is 3-approximately convex. Then, for any 0 s K-1,
| , (8exp(23/T:+1) < 0(1).
Therefore, the warmness property is satisfied.
We also prove that the Markov chains in this annealing schedule are slowly evolving: Lemma 3 (Informal version of Lemma 13). Let qy. be distribution with density proportional to (x( = exp(- (a (T), where F(x) is 3-approximately convex. Then, for any i
K (m)))+))|| 2
1)/2)= S((1).
Hence, the overlap property is also satisfied.
With the warmness and classical analysis of the hit-and-run walk (Theorem 7), we get that the classical mixing time from Tg. to ag and vice versa can be bounded by Ō(23).

---

Moreover, we also show in Appendix C.I and Lemma 14 that each call to the quantum walk operator can be implemented by querying the evaluation oracle (1)) times.
Thus, by Theorem 3, we get the following theorem:
Theorem (Low level quantum speedup, informal version of Theorem 11), Letr E (0,1/e). Let (x(x) exp( (x)) (T.) be the density of kg. with Fx)) being 8/2-approximately convex. Let
= - (11-1/vm) Vn) for 0 S S K. Then, for each I i S K 1, given a state ( we can
produce state o (m)) such that
10! Mll S 50(),
using m Önn.. calls for the evaluation oracle of F.
In the Middle level, we need to use N independent samples from Tg. to construct linear transfor- mation Σ; for rounding. However, we cannot directly measure the state (T since it will destroy the quantum coherence. Instead,
propose non-destructive approach construct the linear transformation (the proof is deferred to Appendix C.2):
Lemma (Non-destructive rounding, informal version of Lemma 15). For each E [K], the linear transformation M; can be obtained using Õ(N) copies of the states (T._)), with query complexity Ö(N- n.W.....).... .5. Moreover, the states - will be recovered with high probability.
Now, we can put all the components together and obtain a quantum algorithm for optimizing ap- proximately convex function with 5n5 quantum query complexity (Algorithm 1). We sketch the proof below and the formal proof given Appendix C.3:
Proof sketch of Theorem 1. Observe that at each annealing stage, the sample distribution is the same the classical algorithm. Thus, by the classical analysis (Theorem 9) in [8], the same optimization guarantee still holds for the quantum algorithm. Thus, if take K v log(n/e) and N O(n). the output x, of QSIMANNEALING procedure satisfies:
F(x.) - min F(x) & O(c)
with high probability.
Then, consider the query complexity. There are K stages in the annealing process, where each stage maintains Ö(N) samples (quantum states). By Theorem 4, evolving each state takes (
queries. Therefore, the total query complexity is
K- N (V-Ö =((3).
Here, we assume that the convex body K. is known, e.g., K. = RD or S". However, even if K. is unknown, we can call its membership oralce to run our algorithm. More specifically, constructing the initial state (o),, we need to query the membership oracle for ((1) times. And since we prepare N copies, this step takes Ö(N) queries in total. Then, in each step of the quantum walk, we need to query the membership oracle for Õ(1) times determine the intersection point for the hit-and-run process. Thus, the number of queries to the membership oracle of K. is the same as the the number of evaluation oracle queries. Hence, our algorithm will query the membership oracle for (n²) times in all.
As for the number of qubits to implement our algorithm, each state (T)) uses Ö(n) qubits. Thus, Ō(n²) qubits are used to store all states. And we need (n)) ancilla qubits for the quantum walk unitaries. Therefore, our algorithm uses Ö(n²) qubits total.
Optimization approximately convex functions with decreasing fluctuations. Beyond the -nom assumption for all E K. in Eq. (1), it is also possible to give efficient algorithms for optimizing other types of approximately convex functions. Specifically, Belloni et [8, Section 7] studied approximately convex functions with decreasing fluctuations.
7

---

Algorithm Quantum speedup for approximately convex optimization (Informal version)
1: procedure QSIMANNEALING
Theorem
2: N + Ó()) K + vn log(n/e)
3: Prepare N (approximately) copies of (To). denoted |= ,..... 1=)
4: for t 1,...,K K do
5: Use (1*8"))) to nondestructively construct Σ;
Lemma
6: Apply quantum walk to evolve the states (+[ ) to (+(?))
Theorem
7: end for
8: JKK measure the final state (() K for [N]
9: return arg minje[N] F(rkk)
10:
end procedure
Suppose that the function f in (I) 1-Lipschtiz and a-strongly convex with minimum at Tmin E K:: f(x) - [[Tmin) 2 (Tm(i)))) Tmin) + 2 || - miin ||
| Xmin !|
Define a measure of "non-convexity" of w.r.t to f in an n-dimensional ball of radius r near Tmin:
((r) = sup
[xx)) f(x)]-
xEBa(Fmin.))
We can call Theorem iteratively. Suppose that at the start the thh iteration we have a ball 12 satisfying
(2 Tt-1) (2 2r.-1) C. B2 (Emin 3r,-1).
After executing Theorem in this iteration with (n²²) quantum queries, we reach point o, such that with high probability
f(xx) f( s C3A(3rr-1))
for some global constant C' >>> 0. Due to strong convexity, this gives new radius recursively:
a
a
|| Tmin 1 < A33r.-)).
2Cn ri
2On
When A(r) cr for some
0, (0,2), the iteration stops when
r* = (2 3 33"cCn/a) cCn/a)2/12-p)
and when
( = clog(1 + dr)
for some e, > the iteration stops r* satisfying
(2cCn/a) log(1 + 3dr*) = (r*)².
The total number of quantum queries is still Ö(n)).
4 Quantum Algorithm for Zeroth-Order Stochastic Convex Bandits
We first prove Corollary using quantum mean estimation with a Gaussian tail:
Proposition 1 (Adapted from [20, Theorem 4.2)). Suppose that X is a random variable on prob-
ability space (St.p) with mean p and variance o², Suppose we have unitary oracle U satisfying U} =
Szen v /p(x) (x) Then, for any A (0, 1) and T E N such that t 2 llo(l///)) ()), there is quantum algorithm that outputs mean estimate jı such that
1l (log(//))
Pr 1
< A
using O(T 212 log log(T)) queries to U.

---

Proof of Corollary 1. We follow Section 6 of [8] while use Theorem and Proposition 1. Specifi- cally, for parameter Na is a-net of K. in &oo norm. Since K. S (0, R), [aa S (R/a)".
a < let N₁ be a box grid of K. with side length a. In other words,
Note that for the sub-Gaussian random variable 6r in (2), it has variance most 4 because
/
B1lea191 Pr[lex| > v ds S 2
2 ds 40
Upon query x' E X,, define oracle 07 which returns f(x) + Ez for E No which is closest x', and the Ez here is obtained by applying Proposition with the unitary oracle Oj in Eq. (4) estimate the function value (xx) Specifically, with A exp(-12) where parameter determined later, we have
ot2
Pr
2
I exp( (xp()
We note that our algorithm based on the hit-and-run walk, with probability we not revisit the same point. As a result, 07 is no more powerful than Oy since the learner only obtains information on No., and in the rest of the proof we assume Oj, as the oracle use. We take
= c/2nnL t VnInnn(R//o-- In
Note that the value of t promises that exp( (sp(-t))R/aa"" v 0.1. In other words, with probability at least 0.9, we promise that
ot o(n (n/an)/R))))) + In
max F
(9)
Finally, we take such that the RHS of (9) equals to e/2n, which equivalent to
(n (R(RR)) + In 10) Ö(n²/e).
This will finally promise that
sup [(x)) - f(x) s max [2 + al v zEN.
(10)
aEK
2n
2n
n
meeting the condition of Theorem Consequently, with probability least 0 0.9 0.8, can
find an x² K. such that f(x") minzek f(x) S using Ö(n3) Ö(n queries to the quantum stochastic evaluation oracle (4).
Li
Proof of Theorem 2. We prove that Algorithm 2 satisfies Theorem 2.
Intuitively, we divide the rounds into m + 1 intervals where m < [log, T), such that [T] U Ti and T, := 2 1,, 2 - 1} for each E [m]] When executing in the interval Tú. the output required by the online learner always x, = 12 the at the end of the last interval. On the other hand, the queries in the current interval are applied to running the quantum stochastic convex optimization algorithm in Corollary and output a nearly-optimal solution with probability at least - O(/TT). With |T 2 queries at hand, we divide them into log(T'R) repeats of Corollary 1, each using 2 /ogg(TR) queries in the quantum algorithm. As a result, each repeat j e [log(T R)) outputs a value T2 such that
min f(x) < Ö(n log (o)(2 øeR
with probability at least 0.8. We take 22 arg minje(log (āz: With probability at least (R) OI)TRR), we have
f (azz) - min
min f(x) s Ö(n R))
(11)
Going through all i e [m + 1] intervals, by the union bound, with probability at least
- 0 log T
1 - (m + 1)
TR
TR

---

Algorithm Quantum zeroth-order stochastic convex bandits
1:
procedure QBANDITS(T)
2: m 1og2 Tj, K < (logg((T))
3: I1 1- 0
4: for i < 1,2. 1.2...,, do
5:
f t 2--1
6:
if m then
7:
I + 2
D T; = (2'-1,2(- + 1..... 22
8:
else
9:
L -- T - 2 +1
b Tm++ == 12mm 2m + 1, T
end
11:
for
j +- 1,...... K do yj 4- Q L/K)
P. Corollary with [TilKK queries
13:
for c- 0, 1...,.....11 L/K do
14:
F1++1 -2
Onliner learner's output time t
15:
end for
if ((rs) {(22) then
17:
T2i < yj
18:
end if end for
19:
end for
21:
end procedure
we have
[(x))
- min ((x) S Ö(n log(TR))22-1)
Vi E [m + 1].
(12)
zeK
In all, get that the regret bound as desired:
T
Rr = E
Σ (f(x)) - 54)
log
m+1
(n log TR
log T
<
Σ i=1
2i-1
+0
T LR
TR
2
TR
Ö( log (og(TR)) O(L
Ö( log(T) (Tg()))).
Acknowledgement
We thank anonymous referees for valuable comments. TL was supported by startup fund from Peking University. RZ was supported by the University Graduate Continuing Fellowship from UT Austin.
References
Yasin Abbasi- Yadkori, Peter Bartlett, Victor Gabillon, and Alan Malek, Hit-and-run for sampling and planning in non-convex spaces, Artificial Intelligence and Statistics, pp. 888-895, PMIR, 2017, 111.v:1610.08885.
Dorit Aharonov, Andris Ambainis. Julia Kempe, and Umesh Vazirani, Quantum walky graphs, Proceedings the thirty-third annual ACM symposium on Theory of computing, pp. 50-59, 2001, arXiv:quant-ph/001220 2090.
[3] Joran van Apeldoorn and András Gilyén, Improvements quantum SDP-solving with applications. Pro- ceedings of the 46th International Colloquium on Automata, Languages, and Programming, Leibniz In- tematiinnl Proceedings in Informatics (LIPles), vol. 132, Zentrum fuer Informatik. 2019, 80
Schloss Dagstuhl-Lerie Leibniz-
10

---

[4] Joran van Apeldoom, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-solvers: Bet- upper and lower bounds, Proceedings of the 58th Annual Symposium on Foundations of Computer Science, IEEE, 2017, arXiv:1705.011 170.01143.
[5] Joran van Apeldoom, András Gilyén, Sander Gribling, and Ronald de Wolf, Convex optimization using quantum oracles, Quantum 4 (2020), 220, wat.::18000066.
[6] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, and Joseph C. Bardin et al., Quantum supremacy using programmable superconducting processor, Nature 574 (2019), no. 7779, 505-510, arXiv:1910.1133.
[7] Claude J.P. Bélisle, H. Edwin Romeijn, and Robert L. Smith, Hit-and-run algorithmms for generating multivariate distributions, Mathematies of Operations Research 18 (1993), no. 255-266.
[8] Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, and Alexander Rakhlin, Excuping the local minima via sinulated annealing: Optimization of approximately convex functions, Conference Learn- ing Theory, pp. 240-265, PMLR, 2015, arXiv: 150.0225...
[9] H.C.P. Berbee, C.G.E. Boender, A.H.G. Rinnooy Ran, C.L. Scheffer. Robert L. Smith, and Jan Telgen, Hit-and-rum run algorithms for the identification of nonredundant linear inequalities, Mathematical Program- ming 37 (1987), no. 2, 184-207.
[10] Stephen Boyd and Lieven Vandenberghe, Convex optimization, Cambridge University Press, New York, NY, USA, 2004.
[11] Fernando G.S.L.. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu, Quantum SDP solvers: Large speed-ups, optimality, and opplications to quantum learning, Proceed- ings of the 46th International Colloquium on Automata, Languages, and Programming, Leibniz Interna- tional Proceedings in Informatics (LIPlcs), vol. 132, pp. 27:1-27:14, Schloss Dagstuhl-Leot Sariuuul--eibiiieee Leibniz-Zentrun fuer Informatik, 2019, Xiv: 1Xiv:170000258..
[12] Fernando G.S.I.. Brandão and Krysta Svore, Quanium speed-ups for semidefinite programming, Pro- ceedings of the 58th Annual Symposium on Foundations of Computer Science, pp. 415-426, 2017, axXiv1600.005537,
[13] Yu Cao, Jianfeng Lu, and Lihan Wang, On explicit LZ-convergence rate estimate for underdamped Langevin dynamics, 2019, arXiv:1908.04744.
[14] Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi
Wu, Quantum algorithm for estimating volumes of corvex bodies, 2019, arXiv: 1908.09903..
[15] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu, Quantum algorithms and lower bounds for convex optimization, Quantum 4 (2020), 221, arXiv:1809.00 009.0131..
[16] Ming-Hui Chen and Bruce Schmeiser, Performance of the Gibbs, hit-and-run, and Metropolis samplers, Journal of Computational and Graphical Statistics 2 (1993), no. 3, 251-272.
[17] Andrew M. Childs, Lecture notes on quantum algorithmss, Lecture notes at the University of Maryland, http://wwwwcs.um..ce. amchilds/qa/qa.pll 2021.
[18] Andrew Childs, Tongyang Li, Jin- -e-P Liu, Chunhao Wang, and Ruizhe Zhang, Quantum algorithms
for sampling log- concave distributions and estimating normalizing constants, 2022, manuscript.
[19] Varsha Dani, Thomas P. Hayes, and Sham M. Kakade, Structured logconcave sampling with a restricted gaussian oracle, Conference on Learning Theory, pp. 355-366, 2009.
[20] Yassine Hamoudi, Quantum Sub-Gausxian Mean Extimator, 29th Annual European Symposium on Al- gorithms, Leibniz International Proceedings in Informatics (LIPlcs), vol. 204, pp. 50:1-50:17, Schloss für Informatik, 2021, arXiv:2108.
Dagstuhl- -
[21] Aram W. Harrow and Annie Y. Wei, Adaptive quantum simulated annealing for Bayesian inference and estimating partition functions, Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Al- gorithms, pp. 193-212, 2020, arXiv: (9t.:190700996..
[22] Elad Hazan and Yuanzhi Li, An optimal algorithm for bandit convex optimization, 2016, arXiv:1603.0433:
[23] Alexei Yu Kitaev, Quantum measurements and the Abelian stabilizer problem, 1995, arXiv:quant- ph/9511024
[24] Tor Lattimore, Improved regret for zeroth-order adversarial bandit convex optimisation, Mathematical Statistics and Learning 2 (2020), no. 3, 3-134,, arXiv:2006.00475
[25] Tor Lattimore and Andras Gyorgy, Improved regret zenotlorrder stochastic convex bandits, Conference on Learning Theory, pp. 2938 2964, PMLR, 2021.
[26] László Lovás7, Hit-ond-run mixes fast, Mathematical Programming 86 (1999), no. 3, 443-461.
11

---

[27]
László Lovász and Santosh Vempala, Hil-and-run is fast and fun, 2003, Preprint, Microsoft Research, httss//www.miicrooff.oo///nne/ wwtps///seatttwwooooeeeenanaaaae
[28] László Lovász and Santosh Vempala, Hit-and- run from corner, SIAM Journal on Computing 35 (2006), no. 4, 985-1005.
[29] László Lovász and Santosh Vempala, The geometry of logconeave functions and sampling algorithms, Random Structures and Algorithms 30 (2007). no. 3. 307-358.
[30] Michael A. Nielsen and Isaac L. Chuang, Quantum computation and quanum information, Cambridge University Press, 2000.
[31] Davide Orsucci, Hans J. Briegel, and Vedran Dunjko, Faster quantum mixing for slowly evolving se- quences of markov chains, Quantum (2018), 105, arXiv:1503.013
[32] András Prékopa, Logarithmic concave measures with applications to stochastic programming. Acta Sci- entiarum Mathematicarum 32 (1971), 301-316.
[33] András Prékopa, On logarithmic concave measures and functions, Acta Scientiarum Mathematicarum 34 (1973), 335-343.
[34] Andrej Risteski and Yuanzhi Li, Algorithms and matching lower bounds for uppraximately-comvex upti- mization, Advances in Neural Information Processing Systems, vol. 29, 2016.
[35] Robert L. Smith, Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions, Operations Research 32 (1984), no. 6, 1296-1308.
[36] Mario Szegedy, Quantum speed-up of Markov chain based algorithms, 45th Annual IEEE Symposium on Foundations of Computer Science, pp- 32-41, IEFF, 2004.
[37] Zongqi Wan, Zhijie Zhang, Tongyang Jialin Zhang, and Xiaoming Sun, Quantum multi-armed bundits and stochastic linear bundits enjoy logarithmic regrets, 2022, arXiv:2205. 14988..
[38] Pawel Wocjan and Anura Abeyesinghe, Speedup via quantum sampling, Physical Review A 78 (2008). no. 4, 042336, arXiv:0804.4259.
[39] Pawel Woejan, Chen-Fu Chiang, Daniel Nagaj. and Anura Abeyesinghe, Quantum algorithm, for apprex- imating partition functions, Physical Review (2009), no. 022340, arXiv:08 11:00811.050 11.0596.
[40] Zelda B. Zabinsky. Robert L. Smith, J. Fred McDonald, Н. Edwin Romeijn, and David E. Kaufmann Improving hit-and-run for global optimization, Journal of Global Optimization (1993), no. 171-192.
[41] Chenyi Zhang, Jiaqi Leng, and Tongyang Li, Quantum algorithms for escaping from saddle points, Quan- tum 5 (2021), 529, arXiv:2007. 201022007.10253.
[42] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Bing-Cheng Chen, and Li-Chao Peng et al., Quantum com- putational advantage using photons, Science 370 (2020), no. 6523,
arXiv:2012.01625.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
12

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "sBUscvAYi6i", "reviewer": "Reviewer_RonT", "summary": "Main Contributions:\n1. The first study of Approximately convex and stochastic convex functions using Quantum Algorithms\n2. The application of these algorithms and performance bounds to bandit algorithms resulting in a logarithmic regret\n\nThe authors use a more general problem of approximately- and stochastic- convex optimisation using Quantum algorithms to then derive specific results for the Bandit Algorithm Case.", "questions": "Questions & Suggestions:\n1. What does poly(e, 1/n) mean, as there are two arguments. [Line 32]\n2. Zeroth-Order Bandit Algorithms / Oracles are a confusing terminology and a reference, footnote, or detailed explanation would be helpful.\n", "limitations": "Limitations:\n1. The claim of logarithmic bounds is only true due to an associated probability of achieving the result, hence direct comparison is not possible. A discussion of this would be helpful.\n2. How realistic is this algorithm in terms of Qubits required to run (given what problem dimension). Discussion of this would be interesting.\n\nSocietal Impact:\n1. Everything seems to have been discussed. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts:\n1. Clever use of stochastic optimisation in general leads to a direct application to Bandit algorithms yielding a logarithmic regret bound. \n\nWeaknesses:\n1. Unclear if you are proposing the first Quantum algorithm that has the Logarithmic Quantum regret bound, if so then it is very big, if not (which is more likely) then a comparison against existing methods is missing.\n2. The Theorems 2 & 3 suggest seemingly arbitrary probablity bounds 0.9 and 0.8 resp. this should have more explanation.\n3. (ideally) Theorems 2 & 3 would have a delta (representing the probability) with which the result can be found (and it will then also feature in the formula) as opposed to fixed probabilites 0.9 and 0.8.\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "k_z8r8L99ou", "reviewer": "Reviewer_r2eB", "summary": "The manuscript \"Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits\" investigates the use of quantum algorithms for the optimization of approximately convex functions. In particular, the authors describe how to achieve a polynomial quantum speedup in terms of the dimension $n$ compared to the best-known classical method by exploiting quantum walks. The framework is then adapted to give a quantum algorithm for zeroth-order stochastic convex bandits, showing a exponential speedup in the number of rounds $T$.\n", "questions": "(1) page 2, line 43: missing comma after \"technology\"\n\n(2) page 2, line 54: It is clear what is meant by \"... if we measure *this* quantum state, ...\", but the formulation is confusing.\n\n(3) page 2, lines 61-62: refer to Appendix C for details and proof\n\n(4) page 5, line 177: Why is the integration variable changed in the definition of $\\psi_x$? On page 4, line 143 and page 13, line 439, the integral is defined w.r.t. the second variable of $P$. This is also the case in [34,35].\n\n(5) page 5, line 183: \"require*s*\"\n\n(6) page 6, line 186: Why the term \"user-fiendly\"? Could you elaborate on that?\n\n(7) page 7, line 244: Instead of having two nearly identical pseudo codes, it might make sense to replace Alg. 1 by Alg. 6 without repetition in Appendix C.3.\n\n(8) page 9, line 283: $\\mathcal{O}^{stoc}_f = \\mathcal{O}^{\\tau,\\alpha}_f$ in Alg. 2, line 12?\n\n(9) page 11, lines 380-383: [35] and [36] are identical.\n\n(10) pages 13-21: Three different notations for the transition probabilities are used in the Appendix: $P(x,y)$ and $p_{x \\to y}$ on page 13 and $P_{x,y}$ on page 21. The first variant is also used in Sections 2 and 3, so it would be coherent to stick to that.\n\n(11) page 13, line 450: $D$ is not defined.\n\n(12) page 14, lines 460 and 469: The order of integration is not correct.\n\n(13) page 14, line 473: \"Theroem\"\n\n(14) page 15, lines 516-522: Is Theorem 3 the informal version of Corollary 2?\n\n(15) page 18, Alg. 5, lines 7 and 8: $\\Sigma^\\prime_i = \\Sigma^\\prime$?\n\n(16) page 21, lines 632/633: One $\\ket{x}$ too much on the right-hand side of the equation.\n\n(17) page 21, lines 637-640: A bit more detail on the last steps of the implementation of the quantum walk operator would be helpful.", "limitations": "Yes, the authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The presented work is purely theoretical. The authors start with clear statements of their contributions in form of two major theorems and address open questions. Then, the basic concepts of quantum computing, classical and quantum walks, and Hit-and-Run walks are explained in a clear and comprehensible fashion. Section 3 gives a condensed overview of the main results and their derivations. That is, a \"user-friendly\" quantum walk framework is introduced and the authors show how to apply this framework for optimizing approximately convex functions. Both parts are reconsidered and described in detail in the Appendix. This way of structuring the paper is a good idea, but leads to some repeated or redundant statements.\n\nOverall, the manuscript is well-written and all algorithms and results are described in greater detail. The work is very interesting and shows that the use of quantum walks can improve the query complexity of sampling methods. I recommend it for publication after minor revision\n\n\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OsFxlNY4WwE", "reviewer": "Reviewer_bFZB", "summary": "The paper studies the quantum algorithm for minimizing an approximately convex function. It is faster than the classical algorithm by a factor  O(n^1.5). This is achieved by implementing a quantum version of the classical algorithm which is based on simulated annealing and the hit-and-run walk. It also gives rise to a quantum algorithm for zero-th order stochastic convex bandits with an exponential speedup in time horizon.", "questions": "This paper focuses on zero-th order quantum optimization for the considered problem. I am curious about if there exists any result on first-order quantum optimization. ", "limitations": "I feel the presentation could be improved a lot so that it is more accessible to general readers. It would better if Eq. (4) can be explained more: how to understand the right-hand side which is a quantum state followed by another quantum state (there seem to be no such definitions in Section 2.1). Also,  $\\xi$ is n-dimensional but $y$ is a scalar.\n", "rating": 7, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "originality: the paper initiates the quantum version of minimizing approximately convex functions.\n\nquality: technical depth is sufficient\n\nclarity: not friendly to readers not in this area.\n\nsignificance: pure theoretical contribution", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MVE9fa1p27X", "reviewer": "Reviewer_Dqks", "summary": "This work considers the task of minimizing approximately convex functions and that of regret minimization for stochastic convex bandits. The results here using a quantum evaluation oracle offers an improvement (in T for bandits, and dimension for optimization) compared to classical models of access.\n", "questions": "Please see above. Additionally—\n\n— Can the authors comment on the number of calls made to the membership oracle for the set K? Quantum algorithms also have an advantage in this sense because separation oracles carry the same complexity as membership ones (e.g. https://arxiv.org/abs/1809.00643)\n", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "For someone unfamiliar with quantum algorithms (like me), the first disclaimer here is that these speed-ups result from the being able to query the noisy function in superposition. These are stronger models of access than classical counterparts, and can therefore overcome classical lower bounds like T^0.5 for regret. \n\nThe optimization result is easier to understand of the two. The speed-ups result from amplitude amplification (of which Grover is an example) like properties of quantum hit-and-run. The algorithmic primitives that avoid decoherence seem sound.\n\nI am concerned regarding the regret result. The minimization of approximately convex immediately yields an improvement (n^5/eps) for sample complexity of the best point with access to noisy evaluations. This is sound and this reduction is present in BLNR; here there’s an added advantage of being able to estimate the mean of a Gaussian at 1/N rate. \n\nThe paper claims a regret result. But to the best of my reading, the regret is not measured on the points the algorithm actually queries (which are quantum superpositions), but an a separate (vector) point chosen as “output”. If so, this goes against the usual definition, where exploration induces a penalty absent here. Can the authors comment on this? Failing this, I think it would be best to present this as a best-arm result (which is also what BLNR does).", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept