🤖 machine learning

Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback

This paper resolves open questions regarding adversarial online learning with hidden-convex losses by proving that Online Gradient Descent achieves the optimal $\mathcal{O}(\sqrt{T})$ regret under a necessary-and-sufficient Hessian compatibility condition, while also establishing a matching lower bound for its failure and extending these results to bandit feedback settings.

Original authors: Anas Barakat, Andreas Kontogiannis, Vasilis Pollatos, Ioannis Panageas, Antonios Varvitsiotis

Published 2026-05-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anas Barakat, Andreas Kontogiannis, Vasilis Pollatos, Ioannis Panageas, Antonios Varvitsiotis

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 video game where the rules change every second, and you have to make a move, get a score, and then immediately make another move. Your goal isn't just to survive, but to perform almost as well as the "perfect player" who knew all the future rules in advance. In the world of computer science, this is called Online Learning.

Usually, this game is easiest when the "scoring rules" (called loss functions) are simple and bowl-shaped (convex). In that case, a simple strategy called Online Gradient Descent (OGD)—which is like taking a small step downhill every time you get a bad score—guarantees you won't fall too far behind the perfect player.

However, the real world is messy. Sometimes the scoring rules are twisted, bumpy, and full of traps (non-convex). In these situations, the simple "step downhill" strategy often fails, and you might get stuck in a local hole, performing terribly compared to the perfect player.

The Secret Map: Hidden Convexity

This paper focuses on a special type of tricky game called Hidden-Convex Loss. Imagine the game board looks like a jagged, confusing mountain range to you. But, there is a secret map (a mathematical transformation) that, if you could see it, would reveal that the mountain is actually just a smooth, gentle hill.

The problem? You don't have the map. You only see the jagged mountains. The question the authors asked is: Can the simple "step downhill" strategy still work if the game is secretly a smooth hill, even though you can't see the smoothness?

The Big Discovery: Yes, It Works!

Previous research suggested that if you use the simple strategy on these hidden-smooth games, you would eventually fall behind the perfect player at a rate of roughly $T^{2/3}$ (where $T$ is the number of rounds). This is okay, but not great.

The authors' main breakthrough is proving that the simple strategy actually performs much better: it achieves the optimal rate of $\sqrt{T}$ .

Think of it this way:

Old belief: If you try to walk down a jagged mountain that is secretly a smooth hill, you will stumble a bit, and your total stumbling distance will grow at a moderate pace.
New finding: The authors proved that if the mountain has the right "hidden geometry," your stumbling is so minimal that you actually walk down as efficiently as if you were on a perfectly smooth hill from the start. You are essentially "tricking" the jagged mountain into behaving like a smooth one.

The "Hessian Compatibility" Rule: The Shape of the Map

The paper also answers a crucial "why" question. Why does this work for some hidden hills but not others?

The authors discovered a specific geometric rule they call Hessian Compatibility.

The Analogy: Imagine the secret map is a piece of fabric. For the simple strategy to work, the way the fabric stretches and twists (the geometry) must be perfectly consistent with the way the "downhill" steps are calculated.
The Result: The authors found that if this geometric consistency exists, the strategy works perfectly. But, they also proved that if this consistency is missing, the strategy fails miserably. In fact, they constructed a specific "trick" game where, without this geometric rule, the simple strategy gets stuck in a loop, and your performance gets worse and worse linearly (like walking in circles forever).

They also improved the definition of this rule. Previous work said the map had to be very rigid (like a grid). The authors showed the map can be much more flexible and twisted, as long as it follows this deeper geometric rule.

The Blindfolded Player: Bandit Feedback

Finally, the paper tackles an even harder version of the game: Bandit Feedback.

Full Information: You see the score and the exact direction of the slope (gradient).
Bandit Feedback: You are blindfolded. You only see your final score for the move you made. You don't know which way is "down."

