AI RESEARCH
From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization
arXiv CS.LG
•
ArXi:2606.02948v1 Announce Type: new Curvature adaptivity is a classical theme in online optimization: for convex Lipschitz losses, adaptive methods interpolate between the optimal $O(\sqrt{T})$ regret for general convex losses and $O(\log T)$ regret under strong convexity. Recent work has shown that Follow-the-Perturbed-Leader (FTPL) achieves optimal $O(\sqrt{T})$ regret even for online non-convex Lipschitz losses, assuming access to an approximate offline-optimization oracle, but these guarantees do not exploit curvature.