Pith. sign in

REVIEW 2 major objections 4 minor 27 references

This paper constructs hard convex functions with a hidden 'tube' showing that bandit convex optimization has minimax regret at least d^{5/4}√T over log factors, strictly larger than the linear-bandit Θ(d√T) rate.

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 14:49 UTC pith:6TU24P7O

load-bearing objection Novel construction and a plausible high-level tradeoff, but the proof of Lemma 3.3 relies on a false small-ball inequality, so the d^{5/4}√T lower bound is not established as written. the 2 major comments →

arxiv 2607.18652 v2 pith:6TU24P7O submitted 2026-07-21 stat.ML cs.ITcs.LGmath.IT

The Price of Hidden Curvature: An widetilde{Ω} (d^(5/4) sqrt{T}) Lower Bound for Bandit Convex Optimization

Nived Rajaraman This is my paper
classification stat.ML cs.ITcs.LGmath.IT MSC 68Q3262L0590C25
keywords bandit convex optimizationminimax regret lower boundconvex banditsregret separationFisher informationadaptive sample complexitysoftmax tube constructionanticoncentration
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.

The paper proves that stochastic bandit convex optimization of 1-Lipschitz convex functions on the Euclidean ball has minimax regret Ω~(d^{5/4}√T), the first lower bound that grows faster than the linear-bandit d√T rate. It constructs a hard family of convex functions in 2d dimensions: each function is the scaled softmax of a 'tube' — a norm that forces the two halves of an action to line up through an unknown matrix W* — and a quadratic that penalizes distance to an unknown target u*. Observations reveal u* only near the tube, so a learner must either learn W* or burn samples missing the tube; the analysis shows the optimal tradeoff costs Ω(d^{5/2}/ε²) samples to find an ε-optimal point, which converts to the d^{5/4}√T regret bound. A matching (up to logs) upper bound for this hard prior shows the dimension exponent is not an artifact of the construction, and the same lower bound extends to the unconstrained action space ℝ^d.

Core claim

The central claim is that for every sufficiently large d and every T ≥ C d³/log(ed), no adaptive learner can guarantee expected regret better than c d^{5/4} √(T/log(ed)) over 1-Lipschitz convex functions on the unit ball. The proof builds a prior over functions f_{W*,u*}(a) = ε · softmax( (1/r)||W* a¹ − (r/(8ε)) a²||₂, ½||a¹ − u*||² − ½||u*||² ), where the action is split as a=(a¹,a²) ∈ ℝ^d × ℝ^d. The second softmax branch is minimized at a¹ = u*, but the learner sees its signal only when a² sits on the 'tube' a² ≈ (8ε/r) W* a¹, which depends on the hidden map W*. The analysis tracks two Fisher-information matrices: the posterior-averaged likelihood information about u*, and the total input

What carries the argument

The central mechanism is the 'tube' construction: a convex function whose informative region is the narrow set a² ≈ (8ε/r) W* a¹, hiding the target u* behind an unknown linear map W*. Three tools carry the argument: (i) the Fisher Small-Ball Lemma (Lemma 3.3), a Sobolev-based anticoncentration bound that controls the probability a query lands in the tube by the squared tube radius divided by the learner's directional Fisher information about W*; (ii) the total input Fisher information matrix K_t and its envelope K*, built via a non-commutative Doob maximal inequality so that one matrix dominates every posterior K_t while costing only O(log²(ed) ε² n / (r² d²)) in trace; (iii) the eigenvalue

Load-bearing premise

The entire bound rests on the Fisher Small-Ball Lemma (Lemma 3.3): the posterior probability that a learner's query lands inside the hidden tube is at most a universal constant times (tube radius)² times the inverse directional Fisher information about the hidden matrix; if this anticoncentration inequality failed for a wider class of posteriors, the learner could reach the tube far more frequently than the d^{5/2}/ε² sample-complexity analysis allows.

What would settle it

For d=100 and the paper's parameter choices, simulate the Gaussian-prior hard family, track the posterior Fisher matrix K_t, and check Lemma 3.3 directly: is Pr(||W a¹ − z||₂ ≤ s) · a^{1T} K(ρ)^{-1} a¹ ≤ C s² ever violated by more than universal constants under an adaptive query sequence? Or test the sample-complexity claim by attempting to find an ε-optimal action in fewer than c d^{5/2}/ε² log(ed) queries using any adaptive rule; success would falsify the bound.

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

