Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback
Authors: Anas Barakat, Andreas Kontogiannis, Vasilis Pollatos, Ioannis Panageas, Antonios Varvitsiotis
Organizations: Singapore University of Technology and Design · National Technical University of Athens · Archimedes, Athena Research Center, Greece · National and Kapodistrian University of Athens · University of California, Irvine · National University of Singapore, Centre for Quantum Technologies
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 Θ(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 Ω(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.
This paper introduces a new problem-dependent regret measure for online convex optimization with smooth losses. The notion, which we call the G⋆ regret, depends on the cumulative squared gradient norm evaluated at the decision in hindsight. We show that the G⋆ regret strictly refines the existing L⋆ (small loss) regret, and that it can be arbitrarily sharper when the losses have vanishing curvature around the hindsight decision. We establish upper and lower bounds on the G⋆ regret and extend our results to dynamic regret and bandit settings. As a byproduct, we refine the existing convergence analysis of stochastic optimization algorithms in the interpolation regime. Some experiments validate our theoretical findings.
We study constrained online convex optimization with adversarial time-varying constraints. At each round the learner acts before observing the loss and constraint, and is compared with the best fixed action satisfying all constraints in hindsight. The goal is to obtain minimax-optimal regret while controlling cumulative constraint violation (CCV). Prior algorithms achieved O(logT) regret with O(TlogT) CCV for strongly convex losses, and O(T) regret with O(TlogT) CCV for convex losses. We propose NP-OGD, an iterated nested-projection algorithm. For strongly convex losses it achieves O(logT) regret and O(logT) CCV; for convex losses it achieves O(T) regret and O(T) CCV. The analysis relies on a geometric movement bound: after lifting the nested projected-gradient trajectory to one higher dimension, the lifted path is self-contracted under a nonstandard norm, so a finite-length theorem for self-contracted curves controls the total projection movement. We also prove complementary lower bounds using layered sphere packings. For strongly convex losses, any online algorithm with polynomially sublinear regret can incur CCV at least Ω((logT)(d−1)/(d+1)/loglogT). For convex losses, we prove CCV lower bounds Ω(T(d−1)/(2(d+3))) for weakly adaptive algorithms and Ω(T(d−1)/(2d)) for NP-OGD. Finally, for the constrained experts special case over N experts, an active Hedge algorithm attains O(TlogN) regret and O(N) CCV, with a matching minimax CCV lower bound for sufficiently large horizons.
We study high-probability regret bounds for online convex optimization (OCO) with strongly convex losses and establish three results that resolve open questions at the intersection of noise adaptivity, feedback structure, and constraint satisfaction. For the full-information setting with sub-Gaussian stochastic gradients, we prove a noise-adaptive high-probability regret bound in which the martingale deviation term scales with the noise level σ rather than the gradient bound G, yielding a multiplicative improvement of G/σ over the classical Azuma-Hoeffding baseline. Our analysis introduces an exponential supermartingale argument that bypasses the bounded-difference requirement of Freedman's inequality, enabling direct treatment of unbounded sub-Gaussian noise without truncation artifacts. For bandit feedback, we prove a minimax lower bound: the high-probability regret scales linearly in log(1/δ), in contrast to the log(1/δ) confidence cost under full information. This constitutes a formal separation in the confidence cost of strongly convex OCO across feedback models. Regarding constrained OCO with stochastic constraints satisfying a Slater condition, we provide simultaneous high-probability guarantees for both cumulative regret and long-run constraint violation, achieving O(Tlog(m/δ)) regret and O(T/(ζδ)+mTlog(m/δ)) violation. Synthetic experiments corroborate all theoretical predictions.