Research map / Bandits and online learning / Online convex optimization and games
Online Non-convex Learning in Dynamic Environments
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.
Extends follow-the-perturbed-leader (FTPL) non-convex online learning to dynamic environments, proposing FTPL-D (restarted FTPL), FTPL-D+ (meta-tracked restarts with randomized sampling), and FTPL-A (geometric covering intervals with AdaNormalHedge) for dynamic and strongly adaptive regret.
Problem
Online learning with non-convex losses in dynamic environments, where static regret is inadequate because the comparator shifts over time; the paper targets dynamic regret and strongly adaptive regret with guarantees.
Approach
Restart FTPL periodically (FTPL-D) to get O(T^{2/3}(V_T+1)^{1/3}) dynamic regret; track restart parameters with Hedge using randomized expert sampling since non-convex outputs cannot be averaged (FTPL-D+); and build geometric covering intervals with FTPL experts combined by AdaNormalHedge with randomized sampling to get O(sqrt(tau) log T) strongly adaptive regret (FTPL-A), which also yields near-o
Key results
- FTPL-D achieves O(T^{2/3}(V_T+1)^{1/3}) dynamic regret with known V_T, matching restarted OGD for convex losses.
- FTPL-A achieves O(sqrt(tau) log T) strongly adaptive regret for non-convex losses, matching the best convex bound.
- In meta-imitation learning experiments, FTPL-D+ and FTPL-A show significantly lower cumulative loss than FTPL in both abruptly changing and gradually evolving environments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| restart FTPL periodically using the known functional variation to set the restart interval | FTPL-D · Dynamic regret | dynamic regret bound: O(T^{2/3}(V_T + 1)^{1/3}) | Helped |
| run multiple restarted FTPL instances with different restart intervals and track them with randomized Hedge | FTPL-D · Dynamic regret | dynamic regret bound: O(T^{2/3}(V_T + 1)^{1/3}) | Helped |
| use geometric-covering intervals and AdaNormalHedge to combine FTPL experts | FTPL-A · Strongly adaptive regret | strongly adaptive regret bound: O(√τ log T) | Helped |
| use FTPL-A to minimize adaptive regret while also bounding dynamic regret | FTPL-A · Dynamic regret | dynamic regret bound: ˜O(T^{2/3}(V_T + 1)^{1/3}) | Helped |
| use FTPL-D+ or FTPL-A instead of FTPL in abruptly changing and gradually evolving environments | Online constrained meta-learning with imitation learning · Meta-imitation learning | cumulative loss | Helped |
| use FTPL-D+ or FTPL-A instead of FTPL in abruptly changing task environments | Robust few-shot image classification · CUB-200-2011, 5-way 5-shot | clean accuracy | Helped |
| use FTPL-D+ or FTPL-A instead of FTPL in abruptly changing task environments | Robust few-shot image classification · CUB-200-2011, 5-way 5-shot | PGD accuracy | Helped |
| use FTPL-D+ or FTPL-A instead of FTPL in abruptly changing task environments | Robust few-shot image classification · CUB-200-2011, 5-way 5-shot | B-score | Helped |
Limitations
- Dynamic regret is bounded only in terms of functional variation V_T, not other comparator regularities like path length.
- Requires an offline optimization oracle assumption (approximate minimizer of perturbed objective), and results hold in expectation.
- FTPL-A is more complex to implement than FTPL-D+ due to geometric covering intervals and many experts.
Experimental setup
Datasets: LASA-style letter demonstrations from Huang et al. 2019 CUB-200-2011
Benchmarks: Meta-imitation learning (letter writing, abruptly changing and gradually evolving environments) CUB-200-2011 robust 5-way 5-shot classification
Metrics: instantaneous loss cumulative loss clean accuracy PGD accuracy B-score constraint violation dynamic regret bound strongly adaptive regret bound
Baselines: FTPL Restarted OGD (convex, theoretical comparison) CBCE (theoretical comparison)
Builds on: Follow the perturbed leader (Suggala and Netrapalli 2020) Restarted OGD (Besbes et al. 2015) Strongly adaptive online learning (Daniely et al. 2015) AdaNormalHedge (Luo and Schapire 2015) Sleeping coin betting (Jun et al. 2017)
Closest papers by meaning
- Dynamic Regret in Online Convex Optimization with Indicator Switching Costs (NeurIPS 2026 · similarity 0.89)
- A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of $\Theta(T^{2/3})$ and its Application to Best-of-Both-Worlds (NeurIPS 2024 · similarity 0.88)
- Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability (ICML 2025 · similarity 0.88)
- Non-stationary Projection-Free Online Learning with Dynamic and Adaptive Regret Guarantees (AAAI 2024 · similarity 0.88)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.88)
- Efficient Non-stationary Online Learning by Wavelets with Applications to Online Distribution Shift Adaptation (ICML 2024 · similarity 0.88)
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.