If this is right

  • For stochastic bandit convex optimization, minimax regret is at least c d^{5/4} √(T/log(ed)), strictly exceeding the Θ(d√T) linear-bandit rate — an open separation that is now settled.
  • Any successful learner must incur Ω(d^{5/2}/ε²) queries to find an ε-optimal action on this hard family, matching the Bayesian two-stage exploration algorithm the paper constructs, so the d-exponent is tight for this prior.
  • The lower bound extends from the Euclidean-ball action space to the unconstrained setting ℝ^d, so the separation is not an artifact of a bounded domain.
  • The paper conjectures that the true minimax regret is Θ~(d^{3/2}√T ∧ T), refining the previous conjecture by targeting the exact dimension dependence.

Where Pith is reading between the lines

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

  • The hidden-tube mechanism suggests a general recipe: in zeroth-order convex optimization, nonlinearities can act as 'information shields' that force learning of nuisance structure before the target can be estimated; analogous shields may produce intermediate rates (between d√T and d^{3/2}√T) in smooth or strongly convex settings depending on curvature.
  • The Fisher Small-Ball Lemma is likely reusable beyond this proof as a standard tool for adaptive experiments with linear-nuisance parameters — it converts 'volume of a small cylinder' intuitions into a posterior-Fisher-information bound valid in high dimension.
  • A direct testable extension would chain several tubes in series with actions blocked per tube; the paper argues this grows the cost additively, but a design that forces simultaneous satisfaction of multiple hidden constraints — preventing sequential recentering — could push the exponent toward the conjectured d^{3/2}√T.
  • The construction's matching upper bound (Theorem 5.1) implies that any further improvement must come from a different prior/hard family, not from retuning the tube width r in this one — useful guidance for future lower-bound attempts.

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

2 major / 4 minor

Summary. The paper claims a new minimax lower bound for stochastic bandit convex optimization (BCO) of 1-Lipschitz convex functions on the Euclidean ball: regret Ω̃(d^{5/4}√T), which would separate BCO from linear bandits. The hard instance is a softmax of a 'tube' term r^{-1}‖W^* a^1 - (r/(8ε)) a^2‖ and a quadratic (1/2)‖a^1 - u^*‖^2, with Gaussian prior on (W^*, u^*). The proof uses posterior Fisher information matrices, a curvature bound (Lemma 3.2), a 'Fisher small-ball lemma' (Lemma 3.3) to control the probability of hitting the hidden tube, a noncommutative Doob maximal inequality to build a dominating Fisher envelope (Lemma 3.4), and a transfer from Gaussian to bounded priors. A matching upper bound for the Gaussian prior is given in Theorem 5.1, and the lower bound is extended to unconstrained action spaces in Theorem 5.2.

Significance. If the main theorem (Corollary 1.2) were established, it would be a major advance: it would show that stochastic BCO is fundamentally harder than linear bandits, breaking the long-standing Ω(d√T) barrier. The manuscript is unusually thorough, providing detailed proofs of all auxiliary technical lemmas, a matching upper bound for the constructed Gaussian family, and a careful treatment of the bounded-prior and unconstrained extensions. However, the proof rests on Lemma 3.3, whose proof appears to be invalid because the stated small-ball inequality (Eq. (32)) is false in general. Since this lemma is load-bearing for the exploration/exploitation tradeoff, the central claim is not established by the current manuscript.

major comments (2)
  1. [§3.2, Lemma 3.3 and Eq. (32)] The proof of Lemma 3.3 relies entirely on Eq. (32): sup_z Pr(‖Z-z‖≤s) ≲ s²/d² · Tr(J(Z)). This inequality is false for general smooth densities. Consider Z distributed according to a smoothed uniform distribution on the unit sphere in R^d with thickness δ. For s=1 and z=0, the left-hand side is 1 (the whole mass lies in the unit ball). The density depends only on the radial coordinate, so the score is radial with magnitude ~1/δ; hence Tr(J(Z)) ~ 1/δ², independent of d. Eq. (32) would then require 1 ≤ C/(d²δ²), impossible for any universal C and large d. Consequently the proof of Lemma 3.3 collapses. Moreover, the lemma itself is false as stated: taking W with first column distributed as the sphere shell and other columns degenerate gives a1 = e1, a1^T K(ρ)^{-1} a1 ~ d²δ², while Pr(‖W a1 - z‖≤s)=1 for s=1 and z=0, so the left side of Eq. (31) is unbounded in d, contradicting the claimed u
  2. [§3.2, use of Lemma 3.3 in Eq. (25)] Lemma 3.3 is directly used to derive Eq. (25), which bounds the expected softmax weight p_t² and yields the tradeoff in Eq. (26). This tradeoff is the core of Lemma 2.2 and Theorem 2.3. Without a valid proof of Lemma 3.3, the bound E[p_t² a1_t^T K_{t-1}^{-1} a1_t 1_ℰ] ≲ r² does not follow, and the exploration/exploitation balance (Eqs. (15)–(16)) that produces the d^{5/4}√T rate is unsupported. Since this is a load-bearing step, the main lower bound (Corollary 1.2) is not proven in the current form.
