aiqbench analysis
This research introduces a curvature-adaptive variant of Follow-the-Perturbed-Leader (FTPL) that dynamically adjusts perturbation scales to exploit increasing problem curvature without prior knowledge. The method bridges the gap between worst-case non-convex guarantees and fast convergence rates for strongly convex regimes, achieving optimal regret bounds that match theoretical lower limits. For practitioners in online optimization, this offers a robust algorithmic improvement that automatically accelerates learning as the underlying loss landscape becomes more favorable.
From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization
arXiv:2606.02948v1 Announce Type: new Abstract: 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. We show that FTPL can be made curvature-adaptive in the non-convex setting, without knowing in advance how curvature will accumulate over time. Our algorithm replaces the fixed perturbation scale of standard FTPL with a time-varying scale chosen using only past information. We give a simple follow-the-leader tuning rule for this scale and show that it competes, up to constants, with the best choice in hindsight. The resulting method achieves $O(\sqrt{T})$ regret for arbitrary non-convex Lipschitz losses and improves as cumulative curvature grows; with sufficiently accurate oracle calls, it achieves $O(\log T)$ regret when cumulative curvature grows linearly, which includes the classical strongly convex regime. We complement these upper bounds with matching lower bounds for prescribed cumulative-curvature sequences, already for one-dimensional convex losses, showing that the tradeoff between worst-case non-convex regret and curvature-driven fast rates is intrinsic.
Abstract: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. We show that FTPL can be made curvature-adaptive in the non-convex setting, without knowing in advance how curvature will accumulate over time. Our algorithm replaces the fixed perturbation scale of standard FTPL with a time-varying scale chosen using only past information. We give a simple follow-the-leader tuning rule for this scale and show that it competes, up to constants, with the best choice in hindsight. The resulting method achieves $O(\sqrt{T})$ regret for arbitrary non-convex Lipschitz losses and improves as cumulative curvature grows; with sufficiently accurate oracle calls, it achieves $O(\log T)$ regret when cumulative curvature grows linearly, which includes the classical strongly convex regime. We complement these upper bounds with matching lower bounds for prescribed cumulative-curvature sequences, already for one-dimensional convex losses, showing that the tradeoff between worst-case non-convex regret and curvature-driven fast rates is intrinsic.
Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS)
arXiv:2606.02948 [cs.LG]
(or arXiv:2606.02948v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2606.02948 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 298 words
Related coverage
Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions
arXiv · Jul 23, 2026
Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds
arXiv · Sep 15, 2026
Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets
arXiv · Sep 1, 2026
Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization
arXiv · Jun 9, 2026