mlsanityData to 14 Oct 2026

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

arXiv 2605.26373 ↗First posted 25 May 2026cs.LG math.OC stat.MLcited by 0

Not on the map. Why?

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.

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

30 of 44 references.

References · 30

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  3. 2018Provably Efficient Maximum Entropy Explorationcited by 242
  4. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 111
  5. 2021Reward is enough for convex MDPscited by 84
  6. 2015Beyond Convexity: Stochastic Quasi-Convex Optimizationcited by 76
  7. 2019Robust Bi-Tempered Logistic Loss Based on Bregman Divergencescited by 61
  8. 2022Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descentcited by 39
  9. 2019Online Non-Convex Learning: Following the Perturbed Leader is Optimalcited by 32
  10. 2020The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutionscited by 30
  11. 2018Learning in Non-convex Games with an Optimization Oraclecited by 24
  12. 2022The effect of smooth parametrizations on nonconvex optimization landscapescited by 21
18 more
  1. 2024Bandit Convex Optimisationcited by 19
  2. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  3. 2019Poincar'e Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Gamescited by 15
  4. 2023Stochastic Optimization under Hidden Convexitycited by 12
  5. 2022Non-convex online learning via algorithmic equivalencecited by 11
  6. 2020Online non-convex optimization with imperfect feedbackcited by 10
  7. 2023The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Modelscited by 7
  8. 2024On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learningcited by 6
  9. 2022Efficient Algorithms for A Class of Stochastic Hidden Convex Optimization and Its Applications in Network Revenue Managementcited by 5
  10. 2024Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problemcited by 5
  11. 2023Exploiting hidden structures in non-convex games for convergence to Nash equilibriumcited by 3
  12. 2024Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learningcited by 3
  13. 2025Solving Zero-Sum Convex Markov Gamescited by 2
  14. 2025Global Solutions to Non-Convex Functional Constrained Problems with Hidden Convexitycited by 2
  15. 2024Solving Hidden Monotone Variational Inequalities with Surrogate Lossescited by 1
  16. 2025Solving Neural Min-Max Games: The Role of Architecture, Initialization & Dynamicscited by 1
  17. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  18. 2026Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspectivecited by 1

Built on by

Not cited yet.