2024/05/29 by Andrew Jacobsen, Jacobsen, Andrew, Ashok Cutkosky +1 · 2 citations
Business, Management and Accounting · Computer Science · Decision Sciences · #Consumer Market Behavior and Pricing #Data Stream Mining Techniques #FOS: Computer and information sciences #Forecasting Techniques and Applications #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · pdf · doi:10.48550/arxiv.2405.19175
openalex publication_date 2024/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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)\vee √dPTγ(u)T), where PTγ(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.