Pith. sign in

REVIEW 3 major objections 4 minor 67 references

By exploiting coherent access to samples, quantum computers can estimate heavy-tailed means and train stochastic models with strictly fewer oracle queries than any classical method, when the effective dimension is small.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 02:16 UTC pith:ATLVG4AA

load-bearing objection Genuinely new quantum mean estimators for heavy-tailed vectors and a solid lower-bound framework, but the flagship nonconvex theorem's expectation claim needs a fix. the 3 major comments →

arxiv 2607.25492 v2 pith:ATLVG4AA submitted 2026-07-28 cs.LG

Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise

Bin Luo , Chengchang Liu , Jonathan Allcock , Shengyu Zhang , John C.S. Lui This is my paper
classification cs.LG
keywords quantum mean estimationheavy-tailed noisestochastic optimizationquantum query complexitynonconvex optimizationmultilevel Monte Carlolow-dimensional regime
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Stochastic gradients in modern machine learning often have only a finite p-th moment, with tail index p between 1 and 2, so variance may be infinite. The paper shows that a quantum computer with coherent access to samples can estimate the mean of such heavy-tailed random vectors in roughly sqrt(d) times (sigma/epsilon)^(p/(2(p-1))) queries, instead of the classical (sigma/epsilon)^(p/(p-1)) rate, by centering, truncating, and then using a bounded-variance quantum estimator. It also builds an unbiased version and proves lower bounds showing the dependence on sigma and epsilon is optimal up to log factors when dimension is constant, with a new dimension dependence for p > 4/3. Plugging these estimators into normalized and projected SGD yields quantum query speedups over classical lower bounds for nonconvex and convex stochastic optimization in low-dimensional regimes.

Core claim

The paper's central claim is that the quantum sampling oracle changes the complexity of heavy-tailed mean estimation: a d-dimensional random vector with E||X-E[X]||^p <= sigma^p can have its mean estimated to accuracy epsilon with O~(sqrt(d) (sigma/epsilon)^(p/(2(p-1)))) queries, versus the classical Theta~((sigma/epsilon)^(p/(p-1))) rate. The construction centers the variable with a classical median-of-means estimate, truncates at radius B=(3*2^p sigma^p / epsilon)^(1/(p-1)) so that bias is bounded by epsilon/3, and then hands the truncated variable to a bounded-variance quantum mean estimator; debiasing is achieved by a generalized multilevel Monte Carlo wrapper. The paper further proves q

What carries the argument

QHTME's center-truncate-estimate loop is the load-bearing object. A classical rough center keeps the truncation decision aligned with the unknown mean; the truncation radius B is chosen so that deleting samples with ||Y||>B costs at most epsilon/3 of bias while leaving a trace-covariance bound L=2^p sigma^p B^(2-p) that the bounded-variance quantum estimator can exploit. QUHTME removes bias by drawing a geometric number of accuracy levels and combining three QHTME+ calls, a multilevel Monte Carlo identity that preserves the query rate. On the lower-bound side, the hard-instance primitive Recovery∘Search—a bit-string recovery problem superimposed on a rare-spike search—yields the dimension-de

Load-bearing premise

The entire speedup rests on the assumption that the bounded-variance quantum mean estimator used inside QHTME keeps its guarantees under an oracle that gives coherent access to sampled values but not to the random seed; the paper argues for this transfer but gives no circuit-level proof, and if it fails the quantum rates fall back to the classical ones.

What would settle it

