Timezone: »

 
Poster
Online Forecasting of Total-Variation-bounded Sequences
Dheeraj Baby · Yu-Xiang Wang

Thu Dec 12 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #22
in Algorithms -- Online Learning »
We consider the problem of online forecasting of sequences of length $n$ with total-variation at most $C_n$ using observations contaminated by independent $\sigma$-subgaussian noise. We design an $O(n\log n)$-time algorithm that achieves a cumulative square error of $\tilde{O}(n^{1/3}C_n^{2/3}\sigma^{4/3} + C_n^2)$ with high probability. We also prove a lower bound that matches the upper bound in all parameters (up to a $\log(n)$ factor). To the best of our knowledge, this is the first **polynomial-time** algorithm that achieves the optimal $O(n^{1/3})$ rate in forecasting total variation bounded sequences and the first algorithm that **adapts to unknown** $C_n$.Our proof techniques leverage the special localized structure of Haar wavelet basis and the adaptivity to unknown smoothness parameters in the classical wavelet smoothing [Donoho et al., 1998]. We also compare our model to the rich literature of dynamic regret minimization and nonstationary stochastic optimization, where our problem can be treated as a special case. We show that the workhorse in those settings --- online gradient descent and its variants with a fixed restarting schedule --- are instances of a class of **linear forecasters** that require a suboptimal regret of $\tilde{\Omega}(\sqrt{n})$. This implies that the use of more adaptive algorithms is necessary to obtain the optimal rate.
Keywords: Online Learning · Algorithms · Algorithms -> Regression; Applications -> Denoising; Applications -> Signal Processing; Applications · Time Series Analysis; O

Author Information

Dheeraj Baby (UC Santa Barbara)
Yu-Xiang Wang (UC Santa Barbara)

More from the Same Authors