Research map / Bandits and online learning / Online convex optimization and games
Non-stationary Projection-Free Online Learning with Dynamic and Adaptive Regret Guarantees
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.
Gives the first general-case dynamic regret bounds for projection-free online learning (BOGDIP, POLD) and a projection-free adaptive regret method (POLA) with ~O(τ^{3/4}) strongly adaptive regret, using linear optimization oracles.
Problem
Projection-free online convex optimization in non-stationary environments, where static regret fails to capture changing best actions; prior projection-free work only covered worst-case dynamic regret or weak adaptive regret, and the strongly adaptive method needed costly membership oracles.
Approach
Analyze the projection-free BOGDIP for general-case dynamic regret (O(T^{3/4}(1+P_T))), then run multiple BOGDIP instances with different step sizes combined by Hedge (POLD) to reach O(T^{3/4}(1+P_T)^{1/4}); and for strongly adaptive regret, run a BOGDIP expert per geometric covering interval combined by AdaNormalHedge (POLA), which also attains the same dynamic regret bound.
Key results
- POLD and POLA achieve O(T^{3/4}(1+P_T)^{1/4}) dynamic regret, improving BOGDIP's O(T^{3/4}(1+P_T)) dependence on path-length.
- POLA attains ~O(τ^{3/4}) strongly adaptive regret for any interval of length τ, versus ~O(√τ) for the membership-oracle method of Lu et al. (2023).
- On online matrix completion, projection-free methods run significantly faster than projection-based Ader, with lower cumulative loss than projection-free Multi-OCG.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use multiple BOGDIP step sizes and track experts with a meta algorithm instead of a single BOGDIP step size | Projection-free dynamic regret minimization · General-case dynamic regret | dynamic regret: O(T 3/4(1 + PT )) -> O(T 3/4(1 + PT )1/4) | Helped |
| Use geometric-covering intervals with BOGDIP experts and a meta algorithm | POLA · Strongly adaptive regret, interval length τ | adaptive regret: ˜O(τ 3/4) | Helped |
| Use POLA to minimize dynamic regret as well as adaptive regret | POLA · General-case dynamic regret | dynamic regret: O(T 3/4(1 + PT )1/4) | Helped |
| Use the proposed projection-free methods instead of the projection-based Ader | BOGDIP, POLD, and POLA · Online matrix completion, MovieLens 100K | runtime | Helped |
| Use the proposed methods instead of Multi-OCG | BOGDIP, POLD, and POLA · Online matrix completion, MovieLens 100K | cumulative loss | Helped |
Limitations
- POLD and POLA maintain O(log T) experts, so O(log T) linear optimizations per round.
- Dynamic regret bound for POLA/POLD is O(T^{3/4}(1+P_T)^{1/4}), which is weaker than projection-based O(sqrt(T(1+P_T)))
- Experiments are limited to a single online matrix completion task with a simulated non-stationary dataset.
Experimental setup
Datasets: MovieLens 100K
Benchmarks: online matrix completion on MovieLens 100K (non-stationary extension)
Metrics: instantaneous loss cumulative loss runtime
Baselines: Multi-OCG Ader BOGD-IP
Builds on: BOGDIP Online Frank-Wolfe AdaNormalHedge Strongly Adaptive Online Learner (SAOL) MetaGrad-style multiple step sizes
Closest papers by meaning
- Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 2025 · similarity 0.91)
- Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability (ICML 2025 · similarity 0.90)
- Efficient Non-stationary Online Learning by Wavelets with Applications to Online Distribution Shift Adaptation (ICML 2024 · 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)
- Online Non-convex Learning in Dynamic Environments (NeurIPS 2024 · similarity 0.88)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · 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.