Set d=1, p=3/2, sigma=1, and use the distribution P(X=3*epsilon^(-2))=epsilon^3, P(X=0)=1-epsilon^3, so E|X-E X|^(3/2)=Theta(1). Simulate QHTME under the paper's quantum sampling oracle and measure coherent queries as epsilon shrinks. The claimed rate is about epsilon^(-3/2); observing the classical epsilon^(-3) rate would refute the central speedup.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • For nonconvex objectives satisfying smoothness and a lower bound, QNSGD produces an iterate whose average gradient norm is at most epsilon with high probability, using O~(sqrt(d) epsilon^(-(5p-4)/(2p-2))) queries; when d is at most about epsilon^(-p/(p-1)), this beats the classical lower bound Omega(epsilon^(-(3p-2)/(p-1))).
  • For convex objectives, QPSGD reaches expected epsilon-suboptimality in O~(sqrt(d) epsilon^(-(3p-2)/(2(p-1))) + epsilon^(-2)) expected queries, beating the classical Omega(epsilon^(-p/(p-1))) bound for p in (1,2) when d is at most about epsilon^(-(2-p)/(p-1)).
  • The underlying QHTME and QUHTME estimators achieve O~(sqrt(d) (sigma/epsilon)^(p/(2(p-1)))) queries for both biased and unbiased mean estimation, giving a quadratic improvement over the classical exponent p/(p-1) in the low-dimensional regime.
  • The lower bounds establish that the sigma, epsilon dependence is optimal up to log factors when d is constant, and that for p > 4/3 a dimension-dependent factor is unavoidable, with matching dimension dependence in the p = 2 case.
  • The p = 2 case recovers the earlier quantum nonconvex complexity O~(sqrt(d) epsilon^(-3)), so the framework contains the bounded-variance setting as a special case.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This inference is not in the paper: if a fault-tolerant quantum device could implement the quantum sampling oracle for heavy-tailed gradients arising in parameter-sparse quantum models, QHTME would offer an immediate query-count advantage in regimes where vanishing gradients already push toward sparse architectures.
  • This inference is not in the paper: the claimed speedups are sensitive to how the bounded-variance quantum estimator is compiled on the weaker oracle; a circuit-level counterexample or a missing coherent-access primitive would reduce the rates to classical, so a natural next step is to exhibit explicit circuits or a no-go argument.
  • This inference is not in the paper: the dimension-dependent lower bound suggests that in high dimensions the advantage disappears, so practical speedups may require combining QHTME with sketching or coordinate-subspace methods that reduce effective dimension before applying the estimator.
  • This inference is not in the paper: the estimator could be benchmarked on synthetic heavy-tailed distributions, such as a rare large-spike mixture, as a standalone primitive before it is embedded in a full optimizer.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies stochastic optimization when gradient noise is heavy-tailed, modeled by a bounded p-th central moment for p∈(1,2]. It proposes QHTME, a quantum heavy-tailed mean estimator that combines classical centering, truncation, and the bounded-variance quantum estimator of [13], and claims query complexity O~(√d (σ/ε)^{p/(2(p−1))}). It then constructs an unbiased variant QUHTME via a generalized multilevel Monte Carlo scheme. Lower bounds are proved using an unstructured-search reduction and a new Recovery∘Search primitive, yielding dimension-dependent bounds for p∈(4/3,2]. The estimators are applied to nonconvex optimization via QNSGD, giving high-probability stationary-point guarantees, and to convex optimization via QPSGD, giving expected suboptimality guarantees. The paper claims speedups over classical lower bounds in low-dimensional regimes.

Significance. If the oracle-model transfer and the expectation conversion are repaired, this is a substantial contribution. Extending quantum mean estimation from bounded variance to bounded p-th moments is a natural and nontrivial step, and the Recovery∘Search lower-bound construction is an original technical tool that goes beyond a routine Grover reduction. The paper is transparent about the remaining gaps between upper and lower bounds, and the detailed appendices make most of the technical claims checkable. The optimization results are conditional on the two gaps identified below, but the mean-estimation core and the lower-bound framework appear sound and valuable in their own right.

major comments (3)
  1. [Theorem 4.4 / Section D.1] The formal nonconvex claim is stated in Definition 4.1 as E[∥∇f(x̂)∥]≤ε, and the abstract and Table 3 depend on this. The proof, however, establishes only that with probability at least 1−δ, (1/T)Σ_{t=0}^{T−1}∥∇f(x_t)∥≤ε. The 'Consequently' claim that E[∥∇f(x̂)∥]≤ε does not follow: Assumptions 1.1 and 4.2 impose no bound on ∥∇f∥ on the failure event, and the failure probability δ is never traded against a gradient bound. This is patchable by either stating the result as a high-probability guarantee or adding a bounded-gradient/truncation argument and choosing δ accordingly, but as written the central nonconvex contribution is not supported.
  2. [Appendix A.1 / Lemma 3.3] The upper bounds for QHTME and QUHTME rely on Lemma 3.3, quoted from [13], whose oracle model uses coherent access to the random seed ω via separate probability and binary oracles (Definitions A.1–A.2). The paper's Definition 2.2 is strictly weaker. The statement in Appendix A.1 that QEstimator 'only relies on coherent access to the values' is asserted informally, with no circuit-level proof that the algorithm of [13] can be implemented with one query to the weaker oracle per query of Definition 2.2. If this transfer fails, the QHTME/QUHTME query bounds, and consequently Theorems 4.4 and 5.3, collapse to the classical rates. This is load-bearing and needs a proof or a re-statement of the upper bounds under the stronger oracle model.
  3. [Algorithm 2 / Appendix C.4] The unbiasedness proof for QUHTME replaces the geometric random variable J by an infinite telescoping sum and uses E[μ_j]→μ as j→∞. Since QHTME+ is not unbiased, this interchange must be justified explicitly. The p-th moment bounds in Lemma C.9 should imply the needed integrability and convergence, but the proof does not state or prove the dominated-convergence step. This is a short fix, but unbiasedness is the property that makes QPSGD valid, so it should be made rigorous.
