Rajaraman's lower bound proves bandit convex optimization harder than linear bandits
First regret lower bound growing faster than d√T shows hidden curvature costs more.
A new paper by Nived Rajaraman on arXiv (2607.18652) proves that stochastic bandit convex optimization (BCO) is fundamentally more difficult than previously thought. The author establishes a Ω̃(d^{5/4} √T) lower bound on minimax expected regret for 1-Lipschitz convex functions on the Euclidean ball. This is the first lower bound that grows faster than d√T for any regime—a stark contrast to linear bandits where d√T is optimal. The result shows that BCO cannot be reduced to linear bandits without significant extra cost.
The lower bound is achieved through a novel construction in 2d dimensions. Each function is the scaled soft maximum of a "tube" (dependent on an unknown linear transformation W⋆) and a squared distance to an unknown vector u⋆. Observations reveal u⋆ only when the learner's action lies near the tube, creating a tradeoff: either find the tube without knowing W⋆ or spend samples learning W⋆. The regret analysis uses posterior spread of Fisher information matrices under adaptive actions. This yields a sample complexity lower bound of Ω̃(d^{5/2}/ε²) to find an ε-optimal action, translating to the regret bound. The result also extends to unconstrained action spaces.
- Establishes first lower bound of Ω̃(d^{5/4} √T) for stochastic bandit convex optimization, exceeding d√T for linear bandits.
- Uses a hard construction with a hidden tube and squared distance function to force a tradeoff between exploration and exploitation.
- Analysis leverages Fisher information matrices under adaptive actions, yielding a sample complexity lower bound of Ω̃(d^{5/2}/ε²).
Why It Matters
Sets a fundamental lower bound for bandit convex optimization, guiding algorithm design and highlighting the cost of hidden curvature.