Pith. sign in

REVIEW 2 major objections 4 minor 25 references

A Regularized Online Newton Method for Stochastic Convex Bandits with Linear Vanishing Noise

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read A regularized online Newton method achieves polylogarithmic regret in stochastic convex bandits with linear vanishing noise under a quadratic growth condition.

desk verdict A careful and mostly sound extension of polylog vanishing-noise bandits to convex losses; the main caveats are the exact knowledge of the quadratic-growth constant and a phantom 'experiments' claim in the concluding section. read the letter →

arxiv 2501.11127 v1 pith:HFXQTFZ7 submitted 2025-01-19 math.OC cs.LGstat.ML

Jingxin Zhan , Yuchen Xin , Kaicheng Jin , Zhihua Zhang This is my paper · ORCID
classification math.OCcs.LGstat.ML MSC 90C2568Q32
keywords stochasticconvexbanditslinearvanishingnoiseonlineNewtonmethodpolylogarithmicregretquadraticgrowthconditionextensionGaussiansmoothingsurrogatemultiplicative
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper asks when a stochastic convex bandit is learnable when the observation noise shrinks as the chosen action approaches the minimizer: at time $t$, the noise is subgaussian with scale at most $\lVert X_t - x_\star\rVert_2$. Its answer is that under a quadratic growth condition on the loss, a Regularized Online Newton Method (RONM) achieves regret that is polylogarithmic in the time horizon $n$, roughly a power of $\log n$, rather than the usual $\sqrt n$ scaling. This extends an earlier polylogarithmic result for linear bandits to general convex losses, and the same machinery gives faster convergence rates when the loss grows faster than quadratically. The paper also introduces and analyzes two new noise models: noise scaled to a subgaussian parameter function, and multiplicative noise.

What carries the argument

The load-bearing object is the precision matrix $\Sigma_t^{-1}$ maintained by the online Newton update, modified by a quadratic regularizer. RONM plays the mean $\mu_t$ of a Gaussian sampling distribution, samples $X_t$, and updates $\Sigma_{t+1}^{-1} = \Sigma_t^{-1} + \eta(\tfrac12 H_t + \gamma I_d)$ with $\gamma=\rho$. Because $\gamma I_d$ is added every round, $\Sigma_t^{-1} \succeq \eta\rho(t-1)I_d$: the precision matrix grows at least linearly in $t$. The proof then uses this linear growth to show that the accumulated estimation error, which in the unregularized analysis would be $\widetilde{O}(\sqrt n)$, is actually $\widetilde{O}(1)$: the differenced losses $Z_t = Y_t - Y_{t-1}$ are each $\widetilde{O}(t^{-1/2})$ with high probability, so $\sum_t Z_t^2$ telescopes to a constant. The regularizer constant $\gamma=\rho$ is chosen so that it cancels against the quadratic-growth lower bound on the surrogate regret in the decomposition, and the $Z_t$ differencing handles the case $f(x_\star)>0$, where raw losses would not concentrate.

What would settle it

Take $K=[-1,1]$, $f(x)=\rho x^2/2$, and conditionally $|X_t-x_\star|$-subgaussian noise with known $\rho$, and run Algorithm 1 for $n$ up to $10^6$. The theorem predicts $R_n=O(\mathrm{poly}(\log n))$ and $|X_t/\pi_+(X_t)-x_\star|=\widetilde{O}(t^{-1/2})$; if the measured regret scales instead like a power of $n$, or if the minimal eigenvalue of $\Sigma_t^{-1}$ does not grow linearly, the central mechanism fails.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.1: if the convex loss $f$ on the convex compact action set $K$ satisfies the $\rho$-quadratic growth condition $f(x) - f(x_\star) \ge (\rho/2)\lVert x - x_\star\rVert_2^2$, then with probability at least $1-\delta$ the regret of Algorithm 1 (RONM) is $O(H^4 d^6 L^{10}/\rho)$, where $L$ grows logarithmically in $n,d,H,1/\rho,1/\delta$, and the action error satisfies $\lVert X_t/\pi_+(X_t) - x_\star\rVert_2 = \widetilde{O}(t^{-1/2})$ for every round $t$. In the author's telling, the right way to read this is that the vanishing noise model is not just tractable in linear bandits: it is tractable for general convex losses as long as the loss itself grows quadratically near its minimizer, and the same proof mechanism yields faster $t^{-1/\ell}$ convergence for $(\beta,\ell)$-convex losses.

