📊 statistics

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

This paper establishes the first nontrivial minimax regret lower bound of $\widetilde{\Omega}(d^{5/4}\sqrt{T})$ for stochastic bandit convex optimization of 1-Lipschitz functions, proving that the problem is fundamentally harder than linear bandits by constructing a hard class of functions where learning an unknown linear transformation and a target vector requires a difficult tradeoff between exploration and information gathering.

Original authors: Nived Rajaraman

Published 2026-07-22

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Nived Rajaraman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a high-stakes game of "Guess the Secret" with a computer. You are trying to find the perfect spot in a vast, multi-dimensional landscape to minimize a hidden score. Every time you pick a spot, the computer tells you your score, but with a twist: it adds a little bit of static noise, like a radio tuned slightly off-station. This is the world of stochastic bandit convex optimization. It's a fundamental problem in machine learning where an algorithm must learn to make the best decisions by trial and error, without ever seeing the full map of the terrain.

For years, researchers believed that the difficulty of this game was mostly about how many dimensions the landscape had. They thought that if you had a linear relationship between your actions and the score (like a straight line), the game was hard, but if the relationship was curved (convex), it was only slightly harder. The prevailing wisdom was that the number of guesses needed to win grew at a rate proportional to the number of dimensions multiplied by the square root of the total time you have to play. It was a comfortable, predictable rhythm. But what if the landscape wasn't just a simple curve? What if it had a hidden, tricky geometry that made it much, much harder to navigate than anyone suspected?

