Research map / Bandits and online learning / Online convex optimization and games
Online Linear Regression in Dynamic Environments via Discounting
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 a discounted Vovk-Azoury-Warmuth forecaster achieves optimal static and dynamic regret for online linear regression with no prior knowledge, via a mirror-descent analysis and oracle-tuned discount factor.
Problem
Online linear regression in dynamic (non-stationary) environments, where algorithms typically need prior knowledge of comparator norms or variability to achieve optimal dynamic regret.
Approach
A discounted variant of the VAW forecaster, with discount factor gamma, is analyzed via an optimistic FTRL / mirror-descent equivalence; a regret bound in terms of a discounted path-length measure P_T^gamma is obtained, and an existence lemma picks a good gamma so the bound holds without prior knowledge.
Key results
- Discounted VAW with oracle-tuned gamma achieves dynamic regret O(d log T ∨ sqrt(d P_T^gamma(u) T)) per the abstract, and the appendix bound R_T(u) ≤ O(sqrt(2d P_T^{γ*}(u) Σ(y_t - ỹ_t)^2)) plus lower-order terms.
- The key analysis interprets the discounted VAW update as mirror descent, yielding the regret decomposition in the appendix.
Limitations
- Bounds hold up to lower-order terms and constants hidden in O(.) notation.
- Oracle tuning of the discount factor gamma requires quantities depending on the unknown comparator sequence in the theorem; the parameter-free result is only stated via the existence lemma.
Experimental setup
Metrics: dynamic regret static regret
Builds on: Vovk-Azoury-Warmuth forecaster optimistic FTRL optimistic mirror descent
Closest papers by meaning
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.89)
- Adaptive Online Learning in Dynamic Environments (NeurIPS 2018 · similarity 0.89)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.88)
- On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning (ICML 2025 · similarity 0.88)
- Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability (ICML 2025 · similarity 0.88)
- Dynamic Regret in Online Convex Optimization with Indicator Switching Costs (NeurIPS 2026 · similarity 0.87)
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.