{"id":"b8d5be09-f579-4074-97b2-ea9c5a0bab9e","arxiv_id":"2607.18652","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Stochastic bandit convex optimization has minimax regret at least Ω~(d^{5/4}√T), the first lower bound exceeding the linear-bandit d√T rate.","lead":"A new lower bound shows that bandit convex optimization — learning to minimize an unknown convex function from noisy function values — has minimax regret Ω~(d^{5/4}√T), strictly larger than the d√T rate of linear bandits. A smart generalist may read it because it proves, for the first time, that convex bandits are fundamentally harder than linear bandits, resolving a long-open separation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Lemma 3.3 relies on a false small-ball inequality (Eq. 32); the Sobolev step is invalid, so the d^{5/4}√T bound is not established.","rationale":"The reader identified Lemma 3.3 as the weakest load-bearing assumption and requested independent checking. My stress-test confirms that this is the right locus, but sharpens the concern: it is not merely a 'black-box' inequality to be checked, but a specific step in the proof (Eq. 32) that appears demonstrably false. The spherical-shell counterexample shows that Eq. (32) cannot hold with a universal constant for all smooth densities; the paper's proof of Lemma 3.3 therefore has a concrete gap. Because Lemma 3.3 is used directly to obtain Eq. (25) and the Fisher-information tradeoff in Lemma 2.2, the central regret bound is not established by the current manuscript. I do not claim Lemma 3.3 itself is false—it may be true for the specific posteriors arising under the Gaussian prior, where K⪰I_d—but the provided proof is invalid. The result is therefore unverified rather than accepted, even conditionally. A corrected proof of Lemma 3.3 (or a different small-ball argument) is needed before the claim can be evaluated.","tokens_in":34556,"tokens_out":52826,"duration_ms":491926,"concrete_test":"Independently re-derive Eq. (32) from the sharp Sobolev inequality. The H^1 embedding gives, for any density p, Pr(||X-z||≤s) ≤ C_d s² ||∇√p||₂², with C_d ~ const/d (so the bound is s²/d · Tr(J), not s²/d² · Tr(J)). Then instantiate a smoothed uniform distribution on the unit sphere in R^d with fixed width δ (e.g., δ=0.1) and compute Tr(J)≈1/δ². For s=1, z=0, the left side of Eq. (32) is 1, while the right side is C/(d²δ²), which is <1 for all d > C^(1/2)/δ. Hence Eq. (32) is false for any universal constant, and the proof of Lemma 3.3 fails.","verdict_should_be":"UNVERDICTED","load_bearing_attack":"The proof of Lemma 3.3 (Fisher Small-Ball Lemma) hinges entirely on Eq. (32), attributed to Talenti's Sobolev inequality: sup_z Pr(||Z-z||≤s) ≲ s^2/d^2 Tr(J(Z)). This inequality cannot hold for general smooth densities with universal constant. Consider a smoothed uniform distribution on the unit sphere in R^d with thickness δ. The small-ball probability with s=1 and z=0 is exactly 1 (the entire mass lies in the unit ball). The Fisher information Tr(J(Z)) is O(1/δ^2): the density depends essentially only on the radial coordinate, so the score is radial and its squared norm is ~1/δ^2, independent of d. Thus Eq. (32) would require 1 ≤ C/(d^2 δ^2), which for fixed δ tends to 0 as d→∞, impossible for any universal C. The standard Sobolev/H^1 derivation actually yields a factor 1/d, not 1/d^2; the extra 1/d is obtained by a dimension-counting error. Since Eq. (32) is the sole justification for Lemma 3.3, the proof of Lemma 3.3 collapses. This lemma is load-bearing: it controls the tube-hitting probability via Eq. (25), converting the volumetric intuition into the s² scaling used in Eqs. (15)-(16). Without a valid proof of Lemma 3.3, the exploration/exploitation tradeoff underlying Theorem 2.3 and hence Corollary 1.2 is unsupported. The lemma itself may be salvageable by a different argument, but the current manuscript does not provide one.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":34870,"tokens_out":11174,"duration_ms":129053,"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":[{"comment":"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","section":"§3.2, Lemma 3.3 and Eq. (32)"},{"comment":"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.","section":"§3.2, use of Lemma 3.3 in Eq. (25)"}],"minor_comments":[{"comment":"Typo in the sentence 'Next next two lemmas connect...' should read 'The next two lemmas'.","section":"§3.1"},{"comment":"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.","section":"Throughout"},{"comment":"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.","section":"§1 and abstract"},{"comment":"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.","section":"§5.2, Eq. (45)"}],"recommendation":"major_revision","confidential_remarks":"The false small-ball inequality (Eq. (32)) is a serious correctness gap. The paper's central claim is plausible and the construction is intriguing, but the current proof does not establish it. The author should either prove a correct version of Lemma 3.3 under the specific posterior structure (e.g., using log-concavity or Gaussian-mixture properties), or substantially modify the argument. Unless this is repaired, the paper cannot be accepted. Given the novelty, a major revision that fixes the lemma could make the paper publishable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nWhat you should know: this paper contains the first construction that might separate stochastic BCO from linear bandits, and the high-level story is compelling. But the proof of the load-bearing small-ball lemma (Lemma 3.3) is built on an inequality that is false, so the claimed d^{5/4}√T bound is not established.\n\nThe construction is genuinely new: a softmax of a hidden tube and a quadratic, with a posterior Fisher-information envelope built from noncommutative Doob maximal inequalities. The paper is unusually careful for a lower-bound paper: Lemma 2.1, the Fisher identity, the curvature bound, the bounded-prior transfer, and the online-to-batch conversion are all spelled out. The matching two-stage upper bound for the Gaussian prior (Theorem 5.1) is a good sanity check and rules out tuning the tube width for a stronger bound within this prior.\n\nThe soft spot is exactly where the stress-test points. Lemma 3.3 relies entirely on Eq. (32): for any smooth density of Z, sup_z P(||Z-z||≤s) ≲ s²/d² Tr(J(Z)). That inequality is not a consequence of Talenti's Sobolev inequality. The Sobolev route gives P ≲ (s/d)√Tr(J), not the squared version, and the extra factor of 1/d in the square is not available. A smoothed uniform distribution on a thin spherical shell is a concrete counterexample: the small-ball probability with s=2 is 1, while Tr(J) ~ d/δ, so Eq. (32) would require 1 ≤ C/(dδ), false for fixed δ and large d. Since Lemma 3.3 is the only argument converting the volumetric intuition into the s² scaling used in Eq. (25), the whole exploration/exploitation tradeoff in Lemma 2.2 and Theorem 2.3 is unsupported. The lemma may be salvageable with a different proof—perhaps exploiting the specific Gaussian-posterior structure—but the manuscript does not provide one.\n\nThat's not a minor blemish; it's a load-bearing gap. The rest of the paper, however, is coherent and the authors are candid about limitations. The AI-use statement makes the lack of a machine-checked proof more salient, but the problem is mathematical, not a question of authorship.\n\nWho this is for: anyone working on lower bounds for bandit convex optimization. The construction and the envelope technique deserve a serious referee, and if Lemma 3.3 gets fixed the result would be a significant advance. But the current version cannot be accepted as-is.\n\nMy recommendation: send it to review, with clear instructions that the referee should focus on Lemma 3.3. It's too interesting to desk reject, but the gap is real and must be closed.","headline":"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.","tokens_in":35443,"tokens_out":12550,"would_cite":false,"duration_ms":138529,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","62L05","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["bandit convex optimization","minimax regret lower bound","convex bandits","regret separation","Fisher information","adaptive sample complexity","softmax tube construction","anticoncentration"],"falsifier":"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.","tokens_in":34355,"feed_emoji":"🎯","tokens_out":6451,"duration_ms":70808,"temperature":0.7,"pith_summary":"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.","feed_headline":"Convex bandits need d^5/4√T regret","feed_subtitle":"New lower bound beats the classical d√T rate; learning a hidden map before the target costs extra samples.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Hidden curvature forces d^5/4√T regret in convex bandits","Convex bandit lower bound jumps past d√T","Tube-dependent learning: convex bandits hit d^5/4√T","First super-linear regret bound for convex bandits","Curved maps raise convex bandit regret to d^5/4√T"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Hidden curvature forces d^5/4√T regret in convex bandits","Convex bandit lower bound jumps past d√T","Tube-dependent learning: convex bandits hit d^5/4√T","First super-linear regret bound for convex bandits","Curved maps raise convex bandit regret to d^5/4√T"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000926,"raw_usage":{"total_tokens":3954,"prompt_tokens":1044,"completion_tokens":2910,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":788,"completion_tokens_details":{"reasoning_tokens":2818}},"tokens_in":788,"tokens_out":2910,"duration_ms":23924,"temperature":1.0,"reasoning_tokens":2818,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T14:49:09.316494+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}