Research map / Bandits and online learning / Online convex optimization and games
An Equivalence Between Static and Dynamic Regret Minimization
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.
Shows that for linear losses dynamic regret equals static regret in an extended space W^T, derives a variance-variability lower-bound frontier, and gives a Haar-wavelet-based weighted-norm algorithm achieving locally-smoothed squared path-length bounds.
Problem
Dynamic regret minimization in unbounded-domain online linear/convex optimization: no unifying framework, and adapting to squared path-length of the comparator sequence is not understood.
Approach
Embed comparator sequence as one vector in W^T so dynamic regret for linear losses equals static regret in the extended space; then choose weighted norms (dual-norm pairs) to trade off comparator variability against gradient variance, showing squared path-length adaptation requires vacuous (linear) variance penalty and proposing a Haar-based locally-smoothed alternative.
Key results
- Proves a lower bound frontier: adapting to squared path-length requires variance penalty Tr(M^{-1}) = Omega(T^2), making the ideal squared path-length guarantee vacuous.
- Haar-based choice of M gives per-round gradient variance factor (1+log T) and regret O~(sqrt((||ubar||^2 + max_tau sum of squared local-average differences) * sum ||g_t||^2)), with O(d log T) per-round computation.
- Shows the local-averaged squared path-length is bounded by O~(Dbar^2 + Dbar P_T), matching worst-case path-length guarantees up to polylog terms.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Haar-based weighted norm and locally averaged comparator variability instead of direct squared path-length | Dynamic regret for unconstrained OLO · Arbitrary comparator sequences | dynamic regret: \widetilde\mathcal{O}(\Log{T}\sum_{t=1}^{T} \norm{\bg_{t}}^{2}) | Helped |
| Adapt directly to squared path-length using the finite-difference weighted norm | Dynamic regret for unconstrained OLO · Arbitrary comparator sequences | variance penalty: \Tr\brac{\boldsymbol{M}^{{-1}}} = \frac{T(T+1)}{2} | Hurt |
| Reduce dynamic regret to static regret in the extended decision space for linear losses | Dynamic regret minimization · Online linear optimization | regret | Helped |
Surprising findings
- Adapting to the exact squared path-length of an arbitrary comparator sequence is impossible without incurring a linear (vacuous) variance penalty.
Limitations
- Results are for linear losses; general convex losses require the standard OCO-to-OLO reduction.
- The logarithmic dependence of the lower bound is not tight; achieving correct log factors is challenging.
- Potential functions involving infimal convolution for coupled guarantees are hard to design with.
Experimental setup
Metrics: dynamic regret bound
Baselines: Haar OLR Online Gradient Descent with dynamic regret bounds Jacobsen and Cutkosky dynamic regret algorithms
Builds on: Haar OLR parameter-free online learning 1-dimensional reduction for OMD/FTRL with arbitrary norms reward-regret duality
Closest papers by meaning
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.96)
- Dynamic Regret in Online Convex Optimization with Indicator Switching Costs (NeurIPS 2026 · similarity 0.94)
- On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning (ICML 2025 · similarity 0.91)
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.91)
- Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points (NeurIPS 2026 · similarity 0.90)
- Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously (NeurIPS 2024 · similarity 0.90)
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.