Online Linear Regression in Dynamic Environments via Discounting

Andrew Jacobsen, Ashok Cutkosky
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:21083-21120, 2024.

Abstract

We develop algorithms for online linear regression which achieve optimal static and dynamic regret guarantees 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 RT(→u)≤O(dlog(T)∨√dPγT(→u)T), where PγT(→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 strongly-adaptive guarantees which hold over every sub-interval [a,b]⊆[1,T] simultaneously.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-jacobsen24a, title = {Online Linear Regression in Dynamic Environments via Discounting}, author = {Jacobsen, Andrew and Cutkosky, Ashok}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {21083--21120}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/jacobsen24a/jacobsen24a.pdf}, url = {https://proceedings.mlr.press/v235/jacobsen24a.html}, abstract = {We develop algorithms for online linear regression which achieve optimal static and dynamic regret guarantees 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\Big(d\log(T)\vee \sqrt{dP_{T}^{\gamma}(\vec{u})T}\Big)$, 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 strongly-adaptive guarantees which hold over every sub-interval $[a,b]\subseteq[1,T]$ simultaneously.} }
Endnote
%0 Conference Paper %T Online Linear Regression in Dynamic Environments via Discounting %A Andrew Jacobsen %A Ashok Cutkosky %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-jacobsen24a %I PMLR %P 21083--21120 %U https://proceedings.mlr.press/v235/jacobsen24a.html %V 235 %X We develop algorithms for online linear regression which achieve optimal static and dynamic regret guarantees 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\Big(d\log(T)\vee \sqrt{dP_{T}^{\gamma}(\vec{u})T}\Big)$, 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 strongly-adaptive guarantees which hold over every sub-interval $[a,b]\subseteq[1,T]$ simultaneously.
APA
Jacobsen, A. & Cutkosky, A.. (2024). Online Linear Regression in Dynamic Environments via Discounting. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:21083-21120 Available from https://proceedings.mlr.press/v235/jacobsen24a.html.

Related Material