Online Linear Regression in Dynamic Environments via Discounting
<|reference_start|>Online Linear Regression in Dynamic Environments via Discounting: We develop algorithms for online linear regression which achieve optimal static and dynamic regret guarantees \emph{even in the complete absence of prior knowledge}. We present a novel analysis showing that a discounted variant of the Vovk-Azoury-Warmuth forecaster achieves dynamic regret of the form $R_{T}(\vec{u})\le O\left(d\log(T)\vee \sqrt{dP_{T}^{\gamma}(\vec{u})T}\right)$, where $P_{T}^{\gamma}(\vec{u})$ is a measure of variability of the comparator sequence, and show that the discount factor achieving this result can be learned on-the-fly. We show that this result is optimal by providing a matching lower bound. We also extend our results to \emph{strongly-adaptive} guarantees which hold over every sub-interval $[a,b]\subseteq[1,T]$ simultaneously.<|reference_end|>
@article{jacobsen2024online,
    title={Online Linear Regression in Dynamic Environments via Discounting},
    author={Andrew Jacobsen and Ashok Cutkosky},
    journal={arXiv preprint arXiv:2405.19175},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.19175},
    primaryClass={cs.LG stat.ML}
}