This paper, titled The Price of Hidden Curvature, steps into that game and shatters the old rhythm. The authors, Nived Rajaraman (who collaborated with an advanced AI model to refine the proof), have constructed a specific, tricky type of curved landscape that forces the learner to work significantly harder than the old rules predicted. They prove that for certain 1-Lipschitz convex functions (functions that don't change too wildly), the number of guesses required to find a near-perfect solution grows much faster than previously thought. Specifically, they show a lower bound of roughly $d^{5/4}\sqrt{T}$ , where $d$ is the number of dimensions and $T$ is the number of rounds. This is a strict improvement over the previous best guess of $d\sqrt{T}$ , proving that stochastic bandit convex optimization is fundamentally harder than its linear cousin.

The Mystery of the Invisible Tube

To understand why this is so hard, imagine the landscape isn't a smooth hill, but a giant, multi-dimensional room filled with a specific kind of trap. The authors designed a "hard class" of functions that look like a soft maximum of two things: a "tube" and a "distance function."

Think of the tube as a narrow, invisible hallway floating in the middle of the room. This hallway is determined by a secret, hidden transformation (let's call it $W^*$ ) that twists and turns the space. To get a low score, you must walk inside this hallway. If you step even a tiny bit outside, the score explodes, and you get no useful information about where the true target is.

The target (let's call it $u^*$ ) is a specific point inside this hallway that you need to find. Here's the catch: you don't know where the hallway is because you don't know the secret twist $W^*$ . It's like trying to find a specific room in a maze, but the maze itself is constantly shifting shape based on a secret code you haven't cracked yet.

The Two-Step Dance

The learner is stuck in a terrible dilemma, a "tug-of-war" between two tasks:

Explore the Tube: You have to guess the shape of the hallway ( $W^*$ ) just to know where to walk. But to guess the shape, you need to take steps that might land you outside the hallway, where you get no information.
Find the Target: Once you are inside the hallway, you can finally start learning where the target $u^*$ is. But you can't get inside the hallway until you know where it is.

The paper shows that this trade-off is incredibly expensive. To learn the shape of the hallway well enough to enter it, and then to find the target inside it, you need a massive number of guesses. The authors prove that for every dimension you add, the cost doesn't just go up linearly; it explodes.

The Proof: A Game of Information

The authors didn't just guess this; they built a mathematical fortress to prove it. They used a "Gaussian prior," which is essentially a way of saying, "Let's assume the secret code $W^*$ and the target $u^*$ are chosen randomly from a specific distribution."

They then analyzed the "Fisher information," which is a fancy way of measuring how much a single guess tells you about the hidden secrets. They showed that:

To learn the target $u^*$ , you need to gather a lot of information in many different directions.
But you can only gather information in a direction if you are already inside the tube for that direction.
Getting inside the tube requires learning the secret code $W^*$ , which is expensive.

By balancing these costs, they derived a formula showing that the total number of guesses needed to find a good solution scales as $d^{5/2}/\epsilon^2$ (where $\epsilon$ is how close you want to get to the perfect answer). When you translate this back into the "regret" (the total score you lose by not playing perfectly), it becomes $d^{5/4}\sqrt{T}$ .

Why This Matters

This result is a big deal because it separates two worlds that were thought to be similar. Before this, people thought that if you could solve the linear version of the game (where the landscape is flat), you could solve the curved version with only a small penalty. This paper says: No. The curvature hides a "tube" that acts as a gatekeeper. You can't just walk through; you have to solve a puzzle to open the door first.

The authors also checked if their construction was the best possible. They showed that a clever algorithm can solve this specific type of problem in roughly the same number of steps, meaning their lower bound is tight for this specific setup. They even extended the proof to show that this difficulty holds even if you aren't confined to a ball and can walk anywhere in infinite space.

In short, the paper reveals that the "hidden curvature" of these optimization problems comes with a heavy price tag. The more dimensions you have, the more you pay, and the price is higher than anyone expected. It's a reminder that in the world of machine learning, sometimes the most dangerous obstacles aren't the steep cliffs, but the invisible, narrow hallways you can't see until you're already lost.

Technical Summary: The Price of Hidden Curvature

Problem Statement

This paper addresses the fundamental limits of stochastic bandit convex optimization (BCO). In this setting, a learner seeks to minimize an unknown convex function $f: \mathcal{A} \to \mathbb{R}$ over a convex action space $\mathcal{A} \subseteq \mathbb{R}^d$ by sequentially choosing actions $a_t$ and receiving noisy observations $r_t = f(a_t) + Z_t$ , where $Z_t$ is i.i.d. Gaussian noise. The performance metric is the minimax expected regret, defined as the worst-case difference between the cumulative loss of the learner and the optimal loss over $T$ rounds.

Prior to this work, the strongest known dimension-dependent lower bound for general Lipschitz convex functions was $\tilde{\Omega}(d\sqrt{T})$ , inherited from linear bandits. This suggested that convex bandits might not be fundamentally harder than linear bandits. The paper investigates whether this intuition holds for the class of 1-Lipschitz convex functions on the Euclidean ball $\mathcal{A} = B^d_2$ and the unconstrained space $\mathcal{A} = \mathbb{R}^d$ .

Methodology and Construction

The authors construct a "hard" class of convex functions designed to force a tradeoff between learning a hidden geometric structure and estimating a target parameter. The construction operates in dimension $2d$ , splitting the action $a = (a_1, a_2) \in \mathbb{R}^d \times \mathbb{R}^d$ .

The Hard Function Class

The ground-truth function $f_{\theta^*}$ is parameterized by a hidden linear transformation $W^* \in \mathbb{R}^{d \times d}$ and a target vector $u^* \in \mathbb{R}^d$ . The function is defined as a scaled soft-maximum of two branches:

The Tube Branch: A squared distance term $\frac{1}{r} \| W^* a_1 - \frac{r}{8\varepsilon} a_2 \|^2$ . This term is small only when $a_2 \approx \frac{8\varepsilon}{r} W^* a_1$ , defining a narrow "tube" in the action space.
The Target Branch: A squared distance term $\frac{1}{2} \| a_1 - u^* \|^2 - \frac{1}{2} \| u^* \|^2$ , which is minimized when $a_1 \approx u^*$ .

The function is formally:
$f_{\theta^*}(a) = \varepsilon \cdot \text{softmax}\left( \frac{1}{r} \left\| W^* a_1 - \frac{r}{8\varepsilon} a_2 \right\|^2, \frac{1}{2} \| a_1 - u^* \|^2 - \frac{1}{2} \| u^* \|^2 \right)$

The Core Difficulty

To achieve low regret, the learner must find an action where both branches are small. This requires:

Locating $u^*$ (the target).
Satisfying the tube constraint $a_2 \approx \frac{8\varepsilon}{r} W^* a_1$ .

Crucially, the tube branch dominates the function value unless the learner's action lies within the tube. If the learner chooses an action outside the tube, the observation provides no information about $u^*$ , regardless of how close $a_1$ is to $u^*$ . Since $W^*$ is unknown, the learner cannot deterministically enter the tube. They must either:

Explore $W^*$ : Spend samples to learn the directions of $W^*$ to predict the tube location.
Guess the Tube: Attempt to enter the tube by guessing $W^* a_1$ , which is highly improbable without prior knowledge.

This creates a tension: learning $u^*$ requires being in the tube, but finding the tube requires learning $W^*$ .

Analytical Framework

The proof utilizes a Bayesian framework with a Gaussian prior on $W^*$ and $u^*$ . The analysis relies on two key information-theoretic quantities:

Likelihood Fisher Information for $u^*$ ( $\mathcal{I}^u_n$ ): Measures the information gained about $u^*$ . The paper proves that to estimate $u^*$ to constant error, $\mathcal{I}^u_n$ must have many large eigenvalues.
Posterior Fisher Information for $W^*$ ( $K_t$ ): Measures the information gained about the hidden map $W^*$ .

The central technical contribution is Lemma 2.2, which establishes a "tension" between these two matrices. It shows that the cost of acquiring enough Fisher information about $u^*$ (to get large eigenvalues in $\mathcal{I}^u_n$ ) is bounded by the cost of learning $W^*$ . Specifically, the trace of the inverse of the Fisher information envelope for $W^*$ , weighted by the information gained about $u^*$ , is bounded. This forces the learner to spend a significant number of samples learning $W^*$ before they can effectively learn $u^*$ .

Key Results

Estimation Lower Bound

Theorem 1.1 establishes a lower bound on the sample complexity required to find an $\varepsilon$ -optimal action. For any adaptive learner making $n$ queries on the Euclidean ball $B^d_2$ , if $n < c_2 \frac{d^{5/2}}{\varepsilon^2 \log(ed)}$ , there exists a function in the hard class such that the expected suboptimality is at least $c_0 \varepsilon$ .

Regret Lower Bound

Corollary 1.2 translates the estimation bound into a regret lower bound. For $T \geq C d^3 / \log(ed)$ , the minimax regret satisfies:
$\mathfrak{R}^*_T(d; B^d_2) \geq c d^{5/4} \sqrt{\frac{T}{\log(ed)}}$
This result is extended to the unconstrained setting $\mathcal{A} = \mathbb{R}^d$ in Theorem 5.2 via a smoothed conic extension that preserves the hardness properties outside the unit ball.

Tightness

Theorem 5.1 presents a two-stage Bayesian algorithm (E2B) that achieves an upper bound of $\tilde{O}(d^{5/2}/\varepsilon^2)$ for the specific Gaussian prior used in the lower bound. This demonstrates that the lower bound is tight for the constructed prior, confirming that the $d^{5/4}$ factor is not an artifact of the proof technique but a fundamental property of this class of functions.

Significance and Claims

The paper claims to establish the first nontrivial regret lower bound for stochastic bandit convex optimization that grows strictly faster than the linear bandit bound of $\tilde{\Omega}(d\sqrt{T})$ .

Separation of Convex and Linear Bandits: The result proves that stochastic bandit convex optimization is fundamentally harder than linear bandits over the Euclidean ball. While linear bandits scale as $d\sqrt{T}$ , the constructed convex instances scale as $d^{5/4}\sqrt{T}$ .
Role of Hidden Curvature: The hardness arises from "hidden curvature"—the need to learn a hidden linear transformation ( $W^*$ ) that dictates the geometry of the information-revealing region (the tube). This structure prevents the learner from using standard linearization arguments that work for smooth or linear functions.
Limitations of Current Upper Bounds: The paper notes that the best known upper bounds are $\tilde{O}(d^{3/2}\sqrt{T})$ . The gap between the lower bound ( $d^{5/4}$ ) and the upper bound ( $d^{3/2}$ ) remains open. The authors conjecture that the true minimax rate is $\tilde{\Theta}(d^{3/2}\sqrt{T})$ , suggesting that the current lower bound construction, while optimal for its specific prior, may not capture the full difficulty of the general problem, or that tighter upper bounds are needed.

The authors explicitly state that their construction relies on a specific tradeoff between learning the nuisance parameter $W^*$ and the target $u^*$ , and that simple extensions (like adding more tubes or changing the width) do not immediately yield stronger exponents, highlighting the specific geometric nature of the hardness.