Research map / Bandits and online learning / Online convex optimization and games
Dynamic Regret Reduces to Kernelized Static Regret
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.
Reframes dynamic regret as static regret over an RKHS of comparator functions, yielding optimal sqrt(P_T) horizon-free and scale-free guarantees for linear losses and curvature-dependent bounds for general convex losses.
Problem
Dynamic regret in online convex optimization against arbitrary comparator sequences, where existing dynamic-to-static reductions only hold for linear losses and existing optimal path-length bounds often need horizon knowledge or doubling tricks.
Approach
Interpret the comparator sequence as evaluations of a fixed comparator function in an RKHS; the dynamic regret equals static regret in that function space for any loss sequence. A carefully designed translation-invariant kernel (spectral density ~1/|omega| with tapering) bounds the RKHS norm by path length, enabling horizon-independent optimal rates.
Key results
- Achieves O~(sqrt((M^2 + M P_T) sum_t ||g_t||^2)) dynamic regret for linear losses with a horizon-independent kernel, without doubling trick.
- Kernelized ONS yields O(lambda ||u||_H^2 + d_eff(lambda) ln T) dynamic regret for exp-concave losses.
- Linear spline kernel gives O~(T^{2/3} (C_T')^{2/3}) squared-path-length-type bound for squared loss regression, matching minimax rate for discrete Sobolev sequences.
Surprising findings
- Existing standard kernels (Gaussian, Matern) fail to give optimal trade-offs between comparator RKHS norm and k(t,t), requiring a new spectral density design.
Limitations
- Naive kernelized implementation requires O(t) time and memory per round, versus O(ln T) for existing dynamic regret algorithms.
- Squared-loss regression achieving T^{1/3} C_T^{2/3} optimal rate is not obtained; left as future work.
- Purely theoretical; no empirical experiments reported.
Experimental setup
Metrics: dynamic regret
Baselines: Jacobsen & Orabona (2024) reduction Gaussian and Matern kernels (as kernel choices) spline kernel (as kernel choice) doubling trick
Builds on: Jacobsen & Orabona (2024) dynamic-to-static reduction Kernelized Online Newton Step Cutkosky-Orabona style parameter-free static regret (Cutkosky & Orabona 2018 coi Kernelized VAW forecaster Zhang et al. 2023 unconstrained dynamic regret
Closest papers by meaning
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.96)
- Dynamic Regret in Online Convex Optimization with Indicator Switching Costs (NeurIPS 2026 · similarity 0.93)
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.92)
- On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning (ICML 2025 · similarity 0.92)
- Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability (ICML 2025 · similarity 0.91)
- Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets (NeurIPS 2024 · similarity 0.91)
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.