Robustness of Quantum Algorithms for Nonconvex Optimization
Authors: Weiyuan Gong
Chenyi Zhang
Tongyang Li
Venue: ICLR 2025 Poster (2025)
Keywords: Nonconvex optimization
Robustness
Quantum algorithms
Primary area: optimization

Abstract: In this paper, we systematically study quantum algorithms for finding an $\epsilon$-approximate second-order stationary point ($\epsilon$-SOSP) of a $d$-dimensional nonconvex function, a fundamental problem in nonconvex optimization, with noisy zeroth- or first-order oracles as inputs. We first prove that, up to noise of $O(\epsilon^{10}/d^5)$, perturbed accelerated gradient descent equipped with quantum gradient estimation takes $O(\log d/\epsilon^{1.75})$ quantum queries to find an $\epsilon$-SOSP. We then prove that standard perturbed gradient descent is robust to the noise of $O(\epsilon^6/d^4)$ and $O(\epsilon/d^{0.5+\zeta})$ for any $\zeta>0$ on the zeroth- and first-order oracles, respectively, which provides a quantum algorithm with poly-logarithmic query complexity. Furthermore, we propose a stochastic gradient descent algorithm using quantum mean estimation on the Gaussian smoothing of noisy oracles, which is robust to $O(\epsilon^{1.5}/d)$ and $O(\epsilon/\sqrt{d})$ noise on the zeroth- and first-order oracles, respectively. The quantum algorithm takes $O(d^{2.5}/\epsilon^{3.5})$ and $O(d^2/\epsilon^3)$ queries to the two oracles, giving a polynomial speedup over the classical counterparts. As a complement, we characterize the domains where quantum algorithms can find an $\epsilon$-SOSP with poly-logarithmic, polynomial, or exponential number of queries in $d$, or the problem is information-theoretically unsolvable even with an infinite number of queries. In addition, we prove an $\Omega(\epsilon^{-12/7})$ lower bound on $\epsilon$ for any randomized classical and quantum algorithm to find an $\epsilon$-SOSP using either noisy zeroth- or first-order oracles.