minor comments (4)
  1. [Definition 4.1] There is a typographical error in the displayed definition: 'E[∥∇f(ˆx)]∥≤ϵ' should be 'E[∥∇f(ˆx)∥]≤ϵ'.
  2. [Algorithm 2] Line 3 samples j∼Geom(1/2)∈N, but line 5 uses μ_{j−1}; if the geometric distribution is supported on {0,1,2,...}, this is undefined with probability 1/2. The algorithm should specify that j is supported on positive integers, matching the proof in Appendix C.4.
  3. [Appendix C.4] In the proof of Lemma C.8, the law-of-total-expectation display uses Pr(S) twice; the second occurrence should be Pr(¬S) or the complement should be denoted explicitly. The current notation is confusing.
  4. [Abstract and Table captions] Several displayed exponents lose their braces in the arXiv rendering, e.g. 'ε^{− 5p−4/2p−2}' should read 'ε^{−(5p−4)/(2p−2)}'. The captions of Tables 1 and 2 would also benefit from a statement that lower bounds are for the quantum sampling oracle of Definition 2.2.

Circularity Check

0 steps flagged

No circular derivation: estimators and lower bounds are derived from stated moment conditions and external primitives; Theorem 4.4 has a non-circular proof gap.

full rationale

I walked the derivation chain. QHTME (Theorem 3.4) centers with CHTME (Theorem 2.5), truncates, and calls QEstimator from [13]; its proof (Appendix C.2) bounds truncation bias and trace covariance from the p-th moment assumption, with no fitted parameter. QUHTME (Theorem 3.7) is built from QHTME+ and an MLMC telescope; the proof follows [49] but with a new Lemma C.8 and p-th moment bounds. The lower bounds (Theorems 3.9 and 3.10) reduce to unstructured search, Recovery∘Search, and the independent [13] bounded-variance lower bound; they are not obtained from the upper bounds. QNSGD and QPSGD combine the estimator bounds with standard descent lemmas (Lemma 4.3 from [14]; Lemma 5.2 following [37]); the ε-dependence is algebraic. No fitted parameter is renamed as a prediction, and no assumption includes the target result. The only self-citations ([35], [36]) appear in Appendix B as examples of related quantum-algorithm work and are not load-bearing. I therefore find no circularity. Two non-circular concerns are flagged. First, Appendix A.1 asserts, without a circuit-level proof, that [13]'s QEstimator works under the paper's weaker quantum sampling oracle: 'this difference does not affect the upper bound in Lemma 3.3. In particular, the algorithm QEstimator in [13] only relies on coherent access to the values of the random variable, rather than the underlying random seed.' This is load-bearing but is a transfer/assumption, not circularity. Second, Theorem 4.4 proves only a high-probability bound, '(1/T)Σ∥∇f(x_t)∥≤ϵ', and then states 'Consequently, QNSGD takes ... queries ... such that E[∥∇f(x̂)∥]≤ϵ' without controlling the failure event; the expectation guarantee does not follow from the proof. This is a correctness gap, not circularity. Neither issue makes the derivation equivalent to its inputs, so the circularity score remains low.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 0 invented entities

No numbers are fitted to data; the only new construction is the Recovery∘Search lower-bound primitive, which is a proof gadget rather than an invented physical entity. All other assumptions are either standard mathematical results or explicitly stated domain assumptions of the optimization/oracle models.

axioms (6)
  • domain assumption Assumption 1.1: E∥∇F(x;ξ)−∇f(x)∥^p ≤ σ^p for p∈(1,2]
    Defines the heavy-tailed noise model; all complexity expressions depend on σ and p as given constants.
  • domain assumption Quantum sampling oracle (Definition 2.2) and quantum stochastic gradient oracle (Definition 2.4)
    Upper bounds count coherent oracle queries; the paper interprets unbounded heavy-tailed distributions through finite-precision truncation/discretization.
  • standard math Lemma 3.3: bounded-variance quantum estimator QEstimator of [13]
    Used as a black box for the truncated bounded-variance variable; the paper argues its compatibility with Definition 2.2 informally in Appendix A.1.
  • standard math Vector-valued von Bahr–Esseen inequality (Lemma C.2)
    Controls p-th moments of block means in the classical heavy-tailed mean estimator.
  • standard math Grover search lower bound and quantum adversary method [2,5,47]
    Basis for the dimension-independent and Recovery∘Search lower bounds.
  • domain assumption Assumptions 4.2 and 5.1: L-smooth lower-bounded f; convex f with bounded constraint set and bounded gradient
    Standard optimization assumptions used in the QNSGD and QPSGD convergence lemmas.