minor comments (4)
  1. [§3.1] Typo in the sentence 'Next next two lemmas connect...' should read 'The next two lemmas'.
  2. [Throughout] The notation eΩ, eΘ, and Õ is used without explicit definition of the tilde-notation (poly-logarithmic factors); standard in the field but a formal definition would improve accessibility.
  3. [§1 and abstract] The paper does not explicitly define the action space dimension and ambient dimension mapping between 2d and d in Theorem 1.1 before the proof; this is eventually addressed, but an early clarification would help.
  4. [§5.2, Eq. (45)] The smoothed conic extension is introduced with several constants (λ, ρ, 𝔯0) and a smoothed hinge Ψ; the derivation in Appendix B is lengthy and would benefit from a short table of parameter choices.

Circularity Check

0 steps flagged

No circularity found; the central lower bound is self-contained and does not reduce to fitted inputs or load-bearing self-citations.

full rationale

The derivation starts from an explicit Gaussian prior (Eq. 9) with fixed parameters (Eq. 10), and the hard-function class is defined independently of the target regret. Theorem 2.3 combines two genuinely derived information-theoretic claims: Lemma 2.1 (accurate estimation of u* forces large likelihood Fisher information) and Lemma 2.2 (a budget tradeoff between learning W* and learning u*). These are proved from the posterior Fisher identity, matrix concentration, the small-ball Lemma 3.3, and the Fisher-information envelope Lemma 3.4. The small-ball lemma is justified by an external Sobolev inequality (Talenti, 1976); even if that inequality step were invalid, that would be a correctness issue, not circularity. The parameter r^2 = log(ed)/sqrt(d) is chosen by balancing the two lower bounds m1 and m2 in the proof of Theorem 2.3, not by fitting the final regret expression. The matching Gaussian-prior upper bound in Theorem 5.1 is explicitly and correctly described as applying only to that prior and not implying the minimax rate, so it is not used to derive the minimax claim. The only self-citation (Rajaraman et al., 2024) appears in background context for the linear-bandit baseline and is not load-bearing for the new construction. No uniqueness theorem, ansatz, or known result is imported from the authors' prior work as a substitute for proof, and no prediction is a renamed fitted parameter. The paper's own limitation discussion is about possible extensions, not about the derivation being circular. Accordingly, the circularity score is 0.

Axiom & Free-Parameter Ledger

3 free parameters · 6 axioms · 0 invented entities

All axioms are either standard mathematical theorems cited in the literature (Talenti, Junge, Pinelis, Tropp, Dembo et al.) or explicit choices in the hard-instance construction. No new physical entities or unstated hidden variables are postulated beyond the construction's W* and u*, which are conventional statistical parameters. The construction parameters ε and r are part of the theorem's quantifier structure and are tuned to balance the two proven lower-bound costs, not fitted to data.

free parameters (3)
  • r (tube width) = sqrt(log(ed)/sqrt(d))
    Tuned in Eq. (10) to balance W*-exploration cost d² r²/(ε² E²) and u*-exploration cost d E²/(ε² r²) (Section 1.2); the balancing yields the d^{5/2}/ε² sample complexity and the d^{5/4}√T regret rate. A hand-tuned construction parameter, not a data fit.
  • ε (accuracy target) = in (0, 1/(16 d^{1/4}))
    The target accuracy parameterizing the hard family; the lower bound holds for every ε in this range, and the regret conversion sets ε² ≍ d^{5/2} log/T. Introduced as part of the theorem statement rather than fitted to data.
  • prior variances = vec(W*)∼N(0, I/d), u*∼N(0, I/(16d))
    Eq. (9) scaling ensures W* and u* have O(1) norm on the typical event and controls Lipschitzness after conditioning on the bounded event E_b. Chosen by hand as part of the hard-instance design.
