Isotropic Noise in Stochastic and Quantum Convex Optimization
Authors: Annie Marsden
Liam O'Carroll
Aaron Sidford
Chenyi Zhang
Venue: NeurIPS 2025 poster ()
Keywords: stochastic convex optimization
quantum convex optimization
cutting plane methods
Primary area: optimization
TL;DR: We introduce a new gradient noise model for stochastic convex optimization and apply it to achieve state-of-the-art rates in both quantum and non-quantum settings.

Abstract: We consider the problem of minimizing a $d$-dimensional Lipschitz convex function using a stochastic gradient oracle. We introduce and motivate a setting where the noise of the stochastic gradient is isotropic in that it is bounded in every direction with high probability. We then develop an algorithm for this setting which improves upon prior results by a factor of $d$ in certain regimes, and as a corollary, achieves a new state-of-the-art complexity for sub-exponential noise. We give matching lower bounds (up to polylogarithmic factors) for both results. Additionally, we develop an efficient quantum isotropifier, a quantum algorithm which converts a variance-bounded quantum sampling oracle into one that outputs an unbiased estimate with isotropic error. Combining our results, we obtain improved dimension-dependent rates for quantum stochastic convex optimization.

Isotropic Noise in Stochastic and Quantum Convex Optimization
Annie Marsden'
Liam O'Carroll
Aaron Sidford
Chenyi Zhang?
Abstract
We consider the problem of minimizing d d-dimensional Lipschitz convex function using stochastic gradient oracle. We introduce and motivate setting where the noise of the stochastic gradient is isotropic in that it is bounded in every direction with high probability. We then develop an algorithm for this setting which improves upon prior results by a factor of d in certain regimes, and as corollary, achieves a new state-of-the-ar complexity for sub-exponential noise. We give matching lower bounds (up to volylogarithmic factors) for both results. Additionally, we develop an efficient quantum isotropifier, a quantum algorithm which converts a variance- bounded quantum sampling oracle into one that outputs unbiased estimate with isotropic error. Combining our results, we obtain improved dimension-dependenn rates for quantum stochastic convex optimization.
Introduction
Stochastic convex optimization (SCO) [51, 47, 48, 9] is a foundational problem in optimization and learning theory, with numerous applications in theoretical computer science [16], operations research [50], machine learning [11], and beyond. Algorithms for SCO, most notably stochastic gradient descent (SGD) and its many variants, are extensively studied and widely deployed in practice. In addition, there has been increasing interest recently in its quantum analog, quantum stochastic convex optimization, and provably efficient quantum algorithms with have been developed [53, 67).
In one of its simplest forms which we focus on in this paper, SCO asks to compute e-optimal point of a differentiable' convex L-Lipschitz function f: + R, minimized at an unknown point xt bounded stochastic gradient oracle, which we define formally in Definition and Definition 2 below. Throughout, we assume that the randomness in calls to any oracle are independent of previous calls.
with ||-1| < R for the Euclidean norm ||-II, given access
Definition 1 (SGO). O()) is a stochastic gradient oracle (SGO) differentiable f: Rd - if when queried at x E Rdd, it outputs O(x) E dRd such that BO(x) V f(x).
Definition (BSGO). Ob(-) is a boubdddded SGO po--BSGO) for differentiable f: RRd R if is an SGO for f such that E| (x())] < of for any query Rdd.
It is well known that SGD, particular, iterating Tr+1 --- ((00),))) with appropriate choice of step size solves SCO with O queries, which is optimal even when d = 1 [2]. In
this paper, we seek bypass this fundamental limit by studying more fine- mne-griieed models of the stochastic gradient. In particular, we study the following question:
"Google Deepmind, anniemarsden@goggee
Stanford University, {ocarroll, sidfoor, ctt.cyyiieettaaaoorrrra waw.nford.dd...............o...e edu
Preprint available at arXiv:2510.20744
We assume objective functions are differentiable. Following similar argument in prior works (e.g.. [17, 53]), our results extend to non-differentiable settings because convex functions are almost everywhere differentiable, and our algorithms are robust to polynomially small numerical emors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Can identify shape-dependent assumptions the noise of the stochastic gradient which allow us to obtain new state-of-the-ar algorithmic guarantees?
One of the most natural shape- deppedddeeddenttt assumptions is to assume bound on the variance of the SGO, which we capture in the following definition:
Definition 3 (VSGO). Ov(-) is a oy-variance- SGO (oy-VSGO) for differentiable f R IR if it is an SGO for I such that ElOv((z) v=))) & of for any query x E IR....
In the setting we consider where f is L-Lipschitz (see Problem for a formal definition). SGD trivially achieves rate of (L + (+²) = O to the observation that a oy- is O σv J-BGO. Inspecting the above rate, the R² Root. term unimprovable even when d = [2].* However, the same is not true for the R /e2 term, which stems from the non-stochastic component of the problem. Indeed, when Øv = 0. in which case the SGO is a gradient oracle, the OH2L2//e" rate (which is achieved by gradient descent [49]) is optimal only for e 2 QQRL Vd) [24]; cutting plane methods which achieve (d) rates are better at smaller target precisions, where we use Ō()) throughout the paper to hide polylogarithmic factors in 1/e, log(1/o), d, R. and L.
+ R L2/ (22 under ov-VSGO due
This leaves the door open for improved dimension-depender rates for SCO under a VSGO, which have not been explicitly studied to the best of our knowledge. In particular, in light of the fact that a O O(Roty/e + R²L2/e²) rate is achievable by SGD and it is possible to achieve min L2 {(d) when ov = 0, this begs the natural open problem:
Open Problem
possible to solve SCO with Ö(R ot /22 d) queries to VV-VG
While do not solve this open problem, we nonetheless make substantial progress in characterizing the complexity of SCO under more fine-grained shape-dependent assumptions on the SGO. Our main conceptual contribution is to answer this open problem in the affirmative under stronger noise model which we introduce in the next section, termed isotropic noise, We provide a dimension--deeendent algorithm in this setting which achieves the conjectured Ö(R² o²/e² /e2 + d' rate (albeit o² is not the variance but a different parameter associated with our noise model). We then instantiate this result to achieve the target O(R²02 + d) rate for sub-exponential noise, widely studied class of distributions in machine learning and statistics, as well as a OddR"tt + d) rate for SCO under VSGO, which is worse than the conjectured rate by a d-factor. We then give lower bounds for isotropic noise and sub-exponential noise which show that in any parameter regime, applying the better of our algorithm and SGD is optimal (up to polylogarithmie factors).
Finally, we leverage our algorithm to obtain a new state-of -ft-----tthrrrnn- the-art guarantee for quantum SCO under quantum analog of the VSGO oracle. In what may be of independent interest, our quantum result relies on a quantum subroutine which we call a quantum isotropifter, which converts a quantum analog of the VSGO oracle into which outputs unbiased estimate of the gradient with isotropic noise. In other words, this subroutine allows us to apply our improved guarantees for isotropic stochastic gradients to an even broader class of noise models in the quantum setting.
In the remainder of the introduction, we define our noise model and present our results in more detail (Section 1.1), discuss additional related work (Section 1.2), define notation (Section 1.3), and give roadmap of the rest of the paper (Section 1.4).
1.1 Results
Isotropic and sub- sub-exponential SGOs. As our main conceptual contribution, we define a new noise model for SCO which captures the impact of the shape of the noise, as opposed to only its moments. In particular, we consider an isotropic noise model, formalized in the following definition, where the magnitude of the noise in any fixed direction is bounded with probability at least 1 - 8.
'This follows from the same lower bound construction which shows that (2 12R202/e2 for SCO under o -BGGO. Indeed, in that construction (e.g.. Section 5 [23]), it the case that of O(a)) 'e emphasize that although they study a different setting, this rate can be recovered by modifying the techniques of [53]; see Sections 1.1 and 2 for further discussion.
o2/e²) queries are necessary

---

Definition& 4 (ISGO), O₂(-) is a (ar, 8) -iistrooppc SGO ((0,,0)-1008 0)-100)) for differentiable f R - R it an SGO for f such that
IP (0) Vf(x), u))l 2 क1 / S d for any I, RR s.t. ||u||
The 1/Vd scaling factor in Eq. 1 is included to ensure dy in Definition 4 and øy in Definition 3 are comparable in scale. For example, (a, 0)-ISGO Or(-) is also a --VGG, since with e, the i-th standard basis vector:
E| (x)) ff(2)]
ff(x)) E Σ V((())))))( iE
Σ E(e, (1(2) v(a))" KE(d
Informally, ISGO can be thought of as a VSGO with the stronger assumption that the noise is bounded evenly in all directions, thereby imposing additional structure on its shape. Formally, we show later in Lemma that a (60v -I-IGO query can be implemented with logarithmically many queries to σv- -VSGO, thereby allowing to translate algorithmic guarantees for ISGO to VSGO the cost of v ddffcc.
ISGOs also naturally capture a variety of light- distributions, for which we use sub-ex aub-exponential distributions representative example throughout this paper due to their widespread prevalence in machine learning and statistics. In particular, we consider the following ESGO:
Definition (ESGO). Og(+) is s---u--eeonenniid SGO (og-ESGG)) for differentiable f R
R if it is an SGO for J such that for any x, u E IRd such that ||u| =
P[[(n(()) (x))), n)) 2 t) 2 exp(- exp(-tvd/oz) for all t
The vd factor in Definition 5 present for the same reason present Definition 4, and we show for all 5 (0, 1) that any o-ESGO is (2log(2/5),. 8)) (see Lemma 8). We collect and review basic facts about sub-exponential distributions, as well as provide some additional discussion about the relationships between the various SGO oracles define, in Appendix D. In particular, show that a E is a Co E-g-VVGO VSGO for some absolute constant C, and thus Definition 5 can also be interpreted imposing structure on the shape of the noise beyond variance bound.
The complexity of SCO with ISGOs, ESGOs, and VSGOs. We formalize the general setting we consider in Problem 1 and then present our results, including upper and lower bounds. Problem 1 (SCO). Given access an SGO (--) for a convex and L-Lipschitz (with respect the (2-norm) function f: Idd + R such that there exists x² argmin f(z with |I*|| < R, the goal is to output an c-optimal point.
In Theorem and Corollary 2 (proven in Section A and Section B respectively), we achieve upper and lower bounds for Problem 1 given access (σ,, 6)-ISGO. We obtain the upper bound Theorem I via a stochastic cutting plane method by extending the techniques of [53]. and the lower bound Corollary 2 by reducing mean estimation problem to Problem 1; see Section for a technical overview. In Corollary 2, we use 52(-) to hide logarithmic factors in d. Theorem 1. Problem I can be solved with probability at least 2/3 in O(R2of/e" d) queries to (ar, -)SG for any 8 Ma((ootaaady where M = Ō(1).
Corollary 2. Any algorithu which solves Problem 1 with probability at least 2/3 using (01, 6)- ISGO makes least 52 of
of/(e (6² log" (1/8)) RR 1.2 / queries.
In other words, Theorem 1 says that Ö + d) rate is achievable long as 8 is inverse- polynomially small, and Corollary 2 says this is tight up to polylog factors when the target precision sufficiently small so that d < R² L ee2 or equivalently c < RL/Vd. In particular, Theorem demonstrates that shape-dependent assumptions rates for SGD. For example, for a (o, OS-IGO (which we saw above is also a a oVVSGO), the Ó /22 + d) rate of Theorem improves upon the ORRo2iee + T.2 /22 rate of SGD when LS max(o, e V RR,, which captures variety of high precision, low variance regimes. Next, using the fact discussed above that ISGO queries can be implemented via ESGO and VSGO oracles, we obtain the following upper bounds (proven in Section A) as corollaries of Theorem 1:
the noise can lead speedups over the known
3

---

Corollary 3. Problem can be solved with probability at least 2/3 in O + d) queries to Eg-ESGO.
Corollary Problem I can be solved with probability least 2/3 Ö (dRRot/C + d) queries to oy-VSGO.
Thus, sub-exponential noise allows us to match the rate conjectured in Open Problem 1, whereas using VSGO results in additional d factor in the variance-dependent term. Nevertheless, Corollary still outperforms the O1IPot /ē2 + R2 (() rate achieved by SGD for solving Problem given vv-VSGO when L > vd. max c/R) R). We emphasize that while they study a different setting, modification of the techniques of [53] can achieve the same complexity Corollary 4; the technical overview in Section for further discussion. However, we believe the fact that we are able to recover Corollary 4 as a simple consequence using our more general 0)-,G) primitive illustrates its potential broader applicability.
Finally, prove in Section B that Corollary 3 is tight up polylog factors when d 2 R2= Theorem 5. Any algorithm which solves Problem with probability at least 2/3 using og gEEESGO makes at least Q2( R o / min RR / dd) queries.
This effectively solves Open Problem for the special case of sub-exponential noise in light of the fact that SGD matches our lower bound in the other regime where d s R² R
Quantum SCO under variance-bounded noise. As an additional application of Theorem we consider stochastic convex optimization (SCO) with access to quantum analog of VSGO, which we refer as a QVSGO. The QVSGO is a direct and natural extension of VSGO, and slightly generalizes the notion of QSGO introduced in [53, Definition 3].
Definition 6 (QVSGO), For f: Rd + R and ov > O. its quantum bounded stochastic gradient oracle (av-QVSGO) is defined as
Oqv (x) 2 10)
+ (z)
JEER VDI=<ggdgg (g) @ lgarbage(g))
(3)
where (f,(.) ()) is the probability density function of the stochastic gradient that satisfies
E [g] Vz(x), gmPpsx
E g-Pf.
llg [(xx)] oo..
Given access QVSGO, we develop a quantum algorithm that achieves improved query complexity for the following quantum SCO problem. This problem slightly generalizes [53, Problem 1] by introducing an additional parameter øy alongside the Lipschitzness L.
Problem 2 (Quantum SCO). Given query access σy QV-GVO OQv for convex and L-Lipschitz (with respect the (o-momm function f: Fdd + R such that there exists x* E argmin fzz with | || < R, the goal is to output an e-optimal point.
To solve Problem error is isotropic, which we refer to as quantum isotropifier. We use this algorithm to prepare an ISGO using QVSGO:
develop unbiased quantum multivariate mean estimation algorithm whose
Theorem 6. For any differentiable J: Rd + R, (a,, S)GGO of J can be implemented using Olovvdlog" (Lo/)/)o"(L//))) (Lr)))/r) queries av- QVSGO.
Combining Theorem I and Theorem 6, we obtain the following improved query complexity for quantum SCO (proven in Section C):
Theorem 7. With success probability at least 2/3, Problem 2 can be solved using ÖddRov /c) queries to a ov -VVSGO.
'Considering such quantum extensions of classical oracles is standard in the literature, e.g., [20, 65, 53]. Moreover, theoretically there well-established techniques for implementing these quantum analogs of classical oracles. Specifically, a classical oracle can implemented quantum oracle can be implemented using a quantum circuit of the same size. A description of the quantum notation can be found in Section C.
classical circuit, corresponding

---

To compare, the prior state-of the- art for solving Problem 2 includes two quantum algorithms of [53] which achieve query complexities of ((d σv R//e) and O(d5/s + vv) R\ With minor modifications, the query complexity of the first algorithm can be reduced to oy e.). However, it remains unclear whether a similar reduction in query complexity can be achieved for the second algorithm. In comparison, our algorithm achieves polynomial improvement in d.
1.2 Additional related work
Stochastic convex optimization. SCO is a foundational problem in optimization theory and has been extensively studied for decades. In particular, SCO with VSGO has been studied under different assumptions on the objective function ff than the L-Lipschitz assumption we focus on in this paper. Notably, if the gradient of is 3-Lipschitz, the seminal paper [39] achieved an optimal error of ( 2 + σv / /V)) after T queries. We note that our guarantees for Problem I can be extended to the setting where the gradient of f is B-Lipschitz at the cost of only polylogarithmic factors since our bounds have polylogarithmic dependence
the Lipschitz constant of f. This follows because a function with 3-Lipschitz gradient which is minimized in a ball of radius R is itself ((BR)) in the ball.
Beyond the bounded variance assumption, [62] examines SGOs with heavy-tailed or infinite variance noise and shows that stochastic mirror descent is optimal in such cases. As for cutting plane methods, there a long line of work in deterministic settings which has sought to improve the query complexity and/or runtime; see c.g. [56, 40, 34].
Quantum mean estimation. Quantum mean estimation and the closely closely related problems of amplitude estimation and phase estimation have been extensively studied [1, 54, 32, 64, 14, 46, 31]. The seminal amplitude estimation algorithm [15] can be used to obtain a quadratic improvement on the query complexity for estimating the mean of any Bernoulli random variable. Building upon this result, [30] (whose query complexity is further improved by [38]) introduced a quantum sub-Gaussian mean estimator that achieves quadratically better query complexity than the classical counterpart while providing mean estimate with sub-Gaussian error, without requiring additional assumptions on the variance or tail behavior of the underlying distribution. Multilevel Monte Carlo methods have also been widely used in quantum algorithms [3, 42].
Quantum algorithms and lower bounds for optimization problems. There has been a rich study of quantum algorithms for classical optimization problems, including semidefinite programs [7, 13, 12, 37, 60), convex optimization [6, 59, 19, 41], and non-convex optimization [65, 21, 28, 43, 41]. Despite these recent progress in quantum algorithms using quantum evaluation oracles and quantum gradient oracles, their limitations have also been explored a series of works establishing quantum lower bounds for certain settings of convex optimization [25, 66] and non-convex optimization [66].
1.3 Notation
|l-Il the fg-norm. We define Bp(r, x0) fz e Rd -|=- zoll, 1 S Sr to be the ball of radius centered at wo, and use (r(r) == (r,r and B, (1, A halfspace is denoted by H (a e R2,6 E R) == {" E Rdd : a To 2 bj. For f: Rd + R. we let / = inf, fxx and call x E Rd e-(sub)optimat if f(z) f* + function f: Rd - i is L-Lipschitz if f(z) - f(y) S L|| - yll for all x., y E TR.. For two matrices A, B Rdxd we write A < B if x: Ax S Bx for all x E IRd The standard basis in H is denoted (ei...., ea). For random variables X, Y. we use (x))=
Σx p(x) log p(x) to denote the entropy of X, use HY = H(X, Y) - (X) to denote the conditional entropy of Y with respect to X, and use I(X;Y) = HX denote the mutual information between X and Y. The cardinality of finite set S is denoted [S].
We use Ō(-) and f2(-) to denote big-O notation omitting polylogarithmic factors.
1.4 Paper organization
We give a technical overview of the paper in Section 2 and conclude in Section 3. We prove our upper bounds for Problem 1 under ISGO, ESGO, and VSGO oracles (resp. Theorem and Corollaries and 4) in Appendix A. We establish our lower bounds for Problem I given either an ISGO or ESGO
5

---

oracle in Appendix B. In Appendix C, we present our quantum isotropifier and then apply it to obtain an improved bound for quantum SCO under prriance-bounder noise. In Appendix D, we review sub-exponential distributions and further discuss the relationships between the various stochastic gradient oracles we study. Finally, we collect miscellaneous technical lemmas in Appendix E.
2 Technical overview
In this section, present high-level overviews of our techniques. In Section 2.1, give overview of our stochastic culling plane method, based on an extension of the techniques of [53], which we to obtain our upper bounds for Problem 1. In Section 2.2, we give technical overview of lower bounds for Problem 1. We conclude in Section 2.3 with a discussion of our application to quantum SCO; we believe our quantum isotropifier subroutine discussed in that section may be of independent interest. The formal proof's of the results discussed in Sections 2.1, 2.2, and 2.3 can be found in Sections A, B, and C respectively.
2.1 Overview of our upper bounds for SCO
Recall that our main non-quantum algorithmic result is Theorem I, which says that Ö(Roj + d) queries to a (a,, 6)-ISGO suffice to solve Problem when 5 is anversepooynommilly small. We prove this upper bound using stochastic cutfing plane method via extension of the techniques of [53] (see Section A for formal proofs). Cutting plane methods are foundational class of algorithms in convex optimization which solve feasibility problems, for which we use the following formulation: (recall H> (a E gd E R) denotes the halfspace {o E Rd
b}):
Definition 7 (Feasibility Problem). For R' rr> O, we define the (R', (R',,))feasibll rr-fesibbillity problem as follows: We are given query access to a (potentially randomized) halfspace oracle which when queried at x E (2R outputs a vector 9n. E Rd ([]. The goal is to query the oracle at sequence of points .I. E (2(R') such that B2(R') (EETT H> (g2. 92, xt) does not contain ball of radius r (namely, any set of the form (r 2) for Rd We call an algorithm a T -algorithh for the (R', r) reasibbiyyyyyy problem if it achieves this goal with at most T queries.
variety of cutting plane methods [56, 40, 34] are (dd) for the (R', fea-sbbiiiy problem, where Ó-)) hides logarithmic factors d, R', and 1/r. Furthermore, is well known that solving the feasibility problem where the halfspace oracle is given by the negative gradient of suffices to solve Problem 1 using Ö(d) queries to exact gradient oracle, where Ó(-) hides logarithmic factors in R. d, I., and 1/c. (Technically, there also an additional post- post-processing step needed which we discuss later.) This reduction follows from the fact that by the Lipschitzness of f. every point in the ball B2(e/L, L, x²) = (2 Rdd ||2 - x=Il S L/L} is e-optimal. Therefore, setting r == e/L and R' = 2R so that L,(e/L,x*) C (R'))) (we can assume r R without loss of generality RL, the origin is e-optimal) and running of the aforementioned
since if
for the (R', (f)-rr-faiiiiiityy problem with the halfspace oracle given by - V f(), we must have queried fxx)) x, for some E B2(e/ L, x*). This
the oracle at an iterate H, such that - fxx()) implies I, is e-optimal by convexity:
f(x))
(V.(z)), s f()) f(z))+
Recently, [53], which broadly studies quantum algorithms for stochastic optimization in variety of settings, observed the above analysis can be extended to the setting where we only have access to an approximate gradient, which they capture as follows (paraphrased from Definition 5 in [53]):
Definition 8 (AGO). h(-)) is a a-approximaae gradient oracle (y-AGO) if when queried the (potentially random) output h(x) E Idd satisfies [}λ(x)) fx()) <
Rd.
In other words, a AGG h(-) gives an estimate of the gradient with at most y error in norm. Then running an Ödd)
for the (R' = 2R, = e/ L)--fssibbiiii problem as before, except with -h(-) as the halfspace oracle as opposed to - ff(x), implies there exists an iterate and c-optimal E B2(e/ L,x") such that -h, -h Zt, where he was the result of calling h(-) with input z; at

---

the t-th step. Thus, by convexity:
f(x)) - f()) + (2)())), 2)
= [(²) + (1e, te - z) + (V - b4 Tt - =) S f(x)) ) + + 4RT:
where the last inequality follows because = is e-optimal; ! < 0 by assumption; and 2 S f he ||]|= =|| 4Ry by the Cauchy-Schward inequality. Definition 8, and the fact that 22, E (2()') = B2(2R). In particular, if S e/(4R), then T; is 2e-optimal.
[53] used this observation to obtain then state-of-the- art quantum algorithms for Problem using quantum analog of the BSGO oracle (see Definition 2). In particular, they implement an c/ c/44R)-AGO at each step with high probability using quantum variance reduction procedure. While it is not explicitly stated, this analysis can be extended to the non-quantum setting by mini-batching. One can show that an e/(4R)-AGt query can be implemented using Ó + 1) queries to a vv-VSGO (-) with success probability at least 1 - E. where Ó(-) hides logarithmic factors in 1 1/c. Then choosing & appropriately to union bound the failure probabilities over all iterations, an adlgooggoi for the feasibility problem with the halfspace oracle given by this mini-batching procedure yields an Oddoo /e" + d) rate for solving Problem 1 given a -VSGO, matching the rate we recover in Corollary 4 as a result of our more general framework.
Our improvements over [53] are built on the key observation that control the error of the approximate gradient in 22-norm (it can be polynomially large), as long as we tightly control the error of the approximate gradient in a particular fixed ftrection-named the direction to the optimum x². To start, we refine Definition 8 as follows by defining a marginal approximate gradient oracle:
fact suffices only weakly
Definition 9 (MAGO). g(:--) is marginal (n 0,1 -p-apoooiemate gradient oracle ((n,I)- MAGO) if when queried at E Rdd, the (potentially random) output ğ(x, u) E Rd satisfies
l1āx,, u) f S T and (ī(x,, u) fz()), ai S n for û n///uil.
(4)
Next, consider running a cutting plane method for the (R' == 2R, r == min L, - problem, where the halfspace oracle at a query point x E Rd is given by - -(x x - x: x²). As before, there exists an iterate x; and e-optimal E B2(r, x²) such that -9. < 9 Ht where gr was the result of calling g(æ,, Fz- x²) at the t-th step. Then by convexity:
f(x)) - (=) + (V](()), 2)
= f()) + (gt, It 2) (Vf(z)) - Jr - x
V (())
9t, x= -
[((x)) + 2e 4RT,
where the last inequality followed because z is e-optimal: 3 by assumption; by Definition 9 and triangle inequality 4 < r/| x='| < 4ft;; and finally 5 < | fxx) ge ||=""*" - =|| S Tr S by Cauchy-Schward Definition 9, and the choice of r. Thus, if n I c/(4R) then x, is op-omtimal. Crucially, because cutting plane methods for the fcasibility problem have logarithmic dependence on l/r, polynomial bound on I" suffices to maintain Qud)-yueyy complexity for this problem.
Next, we show how to implement a MAGO using (a), -ISGO in the following lemma, proven in Section A:
Lemma 1. For any ö, E (0, x, Rdd; and n > 0, a query ğ(æ, u) to an (n, = m MAGO
can be implemented using K = O an log(2d/{) +1) queries to (a1, 6S-G O7(-). with success probability at least - 5d and without access to the input u.
de With 17 + c/(4R), Lemma implies that Ō Koo + 1) queries are enough to implement an
(e/(4I), e (V/(((A)) which suffices to ensure x; is 3e-optimal by the above analysis while also maintaining a polynomial bound on r. Critically, note that implementing each MAGO query does not require knowledge of the second argument u, which is important since the second argument to the MAGO depends x² in the above analysis. We also emphasize that the term 5 above cannot
7

---

be bounded by attempting to control the ertor of the MAGO in the direction x² 2; this is because not fixed in advance and indeed depends on gt-
Thus, leaving details regarding handling ō to Section A, combining Lemma 1 with an ((d) -ldg-ogoo for the feasibility problem suffices ensure iterate F, is 3e-optimal using O( / + d)-queries to an ISGO. However, it not a priori clear which of the ((d) iterates returned by this algorithm 3c-optimal. [53] solve an analogous problem in their setting via a post-processing procedure which iteratively refines the output of the first stage via binary search to ultimately return an Oct)mmali point (see also [33, 18, 5] for related procedures). In Section A, we carefully adapt this procedure to (a,, 6)-SGO, showing it can also be implemented with of /c2 + d) queries and thereby achieving a d-factor savings over using a VSGO as in the first stage described above. Finally, at the end of Section A we instantiate Theorem
achieve a new state-of of-te-of-thh-arr O(R2 + d)- complexity for Problem given a EESOO (see Corollary 3), and also recover the aforementioned Odd of / + d) rate given a VSGO as simple consequence (see Corollary 4).
2.2 Overview of our lower bounds for SCO
The starting point of our lower bounds for SCO with ISGOs and ESGOs is the connection between SCO and multivariate mean estimation problems, which has been widely used to derive lower bounds for SCO in various settings e.g. 53D. Specifically, as detailed in Section B.2, for any random variable X, we consider an instance of Problem 1 where f is defined as the expectation of collection of linear functions with an added regularizer term. The set of linear functions is parameterized by samples from X, which also determines the stochastic gradient, ensuring that it follows noise model of the same form as X. Moreover, finding an e-optimal point of I yields Ó(E -eestimmaee of B[X], thus establishing a reduction from the mean estimation problem to SCO.
Building on this reduction, we establish a lower bound for SCO with ESGOs by introducing variant of the mean estimation problem where the noise follows a sub-exponential distribution. Specifically. we construct hard instance in which the random variable X is parameterized by another random variable V, as detailed in Section B.1. We show that any algorithm approximating E[X] must retain significant mutual information with V. We then upper bound this mutual information in terms of the number of samples, yielding the desired lower bound for the mean estimation problem (see Lemma 11) and, consequently. for SCO with ESGOs (see Theorem 5). As corollary, we derive a lower bound for SCO with ISGOs (see Corollary 2). Regarding the mean estimation problem itself (namely, Problem 3), we note that similar lower bounds to Lemma 11 may be derived as corollaries of recent high probbbrbbabylity minimax lower bounds [45], but we provide our own analysis for completeness.
2.3 Quantum isotropifier and quantum SCO under variance-bounded noise
Our main technical ingredient of our improved bound for quantum SCO is an unbiased quantum multivariate mean estimation algorithm whose error is isotropic in the sense that it is small in every direction with high probability, which we refer to as quantum isotropifier. Adopting the notation of [53, Definition 1J. define having quantum access d-dimensional random variable X as the ability to query a quantum sampling oracle that produces a quantum superposition representing the probability distribution of X.
Definition 10 (Quantum sampling oracle). For d-dimensional random variable X, its quantum sampling oracle x is defined as
Sf IEER VPx(x)de (x) @ Igarbage(x:))
Ox 10) -
(5)
where px (x) represents the probability density function of X.
Using Ö(g/E) queries to quantum sampling oracle Ox of any random variable X e Rd with variance d², our quantum isotropifier outputs an unbiased estimate j of E[X] such that for any unit vector E Fd. (v. - B[X] is at most e with high probability. This allows us construct a (ar, ISGG using Ö(rv log(1/8/ar) queries to -VSQOO Combined with our stochastic cutting plane result in Theorem 1, and with appropriate choices of or and d, this leads to our
8

---

improved O(dRov/e /e) query complexity for quantum SCO in Theorem 7, whose proof can be found in Section C.5.
Next, we provide a technical overview of our quantum isotropifier, which builds on the quantum multivariate mean estimation framework of [22]. We begin by considering simplified scenario where the random variable X is bounded and satisfies || S 1. In this case, [22] first implements a directional mean oracle that approximately maps (g) to e((,, [g) for a query & E RR, This oracle requires only constant number of queries to the quantum sampling oracle Ox provided that |Eig, X < |[[ To estimate E[ using this directional mean oracle, [22] applies it to the superposition Σ Egease 1g), where G&d is d-dimensional grid defined as
1 2m
: kE (o...... m- 10.....m--1] 11} c
( 1 2
G =
m
2
The resulting quantum state approximately decomposes as a tensor product
Σ gJEG
BiX,) 10,)
Then, phase estimation can be performed independently in each dimension to estimate each coordinate of B[X], similar to the quantum gradient estimation algorithm in [36].
The error in this procedure has two parts: the error in the quantum directional mean oracle and the error from quantum phase estimation. The first part of the error arises the directional mean oracle is accurate only for grid points g E G with Kg E[X]>| S [|[[X]]]_ In Section C.2, we provide an improved error analysis, showing that only an exponentially small fraction of g E G do not satisfy this condition. Hence, in the analysis perfect one that performs the map [g) -> ef(a: (g) exactly for all g G and the resulting quantum state only has an exponentially small change in trace distance.
m
can effectively replace the directional mean oracle by
As for the second part of the error, we note that while the phase estimation procedures in different coordinates are independent, i.e., for any j * k: the estimates رu, and iúg of TR. [[X)) and [[Xx] are sampled independently from two distributions, their biases may still contribute positively in certain directions. Consequently, even if each jı, has a bounded error satisfying Aá - E [X,]| S e, there may
exist a unit vector u E RRd such that [[X] w)| = @(evd) which is larger than the per-coordinate guarantee by factor of vd. In this work, we demonstrate that the additional vdd overhead can be avoided by replacing the original phase estimation with the boosted unbiased phase estimation algorithm from [57]. For each coordinate j. this algorithm produces an unbiased estimate ùú that has bounded error رما E[X,]I I e with high probability. Consequently, for any unit vector u E Rd the error (p _[ u) can be approximated which follows sub-Gaussian distribution with variance ((a2) (s [61]. This implies that jú not only is unbiased but also has isotropic noise.
weighted sum of zero-mean bounded random variables,
We then extend this result to unbounded random variables, as detailed in QUnbounded (Algorithm 3) in Section C.3. Following a similar approach to [22], we decompose X into a sequence of truncated bounded random variables and estimate each one independently. We show that the isotropic noise property is maintained throughout this process. Despite our use of the unbiased phase estimation subroutine [57], the output of QUnbounded may still be biased due to truncations. Notably, while [53] developed a general debiasing scheme for quantum mean estimation algorithms that treats them as black box procedures, directly applying their scheme to QUnbounded would compromise the isotropic noise property. As detailed in Section C.4, we utilize the multi-level Monte Carlo (MLMC) technique [26] to address this issue. Specifically, we develop modified version of the MLMC variants introduced in [10, 4, 53) that preserves isotropic noise while maintaining unbiasedness.
To illustrate our approach, suppose we want an unbiased estimate whose error is smaller than in any direction with high probability. Let gاا denote the estimate obtained by running QUnbounded to accuracy 8,e, i.e., ((GG) - E[[X,, u\) $ Bye with high probability, where 3, a chosen coefficient. Then, our new estimator is:
Draw j Geom
E N, compute j + -2() + 22(0 - p11-11).
2

---

This estimator is unbiased as long as lim Pg = O. given that
E | = 3 + E P[J=
- Elab 111 - lim 11 = [E[X].
10000
Moreover, the expected query complexity of the new estimator ja is larger than that of a which is of order ((o/e), by a multiplicative factor of
+
Σ = -363 + -1+ 2- 1=1
+ +.)1))
j=1
This factor is a constant if we choose 3, 2- for any C> Furthermore, we show later that fi also satisfies ( E[X], u)l S (e)) with high probability long as C' is constant, preserving the isotropic noise property. our full algorithm, Algorithm Section C.4, we choose C' = 2 for simplicity.
3 Conclusion
We define a new gradient noise model for SCO, termed isotropic noise, for which we achieve tight upper and lower bounds (up to polylogarithmic factors). Our upper bound improves upon the state-of- the-art (and in particular SGD) in certain regimes, and corollary we achieve a new state-of-the-ard complexity for sub-exponential noise. We then develop subroutine which may be of independent interest called a quantum isotropifter, which converts into an unbiased estimator with isotropic noise. By combining our results, we obtain improved dimension- deessinnddeeedentt rates for quantum SCO.
bounded quantum sampling oracle
One limitation of our work is we only resolve Problem I under stronger assumptions on the noise (e.g.. sub-exponential noise in Corollary 3), whereas the rate we achieve under a VSGO (Corollary 4) is worse by roughly a d-factor. Another limitation is that our improved quantum rates are dimension- dependent, and have unclear long-term practical impact. Regarding the former, we note that series of works have shown that dimensions-dependeee improved scaling 1/c in a variety of settings [24, 25, 66].
is necessary for quantum algorithms to achieve an
We hope that by identifying the natural open problem Problem and developing techniques to resolve under stronger assumptions, we leave the door open future work on resolving fundamental trade-offs between the variance, Lipschitz constant, and dimension in SCO. We believe charting these trade-off's is important since it would yield sharp understanding of the precisions which algorithms such as SGD are superseded by other methods. Such questions have long been understood in the deterministic setting, and we believe our work an important step in resolving them under stochasticity and in quantum settings.
Acknowledgments
Thank you anonymous reviewers for their feedback. Aaron Sidford was funded in part by Mi- crosoft Research Faculty Fellowship, NSF CAREER Award CCF-1 184455, NSF Grant CCF1955039, and PayPal research award. Chenyi Zhang was supported in part by the Shoucheng Zhang graduate fellowship.
References
[1] Daniel S. Abrams and Colin P. Williams. Fast quantum algorithms for numerical integrals and stochastic processes. arXiv preprint quant-ph/9908083, 1999.
[2] Alekh Agarwal, Martin J Wainwright, Peter Bartlett, and Pradeep Ravikumar. Information- theoretic lower bounds on the oracle complexity of convex optimization. Advances in Neural Information Processing Systems, 22, 2009.
[3] Dong An, Noah Linden, Jin-Peng Liu, Ashley Montanaro, Changpeng Shao, and Jiasu Wang. Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance. Quantum, 5:481, 2021.
10

---

[4] Hilal Asi, Yair Carmon, Arun Jambulapati. Yujia Jin, and Aaron Sidford. Stochastic bias-reduced gradient methods. Advances in Neural Information Processing Systems, 34:10810-10822, 2021.
[5] Hilal Asi, Daogao Liu, and Kevin Tian. Private stochastic convex optimization with heavy tails: Near-optimality from simple reductions, 2024.
[6] Brandon Augustino, Dylan Herman, Enrico Fontana, Junhyung Lyle Kim, Jacob Watkins, Shouvanik Chakrabarti, and Marco Pistoia. Fast convex optimization with quantum gradient methods, 2025.
[7] Brandon Augustino, Giacomo Nannicini, Tamás Terlaky, and Luis F. Zuluaga. Quantum interior point methods for semidefinite optimization. Quantum, 7:1110, 2023.
[8] Aharon Ben-Tal and Arkadi Nemirovski. Lecture notes: Optimization iii (convex analysis, nonlinear programming theory, nonlinear programming algorithms). Lecture Notes, ISYE 6663, Georgia Institute of Technology & Technion Israel Institute of Technology, 2023.
[9] Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive algorithms and stochastic approximations, volume 22. Springer Science & Business Media, 2012.
[10] Jose Blanchet and Peter W. Glynn. Unbiased Monte Carlo for optimization and functions of expectations via multi-level randomization. In 2015 Winter Simulation Conference (WSC), pages 1666--667..0 IEEE, 2015.
[11] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223-311 2018.
[12] Fernando G.S.I. 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. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1-27:14. Schloss Dagstuhl-Leibniz-Zenniee
fuer Informatik, 2019.
[13] Fernando G.S.L. Brandão and Krysta M. Svore. Quantum speed-ups for solving semidefinite programs. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 426. IEEE, 2017.
[14] Gilles Brassard, Frederic Dupuis, Sebastien Gambs, and Alain Tapp. An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance. 2011.
[15] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53-74, 2002.
[16] Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357,201: 2015.
[17] 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.
[18] Yair Carmon and Oliver Hinder. The price of adaptivity in stochastic convex optimization. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 772-774. PMLR, 30 Jun-03 Jul 2024.
[19] Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu. Quantum algorithm for estimating volumes of convex bodies. ACM Transactions on Quantum Computing, 4(3):1-60, 2023.
[20] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Ronald de Wolf. Quantum algorithms and lower bounds for convex optimization. Quantum, 4:221, 2020.
[21] Andrew M. Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, and Chenyi Zhang. Quantum simulation of real-space dynamics. Quantum, 6:680, 2022.

---

[22] Arjan Cornelssen, Yassine Hamoudi, and Sofiene Jerbi. Near-optimal quantum algorithms for multivariate mean estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 33-43, 2022.
[23] John C. Duchi. Introductory lectures on stochastic optimization. The mathematics of data, 25:99-186, 2018.
[24] Ankit Garg. Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. No quantum speedup over gradient descent for non-smooth convex optimization, 2020.
(25] 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:29874-29884, 2021.
[26] Michael B. Giles. Multilevel Monte Carlo methods. Acta Numerica, 24:259-328, 2015.
[27] András Gilyén and Tongyang Li. Distributional property testing in a quantum world. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2020.
[28] Weiyuan Gong, Chenyi Zhang, and Tongyang Li. Robustness of quantum algorithms for nonconvex optimization, 2022.
[29] Branko Grünbaum. Partitions of mass-distributions and of convex bodies by hyperplanes. Pacific Journal of Mathematics, 10:1257-1261, 1960.
[30] Yassine Hamoudi. Quantum sub-gaussian mean estimator: In 29th Annual European Symposium on Algorithms (ESA 2021). Schloss Dagstuhl-LeibnizzZarni Zentrun für Informatik, 2021.
[31] Yassine Hamoudi and Frédéric Magniez. Quantum Chebyshev's inequality and applications. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019),
2019.
[32] Stefan Heinrich. Quantum summation with an application integration. Journal of Complexity, 18(1):1-50, 2002.
[33] Arun Jambulapati, Aaron Sidford, and Kevin Tian. Closing the computational--ueryy depth gap in parallel stochastic convex optimization. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 2608-2643, PMLR, 30 Jun 03 Jul 2024.
[34] 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. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 944-953, Chicago IL USA, June 2020. ACM.
[35] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M. Kakade, and Michael I. Jordan. A short note on concentration inequalities for random vectors with subgaussian norm, 2019.
[36] Stephen P Jordan. Fast quantum algorithm for numerical gradient estimation. Physical review letters, 95(5)0050501, 2005.
[37] Iordanis Kerenidis and Anupam Prakash. quantum interior point method for LPs and SDPs, 2018.
[38] Robin Kothari and Ryan O'Donnell. Mean estimation when you have the source code; or, quantum Monte Carlo methods. In Proceedings the 2023 Annual ACM-SIAM Symposium on Discrete Algorithums (SODA), pages 1186-1215. SIAM, 2023.
[39] Guanghui Lan. An optimal method for stochastic composite optimization. Matherntical Programming, 133(1-2):365-397, 2012.
12

---

[40] Yin Tat Lee, Aaron Sidford, and Sam Chiu- Wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1049-1065, Berkeley, CA, USA, October 2015.
IEFE.
[41] Jiaqi Leng, Ethan Hickman, Joseph Li, and Xiaodi Wu. Quantum Hamiltonian descent. Bulletin of the American Physical Society, 68, 2023.
[42] Xiantao Li. Enabling quantum speedup of Markov chains using a multi-level approach, 2022.
[43]
Yizhou Liu, Weijie Su, and Tongyang Li. On quantum speedups for nonconvex optimization via quantum tumneling walks. Quantum, 7:1030, 2023.
[44] Gábor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed distributions: A survey. Foundations of Computational Mathematics, 19(5):1455-199 2019.
[45] Tianyi Ma, Kabir A. Verchand, and Richard J. Samworth. High-probability minimax lower bounds, 2024.
[46] Ashley Montanaro. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A, 47110118))220150001,,2 2015.
[47] Arkadi Nemirovski. Efficient methods in convex programming, 1994. Lecture notes.
[48] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574- 1609, 2009.
[49] Jurij Evgen evive Nesterov. Lectures convex optimization. Springer optimization and its applications. Springer Nature, Cham, second edition edition, 2018
[50] Warren B Powell. A unified framework for stochastic optimization. European Journal of Operational Research, 275(3):95-821, 2019.
[51] Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400 407, 1951.
[52] Aaron Sidford. Optimization algorithms, 2024. Lecture notes; compiled on March 18, 2024.
[53] Aaron Sidford and Chenyi Zhang. Quantum speedups for stochastic optimization. Advances in Neural Information Processing Systems, 36, 2024.
[54] Barbara Terhal. Quantum algorithms and quantum entanglement. PhD thesis, University of Amsterdam, 1999.
[55] MTCAJ Thomas and A Thomas Joy. Elements of information theory. Wiley-Interscience, 2006.
[56] P.M. Vaidya. new algorithm for minimizing convex functions over convex sets. In 30th Annual Symposium Foundations of Computer Science, pages 338-343, 1989.
[57] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, and Giacomo Nannicini. Quantum tomography using state- prtteerrrrartiion unitaries. In Proceedings of the 2023 Annual (CM-SIAM Symposium on Discrete Algorithms (SODA), pages 1265-1318. SIAM, 2023.
[58] Joran Apeldoom and András Gilyén. Improvements in quantum SDP-solving with applica- tions. In 46th International Colloquium on Automata, Languages, and Programming (ICALP fuer Informatik, 2019.
2019). Schloss Seaettull-Libbii--eieie
[59] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimiza- tion using quantum oracles. Quantum, 4:220, 2020.
[60] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP. solvers: Better upper and lower bounds. Quantum, 4:230, 2020.
13

---

[61] Roman Vershynin. High digen-iiiensooaal probability, volume 47 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2018, An introduction with applications in data science, With foreword by Sara van de Geer.
[62] Nuri Mert Vural, Lu Yu, Krishna Balasubramanian, Stanislav Volgushev, and Murat A Erdogdu. Mirror descent strikes again: Optimal stochastic convex optimization under infinite noise variance. In Conference Learning Theory, pages 652102. PMLR, 2022.
[63] Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, New York, NY, 1st ed edition, 2019.
[64] Pawel Woejan, Chen-Fu Chiang, Daniel Nagaj, and Anura Abeyesinghe. Quantum algorithm for approximating partition functions. Physical Review A A-Atomic, Molecular, and Optical Physics, 80(2)022340, 2009.
[65] Chenyi Zhang, Jiaqi Leng, and Tongyang Li. Quantum algorithms for escaping from saddle points. Quantum, 5:529, 2021.
[66] Chenyi Zhang and Tongyang Li. Quantum lower bounds for finding stationary points of nonconvex functions, 2022.
[67] Yexin Zhang, Chenyi Zhang, Cong Fang. Liwei Wang, and Tongyang Li. Quantum algorithms and lower bounds for finite-sum optimization, 2024.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See the results section: Section 1.1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yss]
Justification:
See the conclusion: Section 3.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Justification:
Full proof' are given in the appendices. See Section 1.4 for roadmap of the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: Our results theoretical.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [NA]
Justification:
Our results are theoretical.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
cublic/guides// wwweeeoaaisisoonneae.o onnolicy))))) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips.co.. wttpccccpppccccceecooc.cccccccct htwubli/guuudes/////eee //ooeeeooebeseeeeeeeeeeee
/ttpe//uuuieeeeouuuuuibiiiiii cemmisssionn weriiisssinnoooiiiioeeoo oniioniy)y for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our results are theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our results are theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
17

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our results are theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:
Answer:
[Yes]
Justification: conforms to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is largely theoretical and consequently we do not expect broad societal impacts (beyond further research and educational use) without further work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is theoretical work and we do not foresee any such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (bttps://neun) //tp:r//eeu...eeeeeee http//rrpssce/ooofeeeeeeeeeeeeee cc//oonfeeeeccc/2225111111 for what should or should be described.
21

---

A Upper bounds for SCO under ISGO, ESGO, and VSGO oracles
In this section, we prove an upper bound for Problem given a (0,, 6I-SGO in Theorem 1, and then instantiate the result achieve upper bounds for Problem 1 given either a og-ESGO or vv-VSGO in Corollaries 3 and 4 respectively. Given an ISGO, our algorithm for Problem 1 proceeds in two stages. In Section A.I, we give stochastic cutting plane method which utilizes a (a), -ISGO to return a finite set of points with the guarantee that at least one of the points is e-optimal. Then in Section A.2, we show how to use a (01, 83-ISGO to obtain an approximate minimum among this finite set of points. We note that all results and discussion in Sections A. and A.2 are stated in the context of solving Problem given (ar, 6)-ISGO, unless we explicitly specify otherwise. Finally, we put everything together and prove Theorem 1 in Section A.3.
A.1 Finding candidate solutions via a stochastic cutting plane method
In this subsection, we show how to obtain finite set of points with the guarantee that at least one of them is e-optimal via stochastic cutting plane method the setting of Problem given (a,, 6)- ISGO. Cutting plane methods solve feasibility problems, for which we will use the formulation of [52, Definition 8.1.2], except we translate from distance bounds in the Lo -o-oorm to distance bounds in the 62 f2-norm.
Definition 7 (Feasibility Problem). For R' 2 2 O, we define the (R)r)feasibility problem as follows: We are given query access to a (potentially randomized) halfspace oracle which when queried at x E (2) ), outputs a vector Ir E Rdd {0). The goal is to query the oracle at a sequence of points "TT E (R') such that (2()))) radius (namely, any set of the form (r(r, z) for R(). We call an algorithum a T -alloorithm for the ( RR' feasiibiiyyy problem if it achieves this goal with at most TT queries.
( Quegzy Hz (gz 22, xt) does not contain a ball of
We give a standard query complexity for the RR', .)) feasibiityyy problem in the following proposition. For completeness, we also give a standard short proof using the center of gravity cutting plane method, but we emphasize that our results are agnostic to the choice of cutting plane method used to prove Proposition 1. See, e.g., [56, 40, 34] for other cutting plane methods with similar query complexities (and which may have improved runtimes).
Proposition 1. There exists an Oddogg(R' /ag)-alo for the (R)-)eeasiibiliy problem.
Proof. We apply the so-called center of gravity method, e.g.. [8]. For iterations t = 1, .... the center of gravity method queries the halfspace oracle at the origin for = 1 (the center of gravity of B2(RR)) and at the center of gravity of the set B2 (P²) NkE Hz (gz, 9e. 2x) for L >>> 1, where Th E Idd denotes the iterate at step k: and 9z, E Id denotes the halfspace queried at I' during step k. Recall that the volume of d-dimensional Euclidean ball (equivalently, fg-ball) of radius > 0 is h(d)- 3d, where h is some function of the dimension d which won't 't matter in the following. Then letting vol(-) denote the volume of a set, we have vol( B2()")) = h(d)- (R')d, and the volume of (o(R')Nee NREj. H (gou I2. ax) Grünbaum's 's theorem [29] yields vol(S.) < (1 - 1/e)* vol( (2()))) and the result follows.
any Euclidean ball of radius is (d)) yd Letting S, == (2()))
Ix, for t E N,
L
is well known that solving the feasibility problem where the halfspace oracle is given by the negative gradient of I suffices to obtain finite set of points such that at least one is e-optimal [47, 40J. [53] demonstrated that this is still possible with stochastic estimates of the gradient, provided that - V is approximated to sufficiently high accuracy in the fz-norm with high probability at each iteration by averaging over multiple samples. Our key observation is that the analysis of [53] mainly relies on controlling the error of the gradient estimator in single direction, namely the one-dimensional subspace spanned by V₁- x², where V, is the current iterate. A (a, -I-GGGO with å sufficiently small allows us to control this error with fewer samples than, for example, o oVSGGO (Definition 3), allowing for savings of up to a multiplicative factor in the complexity of estimating the gradient at each step when compared to a- VSGO or oBBGGO
Toward formalizing this discussion, we first define a marginal version of the r--approximate gradient oracle specified in [53, Definition 5]. Note that this definition still allows us to control the error of the estimator in formo This will be necessary to obtain our guarantee, but we will only need to weakly control this error which can be polynomial in d.
22

---

Definition 9 (MAGO). ((--)) is a marginal (n 2 0, 2 Oj-approximate gradient oracle ((n, I)- MAGO) if when queried at x; u E RR,, the (potentially random) output g(x, u) E RR satisfies
(0(x,,) V < P and (ī(x, u) Vf(x), xلل S 1 for ū == =//lull
(4)
Next, we show that an (n) .7y d) -MAGO can be implemented with high probability using (01, 6)- ISGO without knowledge of the second argument, the directional input u.
Lemma 1. For any ó, 5 E (0, 1): x; E TR;; and v > O, a query ((z, u) (n, T= nvd) can be implemented using K = O( dry"
ei, log(2d/E) +1 queries to (a1, 6)-SGO (,),), with success
probability at least - Ç 5dK and without access to the input
Proof. For K E N be chosen later, consider the estimator 7 = K ELE[K] 7g for 7,,..., 7x id Or(x),, which does not require knowledge of u. Let {ueFee(d denote any orthonormal basis of R such that = wu/lull, and define for all & E [c]:
( =
1 K
Σ KE[R]
(()) where y( = (Zx - Vf((), uz) for & E [K].
< for all (k E [K] [d] with probability at least 1 ōdK by Definition 4 and a union bound. Then conditioning on the latter event E, Hoeffding's inequality [63, Proposition 2.5] yields for all é E [d]:
Note that EY( = O, and (
P
P|TTO
1
2 2t
s 2exp
- -Kdt
for all t t22 0.
20
Choosing K = 0 بi log 2d/E) +
gives P (Ix((0) (1)
2 E
S E/d all E [d], in which case
( S 1 3
P
sup [E
ZZ
V fxx), us)l 5n
=P
sup
[[ 2 (1 -0 5dk) 2 1- 5dK
EE|d]
by union bound. Finally, note that the event E' implies the first condition in (4) since then
1Z vf(z)] =
7 V f(x), ue) S nvd.
#E|4]
and the second condition in (4) follows because recall we chose U1 u/ u/||u||-
Next, we show how to obtain a finite set points such that at least one is e-optimal using an appropriate MAGO. Critically, the second argument to the MAGO must be allowed to depend x* However, this does not pose an issue when we ultimately instantiate the MAGO queries via ISGO queries since doing so does not require any knowledge of the second argument to the MAGO, per Lemma 1.
Lemma 2 (Obtaining candidate solutions via the feasibility problem). Suppose R',r > 0 are such that (2 x²) C B2(R') and f(2) s f(x*) + c/2 for all B2(r, Then given mVAG-MAGO g(--)) where only the second argument can depend on x" and T T-algorithm for the (R', r) feasibiltyyy problem, and additionally supposing e/(4r), we can compute a finite set of points C B2(R') with [S| = such that minges f(x) S f(xx) +
(1) = ,
Proof. We run the -algorrithm for the (R', reasiiiibyyy problem with the halfspace oracle at point x E dd given by -ğ(x, - x*). By definition, this produces a sequence of points S == {a, e (e(rr such that (2( NeeMT H>(-9x - xx) does not contain a ball of radius r, where -9t denotes the output of the halfspace oracle the 1-th step (i.e., St was the result of the oracle pad S with
call T( x))). (If the T- -algoriihh terminates with less than T queries,
23

---

duplicates.) Note that we can terminate immediately if the halfspacc oracle outputs Jr = 0 at some step & since then
It x*
f(x)) - ((x)))((=)55))
xx) -Vf(xx) - 9t, It --)=x))- x=) 2R' v)(zz)) - 9t,
S
2*1
by convexity, the fact that 24, 2,, x²' E B2(R"), and the definition of 5( I2 x²). Then supposing
ge * O for all E [7]. it must be the case that at some iteration / E [7]. there exists E B2 such that -9. 2 < -9t 24. Then by convexity
f(xx) - f() + (V)( Ft 2)
= (2) + (g), Jt 2) + (V((
gr, Jt xx)
(3))
gt: x - 2) S [(x')( +
where the last inequality followed because ! < 0 by the definition of 2; we have 2 S n - x"1 <
2 S. e/4 by the definition of ğ( Te. =x);; we have 3 < Pr S <//4 by Cauchy-Schward the
definition of g( 2t x²), ) and the additional assumption on r; and finally is e/2-optimal. O
Finally, we give our main result for this subsection:
Lemma (Obtaining candidate solutions via an ISGO). For T Oddlog(d RL/c)), there exists an algoritium which returns finite set of points S C (2R) with |S| = T and minges fz) S f(x)) + e using
M ( R20t de
+1)) queries to (a,, 07()
log(2a)T/)++1))
and with success probability at least 1 8dM.
Proof. We first apply Lemma 2 with R' == 2R and minf 2 41' _ (with i and [ := v/va as in Lemma 2). Note that we can assume c E (0, RL) without loss of generality as otherwise the origin is e-optimal, in which case R 2 r, implying x2(r,x") S (R''). Furthermore, every point in B2 (r, x*) is / /2-optimal given that f is L-Lipschitz. Thus, combining Lemma 2 with Proposition 1, we can obtain S with
sR
T Od /r) = Old (((L)) = Oddog(( + RL/e))
queries to a (1) aR r d) The result then follows by instantiating each MAGO query per Lemma 1, and the final success probability follows from union bound.
A.2 Approximate minimum finding among a finite set of points
Here show how to an ISGO to obtain approximate minimum among finite set of points SC Rd. (As a reminder, Section A.2 is stated in the context of Problem I given access to a (aI, 6)- ISGO, unless solves the same problem except with a (quantum) BSGO (recall Definition 2).² At a high level, the procedure involves iteratively replacing pairs of points (x, x') in S with point 5 the line segment between x and z', with the guarantee that the objective value of 2 is (approximately) at least as good as that of both æ and x'. This is done in multiple levels, eventually comparing pairs that were the result of previous comparisons, until only a single point remains. For a pair (z. x²), the point T is computed via a binary search procedure on the line segment between them using the ISGO. Critically, analogously to the main result of Section 1, a (a, -)-GG allows for up to a d-factor savings when implementing this binary search over a -BSGO or -SGG.
specify otherwise.) To do so, we adapt the techniques of [53, Section 4.2], which
To start, Algorithm 1, which is stated independently of the context of Problem I, gives a procedure for computing an approximate minimum over [0, 1] of one-dimensional Lipschitz convex function, given access to a sequence of approximate first-order derivatives (see Line 4). We will ultimately use Algorithm 1 to obtain z for a pair (I. x') as discussed above. Algorithm and its analysis are based on Al Algorithm& in [53].
An alternate procedure for solving this problem via a BSGO was given in [33, Proposition 3]. However, unlike the procedure of [53, Section 4.2], it is not clear how to adapt their techniques to an ISGO (or even a VSGO). See also [18, 5] for related procedures.
24

---

Algorithm 1: Inexactt.inessarcchh]]]]]]
Input: Convex G-Lipschitz h + IR, target accuracy c'
Output: E [0, s.t. h(2) I min ((2) +
2p
O, 2, +-1
2 while 2, zt. > e/G do
Zm <- (z, zt)/2
Let them
be s.t. Bi.m (=())) S 56/4
< 6 then return f- 2m
if' Usm > 0 then 2r + 2m else 21 f-
7 return E 6 2t
Lemma 4 (Algorithm 1 guarantee). Given differentiable, convex, G-Lipschitz h: R + R and 0, Algorithm / terminates after Ollog(G/c') iterations' and returns ž E [0,1] such that h(2) & min h(2)+
Proof. The iteration bound is immediate from the fact that each iteration halves the length of [zg. 2,] As for correctness, if Algorithm I terminates on Line 6, then |h' (zm)) S e'/2 by triangle inequality, in which case convexity implies for all z [0, 1]:
h(z)) S h(z) + I (Zm - 2) - h(z)) + [=()))) [(2m)]]== Izm =| S h(=)
On the other hand, suppose Algorithm terminates on Line Pick any x" E argmin h(2), and we claim Algorithm maintains the invariant =" E [ze, =z] This follows by induction because the condition ü.... 0 in Line 6 implies ü... e/4 due to the failure of the termination condition in Line 5, in which case h 1/((2 (2m) > by a reverse triangle inequality. Then
h (2m) =²) 2 (((m) h(=*) 2
3m - 2 2" E [ze, 2m]-
The case where ū.m. < 0 in Line 6 is analogous. To conclude, the termination condition of Line implies the following in Line by the invariant and Lipschitzness:
2 24 S / = 12e - 2"1 e/GG = h((z)) S h(2²))))))))))))))) +é'
Before proceeding, we provide a version of Lemma where we don't t control the error of the MAGO estimator in f2-norm, allowing for a potential logarithmic-factee improvement the ISGO query complexity needed to implement the MAGO as well as a higher success probability. Technically Lemma 5 is not necessary to prove our ultimate guarantee Theorem where we do not explicitly state polylogarithmic factors for brevity, but we include it for completeness and to make it clear what aspects of the MAGO we actually need for individual lemmas.
Lemma 5. For any 5,E E (0, 1); x, E Rd; and > O, query ğ(a, u) to an (n, -o) can log(2/5) 1) queries to (a1, 8)-ISO Or(,), with success be implemented using K = ( dip
probability at least - - 8K and without access the inpul u.
Proof. Consider the estimator Z R EvE(K] Zt for Z1, knowledge of Define
ZK Oz(z), which doesn't 't require
Y T K
1
Σ Ya where Ye = (Zx- - Vf(x), u) for & E [K]. KE|K]
Note EY, = 0 and Y& S <a//vd for all E [K] with probability at least - SK by Definition and union bound. Letting& denote the latter event, application of Hoeffding's 's inequality implies P|| 2 El < &. in which case
P V f(() u) < <n = P 1
P[ N 21 1 8K.
An iteration is single execution of Lines 3-6.
25

---

We now use Algorithm 1 as subroutine to obtain T for pair (2, 22)
Lemma 6. For é' > 0 E (0,1); and x, x' E IR with D == || x/I, there exists algorithm
which computes T, a convex combination of x and xf such that f(Ø) S minxe(o.1] J (x++((a' -x)d using most
M M
D2 de
log (gg(MM (0) for M' = =((log(D//))
queries to a (ar, 6I-GO Or(,), with success probability at least - -MM.
Proof. If D- O, we return Otherwise, define 2 = + A(x' x) for X E R, and let
h(A) = f(xx). Note that h is DL-Lipschitz since
h'(A) (V fzx), x' - x)
(((A)) V fxx) || x|1 DL.
Note that for a given À E and y > 0, we can obtain ūx E R such that رش - (2())) I using a single query (</ D, oc) o MMAGO 0(., +). Indeed, with Z g(xx, x' x) and ūx < (Z, x' z).
μu - h (A)) kkZ Vf(xx), - 2)1 S
Furthermore, for & E (0, each query to )(-;))
be implemented with K dn log(2/5") + +1) queries to (01, 6I-IGO and success probability 1 - 5K by Lemma 5.
of Dioi
Putting this together, we can obtain üx such that ي - ((()) S with o( ai di log(2/E)) +1) queries to (o,, 6)-ISGO and success probability 1 1- 5' 8K. Com- bining this with the fact that DI--iipchhiz, clear that <- InexactLineeSarchhh, e') can be implemented with
M M= M-O(M AM
o'ot log log(M' ((SM for M' = O(log(DL/E))
de
queries to a (a,, 6I-IGO, with, by a union bound, success probability at least 1 5 5 - 8M. To conclude, note
f(i = ==x==x)== = h()) -
min h(A) = min f(r + A(x' - =))).
xE xE|o,1]
Finally, we give our main result for this subsection:
Lemma (Finding the best among a finite set of points). For T E N, suppose S= (a+ E RR herz such that ||x, - 23 D for all i,j [T]. Then for >> 0 and & E (0, there an algorithm which returns a point x in the convex hull of S such that f(r) & minges fxx) + using at most M(T 1) queries (01,8)-ISGO O,),,,or
M -=0(MM (M
(D log log(M' (M' log + +1)) with M' de2
dd2
and it succeeds with probability at least 1 - --5M log
Proof. For pair x, x' in the convex hull of S. we can apply Lemma to obtain E, a convex combination of x and x' such that f(ī) S (f() <//log using
M M=Ol M-0(MM M
log" (Tg lo' log T/5) T/55+1) de
+1)) for M' = O(log( lg T/e))
queries to (aI, -SSGGO, with success probability - E/ log T 5M.
Next, we assume without loss of generality that [T] is a power of 2, as I can be duplicated if this is not the case. Then consider a complete binary tree with leaves, and define the b-th layer for & E {0) J [logg7) to denote those vertices which are distance É from a leaf node. (In other words, the O-th layer contains the leaf nodes, and the final (log, 7)-th layer the root.) We assign
Di, Zr to the leaf nodes, and iteratively populate the é-th layer of the tree for l = 1,2,..., logg T
26

---

via the following process: For each node in the f-th layer with children æ and x' in the (L + 1)- th layer, we assign to that node the estimator described above with inputs a and x'. Assuming
an E argmin (1) without loss of generality, note that conditioned on all of the estimates along the path from the leaf 21 to the root succeeding, which happens with probability at least
1 - 8M log T by union bound, the value of f at the root xr (which we output) can be bounded as fx+) I f(x1) + e. The final query bound follows from the fact that we call the estimator T 1
times, since there are T non-leaf nodes in the tree.
A.3 Putting it all together
We now restate and prove main guarantee for Problem 1 given (0-,B)-
Theorem 1. Problem 1 can be solved with probability at least 2/3 in O of/e² + d) queries to (ar, -1500 for any 8 < Mi( where M = Ō11.
Proof. By Lemma 3, we can obtain finite set S S B2R2 with |S| = O(d) and min f(z) s f(**) + c/2 using K Ö(Roof/e² + +d) queries to the (01, 6)-ISGO, with success probability at least 9/ 10 - 5dK. Then giving this set S as input to Lemma 7, we can obtain x E (2R) such
that f(x) S minyrss (x²' + c/2 using K" = oRRoo 2 + d) queries to the
with
success probability at least 9/10- - 5- δ
R²
d2 + +1) Then (x) & f(x') + with probability at
least 2/3 by the valid range of 5 and a union bound, and the total number of queries is K + K" 0(1607/e2 + d).
Next, we instantiate Theorem obtain upper bounds for solving Problem I with a EEGESGO or vv-VSGO. First, we show in the following lemmas that ISGOs can be implemented using ESGOs and VSGOs respectively. In particular, Lemma says that an ISGO query can be implemented with an ESGO at the cost of only log factor, whereas Lemma 9 says that doing so with a VSGO additionally picks up v factor. Indeed, this /d-factor is the reason our rate for solving Problem I with a VSGO is d-factor worse than solving Problem with an ISGO or ESGO. We note that the proof of Lemma 9 is based on ideas from [53, Lemma 7].
Lemma 8. For any og > 0 and 8 E (0, 1), a Eg-E is a (ag (0g(2/6),))-133))
Proof. For any E (0, 1) and any unit vector u Rd. by Eq. 2 we have
P (0 - Vf(x), m) 2 (az/Va) log(2/6) s 5.
Lemma 9. For any ov and 8 E (0. 1), a query to (60y Vd. (+) can be implemented using (loo((2/8) queries to a VVGO (v()).
Proof. Supposing we wish to query O)(-) at x E Rd let 7 Zk Rid
~ Oy for K E N to
be chosen later. Chebyshev's inequality yields P Z vf())] > 20v] < 1/4 for all 1 E [K]. Define J := {k E [K] 2x - vx(()) < 20v J. in which case a Chernoff bound gives P[]]| <
2K/3) < 2e -cc for some absolute constant e E (0, 1). Thus, choosing K (llo((/66) yields
P[J] < 2K/3] < 8. Then conditioning on the event where [J] > 2K/3 which happens with
probability least 1 5, observe that if a sample Zg for some k E [K] is such that
H( E [K]
1
Z || S 40v 2 2K/3,
namely Z₁ is -oy-cl to at least 2K /3 of Zi Zi...., Zx. then there must exist some E J such that ||Z 1 < 25v, implying || IZx vf(x)]] < Gay by a triangle inequality. Furthermore, such a sample Z₁ is guaranteed to exist when conditioning on [J] 2 2K/3 since any sample corresponding to an index in J satisfies this property in particular by a triangle inequality. Finally, we conclude by noting therefore that when J > 2K/3, we have for any u E Rdd with ||u|] = 1:
k2 - vf(x), u)) < 1 vf(z)) S 6σy.
27

---

Finally, we give our upper bounds for Problem with a oE or dv-VSGO in the following corollaries, which we restate here for convenience. Corollary 3. Problem can be solved with probability at least 2/3 in O + dd) queries to dg-ESGO.
Proof. By Lemma 8, Og(+) is a ( per Definition 4. The result then follows by setting 8 + M where M = O1) and applying Theorem 1.
Corollary 4. Problem I can be solved with probability least 2/3 in OldRo + d) queries to ov-VSGO.
Proof. By Lemma 9, we implement query (60v /d, 8)-ISGO with ((log(1/6)) queries to
(v()). We conclude by setting å 1R where M ((1) and applying Theorem 1.
B Lower bounds for SCO under ISGO and ESGO oracles
In this section, we establish lower bounds for solving Problem with either (01, 8)-ISGO or dg- ESGO. We begin by defining mean estimation problem for random variables with sub-ex sub-exponential noise and provide a lower bound for this problem in Section B.1. Then in Section B.2, establish our lower bound for solving Problem I given a g-ESSO by reducing this isotropic mean estimation problem to the former. Finally, we give our lower bound for Problem given (ar, 6)-ISGO the end Section B.2 as a simple corollary by noting that a oEESGO is Ō log(2/6), ISGO for any 8 (0,
B.1 Lower bound for mean estimation with sub-exponential noise
Problem 3 (Mean estimation with sub-exponential noise). Given sample access d-dimensional random variable X that satisfies
PlKu x
E[X])| 2 t < exx (-tVa/oE)
for any 0 and any unit vector the goal is output estimate j of == E[X] satisfying pl u112 S é.
Let U E dd be fixed vector in the d-dimensional hypercube. We establish our lower bound for Problem 3 by considering the following d-dimensional random variable X, where each component X; are sampled independently random
B
w.p.
ToyT
X;
2vd
SEy/log
2vd
w.p.
for all E [d]. Let Po(-) denote this probability distribution.
Lemma 10. For any fixed E {=1}d and any unit vector Rd the random variable X defined in Eg. satisfies
Pl[Ku, X - 2 1) S max (2exp(-Ed/oB)..) S 22exp
Proof. For any unit vector u e Rd. using the fact that each coordinate X₃ is sampled independently and satisfies [X, E[X,]| < ag/v d, by Lemma 21 we know that (u, X E[X]} is a sub- Gaussian random variable with variance
u = o d
j=1 d
Hence, for any we have
< 2exp (exp(-IVa/o))
[ X
E[X]) 2 < max
28

---

Lemma 11. Any algoritium that solves Problem 3 with success probability at least 2/3 must have observed at least
Ω
22 log d
i..d. samples of X.
Lemma 12 (Chain rule of mutual information, Theorem 2.5.2 of [55]). For any n > 0 and any random variables V,X(),, ...., .xtm,, we have
(V) Σ IIV ....
.(..)) x(-1)).
Proof of Lemma 11. Consider the random variable X ~ P.. defined Eq. 6 where e is chosen uniformly at random from {=1]d. For convenience, let p = Sē Sēvlog d/gd and o 2vd Observe
that V (x("), ..... x())) - X is Markov chain, regardless of the algorithm used to construct X. Therefore, by the data processing inequality,
I(V:8)= S I(V: (X (XO,,.......
where r(V; X) is the mutual information between V and X, as defined in Section 1.3. We will prove that if an algorithm outputs X such that |X Ep, [x]] I with success probability at least 2/3 then,
I(V:X) 2 d/6.
(8)
On the other hand, we will prove that
I(V (x(), (0.,,,,(m)))) x(m))) S 28ndy?.
99)
Assuming Eq. and Eq. 9 for now and combining them with Eq. 7 we have d/6 < 28ndp". Therefore,
=52 of 6 2828p
log d
Proof of Eq. 8: Suppose an algorithm outputs X satisfying I| (X]] S with success probability at least 2/3. Let E be the event that || - Ep, [X]] < غ. We have
I(V H(V) H(VIX)
HVV
E)(E)
p(E))
2 H(V) (H(V)X,E)M(E)) + (1-
= =x(E) (H(V) - H(VX E1).
Observe that p(E) 2 2/3 and HVV = d. To compute H E) we consider the set
S == 1 E [+1]² s.t. |
18-Epa E,, Bx-ER,(x] st).
and note that H(V E) < log S|. To bound the size of this set S. fix some vo S and consider,
S' = {u t E [+1]d s.t. - u <
2²/(pē))
Using the fact that Ep, = gv and the triangle inequality, we have S C S'. To bound the cardinality of S' note that for E S'. cannot differ from uo on more than N [22(p200)] [d/(16log log d)] coordinates. Since N < d/2,
d
d N
S Σ 1=1
S N
< 2 logd+log
29

---

Thus for d 2 2,
H(VIX, B) < N log d + log(N)
16 16 d + +1) log(d) + log
(Toiga
d 16logg +1)
S 3d/4.
We conclude that
I(V:X) 2 d/6.
This concludes the proof of Eq. 8.
By Lemma 12 and the fact that X and Xú) are identically and independently distributed conditioned on V, we have
Proof of Eq. 9:
Consider I(V;
(V;Xx),..,,xx") = [(V = =
Similarly, since the coordinates of X are independent we have
I(V (())) = x.)
Next we give an expression for [V; X,) in terms of p.
X,) H(x,) - HX,IVV)
= 11 - h22 +
where hf( is the binary entropy: hz(t) = -too((t) - -(1 (1- - t) log(1 -t.. We claim
1
h2
+p/
2 - - 11228p²
(10)
2
Assuming Eq. 10 we have,
T(V; x(V; x(1)) (V; S 28ndp².
It remains show that h2 [ + p) 2 1 228p Observe the following equality:
1
l12 2 t =
2 + log
+ + 2
2 log
2
+ log
(1 + 2p)
+
-
log
2 (1 - 2p)
2
2
log
+
2 + +
log (1 + 2p) +
2 - p
log (1 - 2p)
2
11+2p
log (1 4p²) + p log
1-
So it is equivalent upper bound the following by 28p²:
2 log (1 4p²) log 1 + 2p
1
1 2p
Since p 2 0, 1/2 log (1 - 4p²) S 0. Hence, it suffices to show that log ((1 + 2p) -2p)) < 28p.
To do this we use the facts that 1/(1 x) < 1+ 2x for x < 1/4, and log(1 + x) S 2r for any x 2 and finally 0 < < 1/4:
1+
log
< log ((1 + 2p) + 4p))
1 1-2p
< log (1 + 14p)
< 28p.
30

---

B.2 Proving Theorem 5 and Corollary
We establish lower bound for SCO with sub-exponential noise by establishing correspondence between Problem and solving Problem given ggEESGO. Specifically, for any random variable X in Problem with 48ey/ogg R, we design the following convex function whose optimal point is related to [[X],
f(x)= = Blfx())
(11)
where
(x, x) -2,00---(),,)
2L max ||
R
fx(x)
(12)
2
Lemma 13. Denote w = [[ Given that [[X] S L, the function f defined in (11) has the following properties:
1. f is convex.
2. f is minimized at x² R
3. Every e-optimum of ʃ satisfies
x |
6c RE X
w 2
4. For
X 2L
R > 0
(x(x)
1
||0||
(13)
||0||
we have
flox(1) (x) Eff()),
Vo E Rd.
5. For any > 0 and unit vector Rd. we have
Pil 9x (x) vf(x)) 2 t s 2exp -tVdloo))
Proof.
Proof of (1): By linearity of expectation,
2L max 0. ||
R
f(x) = (z. E(1) +
(14)
2
This is a convex function of since it is the sum of linear function and the max of two convex functions.
Proof of (2): Suppose ||>||| = 1. We claim that for any > R/2:
R
f(cx) 2 f
x
2
given that
1
2L.
R
1
R 2
f(er) 2 f(Rx/2)
CD
[[
C
>
x
E[X
3
3
2
3
2L
R
E[X]
c
2
L >
E
2
31

---

Since ||[[]]|| I L, the last line holds. Recalling w |[ notice that if z satisfies x w 2 O, we can decrease the function value by increasing the norm of x up to the value of R/2. That is, for any R/2 we have
R
[(x))
(15)
2
Therefore, since the optimal satisfies that x 2 O, we must have x (R/2)w.
Proof of (3): Given any e-optimum 2, since we must have that x xTw w 2 0, it follows by Eq. 15 that 1 П is also an e-optimum. Therefore,
I x
[(x')
1 3
(
x
R
x
B[X] Se.
2 |
Since x² = (R/2)w we equivalently have
R
B[X]
S
6
|
Using that ||w]|² = 1 and rearranging terms we get
6e R [X]
|
W
221
Proof of (4): By Eq. 14 and linearity of expectation have
[x]xx(x)] = [[[] 2T.
1
|||||
R
0 |
0f(x).
(16)
Proof of (5): For any x, 9x (I) takes the form
πx (x(x) C1 +
(17)
where с₁ - and y 2 1 [|||=||
R > 0} া Then by Lemma 10 we can conclude that
(il (x)
vf(z))) > 1) S exp Hap(--aa/os
for any / > 0 and any unit vector E Rdd
The next lemma establishes lower bound for Problem with access to actual gradients, or equiva- lently EESEGO with og 0.
Lemma 14 (Theorem of [24]). Any algorithun that solves Problem I with success probability at least 2/3 must make at least [imin(RL/e d)}) queries.
Theorem 5. Any algorithum which solves Problem with probability at least 2/3 using -g-ESGO makes at least S R2 2/// + min (R2 10, d)) queries.
Proof. Consider the function f(.) defined in Eq. 11 with the random variable X P, defined in Eq. 6, where v is chosen uniformly at random from [=1]d Let x denote the output of the algorithm after making queries. is c-optimal point, then by Lemma 13,
E[X] |E[]]]
6c
21
|
R|
Using the fact that, for any unit-norm vectors and v. |/u
21l2 / (1
u v), we have
E[X]
12c
S
|00
[|]
32

---

For X defined in Eq. 6 we know that ||] = 4og d. regardless of the value of v. Therefore,
defining X = x -
ER 2, and 18 we have
x [--E S |22
(18)
Next, we observe that can simulate the responses of the subgradient oracle defined Eq. 13 using only n i.idd samples of X ~ Ps. which is dg-ESGO by Lemma 13. Therefore, any algorithm which can output an c-optimal point with probability least 2/3 can be used to construct mean- estimation algorithm which outputs an estimate X that satisfies X - [[X]]| S ? with probability least 2/3. Therefore by the hardness of mean estimation with isotropic noise, established in Lemma 11, we must have that
-o0 -
O 2o
n 2
Combined with Lemma 14, obtain the desired result.
Finally, we obtain our lower bound for Problem given (ar, 8)-SGO as simple corollary. Corollary 2. Any algorithm which solves Problem I with probability at least 2/3 using a (a1, 6)- ISGO makes at least [([Po]/(("" log" (1/8)) + min L² /2///,////0/ dd)) queries.
Proof. By Lemma any &g-ESGO a (og (0g(2/ The result then follows by setting og - 0 (2/() and applying Theorem 5,
C Quantum isotropifier and an improved bound for quantum SCO
C.1 Qubit notation and conventions.
We use the notation 1+) denote input or output registers composed of qubits that can exist in superpositionss Specifically, given points Ii...., Zm IRd and coefficient vector E C such that Eie(m] |c = 1, the quantum register could be in the state (eb) = Σie[m] Ca (æ;), which represents a superposition over all m points simultaneously. Upon measuring this state, the outcome will be x; with probability |c,/2. Moreover, to characterize classical probability distribution p over Rd in a quantum framework, we can prepare the quantum state SReR= vp(x))dr |zz), which we denote
as the state over d with wave function / p(r). Measuring this state will yield outcomes according to the probability density function p. When applicable, we use garbage(-)) to denote possible garbage states."
Throughout this paper, we assume that any quantum oracle unitary operation, and we can also access its inverse O-1 satisfying O O 00 = I. This is standard assumption in prior works on quantum algorithms, see e.g. [22, 53].
C.2 Bounded random variables
In this subsection, we introduce our quantum multivariate mean estimation algorithm for bounded random variables whose error is small in any direction with high probability. This algorithm is variant of [22, Algorithm 2]. We begin by presenting some useful algorithmic components.
Lemma 15 (Directional mean oracle, Proposition 3.2 of [22]). Suppose we have access to the quantum sampling oracle Ox of a bounded random variable X satisfying || < 1. Then for any >> 0, there exists two procedures, QDirectionalMean (X, X, m, or, v) and @DireccionallMaatt
X, m, Ot, v).
The garbage state is the quantum counterpart of classical garbage information generated when preparing a classical random sample or classical stochastic gradient, which, in general, cannot be erased or uncomputed. In this work, consider general model without any assumptions about the garbage state. See e.g., [27, 53] for similar discussion
standard use garbage quantum states.
Throughout this paper, whenever we query a quantum oracle that contains a garbage state, we do not assume we know its identity. Nevertheless, our algorithm requires that the garbage state be maintained coherently as part of the system perform the inverse operation.
33

---

that respectively uses O (1/v)) and (omlog"m11// (1/v)) queries, and output quantum states
(ouue,)) (prodd {+1),
(ooue,2) (prodd + [12)
where
Wprood
e [[X,) (زو)
j=1
By BG
and
11 Sv+
P LE (g. X)
X|I| + 2/madd /4 1/02
gr
(1 S
IP 9-
[aE] Kg X
1] + 2 2/madd/44
Using QDirectionalMean/ (-) as subroutine, [22] develops quantum multivariate mean estima- tion algorithms for bounded random variables. In this work, we provide an improved error analysis of this algorithm, based which we apply the boosted unbiased phase estimation technique introduced in [57] to suppress the bias in multivariate mean estimation.
Lemma 16 (Boosted Unbiased Phase Estimation, Theorem 28 of [57]). Given k copies of a quantum
state (xb) Tm Egeg., eimos (g) for some unknown phase & satisfying 2g Φ S 3. there is
procedure BosatellhbaarelPPaassssstttt @k) that returns an unbiased estimate satisfying
FI Ø1 S 6/m]] 2
Proposition 2. For any bounded random variable X satisfying ||]|| s 1 and minx Algorithm 2 and its output ja satisfy the following:
|X|
1. |All S Vd.
2. f is almost unbiased, i.e., [|B|a] E[X]| (((vd)).
3. For any coordinate j E [d]. we have
PlA, B[X,]| 2 cl S 00)).
4. For any unit vector u E Rd. we have
P[ [[X]M llog(1/8) < Ō(dd).
5. Algorithm uses O(VE log (1/5)/e) queries to Ox when B = and (1/55e) queries when B = 2.
Proof. By Lemma 15, the quantum state (oout) in Line 4 is defined on G Hence, we have | and ||ع||| & Vd. Moreover, it satisfies
(out /pprod) (1T)
(19)
where
(prraa) =
imag, E[X,] (g5)
1=1
gyEGm.
We first analyze the algorithm with [Dout) replaced by (Pprod) Line 4. Note that (Vprod) is product state, so the outcomes òi,..., da of Bostrelthhiieed@hssetttttttt follows
34

---

Algorithm 2: Bounded quantum mean estimation with boosted unbiased phase estimation
(ebiased-QBounded]
Input:
Random variable X, target accuracy < <<S failure probability 8 Σ 2 choice of
subroutines / = 1 or 2
Output: An estimate j of [
Set é' t c/8,n V E X log(d/8)/e
log(
), and t-
Set a t
2
V Vlog( 1000
for k 1,... [18 (ogllog(///// (1/5) do
(16 f 4DirectioonalMoonXXXX,,..... v)
5 Run io on the d coordinates independently and denote
21..... 6d to be the outcomes
return f 2x àa)
product distribution. Hence, in this ideal jú also follows product distribution, which denote
as
pi
X P2 X ... @ Pa-
Given that the phase in (proad) satisfies aa X
Σ 2 /3, by Lemma 16, we have
já] - E E| = 0,
and
P
E[X,] 2
S 6,
P [AA - E[x,1| 2 c) S 6, Aprii
2x
Thus, for any unit vector u Rdd the random variable
(u, it E(X)), i 80.00.00
satisfies
P a~0i 00.....000 &dd
f - E(X]) clog(1/8)] s ((d))
by Lemma 22 where set k d.
Next, we discuss the errrr caused by the difference between (viprod) and the actual state [oout), i.c. the (1 term in Eq. 19. By Lemma 15, we have
|| || Su+ +
[a (g.
X
E
XII] + 2//mdd 1 1/0²
gr
6
+
P
jo
(g.
X)
X||]
3
g-
and
(1
|| 1V
P
X)I
1] + 2 2/mad - 1//a
gr
|aE
(g. X > 1]
gr
given the choice of parameters of a, m in Algorithm 2. By Corollary 9, we have
8²
X > E X|| & 16avde -2a--110 1/(32a3) log (avd/c) <
G4
36
35

---

and
IP [g X) 1] S 4a 8² g~
which leads |1|-) 11. 2 || - 6/2. Hence, the actual probability distribution ş of f satisfies
/ أ1 & و2 8 ... @ pall; S 2 18 (oog(16)1]] (ont) (Prrod) = 726 (1/6))
Then, derive that
[ - |[X]|| S
E prup
given that || S vd and || s 1. Morcover, we have
[ lag [[X;]] S 8 720lo11/) Ō(6),
amp
and
P [K, Ai E[XM 2 S ((dd) 725 log(1/6) Ö(8d). amp
By Lemma 15, when 3 1 the number of queries to Ox is
[18 (o8g(166)) ( log"( Ö(v log (1/0)/e).
For B 2, the number of queries is
[18log(1/6]] (omloo2(11/)) (1/8))))))
(1/6)/E).
(20)
L
C.3 Unbounded random variables with bounded expectation
In this subsection, we introduce our quantum multivariate mean estimation algorithm for unbounded random variable with bounded expectation, variant of [22, Algorithm 2], obtained by applying Algorithm 2 to a series of truncated bounded random variables.
Algorithm 3: Unbounded quantum mean estimation (QUnbounded)
Input: Random variable X, target accuracy 0 < < 1, failure probability 8
Output: estimate ğ of [E[X] with loz error at most e
Set o' a log(a/e), e/ log(1/6)), K + 2 log (2/2/e")1
Take [64 log (1/c) log(d) (d(()))] classical random samples XI,..., X lo4 logd//)) use
denote their coordinate median
Define new random variable Y x
a_1 f-
5 for k O.....KK aj 2"
Define the bounded random variable Y; : 11( S ||||| < ax}
if 0 then 14/- Debiased Balaaaeedddouuddd(((1.. 2 k- 1-14--1/// e/K,ō/(Kdk)
else jig. < Debiased--Bouudedddeeee 2 //K,8/KKKKK 8/dd)
if ||7% < 2 2-2 then ju i1
11
else Pe <- 0
return á 11 + Σx K
k axfi
Lemma 17 (Theorem 2 of [44]). For any independent samples X Xn of random variable X e Rd,, any 8 > 0, and any n 2 [32 log(d/5)) their coordinate-wiss median satisfies
32 log (d/0)
P |n - || <
> 1
(21)
71.
36

---

Proposition 3. For any e, > 0 and any random variable X E B with variance Var[X] S o², Algorithm 3 outputs an estimate ja satisfying Bla [[ - a/ log(1/e) and
Pll j
-[Ii ž cl - Ō()
(22)
for any unit vector u E R Moreover, Algorithm 3 makes ( log x (1/6)/e) queries to Ox.
K k= akfik- We first consider the case that || - n|1 s o', which happens with probability at least 8 by Lemma 17. Under this condition, we have
Proof. Denote jay = Ek
2 2-k-te
P[Ka,, ji B[[&|>]
|
nll s o s Ō(5/K),
O...,,K K, Vk = vk=0.....
(23)
K
by Proposition 2. Additionally, we have
E ||| S || B|X]|| + x E[X]|| S 0 + Var[X] 2002
and
||| ||3] 22-2K+1
P[||| 2 aak -
ax
Therefore,
E Yull S Plas-1 S || S arl S P[||||| 2 ax-1] S 226+1
Vk = ..... K.
From this, we deduce that if
2 2-
(u, tr - E[YYl>
(24)
K
holds for all unit vectors Rd we have lmal
S 2-22++2 and il pu.- Consequently,
P Ku RYk
juy
)
| m/1 so S O(6) 2 6
2
by union bound. Furthermore, we have
B Σ E
= E I[|l|| 2 ax) Illl
s E| T[ 2 axH
< /Elly P ax) 2
which leads to
([ joy B[- 2 2||||= n/l o1 < Ō0)).
Note that || S ||[[]]| + o S L in this case, we have ft E(X] = -fy E(. Thus,
[|] (u, A |[ 2 e || - 7| S 5o < Õ(6)
Counting in the error probability when || - |X|]||| 2 d. we have
- ż o] s 5(6) + 8 0(6)
(25)
As for the bias of f we have
K
K
| EXX]
a [
||
E[X|||
Σ
a
S
log(a/e)
k=
k=
Next, we discuss the query complexity of Algorithm 3. The number of queries in the iteration k = 0 is
0 log (5K/8)
Klog"(5/88)
- log (1/8))
C'
37

---

and the number of queries in the k-th iteration for lo >> is
o K B log (1/0)
2-h-le' =0(- (1/00)))))))))
-0 (1/00
Combining with the number of classical samples to obtain Je, can conclude that the total number of queries equals
o ( (1/0)) + K - 6(010g"(110) - ō 0 (1/8))
log
C.4 Removing the bias
In this subsection, we combine Algorithm with the multi-level Monte Carlo (MLMC) technique to obtain unbiased estimate of an unbounded random variable whose error small in any direction with high probability.
Algorithm 4: Quantum Isotropifier
Input: Random variable X, target accuracy e, failure probability
Output: An unbiased estimate ů of [[[]]
Define 3, == 2 2 vjj E
Set (a()) (QUnbounded((X, X, e/6,8) 8)
Randomly sample Geom (5) E
((6) QUUnoounded( X, B5e/6, 66
5 aG-1) +QUnbounded 1
6 j + (a(0) + 2 ( (1-11)
return P
Theorem 8. For any e, Ō and any random variable X Rdd with variance Var[X] s 0², the output ja of Algorithm 4 satisfies [[s]] [[ and
P [ ft E[x]) 2 clog)(8/8) - Ō(8).
(26)
for any unit vector E Rd. Moreover, Algorithm makes Ö( logglog1/000 (1/8)/e) queries Ox in expectation.
Proof. The structure of our proof is similar the proof of Theorem 4 of [53]. Note that the output of Algorithm 4 can be written as
(0) + (1(() (((1-1)),
J J~ Geom + 2
N.
(27)
Thus,
BlA (0) j (1B(0)) B
E B[X].
For each j E N and ر( we denote ((ي) jا6ر) - E[X]. Then,
P[ fi - [[X])| 2 log (8/0)]
(u, (0) + 2d (((J) - 2 elog (8/8)]
2 (u, 5 (0)) 2 e (ogg2(8)))
+ ( 2o (8/8)/6)
+ KM (
(1-1) 1| > 2- 2elog (8/8)/6)
where by Proposition we have
P P|[(u, (()) 2 clog2 (8/5)(8/))/6)
< 5|,,, c/6] < Ō(0).
38

---

and
(l((,,50)) 2 (8/00// z P B,e/6] + +12233, 18/6 Ō(0)
Similarly, we have
F[l(u, <(>-1)>| 2 2 clo" cog)) - SPlKu,, ž 1 + +
log log (8/5)]=((8)
which gives F[luu, f - B[X]]| 2 E elog (8/0) _ Ō Moreover, the number of queries of Algorithm 4 equals
① log (1/0)) (1+ Σ P(J pPJ= + + Ö ((- (o (1/0)
Σ 1
Ö o 0 log')
by Proposition 3.
C.5 An improved bound for quantum SCO
In this subsection, we apply Algorithm 4 to obtain an ISGO using queries to QVSGO, and then solve SCO using the stochastic cutting plane method developed in Section A.
Theorem 6. For any differentiable f: R&d + R. a (01,5)- of f can be implemented using Ölovvdlog" (1/6)/o1) (11/0)) queries
σv ov- -Vv--..SG....
(Algorithm 4) to the QVSGO at In particular, by Theorem 8, there exists some å = Ô()) such that the output of qo log" (8/8), 8) is an (ar, OIISGO, and the number of queries equals Õ(ov Vd (1/6)/a1) = Ölovv log (1/5)/ar) expectation.
Proof. For any E R4, it suffices to apply QuantumIsotropiffe
Theorem 7. With success probability at least 2/3, Problem 2 can be solved using Öddovve) queries to -VSGO.
Proof. The proof is established by combining Theorem and Theorem 6, where we set evd.
D Sub-exponential distributions and additional discussion of SGO oracles
In this section, we review sub-exponential distributions and also further discuss the relationships between the various SGOs we define.
Review of sub-exponential distributions. As there several equivalent ways to define sub- exponential random variable [61, Proposition 2.7.1], we will use the following "tail-inequality" version which suits our purposes:
Definition 11. A random variable X E R is o-s-u--eepoennneee if
P[|X
T.
> 8 2 2exp(-t/o) for all 0.
Analogously to the definition of a nub-Gaussian random vector (see, e.g., Definition 3.4.1 [61] or Definition 2 in [35]), we say random vector X E Rd is sub-exponential if all of the one- mee-iimensional marginals are sub-exponential random variables:
Definition 12. A random vector X E gd is o-subbexponential for any unit vector E RRd, we have that (X, u) is o-sub-exponential, namely:
PI E.X, w)l 2 2exp(-t/o) for all t 2 0.
It is well known that sub-exponential distributions generalize sub-Gaussian distributions and therefore bounded random variables in particular. Finally, we prove a short lemma which we will reference below:
39

---

Lemma 18. X E Rd is o-sub-exponential, then E|J - EXI < C'do² for some absolute
constant C.
Proof.
Letting denote the i-th standard basis vector, have
E - EX
Σ ex, RE(d]
Σ
E(X - EX, S Cdo",
sE|d]
where the last equality follows because if a random variable Z E IR o-sub-exponential, then E(Z - EZ)² < Co [61, Proposition 2.7.1].
Additional discussion of SGO oracles. Note that EEEESGO defined in Definition is d vd- sub-exponential per Definition 5 as opposed to d o--sub-exponential. We perform this scaling so that, per Lemma 18, EEGGO also Co E-VGO for some absolute constant C. In other words, this scaling makes it so that Definition is truly a restriction of Definition 3, and thus the rates of Corollaries and 4 are comparable.
E
Technical lemmas
In this section, collect some miscellaneous technical lemmas. The following lemma from [22] shows that for any fixed vector æ E Rd,, most of the vectors g ~ G have a relatively small inner product with æ.
Lemma 19 (Lemma 3.1 of [22]). Let >> 0. For any vector a E Rdd we have
[al
.> ||]||]]
2e 2/02 Va E
g
We extend this result and show that this exponentially small probability bound still holds when is random variable instead of a fixed vector.
Lemma 20. Let > O. Consider d-dimensional random variable Y E IRd that satisfies
(Y, 2 ||=||| s p(a). Vz E Rd
(28)
for some p(-) that is a function of a, then for any random variable X E Rd, we have
PlaBII x3]] 2 2 max |X|]] S ap(a)) max ||Y||
(29)
and
a |Y M /[I
| X
P[a X)1
[||] (8p((8a)) max
[||]]
log
(30)
minx [|]
Proof. We first prove Eq. 29 by contradiction. Assume the contrary of Eq. 29, we have
E [maxffa (Y, x)I max ||]]] 0H| 2 Eî max(Eja((X, max || |
[I], 0у]
Y,x
El (X,
max || 0H
P/aB (Y, > 2 max ||]] max X||
> ap(a) max |Y|] max X|]
However, by Eq. 28, have
E [maxfal(Xxxx) x)I max | 0}] < E |maxfal XX - [3] v.X
< (a x) 2 ||]] aK(Y, X)
S ap(a) max || max X|],
contradiction.
40

---

Next, we prove Eq. 30 by applying Eq. 29. Denote Ç = x x |||
For any > 0, let
1 SvE
k
log
and define aj = (2 for each E [k]. We then define
Xy = X Iaa--1 - X < az}:
and
X = X 11 X 2 a
which leads
k+1
E X| = Σ
B|
Σ j=1
1||
5=1
and
aBK(Y,X)|
(Y, Xgy1 Sa Σ
XY, + a max |Y|| ||
(31)
/=1
given that
& max ||
E| X
E
max |Y] X
< max
|Y|||
max | {|
a
0k
For any j = 1,...,... ki we define a new random variable Xj that satisfies
Xj:
w.p. P P|x, * 0], w.p. P 0].
X,
0,
Then,
P(X, * 0]
max |XX|||
B||X||| = P[X, * 0] E| 2
KKY P(X, * 0J KY,
2
By Eq. 29, we have
PlaEI X 2 2 max X1 S ap((a max ||||,
which leads to
Pl X,ı, 4E| x,Il ap(a) max [|Y]]
and
TP
E
B||X
< kop(a) max |||
by union bound. Combining Eq. 31, we can conclude that
P aE (Y, x
4 + max | EE
X
XX||X" [|
I ap(a) max |Y| log
C2E
Set
((EI|
? (max |
obtain
max | X
PlaEKY, X)I > X[] ap(a) max |||| log
minx yo ||X||
Since the above inequality holds for any a 2 0. we can rescale a by factor of 8 and conclude that
max
| [|
FY,EE(YY,)) > X|] < 8ap(8a) max ||||| log
minx 40 |X
41

---

Corollary 9. Let a: > 0. For any random variable X E R with ||||| S 1 and minx |X| 2 we have
P
oF
X)
max [X]] I 4a 4av 1/(2a²)
g
and
aE
(g. X)I
|| < 16av de 1/(32a²) log (avd/e).
g
Proof. The results are obtained by combining Lemma 19 and Lemma 20.
The following lemma establishes that the sum of independent zero-mean sub-Gaussian random variables also follows a sub- Sab-Gasssian distribution.
Lemma 21 (Proposition 2.6.1 of [61]]. For any k independent zero-mean uub-Gaussian random
variables Y1, YI,..., Y& with variances of.....oy. their sum Σ3 Yj is also mub-Gaussian with variance
8 E o3.
Lemma 22. For any e, O, u E IR* and l independent random variables Vi,..., YE satisfying
pl|Y; ||| 2 S Vj [k].
(32)
have
k
U Y3
Σ 1=1
u, 2 (/g/\() s 2ōk.
(33)
Proof. Denote Zj = Y, E|y;]. By Eq. 32, each random variable Z, follows a probability distribution Pj that is 8-close to probability distribution pú such that maxz, || S log(1/8) Then, the random variable Z, ~ P, follows a sub-Gaussian distribution with variance most e and the random variable
k
Σ UjZYi E Zx} ~ P1 8
& Pk.
(34)
is also a sub-Gaussian distribution with variance at most
|2,11 < C/I1u11222
(35)
where C' the absolute constant in Lemma 21, which leads to
k Σ
ugZyy
>
Co] s
(36)
j=1
Counting in the difference between pj and the actual distribution Pj. we have
P Pi @
Σ
ug
< 8k 28k.
(37)
j=1
42


Reviews:
[{"review_id": "bVxOMWGgag", "reviewer": "Reviewer_BTYs", "summary": "This submission studies quantum and classical algorithms for convex optimization. In particular, the authors propose isotropic stochastic gradient oracles in the sense that the noise in each direction is bounded with large probability. Using this new oracle, the problems of convex optimization can be solved faster than using SGO in the high precision and low variance regime.\n\nThe authors also proposed a quantum bounded stochastic gradient oracle, which can be used to improve the quantum convex optimizer because the classical isotropic stochastic gradient oracle can be efficiently implemented using this quantum oracle, based on quantum unbiased phase estimation.", "questions": "Some minor comments:\n1. Line 53 seems not grammatically correct.\n2. Line 304: missing \"is\" at the end of the line?\n3. Eq. (3): the use of continuous-space states is not properly defined. (See Section 3 of arXiv:1908.03903).", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "I feel this submission makes a solid theoretical contribution in classical and quantum optimization. Notably, a lower bound for the classical case is also given.\n\nThe major weakness lies in the motivation of the oracle: are there real-time applications of convex optimization that can provide the isotropic oracle without significant overhead?", "was_revised": true, "final_justification": "My questions are mostly addressed. I keep the positive score.", "rebuttal": "Thank you for your feedback on our paper and positive recognition of our contributions. We will correct the typos that you raised in our revised version.\n\n*“The major weakness lies in the motivation of the oracle: are there real-time applications of convex optimization that can provide the isotropic oracle without significant overhead?”*\n\nWe want to emphasize that in our main application to quantum stochastic convex optimization, the isotropic noise model is not an assumption. For quantum stochastic convex optimization, we only assume access to a quantum analog of a VSGO oracle (Definition 6), whose stochastic noise is not guaranteed to be isotropic. In other words, the isotropic noise model is a technical tool which we use to achieve improved rates in a quantum noise model which has been studied previously in the literature.\n\nRegarding non-quantum applications, that is a great question. We identify what we believe is a natural class of distributions where you can achieve improved rates. We leave it to future work to determine whether actual data distributions satisfy this condition, and whether there are additional classes of problems which can be solved more efficiently in this noise model."}, {"review_id": "mURfFkiJi7", "reviewer": "Reviewer_VDzC", "summary": "This paper investigates the problem of stochastic convex optimization under a noise model termed isotropic noise, which includes white additive gaussian model as a special case, and proposes algorithms that improves the state of the art sample complexities. The contribution is two fold. First, in the classical setting with first-order oracle, the authors propose a cutting-plane-based optimization algorithm that achieves an upper bound of $\\tilde{O}(R^2\\sigma^2/\\epsilon^2+d)$ queries under the isotropic noise model for convex and Lipschitz functions. This improves the standard SGD in certain regimes, which has a sample complexity of ${O}(R^2\\sigma^2/\\epsilon^2+R^2L^2/\\epsilon^2)$. A matching lower bound is provided to show that the better of the two algorithms is sample optimal up to logarithmic factors. Second, the authors extended their results to a quantum setting, where $1/\\epsilon$ complexity can be achieved through the well known amplitude amplification approach. This extended algorithm improves previous results in the quantum domain by a polynomial factor in dimension $d$.", "questions": "While the reviewer has an overall positive view on the presented results. The current manuscript has a few issues to be resolved. The reviewer would be happy to raise the score if they are addressed adequately.\n\n1. As discussed above in the weakness section, since the quantum oracle considered in this paper provides access to additional information of the objective function compared to the classical case, which makes it an algorithmically easier problem. The reviewer recommends the authors to carefully revise relevant statements such as referring the oracle as \"quantum generalizations of classical oracles\" and the $1/\\epsilon$ complexity as \"quantum speedups\".\n\n2. In terms of the motivation of the quantum oracle formulation, the authors provided a supporting argument in the footnote on page 4 from the aspect of oracle implementation, mentioning that such quantum oracle can be implemented if the implementation of the classical oracle is available. However, in optimization problems the identity of the circuit for the classical oracle can not be known, otherwise we always have a sample complexity of O(1). Could the authors clarify how such quantum oracle can be constructed without accessing the circuit of classical oracle? \n\n3. Could the authors provide additional motivation on the particular quantum oracle formulation in this work besides that it has been considered in prior work?\n\n4. Do the authors have any conjectures or insights regarding lower bounds in the quantum setting?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \nThe technical results are sound, with detailed proofs provided in the appendix. To the best of the reviewer's knowledge, the presented achievability of the optimal sample complexity in the classical case is new. Given that finding optimal sample complexities for Lipschitz convex functions is a fundamental problem, the achievability result presented in this paper that matches the lower bound is quite significant, albeit requiring the isotropic noise assumption. \n\nWeakness:\n1. The clarity and structure of writing can be improved, particularly for the introduction. Especially, it would be helpful to state the assumptions on the objective functions upfront, i.e., Lipschitz and convex, since the introduction explores various frameworks including ones with Lipschitz gradient. Stating the assumptions clearly helps readers better understand the strength of the proposed result. Besides, it is not clear how the results for the Lipschitz gradient case is connected to the results in the framework in this paper. The authors are recommended to either clarify their connections, or to move those discussions to a separate paragraph at the end of introduction as overview of related works.   \n\n2. A significant limitation of this work is on the quantum formulation, where the authors assumed the quantum oracle essentially provides a pure-state outcome, specifically, the garbage state that is entangled to the gradient outcome $|g>$ is assumed to be known and used in the amplitude amplification part of the algorithm. While this is a typical assumption in related works, it is technically incorrect to claim that this formulation is a generalization to the classical case and the proposed algorithm achieves a \"quantum speedup\", as in the classical case the garbage states are viewed as part of the environment of which the identity is unknown and is not accessible by the algorithm. The reviewer believes that if we consider the most general non-pure state quantum oracles then the $1/\\epsilon$ complexity is not achievable and the optimal sample complexity would reduce to the result in the classical case.  \n\n3. While the bounds under isotropic noise and sub-exponential noise are tight up to log factors, the main open problem of achieving optimal sample complexities for variance-bounded noise remains unresolved.", "was_revised": true, "final_justification": "My review comments are addressed in the second response of the authors, where they provided a high-level plan for the revision. While the exact revision is not provided, the issues raised in the review might be resolved if the manuscript is revised appropriately.   \n\nGiven the uncertainty and the partial resolution of the concerns, my score remains unchanged. However, I do not strongly oppose the acceptance of this paper.", "rebuttal": "Thank you for your feedback and questions on our paper. \n\nTo respond to the weaknesses you raised:\n\n- *\"It would be helpful to state the assumption on the objective functions upfront, i.e., Lipschitz and convex.\"*\n\nNote that we state that $f$ is convex and $L$-Lipschitz in Lines 19 - 22. More broadly, the introduction was structured with the intent of making the assumptions clear. If you could identify places in the paper where you feel we missed a statement or an explanation, please let us know; we would be grateful and are eager to further improve the paper’s clarity.\n\n- *\"It is not clear how the results for the Lipschitz gradient case is connected to the results in the framework in this paper.\"*\n\nThank you for this question. We do mention prior dimension-independent work on the Lipschitz gradient case in Line 37 when explaining the prior work on SCO with a VSGO oracle. Additionally, our bounds can be extended immediately to the Lipschitz gradient case at the cost of only logarithmic factors since our bounds have logarithmic dependence on the Lipschitz constant of $f$. This follows because a function with a $G$-Lipschitz gradient which is minimized in a ball of radius $R$ is itself $O(GR)$-Lipschitz in the ball. We will mention this in our revision.\n\n- *“A significant limitation of this work is on the quantum formulation, where the authors assumed the quantum oracle essentially provides a pure-state outcome, specifically, the garbage state that is entangled to the gradient outcome $|g>$ is assumed to be known and used in the amplitude amplification part of the algorithm.”*\n\nThank you for this question. We would like to clarify that the garbage state is not assumed to be known by our algorithm. This is because quantum amplitude amplification requires only the ability to apply the oracle and its inverse as a black box, without knowledge of the garbage state. Accordingly, our algorithm only needs to maintain coherence with the environment but does not require knowledge of its identity.\n\n- *“While this is a typical assumption in related works, it is technically incorrect to claim that this formulation is a generalization to the classical case and the proposed algorithm achieves a \"quantum speedup\", as in the classical case the garbage states are viewed as part of the environment of which the identity is unknown and is not accessible by the algorithm.”*\n\nThank you for raising the question regarding our use of the term “quantum speedups.” We adopted this terminology in part because it is commonly used in the literature (e.g., [1, 2]), and also due to the widespread convention of referring to Grover’s algorithm as achieving a “quadratic speedup.” That said, we can see how this phrasing may lead to confusion, and will look into alternative expressions in the final version.\n\n- *\"While the bounds under isotropic and sub-exponential noise are tight up to log factors, the main open problem of achieving optimal sample complexities for variance-bounded noise remains unresolved.\"*\n\nIn regard to open problems, key quantitative contributions of this paper are tight rates for ISGOs and faster quantum stochastic convex optimization. Indeed, we do present what we believe is a natural further open problem suggested by this line of work, but we kindly suggest reviewers view this as an additional open problem or contribution, which is intended to encourage the community to further improve upon our results (rather than a failing of them). Also, note that resolving the open problem wouldn’t immediately yield faster quantum stochastic convex optimization algorithms than our approach, due to our quantum isotropifier. We hope that our work may facilitate further research on this fundamental open problem that we highlight.\n\nTo respond to your questions:\n\n- We thank you for raising the question regarding our use of the term “generalization” for our quantum oracle. We use this term to convey that the quantum stochastic gradient oracle is strictly more powerful than its classical counterpart, since the latter can be obtained by measuring the quantum oracle. Given known query complexity lower bounds for algorithms using classical stochastic oracles, improved rates are only possible with access to strictly more powerful oracles. We acknowledge that the term “generalization” may cause confusion in this context, and will fix this in our final version.\n\n- Thank you for your question regarding the implementation and motivation of the quantum oracle. We would like to clarify that, in the worst case, we do not see how to implement the quantum oracle efficiently using a classical oracle without incurring a loss in query complexity. We did not intend to suggest otherwise, and if any part of the paper leads to this confusion, we are happy to try to revise it for clarity.\n\n- Regarding your question on the access to the identity for the circuit to the classical oracle, indeed, knowing the gradient circuit makes the query complexity of the problem trivial. However, it doesn’t necessarily make the problem computationally trivial. As discussed in [3, 4], even if the classical oracle’s internal circuit is known, computing the gradient exactly from this description may require exponential time in the circuit size (as far as we know). Therefore, it remains meaningful to study algorithms that access the oracle in a black-box manner, which is the motivation behind the transformation we described. If there are specific parts of the paper that would benefit from further clarification, we would be more than happy to expand on them in the final version.\n\n- Regarding the motivation of the quantum oracle, we are not aware of any key motivation for considering this setting that was not already present in prior works. For this reason, we simply cited the prior work rather than repeat these motivations.\n\n- Regarding your question on lower bounds in the quantum setting, we agree that this is a good question. We would like to note that a lower bound is established in prior work [2]. However, this lower bound does not match our algorithmic result, and it is unclear to us how to improve the existing construction. We may include this as an open question in the revised version.\n\n[1]. Ashley Montanaro. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 2015.\n\n[2]. Aaron Sidford and Chenyi Zhang. Quantum speedups for stochastic optimization. NeurIPS 2023\n\n[3]. Robin Kothari, and Ryan O’Donnell. Mean estimation when you have the source code; or, quantum Monte Carlo methods. SODA 2023. \n\n[4]. Clément L. Canonne, Robin Kothari, and Ryan O'Donnell. Uniformity testing when you have the source code. 2024."}, {"review_id": "4GO7U7582G", "reviewer": "Reviewer_62sv", "summary": "This work introduces a setting where the noise of the stochastic gradient is bounded in every direction with high probability, i.e., the noise is isotropic. As a special case, the proposed algorithm achieves the best complexity which improves a factor of $d$ in certain regimes, for sub-exponential noise. Matching lower bounds are also provided under this noise model.", "questions": "- Why is $R^2 \\sigma_V^2 / \\epsilon^2$ unimprovable when $d=1$? Isn't the optimality with $\\sigma_B^2$ instead? \n\n- What is the query complexity of SGD under the same noise model (ISGO)? \n\n- Can the authors comment on the sensibility of the isotropic noise model? Is it the same model as what is being referred in [1]?\n\n- It seems that there exists dimension independent quantum algorithms for similar problem setting. How does this work compare with [2] for example?\n\n[1] H. Daneshmand et al., \"Escaping Saddles with Stochastic Gradients\"\n\n[2] B. Augustino et al., \"Fast Convex Optimization with Quantum Gradient Methods\"", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strength:**\n- Achieves the best known complexity for sub-exponential noise, which is $\\tilde{O} (R^2 \\sigma^2 / \\epsilon^2 + d)$ query complexity. \n\n- The quantum isotropifier, which converts a variance bounded quantum sampling oracle to an unbiased estimate with isotropic error can be of an independent interest.\n\n\n**Weakness:**\n- The considered regime is fairly specific, and the posed open problem is not completely resolved (other than sub-exponential noise). \n- It would be great if the authors can comment on the sensibility of the noise model. It feels that the noise model was introduced in order to justify for the quantum isotropifier. From the stochastic convex optimization perspective, though, it is unclear if the assumption is reasonable.", "was_revised": true, "final_justification": "The authors have provided a fairly detailed reply, which addresses my previous concerns. I think the proposed regime is still quite specific, but I recommend acceptance as achieving SOTA complexity for subexponential noise, having a lower bound, and proposing a quantum isotropifier are valuable to the community.", "rebuttal": "Thank you for your feedback and questions on our paper.\n\nTo respond to the weaknesses you raised:\n\n- *\"The posed open problem is not completely resolved (other than sub-exponential noise).\"*\n\nIn regard to open problems, key quantitative contributions of this paper are tight rates for ISGOs and faster quantum stochastic convex optimization. Indeed, we do present what we believe is a natural further open problem suggested by this line or work, but we kindly suggest reviewers view this as an additional open problem or contribution, which is intended to encourage the community to further improve upon our results (rather than a failing of them). Also, note that resolving the open problem wouldn’t immediately yield faster quantum stochastic convex optimization algorithms than our approach, due to our quantum isotropifier. We hope that our work may facilitate further research on this fundamental open problem that we highlight.\n\n- *\"It would be great if the authors can comment on the sensibility of the noise model. It feels that the noise model was introduced in order to justify the quantum isotropifier.\"*\n\nWe want to emphasize that in our main application to quantum stochastic convex optimization, the isotropic noise model is not an assumption. For quantum stochastic convex optimization, we only assume access to a quantum analog of a VSGO (Definition 6), whose stochastic noise is not guaranteed to be isotropic. In other words, the isotropic noise model is a technical tool which we use to achieve improved rates in a quantum noise model which has been studied previously in the literature.\n\nRegarding the sensibility/applicability of the noise model beyond quantum stochastic convex optimization, that is a great question. We identify what we believe is a natural class of distributions where you can achieve improved rates. We leave it to future work to determine whether actual data distributions satisfy this condition, and whether there are additional classes of problems which can be solved more efficiently in this noise model.\n\nTo respond to your questions:\n\n- *\"Why is $R^2 \\sigma_V^2 / \\epsilon^2$ unimprovable when $d = 1$?\"*\n\n$R^2 \\sigma_V^2 / \\epsilon^2$ can be shown to be unimprovable when $d = 1$ using the same lower bound construction which shows that $R^2 \\sigma_B^2 / \\epsilon^2$ is unimprovable when $d = 1$. Indeed, in that construction (e.g., Section 5 in [1]) it is the case that $\\sigma_V^2 = \\Theta(\\sigma_B^2)$. We will include this point in our revision.\n\n[1]. John Duchi. Introductory Lectures on Stochastic Optimization. IAS/Park City Mathematics Series, American Mathematical Society.\n\n- *\"What is the query complexity of SGD under the same noise model (ISGO).\"*\n\nRegarding the query complexity of SGD under an ISGO: When $\\delta$ is sufficiently small as an inverse polynomial in the problem parameters (analogously to Theorem 1), then SGD achieves an $\\tilde{O} ( R^2 (L^2 + \\sigma_I^2) / \\epsilon^2)$ rate with high probability. In this case, a $(\\sigma_I, \\delta)$-ISGO query implements a $O(L + \\sigma_I)$-BSGO (Definition 2) query with high probability, in which case we can apply the classical SGD rate for BSGOs.\n\n- *\"Can the authors comment on the sensibility of the isotropic noise model?\"*\n\nSee above.\n\n- *\"Is it the same model as what is being referred to in [1].\"*\n\nWe do not believe it is the same model. I could not find a formal definition of “isotropic noise'' in that paper or the papers it cites under the “isotropic noise'' header on the first page. To my understanding, when that paper refers to isotropic noise they mean noise which must have a component in every direction (see \"exhibits a certain amount of variance along all directions in $\\mathbb{R}^d$\" on page 1), namely a lower bound on how much noise the distribution has in each direction, whereas our definition corresponds to an upper bound on how much noise the distribution has in each direction.\n\n- *\"It seems that there exists dimension independent quantum algorithms for similar problem setting. How does this work compare with [2] for example?\"*\n\nThank you for your question regarding the comparison between our work and that of B. Augustino et al. We would like to clarify that these works belong to two distinct lines of research on quantum algorithms for continuous optimization:\nThe first line, which includes [2, 3] and the work by Augustino et al., focuses on algorithms that access a (possibly approximate) quantum value oracle. In this setting, the oracle’s output need not be unbiased but must have small errors. For instance, in Theorem 2.1 of Augustino et al., the required error is of the order $\\mathrm{poly}(\\epsilon)/\\mathrm{poly}(d)$.\n\nThe second line, which includes [4] and our work, considers access to a quantum stochastic gradient oracle. In this setting, the oracle provides unbiased gradient estimates with variance that is independent of both $\\epsilon$ and $d$. Notably, [4] proves that a dimension-independent quantum speedup is impossible in this setting.\n\nWe thank you for pointing out the relevant work by Augustino et al. and may include some discussion of this work in our final version.\n\n[2]. Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimization using quantum oracles. Quantum 2020\n\n[3]. Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization. Quantum 2020\n\n[4]. Aaron Sidford and Chenyi Zhang. Quantum speedups for stochastic optimization. NeurIPS 2023"}, {"review_id": "mx7Cp4zhmy", "reviewer": "Reviewer_QeNG", "summary": "This paper studies the stochastic convex optimization (SCO) problem using a stochastic gradient oracle. Under a new assumption that the stochastic gradient is isotropic, the authors develop a quantum algorithm that achieves a speedup of a $d$ factor in certain parameter regimes. This result can be generalized to a stochastic gradient with a sub-exponential noise, therefore achieving the current STOA complexity for stochastic convex optimization with sub-exponential noise. In both cases, the authors also prove matching lower bounds (up to polylogarithmic factors). Therefore, the upper bounds can be regarded as tight. This work can be regarded as a follow-up work of [50] and [64].", "questions": "- The isotropic noise seems to be a technical requirement in the proof. Except for sub-Gaussian noise, is there any practical model that exhibits this type of noise distribution?\n- Lemma 10 suggested that a $(O(\\sqrt{d}), \\delta)$-ISGO can be implemented using very few queries to a VSGO. Is it possible to implement a $(O(1), \\delta)$ ISGO with $poly(d)$ queries to VSGO (without using quantum)? If so, how would it be worse than Theorem 6? \n- Can you comment on other potential computational problems that would benefit from the quantum isotropifier? Or does this technique heavily rely on the assumption of isotropic stochastic noise?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Under the new assumption of isotropic stochastic gradient, an improved query complexity is achieved. \n- Matching lower bounds are proven, showing that the proposed quantum algorithms are near-optimal. \n- The authors systematically develop a *quantum isotropifier*, which is the key ingredient in the improved bound for quantum SCO.\n\nWeaknesses:\n- The improved query complexity results are obtained under stronger theoretical assumptions, such as isotropy and sub-exponential tails.\n- The quantum speedup yields only a $d$-factor improvement, which is relatively modest. Considering that the proposed algorithm would require a large fault-tolerant quantum computer, the overhead from quantum error correction could significantly limit its practical applicability.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback and questions on our paper.\n\nTo respond to the weaknesses you raised:\n\n- *\"The improved query complexity results are obtained under stronger theoretical assumptions, such as isotropy and sub-exponential tails.\"*\n\nThough we do require these assumptions for our non-quantum results, we want to emphasize that in our main application to quantum stochastic convex optimization, the isotropic noise model is not an assumption. For quantum stochastic convex optimization, we only assume access to a quantum analog of a VSGO (Definition 6), whose stochastic noise is not guaranteed to be isotropic. In other words, the isotropic noise model is a technical tool which we use to achieve improved rates in a quantum noise model which has been studied previously in the literature.\n\n- *\"The quantum speedup yields only a $d$-factor improvement, which is relatively modest...\"*\n\nRegarding your comment that our quantum speedup is relatively modest and comes with an additional $d$ factor, we agree that this may limit the applicability of our algorithm on near-term quantum devices. Nevertheless, we would like to note that, as shown in prior work [1], achieving a quantum speedup in $\\epsilon$ without incurring additional $d$-dependence is impossible in the worst case. We believe it is an interesting and natural open problem to explore whether our techniques can lead to more practical quantum algorithms given additional assumptions on the stochastic optimization problem.\n\n[1]. Aaron Sidford and Chenyi Zhang. Quantum speedups for stochastic optimization. NeurIPS 2023\n\nTo respond to your questions:\n\n- *\"The isotropic noise model seems to be a technical requirement in the proof. Except for sub-Gaussian noise, is there any practical model that exhibits this type of noise distribution?\"*\n\nJust to emphasize the point we made above, for our main application to quantum stochastic convex optimization, the isotropic noise model is a technical tool as opposed to an assumption.\n\nRegarding non-quantum applications beyond sub-Gaussian distributions, that is a great question. We believe isotropic noise constitutes a natural class of distributions where you can achieve improved rates. We leave it to future work to determine whether actual data distributions satisfy this condition, and whether there are additional classes of problems which can be solved more efficiently in this noise model.\n\n- *\"Is it possible to implement a  $(O(1), \\delta)$ ISGO with $\\mathrm{poly}(d)$ queries to VSGO (without using quantum)? If so, how would it be worse than Theorem 6?\"*\n\nRegarding your question about implementing an $(O(1), \\delta)$-ISGO with $\\text{poly}(d)$ queries to a VSGO: Using a sub-Gaussian mean estimator (e.g., Theorem 8 in [2]), a $(O(1), \\delta)$-ISGO can be implemented with $d$ queries (up to log factors) to a VSGO, whereas Theorem 6 is able to achieve $\\sqrt{d}$ queries (up to log factors).\n\n[2]. Lugosi and Mendelson. Mean Estimation and Regression Under Heavy-Tailed Distributions: A Survey. Foundations of Computational Mathematics.\n\n- *“Can you comment on other potential computational problems that would benefit from the quantum isotropifier?”*\n\nWe think that is a great question. We are only using it inside cutting plane methods for now, but it is an interesting question if other problems, particularly those related to the applications of quantum multivariate mean estimation, might benefit or if it affects practical performance. However, we leave this for future work.\n\n- *“Does this technique heavily rely on the assumption of isotropic stochastic noise?”*\n\nIsotropic noise is not an assumption for the technique. Rather, it produces isotropic noise from a (potentially) non-isotropic distribution."}]

Author rebuttal:

Meta-review: All reviewers strongly agree that this submission makes a valuable contribution to both quantum and classical optimization. At the same time, we urge the authors to take the feedback seriously—particularly with respect to the presentation of the results—and to incorporate the necessary revisions.
Decision: Accept (poster)