pith-pipeline@v1.3.0-alltime-deepseek · 40701 in / 21116 out tokens · 199811 ms · 2026-08-01T02:16:05.976315+00:00 · methodology

0 comments
read the original abstract

We study stochastic optimization with heavy-tailed gradient noise. We first propose a novel quantum mean estimator for multivariate heavy-tailed random variables that achieves lower query complexity than optimal classical estimators in the low-dimensional regime. We further develop an unbiased quantum mean estimator by applying a generalized multi-level Monte Carlo technique. We prove quantum lower bounds showing that, when the dimension $d$ of the random vector is small and can be viewed as a constant, our quantum estimators are optimal up to logarithmic factors. We further derive stronger dimension-dependent lower bounds for tail index $p>4/3$, showing that a nontrivial dependence on the dimension is unavoidable in the low-dimensional regime. Based on these estimators, we propose a quantum normalized stochastic gradient descent method ($\texttt{QNSGD}$), which finds an $\epsilon$-stationary point using $\tilde{\mathcal{O}}\big(\sqrt d\,\epsilon^{-\frac{5p-4}{2p-2}}\big)$ queries to the quantum stochastic gradient oracle. For a convex objective function, we propose a quantum projected stochastic gradient descent method ($\texttt{QPSGD}$), which computes a solution with $\epsilon$-optimal solution using $\tilde{\mathcal{O}}\big(\sqrt d\,\epsilon^{-\frac{3p-2}{2p-2}}+\epsilon^{-2}\big)$ queries in expectation. These sharper bounds improve upon the classical lower bounds $\Omega\big(\epsilon^{-\frac{3p-2}{p-1}}\big)$ for nonconvex problems and $\Omega\big(\epsilon^{-\frac{p}{p-1}}\big)$ for convex problems in the low-dimensional regimes $d\lesssim\epsilon^{-\frac{p}{p-1}}$ and $d\lesssim\epsilon^{-\frac{2-p}{p-1}}$, respectively.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

