Quantum speedups for stochastic optimization
Authors: Aaron Sidford
Chenyi Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: continuous optimization
quantum algorithms
stochastic optimization
gradient oracle

Abstract: We consider the problem of minimizing a continuous function given given access to a natural quantum generalization of a stochastic gradient oracle. We provide two new methods for the special case of minimizing a Lipschitz convex function. Each method obtains a dimension versus accuracy trade-off which is provably unachievable classically and we prove that one method is asymptotically optimal in low-dimensional settings. Additionally, we provide quantum algorithms for computing a critical point of a smooth non-convex function at rates not known to be achievable classically. To obtain these results we build upon the quantum multivariate mean estimation result of Cornelissen et al. and provide a general quantum variance reduction technique of independent interest.

Quantum speedups for stochastic optimization
Aaron Sidford and Chenyi Zhang
{sidford, ceadford,cheniizee (aleeniz)@sttnffonn edu
Abstract
We consider the problem of minimizing a continuous function given given access natural quantum generalization of stochastic gradient oracle. We provide two new methods for the special case of minimizing a Lipschitz convex function. Each method obtains a dimension versus accuracy trade-off which is provably unachievable classically and we prove that one method is asymptotically optimal in linddimeniional settings. Additionally, we provide quantum algorithms for computing critical point of a smooth non-convex function at rates not known be achievable classically. To obtain these results we build upon the quantum multivariate mean estimation result of Cornelissen et al. [25] and provide a general quantum variance reduction technique independent interest.
Introduction
Stochastic optimization is central to modern machine learning. Stochastic gradient descent (SGD), and its many variants, are used broadly for solving challenges data science and learning theory. In theory, SGD and stochastic optimization, have been the subject of decades of extensive study. [19, 68, 27] established that SGD achieves optimal rates for minimizing Lipschitz convex functions' (even in one dimension) and stochastic optimization methods have been established for range of problems [72, 70, 73, 74]. More recently, the complexity of stochastic gradient methods for smooth non-convex optimization, c.g., critical point computation, were established [3, 29, 30, 49, 50].
Given the foundational nature of stochastic optimization and the potential promise and increased study of quantum algorithms, it is natural to ask whether quantum computation could enable improved rates for solving these problems. There has been work studying whether access to quantum counterparts of classic optimization oracle can yield faster rates for semidefinite pro- grams [13, 12, 43, 75, 76, 54], convex optimization [21, 5, 20], and non-convex optimiza- tion [23, 63, 80). Notably, [52] showed that with just access to the quantum analog of an zeroth-order oracle, i.., an oracle that when queried at a point outputs the value the function at that point, possible to simulate access to classic gradient oracle with a single query. This tool immediately yields improved rates for, c.g., convex function minimization, with a zeroth-order oracle.
Unfortunately, despite this progress and the established power of quantum evaluation oracles, ob- taining further improvements has been challenging. A line of work established a variety of striking lower bounds ruling out quantum speedups for fundamental optimization problems [31, 32, 82). For example, [31] showed that when given access to the quantum analog first-order oracle, i.e. an oracle that when queried at a point outputs the value of the function as well as the gradient at that point, quantum algorithms have no improved rates for non-smooth convex optimization over GD and SGD when the dimension is large. [82] extended this result to the non-convex setting and
We assume all abjective functions differentiable. Similar related work, see e.g., [155, results be generalized non- ci-differentiable settings since convex functions are almost everywhere differentiable and our algorithms and corresponding convergence analysis are robust to polynomially small numerical emror.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

showed that given access the quantum analog of a stochastic gradient oracle, quantum algorithms have no improved rates for finding critical points over SGD when the dimension is large.
In spite of these negative results, we nevertheless ask, for stochastic optimization are quantum- speedups obtainable? Our main result is an answer to this question in the affirmative for dimension- dependent algorithms. We provide two different quantum algorithms for stochastic convex opti- mization (SCO) which provably outperform optimal classic algorithms. Furthermore, we provide a quantum algorithm for computing the critical point of smooth non-convex function which improves upon the state-of-the th-ttherrt. We obtain these results through a new general quantum quantum-variance reduction technique built upon the quantum multivariate mean estimation result of Cornelissen al. [25] and the multilevel Monte Carlo (MLMC) technique [41, 10, 7]. We complement these results with lower bounds showing that one of them is asymptotically optimal in low-dimensional settings.
General notation. We use || || to denote the Euclidean norm and let [x(()) := fy E R lly x|| S R) and [T] := {1, (I..... 7) We use bold letters, e.g., x, y, to denote vectors and capital letters, e.g., A, B, to denote matrices. For a d-dimensional random variable X, we refer to the trace of the covariance matrix of X its variance, denoted by Var[X] For f: Rd IR, we let f == infx [(x) and call x E IR e-(sub)optimal if fxx S f e and e-critical if || [X)ii I Moreover, call a random point x E Rd expected e-(sub)optimal if [x I f + and expected c-critical if [x]][ < e. f: R2d - R is L-Lipschitz if f(x) f(y) < L||x - yll for all x, E Rd and E-smooth if [x) - f(y)) S f||x - yll for all x, E Rd. For two matrices A, B E Rdddd
A < B denotes that x" Ax S x" Bx for all x E Rd We use Ô to denote the big-O notation omitting poly-logarithmic factors in e, d, o, R. and L. When applicable, we use Igarbage(-)) to denote possible garbage states² that arise during the implementation of quantum oracle (e.g., in Definitions (1) and (2)).
1.1 Quantum stochastic optimization oracles
Here we formally define quantum stochastic optimization oracles that we study in this work.
Qubit notation. We use (.) to represent input output registers made of qubits that could be in superpesitions. In particular, given m points Xi....y Xm E Rd and coefficient vector e E C with Eie(m) |q|² = 1, the quantum register could be in the quantum state (e) = -ieg(m) % (x,). which is superposition over all these m points at the same time. If we measure this state, we will get each x; with probability |c./3. Furthermore, to model classical probability distribution p over Rd quantumly, can prepare the quantum state SxER" v Vp(x) dxx (x). If we measure this state, the measurement outcome would follow the probability density function
Quantum random variable access. We say that we have quantum access d-dimensional random variable X if we can query the following quantum sampling oracle of X that returns a quantum superposition over the probability distribution of X defined as follows.3
Definition 1 (Quantum sampling oracle). For a d-dimensional random variable X, its quantum sampling oracle Ox is defined as
Ox Ox - / Vxx(x) (x) @ |garbage(x))
where px(.) represents the probability density fincctinn of X.
The garbage state in Definition 1 is a quantum analogue of classical garbage information that arises when preparing the classical sampling oracle of X. When implementing the quantum sampling
"The garbage state is quantum analogue of classical garbage information that arises when preparing the classical stochastic gradient oracle which cannot be erased or uncomputed general. this work, we consider a general model where we make no assumption on the garbage state. See e.g., [42] for a similar discussion of this standard use of garbage quantum states.
3 'Throughout this paper, whenever we have access to quantum oracle O we assume that is unitary operation and that we also have access to its corresponding inverse operation, denoted as O-1, that satisfies 0 = 0001 I. These are standard assumption, either explicitly or implicitly, in prior work on quantum algorithms,, see e.g.. [14, 44, 25].
2

---

oracle in quantum superpositions however, this garbage information will appear in quantum state and cannot be erased or uncomputed general. In this work, we consider a general model where make no assumption on the garbage state. See e.g.. [42] for a similar discussion of this standard use of garbage quantum states.
Observe that if we directly measure the output of Ox, it will collapse classical sampling access to X that returns random vectors with respect to the probability distribution px-
Quantum stochastic gradient oracle. When considering the problem of optimizing a function f: Rd R. we often given access stochastic gradient oracle that returns a random vector from the probability distribution of the stochastic gradient.
Definition 2 (Stochastic gradient oracle (SGO)). For f: Rd + R, its stochastic gradient oracle (SGO) Cg is defined as random function that when queried at x, samples vector g(x) from probability distribution (.) over TRd that satisfies
E g(x)= Vf(x), Vx E g(X)P/,x
We say the oracle is L-bounded if
E
[g(x) L2 Vx e
g(x) x
and we say the oracle has variance o² if
E g(x)<pix
[g(x) Vf(xx]] so², Vx E
In this paper, we further assume quantum access to a stochastic gradient oracle, or access to quantum stochastic gradient oracle for brevity, that upon query returns quantum superposition over the probability distribution Pf.x (v).
Definition (Quantum stochastic gradient oracle (QSGO)). For f: Rd its quantum stochastic gradient oracle (QSGO) is defined as
Og xx) 2
10)
(x)
V (f)x(V)dv (v) @ lgarbage(v)).
VERU
where Psx(+) is as defined in Definition
Observe that if we directly measure the output of Og. will collapse to classical stochastic gradient oracle that randomly returns a stochastic gradient at x.
Another standard assumption in previous works [1, 29, 30, 50] that the stochastic gradient can be queried simultaneously, which means that the algorithm can choose the random seed w that is being queried. We assume that in such setting there Big(x.w)) = (x)).. Similarly, we define the quantum access to stochastic gradients allowing
explicit probability distribution w such that
simultaneous queries, or access to a quantum stochastic gradient oracle with simultaneous queries for brevity, that upon query returns g(x, w) in a quantum state.
Definition 4 (a- (Q-SQ-QSGO). For f: Rd I with its stochastic gradient g(x, w) indexed by ran- dom seed w that satisfies
Eg Eg(x,w) = fx() Blg(x,w) - V[(x)] 0², Vx Rd and
gg(x, w) g(y, w) < y12 Vx.y e Rd
(3)
its simultaneously queriable, o-mean-squared smooth quantum stochastic gradient oracle (a-SQ- QSGO) is defined as
2 10) xx) X w) lg(x,w)) @ |garbage(x,.))) w/))
(4)

---

1.2 Results
Here we present our main results on new quantum algorithms for stochastic optimization. Our results and the prior state-of-the-art lower bounds that we establish for quantum variance reduction and stochastic convex optimization. Our algorithmic results leverage common technique for quantum variance reduction introduced in the next Section 2. This technique uses a combination of the quantum multivariate mean estimation result of Cornelissen et al. [25] and multilevel Monte Carlo (MLMC) [41, 10, 7].
summarized in Table 1. Further, discuss quantum
Setting
Queries
Output
Method
Convex
e-optimal
SGD
Convex
8
3/2
e-optimal
Our Result (Q-AC-SA, Algorithm 2)
Convex
03/2E-1
e-optimal
Our Result (Q-SCP, Section
Non-convex
e-critical
Randomized SGD [40]
(Bounded variance)
Non-convex
d2/26-3
c-critical
Our Result (Q-SGD, Algorithm 6)
(Bounded variance)
Non-convex
e-critical
SPIDER [29]
(Mean-squared smoothness)
Non-convex
d2/2 -5/2 5/2
e-critical
Our Result (Q-SPIDER, Algorithm 7)
-Mean-squared smoothness)
Comparison between our quantum algorithms and state-of-the-art classical algorithms for Problem (the convex setting) and Problem (the non-convex setting) where, for simplicity, assume R L for Problem and f = o = 5 = 1 for Problem 2. The Ô symbol was omitted in the "Queries" column.
Table I:
Stochastic convex optimization. In this work consider the quantum analog of the standard stochastic convex optimization (SCO) problem defined as follows.
Problem 1 (Quantum stochastic convex optimization (QSCO)). the quantum stochastic corvex optimization (QSCO) problem are given query access to an L-bounded QSGO Og (see Defini- tion 3) for convex function f: Rd - R whose minimum is achieved at x* with x|x" S R and must output an expected c-optimal point.
Classically, it is known that simple stochastic gradient descent, e.g. F1+1 T, Tgt,. can solve QSCO with O²) queries. Further, this bound known to be optimal in the worst case [69, 77].
Nevertheless, develop two quantum algorithms for Problem in Section 3 and Section 4, respec- tively. The query complexities of these algorithms are summarized in the following Theorem 1. In comparison to the optimal classical query complexity of O(E 2) queries, algorithms obtain an improved dependence in terms of e at the cost of a worse dependence on the dimension, d; Theo- rem 1 shows that quadratic speedup is achievable when is constant.
Theorem 1 (Informal version of Theorem 5 and Corollary 1). Problem can be solved using expected (min (B/inn))((LR//)) d LR/et) queries.
We complement Theorem with the following lower bound on the query complexity for QSCO.
Theorem 2 (Informal version of Theorem 8), For any S Odd11/2), any quantum algorithm that solve Problem I with probability at least 2/3 makes at least (2dd1/2 queries in the worst case. For any ((d-1/2) < e S 1, any quantum algorithm that solves Problem I with success probability al least 2/3 must make at least Q(E-2 queries in the worst case.
Theorem shows that the 0(d rate that we obtain is asymptotically optimal for d 5(1) key open problem is whether the dimension dependence in either our upper bounds (Theorem and Corollary 1) or our lower bound (Theorem 8) can be improved.
Stochastic critical point computation.
We also develop quantum algorithms for finding critical points, i.c., points with small gradients, of (possibly) non-convex functions.

---

Problem 2 (Quantum stochastic critical point computation (QSCP)). In the quanium stochastic critical point computation (QSCP) problem, for an E-smooth (posssibly) non-convex f: TRd + IR
satisfying f(0) - infx fxx A we are given query access to one of the following two oracles
1. (Bounded variance setting). A QSGO Og with variance o² (see Definition 3), or
2. (Mean- (Mean-squared smoothness setting). a-SQ-QSGO O (see Definition 4),
and must output an expected e-critical point.
Leveraging [40] and [29] we develop two quantum algorithms that solve Problem 2 in the bounded variance setting and the mean--quared smoothness setting, and obtain the following result.
Theorem (Informal version of Theorem and Theorem 7). In the bounded variance setting, Prob- lem 2 can be solved using an expected Ô (Alod' (3 queries. In the mean- squared smoothness setting, Problem 2 can be solved using expected Ô (#3(do))122-557) queries.
In the bounded variance setting, Problem can be solved using O(e queries classical SGO with variance o² (Definition 2) [40], which is known to be optimal [6]. In comparison, our algorithm improves terms of and achieves a quantum speedup when d < O 2). In the mean-squared smoothness setting, Problem 2 can be solved using OE ") queries to a classical stochastic gradient oracle with variance o² that satisfies if it satisfies (3) (Definition 2) [29], which known to be optimal [6]. In comparison, our algorithm improves in terms of and achieves a quantum speedup when d < O.
Quantum zeroth-order oracles. Throughout the paper, we focus stochastic gradient oracles in correspondence with classical work on stochastic optimization. However, it is worth noting that in certain cases our results extend gracefully to quantum stochastic zeroth order oracles. For exam- ple, when the objective function exhibits a finite-sum structure and we have access each component function individually through a quantum zeroth-order oracle, we can achieve an SQ-QSGO (Defini- tion 4) with just a single query, utilizing quantum gradient estimation [52]. However, in other cases, the correspondence is less clear. For instance, if we are given a quantum stochastic zeroth-order ora- ele where the function value is obfuscated by some external noise, quantum gradient estimation [52] not directly applicable. Further study could be an interesting direction for future work.
Practicality. Regarding the utility of our algorithm in practical situations, note that our quantum oracles in Definition 3 and Definition are defined as direct, natural generalizations of the corre- sponding classical oracles. Considering such quantum generalizations of classical oracles is standard in the literature, see e.g., [21, 81]. There are standard techniques for implementing such quantum analogs of classical oracles (in theory for now given the current state-of-the-art in implementing quantum algorithms in practice). In particular, if there is a classical circuit for the classical oracle, there is standard technique obtain a quantum circuit of the same size which implement the cor- responding quantum oracle and its inverse. Hence, our quantum algorithms have the potential to surpass blackbox classical algorithms in low dimensional settings where the oracle given as an explicit circuit.
Dimension dependence. Regarding potential concerns regarding the dependence of our quantum algorithms the problem dimension, below we provide several supplementary points of context.
As discussed, in the classical setting, prior research [27] demonstrated that when opti- mizing an I-Lipschitz convex function, SGD has query complexity of O(e-2) which is optimal, even in the one-dimensional case. In the quantum setting, we showed that, theo- retically, quantum speedups which offer a different tradeoff between and dependencies are possible. Additionally, from our lower bound presented in Theorem 2 we know that some dimension dependence is inherent in obtaining an improvement.
Classically, the complexity of dimension dependent optimization methods is well studied. In particular, there are parallel and private stochastic convex settings where the dimension dependencies are discussed, see e.g.. [15, 18), and there exists works on critical point com- putation in low dimension settings, see e.g.. [22].
5

---

Even for high-dimensional problems, our algorithms can potentially be used as subrou- tines for low-dimensional subproblems. For instance, in this paper we apply these method the approximately best point problem (Problem 5), wherein we utilize our algorithm repeatedly within a one-dimensional setting.
1.3 Paper organization
In the next Section 2 we propose and develop a new algorithm for a new problem quanium variance reduction; this algorithm is the basis of our quantum speedups for stochastic optimization problems. We then discuss the application of quantum variance reduction for stochastic convex optimization by presenting two quantum algorithms in Section 3 and Section 4, respectively. Technically, it is possible obtain our result in Section just using the quantum mean estimation routine of [25] rather then quantum variance reduction, however our use of quantum variance reduction facilitates presentation. Furthermore, on quantum variance reduction in Section 5. Finally, in Section we prove quantum lower bounds for quantum variance reduction and quantum stochastic convex optimization that establish the opti- mality of our algorithms, and conclude the paper in Section 7.
present quantum algorithms for non-convex optimization based
2 Quantum variance reduction
We obtain our quantum speedups for stochastic optimization problems by proposing and developing new algorithms for new problem which we call the quantum variance reduction problem.
Problem 3 (Variance reduction). For a d-dimensional random variable X with Var[X] < L2² and some & 2 O, suppose we are given access to its quantum sampling oracle Ox defined in Definition 1.
The goal to output an unbiased estimate pa of μ E[[] satisfying Eli u1| 6².
Classically, Problem 3 can be solved by averaging O(L2 samples of X; this query complexity
optimal among classical algorithms [64]. However, if we have access to the quantum sampling oracle defined in Definition 1, [25] showed that (possibly) biased estimate j with error || -lll S & can be computed using O(L dā queries.
Lemma ([25, Theorem 3.5]). Given access to the quantum sampling oracle Ox. for any ô 2
there is a procedure quantumleannsstimatiio (X, ô. 5) that uses Ö(LV log([ (og(1/8)/á) queries and outputs an estimate ğ of the expectation μ of any d-dimensional random variable X satisfying Var [a][ < L with error || All < ā S L and success probability 1
QuantumMeanEstimtiin [25] proceeds by introducing directional mean function that reduces a multivariate mean estimation problem to a series of univariate mean estimation problem through quantum Fourier transform, which in the bounded norm case can be solved by quantum algorithms with a quadratic speedup using phase estimation. In terms of error rate, QuantumMeanEst:ine in Lemma 1 improves over any classical sub-Gaussian estimator when f. Z J However, its bias hinders its combination with various optimization algorithms assuming unbiased inputs, see e.g., [57, 2, 29, 30]. In this work we show how to carefully combine their algorithm with a classic multi-level Monte-Carke Carlo (MLMC) technique from [10. 7] to obtain an unbiased estimate f and success probability with the same rate as [25] and prove the following theorem.
Theorem 4. Algorithm solves Problem 3 using an expected ((Ld1/23-1) queries.
In the following Table 2 we provide a comparison between our result and previous works and in Section 6 we prove that our algorithm is optimal up to a poly-logarithmic factor. Notably, our algorithm does not depend on the detailed implementation of QuantumMeanEstimett its query complexity. Hence, we believe that our approach may also be useful in removing the bias of other quantum mean estimation algorithms with similar expressions of query complexities e.g., quantum phase estimation [55, 24] and quantum amplitude estimation [14].
but only
Our algorithm consists of two components. First, we show that we can obtain variant of the quan- tum mean estimation algorithm, denoted as QuantunkeenEsttinatioor (X, that outputs a low variance estimate with probability 1. This procedure compares the outcomes of the quantum esti- mator and a classical estimate, and in the event of significant disparity, generates a new independent classical estimate.

---

Queries
Bias
Variance
Method
6-2
6²
Classical Variance Reduction
12120-1
6²
Quantum Multivariate Mean estimation [25]
log" 2 (1/2)
7
g²
One-dimensional Quantum Mean estimation [24]
d1/20-1
6²
Our Result (Theorem 4)
Table 2: Comparison between different methods for variance reduction case of and ē E (0, 1).
The O symbol was omitted in the "Queries" column.
Second, we use the MLMC technique [41], specifically a variant of the methods described in [10, 7]. carefully invoke the biased subroutine muantummeanEstimattin estimate. The algorithm, Algorithm I, simply invokes QuantumMeanEstimat:: domly chosen accuracies and combines them obtain the result. Though there number of possible accuuracies chosen, we show that the expectation, the variance, and expected number of queries are all suitable prove Theorem 4, whose proof is deferred to Appendix B.
and compute the unbiased for three ran- infinite
Algorithm 1: Quantum variance reduction
Input: Random variable X, target variance 82
Output: An unbiased estimate j of [X[]] with variance at most 8²
Set াág in on o/10)
2 Randomly sample j ~ Geom E N
Jı - (X, 27,2-3///8/1))
Ai-1 - (X,2 (
j f No+ 22 (i: P)-1)
return j
3 Quantum accelerated stochastic approximation
In this section, we present our e(d5/8 -3/2) query quantum algorithm for Problem 1. Our approach builds upon the framework proposed by Duchi et al. [28, 15], which involves performing Gaussian convolution on the objective function ff and then optimizing the resulting smooth convoluted func- tion. Compared to their algorithm, our algorithm differs by replacing the variance reduction step by our quantum variance reduction technique (Algorithm 1).
As with variety of prior work on parallel and private SCO [28, 33, 15], we consider the smooth function F, that is the Gaussian convolution of the objective function f:
/ (x(x))(x->))))
| 2r
(x
where 7r. (y)
(V2rr) exp
(5)
As shown in Lemma when the radius of the convolution is sufficiently small, F, closely approx- imates ff pointwise. Consequently, to find an e-optimal point of f it suffices to find an e/ 4-otimalll point of F, for r 4vār. Moreover, Lemma shows that the stochastic gradient gr of F, can be defined and obtained based on the stochastic gradient g of f as follows:
gx(x) g(x y),
y Tr.
(6)
which satisfies
gg -FF and [[gr(x)] S L, Vx.
your
Hence,
[VF(()) S. [[gr(x)]ldy & L
indicating that F, is also L-Lipschitz.

---

To optimize this smooth convex function F,, leverage the accelerated stochastic approximation (AC-SA) algorithm introduced in [57], which applys an accelerated proximal descent method on the objective function using unbiased estimates of gradients. Our algorithm given Algorithm 2 is specialization of the AC-SA algorithm,, where we implement those unbiased estimates of gradients using quantum variance reduction (Algorithm 1). In the classical setting, one query to the stochastic gradient gr (x(x) of I' can be implemented by a random sampling a vector E IR from the Gaussian "y followed by a query to the SGO Cg (Definition 2) at x y. Similarly, we can show that one query to QSGO of F, (Definition 3) can also be implemented by one query to the QSGO of f. The subsequent theorem presents the query complexity of Algorithm 2.
Algorithm 2: Quantum accelerated stochastic approximation (Q-AC-SA)
Input: Function f: Rd >> IR, precision c
Domain Size R, total iteration budget T 4d L. target variance
Parameters:
σ g//s
convolution radius r AvdL 7 (T+2)/25
t
RyGEE
R
Output: an e-optimal point of F
Denote Fx(x) == %x()) y)dy as in (5)
2 Set X f 0, x1 x-
for i
Se + t+1
2, + 2
111
x,ndd + xx'x,+
3, xx2""
Call Algorithm for unbiased estimate g. of (x((dd with variance most 82
X++1 arg min t (gr, - x(rd) L||xx] -z|l²/(rr)
x B X,41 (1 (1-3, x2
return X1+1
Theorem (Formal version of Theorem 1, Part 1), Algorithm solves Problem I using an expected
((R//(LR/)))) queries.
The proof of Theorem 5 is deferred to Appendix C.
4 Quantum stochastic cutting plane method (Q-SCP)
In this section, we develop our ((d/2LR)(() query algorithm for Problem which is based on a stochastic version of the cutting plane method. We introduce the key properties and related concepts of cutting plane methods, and then provide a procedure for efficiently post-processing the outcomes obtained from the stochastic cutting plane method using quantum variance reduction (Algorithm I). Then, we analyze the overall query complexity for solving Problem 1. Technically, it is possible to obtain the results of this section using the quantum mean estimation routine of [25], rather then quantum variance reduction, however using quantum variance reduction facilitates our presentation.
We begin by introducing some notation and concepts on cutting plane methods. Cutting plane methods solve the feasibility problem defined as follows. Note that this problem is slightly easier to solve then the in, e.g., [48], however is simple suffices for our purposes.
Problem 4 (Feasibility Problem). We are given query access to a separation oracle for a set K C Rdd such that on query E Rd the oracle outputs vector с and either c = O, in which case x E K, or e + O, in which case H == {z:
S c xxx K. The goal is to query a point x E K.
[48] showed that Problem 4 can be solved by cutting plane method using O(dlog(dR/r)) queries to separation oracle where R and r denote bounds on K.
Lemma 2 ([48, Theorem 1.1]). There is culting plane method which solves Problem 4 using at most C log(dR/r) /r) queries for some constant C, given that the set K is contained in the ball of radius R centered at the origin and it contains a ball of radius
8

---

167, 58] demonstrated that, running cutting plane method a convex function with the separation oracle being its gradient yields a sequence of points where at least one of them is an 6-optimal point of f. This follows from the fact that there exists ball of radius (e) around such that every point in this ball is e-optimal. In the stochastic setting, although we cannot access the precise gradient, we show that it suffices to use an Appendix D.I) as the separation oracle. Specifically, we prove the following result.
gradient oracle of f (formally defined in
Proposition 1. For any 0 I S LR, with success probability least 5/6 we obtain T = Ol Log(dLR/e) points X1....,XT E OO) such that one of the I; is e-optimal using δ (dd/2LR/c) queries to the QSGO Og defined in Definition 3.
The proof of Proposition 1 is deferred to Appendix D.1. After applying Proposition 1, it is not clear which query x; an (cc)ommi point. This difficulty arises because we lack access to the function value of f. which sets problem apart from the feasibility problem discussed in [48], where there a clear indication when a query successfully lies within the feasible region. Consequently, we next focus on identifying the optimal solution within the finite set I' of points using access to the QSGO. We conceptualize this task as the approximately best point problem, formulated as follows.
Problem 5 (Approximately best point). For a L-Lipschitz convex function f: R - IR and points Xy E B (.) find a convex combination X E Rdd of the points satisfying
f(x) < min f(x:) t
TET
In this work, we develop an algorithm that solves Problem by making pairwise comparisons in hierarchical order, where each pairwise comparison is computed by running binary search on the segment along the segment between the two points. Formally, we prove the following result.
Proposition 2. For any accuracy parameter e > O, with success probability at least 5/6 Algorithm 5 solves Problem 5 using Ô (RLT/e /e) queries to an L-bounded QSGO Og defined in Definition 3.
The proof of Proposition 2 and the corresponding quantum algorithm can be found in Appendix D.2. Next, we present the main result of this section, which describes the query complexity of solving Problem I using quantum stochastic cutting plane method.
Corollary (Formal version of Theorem 1, Part 2). With success probabiiity at least 2/3, Problem can be solved using an expected Ö (R/6) queries.
The proof of Corollary is deferred to Appendix D.3.
Quantum stochastic non-convex optimization
In this section, we present our quantum algorithms for Problem 2 in the bounded-varianee setting and the sqean-s smoothness setting, respectively, using our quantum variance reduction technique.
To solve Problem 2 in the bounded variance setting, we leverage the randomized SGD method in- troduced in [40], which is a variant of SGD where the number of iterations is randomized. Our algorithm is specialization of the randomized stochastic gradient algorithm, where we replace the classical variance reduction step by quantum variance reduction (Algorithm 1). The query complex- ity of our quantum algorithm is given in the following theorem.
Theorem 6 (Formal version of Theorem 3, bounded variance setting). For any > 0, Algorithm 6 solves Problem 2 in the bounded variance setting using an expected ( dde queries.
The proof of Theorem 6 and the corresponding quantum algorithm can be found in Appendix E.
To solve Problem in the mean-squared smoothness setting, we leverage the SPIDER algorithm introduced in [29], which is variance reduction technique that allows to estimate the gradient of a function with lower cost by utilizing the smoothness structure and reuse the stochastic gradient samples at nearby points. Our algorithm is specialization of the SPIDER algorithm, where replace the classical variance reduction step by quantum variance reduction (Algorithm 1). The query complexity of our quantum algorithm is given in the following theorem.
Theorem 7 (Formal version of Theorem 3, mean-squared smoothness setting). For any 0 S < Algorithm 7 solves Problem 2 in the mean-squared smoothness setting using expected δ (AV number of queries.

---

The proof of Theorem 7 and the corresponding quantum algorithm be found in Appendix F.
Lower bounds
In this section we present two quantum lower bounds for solving quantum variance reduction (Prob-
lem 3) and stochastic convex optimization (Problem 1), respectively.
We first establish the following quantum lower bound for the variance reduction problem (Prob- lem 3) which shows that our Algorithm
optimal up to a poly-logarithmic factor when â O (d-1/2) By Markov's inequality, Proposition equivalently states that any quantum algorithm that solves Problem 3 must make an expected ((Lydàā-) queries. This matches our algorithmic result provided in Theorem up to moly-logarithmic factor.
Proposition 3. There is constant such that for any â avdd any quantum algorithm that solves Problem 3 with success probability at least 2/ast2/3 must make at least ((LL queries in the worst case.
The proof of Proposition 3 is deferred Appendix G.1
Next, we establish the following quantum lower bounds for stochastic convex optimization (Prob- lem 1) in the low-dimension regime and the high-dimension regime, respectively, which show that our quantum stochastic cutting plane method in Section is optimal up to a loly-logarithmic factor when the dimension d is constant, and there is no quantum speedup over SGD when d > Ω (e 9)-
Theorem 8. For any E S 100Vd' any quantum algorithm that solves Problem with success proba- RL S E S 1, bility at least 2/3 must make at least 12( ((VVRL/fe) queries in the worst case. For any 100Vd any quantum algorithm that solves Problem I with success probability least 2/3 must make at least (2 (2((²) queries in the worst case.
RL
The proof of Theorem 8 deferred to Appendix G.2.
Conclusion
We presented improved quantum algorithms for stochastic optimization. We developed nical tool which we call quantum variance reduction and show how to use it to improve upon the query complexity for stochastic convex optimization and for critical point computation in smooth, stochastic, non-convex functions. Further, we provided lower bounds which establish both the opti- mality of our quantum variance reduction technique and of one of our stochastic convex optimiza- tion algorithms in low dimensions. A natural open problem suggested by our work is to establish the optimal complexity of the problems we study, e.g., stochastic convex optimization and stochas- tic non-convex optimization with quantum oracle access, in higher dimensions. We hope this paper fuels further study of these problems.
tech-
Acknowledgement
We thank Adam Bouland, Yair Carmon, András Gilyén, Yujia Jin, and Tongyang Li for helpful discussions. A.S. was supported in part by a Microsoft Research Faculty Fellowship, NSF CAREER Award CCF-1844855, NSF Grant CCF-1955039 Fellowship. C.Z. was supported in part by the Shoucheng Zhang Graduate Fellowship.
PayPal research award, and Sloan Research
References
[1] Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma, Finding approximate local minima faster than gradient descent, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory Computing, pp. 1195-1199, 2017,
1.111111116666
[2] Zeyuan Allen-Zhu, Katyusha: The first direct acceleration of stochastic gradient methods, The Journal of Machine Learning Research 18 (2017), no. 1, 81948198899 8244, arXiv: 1 603.05553..
10

---

[3] Zeyuan Allen-Zhu and Yuanzhi Li, Neon2: Finding local minima via first-order oracles, Ad- vances in Neural Information Processing Systems, pp. 3716-3726, 2018, arXiv: 1tt::17111000 111111611.6.... 1.06673.
[4] Dong An, Noah Linden, Jin-Peng Liu, Ashley Montanaro, Changpeng Shao, and Jiasu Wang. Quantunn-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance, Quantum (2021), 481, arXiv:2012.06282
[5] Joran van Apeldoom. András Gilyén, Sander Gribling, and Ronald de Wolf, Convex optimiza- tion using quantum oracles, Quantum 4 (2020), 220, arXiv: 00643...
[6] Yossi Arjevani. Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth, Lower bounds for non-convex stochastic optimization, Mathematical Program- ming (2022), 1-50, arXiv:1912.022: 1912.0266..
[7] Hilal Asi, Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford, Stochastic bias- reduced gradient methods, Advances in Neural Information Processing Systems 34 (2021), 108 10810-10822, arXiv:2106.09453
[8] Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Global optimality of local search for low rank matrix recovery, Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 3880-3888, 2016, arXiv:1605.0722..
[9] Ernesto G. Birgin, J. L. Gardenghi, José Mario Martínez, Sandra Augusta Santos, and Ph. L. Toint, Worst-case evaluation complexity for unconstrained nonlinear optimization using high- order regularized models, Mathematical Programming 163 (2017), 359-368.
[10] Jose H. Blanchet and Peter W. Glynn, Unbiased Monte Carlo for optimization and functions of expectations via multi-level randomization, 2015 Winter Simulation Conference (WSC),
pp. 3656-3667, IEEE, 2015.
[11] Stephen Boyd and Almir Mutapeic, Stochastic subgradient methods, Lecture Notes for BE364b, Stanford University (2008), 97.
[12] 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 applications to quantum learning, Proceedings of the 46th International Colloquium
Automata, Languages, and Programming, Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 27:1- 27:14, Schloss Dagstuhl--LebbiizZZaee
fuer Informatik, 2019, arXiv:1710.0255
[13] Fernando G.S.L. Brandão and Krysta M. Svore, Quantumn speed-uy ups for solving semidefinite programs, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 415-426, IEEE, 2017, 1609.05537.
[14] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplifica- tion and estimation, Contemporary Mathematics 305 (2002), 53-74, urXiv:quant-ph/000005..
[15] Sébastien Bubeck, Qijia Jiang, Yin-Tat Lee, Yuanzhi Li, and Aaron Sidford, Complexity of highly parallel non-smooth convex optimization, Advances in neural information processing systems 32 (2019), 1t..v:.996..06660
[16] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford, "Convex until proven guilty": : Dimension-fres free acceleration of gradient descent on non-convex functions, International con- ference on machine learning, pp. 654-663, PMLR, 2017, arXiv:1705.02766
[17] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford, Accelerated methods for nonconvex optimization, SIAM Journal Optimization 28 (2018), no. 1751-1772,
arXiv:1611 1.00766.......
[18] Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, and Kevin Tian, ReSQueing parallel and private stochastic convex optimization, 2023, arXiv:2301.0044
[19] Nicolo Cesa- Bianchi, Alex Conconi. and Claudio Gentile, On the generalization ability of on- line learning algorithms, IEEE Transactions on Information Theory 50 (2004), no. 9, 2050- 2057.
[20] Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu, Quantum algorithm for estimating volumes of convex bodies, ACM Transac- tions on Quantum Computing 4 (2023), no. 3, 1-60,
[21] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu, Quantum algo- rithms and lower bounds for convex optimization, Quantum 4 (2020), 221, arXiv: 1800.0173.
11

---

[22] Sinho Chewi, Sébastien Bubeck, and Adil Salim, On the complexity of finding stationary points of smooth functions in one dimension, International Conference on Algorithmic Learning The- ory, pp. 358-374, PMLR, 2023, arXiv.arXiv:22000755..
[23] Andrew M. Childs, Jiaqi Leng. Tongyang Li, Jin-Peng Liu, and Chenyi Zhang. Quantum sim- ulation of real-space dynamics, Quantum (2022), 680, arXiv:2203. 1706..
[24] Arjan Cornelissen and Yassine Hamoudi, A sublinear-time quantum algorithm for approximat- ing partition functions, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1245-1264, SIAM, 2023, arXiv:2207 .06643...
[25] Arjan Cornelissen, Yassine Hamoudi, and Sofiene Jerbi, Near-optimal quantum algorithms for multivariate mean estimation, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 33-43, 2022, arXiv:21 11100997777
[26] Aaron Defazio, Francis Bach, and Simon Lacoste-Julien, Saga: A fast incremental gradient method with support for non-strongly convex composite objectives, Advances in neural infor- mation processing systems 27 (2014).
[27] John C Duchi, Introductory lectures on stochastic optimization, The mathematics of data 25 (2018), 99-186.
[28] John C. Duchi, Peter L.. Bartlett, and Martin J. Wainwright, Randomized smoothing for stochas- tic optimization, SIAM Journal on Optimization 22 (2012), no. 2, 674-701.
[29] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang, SPIDER: Near-optimal non- convex optimization via stochastic intteiinteerted differential estimator, Advances Neural Information Processing Systems 31 (2018), arXiv: 016..
[30] Cong Fang, Zhouchen Lin, and Tong Zhang. Sharp analysis for nonconvex SGD escaping from saddle points, Conference on Learning Theory, pp. 1192-1234, 2019, arXiv: 1XXX:19922.00277
[31] Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif, No quantum speedup over gradient descent for non-smooth convex optimization, 2020, arXiv:2010.01801.
[32] 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 Process- ing Systems 34 (2021), 29874 29884,
12::01112.111..
[33] A. V. Gasnikov, E. A. Gorbunov, D. A. Kovalev, A. A. Mohammed, E. O. Chernousova, et al., The global rate of convergence for optimal tensor methods in smooth convex optimization, Computer research and modeling 10 (2018), no. 6, 737-753, arXiv:1809.00382
[34] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan, Escaping from saddle points on- line stochastic gradient for tensor decomposition, Proceedings of the 28th Conference on Learning Theory, Proceedings of Machine Learning Research, vol. 40, pp. 797-842, 2015, arXiv:1503.0211
[35] Rong Ge, Chi Jin, and Yi Zheng, No spurious local minima in nonconvex low rank problems: A unified geometric analysis, International Conference on Machine Learning, pp. 1233-1242, PMLR, 2017, arXiv: 1iti::10044: 704.00708.
[36] Rong Ge, Jason D. Lee, and Tengyu Ma, Matrix completion has no spurious local minimum, Advances in Neural Information Processing Systems, pp. 2981-2989, 2016, arXiv:1605.07272.
[37] Rong Ge, Jason D. Lee, and Tengyu Ma, Learning one-hidden-layer neural networks with landscape design, International Conference on Learning Representations, 2018,
arXiv:1711.00501.
[38] Rong Ge, Zhize Li, Weiyao Wang, and Xiang Wang, Stabilized SVRG: Simple variance re- duction for nonconvex optimizution, Conference on Learning Theory, pp. 1394-1448, PMLR, 2019, 10XXiv1905.00522.
[39] Rong Ge and Tengyu Ma, On the optimization landscape of tensor decompositions, Advances in Neural Information Processing Systems, pp. 3656-3666, Curran Associates Inc., 2017, 1rXiiv1176.000
[40] Saeed Ghadimi and Guanghui Lan, Stochastic first-and zeroth-order methods for nonconvex stochastic programming, SIAM Journal on Optimization 23 (2013), no. 4, 2341-2368.
12

---

[41] Michael B. Giles, Multilevel Monte Carlo methods, Acta Numerica 24 (2015), 259-328.
[42] András Gilyén and Tongyang Li, Distributional property testing in a quantum world, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2020, 1.X.:v1902.001144
[43] Weiyuan Gong, Chenyi Zhang, and Tongyang Li, Robustness of quantum algorithms for non- convex optimization, 2022, arXiv:2212.02544
[44] Yassine Hamoudi, Quantum sub-Gaussian mean estimator, 29th Annual European Sympo- sium on Algorithms (ESA 2021), Schloss Pagstuhl-Leibniz-zenttee für Informatik, 2021,
121172 12172.
[45] Yassine Hamoudi and Frédéric Magniez, Quantum Chebyshev's inequality and applications, 46th International Colloquium Automata, Languages, and Programming (ICALP 2019), 2019, (.XXiv1807.064555
[46] Moritz Hardt, Tengyu Ma. and Benjamin Recht, Gradient descent learns linear dynamical systems, Journal of Machine Learning Research 19 (2018), no. 29, 1-44, arXiv:1609.05191
[47] Trevor Hastie, Robert Tibshirani, Jerome H. Friedman, and Jerome H. Friedman, The elements of statistical learning: Data mining, inference, and prediction, vol. 2, Springer, 2009.
[48] Haotian Jiang. Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong, An improved cutting plane method for convex optimization, convex-concave games, and its applications, Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, pp. 944-953, 2020, Niti:2000.042540
[49] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael I. Jordan, How to escape saddle points efficiently. Proceedings of the 34th International Conference on Machine Learning, vol. 70, pp. 1724-1732, 2017, arXiv: 10o:17033000 703.00887.
[50] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I. Jordan, On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points, Journal of the ACM (JACM) 68 (2021), no. 2, 1-29, arXiv:1902.04811
[51] Rie Johnson and Tong Zhang, Accelerating stochastic gradient descent using predictive vari- ance reduction, Advances in neural information processing systems 26 (2013).
[52] Stephen P. Jordan, Fast quantum algorithm for numerical gradient estimation, Physical Review Letters 95 (2005), no. 5, 050501, utXiv:quant--h//W ph/0405146 146.
[53] Jonathan Kelner, Jerry Li. Allen X. Liu, Aaron Sidford, and Kevin Tian, Semi-random sparse recovery in hearly-linear time, The Thirty Sixth Annual Conference on Learning Theory, pp. 2352-2398, PMLR, 2023, 2xXiv:2203.0400
[54] Iordanis Kerenidis and Anupam Prakash, A quantum interior point method for LPs and SDPs, 2018, ww..iv11808.99101
[55] A. Yu. Kitaev, Quantum measurements and the Abelian stabilizer problem, (1995), arXiv:quant-ph/9511 1026.
[56) Robin Kothari and Ryan O'Donnell, Mean estimation when you have the source code; or, quantum Monte Carlo methods, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1 1186-1215, SIAM, 2023, wrXiv:2208.07544
[57] Guanghui Lan, An optimal method for stochastic composite optimization, Mathematical Pro- gramming 133 (2012), 1-2, 365-397.
[58] Yin Tat Lee, Aaron Sidford, and Sam Chiu-war wai Wong, A faster cutting plane method and its implications for combinatorial and convex optimization, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 1049-1065, IEEE, 2015, arXiv:1508.044 048804
[59] Tongyang Li and Xiaodi Wu, Quantum query complexity of entropy estimation, IEEE Trans- actions on Information Theory 65 (2018), no. 5, 2899-2921 arXiv:1710.06025.
[60] Xiantao Li, Enabling quantum speedup of markov chains using multi-level approach, 2022.
[61] Zhize Li, SSRGD: Simple stochastic recursive gradient descent for escaping saddle points, Ad- vances in Neural Information Processing Systems 32 (2019), 1523-1533, arXiv: 1904009265
13

---

[62] Mingrui Liu, Zhe Li, Xiaoyu Wang, Jinfeng Yi, and Tianbao Yang. Adaptive negalive curva- ture descent with applications non-convex optimization, Advances in Neural Information Processing Systems 31 (2018), 4858-4867.
[63] Yizhou Liu, Weijie J. Su, and Tongyang Li, On quantum speedups for nonconvex optimization via quantum tunneling walks, Quantum 7 (2023), 1030, arXiv:2209.144: 14500.
[64] Gábor Lugosi and Shahar Mendelson, Mean estimation and regression under heavy-tailed distributions: A survey, Foundations Computational Mathematics 19 (2019), no. 5, 1145- 1190.
[65] Ashley Montanaro, Quantum speedup of Monte Carlo methods, Proceedings of the Royal So- ciety A 471 (2015), no. 2181, 20150301,
[66] Katta G. Murty and Santosh N. Kabadi, Some NP-complete problems in quadratic and nonlin- ear programminng Mathematical Programming: Series A and B 39 (1987). no. 2, 117-129.
[67] Arkadi Nemirovski, Efficient methods in convex programming. Lecture notes (1994).
[68] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro, Robust stochas- tic approximation approach to stochastic programming, SIAM Journal on optimization 19 (2009), no. 4, 1574-1609.
[69] Arkadij Semenovive Nemirovskij and David Borisovich Yudin, Problem complexity and method efficiency in optimization, 1983.
[70] Yurii Nesterov, Introductory lectures on convex optimization: basic course, vol. 87, Springer Science & Business Media, 2003.
[71] Yurii Nesterov and Boris T. Polyak, Cubic regularization of Newton method and its global performance, Mathematical Programming 108 (2006), no. 177-205.
[72] Boris T. Polyak, Introduction to optimization. Optimization software, Inc., Publications Divi- sion, New York 1 (1987), 32.
[73] Shai Shalev-Shwarde Online learning: Theory, algorithms, and applications, Hebrew Univer- sity, 2007.
[74] Shai Shalev-Shwart and Shai Ben-David, Understanding machine learning: From theory to algorithms, Cambridge university press, 2014.
[75] Joran van Apeldoom and András Gilyén, Improvements quantum SDP-solving with appli- cations, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Schloss Dagstuhl-Leibniz: Zentruu fuer Informatik, 2019, 180405555..
[76] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf, Quantum SDP- solvers: Better upper and lower bounds, Quantum 4 (2020), 230, 1705.01843.
[77] Blake Woodworth and Nathan Srebro, Lower bound for randomized first order convex opti- mization, 2017, arviv: 1 7709003594.
[78] Yi Xu, Rong Jin, and Tianbao Yang, NEON+: Accelerated gradient methods for extracting negative curvature for non-convex optimization, 2017, arXiv:1712.01033.
[79] Yaodong Yu, Pan Xu, and Quanquan Gu, Third-order smoothness helps: Faster stochastic
optimization algorithms for finding local minima, Advances in Neural Information Processing Systems (2018), 4530-4540
[80] Chenyi Zhang, Jiaqi Leng, and Tongyang Li, Quantum algorithms for escaping from saddle points, Quantum 5 (2021), 529, arXiv:2007.10253.
[81] Chenyi Zhang and Tongyang Li, Escape saddle points by simple gradient-descent based algorithm, Advances in Neural Information Processing Systems 34 (2021), 8545-8556, arXiv:2111.14069.
[82] Chenyi Zhang and Tongyang Li, Quantum lower bounds for finding stationary points of non- convex functions, 2022. arXiv:2212.03990
[83] Xiao Zhang, Lingxiao Wang, Yaodong Yu, and Quanquan Gu, A primul-dual analysis of global optimality nonconvex low-rank matrix recovery, International Conference on Ma- chine Learning, pp. 5862-5871, PMLR, 2018
14

---

[84] Dongruo Zhou, Pan Xu, and Quanquan Gu, Stochastic variance-reduced cubic regularized Newton methods, International Conference on Machine Learning, pp. 5990-5999, PMLR, 2018, arXiv:1802.04796.
[85] Dongruo Zhou, Pan Xu, and Quanquan Gu, Stochastic nested variance reduction for non- convex optimization, Journal of Machine Learning Research 21 (2020), no. 103, 1-63, arXiv:180.00781..
15

---

A Additional related work
Stochastic convex optimization. Stochastic convex optimization is a broad, well-studied area of research. Beyond the works mentioned in the introduction, for additional references and discussion of research in the area, see [11, 47, 68] for detailed overviews of stochastic convex optimization methods and [19] for a presentation of convex optimization in the online learning setting. Addition- ally, see [26, 51] for a discussion of the closely related problem of finite-sum optimization.
Non-convex optimization. Non-convex optimization is rapidly advancing research area in op- timization theory. These advances are motivated in part by the fact that the landscapes of various modern machine learning problems are typically non-convex, including deep neural networks, prin- cipal component analysis, tensor decomposition, etc. In general, finding a global optimum of a non-convex function is NP-hard [66, 69]. Hence, many theoretical works instead focus finding local minima rather than a global one, given existing empirical and theoretical evidence that local minima can be as good as global minima in certain machine learning problems [8, 34, 36, 37, 39, 46]. The first step of finding local minima would be to find stationary points, which has been discussed in many previous works [1, 9, 17, 16, 70, 71J. An important line of work focuses on first-order, (stochastic) gradient- based algorithms for finding critical points and local minima since higher-order derivatives are often not accessible in practical scenarios [3, 17, 29, 30, 34, 49, 50, 62, 78, 81]. There are also results on non-convex optimization that study different settings [38, 61, 79, 85, 35, 83, 84].
Quantum Monte Carlo methods. Since [65], quantum Monte Carlo methods have been broadly investigated. In particular, [59] discussed quantum Monte-Carlo methods for entropy estimation, and [45] initiated the study of quantum mean estimation problem with multiplicative error, which followed by [44, 25, 24, 56]. Multilevel Monte Carlo methods are also widely used in quantum algorithms, see e.g., [4, 60]. Specifically, the particular multilevel Monte Carlo strategies we use for quantum variance reduction have roots in the classic computation work of [10, 7].
B Proof of Theorem 4
Algorithm 3: QuanttumMeanESstinnatiinn O)
Input: Random variable X, target variance à² S r,2
Parameters: 5 = == D = &
+
1
0
Output: An estimate P of μ [[X] satisfying El - 2 0²
<
Set X1 --uuantumMenEEttinne (nX, 6/4, 6)
on
2 Randomly draw one classical sample X2 of X
||x; X2ll < D then return X3
4 else
Randomly draw one classical sample X3 of X
return X3
We begin by presenting a lemma showing how two unbiased, bounded variance random variables (X₂ and X3 in the lemma) can be used to control the expected l error random variable (X1 in the lemma) that is close to the expectation of Xe and X, with some probability. In Algorithm 3 X1 corresponds to the output of QuantumMeanEst imation and then X2 and X3 are obtained by classic sampling.
Lemma 3. Let X1, X3 Ied be independent random variables where EX2 EX2 14, Var [x]] & L2, and Var & I2, and [| lill < with probability at least 1 Further, let Z be the random variable that is X1 [| X² D and X3 otherwise where D > ô. Then,
I 02)
E Z
1ll
< 0² + L
+ + +3LP)
D D-
Consequently, E|Z 1dl? < 2 when D = r + 1/202 and 8 < 80 60/LO.
16

---

Proof. Let S denote the event that || 1ll2 S ā and let 7 denote the event that || X2ll2 S D. Then by the law of total expectation
Z pl1 Pr [S] 1|
pl12 s
+ Pr [not S)
1 1ll2 not
2 ml1 |
+ 8.
| - -11l not s)
Where we used that Pr[S] - 1 and Pr[not S] s 8. We will prove the lemma by leveraging this inequality and upper bounding both E
|
م 2 S
and E || - mll2 not S
First, we upper bound Z we have that
[z 1012 S
Again by the law of total expectation and the definition of
E 11 1112 |||
Pr [T]
S]
Iz 1112 T and s
+ Pr not T S || 1l12 T and not S)
Pr 6) + Pr |not | 1.
(8)
Here we use that if T and S both hold then Z = X1 and || 1ul| < ā and that if S holds and not then Z X3 and X3 is independent of S and with variance I Now, if [| pllp D à then when S holds by triangle inequality
|X X2ll < |X ulll + |X اll D.
Applying this bound and Chebyshev inequality to X2 (and using that X2 is independent of 5) we have that
L
Pr[T S) 2 Pr[lIX2 - 14l12 S D - à =
- 1ll2 DD - o)
D-
Since ā < L,, combined with (7) this implies that
E 1| 11/ s}
L
82
13
82 +
-2
D
D
D -
Next, we upper bound EP
17 - -1112 not S)
Note that if T holds then
|| μ| < 2 X2l1 2|| A11 s 2D 21| - nll?
Since = Xg if T does note hold, we then see that in either case
2 1| s 2D2 2|| - /a|l + ||x3 n1l2
Since, X2 and X3 are independent of S with variance L this therefore implies that
E 1z
1 2 not s]
2D 21| m11 + || x1] 2D2 + 3L2,
which leads to
E Z - 21 < || 2 | +8.E |1 - |111 not s)
T?2 Ø2
< 6 + L
D - + +8(2D2 +3L2).
Corollary 2. Given access to the quantum sampling oracle Ox of a d-dimensional random variable X, for any ā, 2 O, the procedure QuantunkeanEstimatiie (X,ō) (Algorithm 3)
uses (( dō -1 queries and outputs an estimate j of the expectation EllA p 82.
[[ satisfying
*At Line 2 and Line 5 of Algorithm 3, we can further retine our approach to obtain X₂ and X. by taking the same number of classical samples as we would have used in the QuantumMeants umMeanEse reduce the loga-togaii factor in the overall query complexity.
immation procedure, which
17

---

Proof. By Lemma the output of QuantumlWeaFaatmmattonn (X,ō) (Algorithm 3) satisfies
Elli ull² o².
As for the number of queries to Ox, note that it uses
( δ I LVdlog(1/6) = δ Lvd log
1 66
δ Lvd
queries to prepare X1. Moreover, we can prepare the classical samples X2 and X3 by measuring the quantum state Ox [0) in the computational basis, which takes query Ox. Hence, the overall query complexity equals (LLVda
Equipped with Corollary 2, we are ready to prove Theorem 4.
Proof of Theorem 4. The structure of our proof is similar to the proof of [7, Proposition 1]. Observe that the output f of Algorithm 1 can be expressed as
jáo + 2" (ās pi--)), j
Geom
E N.
(10)
Then we have
Blp Blin]
Σ
Pr{J= (E Elūz E(poo] 3r.
given that Pr(J= = 5} = 2- As for the variance, we have
E E ul12 < 2BI1 2oo12 + Ao mll?,
where
E pt 200l2
Pr(J = =)2/ - -3
2 jag - 13--111
j=1
j=1
and for each j we have
Eli 11--111 z 1 - 1l1 + 21E j 11112
By Corollary 2.
8²
16 1 -1112 <
Vj 2220,
100
23//2'
which leads
a²
o²
Eliig - =11 <
+
50
231
1)/2
50
231/2
10 23)/2'
and
0
1
Bll
Rol12
62
10
2)/2
Hence,
Eliū 21 < 2 2011
+2
1112 6²,
given that Ellio - 2ul2 < 02/1100 by Corollary 2. Moreover, the expected number of queries is
T d dogl
20 1+ Σ
Pr(J = (231/1 280- - = Lvd
j=1
18

---

C Proof of Theorem 5
We first state a result from [15] which bounds properties of defined in (5). The lemma states that, provided the radius of the convolution is sufficiently small, F is pointwise close to f and hence finding an (c))miinimum
f is equivalent to finding an e-minimum of F. Further the lemma shows that F is Lipschitz and smooth.
Lemma 4 ((15, Lemma 8)). For any L-Lipschitz convex function f: Rd - R. its Gaussian convo- lution g defined Eq. (5) convex, L-Lipschitz. and satisfies
If(x) g(x)l S vd. Lr and V2 S (L/r) Tla Vx V Rd. where Il is the d-dimensional identity matrix.
Prior to proving Theorem 5, we show that one query QSGO Ogr (Definition 3) of P, satisfying
Og gg
x)
X
(0)
x)
X
VVER
PF (v)dv |v) @ @ggarbagevv))
(11)
can be implemented by one query to Og of defined in Definition 3. Lemma 5. The QSGO Ogr of F, defined in (II) can be implemented with query to the QSGO
Og f.
Proof. We first prepare the following quantum state
(+) = xx) & ( V)r(ydd x x @ 10), Vx e
Applying Og the last two registers yields
(I (I (b) xx) (LER Virlr)dy/x-y)) JVERU V (V)xx)(v)drlv)
/ JyveRd V -x)ddd////yy/))
xx)
(12)
Given that
PF / JyeR= 7r 7,(x)p/x--((1))
we measure the last register, the probability density function of the outcome would exactly PFx- Hence, the quantum state (I @ Og) (1)) in (12) can also be written
21 = (x) @ J V (rxx(v)dv garbage @ lv).
By swapping the last quantum registers,
obtain the desired output state of O Ogr-
The following result from [57] bounds the rate at which Algorithm 2 decreases the function error of F,. Note that validity of this result relies solely the fact that, Line 6, the variance of the unbiased gradient estimate g, does not exceed 62, irrespective of its implementation.
Lemma 6. The output x of Algorithm satisfies
4LR
4Rt
(x7 -F1 TT(T +2)
+
VT
where F, is the convoluted function functioo defined in Line I of Algorithm 2 and F is its minimum.
Proof. This lemma follows from [57, Corollary 1]. which shows that
R2 4R0
E (( F T(T+2) VT
where E is the Lipschitz parameter of F,,, which equals L/r by Lemma 4.
19

---

Equipped with above results, ready present the proof of Theorem 5.
Proof of Theorem 5. By Lemma 6, the output Xout of Algorithm 2 satisfies
48 R
4
[F - F*] I rT(T +
VT S
(13)
2
Moreover, by Lemma 4 can derive that
[x - f = B[f - F Fxxott) + (f" - Fr) +
Fr]
Finally bound the expected number of queries to Og used in the algorithm. Since [x)] S L for any E Rdd by Theorem V Fx(x)")) with variance at most 6² using O(LVd/)) queries to the oracle Op, and hence the same number of queries to Ox by Lemma 5. Then, the total number of queries to Oz equals
know that Algorithm 1 can output estimate gr(xp(d) of
Lvd
LR
Lvd (2/8
R Le
LR 3/2
T.O
(5/88
V
D Proof of quantum stochastic cutting plane method
D.1 Proof of Proposition
Definition t6-approximate gradient oracle (6-AGO)). For F: + R. its 8-approximate gradient oracle, 8-AGO, is defined as a random fanction that when queried at x, returns vector gxx) that satisfies [lx(x) [x()]] S 6.
We show that 5-AGO be efficiently implemented using our quantum variance reduction al- gorithm. To obtain this result we can also use [53, Claim 1] by changing some parameters. Nev- ertheless, compared their deterministic implementation, our approach has lower expected time complexity (though is randomized).
Lemma 7. For any ö, 2 O, with success probability at least 1-E, the 8-AGO of Lipschitz.uuction can be implemented using O(log(1/E)) calls to Algorithm with in total ([LV)log(1/5))) queries to the QSGO.
Proof. We implement the 6-AGO using the following procedure. First, we obtain = log (bg((1)))11 independent unbiased estimates g1,... ........ gk of V f(x) with variance 8² /16 by Algorithm 1, using
Ld k 8 OLLV)log(
queries in total the QSGO Og. by Theorem 4. Note that any individual sample gi satisfies
6 2
Pr |lg. fx(x)
Hence, if we let denote the subset of [k] where each i S have &a distance to V.(x) at most 8/2, then by Hoeffding's 's inequality, |S| 2 2 with probability at least
- exp 2(k/3 - k/4)² 2 21
Observe that for any sample g; satisfying llg. Bill 6/2 for at least 2k/3 of g, there must exist at least some gy' E S such that [|g. gr < 8/2, and therefore Igg - vf(x)] < 5 by triangle inequality. Consequently, we just need to find and output any such g: as an 8-AGO, which is guaranteed to exist given that any sample in S satisfies this property. This can be done in expected ((k) time by picking random estimate and checking whether close at least 2k/3 of other estimates.
20

---

Next, establish that query e-optimal point by applying the cutting plane method with the separation oracle being an (E RttRRRaaapppiiaaa gradient oracle, as provided by Lemma 7.
Proof of Proposition 1. Define Ke/2 as the set of e/2-optimal points of the function S. and K, as the set of e-optimal points of f. We know that Ke/2 contains a ball of radius at least </(2T.)
since for any x with ||x x" S rx we have
f(x) [(x' S -|xx
(14)
We apply the cutting plane method, as described in Lemma 7, to query point in Ke/2, which subset of the ball (O). To achieve this, we use an (e/ (1)) of J. implemented using Lemma 7, the separation oracle for the cutting plane method. Throughout this process, we assume each query to the e(10RR)AGO is successfully exe- cuted, and will later discuss the enror probability associated with this assumption. In this case, we show that any query outside of K. to the e/100R)-AGO will be a valid separation oracle for Ke/2. In particular, if ever queried the e/ e(10R))AGO any BB K, with output being g, for any E Ke/2 we have
gradient oracle
ggy x) S (Vf(x), x) + l Vf(x)] ly - x||
$ f(y) f(x) + - fx))]] by -xl
- E + 4R < O,
2
10R
where the second inequality is due to the convexity f. indicating that g a valid separation oracle
for the set Ke/2. Consequently, upon applying Lemma 2, we can deduce that after (oo(dd//r)) iterations, at least one of the queries must lic within Kg.
To ensure overall success probability of at least 5/6, we employ the union bound, which neces- sitates that each query the c/100))AGG be implemented with a failure probability of no more than (6Cd log( R/rx)) which by Lemma 7 requires
10LRVd e
LRVd
log (og(GGdoog((R/xx)) =
c
queries to the QSGO Og. and the overall query complexity equals
δ LRVd
(3/2 LR
Cdllog(dR/rk) 5
6
D.2 Proof of Proposition
We first present the following algorithm that makes pairwise comparison using queries to the QSGO(Definition 3).
Note that in Line 7 of Algorithm 4 the estimation step is carried out in a projected space along the vector This is motivated by the fact that we are specifically interested the information of the gradient Vf within this projected space, which effectively reduces to a one-dimensional variable. As result, the mean estimation can be performed without introducing an additional factor of /d in the query complexity as given in Theorem 4.
Lemma 8. For any Yio- Y.o (0) and any é' > O. with success probability at least 1/(6T) Algorithm 4 returns point ý Rd satisfying
f(8) < min f(Ayio + -)yrro) + XE
using (RT./e) queries to an I--buunedd QSGO Og defined in Definition 3.
21

---

Algorithm 4: StochasttcclmsSSarally.....o
Input:
Endpoints Y, E (0), accuracy e' Output: y such that f(y) I minxe[o.1] (Ay -)yr)) +
Yt f Yio- Yr + Yro
if yr then return y1
3 else
C YI-Xi
-y- Y:ll
repeat
Ym < (y: + y-)/2
Obtain an estimate (y (yym)) T with error most (/R(RR)
if (ym)) - (4R) then return f Ym
else
if gb (ym) > 0 then yr Ym. else Y1 Ym
until y,, vill d/TL. return y f Y1
12
Proof. Observe that each iteration the value lly, - yrll is decreased by at least 1/2. Hence, the total number of iterations is at most
(1>rro- - Ytoll e//L
- (2RL)
log2
loga
e'
Within each iteration, we need to estimate the value V which is the component of V along è. Note that this is essentially univariate mean estimation problem, given that é is fixed in this iteration we can define an 1-dimensional random variable (y(ym) è whose variance most
Var (Vy Tēl E (y
E (y L
Then by Lemma 7, with success probability at least
2RL -1
6T loga
(15)
e'
an estimate of (y)m Te with error at most c'/(4R) can be obtained using
</(4R) log
(6T logz
6T
- (2 e'
(2RL
RL
é'
queries to the quantum stochastic gradient oracle Og. given that can prepare the following quan- tum oracle
10)
|x) &
(P /v é) s lgarbage(v))
VERU
using one query Og. Hence, Algorithm 4 uses Ö(RL/e)) queries the quantum stochastic gradient oracle Og, with failure probability at most
||yza 1y-0--1o) Viol
-voll
(6T
2RL
1
loga
(16)
E/L
6T
by union bound. Next, show that the output of Algorithm 4 has relatively small function value as desired, We denote
arg mi + +(1 -))+o)) and y" = X'y + (1 X*) XE[O.1]
If the algorithm terminates at point ý satisfying [لa(ه e' e//(4R), by convexity and the Cauchy Schwarz inequality we have
f(8) f(y)) Vf(T) - - 2R
2R < <.
22

---

Otherwise, by induction demonstrate that in each iteration of the algorithm, y" resides within the segment bounded by yr and yr- Assume that this assertion holds true for the /-th iteration. ga(ym) e'/(AR), we have
(V((m)) - ym) = (V 8)
11y: - ymll
S - Te (ym) - 4R lly: ymll < O,
indicating that the value of J will decrease along the direction yr ym- Hence, y* lies in the segment between YI and ym of the 1-th iteration, or equivalently, the segment between yr and Yı. of the (t + 1)-th iteration, given that is convex. A symmetric argument applies in the case of ge(ym) é (4RR). Then, we have
1 & Jyy - yrll
for every iteration, which leads
|1 - y s e' L
when the algorithm terminates. Hence,
f()) f(y)) L 1l y"l =
considering that f is L-Lipschitz.
Using Algorithm 4 as subroutine, we develop the following Algorithm 5 that solves Problem 5.
Algorithm 5: Stochastic Approximately best point among finite number of points
Input: A set of points (X1, [xi....;77) C (0) where T is power of 2, accuracy Output: such that f(x) I min, f(x)) +
Yo,i < X; for all E [7]
2 for T = 1,... log T do
for j = ..... T/2 do Yrj wttchhattcc..sssarrrryssgg.gaaae e/ogg////////
logg T)
return Ylog T.1
Proof of Proposition 2. to be power of I is not already power of 2, can simply augment the set with most TT points, each being X1, without changing the algorithm's output.
We start by demonstrating that without loss of generality we can assume T
Next, show that Algorithm makes T - 1 calls to the StochasticLinnSeardhh subroutine (Algorithm 4) with an accuracy of é' = e/ log, T to solve the Problem 5 problem. The algorithm exhibits hierarchical structure, as illustrated in Figure 1, where each non-leaf node invokes the StochatiicLneeerrcc(() subroutine once. Consequently, the total number of calls is T-1
By Lemma 8, each call to StochastieLineSerrchhh least 1/(6 Then by union bound, we can deduce that the likelihood of all calls to Stochasti cLineSearch()) being successful is at least 5/6. In this case, for any node Yr.j in the tree with r E [log, T] and [T/2"), by convexity and the guarantee of Lemma 8 we have
is executed successfully with probability
f(y+s) < min fAy + (1 - A)y A)y--125) + E/ logz T
xE[D,1]
< minnff(y-1112) 1,2 f(y + 1/log2 T.
Therefore for any leaf node x, with j E [T]. by summing over the path between the root y., and Xj we have
f(y..) S f(x)) +t logz T =(xx) +
which leads to
f(y,,) _ min f(x;) +c, jE(m]
23

---

V6,1
yt-1.
Y1-12
Y1,1
y1,4
+1
y1,
X1
x
x-1
x
x +1
x
XT-1
XT
Figure 1: The hierarchical structure of Algorithm 5.
indicating Yt,1 is valid solution of Problem 5. Note that there are in total non-leaf' nodes in Figure I, and the value of each non-leaf node is computed by one call to the subrou- tine (tochasticcLimeBerrctt))
Hence, the total number of calls to StochasticL.neeearchhl equals T - 1, and the overall failure probability of Algorithm 5 is at most
(T 1)
67
(17)
by union bound, the failure probability of Algorithm 4 is most 1/(6T). Since each call to Algorithm takes
RL e
RL
3
queries to the quantum stochastic gradient oracle Og defined in (2), the total number of queries to the quantum stochastic gradient oracle Og is then ① (RLT/e) /c).
D.3 Proof of Corollary
Proof of Corollary We first run cutting plane method with the separation oracle being an TD approximate gradient of implemented by Algorithm which by Proposition I outputs set I of ((e)-optimal point of ʃ using O (d8/2 queries Og with success probability least 5/6. Then by running Algorithm 5 on I, with success probability least 5/6 find point & E Rd satisfying
T (do)(E/))) points containing least
f(x) I min f(x) S f(x' + O(c),
xei
which takes Ō(RIT ÖdRL queries to Og by Proposition Hence, the overall number of queries Og equals ((dd/2LR// and the overall success probability is at least 2/3.
E Proof of Theorem 6
The proof Theorem based on following result from [40].
Theorem 9 ([40, Theorem I]). Consider the bounded variance setting in Problem 2, the output Xout of Algorithm is an expected 2 7 + -crrtticall point.
Proof of Theorem 6. By Theorem 9 and the associated parameter setting, the output Xout of Algo- rithm 6 satisfies
2
E| V )1
+ 0² <
T
24

---

Algorithm 6: Quantum randomized SGD (Q-SGD)
Input: Function f: RR -> IR, precision c, variance a, smoothness Parameters: & c/3, total iteration budget T 12A(
Output: e-critical point of f
Uniformly randomly select N from I,...,T
2 Set Xn < 0
for 0.1,2....... N do
Call Algorithm for an unbiased estimate gi of (x(x)) with variance at most o²
X++1 < X B./l
return XN
implying that Algorithm 6 solves Problem with probability at least 2/3 under the bounded variance setting, and the remaining thing would to analyze the number of queries it makes to Og- By Algorithm I to obtain unbiased estimate g: of (x(x,
Theorem 4, each iteration with variance at most 6² using
oovd 6 = θ
queries Og. Then, the total number of queries Og is at most
T.O 0 ovd
6
F
Proof of Theorem 7
Algorithm 7: Q-SPIDER
Input: Function f: Rd R. precision c, variance d, smoothness l
Parameters: y 20 ō 02 I0 total iteration budget T Output:
1600FA
a²
e-critical point of
Set X < 0
2 for t = 0, 1, 2, .............
if
mod (t, 0 then
Call Algorithm to obtain an unbiased estimate g. of V fxx:) with variance of gr
V.
else
Call Algorithm to obtain an unbiased estimate g: of Vf(x)) (x((x-1) with variance o²
V. g: V:-1
if [e] < 2c then return X;; else X(+1 f- Xx - T
10
Vi
return X-
The proof of Theorem 7 is based on the following result from [29].
Theorem 10 ([29, Theorem 1]). Consider the mean-squad sqean-squared smoothness setting in Problem 2, the output Xout of Algorithm 7 an expected e-critical point.
Proof of Theorem 7. Theorem 10 shows that Algorithm 7 can solve Problem 2 under the mean- squared smoothness setting and the remaining thing would be to analyze the number of queries makes to O
25

---

For each iteration / with mod(t. g) such that Line is executed, note that prepare the following quantum oracle
x) X / Vp(widdw (g(x w)) @ |garbage(x, w))
ÖR
x
0)
where p(w) is the probability distribution of the random seed w, by first applying Og to the state
xx) @ ([(Wdw)wwlw) (w)
(0)
and then uncompute the second register. This procedure uses one query to the a-SQ-QSGO Os (Definition 4). By Theorem 4, one can run Algorithm to obtain an unbiased estimate g: of fx(x)) with variance at most of using
ovd ④1
ovd
queries to Ög and thus the same number of queries to O
Similarly, for each iteration & with mod = O such that Line 7 is executed, note that one can prepare the following quantum oracle
O xx.) &0 (x-1) s (0)
(xx) 68 (x(-1)
L. (lw)ddll((x,co - g(x:-1,w)) @ ggarbage(xx, (x,baag(xxxxx1,1))) x)-1,
x
by first applying S twice obtain the state
x) x1-1) s / p(w))dw (w) @ (g(x, w)) x (g(x(-1,
lg(xxw) w) g(x @ (x,
and then uncompute the fourth and the fifth register. Observe that
(lg w()+11,W|| < e [x x1-1/| S 2
then by Theorem 4, one can run Algorithm to obtain unbiased estimate 8o of vf(x;)
V (x(((1)) with variance at most of using
evd d
da
02
queries to O' and thus twice the number of queries to g' Then, the total number queries to 0 can be expressed
T
δ ovd
+
(v
do
= LAVd (1 1+ 2
1
q
G Proof of lower bounds
G.1 Proof of Proposition 3
Note that Problem is strictly harder than the multivariate mean estimation problem considered in [25]. In the latter, the objective is to produce an estimate of the expected value within a bounded l2 error, without the requirement of unbiasedness. query lower bound for solving quantum mean estimation was established in [25].
26

---

Lemma (125, Theorem 3.8)). Let and denote Pa be the set af d-dimensional quantum random variables with covariance matrix such that Tr(E.) = =o² Suppose every E Pa is indexed by some random seeds w, i.e.
X XWW,,
pr:
where pn denotes the probability distribution of the random seed w. Then there exists a constant such that for any n. > ad and any quantum algorithm that uses at most n queries to the following oracles
On 10) - (Pp(w)ddwk
and
Bx [)] - (w) (
there exists an instance X Pa such that the quantum algorithm returns a mean estimate jı of the mean μ of X. that salisfies
σv d
1 Alll
Ω
with probability at least 2/3.
By employing an oracle reduction argument, we obtain our lower bound result based on Lemma 9.
Proof of Proposition 3. We first show that one query to the quantum sampling oracle Ox defined in Definition 1 can be implemented using one query to On and one query to Bx. In particular, observe that
Bx (0) 2 10) = Vpalw)dw (w) @ (X(W))
By measuring the first register in the computational basis spanned by all the random seeds {[w) }, can obtain the desired output of Ox. Hence, if there exists quantum algorithm making at most OLLvd/o) queries the oracle Ox that solves Problem 3 with success probability least 2/3, there also exists a quantum mean estimation algorithm that uses at most D(Tvd/0) queries to On and Bx and for any X Pa it outputs an estimate j of the mean μ of X that satisfies i all < (()) with probability at least 2/3, which contradicts to Lemma 9.
G.2 Proof of Theorem
Our proof follow similar approach the previous proof of the quantum mean estimation lower bound [25]. Specifically, our results are derived through a reduction to a specific multivariate mean estimation problem. In this problem, all vectors are sampled from a of orthonormal bases and there might be duplicated vectors. We choose to reduce to this particular problem instead of directly reducing mean estimation problem because the construction of hard instances require tighter control over the norm of the vectors as well as the norm of their expected value. This problem can be equivalently represented as the following composition problem, as defined in [25].
Problem 6 N )), ). Let N, M. 2 1 be two integers. Let AN.M denote the set of matrices E (0, N1NxM such that [N/2] rows have Hamming weights [M/2], and the other rows have Hamming weights [M/2] + 1. Define the vector b(A) such that,
6/ (A) [0,
the i-th row of has Hamming weight [M/2], if the i-th row of has Hamming weight [M/2] + +1,
(18)
11
for each i E [N]. Then, the Search Parity" M problem consists of finding vector b E R that minimizes ||b ((A)) given quantumm oracle
O (i.j) + (-1) ((.j).
(19)
[25] showed that MMNM) queries needed to approximate the vector (4) with small error.
27

---

Lemma 10 (125, Lemma 3.6)). There exists constant >> 1 such that, for any quantum algorithm for the Search Parity problem that uses at most N NM/ a queries there exists A AN such that this algorithm returns a vector b satisfying b b b(A)| 2 /N with probability at least 2/3.
We establish our quantum lower bounds for stochastic convex optimization by establishing cor- respondence between the Search" Parity problem and Problem 1. Specifically, for any input A E ANXM to the Search Parity problem, we design the following convex function whose optimal point corresponds to the solution of the Search Parity M problem under certain sets of parameters,
(A(x) = BlA,(()],
(20)
where
2L
(x) = (x. (x,).))
max 0, |
3
2
for some gij E Rd satisfying || S L for all i E [N] and E [M]. E gi.). Then, the function f desined in (20) has the following properties
Lemma 11. Denote B =
gg is non-zero vector
1. fd is convex.
2. fa is minimized at x" R
[
3. Every c-optimum x of FA satisfies
R
x
Re
x"
2
2
|
2 2
4. For
2L
R
gi,(x) =
3 gi.j +
max
||||
2 2
(21)
3
|x|||
it is the case that
E [[)] E (x* and
[x), &
Vx E Rd.
Proof. Since F is the sum of linear function and maximum function, both of which are convex, f itself convex.
Observe that the minimum of f cannot be achieved when ||x|| > R/2 for otherwise the function value can be further decreased when moving towards given that
Σi, gis
Σi gial
L.
NM
NM
When ||x|| < R//2 f can be expressed
1
f*(x) = (x,
which is minimized at
R
g
(A(
2
g
/2d
For any x that an e-optimum fA, we define
x'
X.
X
R <
2
R
otherwise,
2
28

---

which satisfies f(x) (xx and is thus also e-optimum of f. Then derive that
(x'
fxx
3
and
x
(x,x)) 2
(x",
g
Ree
2||g/|
which leads to
X
Rc
2
X
2|g
given that || 2 ||x||.
I.
As for the last entry, note that
1
2L
R
E
B (x)]
gig
|||||
4
43
3
2
|x|
2L
R
g
3
max
|
|
which is the (sub-)gradien) of f at x. Moreover, for any i,j we have
2L
) - gg + S
3
Equipped with Lemma 11, first prove quantum lower bound for Problem in the low- dimensional regime by encoding the Search o Parity problem into the task of finding an c-optimal point of f defined in (20).
Proof of Theorem when S 100/d' Our proof proceeds by contradiction. Denote n RL T00lr Assume for simplicity that d is even, and an is an even multiple of d (the other cases can be handled by padding arguments). Then, we show that Search" Parity on this instance A can be solved by finding an e-optimum of f defined (20). In particular, we define the set vectors {gr,s) to be
aTn ( (-1)++Awee
giy (2an) - d²
(22)
where i E [d]. j E [an/d], and e, E Rd the i-th indicator vector. Consider the function fa defined in (20) with the set of vectors {gin} having the values in (22), we have
d
an/d
= E
gi
1
aLn
e
Σ
(-1)++A
an
(2am)
d
i=1
j=1
d
2L
2L
(AA)
(2
d
(2am)2 d
i=1
where the vector (44 is defined in (18). By Lemma 11, every e-optimal point of J satisfies
R
Re
1
2 |x||
2|
by which we can derive that
R x
b(a)
Re
2 ||X||
xx*
2
2||
3omc
R
V
29

---

which leads
b(a)
2
2
2
Given that
d
x
= b(a)
V2
|x|||
=
V 2
have
V/2 x
Vd
b(a)
|||| 1
2
indicating that we can obtain an estimate obtaining an e-optimal point of fA.
V |x|
of b( with e--eroor at most vd/2 by
Next, we show that we can implement a quantum stochastic gradient oracle of F using only one use one query O to implement the following oracle
query the oracle O given that
0 b bi) (0)
(t) lá) (g.))
and use one query to O g implement
Og
(0) 00) + xx) (t) (5) (x))
where (x) is defined in (21). Then by applying Og to the state
(t) ()) 10)
aan
VE[d] jE[an/d]
and uncompute the second and the third register, we construct the following stochastic gradient oracle Og of f4.
0g1x) 10)
Σ E
Σ
Bis (x))
am
iE(d] jE/m/// /4]
Hence, any quantum algorithm that find an c-optimum of fa using T queries to Og can be transformed into a quantum algorithm for the Search" Parity problem that uses queries to the oracle O defined in (19) and returns an estimate with eg-error at most vd/2. Then by Lemma 10, for any quantum algorithm making less than
an
RL
d 2
d
2Ea
queries to the quantum stochastic gradient oracle Og. there exists an A E Ad, and corresponding fA such that the output of the algorithm is not an c-optimum f with probability at least 2/3. O
Similarly,
obtain our quantum lower bound in the high-dimensional regime by encoding the Search o Parity problem into the task finding an e-optimal point of f defined in (20).
Proof of Theorem 8 when 100Vd
RL Se E < 1. Our proof proceeds by contradiction. Denote
10000 Consider an instance A Aan,1 of the Search o Parity' problem where is a power of 2 and is even. Then, we show that Search am/d this instance A can be solved by finding an e-optimum of f defined in (20). In particular, we define the set of vectors {gij}} where j = to be
L²
g aLA.1
2ann 2a e.
(23)
30

---

where i [an] and e; IRd is the i-th indicator vector. Consider the function fA defined in (20) with the set vectors (gi,1 having the values in (23), we have
al on V 2
I n V 2a 2a
g gi
1
b(A),
2a
where the vector b is defined in (18). By Lemma 11, every c-optimal point of FA satisfies
R
Rc
2
2 ||x|
2 2|g
by which we can derive that
R x
((A)
|b(44]
Re
X
2 g
R
an
6ane
Ryan
2
2
which leads to
an
x
b(4)
an
2
x
2/2
Given that
an
x
b
(A)
an
2
|x|||
2
we have
V
on x
|X||
((4)
<
v an
2
indicating that we can obtain an estimate b obtaining an e-optimal point of f..
an
of ((4) with -r-err at most vd/2 by x
x
Next, we show that we can implement quantum stochastic gradient oracle of fa using only one query to the oracle O given that one can use one query O to implement the following oracle
0 1) (0)
+ (() lg.
and use one query to 0 to implement
O
xx ()) 00) (x) [1) g (x))
where (x) is defined in (21). Then by applying O to the state
&
10 10)
iE (an]
and uncompute the second and the third register, we construct the following stochastic gradient oracle Og of fd.
Og xx) 2 10)
xx)
Σ (x))
an
vE[an]
Hence, any quantum algorithm that can find an 6-optimum of fA using T queries to Og can be transformed into a quantum algorithm for the Search o Parity' problem that uses T queries to the oracle O defined in (19) and returns an estimate with e2-error at most vd/2. Then by Lemma 10, for any quantum algorithm making less than
R² 2
an 100c2
queries to the quantum stochastic gradient oracle Og. there exists an A E Aan.1 and corresponding f such that the output of the algorithm is not an e-optimum of f with probability at least 2/3. O
31


Reviews:
[{"review_id": "gxYjVyipKd", "reviewer": "Reviewer_Zhqz", "summary": "The paper presents quantum optimization algorithms for convex and non-convex optimization. The algorithms access a certain quantum stochastic oracle defined by the objective function f, and the presented complexity is lower than the best possible results in its classical counterparts.", "questions": "Please see the comment on weakness.", "limitations": "It is possible that the limitations of the proposed approach should be emphasized. Please see the comment on weakness.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The formulation is interesting. To the reviewer’s knowledge, this work is one of few that aims to find the fundamental limits of optimization algorithms in a quantum setting.", "weaknesses": "The formulation requires one particular quantum oracle (equation 3), where given any input state x, the “phase” of the outcomes is known, or particularly the oracle returns a pure state. This is strictly stronger than the classical formulation, especially since a classical algorithm would apply when the observation follows equation (1) and the garbage states are orthogonal (i.e., the density matrix being diagonal instead of being rank 1). So it is not immediately clear to the readers whether the reduced complexity is achieved by using quantum algorithms or just because we are dealing with an easier problem. If it is the second case, or if the proposed algorithm will not apply when the quantum phase information is not known. This distinction should be clearly mentioned in the abstract.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and detailed suggestions!\n\nRegarding your comment on the definition of our quantum oracle and the utility of our algorithm in practical situations, we agree that you raised a good point which has also been pointed out by other reviewers. Please refer to the general response for a detailed discussion.\n\nRegarding your question on the \"phase'' of the outcome, it is in general unknown in our setting, given that the garbage states can be arbitrary and contain arbitrary phases. We acknowledge our uncertainty regarding the context you may be referring to. If there is an alternative setting that you have in mind, we kindly request that you provide further clarification or details. We are happy to add more discussion in the final version.\n\nIn regards to the question of \"quantum algorithms\" versus an \"easier problem,\" note that given a standard (classical) stochastic gradient oracle, the rate of $O(\\epsilon^{-2})$ for convex optimization is unimprovable. Consequently, in order to achieve improved complexities, it is essential that we have a more powerful oracle for accessing the function. Note that our focus in this paper is on the query complexity of optimization given this oracle, rather than the additional computation involved in using the oracle. We will be sure to check that our final abstract is clear on the point that we are not working with the standard classical gradient oracle.\n"}, {"review_id": "hIjOUNrly1", "reviewer": "Reviewer_ewVR", "summary": "The authors focus on the optimization problem when quantum access is given to a stochastic oracle. They show that quantum speedups are possible for dimension-dependent algorithms and develop a quantum algorithm for computing the critical point of a smooth non-convex function along with a general quantum-variance reduction technique. ", "questions": "- The success of the quantum oracle is shown by the number of queries required to solve the problem. However there are some further aspects, like how much time each query takes, or also maybe the permutations of the queries (in random sampling since each item has equal probability showing the convergence is simple but how is it in quantum based samplings?), which subset of the queries to take (~active learning). Can the authors comment on these aspects too?\n\n- Is the contribution purely theoretic or are there any empirical results that the authors can show?", "limitations": "This paper does not have a direct potential negative societal impact.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The authors present multiple different quantum-based approaches in different settings along with the theory. Quantum variance reduction for stochastic nonconvex optimization is a novel contribution as far as I know.\n\n- The authors present theoretical advancements obtained by their proposed algorithms in Table 1. It looks technically correct but I might have missed some points. ", "weaknesses": "The main advancements in the theoretical bounds are obtained by adding the additional dimension restriction, it looks technically correct however in practice I am not convinced whether it would be possible to maintain the desired dimensions that benefit the presented algorithm. \n\nWriting related:\n\n- In writing, there is a lot of repetition; abstract, lines 42-48, lines 102-105 are almost the same. \n\n- The results are shared in Table 1, before specific definitions of the parameters are given (epsilon and d are defined after), which is difficult to follow. \n\nMinor : \n\n- Typo in line 62 \"classiic\" -> \"classic\", 290 \"wee\"->\"we\", 292 \"provideed\"-> \"provided\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and detailed suggestions!\n\nRegarding your comment on the definition of our quantum oracle and the utility of our algorithm in practical situations, we agree that you raised a good point which has also been pointed out by other reviewers. Please refer to the general response for a detailed discussion on this point.\n\nRegarding your comments concerning the detailed implementation of the quantum oracle in various scenarios, such as random sampling or active learning, we agree that that these are intriguing questions for future work. and we may expand on this in the final version.\n\nRegarding the typos and repetitions you pointed out, we sincerely appreciate your careful review, and we will fix them in the final version. Regarding your comments on the order between Table 1 and the definitions of parameters, we thank you for pointing this out and we will fix this in the final version."}, {"review_id": "lyTiSxtOuz", "reviewer": "Reviewer_krht", "summary": "This paper tries to give quantum algorithms for solving Lipschitz convex optimization\nproblems with “quantum stochastic oracle”. Additionally, they claim to have a quantum\nalgorithm for computing a critical point of a smooth non-convex function at a rate not known\nto be achievable classically", "questions": "1. Var[X] In Problem 3 should not be a real value. It should be the covariance matrix\nbecause X is a d-dimensional vector. Also, \\hat{\\sigma} has nothing to do with Var[X]\nand L. So it’s not clear what is the goal of the problem here. Also, if \\hat{\\sigma} is\nsmaller than L, this problem is not generally solvable.\n2. The query complexity of multivariate mean estimators depends on the trace of the\ncovariance matrix, while in this paper, they directly assume the trace of the\ncovariance matrix at most 1, which is very unreasonable.\n", "limitations": "The authors did not adequately address the limitation. I suggest the author first carefully\nproofread and check the correctness of the definitions, problems, and the theorems they\ncited.\n", "rating": 4, "confidence": 3, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "This paper tries to use the quantum multivariate mean estimator to solve optimization using the quantum stochastic gradient oracle", "weaknesses": "Neither the quantum sampling oracle (Definition 1) nor the stochastic quantum gradient oracle (Definition3) is well-defined, and it’s not clear how people can get such a quantum oracle as well. Also, all their algorithms are just applying the quantum multivariate mean\nestimation directly to the very well-known classical optimization algorithm. Moreover, the region they can have a quantum speedup is very very limited (assuming all their claims and proofs are correct, which seems unlikely.)\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed comments!\n\nRegarding your question on the notation $\\mathrm{Var}[X]$, in our paper it denotes the trace of the  covariance matrix of $X$ and is referred to as the variance of $X$. This colloquial use of the term variance is common in optimization literature and we therefore felt that the term $\\mathrm{Var}[X]$ was natural to use. However, we see the confusion this could lead to and will clarify in the final version. Thank you for pointing this out! In a similar vein, $\\hat{\\sigma}$ symbolizes the square root of the target variance. Regarding the solvability of the problem it is well established that stochastic gradient descent computes $\\epsilon$-optimal points of convex functions with only bounds on the $\\ell_2$ norm of the minimizer and bounds on the expected squared $\\ell_2$-norm of stochastic gradients. If you still have a concern regarding solvability, please let us know.\n\nIn response to your inquiry about our assumption concerning the trace distance of the covariance matrix, we wish to clarify that our assumption does not entail a strict bound of $1$. Instead, we assume it is bounded by a specific quantity denoted as $L$, which appears in the overall query complexity.\n\nRegarding your question on the novelty of our algorithm, we would like to clarify that we did not directly apply the quantum multivariate mean estimation directly to classical optimization algorithms. Notably, the quantum mean estimation technique introduces potential bias that accumulates during the iterations of classical algorithms and break their convergence guarantees. As discussed in Section 2, in this work we develop a new algorithm that can obtain unbiased estimates, which is a nontrivial technical contribution that might also be useful in other scenarios.\n\nRegarding your comment on the region where our algorithms have quantum speedups, especially its dependence on the dimension $d$, we agree that this is good point which has also been pointed out by other reviewers. Please refer to the general response for a detailed discussion on this point.\n\nRegarding your comment on the implementation of the quantum oracle and the utility of our algorithm in practical situations, we agree that you raised a good point which has also been pointed out by other reviewers. Please refer to the general response for a detailed discussion on this point.\n\nRegarding your comment on the correctness of our proof, we wish to assure you that we have conducted a thorough proofreading process. In this process we encountered some corner cases, e.g., how we handle expected error versus high probability bounds, and we plan to address all in the final version. Nevertheless, if you have any concern regarding any specific part of the paper, please kindly let us know, We are more than willing to perform an additional check to ensure the correctness of our results."}, {"review_id": "eGnYV24n5i", "reviewer": "Reviewer_YvE3", "summary": "This paper proposes several quantum algorithms stochastic optimization. First, a technique called \"quantum-variance reduction\" is introduced and used to develop two new quantum algorithms for convex optimization problems. The \"quantum-variance reduction\" technique uses a quantum sampling oracle to speedup the task of estimating the mean of a random variable with some desired variance. Additionally, a quantum algorithm for finding critical points of smooth non-convex functions is presented. This algorithm also uses the quantum variance reduction technique and applies it to a classical algorithm for solving the same problem.", "questions": "My main question is related to how the proposed algorithms using quantum variance reduction compare to other quantum algorithms for the same problems. In Line 222, it is said that the result can be obtained using quantum mean estimation from an existing paper, in which case there seems to be no need for quantum variance reduction. However, quantum variance reduction is a major contribution of this work, so naturally I wonder how this method benefits the design of quantum algorithms compared to other quantum algorithms.", "limitations": "Algorithm 1 presented in this paper only achieves the optimal scaling with $\\epsilon$ when the dimension $d$ is constant. The authors have addressed this as a potential direction for future work.\n\nSince this is a theoretical work on quantum algorithm design, there are no foreseeable negative societal impacts.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Theorems 1 and 2 are good results for the proposed quantum algorithms for convex optimization. It's good that for fixed dimension, the dependence of $\\epsilon$ is matched between the algorithm and the quantum lower bound.\n- Similarly, Theorem 3 is a good result for the quantum speedup for finding critical points of nonconvex functions.\n- The proposed method for quantum variance reduction is interesting, and improves upon previous results by giving an unbiased estimator with better query complexity.\n- The application of the quantum variance reduction to several classical algorithms leads to an algorithm with better query complexity than the classical counterparts. This also raises the question of whether this method can be used to improve other algorithms, not necessarily in the domain of stochastic optimization.", "weaknesses": "- Since Algorithms 2 and 3 are essentially modified versions of algorithms from existing work, it would be helpful to give a brief description of how each algorithm works in order to make the paper more self-contained.\n- Table 1 only compares the proposed quantum algorithms with the classical counterparts. I think other quantum algorithms for solving the same problem should be included as well.\n- Typos: \"classiic\" instead of \"classical\" in line 62, missing a colon in line 133, \"there\" in line 168, \"wee\" in line 290, \"provideed\" in line 292, \"gradient\" instead of \"gradients\" in line 219\n- In line 229 (Problem 4), it says $\\epsilon \\in (0,K)$. Is $K$ the set or a number? This seems to be a typo.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and detailed suggestions!\n\nRegarding your question on the role of our quantum variance reduction technique in stochastic optimization, we use it critically and directly in results Algorithm 2 and Algorithm 3. In particular, Algorithm 2 and Algorithm 3 encounter potential bias issues if instead quantum mean estimation was applied directly, which can impede their convergence. Furthermore, in a broader context, a considerable number of existing gradient-based classical stochastic optimization algorithms require the stochastic gradient to be unbiased. If we intend to extend these algorithms into the quantum domain, the quantum variance reduction technique becomes indispensable in eliminating the bias.\n\nWe agree with you that we do not necessarily need to use quantum variance reduction in obtaining Corollary 1, given that stochastic cutting plane method is robust against possible bias. However, it is non-trivial to apply stochastic cutting plane method in our setting and the subsequent analysis is far from straightforward, which is also a technical contribution of our work. We agree with you that you raised a good point and we will clarify more in the final version.\n\nRegarding your comments on the presentation of Algorithm 2 and Algorithm 3, we agree that it is helpful to briefly describe how the corresponding classical algorithms work. We will include this discussion in the final version.\n\nRegarding the comparisons between our quantum algorithms and other quantum algorithms in Table 1, we have diligently searched the literature and, to the best of our knowledge, we have not found any prior quantum algorithms specifically addressing the same problems we are considering. However, if you are aware of any previous quantum algorithm that might be relevant, please kindly let us know; we are very happy to include a comparison in the final version.\n\nRegarding the typos you pointed out, we sincerely appreciate your careful review, and we will fix them in the final version."}, {"review_id": "XYqgIQe0B8", "reviewer": "Reviewer_PEHT", "summary": "The paper considers the problem of stochastic optimisation for both convex and non-convex functions and aims at improving the scaling of the number of queries as a function of the approximation error. The authors introduce a technique based on quantum variance reduction, that builds on top of previous work to estimate the mean of a random variable given access to a quantum sampling oracle.\nThe paper is well organised and presents three algorithms (Q-AC-SA, Quantum stochastic cutting planes and Q-Spider) where the main contribution is replace access to classical oracle for bounded variance gradient estimator with their quantum oracle.\nThey show a quadratic speed in some cases at the expense of dependence on the dimensionality d of the optimisation problem.\nThe authors also provide lower bounds for quantum variance reduction, showing their approach is optimal in this sense.", "questions": "- Could you comment on the implementation of the oracle? What would be the overhead say as a function of d? \n- Could you give some intuition around where the quadratic speedup in QuantumMeanEstimation come from?", "limitations": "- The fact that the number of queries scales with d limits the application to high dimensional problems, the typical setting of interest in machine learning\n- No comment on implementation of the oracle and resources required for implementation on a quantum computer is given", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents novel results that combine the field of quantum variance reduction and that of stochastic optimisation.\nThe main strength are\n- clear organisation of the paper\n- relevance of the problem studied. \n- mathematically rigorous statements about their claims\n- broad applicability of the results (convex to non-convex problems)", "weaknesses": "- The scaling of the number of queries of the algorithm introduced now increases with the dimensionality d of the problem.\n- The oracle model makes it hard to understand whether practically there are scenarios where this method is favourable that a classical algorithm\n- The core routine used, QuantumMeanEstimation, which achieves a better scaling is not explained. \n- A few typos (see list below)\n\nMinor:\n\n- Line 58: qubits are superpositions of bit strings, here the authors assume continuous variable. Is the idea to discretise those? \n- Line 62: classiic (typo)\n- Line 63 and in other places: I found using $\\sqrt{dx}$ confusing: I would have written a quantum state $\\int dx \\sqrt{p(x)} |x\\rangle$, otherwise $\\langle x|\\psi\\rangle$ is not a number\n- Equation 2: what is $L$?\n- $\\tilde{O}$ undefined, is it up to polylog?. Why in Theorem 4 we have $\\log d$ and not in Lemma 1?\n- Line 132: gien (typo)\n- Line 133: missing : in definition of f\n- Line 163: $\\hat{\\mu}$ should be $\\tilde{\\mu}$\n- Line 168: there should be their\n- Line 183: where is $j\\le j_{max}$ used?\n- Equation 12: I think that = should be $\\le$ and that there is a missing constant $2(1+2\\sqrt{2})$ which changes the constant in the bounds\n- Line 198: Lemma 3 not defined in the the main text. In general I found the links in the pdf broken.\n- You might consider making $g_F(x)$ a function of $y$ explicitly\n- Line 217: Missing closing parenthesis in $O(d \\log(\\epsilon^{-1}))$\n- Line 230, 231: x should be bold\n- Line 232: $O(d / \\log(\\epsilon^{-1}))$ should be $O(d \\log(\\epsilon^{-1}))$\n- \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and detailed suggestions!\n\nRegarding your comment on the $d$ dependence in the number of the queries, we agree that this is good point which has also been pointed out by other reviewers. Please refer to the general response for a detailed discussion on this point.\n\nRegarding your comment on the implementation of the quantum oracle and the utility of our algorithm in practical situations, we agree that you raised a good point which has also been pointed out by other reviewers. Please refer to the general response for a detailed discussion on this point.\n\nRegarding the intuition of the quadratic quantum speedup given by QuantumMeanEstimation, it proceeds by introducing a directional mean function that reduces the multivariate mean estimation problem to the univariate mean estimation problem, which in the bounded norm case can be solved by quantum algorithms with a quadratic speedup using phase estimation. We will include more discussion on this in the final version.\n\nRegarding the typos you pointed out, we sincerely appreciate your careful review, and we will fix them in the final version."}]

Author rebuttal:
Thank you to the reviewers for their thoughtful consideration of our paper. We appreciate your positive recognition of our contributions and helpful suggestions for improvement. Here we address some common questions that arose in multiple reviews.  

We noticed that the reviewers had some questions in common regarding our submission; here we provide answer these question. (More Specific questions of individual reviewers are provided in individual responses.)

$\mathbf{Practicality. }$
Regarding the implementation of our quantum oracle and the utility of our algorithm in practical situations, we note that our quantum oracles are defined as direct, natural extensions of the corresponding classical oracles. Connsidering such quantum generalizations of classical oracles i standard in the literature, see e.g., [1, 2]. Furthermore, there are standard techniques for implementing such quantum analogs of classical oracles (in theory for now given the current state-of-the-art in implementing quantum algorithms in practice). In particular, if there is a classical circuit for the classical oracle, there is a standard technique to use a quantum circuit of the same size to implement the corresponding quantum oracle. Hence, we believe our quantum algorithms have the potential to surpass blackbox classical algorithms in low dimensional settings where the oracle is given as an explicit circuit. We will add more discussion on this point in the final version. 

Nevertheless, given the current state-of-the-art on quantum computation in practice,  this work is purely theoretical for now. We agree that until more practical quantum computational resources are widely available, the practical utility of our advances is indeed unclear. We will include more discussion on this in the final version, and will add this as a limitation.

$\mathbf{Dimension\ dependence. }$
Regarding the parameter region where our algorithms have quantum speedups and their dependence on the dimension $d$, note that our algorithms apply for all $\epsilon$ and $d$, i.e., there is no dimension restriction on whether they obtain the claimed bounds. However, our claimed bounds only improve upon state-of-the-art classical algorithms when $\epsilon$ is sufficiently small relative to the dimension. Below we provide several additional points towards addressing this concern (all of which will be addressed in the final version):

(1) As mentioned, In the classical setting, prior research [3] has demonstrated that when optimizing an 1-Lipschitz convex function, SGD with query complexity $O(\epsilon^{-2})$ remains optimal, even in the one-dimensional case, and this $\epsilon$-dependence remains unaffected by the inclusion of additional factors, such as dimension $d$. In the quantum setting however, we addressed an interesting question about when quantum speedups are possible and discovered theoretical phenomenon that there exists a tradeoff between $\epsilon$ dependence and $d$ dependence. From our lower bound we know that some dimension dependence is inherent in obtaining an improvement.

(2) Classically, the question of utility dimension dependent is a long line of work. In particular, there are parallel and private stochastic convex settings where the dimension dependence is discussed, see e.g., [4, 5], and there exists works on critical point computation in low $d$ settings, see e.g., [6].

(3) There is the possibility of applying our algorithm as a subroutine in settings where the dimension is lower. For instance, consider its application to the approximate optimal finding problem (Problem 5), wherein we utilize our algorithm repeatedly within a one-dimensional setting.

$\mathbf{References. }$

[1]. Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. "Quantum algorithms and lower bounds for convex optimization."

[2]. Chenyi Zhang, Jiaqi Leng, and Tongyang Li. "Quantum algorithms for escaping from saddle points."

[3]. John C. Duchi. "Introductory lectures on stochastic optimization."

[4]. Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, and Kevin Tian. "Resqueing parallel and private stochastic convex optimization."

[5]. Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. "Complexity of highly parallel non-smooth convex optimization."

[6]. Sinho Chewi, Sébastien Bubeck, and Adil Salim. "On the complexity of finding stationary points of smooth functions in one dimension." 

Meta-review: The paper presents quantum algorithms for stochastic optimization problems, both convex and non-convex, using a technique called “quantum variance reduction.” The reviewers have generally provided positive feedback on the paper, and the authors have responded adequately to the reviewers' comments and concerns.

The paper presents novel results that combine the fields of quantum algorithms and stochastic optimization and offer promising potential for quadratic speedup in specific scenarios, which is a notable contribution. Further strengths of the paper, as highlighted by the reviewers, include its clear organization, the relevance of the problem studied, and its exceptional mathematical rigor.

However, there are some limitations, particularly the scaling of the number of queries with the dimensionality of the problem, which may limit the application to high-dimensional problems – the relevant scenario in machine learning. Additionally, the paper does not provide insights into the practical implementation of the quantum oracle and the resources required for quantum computation; the reviewers have raised questions about the implementation of the oracle, the intuition behind the quadratic speedup achieved in QuantumMeanEstimation, and comparisons with other quantum algorithms for the same problems.

Overall, the paper is technically sound and presents valuable contributions to the field of quantum optimization. The authors should carefully address the major concerns raised by the reviewers and provide additional clarity in the final version.
Decision: Accept (poster)