Online Forecasting of Total-Variation-bounded Sequences

Abstract

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 \emph{polynomial-time} algorithm that achieves the optimal $O(n^{1/3})$ rate in forecasting total variation bounded sequences and the first algorithm that \emph{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 \emph{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.

To appear in NeurIPS 2019

References in corpus (5)

• Adaptive Online Learning in Dynamic Environments
• Dynamic Regret of Strongly Adaptive Methods
• The Falling Factorial Basis and Its Statistical Applications
• Strongly Adaptive Online Learning
• Online Nonparametric Regression with General Loss Functions

Cited by in corpus (10)

• Non-stationary Online Learning with Memory and Non-stochastic Control
• Dynamic Regret of Convex and Smooth Functions
• Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions
• Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization
• Regret-optimal control in dynamic environments
• Optimal Dynamic Regret in Exp-Concave Online Learning
• Temporal Variability in Implicit Online Learning
• Functional estimation and change detection for nonstationary time series
• Multi-Point Bandit Algorithms for Nonstationary Online Nonconvex Optimization
• Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods