Title: Adapting FTPL for Online Optimization: Bridging Non-Convex and Strongly Convex Regimes via Curvature

Abstract:

Curvature adaptivity has long been a central focus in online optimization. For convex, Lipschitz-continuous losses, adaptive techniques are known to interpolate between the optimal $O(\sqrt{T})$ regret typical of general convex problems and the faster $O(\log T)$ regret observed under strong convexity. While recent studies demonstrated that Follow-the-Perturbed-Leader (FTPL) can achieve optimal $O(\sqrt{T})$ regret even for non-convex Lipschitz losses—provided an approximate offline-optimization oracle is available—these prior results failed to leverage curvature information. In this work, we demonstrate that FTPL can be adapted to curvature in non-convex settings without requiring prior knowledge of how curvature will accumulate over time. Our approach substitutes the static perturbation scale of standard FTPL with a dynamic, time-dependent scale determined exclusively by historical data. We propose a straightforward follow-the-leader tuning rule for this scale, proving that it performs competitively, within constant factors, against the best possible choice selected in hindsight. Consequently, the proposed method yields $O(\sqrt{T})$ regret for arbitrary non-convex Lipschitz losses while improving performance as cumulative curvature increases. Specifically, when oracle calls are sufficiently precise and cumulative curvature grows linearly—a condition encompassing the classical strongly convex scenario—the algorithm achieves $O(\log T)$ regret. Furthermore, we establish matching lower bounds for prescribed cumulative-curvature sequences, even in the case of one-dimensional convex losses, thereby demonstrating that the trade-off between worst-case non-convex regret and curvature-dependent fast rates is an inherent property of the problem.

Source: arXiv Generated at: 2026-06-03 00:00:00 UTC