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

2026-07-21 · Source: Takara TLDR - Daily AI Papers · Field: Technology & Digital — Artificial Intelligence & Machine Learning · Depth: Expert, quick

Summary

Nived Rajaraman establishes a ÕÎ(d^{5/4}√T) lower bound on the minimax expected regret for stochastic bandit convex optimization of 1-Lipschitz functions on the Euclidean ball. This represents the first nontrivial regret lower bound exceeding d√T for this problem, demonstrating that stochastic bandit convex optimization is fundamentally harder than linear bandits. The constructed hard class of convex functions in dimension 2d combines a scaled soft maximum of a "tube" (parameterized by ε,r) and a squared distance function, involving unknown linear transformation W^★ ∈ ℝ^{d × d} and vector u^★ ∈ ℝ^{d}. Observations are only informative when actions are near the W^★-determined tube, forcing the learner to either locate this tube or learn useful directions of W^★. This leads to a sample complexity lower bound of ÕÎ(d^{5/2}/ε^2) for finding an ε-optimal action.

Key takeaway

For AI Scientists developing or evaluating bandit convex optimization algorithms, this new ÕÎ(d^{5/4}√T) lower bound indicates that achieving optimal performance requires overcoming a higher inherent complexity than previously understood. You should account for this increased difficulty, particularly in high-dimensional settings, by focusing research on methods that efficiently discover and exploit localized informative regions. This implies a need for more sophisticated exploration strategies beyond those effective for linear bandits.

Key insights

Stochastic bandit convex optimization is fundamentally harder than linear bandits, with a new ÕÎ(d^{5/4}√T) regret lower bound.

Principles

• Stochastic bandit convex optimization is harder than linear bandits.
• Informative observations are localized to specific, unknown regions.

Method

The regret analysis bounds the posterior spread of Fisher information matrices obtained under an adaptive sequence of actions.

In practice

• Consider the ÕÎ(d^{5/4}√T) bound when designing algorithms.
• Focus on strategies for discovering informative regions.

Topics

• Bandit Convex Optimization
• Regret Lower Bound
• Stochastic Optimization
• Lipschitz Functions
• Fisher Information
• Sample Complexity

Best for: Research Scientist, AI Scientist

Related on AIssential

• A Convex Framework for Confounding Robust Inference — A convex programming framework provides a sharp lower bound for policy evaluation in offline contextual bandits, improving robustness against unobserved confounders.
• Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation — The paper provides information-theoretic lower bounds for bit-constrained stochastic optimization, linking it to compressed Gaussian mean estimation.
• Stochastic Linear Contextual Bandits with Bounded Noise: A Set-Membership Approach — Explicitly leveraging bounded reward noise in contextual bandits can yield logarithmic regret, significantly outperforming square-root bounds.
• Revisiting Decentralized Online Convex Optimization with Compressed Communication — FTRL-type algorithms can significantly improve decentralized online convex optimization with compressed communication.
• Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets — Non-monotone DR-submodular maximization over down-closed sets is 1/e-linearizable, enabling online linear optimization reduction.
• Memory-Computation Tradeoffs in Semi Amortized Parametric Optimization — Offline memory requirements for amortized optimization are quantifiable, driven by online convergence and solution map sensitivity.

See Counsel's argued verdicts on the open AI decisions leaders are weighing →

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Takara TLDR - Daily AI Papers.