Research map / Bandits and online learning / Online convex optimization and games
Dynamic Regret in Online Convex Optimization with Indicator Switching Costs
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.
Proposes a meta-learner over randomized lazy FTRL (FPRLL) base learners restarted at dyadic scales, aggregated via maximal coupling of mixture densities, achieving dynamic regret with indicator switching costs.
Problem
Dynamic regret in online convex optimization when the learner pays a fixed indicator penalty each time consecutive decisions differ; prior indicator-cost guarantees only cover static comparators.
Approach
Restart randomized lazy FTRL (FPRLL) learners at dyadic time scales and aggregate them with a movement-aware master that mixes their densities and samples actions by maximal coupling of consecutive mixtures, with a strongly adaptive discounted-normal meta-learner over the scales.
Key results
- Achieves expected dynamic regret plus indicator switching cost of Otilde(min{sqrt(T(S_T+1)), T^{2/3}(P_T+1)^{1/3}}) without prior knowledge of S_T or P_T.
- Piecewise-constant branch Otilde(sqrt((S_T+1)T)) is minimax-optimal up to log factors via a matching lower bound on tracking.
- Shows fixed-restart FPRLL(k) suffers Omega(T^{2/3} tau^{1/3}/log T) dynamic regret on U_S(tau), and unrestarted FPRLL suffers Omega(T).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restarting FPRLL without any restarts (single FTRL run with perturbations and barrier) | FPRLL (randomized FTRL) · dynamic regret on U_S(1) | dynamic regret | Hurt |
| Fixed restart period k added to FPRLL | FPRLL · dynamic regret on U_S(tau) | dynamic regret | Hurt |
| Multiscale meta-learner over restarted FPRLL experts at all dyadic scales with movement-aware mixing | FPRLL base learners · piecewise-constant comparators | R^1_T (dynamic regret + indicator switching cost) | Helped |
| Dyadic restart scale selection via meta-learner (P_T branch) vs. fixed-scale FPRLL | meta-learner · bounded path length comparators | R^1_T | Helped |
| Unified guarantee does not match norm-based O(sqrt(T(1+P_T))) on U_P | proposed meta-learner · bounded path length comparators | R^1_T bound order | Hurt |
Surprising findings
- Even with perturbations and fixed restarts, FTRL-based randomized learners fail to achieve optimal dynamic regret under indicator switching costs.
- Under indicator switching costs the unified sqrt(T(1+P_T)) bound from norm-based SOCO is not attained; the path-length branch degrades to T^{2/3}P_T^{1/3}.
Limitations
- Path-length bound degrades to T^{2/3}P_T^{1/3}, not the optimal sqrt(T(1+P_T)) achievable under norm-based costs.
- Main analysis uses exact surrogate losses and TV distances; practical implementation relies on sampled surrogates with approximations.
- Per-round cost scales with O(log T) FPRLL base learners plus meta overhead.
Experimental setup
Metrics: expected dynamic regret plus indicator switching cost
Baselines: FPRLL FPRLL(k) fixed restart
Builds on: FTRL with perturbations and barrier (FPRLL) discounted-normal predictor strongly adaptive regret reduction (geometric covering) maximal coupling / lazy sampling
Closest papers by meaning
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.94)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.93)
- On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning (ICML 2025 · similarity 0.92)
- Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously (NeurIPS 2024 · similarity 0.91)
- Online Non-convex Learning in Dynamic Environments (NeurIPS 2024 · similarity 0.89)
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · 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.