In the past, for these blindfolded games, the best you could hope for was a performance rate of $T^{3/4}$ . The authors showed that even in this blindfolded scenario, if the game has the "hidden convex" structure, the simple strategy (using a clever guessing technique to estimate the slope) still achieves that same $T^{3/4}$ rate. This matches the best possible performance for blindfolded players on smooth hills.

Summary

In short, this paper proves that:

Simple is powerful: Even when a problem looks complicated and non-convex, if it has a "hidden" smooth structure, a simple algorithm can solve it as efficiently as if it were truly smooth.
Geometry matters: This only works if the hidden structure follows a specific geometric rule (Hessian compatibility). If it doesn't, the simple algorithm will fail.
Blindfolded success: Even when you only get partial information (just a score), this hidden structure allows you to perform as well as the best possible blindfolded player.

The authors didn't just say "it works"; they provided the exact mathematical blueprint for when it works and proved that if the blueprint is missing, the strategy is doomed to fail.

Technical Summary: Online Learning on Hidden-Convex Losses via Algorithmic Equivalence

Problem Statement

The paper addresses the problem of adversarial online learning with hidden-convex losses. In this setting, a learner faces a sequence of loss functions $(\ell_t)$ that are nonconvex in the algorithm's native parameter space $X$ but become convex after a specific, unknown nonlinear reparameterization $q: X \to Y$ . The goal is to minimize external regret against the best fixed decision in hindsight:
$R_T = \sum_{t=1}^T \ell_t(x_t) - \min_{x \in X} \sum_{t=1}^T \ell_t(x)$
where $\ell_t(x) = h_t(q(x))$ and $h_t$ is convex.

While Online Gradient Descent (OGD) achieves the optimal $\Theta(\sqrt{T})$ regret for standard Online Convex Optimization (OCO), the behavior of OGD on nonconvex losses is generally poor. Previous work by Ghai et al. [2022] established that under specific geometric and smoothness assumptions, OGD on hidden-convex losses approximately simulates Online Mirror Descent (OMD) on the convex reparameterized losses, yielding a suboptimal $O(T^{2/3})$ regret bound. The central open questions addressed in this work are:

Can the optimal $\Theta(\sqrt{T})$ regret rate be recovered for hidden-convex losses under exact gradient feedback?
What are the precise geometric conditions required for this recovery, and are they necessary?
Does this framework extend to the bandit feedback setting (where only a single loss value is observed per round)?

Methodology

The core methodology relies on a refined algorithmic equivalence argument between OGD in the original nonconvex space and OMD in the hidden convex space.

1. Algorithmic Equivalence and Discretization Error

The authors analyze the relationship between the OGD iterates $(x_t)$ in $X$ and the OMD iterates $(y_t)$ in $Y$ (where $y_t = q(x_t)$ ).

Continuous vs. Discrete: In continuous time, gradient flow and mirror flow coincide exactly under the reparameterization if the Hessian of the regularizer $R$ matches the metric induced by the Jacobian of $q$ . In discrete time, this equivalence is broken by discretization error.
Key Technical Improvement: Ghai et al. [2022] bounded the distance between one-step OGD and OMD iterates as $O(\eta^{3/2})$ . This paper introduces a sharper analysis proving that the distance is actually $O(\eta^2)$ .
Mechanism: The proof localizes both updates within an $O(\eta)$ neighborhood. It expresses both updates as minimizers of the same strongly convex quadratic model $\Phi_t(y)$ , perturbed by different higher-order Taylor remainders ( $\varepsilon^{OGD}_t$ and $\varepsilon^{OMD}_t$ ). By comparing the first-order optimality conditions directly (rather than bounding the difference in objective values), the authors show that the difference in minimizers is bounded by $\eta$ times the difference in the gradients of the error terms, yielding the $O(\eta^2)$ bound.

2. Geometric Conditions

