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.

Update after reading the authors' response: The authors' response answered my questions well. One limitation that I missed in my initial review is that the coordinates of the parameter theta (the true signal sequence) are not assumed to be bounded; the only assumption is that theta lies in a total variation ball. This means that the only bound on these coordinates is through the bound C on the total variation of the sequence. Hence, the dependence on the bound B on the sequence (L-infty norm of theta) is implicit and replaced by the worst-case upper bound C, which leads to a dependence on C 2 instead of B*C on the intersection of those balls. I think that this limitation should be addressed, given that in the online learning literature it is more customary to provide the explicit dependence on B. To be specific, this would entail assuming that theta lies in the intersection of a TV ball of radius C and an L-infinity ball of radius B (where both B and C can be assumed to be known, though adaptivity to those can be considered), and providing matching upper and lower bound over this class.

The paper introduces an optimal online learning algorithm for the non-parametric class of total-variation bounded sequences. Moreover, it shows that a class of well-known existing methods cannot be optimal, and that there is a separation between the achievable rates for estimation and prediction in terms of regret. These are all fundamental results, and the paper clearly discusses their connections to important developments in non-parametric statistical estimation. Comments for the final version: Please carefully consider the reviews, and take the (updated) comments into account when preparing the final version of the paper. In particular, please consider the dependence on B mentioned by reviewer #1. Note that there is already a well-known online learning algorithm called AROW (Crammer, Kulesza, Dredze, NeurIPS 2009), so please change the algorithm name from ARROWS to something else.

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 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}) .

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 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})$.