axioms (6)
  • standard math Sharp Euclidean small-ball inequality: sup_z Pr(||Z−z||≤s) ≲ s² Tr(J(Z))/d² for d≥3
    Used to prove Lemma 3.3; cited to Talenti (1976) but not proved in the text.
  • standard math Noncommutative Doob maximal inequality for positive matrix martingales (Junge 2002; Junge–Xu 2005)
    Used in Lemma 3.4 to construct a single H_n-measurable envelope K* dominating every K_t; the (p−1)^{-2} constant produces the log²(ed) factor.
  • standard math Hilbert-space martingale moment inequality (Pinelis 1994)
    Bounds the complete-data score moments in Lemma 3.4.
  • standard math Matrix Cramér–Rao inequality and conditional posterior Fisher identity (Dembo et al. 1991)
    Connects estimation error of u* to posterior Fisher information in Lemma 2.1.
  • domain assumption Conditioning the unbounded Gaussian prior on the event {||W||_op≤4, ||u||≤3/8} preserves the lower bound up to e^{-cd} terms (Lemmas 4.1–4.3)
    The hard functions must be 1-Lipschitz with a minimizer inside the unit ball; this conditioning guarantees membership in F_d(B_d^2).
  • domain assumption Observation model: noisy function values y = f(a) + N(0,1) (Eq. (1)), and actions restricted to B_d^2 or R^d
    The problem definition of stochastic bandit convex optimization; the unconstrained extension uses a conic extension to keep outside-ball queries uninformative.

pith-pipeline@v1.3.0-alltime-deepseek · 34069 in / 53254 out tokens · 431098 ms · 2026-08-01T14:49:09.316494+00:00 · methodology

0 comments
read the original abstract

We establish a $\widetilde\Omega(d^{5/4}\sqrt T)$ lower bound on the minimax expected regret of stochastic bandit convex optimization of $1$-Lipschitz functions on the Euclidean ball. This presents the first nontrivial regret lower bound that grows faster than $d\sqrt{T}$ for this problem, establishing that stochastic bandit convex optimization is fundamentally harder than linear bandits. The hard class of convex functions we construct takes the following form in dimension $2d$: for an action $a = (a^1,a^2) \in \mathbb{B}^{2d}_2$, each function is the scaled soft maximum of a "tube", $r^{-1} \| W^\star a^1 - \frac{r}{8\varepsilon} a^2 \|_2$ (hyperparameterized by $\varepsilon,r$), and a squared distance function, $\frac12 \| a^1 - u^\star \|_2^2 - \frac12 \| u^\star \|_2^2$. Here, $W^\star \in \mathbb{R}^{d \times d}$ is an unknown linear transformation, and $u^\star \in \mathbb{R}^{d}$ is an unknown vector which must be learned to minimize the function. Observations are informative about $u^\star$ only when the learner's action lies near the tube determined by $W^\star$, satisfying $a^2 \approx \frac{8\varepsilon}{r} W^\star a^1$: thus the learner must either find this tube without knowing $W^\star$, or spend observations learning useful directions of $W^\star$. Formally, our regret analysis exploits this tradeoff by bounding the posterior spread of Fisher information matrices obtained under an adaptive sequence of actions. Together, these ingredients give a sample complexity lower bound of $\widetilde{\Omega}(d^{5/2}/\varepsilon^2)$ to find an $\varepsilon$-optimal action, which translates to an $\widetilde{\Omega} (d^{5/4} \sqrt{T})$ regret lower bound. We also extend this lower bound to the unconstrained setting where the action space is $\mathbb{R}^d$.

Figures

Figures reproduced from arXiv: 2607.18652 by Nived Rajaraman.

Figure 1
Figure 1. Figure 1 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

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

