Skip to yearly menu bar Skip to main content


Poster

Online Linear Regression in Dynamic Environments via Discounting

Andrew Jacobsen · Ashok Cutkosky

Hall C 4-9 #2006
[ ]
Tue 23 Jul 2:30 a.m. PDT — 4 a.m. PDT

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.

Live content is unavailable. Log in and register to view live content