Load-bearing premise

The theorem is load-bearing only if the algorithm is handed the exact quadratic-growth constant $\rho$, together with $G$, $r$, and the logarithmic scale $L$, to set $\gamma=\rho$; if $\rho$ is unknown or misspecified, the cancellation between the regularizer and the quadratic-growth lower bound that produces the polylog guarantee no longer holds.

Editorial extensions

If this is right

  • If Theorem 3.1 is correct, stochastic convex bandits with linear vanishing noise are learnable with $O(\mathrm{poly}(d, \log n))$ regret whenever the loss is quadratically growing, removing the linearity restriction of the previous polylog result.
  • The learner's action $X_t/\pi_+(X_t)$ converges to the minimizer at rate $\widetilde{O}(t^{-1/2})$, so exploration shrinks at the same speed as the noise itself; this self-limiting exploration is what makes the logarithmic regret possible.
  • For losses satisfying the stronger $(\beta,\ell)$-convexity condition with $1<\ell<2$, the same algorithm attains the faster action-error rate $\widetilde{O}(t^{-1/\ell})$ with the same polylog regret, at the price of an extra dimension-dependent factor.
  • The corollaries extend the guarantee to noise scaled to a subgaussian parameter function $\sigma(x)$ and to multiplicative noise $Y_t = f(X_t)(1+\bar\varepsilon_t)$: polylog regret follows if either $f$ or $\sigma$ is quadratically growing.
  • For $(\beta,1)$-convex losses with symmetry and unconstrained feedback, the paper proves action error arbitrarily close to $t^{-1}$ (Theorem 3.5) but does not claim a polylog regret in that regime.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural testable extension is to make the algorithm adaptive to an unknown growth rate: because the proof's cancellation relies on the exact equality $\gamma=\rho$, an online estimator of $\rho$ or of the local curvature around $x_\star$ could broaden the range of problems, but the paper provides no such procedure.
  • The proof mechanism suggests a general scaling law: if the noise scale were $\lVert X_t - x_\star\rVert_2^\alpha$ for $\alpha \neq 1$, the growth rate of $\Sigma_t^{-1}$ would presumably change, producing regret exponents depending on $\alpha$; the paper only treats $\alpha=1$.
  • Because the lower-bound methods used for standard bandits fail here, the KL divergence explodes, and the paper leaves open whether polylog regret is minimax optimal; a matching lower bound would be an editorial next step.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper studies stochastic convex bandits in which the subgaussian noise parameter vanishes linearly as the chosen action approaches the minimizer. It proposes a Regularized Online Newton Method (RONM), based on the online Newton method of Fokkema et al., and claims a polylogarithmic regret bound when the loss satisfies a quadratic-growth condition, together with faster convergence rates for (β,ℓ)-convex losses and extensions to noise scaled by a function σ(x) and to multiplicative noise. The main result, Theorem 3.1, is proved through a stopping-time argument, concentration bounds, and a cancellation between the regularizer and the quadratic-growth lower bound. The proofs are detailed and rely heavily on imported lemmas from Lattimore (2024), which are restated in the appendices.

Significance. If the main theorem is correct, the paper makes a meaningful extension of the polylogarithmic-regret result from linear bandits to general stochastic convex bandits under quadratic growth, and it provides new convergence-rate analyses for faster-growing losses and for two additional noise models. The stopping-time analysis, the use of the differenced feedback Z_t, and the explicit regularization to force linear growth of the precision matrix are nontrivial and of independent interest. The paper does not ship code, but the appendices contain a substantial proof effort with all constants listed. The significance is tempered by two load-bearing issues: the result requires exact knowledge of the quadratic-growth constant ρ, and the faster-rate theorem rests on a lemma whose stated hypothesis is inconsistent with the algorithm's displayed constants.