27 extracted references

  1. [1]

    Annali di Matematica Pura ed Applicata , volume =

    Talenti, Giorgio , title =. Annali di Matematica Pura ed Applicata , volume =

  2. [2]

    2017 , doi =

    Leoni, Giovanni , title =. 2017 , doi =

    2017

  3. [3]

    1937 , publisher=

    Some matrix-inequalities and metrization of matric space , author=. 1937 , publisher=

    1937

  4. [4]

    The Annals of Probability , pages=

    Optimum bounds for the distributions of martingales in Banach spaces , author=. The Annals of Probability , pages=. 1994 , publisher=

    1994

  5. [5]

    IEEE Transactions on Information theory , volume=

    Information theoretic inequalities , author=. IEEE Transactions on Information theory , volume=. 1991 , publisher=

    1991

  6. [6]

    Mathematics of Operations Research , volume=

    Linearly parameterized bandits , author=. Mathematics of Operations Research , volume=. 2010 , publisher=

    2010

  7. [7]

    Advances in neural information processing systems , volume=

    Exploiting higher order smoothness in derivative-free optimization and continuous bandits , author=. Advances in neural information processing systems , volume=

  8. [8]

    Proceedings of Thirty Eighth Conference on Learning Theory , pages =

    Linear Bandits on Ellipsoids: Minimax Optimal Algorithms , author =. Proceedings of Thirty Eighth Conference on Learning Theory , pages =. 2025 , editor =

    2025

  9. [9]

    Advances in neural information processing systems , volume=

    Query complexity of derivative-free optimization , author=. Advances in neural information processing systems , volume=

  10. [10]

    Journal of Machine Learning Research , volume=

    Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm , author=. Journal of Machine Learning Research , volume=

  11. [11]

    2018 , doi =

    Vershynin, Roman , title =. 2018 , doi =

    2018

  12. [12]

    Journal f\"ur die reine und angewandte Mathematik , volume =

    Junge, Marius , title =. Journal f\"ur die reine und angewandte Mathematik , volume =

  13. [13]

    Bulletin of the London Mathematical Society , volume =

    Junge, Marius and Xu, Quanhua , title =. Bulletin of the London Mathematical Society , volume =

  14. [14]

    , title =

    Tropp, Joel A. , title =. Electronic Communications in Probability , volume =. 2011 , note =

    2011

  15. [15]

    2024 , journal =

    Rajaraman, Nived and Han, Yanjun and Jiao, Jiantao and Ramchandran, Kannan , title =. 2024 , journal =

    2024

  16. [16]

    Advances in Neural Information Processing Systems , volume=

    Information-theoretic lower bounds on the oracle complexity of convex optimization , author=. Advances in Neural Information Processing Systems , volume=

  17. [17]

    and Kalai, Adam Tauman and McMahan, H

    Flaxman, Abraham D. and Kalai, Adam Tauman and McMahan, H. Brendan , title =. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

  18. [18]

    Bandit Convex Optimization:

    Bubeck, S. Bandit Convex Optimization:. Proceedings of the 28th Conference on Learning Theory , series =. 2015 , url =

    2015

  19. [19]

    Exploratory Distributions for Convex Functions , journal =

    Bubeck, S. Exploratory Distributions for Convex Functions , journal =. 2018 , doi =

    2018

  20. [20]

    Kernel-Based Methods for Bandit Convex Optimization , journal =

    Bubeck, S. Kernel-Based Methods for Bandit Convex Optimization , journal =. 2021 , doi =

    2021

  21. [21]

    Mathematical Statistics and Learning , volume =

    Lattimore, Tor , title =. Mathematical Statistics and Learning , volume =. 2019 , doi =

    2019

  22. [22]

    and Hsu, Daniel and Kakade, Sham M

    Agarwal, Alekh and Foster, Dean P. and Hsu, Daniel and Kakade, Sham M. and Rakhlin, Alexander , title =. SIAM Journal on Optimization , volume =. 2013 , doi =

    2013

  23. [23]

    Proceedings of the 34th Conference on Learning Theory , series =

    Lattimore, Tor and Gyorgy, Andras , title =. Proceedings of the 34th Conference on Learning Theory , series =. 2021 , url =

    2021

  24. [24]

    A Second-Order Method for Stochastic Bandit Convex Optimisation , booktitle =

    Lattimore, Tor and Gy. A Second-Order Method for Stochastic Bandit Convex Optimisation , booktitle =. 2023 , url =

    2023

  25. [25]

    , title =

    Fokkema, Hidde and van der Hoeven, Dirk and Lattimore, Tor and Mayo, Jack J. , title =. Proceedings of the 37th Conference on Learning Theory , series =. 2024 , url =

    2024

  26. [26]

    and Kakade, Sham M

    Dani, Varsha and Hayes, Thomas P. and Kakade, Sham M. , title =. Proceedings of the 21st Annual Conference on Learning Theory , pages =

  27. [27]

    Proceedings of the 26th Conference on Learning Theory , series =

    Shamir, Ohad , title =. Proceedings of the 26th Conference on Learning Theory , series =. 2013 , url =

    2013