{"id":"5d5c9bc6-4d9f-4404-b2d7-d8a2f7c3fc81","arxiv_id":"2501.11127","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A regularized online Newton method achieves polylogarithmic regret in convex bandits with linear vanishing noise under quadratic growth.","lead":"Researchers propose a regularized online Newton method for stochastic convex bandits, and prove it achieves polylogarithmic regret when the loss grows quadratically and noise vanishes linearly near the optimum. The result extends a known linear-bandit result to general convex losses, with new convergence-rate analyses for faster-growing losses.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The polylog guarantee is conditional on exact knowledge of ρ: the cancellation in Eq. (12) holds only at γ = ρ, and any constant-factor overestimate of ρ leaves an O(1/(λ²L)) term that breaks the stopping-time induction in Step 4.","rationale":"I read the paper in good faith and found the main argument of Theorem 3.1 to be carefully structured and largely internally consistent: the regularized update forces the linear lower bound Σ_t^{-1} ⪰ ηγt/2 I, the difference estimator Z_t = Y_t − Y_{t−1} correctly eliminates the unknown baseline f(x*), and the high-probability stopping-time argument appears to close when γ = ρ. The constants in Appendix K are mutually compatible for the stated parameter regime. The reader's weakest assumption—that the algorithm requires knowledge of ρ—is indeed the most load-bearing concern. It is not merely a matter of convenience: the cancellation in Eq. (12) is what removes the regularizer term from the potential bound, and an overestimate of ρ leaves a positive term whose size, by the proof's own inequalities, is O(1/(λ²L)), which is L times larger than the threshold 1/(2λ²L²) needed for the induction. Hence a constant-factor misspecification of ρ invalidates the proof as written. A lower bound γ ≤ ρ would work, so the real requirement is a valid lower bound on ρ, but the paper states the algorithm with γ = ρ and does not discuss adaptation or estimation of ρ. The missing experiments mentioned in Section 6 are a genuine but non-central issue; they do not affect the theorem's validity. Since my concern aligns with the reader's weakest assumption and does not move the overall verdict, I recommend leaving the CONDITIONAL verdict unchanged.","tokens_in":39937,"tokens_out":31970,"duration_ms":297689,"concrete_test":"Re-derive Appendix A Step 4 with γ = cρ for a fixed c > 1 (e.g., c = 2). Equation (12) then acquires the extra term η(c−1)ρ/2 Σ_{t=1}^τ ||µ_t − x*||²_2. Applying the proof's own bounds ||µ_t − x*||²_2 ≤ 1/(ηγλ²L²t) and Σ_{t=1}^τ 1/t ≤ L, this term is at least (1 − 1/c)/(2λ²L), which exceeds the required F_{τ+1} ≤ 1/(2λ²L²) by a factor L whenever c − 1 is a positive constant. If this calculation checks out, the proof of τ = n fails under constant-factor overestimation of ρ, confirming that exact (or sufficiently accurate) knowledge of ρ is load-bearing.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3.1's proof depends on the cancellation in Eq. (12): the regularizer contribution ηγ/2 Σ||µ_t − x*||² is removed using the quadratic-growth lower bound η eReg ≥ ηρ/2 Σ||µ_t − x*||². This requires γ ≤ ρ, and the paper sets γ = ρ in Eq. (5). If ρ is unknown and γ is chosen larger than ρ, the leftover positive term η(γ − ρ)/2 Σ||µ_t − x*||² appears. Using the proof's own stopping-time bounds, F_t ≤ 1/(2λ²L²) and Σ_t^{-1} ⪰ ηγt/2 I, one has ||µ_t − x*||² ≤ 1/(ηγλ²L²t), so the leftover term is Ω(1/(λ²L)) for any fixed c = γ/ρ > 1. The target in Step 4 is F_{τ+1} ≤ 1/(2λ²L²), so this leftover is a factor L too large and the induction showing τ = n cannot close unless c − 1 = O(1/L). Thus the central claim is not robust to misspecification of ρ, and the problem statement does not explicitly give ρ to the learner. This is the most load-bearing limitation of the claimed polylogarithmic guarantee.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":40259,"tokens_out":11101,"duration_ms":113050,"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":[{"comment":"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.","section":"Section 3.1, Eq. (5) and Section 4, Eq. (12)"},{"comment":"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.","section":"Lemma 5.1 and Section 3.2, Theorem 3.2"}],"minor_comments":[{"comment":"The line defining η_κ is garbled by missing formatting ('η κ = β2−κ / 1076 d...'), making the constant unreadable; please rewrite it with clear superscripts and parentheses.","section":"Section 3.3 and Appendix B.2, Eq. (41)"},{"comment":"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.","section":"Section 2.2, Example"},{"comment":"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.","section":"Throughout"},{"comment":"The string 'Bd d' appears to be a typo for B_r^d; please correct it.","section":"Section 5, after Lemma 5.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a serious theoretical contribution, but the two issues above must be resolved before publication. The parameter-knowledge issue can be fixed by an explicit assumption; the Lemma 5.1 inconsistency likely reflects a typo in the condition but affects a stated theorem. I saw no grounds for questioning the provenance of the results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper gives a clean answer to a natural question: with linear vanishing noise and quadratic growth, polylog regret is achievable beyond linear bandits. The RONM algorithm and the precision-matrix growth analysis are genuinely new. The proof is detailed, the constants are listed in Appendix K, and I did not find a fatal error in the main regret decomposition. The corollaries for sigma(x)-scaled and multiplicative noise are a nice bonus. This deserves a serious referee.\n\nThe main soft spot is the exact knowledge of rho. The algorithm sets gamma = rho in Eq. (5), and the proof's cancellation in Eq. (12) depends on gamma <= rho. If rho is unknown or overestimated by any constant factor, the leftover positive term breaks the stopping-time induction, as the stress-test note shows. That is a real limitation: the theorem is really for the known-rho case. The paper should state this explicitly and discuss what happens with only a lower bound or an estimate. It is not a fatal flaw, because knowing strong-convexity-type constants is common in this literature, but it is load-bearing and deserves to be highlighted.\n\nA smaller issue: Section 6 says \"the experiments have shown\" twice, but the paper contains no experiments. That passage should be removed or an experiments section should be added. It looks like a leftover from an earlier draft.\n\nThe reliance on imported lemmas from Lattimore (2024) is fine; they are restated in appendices and the dependence is transparent. I also see no circularity or fitted parameters.\n\nWho is this for? Bandit theorists working on second-order methods, vanishing noise, or quadratic growth conditions. It is a solid theoretical paper, not a breakthrough, but it resolves a natural question and opens a small research thread. I would send it to peer review, with the request that the rho-knowledge requirement be stated precisely and the experiments claim be fixed.","headline":"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.","tokens_in":40782,"tokens_out":1803,"would_cite":true,"duration_ms":20409,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"A regularized online Newton method achieves polylogarithmic regret in stochastic convex bandits with linear vanishing noise under a quadratic growth condition.","keywords":["stochastic convex bandits","linear vanishing noise","online Newton method","polylogarithmic regret","quadratic growth condition","convex extension","Gaussian smoothing surrogate","multiplicative noise"],"falsifier":"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.","tokens_in":39745,"feed_emoji":"🎯","tokens_out":8924,"duration_ms":90028,"temperature":0.7,"pith_summary":"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.","feed_headline":"Regret becomes polylog in convex bandits with vanishing noise","feed_subtitle":"A regularizer matched to the loss's quadratic growth cuts regret from sqrt n to polylog n.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the base Online Newton Method for bandit convex optimization and the regret decomposition that RONM modifies with a regularizer and differenced losses.","marker":"Fokkema et al. [2024]"},{"why":"Introduced the linear vanishing noise model and proved polylog regret for linear bandits; Theorem 3.1 recovers that result in the linear case.","marker":"Lumbreras and Tomamichel [2024]"},{"why":"Provides the surrogate-function, convex-extension, and concentration lemmas that the proof relies on throughout.","marker":"Lattimore [2024]"},{"why":"Contributes the use of $Z_t = Y_t - Y_{t-1}$ in the gradient and Hessian estimators, which is essential when $f(x_\\star)>0$.","marker":"Lattimore and György [2023]"},{"why":"Defines the online Newton update for quadratic losses that RONM extends with a quadratic regularizer.","marker":"Hazan et al. [2007]"},{"why":"Gives the generalized Stein lemma used to lower-bound expected Hessian increments in terms of the precision matrix.","marker":"Stein [1981]"}],"fun_headline_variants":["Polylog regret in convex bandits with vanishing noise","Regularized online Newton yields polylog regret in convex bandits","Vanishing noise reduces convex bandit regret to polylog","Convex bandits with vanishing noise achieve polylog regret"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Polylog regret in convex bandits with vanishing noise","Regularized online Newton yields polylog regret in convex bandits","Vanishing noise reduces convex bandit regret to polylog","Convex bandits with vanishing noise achieve polylog regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000831,"raw_usage":{"total_tokens":3638,"prompt_tokens":964,"completion_tokens":2674,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":2603}},"tokens_in":580,"tokens_out":2674,"duration_ms":18608,"temperature":1.0,"reasoning_tokens":2603,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T18:37:04.053869+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Linear bandits with polylogarithmic minimax regret","cited_arxiv_id":null,"evidence_quote":"Introduced the linear vanishing noise model and proved polylog regret for linear bandits; Theorem 3.1 recovers that result in the linear case."},{"cited_title":"A Second-Order Method for Stochastic Bandit Convex Optimisation","cited_arxiv_id":"2302.05371","evidence_quote":"Contributes the use of $Z_t = Y_t - Y_{t-1}$ in the gradient and Hessian estimators, which is essential when $f(x_\\star)>0$."},{"cited_title":"Logarithmic regret algorithms for online convex optimization","cited_arxiv_id":null,"evidence_quote":"Defines the online Newton update for quadratic losses that RONM extends with a quadratic regularizer."},{"cited_title":"Estimation of the mean of a multivariate normal distribution","cited_arxiv_id":null,"evidence_quote":"Gives the generalized Stein lemma used to lower-bound expected Hessian increments in terms of the precision matrix."}],"review_version":1}