major comments (2)
  1. [Section 3.1, Eq. (5) and Section 4, Eq. (12)] Theorem 3.1's polylogarithmic guarantee is contingent on the learner knowing ρ. Algorithm 1 is parameterized with γ=ρ in Eq. (5), and the cancellation in Eq. (12) only holds if γ≤ρ, because it pairs ηγ/2 Σ||µ_t−x*||² with the quadratic-growth lower bound η eReg_τ(x*) ≥ ηρ/2 Σ||µ_t−x*||². If ρ is overestimated by a constant factor c>1, a positive term η(c−1)ρ/2 Σ||µ_t−x*||² remains; with the proof's own bounds F_t≤1/(2λ²L²) and Σ_t^{-1}⪰ηγt/2 I, this leftover is at least Ω(log n/(λ²L²)), which exceeds the Step-4 target 1/(2λ²L²) by a factor of L. The problem statement does not explicitly give ρ to the learner, so the theorem should either state knowledge of ρ as part of the assumption or provide a way to obtain it; as written, the central claim is not robust to misspecification of this parameter.
  2. [Lemma 5.1 and Section 3.2, Theorem 3.2] The faster t^{−1/ℓ} convergence rate claimed in Theorem 3.2 is not derivable from the Algorithm 1 constants in Eq. (5). Lemma 5.1 assumes r√2σ ≥5d, but for σ=r/(5√(2d)) and r≤R=1 one has r√2σ=r²/(5√d)≤1/(5√d)<5 for every d≥1. In addition, the proof in Appendix E.2 uses the reciprocal form r√2/((1−λ)σ) ≥5d after Eq. (19), so the stated hypothesis does not imply the inequality it is used for. Since Theorem 3.2 is proved by applying Lemma 5.1 with the Algorithm 1 parameters, the theorem requires either a corrected statement of the lemma, different constants, or an explicit parameter regime; this is a load-bearing technical inconsistency, not a cosmetic typo.
minor comments (4)
  1. [Section 3.3 and Appendix B.2, Eq. (41)] The line defining η_κ is garbled by missing formatting ('η κ = β2−κ / 1076 d...'), making the constant unreadable; please rewrite it with clear superscripts and parentheses.
  2. [Section 2.2, Example] The linear example f(x)=⟨x,θ⟩ is said to ignore the assumption f∈[0,1]; after truncation or scaling the QG constant changes, so the '1-QG' statement should be made precise or the example labelled as heuristic.
  3. [Throughout] The notation \tilde O is used informally; for a formal theorem the hidden polylogarithmic factors and their dependence on d, r, G, β should be specified or the notation defined.
  4. [Section 5, after Lemma 5.1] The string 'Bd d' appears to be a typo for B_r^d; please correct it.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the polylog regret bound is derived from the QG assumption and the regularized update, with hyperparameter γ=ρ as a stated problem input rather than a fitted value.

full rationale

The central claim (Theorem 3.1) is not circular. The proof decomposes the online-Newton potential (Eqs. (9) and (10)), inserts the quadratic-growth lower bound (Eq. (11)), and chooses γ=ρ so that the regularizer cancels against that lower bound (Eq. (12)). This is a standard self-bounding argument: the quadratic-growth condition is an assumption, not a conclusion, and the regret bound O(H^4 d^6 L^10/ρ) follows transparently from the chosen constants η=ρ/(100H^2 d^4 L^5) and the bound Reg_n = O(1/(ηλ^2 L)). No parameter is fitted to data and no quantity is defined in terms of the target regret. The linear growth of Σ_t^{-1} is explicitly enforced by the added ηγ I_d term, so it is a design choice rather than a smuggled conclusion. All cited prior results (Fokkema et al., Lattimore, Lumbreras–Tomamichel) are external and are used for standard lemmas; there is no self-citation chain. The requirement that the learner know ρ to set γ=ρ is a genuine limitation, and the proof would break if ρ were misspecified, but that is a robustness/correctness concern, not circularity. The faster-convergence results and corollaries follow from the same machinery without reducing the theorem to its inputs. Hence the derivation is self-contained and non-circular.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on the linear vanishing noise model, the quadratic growth condition, the geometric assumptions on K, and the correctness of imported ONM lemmas. The paper introduces no new physical entities and fits no parameters to data. The main additional assumptions appear only in the ell=1 corollary and are explicitly flagged.