The analysis relies on Assumption 1 (Hessian-compatible reparameterization), which requires the existence of a strictly convex regularizer $R$ such that:
$[\nabla^2 R(z)]^{-1} = J_q(x) J_q(x)^\top$
where $z = q(x)$ . This condition ensures that the Euclidean metric in the original space corresponds to the Bregman metric induced by $R$ in the hidden space.

3. Lower Bound Construction

To demonstrate the necessity of the Hessian compatibility condition, the authors construct a counter-example where the condition fails. They define a smooth reparameterization where the induced metric is not a Hessian field (i.e., the associated vector field is not conservative). By designing an adversarial sequence of linear losses, they force the OGD iterates to cycle around a loop with non-zero circulation in the hidden space, accumulating linear regret $\Omega(T)$ .

4. Bandit Extension

For the bandit setting, the paper adapts the Bandit OGD (BOGD) algorithm with spherical smoothing (Flaxman et al. [2005]). The analysis decomposes the expected regret into four components:

Perturbed OMD regret (using a "ghost" OMD iterate).
Domain shrinkage error (due to restricting the domain to allow perturbations).
Gradient estimation bias (arising from the one-point estimator).
Smoothing error (loss evaluated at perturbed points).
The $O(\eta^2)$ coupling result is extended to the bandit setting to control the perturbed OMD term.

Key Contributions and Results

1. Optimal Regret under Exact Gradient Feedback

Result: Under the same geometric and smoothness assumptions as Ghai et al. [2022], OGD achieves $O(\sqrt{T})$ regret for hidden-convex losses.
Significance: This improves upon the previous $O(T^{2/3})$ bound and matches the optimal worst-case rate for adversarial OCO. The improvement stems directly from the tighter $O(\eta^2)$ discretization error bound in the algorithmic equivalence.

2. Refined Geometric Conditions

Result: The paper relaxes the "diagonal-Jacobian" sufficient condition used in prior work. It provides necessary and sufficient conditions for Hessian compatibility (Proposition 1), based on the cross-partial derivatives of the inverse metric field.
Significance: This expands the class of admissible reparameterizations (e.g., affine mixtures of separable parameterizations and rank-one nonlinear mixings) that guarantee sublinear regret.

3. Geometric Barrier (Necessity)

Result: The paper proves that Hessian compatibility is essential for OGD. If the condition fails, there exists a smooth reparameterization and an adversarial sequence where OGD suffers $\Omega(T)$ linear regret (Theorem 2).
Significance: This establishes that the geometric structure is not merely a technical artifact of the proof but a fundamental requirement for the success of first-order methods in this setting.

4. Bandit Feedback Guarantees

Result: In the one-point bandit setting against oblivious adversaries, the proposed Bandit OGD achieves an expected regret of $O(T^{3/4})$ (Theorem 3).
Significance: This matches the best-known rate for bandit OGD on standard convex losses, demonstrating that the hidden-convex structure does not incur an additional penalty in the bandit setting compared to the convex case.

Significance and Claims

The paper claims to resolve open questions regarding the optimality of OGD in hidden-convex online learning. By sharpening the algorithmic equivalence analysis, it demonstrates that the slower $O(T^{2/3})$ rate observed in prior work was an artifact of the analysis rather than an inherent limitation of the problem class.

The work establishes that:

Optimality is recoverable: Simple first-order methods (OGD) can achieve optimal regret rates for structured nonconvex problems if the hidden geometry satisfies Hessian compatibility.
Geometry is critical: The Hessian compatibility condition is a sharp boundary; without it, OGD fails completely (linear regret).
Robustness: The framework extends to bandit feedback, maintaining classical rates despite the additional challenges of gradient estimation and domain shrinkage.

The authors note that while their lower bound rules out sublinear regret for OGD without Hessian compatibility, it remains an open question whether other online algorithms might achieve sublinear regret in the absence of this geometric condition. Similarly, while the bandit rate matches the convex case, achieving sharper rates or high-probability bounds remains a direction for future work.