Published as a conference paper at ICLR 2025
ROBUSTNESS OF QUANTUM ALGORITHMS FOR NONCONVEX OPTIMIZATION
Weiyuan Gong"
School Engineering and Applied Science
Harvard University
Allston, MA 02134
wgongåg harvard.
Chenyi Zhang"
Computer Science Department
Stanford University Stanford, CA 94305
chenyiz@stanford.edd
Tongyang Li
Center on Frontiers of Computing Studies and School of Computer Science
Peking University
Beijing, 100871
tongyangli@pku.c edw.
ABSTRACT
In this paper, we systematically study quantum algorithms for finding an approximate second-order stationary point (eSSOSP of d-dimensional convex function, fundamental problem nonconvex optimization, with noisy zeroth- first-order oracles inputs. We first prove that, up to noise of perturbed accelerated gradient descent equipped with quantum gra- dient estimation takes Ollog d/e).78) quantum queries find e-SOSP. We then prove that standard perturbed gradient descent is robust to the noise of O(e"/ /d*) and O O(e/d0.5+C) for any Ç tively, which provides quantum algorithm with poly-logarithmic query com- plexity. Furthermore, we propose a stochastic gradient descent algorithm using quantum mean estimation the Gaussian smoothing of noisy oracles, which is robust to O /d) and O(e/vd) noise on the zeroth- and first-order oracles, re- spectively. The quantum algorithm takes Odd- /c3.5 and Odd2 queries to the two oracles, giving polynomial speedup over the classical counterparts. As a complement, we characterize the domains where quantum algorithms can find 6-SOPP with poly-logarithmic, polynomial, exponential number of queries in d, or the problem is Enformation-thhorriieee number of queries. In addition, we prove an 1(c=12/7) lower bound on c for any randomized classical and quantum algorithm find an e-SOPP using either noisy zeroth- or first-order oracles.
on the zeroth- and first-order oracles, respec-
unsolvable even with an infinite
"Equal contribution.
1 "orresponniig author.

---

Published as a conference paper at ICLR 2025
INTRODUCTION
Optimization theory is central topic in computer science and applied mathematics, with wide appli- cations in machine learning. operations research, statistics, and many other areas. Currently, various quantum al algorithms for optimization have been proposed, ranging from linear programs (Casares &
Martin- Dertin-Delgado/ 2020; Rains] [199) and semidefinite programs (Brandão & Svore 2017 Brandão et al. 20199; van Apeldoor & Gilyén 2019; van Apeldoorn et al.) (002bb) to general convex opti-
mization (Chakrabarti et al. [020 van Apeldoom et al.. 2020a; (iifford & Zhang (023) and non-
convex optimization (Zhang et al. 2021 Liu Liu et al., 2023 Leng et al. 2023 Chen et al. (223)).
crucial factor of quantum optimization algorithms is their robustness. On the one hand, current quantum applications suffer from noises generated by near-term quantum devices (Preskill 2018))
which may create adversarial perturbations in the worst-case that result in disastrous failures. To ad- dress this issue, certain quantum algorithms or their components such as some adiabatic quantum algorithms (Childs et al., 200T), quantum gates (Harrow & Nielsen, 2003), and machine learning specifically designed to be robust against experimental noise or noisy quantum queries (Buhrman et al. 2007). An alternative solution is develop error correction (Gottesman 1997) or error mitigation (Endo al., [018]] 2021] mechanisms to reduce the influences of experimental noises. In the context of nonconvex op- timization, developing robust quantum algorithms essential for future practical implementations of these algorithms on near-term devices.
algorithms (Liu et al., / al. 2015 Lu et al. 20200
On the other hand, robustness is a natural and erucial requirement for solving classical optimization problems. For instance, in statistical machine learning, we are given data drawn from an underlying probability distribution D (i.e.. the population), and the goal to optimize an objective function known as the population risk F, defined as
F(0) = EZ (LL(
where the expectation is taken over all possible continuous loss functions {L(-:2) with z D. Since direct access to F unavailable, is commonly approximated by the empirical risk function ʃ(0) _/ Σ i= [(0;20 2.). which is computed from a finite set of n samples. The task of optimizing F usinn access to its empirical counterpart f is known as empirical risk minimization (Belloni et al., 2015 Jin et al. 2018a| Vapnik [991). In this setting, noisy evaluations of F can give rise to poorly behaved landscapes, potentially containing an exponential number of shallow local minima- even when F itself exhibits favorable properties such smoothness or Lipschitz continuity (Auer al.,
1995 Brutzkus & Globerson 2017).
Based this observation, line of prior works classical optimization (see e.g. Bartlett & Mendel-
son 2002); Boucheron et al. (2013) studies the setting where we have access to a function f that is pointwise close the actual objective function F.
F - fllo S.
(2)
where the error usually decays with the number of samples. Under this assumption, f may still be non-smooth and contain additional shallow local minima independent of F. Nevertheless, the pointwise closeness between f and F can be leveraged to escape highly suboptimal local minima that exist only in f and to approximate a local minimum of F.
Another related setting involves finding local minima of F using empirical first-order informa- tion (Jin et al., Sa). Similar to Eq. 2 we assume access to a noisy gradient f that remains uniformly close to the actual gradient VF. This model widely used in stochastic settings, where gradient estimations are obtained through sampling procedure using zeroth-order function values. well-known example is stochastic gradient descent [Jin et al., 2021 Sun| 2019), in which an ap- proximate gradient is obtained by sampling mini-batch function values. As the mini-batch size m increases, the gradient estimate converges to the true gradient with high probability:
|VF-
f v
where the error i typically decreases with the mini-batch size m. Here, |VF- maximum infinity norm taken over both the input and the d entries of the gradient
Vfll denotes the
Various approaches (Belloni et al. 2015 Zhang et al. 2017
Jin et al. 2018a Risteski & Li 2016
Singer & Vondrák 2015 Karabag al. 2021 Roy et al. 2020 Zhang et al. 2022) have been
2

---

Published as a conference paper at ICLR 2025
developed to analyze the robustness of optimization algorithms from different perspectives. For example, Belloni et al. (2015) proposed an algorithm for finding an e-approximate minimum of an approximate convex function. where is the precision guarantee for the optimization output (see Assumption 1.1 Assumption 1 1.2 for the formal definition). This algorithm requires Ö(d 22 queries to the stochastic noisy function evaluation oracle, which has zero-mean and sub-Gau aab-Gasssian distributed noise. More recently. Li & Zhang (2022) developed quantum algorithm with query complexity ((d5/e) for the same task, giving a polynomial quantum speedup. In another direc- tion, Singer & Vondrák (2015) established an information-theoreiic lower bound for any convex optimization algorithm that seeks minima within an e multiplicative error using noisy function eval- uation oracles. In the same setting Risteski & Li (2016) developed an algorithm whose dependence on matches this lower bound.
In nonconvex optimization, Chen et al. (2020); Zhang et al. (2117) developed efficient classical al- gorithms to escape poise-induced "shallow" local minima using simulated annealing and stochastic gradient Langevin dynamics (SGLD). These algorithms assume access to an oracle with bounded noise v < O(<2/d)) where e the precision and d is the dimension of F. More recently. JJin et al. 2018a) proposed algorithms for escaping saddle points using polynomial number of queries to zeroth- or first-order noisy oracles, with bounded noise of order D(el.5/d) and O(e/Vi) respec- tively. On the quantum side, Zhang Li (202T) Childs et al. (202)) developed quantum algorithms for escaping saddle points via quantum simulation. Their approach leverages a precise quantum evaluation oracle and applies Jordan's 's algorithm to compute the gradient exponentially faster than classical algorithms using classical evaluation oracles. While quantum evaluation oracles inherently suffer from both empirical loss and experimental noise in physical implementations, the study of nonconvex optimization using quantum algorithms with noisy evaluation oracles remains largely unexplored. This motivates us to systematically investigate the robustness of quantum algorithms in escaping saddle points under such noise. Moreover, we discuss the noise threshold to guarantee the existence of polynomial -uurry classical algorithms for finding an c-approximate local minimum of F.
Nonconvex Optimization with Noisy Oracle. In this work, consider twice-differentiable target function F: Rd + R satisfying
B-bounded: supxER" [F()]] S B:
* F is f-smooth (f-gradient Lipschitz); [| [IF S f||x| -xel. Vx1, E Rd;
F p-Hessian Lipshitz: [[)) V F(xx) S p||x: x2ll. Vx1, Rd.
The goal is to find an c-approximate second-order stationary point (cSOSPP such that
FF c, Amin (22((x)) 2 -Vp..
(4)
Instead of directly querying F, we assume access to a noisy function f that is pointwise close to F. Assumption 1.1 (Noisy evaluation query). The target function F B-bounded, f-smooth, and p-Hessian Lipschitz, and we can query a noisy function f that is v-pointwise close to F::
F - fllec I v.
(5)
Moreover, we consider the problem of finding an e-SOSP of with an alternative assumption, where the gradient f is pointwise close to V..
Assumption 1.2 (Noisy gradient query). The target function F is B-bounded, e-mmooth, and p- Hessian Lipschitz, and we can query the gradient g == V of an I-smooth function f. The gradient of f is pointwise close gradient of F:
IVF /llbo < E.
'The Ô notation omits logarithhi terms, i... Ö(g) Ogg goly
2 A more general target is to find an (c, (c.7)-SOSP x such that || || <
and Amii ( F())) 2 -yy
The definition of an c-SOSP in was proposed first by Nesterov & Polyak (2006) and has been taken as
standard assumption in the subsequent papers (Jin et al. 2017] 2018b Xu et al. [017 2018 C Carmon et al.
2018 Agarwal al. 2017 Tripuraneni et al. 2018 Fang al. 2019 Jin 2021 /Zhag et al. 2021
3

---

Published as a conference paper at ICLR 2025
In quantum computing, the oracles unitary operators rather than classical procedures. Under Assumption 1.1] one can query a quantum evaluation oracle (quantum zeroth-orde oracle) Us which can be represented as
Uy(lx) & 0)) x) @ lf(x))
Vx E Rd.
(7)
Furthermore, quantum oracles allow coherent superpositions of queries. Given vectors (xx) ..... (mm) E Rd and coefficient vector E C such that Σi= /c,/ 1, the quantum oracle outputs U2 C (x,) 6 (0)) - Di=r c, lx,) & [x())) Compared to the classical evaluation oracle, the ability to query different locations simultaneously in superposition is the essence of quantum speedup.
Similarly, in the first-order scenario we assume that one can access the quantum gradient oracle Ug under Assumption 1.2] which can be represented
Ug x) ? (0)) + X) & [V(()))
VX E Rd
(8)
We remark that the quantum oracles defined above are natural extensions of their classical coun- terparts. Similar definitions of quantum oracles are widely used in prior works (Chakrabarti al.
2020 Zhang & Li 2021 Apeldoorn et al. 2020: Garg et al. [02 Zhang & Li (023). Notably, if a classical oracle established by a classical arithmetic eircuit (composed of additions, multiplica- tions, divisions, etc.), it is standard to construct quantum circuit of the same size for the arithmetic calculations (quantum additions, multiplications, divisions, etc. that enable these calculations in superposition) as the corresponding quantum oracle. Consequently, rithms hold promise to outperform black-box classical algorithms in low-dimensional settings where the oracle is given as explicit circuit. In other words, are not assuming the oracle for free, but we consider the same black-bor box optimization setting as the classical counterpart, with essentially the same cost of constructing the oracle.
believe quantum algo-
Contributions. In this paper, we conduct a systematic study of quantum algorithms for nonconvex optimization using noisy oracles. Using zeroth- or first-order oracles as inputs, we rigorously char- acterize different domains where quantum algorithms can find an e-SOSP using poly-logarthhmi, polynomial, or exponential number of queries, respectively. We identify the domain where it is information-the coomaatio-theoreticaall theoretically unsolvable to find an c-SOSP even using an infinite number of queries.
In some of the domains, we further develop lower bounds on the query complexity for any classical algorithms, and thus establish polynomial or exponential quantum speedups compared to either the classical lower bounds or the complexities of corresponding state-of-the-an classical algorithms. We summarize our main results under [Assumption 1.1 and Assumption 1.2 in Table 1 and Table 2] respectively. We (informally) introduce our results in this main body of the paper and provide the intuition for the proofs. We leave the formal version of our results, the corresponding algorithms, and the proofs to the full version of the paper (see supplementary materials).
Noise Strength
Classicul Bounds
Quantum Bounds
Speedup
" 1((1.5)
Unsolvable (Jin et
2018a
Unsolvable Theorem 3.2
N/A
O(e'-),,v= Me */d)
(d)xpdd), 20 Jin et 2018a
Q(ddaga)
Theorem 3.1
N/A
v Ole v= = (2()
O(d+/e5) et al.
2018a
Zhang et al. 2017
Theorem 2.5
Polynomial
(i, 1/9)
1idd d)
Theorem 3.3
Ollog d/e")
Theorem 2.3
Exponential
O(e")/do)
Oid/ log dy Theorem 3.3
O(log 1.6 1.76
Thearem 2.2
Exponential"
Table I: A summary of our results and comparisons with the state-of-the-art classical upper and
lower bounds under (Assumption 1.1 The query complexities are highlighted in terms the dimen- sion d and the precision (*) In the last row, we can obtain the desired classical lower bound and thus exponential speedup in the query complexity when (1ppolyll/dee)) works for 2(poly(1/ddd))
Theorem 3.3
2
UPPER BOUNDS
In this section, we propose different quantum nonconvex optimization algorithms that are robust against different levels of noise. The starting point is the quantum perturbed accelerated gradient
4

---

Published as a conference paper at ICLR 2025
Noise Strength
Classical Bounds
Quantum Bounds
Speedup in d
F (2(c)
Unsolvable Theorem 3.4)
Unsolvable Theorem 3.4
N/A
V O(e), D = ())
Md ")
Theorem 3.4
M(d
Theorem 3.4
N/A
8 O(e/d0.5)
Old /e")
(Ji et al. 2018a
(ld )
Theorem 2.6
Polynomial
V Ole/du.5t))
Oglog' d/e*) Corollary 2.4
O(log' d/e") Corollary 2.4
No
Table 2: A summary of our results and comparisons with the state-of-the-art classical upper and lower bounds under Assumptonn 1.2 In the last line, Ç > and Ç = (og(())))))))))))))))))))))))/ (for instance, this is satisfied for any constant Ç > 0).
descent (PAGD) with accelerated negative curvature finding algorithm, which is inspired by the noiseless nonconvex optimization algorithm in /Zhang & Li (022)) To find an c-SOSP of F using quantum evaluation oracle specified in (7), an important step is to approximate the gradient each iteration. An ingenious quantum approach initiated by (Jodaan (2005) takes a uniform mesh around the point and queries the quantum evaluation oracle (in uniform superposition) in phase using the standard phase kickback technique (Chakrabarti et al. 2020 Gilyén et al. 2019). Then by the Taylor expansion, we have
explif(x))x
Σ exp A=
0f 0xx
Xx
Xk-
The algorithm finally recovers all the partial derivatives by a quantum Fourier transformation (QFT). We refer to Chakrabarti et al. (2200) for precise version of Jordan's gradient estimation algorithm.
Lemma 2.1 (Lemma 2.2, Chakrabarti et al. (2020)). Given target function F and its noisy evalu- ation f satisfying Assumption 1.7 with noise rate v. there exists a quantum algorithm that uses one query to the noisy oracle defined ( and outputs a vector 4 Fx)) such that
Pr FF(x) VF(x) 2 400wdv < min
d
Ye > 1.
(10)
1
This lemma shows that with probability least - one can use one query to the noisy zeroth- oracle and obtain a vector Fx()) such that
FF(x) - VF(x) s(d
(11)
Our quantum perturbed accelerated gradient descent (PAGD) algorithm (see Algorithm in the
supplementary material for details) replaces the gradient queries in Perturbed Accelerated Gradient
Descent (Zhang & Li [021] Zhang & Gu 2022 with Jordan's 's gradient estimation. The cost of this
substitution is analyzed using Lemma 2.1
2.1 TINY NOISE: ROBUSTNESS OF PERTURBED ACCELERATED GRADIENT DESCENT
We consider adding tiny noise to the oracles in quantum gradient descent algorithms. In particular, we consider the function pair (F, f' satisfying Assumption 1.1 and assume that one can access the function values of the noisy evaluation function f. We remark that ff may even be non-differentiabl moonh.. In addition, the noise between f and the target function F might introduce additional SOSPs. Nevertheless, recent work Zhang & Gu (2022) indicates that the performance of PAGD (Tin) et al. 2018b Zhang & Li| (202)) persists when the gradients are inexact. We rigorously prove that the perturbed accelerated gradient descent algorithm with accelerated negative curvature (Zhang &
Li 2021) equipped with Jordan's 's algorithm for quantum gradient estimation (Jordan 2005) robust to the tiny noise on zeroth-order oracles as follow:
Theorem 2.2 (Informal). Given a target function F and noisy function satisfying Assump- lion 1.7 with 10 /d²), there exists a quantum algorithm that finds e-SOSP of F with high probability using Ölog 1.75) queries the noisy geroth-order oracle Uy.
We leave the formal version of Theorem 2.2 the corresponding algorithm, and the proof to Sec- tion 2.1 of the supplementary material. Theorem 2.2 demonstrates that if the noise is small
5