assumptions (5)
  • domain assumption The noise epsilon_t is conditionally sigma_t-subgaussian with sigma_t <= ||X_t - x*|| (linear vanishing noise), and after convex extension the noise remains subgaussian with the same linear decay (Eq. (7)).
    This is the defining model of the paper; the entire polylog result depends on noise vanishing near the optimum.
  • domain assumption The loss f is convex, G-Lipschitz, [0,1]-valued, and satisfies the rho-quadratic growth condition on K (Definition 2.1), with rho known to the algorithm.
    QG provides the lower bound used in Eq. (11) to cancel the regularizer; the algorithm sets gamma = rho in Eq. (5).
  • domain assumption The action set K is convex and compact, contains B_d^r, and is contained in B_d^R with R=1, so the convex extension of Lemma J.13 applies.
    These are the geometric assumptions used throughout the proof and inherited from Fokkema et al.
  • standard math The online Newton method machinery of Fokkema et al. and Lattimore (unbiased estimators, surrogate function lemmas, concentration inequalities, Lemma J.14 regret decomposition) is correct.
    The proof imports many lemmas from Lattimore (2024) and Fokkema et al. (2024); the paper restates them in Appendices H-J but does not re-derive all of them.
  • ad hoc to paper For Theorem 3.5, Assumptions 1-3: f is (beta,1)-convex on R^d, queries outside K are allowed, and f is symmetric about x*.
    These extra hypotheses are introduced specifically to get the t^{-1+kappa/2} rate and are not needed for the main quadratic-growth result.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Regularized Online Newton Method for Stochastic Convex Bandits with Linear Vanishing Noise." pith.science (2026). https://pith.science/paper/HFXQTFZ7

@misc{pith2026250111127,
  author       = {Pith},
  title        = {Pith review of: A Regularized Online Newton Method for Stochastic Convex Bandits with Linear Vanishing Noise},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HFXQTFZ7}},
  note         = {Machine review of arXiv:2501.11127}
}
abstract

We study a stochastic convex bandit problem where the subgaussian noise parameter is assumed to decrease linearly as the learner selects actions closer and closer to the minimizer of the convex loss function. Accordingly, we propose a Regularized Online Newton Method (RONM) for solving the problem, based on the Online Newton Method (ONM) of arXiv:2406.06506. Our RONM reaches a polylogarithmic regret in the time horizon $n$ when the loss function grows quadratically in the constraint set, which recovers the results of arXiv:2402.12042 in linear bandits. Our analyses rely on the growth rate of the precision matrix $\Sigma_t^{-1}$ in ONM and we find that linear growth solves the question exactly. These analyses also help us obtain better convergence rates when the loss function grows faster. We also study and analyze two new bandit models: stochastic convex bandits with noise scaled to a subgaussian parameter function and convex bandits with stochastic multiplicative noise.

Figures

Figures reproduced from arXiv: 2501.11127 by the authors.

Figure 1
Figure 1. This picture shows the case when d = 2 in Lemma 5.2. The yellow segment is Π and the blue sector is the spherical cone we are concerned with. The orange polygon is the combination of the two non-intersecting cones with the same bases Π. E.2 Proof for Lemma 5.1 Recall that in our algorithm, for all t ≤ τ , Σ −1 t ⪰ 1 2Σ¯ −1 t ⪰ 1 2σ2 Id and ∥µt − x⋆∥ 2 Σ −1 t ≤ 1 λ2L2 . Then combining Eq. (19) and Eq. (15), we have E… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 19 canonical work pages

  1. [1]

    Stochastic convex optimization with bandit feedback

    Alekh Agarwal, Dean P Foster, Daniel J Hsu, Sham M Kakade, and Alexander Rakhlin. Stochastic convex optimization with bandit feedback. SIAM Journal on Optimization, 23 0 (1): 0 213--240, 2013

    work page 2013

  2. [2]

    Matrix Analysis, volume 169

    Rajendra Bhatia. Matrix Analysis, volume 169. Springer, 1997

    work page 1997

  3. [3]

    Exploratory distributions for convex functions

    S \'e bastien Bubeck and Ronen Eldan. Exploratory distributions for convex functions. Mathematical Statistics and Learning, 1 0 (1): 0 73--100, 2018

    work page 2018

  4. [4]

    Bandit convex optimization: T regret in one dimension

    S \'e bastien Bubeck, Ofer Dekel, Tomer Koren, and Yuval Peres. Bandit convex optimization: T regret in one dimension. In Conference on Learning Theory, pages 266--278, 2015

    work page 2015

  5. [5]

    Kernel-based methods for bandit convex optimization

    S \'e bastien Bubeck, Ronen Eldan, and Yin Tat Lee. Kernel-based methods for bandit convex optimization. Journal of the ACM (JACM), 68 0 (4): 0 1--35, 2021

    work page 2021

  6. [6]

    About stein's estimators: the original result and extensions

    Tom Demaret et al. About stein's estimators: the original result and extensions. 2019

    work page 2019

  7. [7]

    Error bounds, quadratic growth, and linear convergence of proximal methods

    Dmitriy Drusvyatskiy and Adrian S Lewis. Error bounds, quadratic growth, and linear convergence of proximal methods. Mathematics of Operations Research, 43 0 (3): 0 919--948, 2018

    work page 2018

  8. [8]

    Online convex optimization in the bandit setting: Gradient descent without a gradient

    Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: Gradient descent without a gradient. In SODA'05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 385--394, 2005

    work page 2005

