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

arXiv: https://arxiv.org/abs/2605.26373 · HTML: https://mlsanity.com/paper/2605.26373/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 44 references that are in the map.
- First posted on arXiv 25 May 2026.

## Builds on (most cited first, 30 of 30)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [Beyond Convexity: Stochastic Quasi-Convex Optimization](https://mlsanity.com/paper/1507.02030/) (2015)
- [Robust Bi-Tempered Logistic Loss Based on Bregman Divergences](https://mlsanity.com/paper/1906.03361/) (2019)
- [Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descent](https://mlsanity.com/paper/2207.04036/) (2022)
- [Online Non-Convex Learning: Following the Perturbed Leader is Optimal](https://mlsanity.com/paper/1903.08110/) (2019)
- [The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutions](https://mlsanity.com/paper/2006.05900/) (2020)
- [Learning in Non-convex Games with an Optimization Oracle](https://mlsanity.com/paper/1810.07362/) (2018)
- [The effect of smooth parametrizations on nonconvex optimization landscapes](https://mlsanity.com/paper/2207.03512/) (2022)
- [Bandit Convex Optimisation](https://mlsanity.com/paper/2402.06535/) (2024)
- [Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space](https://mlsanity.com/paper/2306.01854/) (2023)
- [Poincar'e Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games](https://mlsanity.com/paper/1910.13010/) (2019)
- [Stochastic Optimization under Hidden Convexity](https://mlsanity.com/paper/2401.00108/) (2023)
- [Non-convex online learning via algorithmic equivalence](https://mlsanity.com/paper/2205.15235/) (2022)
- [Online non-convex optimization with imperfect feedback](https://mlsanity.com/paper/2010.08496/) (2020)
- [The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Models](https://mlsanity.com/paper/2312.12657/) (2023)
- [On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learning](https://mlsanity.com/paper/2410.04108/) (2024)
- [Efficient Algorithms for A Class of Stochastic Hidden Convex Optimization and Its Applications in Network Revenue Management](https://mlsanity.com/paper/2205.01774/) (2022)
- [Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem](https://mlsanity.com/paper/2410.05673/) (2024)
- [Exploiting hidden structures in non-convex games for convergence to Nash equilibrium](https://mlsanity.com/paper/2312.16609/) (2023)
- [Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2410.16600/) (2024)
- [Solving Zero-Sum Convex Markov Games](https://mlsanity.com/paper/2506.16120/) (2025)
- [Global Solutions to Non-Convex Functional Constrained Problems with Hidden Convexity](https://mlsanity.com/paper/2511.10626/) (2025)
- [Solving Hidden Monotone Variational Inequalities with Surrogate Losses](https://mlsanity.com/paper/2411.05228/) (2024)
- [Solving Neural Min-Max Games: The Role of Architecture, Initialization & Dynamics](https://mlsanity.com/paper/2512.00389/) (2025)
- [Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibria](https://mlsanity.com/paper/2602.12181/) (2026)
- [Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspective](https://mlsanity.com/paper/2603.23831/) (2026)

## Abstract (arXiv)

We study adversarial online learning with hidden-convex losses, i.e., nonconvex losses that become convex after a nonlinear reparameterization. Ghai, Lu and Hazan (2022) proved that, under geometric and smoothness assumptions, online gradient descent (OGD) on such nonconvex losses approximately simulates online mirror descent (OMD) on the underlying convex losses with a suitable regularizer, yielding O(T2/3) regret. They left open whether the optimal Theta(√T) regret from online convex optimization can be recovered in this hidden-convex setting. We answer this question affirmatively. More specifically, via a sharper discrete-time algorithmic equivalence argument, we prove that OGD achieves O(√T) regret under the same assumptions, matching the optimal worst-case rate for adversarial online convex optimization. We also address another open question of Ghai, Lu and Hazan (2022) by clarifying the geometry required for this algorithmic equivalence. We replace the diagonal-Jacobian sufficient condition with a necessary-and-sufficient Hessian compatibility condition, thereby expanding the class of admissible reparameterizations. We complement our tight regret bound with a lower bound showing that the Hessian compatibility assumption is essential for OGD; when it fails, we construct a smooth reparameterization and an adversarial sequence of hidden-convex losses for which OGD suffers Omega(T) regret. Finally, we extend our analysis to one-point bandit feedback and prove a O(T3/4) expected regret bound for bandit OGD with spherical smoothing, matching its classical rate on convex losses.