Research map / Bandits and online learning / Online convex optimization and games
From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Makes FTPL curvature-adaptive for non-convex Lipschitz online losses by using a time-varying perturbation scale chosen via a follow-the-leader rule on past curvatures, achieving O(sqrt T) worst-case and O(log T) under linear cumulative curvature, with matching lower bounds.
Problem
Online optimization with non-convex Lipschitz losses where regret should be O(sqrt T) in the worst case but improve (e.g., O(log T)) when cumulative curvature grows; standard FTPL uses a fixed perturbation scale and does not exploit curvature.
Approach
Replace FTPL's fixed perturbation scale with a non-decreasing time-varying scale rho_t set by a follow-the-leader rule on observed cumulative strong convexity S_i; stability is bounded by the minimum of a non-convex bound and a strongly convex bound, and the scale-selection is a meta online problem that FTL solves with constant competitive ratio.
Key results
- Adaptive FTPL matches O(sqrt T) worst-case regret and, under linear cumulative curvature (S_t >= t^gamma with gamma=1), achieves O(log T) regret; the schedule is provably constant-competitive with the best offline choice up to constants.
- A lower bound Omega(opt_T^0(0)) holds already for one-dimensional convex losses for any prescribed cumulative-curvature sequence, so the minimax regret is Theta(opt_T^0(0)).
- In synthetic quadratic experiments with growing curvature, AdaFTPL's regret grows like FTL (~log T) when p+=0.75 or 1, while FTPL grows like sqrt(T).
Surprising findings
- Standard FTRL-style regularization may not stabilize minimizers of non-convex objectives, which is why FTPL is used instead.
Limitations
- Requires oracle with approximation error alpha and beta; O(log T) needs alpha, beta = O(1/T) (accurate oracle calls).
- Lower bounds are for prescribed cumulative-curvature sequences and d=1; general d tightness not shown.
- Experiments are limited to synthetic quadratic losses with d=10.
Experimental setup
Benchmarks: synthetic quadratic online sequences
Metrics: cumulative regret vs horizon T
Baselines: FTPL with fixed scale rho=sqrt(T) FTL
Builds on: Follow-the-Perturbed-Leader adaptive FTRL / online gradient descent with curvature adaptivity (Bartlett et a oracle-efficient FTPL for non-convex losses (Suggala & Netrapalli-style)
Closest papers by meaning
- Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets (NeurIPS 2024 · similarity 0.94)
- Exploiting Curvature in Online Convex Optimization with Delayed Feedback (ICML 2025 · similarity 0.92)
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.91)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.90)
- Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability (ICML 2025 · similarity 0.90)
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.