Show all 25 references
  1. [9]

    Hidde Fokkema, Dirk van der Hoeven, Tor Lattimore, and Jack J. Mayo. Online newton method for bandit convex optimisation, 2024. URL https://arxiv.org/abs/2406.06506

    2024 arXiv

  2. [10]

    Bandit convex optimization: Towards tight bounds

    Elad Hazan and Kfir Levy. Bandit convex optimization: Towards tight bounds. In Advances in Neural Information Processing Systems, pages 784--792, 2014

    2014

  3. [11]

    Logarithmic regret algorithms for online convex optimization

    Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69 0 (2): 0 169--192, 2007

    2007

  4. [12]

    Liam Hodgkinson and Michael W. Mahoney. Multiplicative noise and heavy tails in stochastic optimization, 2020. URL https://arxiv.org/abs/2006.06293

    2020 arXiv

  5. [13]

    Linear convergence of gradient and proximal-gradient methods under the polyak- ojasiewicz condition, 2020

    Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradient methods under the polyak- ojasiewicz condition, 2020. URL https://arxiv.org/abs/1608.04636

    2020 arXiv

  6. [14]

    Nearly tight bounds for the continuum-armed bandit problem

    Robert Kleinberg. Nearly tight bounds for the continuum-armed bandit problem. In Advances in Neural Information Processing Systems, pages 697--704. MIT Press, 2005

    2005

  7. [15]

    Improved regret for zeroth-order adversarial bandit convex optimisation

    Tor Lattimore. Improved regret for zeroth-order adversarial bandit convex optimisation. Mathematical Statistics and Learning, 2 0 (3/4): 0 311--334, 2020

    2020

  8. [16]

    Bandit convex optimisation, 2024

    Tor Lattimore. Bandit convex optimisation, 2024. URL https://arxiv.org/abs/2402.06535v3

    2024

  9. [17]

    Improved regret for zeroth-order stochastic convex bandits

    Tor Lattimore and Andr\'as Gy\"orgy. Improved regret for zeroth-order stochastic convex bandits. In Conference on Learning Theory, pages 2938--2964, 2021

    2021

  10. [18]

    A second-order method for stochastic bandit convex optimisation, 2023

    Tor Lattimore and András György. A second-order method for stochastic bandit convex optimisation, 2023. URL https://arxiv.org/abs/2302.05371

    2023 arXiv

  11. [19]

    Adaptive estimation of a quadratic functional by model selection

    Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection . The Annals of Statistics, 28 0 (5): 0 1302 -- 1338, 2000. doi:10.1214/aos/1015957395. URL https://doi.org/10.1214/aos/1015957395

  12. [20]

    Linear bandits with polylogarithmic minimax regret

    Josep Lumbreras and Marco Tomamichel. Linear bandits with polylogarithmic minimax regret. arXiv preprint arXiv:2402.12042, 2024

    2024

  13. [21]

    Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states

    Josep Lumbreras, Erkka Haapasalo, and Marco Tomamichel. Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states. Quantum, 6: 0 749, June 2022. ISSN 2521-327X. doi:10.22331/q-2022-06-29-749. URL http://dx.doi.org/10.22331/q-2022-06-29-749

    2022 doi

  14. [22]

    Online convex optimization with a separation oracle

    Zakaria Mhammedi. Online convex optimization with a separation oracle. arXiv preprint arXiv:2410.02476, 2024

    2024 arXiv

  15. [23]

    Estimation of the mean of a multivariate normal distribution

    Charles M Stein. Estimation of the mean of a multivariate normal distribution. The annals of Statistics, pages 1135--1151, 1981

    1981

  16. [24]

    Second order methods for bandit optimization and control

    Arun Suggala, Y Jennifer Sun, Praneeth Netrapalli, and Elad Hazan. Second order methods for bandit optimization and control. arXiv preprint arXiv:2402.08929, 2024

    2024 arXiv

  17. [25]

    High-dimensional probability: An introduction with applications in data science, volume 47

    Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018

    2018

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.