67 extracted references · 2 canonical work pages

  1. [1]

    Linear attention is (maybe) all you need (to understand transformer optimization)

    Kwangjun Ahn, Xiang Cheng, Minhak Song, Chulhee Yun, Ali Jadbabaie, and Suvrit Sra. Linear attention is (maybe) all you need (to understand transformer optimization). InThe Twelfth International Conference on Learning Representations, 2024

    2024

  2. [2]

    Quantum lower bounds by quantum arguments

    Andris Ambainis. Quantum lower bounds by quantum arguments. InProceedings of the thirty-second annual ACM symposium on Theory of computing, pages 636–643, 2000

    2000

  3. [3]

    Fast convex optimization with quantum gradient methods.arXiv preprint arXiv:2503.17356, 2025

    Brandon Augustino, Dylan Herman, Enrico Fontana, Junhyung Lyle Kim, Jacob Watkins, Shouvanik Chakrabarti, and Marco Pistoia. Fast convex optimization with quantum gradient methods.arXiv preprint arXiv:2503.17356, 2025

    Pith/arXiv arXiv 2025

  4. [4]

    Bennett and John Gill

    Charles H. Bennett and John Gill. Relative to a random oracle a,pa̸= npa̸= co-npa with probability 1.SIAM Journal on Computing, 10(1):96–113, 1981. doi: 10.1137/0210008

    work page doi:10.1137/0210008 1981

  5. [5]

    Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani

    Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing.SIAM Journal on Computing, 26(5):1510–1523, October 1997. ISSN 1095-7111. doi: 10.1137/s0097539796300933. URL http://dx.doi.org/10.1137/S0097539796300933

    doi:10.1137/s0097539796300933 1997

  6. [6]

    Quadratic speed-up in infinite variance quantum monte carlo, 2024

    Jose Blanchet, Mario Szegedy, and Guanyang Wang. Quadratic speed-up in infinite variance quantum monte carlo, 2024. URL https://arxiv.org/abs/2401.07497

    Pith/arXiv arXiv 2024

  7. [7]

    Quantum amplitude amplification and estimation

    Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. InQuantum Computation and Information, volume 305 ofContemporary Mathematics, pages 53–74. American Mathematical Society, 2002. doi: 10.1090/conm/305/05215

    doi:10.1090/conm/305/05215 2002

  8. [8]

    Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C

    M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles. Variational quantum algorithms.Nature Reviews Physics, 3(9):625–644, August 2021. ISSN 2522-5820. doi: 10.1038/s42254-021-00348-9. URL http://dx.doi.org/10.1038/s42254-021-00348-9. 11

    doi:10.1038/s42254-021-00348-9 2021

  9. [9]

    Quantum algorithms and lower bounds for convex optimization.Quantum, 4:221, 2020

    Shouvanik Chakrabarti, Andrew M Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization.Quantum, 4:221, 2020

    2020

  10. [10]

    A first-order primal-dual algorithm for convex problems with applications to imaging.Journal of mathematical imaging and vision, 40(1):120–145, 2011

    Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging.Journal of mathematical imaging and vision, 40(1):120–145, 2011

    2011

  11. [11]

    Quantum convolutional neural networks.Nature Physics, 15(12):1273–1278, 2019

    Iris Cong, Soonwon Choi, and Mikhail D Lukin. Quantum convolutional neural networks.Nature Physics, 15(12):1273–1278, 2019

    2019

  12. [12]

    Society for Industrial and Applied Mathematics, January 2023

    Arjan Cornelissen and Yassine Hamoudi.A Sublinear-Time Quantum Algorithm for Approximating Partition Functions, page 1245–1264. Society for Industrial and Applied Mathematics, January 2023. ISBN 9781611977554

    2023

  13. [13]

    Near-optimal quantum algorithms for multivariate mean estimation

    Arjan Cornelissen, Yassine Hamoudi, and Sofiene Jerbi. Near-optimal quantum algorithms for multivariate mean estimation. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC ’22, page 33–43. ACM, June 2022

    2022

  14. [14]

    Momentum improves normalized sgd

    Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. InInternational conference on machine learning, pages 2260–2268. PMLR, 2020

    2020

  15. [15]

    High-probability bounds for non-convex stochastic optimization with heavy tails.Advances in Neural Information Processing Systems, 34:4883–4895, 2021

    Ashok Cutkosky and Harsh Mehta. High-probability bounds for non-convex stochastic optimization with heavy tails.Advances in Neural Information Processing Systems, 34:4883–4895, 2021

    2021

  16. [16]

    Optimal stochastic non-smooth non-convex optimization through online-to-non-convex conversion

    Ashok Cutkosky, Harsh Mehta, and Francesco Orabona. Optimal stochastic non-smooth non-convex optimization through online-to-non-convex conversion. InInternational Conference on Machine Learning, pages 6643–6670. PMLR, 2023

    2023

  17. [17]

    Quantum computing: Lecture notes, 2023

    Ronald de Wolf. Quantum computing: Lecture notes, 2023. URL https://arxiv.org/abs/1907.09415

    Pith/arXiv arXiv 2023

  18. [18]

    Spider: Near-optimal non-convex opti- mization via stochastic path-integrated differential estimator.Advances in neural information processing systems, 31, 2018

    Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex opti- mization via stochastic path-integrated differential estimator.Advances in neural information processing systems, 31, 2018

    2018

  19. [19]

    Can sgd handle heavy-tailed noise?arXiv preprint arXiv:2508.04860, 2025

    Ilyas Fatkhullin, Florian Hübler, and Guanghui Lan. Can sgd handle heavy-tailed noise?arXiv preprint arXiv:2508.04860, 2025

    Pith/arXiv arXiv 2025

  20. [20]

    Logarithmic-regret quantum learning algorithms for zero-sum games.Advances in Neural Information Processing Systems, 36:31177–31203, 2023

    Minbo Gao, Zhengfeng Ji, Tongyang Li, and Qisheng Wang. Logarithmic-regret quantum learning algorithms for zero-sum games.Advances in Neural Information Processing Systems, 36:31177–31203, 2023

    2023

  21. [21]

    Zico Kolter, Zachary C

    Saurabh Garg, Joshua Zhanson, Emilio Parisotto, Adarsh Prasad, J. Zico Kolter, Zachary C. Lip- ton, Sivaraman Balakrishnan, Ruslan Salakhutdinov, and Pradeep Ravikumar. On proximal policy optimization’s heavy-tailed gradients, 2021. URL https://arxiv.org/abs/2102.10264

    Pith/arXiv arXiv 2021

  22. [22]

    On proximal policy optimization’s heavy- tailed gradients

    Saurabh Garg, Joshua Zhanson, Emilio Parisotto, Adarsh Prasad, Zico Kolter, Zachary Lipton, Sivaraman Balakrishnan, Ruslan Salakhutdinov, and Pradeep Ravikumar. On proximal policy optimization’s heavy- tailed gradients. InInternational Conference on Machine Learning, pages 3610–3619. PMLR, 2021

    2021

  23. [23]

    Stochastic first-and zeroth-order methods for nonconvex stochastic programming.SIAM journal on optimization, 23(4):2341–2368, 2013

    Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming.SIAM journal on optimization, 23(4):2341–2368, 2013

    2013

  24. [24]

    Multilevel monte carlo methods.Acta numerica, 24:259–328, 2015

    Michael B Giles. Multilevel monte carlo methods.Acta numerica, 24:259–328, 2015

    2015

  25. [25]

    Robustness of quantum algorithms for nonconvex optimization

    Weiyuan Gong, Chenyi Zhang, and Tongyang Li. Robustness of quantum algorithms for nonconvex optimization. InThe Thirteenth International Conference on Learning Representations, 2025

    2025

  26. [26]

    Gower and Peter Richtárik

    Robert M. Gower and Peter Richtárik. Randomized iterative methods for linear systems.SIAM Journal on Matrix Analysis and Applications, 36(4):1660–1690, January 2015. ISSN 1095-7162. doi: 10.1137/15m1025487. URL http://dx.doi.org/10.1137/15M1025487. 12

    doi:10.1137/15m1025487 2015

  27. [27]

    Quanvolutional neural networks: powering image recognition with quantum circuits.Quantum Machine Intelligence, 2(1):2, 2020

    Maxwell Henderson, Samriddhi Shakya, Shashindra Pradhan, and Tristan Cook. Quanvolutional neural networks: powering image recognition with quantum circuits.Quantum Machine Intelligence, 2(1):2, 2020

    2020

  28. [28]

    Jiayi Huang, Han Zhong, Liwei Wang, and Lin F. Yang. Tackling heavy-tailed rewards in reinforcement learning with function approximation: Minimax optimal and instance-dependent regret bounds, 2024. URL https://arxiv.org/abs/2306.06836

    Pith/arXiv arXiv 2024

  29. [29]

    From gradient clipping to normalization for heavy tailed sgd.arXiv preprint arXiv:2410.13849, 2024

    Florian Hübler, Ilyas Fatkhullin, and Niao He. From gradient clipping to normalization for heavy tailed sgd.arXiv preprint arXiv:2410.13849, 2024

    Pith/arXiv arXiv 2024

  30. [30]

    Tak Hur, Leeseok Kim, and Daniel K. Park. Quantum convolutional neural network for classical data classification.Quantum Machine Intelligence, 4(1), February 2022. ISSN 2524-4914. doi: 10.1007/ s42484-021-00061-x. URL http://dx.doi.org/10.1007/s42484-021-00061-x

    doi:10.1007/s42484-021-00061-x 2022

  31. [31]

    Fast zeroth-order convex optimization with quantum gradient methods

    Junhyung Lyle Kim, Brandon Augustino, Dylan Herman, Enrico Fontana, Jacob Watkins, Marco Pistoia, and Shouvanik Chakrabarti. Fast zeroth-order convex optimization with quantum gradient methods. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025

    2025

  32. [32]

    Quantum adversary (upper) bound.Chicago Journal of Theoretical Computer Science, 19(1):1–14, 2013

    Shelby Kimmel. Quantum adversary (upper) bound.Chicago Journal of Theoretical Computer Science, 19(1):1–14, 2013. ISSN 1073-0486. doi: 10.4086/cjtcs.2013.004. URL http://dx.doi.org/10.4086/cjtcs. 2013.004

    doi:10.4086/cjtcs.2013.004 2013

  33. [33]

    Quantum hamiltonian descent for non-smooth optimization.arXiv preprint arXiv:2503.15878, 2025

    Jiaqi Leng, Yufan Zheng, Zhiyuan Jia, Lei Fan, Chaoyue Zhao, Yuxiang Peng, and Xiaodi Wu. Quantum hamiltonian descent for non-smooth optimization.arXiv preprint arXiv:2503.15878, 2025

    Pith/arXiv arXiv 2025

  34. [34]

    Sublinear classical and quantum algorithms for general matrix games.Proceedings of the AAAI Conference on Artificial Intelligence, 35 (10):8465–8473, 2021

    Tongyang Li, Chunhao Wang, Shouvanik Chakrabarti, and Xiaodi Wu. Sublinear classical and quantum algorithms for general matrix games.Proceedings of the AAAI Conference on Artificial Intelligence, 35 (10):8465–8473, 2021. doi: 10.1609/aaai.v35i10.17028

    work page doi:10.1609/aaai.v35i10.17028 2021

  35. [35]

    Quantum algorithms for non-smooth non-convex optimization.Advances in Neural Information Processing Systems, 37:35288–35312, 2024

    Chengchang Liu, Chaowen Guan, Jianhao He, and John Lui. Quantum algorithms for non-smooth non-convex optimization.Advances in Neural Information Processing Systems, 37:35288–35312, 2024

    2024

  36. [36]

    Quantum speedups for minimax optimization and beyond

    Chengchang Liu, Zongqi Wan, Jialin Zhang, Xiaoming Sun, and John CS Lui. Quantum speedups for minimax optimization and beyond. InThe Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025

    2025

  37. [37]

    Online convex optimization with heavy tails: Old algorithms, new regrets, and applications

    Zijian Liu. Online convex optimization with heavy tails: Old algorithms, new regrets, and applications. arXiv preprint arXiv:2508.07473, 2025

    arXiv 2025

  38. [38]

    Mean estimation and regression under heavy-tailed distributions–a survey, 2019

    Gabor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed distributions–a survey, 2019. URL https://arxiv.org/abs/1906.04280

    Pith/arXiv arXiv 2019

  39. [39]

    The ziggurat method for generating random variables.Journal of statistical software, 5:1–7, 2000

    George Marsaglia and Wai Wan Tsang. The ziggurat method for generating random variables.Journal of statistical software, 5:1–7, 2000

    2000

  40. [40]

    McClean, Sergio Boixo, Vadim N

    Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes.Nature Communications, 9(1), November 2018. ISSN 2041-1723. doi: 10.1038/s41467-018-07090-4. URL http://dx.doi.org/10.1038/s41467-018-07090-4

    doi:10.1038/s41467-018-07090-4 2018

  41. [41]

    Geometric median and robust estimation in banach spaces.Bernoulli, 21(4), November

    Stanislav Minsker. Geometric median and robust estimation in banach spaces.Bernoulli, 21(4), November

  42. [42]

    Quantum speedup of monte carlo methods.Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471(2181):20150301, September 2015

    Ashley Montanaro. Quantum speedup of monte carlo methods.Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471(2181):20150301, September 2015

    2015

  43. [43]

    Improved convergence in high probability of clipped gradient methods with heavy tailed noise.Advances in Neural Information Processing Systems, 36:24191–24222, 2023

    Ta Duy Nguyen, Thien H Nguyen, Alina Ene, and Huy Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tailed noise.Advances in Neural Information Processing Systems, 36:24191–24222, 2023. 13

    2023

  44. [44]

    Cambridge University, 2010

    Michael A Nielsen and Isaac L Chuang.Quantum Computation and Quantum information. Cambridge University, 2010

    2010

  45. [45]

    Quantum speedups for markov chain monte carlo methods with application to optimization.arXiv preprint arXiv:2504.03626, 2025

    Guneykan Ozgul, Xiantao Li, Mehrdad Mahdavi, and Chunhao Wang. Quantum speedups for markov chain monte carlo methods with application to optimization.arXiv preprint arXiv:2504.03626, 2025

    Pith/arXiv arXiv 2025

  46. [46]

    Information complexity of black-box convex optimization: A new look via feedback information theory

    Maxim Raginsky and Alexander Rakhlin. Information complexity of black-box convex optimization: A new look via feedback information theory. In2009 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 803–510. IEEE, 2009

    2009

  47. [47]

    Reichardt

    Ben W. Reichardt. Reflections for quantum query algorithms. InProceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 560–569. SIAM, 2011. doi: 10.1137/1. 9781611973082.44

    doi:10.1137/1 2011

  48. [48]

    High-probability bounds for stochastic opti- mization and variational inequalities: the case of unbounded variance

    Abdurakhmon Sadiev, Marina Danilova, Eduard Gorbunov, Samuel Horváth, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richtárik. High-probability bounds for stochastic opti- mization and variational inequalities: the case of unbounded variance. InInternational Conference on Machine Learning, pages 29563–29648. PMLR, 2023

    2023

  49. [49]

    Quantum speedups for stochastic optimization.Advances in Neural Information Processing Systems, 36:35300–35330, 2023

    Aaron Sidford and Chenyi Zhang. Quantum speedups for stochastic optimization.Advances in Neural Information Processing Systems, 36:35300–35330, 2023

    2023

  50. [50]

    A tail-index analysis of stochastic gradient noise in deep neural networks

    Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. InInternational Conference on Machine Learning, pages 5827–5837. PMLR, 2019

    2019

  51. [51]

    Multivariate stochastic approximation using a simultaneous perturbation gradient approximation.IEEE transactions on automatic control, 37(3):332–341, 2002

    James C Spall. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation.IEEE transactions on automatic control, 37(3):332–341, 2002

    2002

  52. [52]

    More-efficient quantum multivariate mean value estimator from generalized grover operator,

    Letian Tang. More-efficient quantum multivariate mean value estimator from generalized grover operator,

  53. [53]

    Convex optimization using quantum oracles.Quantum, 4:220, 2020

    Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimization using quantum oracles.Quantum, 4:220, 2020

    2020

  54. [54]

    Inequalities for the rth absolute moment of a sum of random variables,1 ≤r≤ 2.The Annals of Mathematical Statistics, 36(1):299–303, 1965

    Bengt von Bahr and Carl-Gustav Esseen. Inequalities for the rth absolute moment of a sum of random variables,1 ≤r≤ 2.The Annals of Mathematical Statistics, 36(1):299–303, 1965. doi: 10.1214/aoms/1177700291

    arXiv 1965

  55. [55]

    Near-optimal quantum algorithm for minimizing the maximal loss

    Hao Wang, Chenyi Zhang, and Tongyang Li. Near-optimal quantum algorithm for minimizing the maximal loss. InThe Twelfth International Conference on Learning Representations, 2024

    2024

  56. [56]

    Mean estimation in banach spaces under infinite variance and martingale dependence, 2025

    Justin Whitehouse, Ben Chugg, Diego Martinez-Taboada, and Aaditya Ramdas. Mean estimation in banach spaces under infinite variance and martingale dependence, 2025. URL https://arxiv.org/abs/ 2411.11271

    Pith/arXiv arXiv 2025

  57. [57]

    Cambridge university press, 2013

    Mark M Wilde.Quantum information theory. Cambridge university press, 2013

    2013

  58. [58]

    Quantum heavy-tailed bandits.arXiv preprint arXiv:2301.09680, 2023

    Yulian Wu, Chaowen Guan, Vaneet Aggarwal, and Di Wang. Quantum heavy-tailed bandits.arXiv preprint arXiv:2301.09680, 2023

    Pith/arXiv arXiv 2023

  59. [59]

    Quantum lower bounds for finding stationary points of nonconvex functions, 2023

    Chenyi Zhang and Tongyang Li. Quantum lower bounds for finding stationary points of nonconvex functions, 2023. URL https://arxiv.org/abs/2212.03906

    Pith/arXiv arXiv 2023

  60. [60]

    Why are adaptive methods good for attention models?Advances in Neural Information Processing Systems, 33:15383–15393, 2020

    Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models?Advances in Neural Information Processing Systems, 33:15383–15393, 2020

    2020

  61. [61]

    Faster stochastic quasi-newton methods,

    Qingsong Zhang, Feihu Huang, Cheng Deng, and Heng Huang. Faster stochastic quasi-newton methods,

  62. [62]

    Quantum algorithms and lower bounds for finite-sum optimization.arXiv preprint arXiv:2406.03006, 2024

    Yexin Zhang, Chenyi Zhang, Cong Fang, Liwei Wang, and Tongyang Li. Quantum algorithms and lower bounds for finite-sum optimization.arXiv preprint arXiv:2406.03006, 2024

    Pith/arXiv arXiv 2024

  63. [63]

    No-regret reinforcement learning with heavy-tailed rewards, 2021

    Vincent Zhuang and Yanan Sui. No-regret reinforcement learning with heavy-tailed rewards, 2021. URL https://arxiv.org/abs/2102.12769. 15 A Discussion on the Quantum Oracles A.1 Discussion on the Quantum Access Model for Random Variables Comparisons with existing quantum sampling oracles.Unlike in the classical setting, existing work

    Pith/arXiv arXiv 2021

  64. [67]

    idealized model

    assumes that quantum access to the distributionP and to the random variableXis typically provided separately, via a probability oracle and a binary oracle, respectively. Definition A.1(Probability oracle).LetX: Ω →E be a random variable on a probability space(Ω, 2Ω,P ), and letHΩ be a Hilbert space with basis states{|ω⟩}ω∈Ω. A probability oracle for the p...

  65. [2015]

    doi: 10.3150/14-bej645

    ISSN 1350-7265. doi: 10.3150/14-bej645. URL http://dx.doi.org/10.3150/14-BEJ645

    doi:10.3150/14-bej645

  66. [2021]

    URL https://arxiv.org/abs/2004.06479. 14

    Pith/arXiv arXiv 2004

  67. [2025]

    URL https://arxiv.org/abs/2504.06940

    Pith/arXiv arXiv