---

Published as a conference paper at ICLR 2025
enough, the impact PAGD algorithm will not lead to an increase on the query complexity. If v = ((pooy(e,1/dd). we further demonstrate that this robustness only exists for quantum algo- rithms by proving a polynomial lower bound in Theorem 3.3 for any classical algorithm.
2.2 SMALL NOISE: ROBUSTNESS OF QUANTUM GRADIENT ESTIMATION
When the strength of noise increases, the negative curvature estimation in standard PAGD will fail. In this case, we show the robustness of the gradient descent algorithm with quantum gradient esti- mation against the noise. We consider the function pair (F. f) satisfying Assumption 1.1 when we can access noisy function f. Z.Zang et al.] (2021): Chakrabarti al. (2020) conveyed the conceptual message that perturbed gradient descent (PGD) (Jin et al.) (021) algorithm with Jordan's 's gradient estimation (Jordan] 2005) possesses a certain degree of robustness to noise. In this work, we formal- ize this intuition by presenting concrete analysis on the convergence rate of PGD with noise, and obtain the following result:
Theorem 2.3 (Informal). Given a target function F and a noisy function f satissying Assump- tion 1.1 with v I (c /dt), there exists a quantum algorithm that finds an c-SOSP of F with high probability using Ö(lgg* d/e²) queries to the noisy zeroth-onder oracle U--
The formal version of Theorem 2.3 the corresponding algorithms, and the proof are given in Sec- tion 2.2 of the supplementary material. [Thoormm 2.3 demonstrates if the noise on the zeroth-order oracle is below a certain threshold, a quantum algorithm can find an c-OSSP of F within a num- ber of queries that is poly-logarithmic in terms of the dimension d. Similar to Theorem 2.2, this robustness only exists in quantum algorithms and provides an exponential quantum speedup in the query complexity compared to the classical counterpart. The key insight for such a speedup as follows. While polynomial number of queries in dimension d is required for classical algorithms to compute the gradient using zeroth-order oracles, quantum zeroth-order queries enable querying function values at different positions in parallel due to quantum superposition. As result, Jordan's algorithm for quantum gradient estimation computes the gradient using exponentially fewer queries compared to classical counterparts, and such speedup is robust to noise up to O(c%/dt)
seems that Theorem 2.2 and Theorem 2.3 provide exponential speed-ups only when the noise thresholds that decay as o 20 (d)) or %dd). However, we will prove later (see Theorem 3.1 that when the noise rate is larger than 22 5.5 /d) a superpolynomial query complexity lower bound of (ddogdd queries for both classical and quantum algorithms is proved in our work. This suggests that we have to focus on the noise regime below Oce (////d) where one can find an algorithm (either classical or quantum) that only requires polynomially many queries in d. Compared this threshold, the noise threshold of ((c')/d²) or O(e" O(c%/at) where quantum algorithms have exponential speed- ups compared to classical ones only polynomially small. We can thus conclude that the noise regime where an exponential quantum speedup is within reasonable amplitude compared to the noise regime where polynomial classical and quantum algorithms for this task exist.
We further extend Theorem 2.3 to function pair (F, satisfying Assumption 1 1.2 In particular, we prove the following corollary indicating that the classical PGD iteration is robust against the noise of ū O(e/d055+5 on the first-order gradient information, where 221/ log(d)) (d)). In addition, can use the techniques above to prove the algorithmic upper bound for function pair (F, f) satisfying
Assumption 1.2 with & < O(c/d05-4 for <> 0 and ((1/log(d). We provide the following
corollary corresponding to the last line in Table 2
Corollary 2.4. Given a target function F and noisy function f satisfying Assumption 1.2 with < O(e/d (5//0 for Ç > and Ç = (111 /og(()))))) There exists an algorithm that outputs an <-SOSP of F satisfying Eq. using Olog* d/e) queries to Ug in 8 with high probability.
2.3 INTERMEDIATE NOISE: SPEEDUP FROM QUANTUM MEAN ESTIMATION
When the strength of noise keeps increasing, the robustness of Jordan's algorithm will also fail to handle the gap between the noisy function f and the target function F. To address this issue, we develop quantum algorithm based on the Gaussian smoothing of f inspired by Jin et al. (201a)). We consider function pairs (F. () satisfying Assumption 1.1 We sample the value z zf((x + z)
f (x))/o², where z ~ (0, a² TT is chosen from the standard Gaussian distribution with parameter

---

Published as a conference paper at ICLR 2025
a² Duchi et al. 2015). We then apply quantum mean estimation to approximate the gradient from the samples of stochastic gradients. The performance of the algorithm is guaranteed as follows:
Theorem 2.5 (informal). Given target function F and a noisy function f satisfying satisfying/Assumppae Assumption 1.I with v S O S /d), there exists quantum algorithm that finds an e-SOSP of F with high proba- bility taking ( (e2.5 queries to the noisy zeroth-order oracle U.-
The formal version of Theorem 2.5] the corresponding algorithms, and the proof are given in Sec- tion 3.1 of the supplementary material. Theorem 2.5 that the quantum algorithm can find an c-SOPP of F using polynomial number of queries
with bounded noise strength v I O(cl.6/6 /d). As the state-of-art classical algorithm (Jin et al. 2018a) solves this problem with the same noise strength I O /d) using O(d* ((" queries, our algorithm provides polynomial improvement compared to this classical result in both the dimension d and the precision
We consider the problem of finding an e-SOSP of functions F taking queries to the quantum gradient oracle in (8) Our approach leverages the fact that V V + z) is stochastic gradient function of the Gaussian smoothing of f where ~ NO, o²1) is chosen from Gaussian distribution with parameter o². Similar to the zeroth-order scenario, apply quantum mean estimation to approximate the gradient of the Gaussian smoothing, which leads to the following algorithmic upper bound.
Theorem 2.6 (Informal). Given a target function F and the gradient information of a noisy function I satisfying Assumption 1.2 with ù s D(e/d..5), there exists quantum algorithm that finds an 6- SOSP of F with high probability using (dd² ((dd(c")) queries to the noisy gradient oracle Ug.
The formal version of Theorem 2.6 the corresponding algorithms, and the proof are given in Sec- tion 3.2 of the supplementary material. The tolerance on i' and the query complexity is larger compared to Theorem 2.5] where we access zeroth-order oracle. The best-known classical algo- rithm finding an 6-SOSP requires Odd² /c*) queries. Hence, this quantum algorithm also provides polynomial reduction in the sample complexity compared to the classical result.
LOWER BOUNDS
Deterministic Classical
Randomized Classical and
Input Oracle
Noise Strength
Lower Bounds
Quantum Lower Bounds
Zeroth-order
0
N/A
Zeroth-order
92(E 16/T/d)
Q(E 12/7
li 12/7)
Theorem 3.5
First-order
D 0
Carmon et al. 2021
N/A
First-order
DiE 8/7 8/T/Vd)
N(E 12/7)
Theorem 3.5
Table 3: A summary of results classical and quantum query complexity lower bounds in under AAssmmttin 1.1 or [roAosuumption 1.2 respectively. The query complexities are highlighted in terms of the dimension d and the precision e.
3.1 LARGE NOISE: QUANTUM QUERY COMPLEXITY LOWER BOUND IN
In this work, we also provide lower bounds concerning d the query complexity required for any classical and quantum algorithms under Assumption 1.T and Assumption 1.2 particular, we construct a hard instance inspired by Jin et al. (2018a) (as shown in the left of Figure I (a)): define a target function F hypercube and use the hypercube to fill the entire space Rd. We start from "scale free" version of function pair (F, where assume p and 1. Denote
sin x == (sin(x1)..... sin (xa)) and T(A) as the indicator function that has value 1 when A is true and otherwise. We choose some constant μ and define the target function as
F(x) = h(sinx) + ||sin x
(12)
2 (v for some polynomials such that the landscape of the function is given the right of Figure 1 [). Here, the vector is uniformly chosen from the d-dimensional unit sphere. In addition, we can split the domain into different regions upon which analysis and constructions are made separately:
where ((x) := lv x) h2

---

Published as a conference paper at ICLR 2025
D(/aa)
S
Sv
3/μ
3/p
Area of +8008
Anga of +-SOS
Figure 1: (a) The Sketch of the hard instance function for Theorem 3.1 The left figure illustrates the construction in the domain and the right figure shows two-dimensional example. (b) The construction of the hard instance function for Theorem 3.4
"ball" 300,3/p) fx R ||>|| 3/m} is the d-dimensional hyperball with radius 3/p.
"band" S, = (00,3/)) (sin v) log d/ d/V
We provide the landscape of F and the region division in Figure (a). The above construction happens within a hyperball and we cannot fill the entire space IK with hyperballs. Therefore, we embed this hyperball into hypercube and add two regions.
"hypercube" H = [- xt x/2/ is the d-dimensional hypercube with length "padding" S₂ H 3/0,3/u).
With the above construction, we can fill the space Rd using these hypercubes. Meanwhile, the noisy function f is defined as
sin x Sv. f(x) F((x),
(13)
ę Sy.
The "band" region Sy is known as the non-informative region as any query f in this area will obtain no information regarding v. Intuitively, the metric of the non-informative area approaches as d increases according the measure of concentration. and quantum) to find a point out of this region. In particular, the probability of classically querying a point on S, is bounded below by
hard for any algorithm (both classical
Area (S)) Area Area(B(O,, (0,3/n)) 2 1 Odd log
(14)
By adding noise to the zeroth- or first-order oracle f. we can erase the information of such that limited number of classical quantum queries cannot find any e-OOSss with high probability. For a function pair (F, f) satisfying AAssumption 1.1 our first result in this part the following quasi-polynomial lower bound.
Theorem 3.1 (Informal). We can find functions F and satisfying Assumption 1.1 with (.. /d) such that any quantum algorithm requires at least Ridlog queries to Ug to find any e-SOSP of F with high probability.
Here, we provide the intuition. Consider function in a hyperball B(O, r) and embed the hy- perball into hypercube, with which we can cover the whole space. Next, we introduce noise to create f with non-informative area around 0 (in the sense that any query to this area will obtain no information about any SOSPs of the target function F"). Then, we transfer this problem into an unstructured search problem. The final lower bound for nonconvex optimization is obtained by applying the quantum lower bound for unstructured search. We mention that the and the d depen- dence for v in Theorem 3.1 are tight up to logarithmic factors. The classical version of Theorem 3.1 is proved in Jin al. (20T8a). The parallelism in quantum algorithms possesses the potential to
8

---

Published as a conference paper at ICLR 2025
query different points in superposition. However, Theorem 3.1 demonstrates that the same query complexity lower bound holds even for quantum algorithms.
If the noise keeps increasing, can further prove the following lower bound that prevents any quantum algorithm from finding any e-SOSPs of target function F:
Theorem 3.2 (Informal). For any quantum algorithm, there exists a pair functions f) satisfy- ing Assumption 1.7 with v = (c)..b) such that it will fail, with large probability, find any c-SOSP of F given access to f.
Despite the quantum lower bound, we also propose a classical lower bound concerning nonconvex optimization using zeroth-order oracle with noise strength v = O =((1poll(d)),
Theorem 3.3. For any 6 S 6o < where eo is some constant, there exists a function pair (F, satisfying Assumption 1.1 with v/ = (2(1/ pd)y,d)), such that any classical algorithm that outputs an e-SOSP of with high probability requires at least St(d/ log d) classical queries to f.
argument inspired by [Chakrabarti et al. 2220 Theorem Theorem 2.3] and [Theorem 3.3] establish the exponential separation between classical and quantum query complexities required for nonconvex optimization using oracles with noise y = (2ollyyypee (c. 1/d)). This separation originates from the Jordan's 's gradient estimation algo- rithm (Jordan 2005). Classically, querying the evaluation oracle can only provide information at one point. Quantumly, however, one can take the superposition on different points and query the quantum evaluation oracle parallel (Gilyén et al. 2019 Chakrabarti et al. 2020).
We prove Theorem 3.3 using an information-theoredd
Moreover, we can extend the above lower bound to function pairs (F, f) Assumpiion 1.2 If the noise increases by even factor that is logarithmic in d from @(c/d"55 exponential lower bound for any classical or quantum algorithm through a similar construction of hard instance used in Theorem 3.1 (as shown in Figure (b)). Unlike Theorem 3.1. we cannot directly apply the hard instance (F, ) defined above because / is not differentiable (or more strictly, not continuous). To address this problem, we construct a different noisy function f. For simplicity, we focus on the "scale free" version here are leave the details in the full version of the paper. We still define the target function F(x) = h(sin x) + ||sin x|| which is the same with 12)) We uniformly choose v and divide the "hypercube" into different regions including: "hypercube"
can prove an
[-r// /2/2,///2' is the d-dimensioonal hypercube with length æ; "ball" BB0, 3/μ² [x E Rd ||a]|| < 3/11 is the d-dimensional ball with radius 3/ pr; "band" S = {x E B(0,3/p)) (sin v) S w) with w = (log d/ vd); and "padding" S2 = H BO,, 3/p). In particular, a new region is added as
"non-informative band" S, {x E (B003/14) (sinx, v) S 0.9w).
Meanwhile, the noisy function f defined as
sin x|1 x Sv;
f(x)
s + g(x),
x S- Sy
(15)
F(xx, x S,
where g(x) = hx(x)) 122 (e(V ||sin x|| (vT sin 2) and ha = (v sin(10x - 9owv /2))
Moreover, if the noise increases to R(E)., there exists similar hard instance with Theorem 3.2 that prevents any classical or quantum algorithm from finding any e-SOPP of F. Formally, we can extend Theorem 3.1 and
and Theorem 3.2 in the context of Assuumttioo 1.2)
Theorem 3.4 (Informal). We can find functions F and f satisfying Assumption 1.2 with i ((e/d0.5) such that any quantum (classical) algorithm that finds an e-SOSP of F with high proba- bility requires at least ((ddogd) queries to Ug. Moreover, can find functions F and f satisfying Assumption 1.2 with i = ((e) with any quantum (classical) algorithm failing with high probability.
3.2 QUANTUM QUERY COMPLEXITY LOWER BOUND IN E
Finally, we establish query complexity lower bounds for classical and quantum nonconvex optimiza- tion algorithms under Assumption 1.1 or Assumption 1.2, respectively (summarized in Table 3).
Theorem 3.5 (informal). There exists a function pair F and f satisfying either Assumption I.1 or Assumption 1.2 with 1667 /d) ū 2 8/7 /Vd). respectively, and additionally

---

Published as a conference paper at ICLR 2025
F(0) infx F(x) < A for some constant A, such that any classical quantum algorithm with query complexity ( 12/7) will fail with high probability to find an e-SOSP of target t function F.
The intuition for Theorem 3.5 employs the hard instance inspired by Carmon et al. (2020) 202 Previously, there have been two lower bounds concerning e dependence that apply to classical al- gorithms for nonconvex optimization. In Carmon et al. (2020), it is proved that at least (((-3/2) queries are required by finding e-SOSPs of a Hessian Lipshitz function F even provided both zeroth- and first-order oracles for either random or deterministic classical algorithmss. Using similar tech- niques, Carmon et al. (2021) further proved that deterministic classical algorithms using first-order noiseless oracle require 92(c 12/7) queries to find an c-SOSP of a Hessian Lipshitz function F.
On the other hand, despite recent results on quantum lower bounds for optimization (Garg et al. bb2 Zhang & Li, 2023), there are settings where quantum lower bounds remain unresolved. Specifically, although Zhang & Li (2023) showed that there is no quantum speedup for finding an e-FOSP of p-th order smooth function with p-th order oracle for any p, it remains unclear whether a quantum speedup exists for finding an e-SOSP of a Atessian-Lipschite function with only gradient oracle, where the order of the function smoothness and the given oracle differ. Notably, this problem has been widely investigated in previous works on classical nonconvex optimization, e.g., Agarwal et al. (2017): ) Allen-Zhu & Li (2018); Liu et al. (018)) In this paper, fill this conceptual gap by extending the classical deterministic lower bound by Carmon et al. (2021) to all classical randomized algorithms and even quantum algorithms, given that noise exists in the function evaluation. In particular, noise allows us to construct hard instance by creating a non non- informmrreeeve area around O. According to the concentration of measure phenomenon, the non-informative area will occupy an overwhelming proportion of the whole space. Technically, our hard instance is also different from Carmon et al. (202T) in the sense that we replace its quadratic scaling function by a sine function as we have an additional B-bounded assumption on the function. Similar to Garg et al.) 2022a b): Zhang & Li (203), the hard instance we construct here exhibits a similar property that, if the number of quantum queries is below a certain threshold, in expectation the output state will barely change if we replace the quantum oracle by an oracle that only encodes "partial" information of the objective function, where the missing information is crucial for any (classical quantum) algorithm to find an e-SOSP of F. Moreover, our lower bound result in Theorem 3.5 be extended to finding e-SOSPs when waive the B-hounded requirement on F.
4 DISCUSSIONS
In the paper, we conduct systematic study on the query complexity for quantum algorithms to find e-SSSP of a nonconvex function using noisy oracles. We prove a series of upper and lower bounds under different noise regimes for first-order and second-order oracles. Our paper leaves several open questions for future investigations:
Can we further improve quantum algorithms for the task of nonconvex optimization using noisy oracles? Can we obtain quantum algorithm with better dependence d and compared to Theorem 2.5)
Can we characterize optimal quantum query complexity for nonconvex optimization? We would like to point out that for all noise ranges, nonconvex optimization in the classical setting does not have optimal bounds either, as shown in Table I and Table 2 As a result, proving optimal quantum query complexity bounds may solicit more techniques and hard instances. It is helpful to investigate sublinear or poly-logari quantum lower bounds in dimension d on general optimization problems using either noiseless or noisy oracles.
We employ a simple model on the noise: only the upper bound of noise strength is consid- ered. In general, can we demonstrate the robustness and speedups for nonconvex optimiza- tion algorithms analytically under other noise assumptions (say, more practical quantum noise models or stochastic noise models)?
A further question one may ask is the quantum version of minimax optimal query com- plexities. Although this is better understood in classical information theory, in the quantum setting this is widely open in general. Some existing results can calculate the success prob- ability of quantum algorithms when we have a fixed number of quantum queries (Zhandry) 2015 2021), but their minimax properties are still open.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENT
We thank Yizhou Liu for helpful discussions about the quantum tunneling walk in Liu et al. (2023). TL was supported by the National Natural Science Foundation of China (Grant Numbers 92365117 and 62372006), and also the Tianyan Quantum Computing Program.
REFERENCES
Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approxi- mate local minima faster than gradient descent. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1195-1199 2017. arXiv 1611. 01146
Zeyuan Allen-Zhu and Yuanzhi Li. Neon2: Finding local minima via first-order oracles. In Advances in Neural Information Processing Systems, pp. 3716-3726, 2018. arXiv/1711. 06673
Joran van Apeldoom, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimization using quantum oracles. Quantum, 4:220, 2020. 1809. 00643]
Peter Auer, Mark Herbster, and Manfred K. Warmuth. Exponentially many local minima for single neurons. In Advances in Neural Information Processing Systems, volume 8, 1995.
Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):433-48) 2002.
Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, and Alexander Rakhlin. Escaping the local minima via simulated annealing: Optimization of approximately convex functions. In Con- ference on Learning Theory, pp. 240-265. PMLR, 2015. arXiv/1501.0722 07242
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymp- totic theory of independence. Oxford university press, 2013.
Fernando G. S. L. Brandão and Krysta M. Svore. Quantum speed-ups for solving semidefinite programs. In 2017 IEEE 58th Anmual Symposium on Foundations of Computer Science (FOCS), pp. 415 426. IEEE, 2017. arXiv 609660.000 05537
Fernando G.S.I.. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Yu Lin, Krysta M. Svore, and Xi- aodi Wu. Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learn- ing. In Proceedings of the 46th International Colloquium on Automata, Languages, and Program- ming, volume 132 of Leibniz International Proceedings in Informatics (LIPlcs), pp. 27:1-27:14. Schloss Bagsstuhl-LeibnizzZenntee
fuer Informatik, 2019. 1rXiv 02581
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaus- sian inputs. In International Conference on Machine Learning, pp. 605-614. PMLR, 2017.
arXiv 07966
Harry Buhrman, Ilan Newman, Hein Rohrig, and Ronald de Wolf. Robust polynomials and quantum algorithms. Theory of Computing Systems, 40(4):379-33) 2007.
Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal Optimization, 1752):15 2018. 1rXiv
Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points I. Mathematical Programming, 184()) (1):71):112,, 2020. a 116.1.100..1166..
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points II: first-order methods. Mathematical Programming,
185(1)331--355, 2021.
Pablo A. M. Casares and Miguel Angel Martin-Delgado. quantum interior-point predictor- corrector algorithm for linear programming. Journal of physics A: Mathematical and Theoretical, 53(44))445305, 2020. arXiv/1902... 06749
Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization. Quantum, 4:221, 2020. arXiv 1809. 01731

---

Published as a conference paper at ICLR 2025
Xi Chen, Simon S. Du, and Xin T. Tong. On stationary-pon ppint hitting time and ergodicity of stochastic gradient Langevin dynamics. Journal of Machine Learning Research, pp. 1-40, 2020. urXiv[1904.1300
Zherui Chen, Yuchen Lu, Hao Wang, Yizhou Liu, and Tongyang Li. Quantum Langevin dynamics for optimization, 2023, arXiv/2311. 15587
Andrew M. Childs, Edward Farhi, and John Preskill. Robustness of adiabatic quantum computation. Physical Review A, 65(1):01232, 2001.
Andrew M Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, and Chenyi Zhang. Quantum simulation of real-space dynamics. Quantum, 6:860, 2022.
Andrew W. Cross, Graeme Smith, and John A. Smolin. Quantum learning robust against noise. Physical Review A, 92(1):012327, 2015, arXiv 5087
John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono. Optimal rates for 7ero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5):7788-2866, 2015, arXiv 1312. 1312.2139
Suguru Endo, Simon C. Benjamin, and Ying Li. Practical quantum error mitigation for near-future applications. Physical Review X, 8(3):03 2018. arXiv 171..092209
Suguru Endo, Zhenyu Cai, Simon C. Benjamin, and Xiao Yuan. Hybrid quantum-classical algo- rithms and quantum error mitigation. Journal of the Physical Society of Japan, 90(3):032001, 2021. arXiv/2011.013
Cong Fang, Zhouchen Lin, and Tong Zhang. Sharp analysis for nonconvex SGD escaping from saddle points. In Conference on Learning Theory, pp. 1192-1234, 2019. arXiv 1902. 00247
Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. No quantum speedup over gra- dient descent for non-smooth convex optimization. In 12th Innovations in Theoretical Computer Science Conference, volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), für Informatik, 2021a. ISBN 978-3-95977-
pp. 53:1-53:20. Schloss
177-1. doi: 10.4230/LIPtcs.ITCS 20211.3...2...... arXiv/2010 01801
Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. Near-optimal lower bounds for convex optimization for all orders of smoothness. Advances in Neural Information Processing Systems, 34:29874-29884, 2021b. arXiv arXiv(2112. 01118
András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe. Optimizing quantum optimization algorithms via faster quantum gradient computation. In Proceedings of the 30th Annual ACM- SIAM Symposium on Discrete Algorithms, pp. 1425-1444. Society for Industrial and Applied Mathematics, 2019. arXiv 00465
Daniel Gottesman. Stabilizer codes and quantum error correction. California Institute of Technol- ogy, 1997.
Aram W. Harrow and Michael A. Nielsen. Robustness of quantum gates in the presence of noise. Physical Review A, 68(1):012308, 2003.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael I. Jordan. How to escape sad- dle points efficiently. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pp. 1724-1732, 2017. arXiv/1703.C033 C0887
Chi Jin, Lydia T. Liu, Rong Ge, and Michael I. Jordan. On the local minima of the empirical risk. In Advances Neural Information Processing Systems, volume 31, 201 Sa. arXiv 09357
Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In Conference on Learning Theory, pp. 1042-1085 2018h.
irXivi1711.111 10466
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M. Kakade, and Michael I Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. Journal of the ACM (JACM), 68(2):1-29, 2021. arXiv 1902. 04811
12

---

Published as a conference paper at ICLR 2025
Stephen P. Jordan. Fast quantum algorithm for numerical gradient estimation. Physical Review Letters, 95(5)0505011, 2005.
Mustafa O. Karabag, Cyrus Neary, and Ufuk Topcu. Smooth convex optimization using sub-zeroth- order oracles. Proceedings of the AAAI Conference Artificial Intelligence, 35(5):8815 3822, May 2021. doi: 10. wttp://.ai..3...11111.
Jiaqi Leng, Ethan Hickman, Joseph Li, and Xiaodi Wu. Quantum Hamiltonian descent, 2023. arXiv/233.0110
Tongyang Li and Ruizhe Zhang. Quantum speedups of optimizing approximately convex functions with applications to logarithmic regret stochastic convex bandits. In Advances in Neural Informa- tion Processing Systems, 2022, arXiv 2209. 12897
Mingrui Liu, Zhe Li, Xiaoyu Wang, Jinfeng Yi, and Tianbao Yang. Adaptive negative curvature de- scent with applications in non-convex optimization. Advances in Neural Information Processing Systems, 31:4853-4483 2018.
Yizhou Liu, Weijie Su, and Tongyang Li. On quantum speedups for nonconvex optimization via quantum tunneling walks. Quantum, 7:1030, 2023, arXiv
Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. A rigorous and robust quan- tur speed-up in supervised machine learning. Nature Physics, 1709:1013-1017, 2021.
2tiiv2211002222.
Sirui Lu, Lu-Ming Duan, and Dong-Ling Deng. Quantum adversarial machine learning. Physical Review Research, 2(3)103321,, 2020. arXiv/2001. 00030
Yurii Nesterov and Boris T. Polyak. Cubic regularization of Newton method and its global perfor- mance. Mathematical Programming, 108(1):177-205 2006.
John Preskill. Quantum computing in the NISQ and beyond. Quantum, 2:79, 2018. ISSN 2521-327X. Sttl:18801.00863
Eric M. Rains. Monotonicity of the quantum linear programming bound. IEEE Transactions on Information Theory, -5(7):2489-2499 1999.
Andrej Risteski and Yuanzhi Li. Algorithms and matching lower bounds for approximately-convex optimization. In Advances in Neural Information Processing Systems, volume 29, 2016.
Abhishek Roy, Krishnakumar Balasubramanian, Saeed Ghadimi, and Prasant Mohapatra. Escaping saddle-point faster under interpolation-like conditions. Advances in Neural Information Process- ing Systems, 33:12414- 12425, 2020.
Aaron Sidford and Chenyi Zhang. Quantum speedups for stochastic optimization. In Thirty-sevnnth Conference on Neural Information Processing Systems, 2023. arXiv 2308 01582
Yaron Singer and Jan Vondrák. erroneous oracles. In Advances in Neural Information Processing Systems, volume 28, 2015.
cntrmattion-thorettie lower bounds for convex optimization with
Ruoyu Sun. Optimization for deep learning: theory and algorithms, 2019. arXiv 91 2 08957
Nilesh Tripuraneni, Mitchell Stem, Chi Jin, Jeffrey Regier, and Michael I. Jordan. Stochastic cubic regularization for fast nonconvex optimization. Advances Neural Information Processing Systems, pp. 2899-2908, 2018. arXiv/1711.0288
Joran van Apeldoor and András Gilyén. Improvements in quantum sdp-solving with applications. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). fuer Informatik, 2019. arXiv 05058
Schloss Crrsstuhl-Lebbii-Zeeen
Joran van Apeldoom, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimization using quantum oracles. Quantum, 4:220, 2020a. arXiv 00643
Joran van Apeldoor, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-solvers: Better upper and lower bounds. Quantum, 4:230, 2020b. arXiv: ( 705. 01 01843
13

---

Published as a conference paper at ICLR 2025
Vladimir Vapnik. Principles of risk minimization for learning theory. In Advances in Neural Infor- mation Processing Systems, volume 4, 1991.
Yi Xu, Rong Jin, and Tianbao Yang. NEON+: Accelerated gradient methods for extracting negative curvature for non-convex optimization, 2017, arXiv 1712. 01033
Yi Xu, Rong Jin, and Tianbao Yang- First-order stochastic algorithms for escaping from saddle points in almost linear time. In Advances in Neural Information Processing Systems, pp- 5530- 5540, 2018. arXiv 1711. 01944
Mark Zhandry. note on the quantum collision and set equality problems. Quantum Information & Computation, 15(7-8):557-56) 2015. arXiv 1027
Mark Zhandry. How construct quantum random functions. Journal of the ACM (JACM), 68(5):
2021.
Chenyi Zhang and Tongyang Li. Escape saddle points by simple gradient-descent based algorithm. Advances in Neural Information Processing Systems, 34:8545-8556 2021. arXiv:2111 14069
Chenyi Zhang and Tongyang Li. Quantum lower bounds for finding stationary points nonconvex functions. In International Conference Machine Learning, pp. 41268 41299. PMLR, 2023. Stiiv22222.09000
Chenyi Zhang, Jiaqi Leng, and Tongyang Li. Quantum algorithms for escaping from saddle points. Quantum, 5:529, 2021. 2rXiv 10253
Hualin Zhang and Bin Gu. Faster gradient-fre free methods for escaping saddle points. The Eleventh International Conference on Learning Representations, 2022.
Hualin Zhang, Huan Xiong, and Bin Gu. Zeroth-order negative curvature finding: Escaping saddle points without gradients. Advances in Neural Information Processing Systems, 35:38332-38344, 2022. arXiv 01696
Yuchen Zhang, Percy Liang, and Moses Charikar. A hitting time analysis of stochastic gradient Langevin dynamics. arXivi1702. 055775
In Conference on Learning Theory, pp. 1980-2022, 2017.
14


Reviews:
[{"review_id": "7XRwWaqd29", "reviewer": "Reviewer_pk5B", "summary": "This paper investigates the robustness of quantum algorithms for non-convex optimization, in the context of finding an $\\epsilon$-approximate second-order stationary point ($\\epsilon$-SOSP) in a d-dimensional non-convex function. As is usually done in optimization literature, the algorithm has access to the function via noisy zeroth or first-order oracles that satisfy certain standard assumptions. \n\nThe paper provides several foundational results for this setup in both upper and lower bounds. The upper bounds, under zeroth and first-order oracles, respectively, are nicely summarized in Table 1 and Table 2 under different noise regimes. Notably, under the zeroth order assumption and low noise regimes, the algorithms achieve exponential speed-ups. Additionally, they establish lower bounds for classical and quantum algorithms, summarized in Tables 1, 2, and 3, under various noise regimes and Zeroth and First order Assumptions.", "questions": "1. In the regime of Table 2 and Theorem 2.5 under the first-order assumption, are there known classical lower bounds?\n2. What are the key algorithmic insights for results that achieve exponential speed-ups? \n3. In the final version, I will encourage the author to expand on open questions more systematically. In general, there are several open gaps to establish minimax optimal query complexities for the problem.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper provides a comprehensive analysis of upper and lower bounds on query complexities of quantum algorithms for an important problem in non-convex optimization, and thus, the contributions are important to the community. The paper is well-written.", "weaknesses": "No major weaknesses. See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EEoSyCfmlc", "reviewer": "Reviewer_kwBc", "summary": "The work studies the task of finding $\\epsilon$-approximate second-order stationary points of $d$-dimensional non-convex functions with zeroth- or first-order noisy quantum oracles. Under various different noise regimes (as functions of $\\epsilon$ and $d$), the work presents upper and lower bounds for the classical and the quantum query complexities of the task. \nWith zeroth order oracle, it has been shown that the quantum algorithm proposed gives an exponential speedup (against classic lower bound) when the noise is at a small scale of $\\tilde O( \\epsilon^6 / d^4 )$, and a polynomial speedup (compared to the state-of-the-art classical algorithm) when the noise is of scale $[ \\tilde \\Omega(\\epsilon^6 / d^4), O(\\epsilon^{1.5} / d) ] $.\nWith first-order oracle, there is a polynomial quantum speedup (compared to the state-of-the-art classical algorithm) when the noise is of scale $\\Theta(\\epsilon / d^{0.5})$.", "questions": "1. Can you give a more descriptive title to Section 4.3 like the surrounding sections?\n2. Table 3 is for lower bounds in $\\epsilon$. But the zeroth-order lower bound for deterministic classical algorithm entry is still an expression in $d$.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The paper provides a comprehensive set of results that cover a wide range of noise scale regimes, and oracle assumptions. The comparison with the classical results are meaningful and well presented.", "weaknesses": "The quantum query complexity bounds established are far from being tight.\nMost of the algorithms are almost identical to the classical version with the gradient estimation replaced by Jordan’s algorithm. The analysis also looks like a rehash of the classical proofs by substituting the guarantees from Jordan’s algorithm. The lower bound constructions seem to be just borrowed from Jin et al., 2018a and Carmon et al., 2021 (up to a unitary rotation and a scaling factor).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "okHMZI38NH", "reviewer": "Reviewer_W1b5", "summary": "This paper studies how to apply quantum algorithms for finding the $\\epsilon$-approximate second-order stationary point ($\\epsilon$-SOSP) of a $d$-dimensional non-convex function, given noisy zeroth- (i.e., noisy evaluation query) or first-order(i.e., noisy gradient query) oracles as inputs. The study focuses on settings where only noisy zeroth-order (evaluation queries) or noisy first-order (gradient queries) oracles are accessible. Specifically, the authors analyze scenarios under various levels of noise, parameterized by poly $(\\epsilon, 1/d)$,  and demonstrate that their approach significantly outperforms state-of-the-art (SoTA) methods regarding query complexity. Furthermore, they establish several lower bounds for alternative scenarios where efficient query complexity is not achievable with the current methods. Tables 1, 2 and 3 concisely summarize the main results, offering a comparative view of query complexity improvements relative to existing methods.", "questions": "- It appears that $\\nabla f(x+z) - \\nabla f(x)$ is intended as an estimate of the Hessian rather than the gradient, as indicated in line 312?\n\n-The most recent work that this paper compares against in Table 1 is from 2018. Are there been any more recent results in this direction?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "- Applying quantum oracles to speedup existing results is a timely and meaningful interesting problem.\n- This work gives a dense collection of results.\n- The summarization of the results in Tables 1, 2 and 3 is informative and clear.", "weaknesses": "- The presentation of technical results in this paper feels somewhat vague; for instance, there is no pseudocode or intuitive explanation of the underlying algorithms. This lack of detail impacts the paper's clarity and readability.\n\n- The current presentation makes it challenging to assess the paper's novelty. For instance, when referencing Jordan's algorithm, the paper points to [2] for details on Jordan's gradient estimation (line 223) and states that it \"replaces the gradient queries in PAGD with this oracle\" (line 232). However, there is insufficient discussion on the complexity of replacing the oracle, which obscures an evaluation of the paper's originality.\n\n- There are no related discussions on when the noise levels are practical, for example, what problem setting would generate a noise level of $\\tilde{\\Omega} (\\epsilon^{1.5} / d)$? \n\n- The definition of $\\epsilon$-SOSP doesn't align with the one in [1]. Instead of letting $\\|F(x)\\| \\leq \\epsilon$, the saddle point should satisfy $\\|\\nabla F(x)\\| \\leq \\epsilon$?\n\n\n- Several notations are used for the same purpose in this work, for example, [line 119-130], $\\||$ , | |, and | are used to denote similar norms. The reviewer would recommend using one notation to denote all the norms.\n\nMinor Comments:\n- Some $O(\\cdot)$ sign probably should be $\\Theta(\\cdot)$ in the column \"noise strength\" in Table 1?\n\n[1] Jin, C., Ge, R., Netrapalli, P., Kakade, S. M., & Jordan, M. I. (2017, July). How to escape saddle points efficiently. In International conference on machine learning (pp. 1724-1732). PMLR.\n\n[2]Chakrabarti, S., Childs, A. M., Li, T., & Wu, X. (2020). Quantum algorithms and lower bounds for convex optimization. Quantum, 4, 221.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)