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

Complex distribution shifts are the main obstacle to achieving accurate long-term time series forecasting. Several efforts have been conducted to capture the distribution characteristics and propose adaptive normalization techniques to alleviate the influence of distribution shifts. However, these methods neglect the intricate distribution dynamics observed from various scales and the evolving functions of distribution dynamics and normalized mapping relationships. To this end, we propose a novel model-agnostic Evolving Multi-Scale Normalization (EvoMSN) framework to tackle the distribution shift problem. Flexible normalization and denormalization are proposed based on the multi-scale statistics prediction module and adaptive ensembling. An evolving optimization strategy is designed to update the forecasting model and statistics prediction module collaboratively to track the shifting distributions. We evaluate the effectiveness of EvoMSN in improving the performance of five mainstream forecasting methods on benchmark datasets and also show its superiority compared to existing advanced normalization and online learning approaches. The code is publicly available at https://github.com/qindalin/EvoMSN.

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

Here, we study different update rules in stochastic gradient descent (SGD) for online forecasting problems. The selection of the learning rate parameter is critical in SGD. However, it may not be feasible to tune this parameter in online learning. Therefore, it is necessary to have an update rule that is not sensitive to the selection of the learning parameter. Inspired by the local regret metric that we introduced previously, we propose to use time-smoothed gradients within SGD update. Using the public data set-- GEFCom2014, we validate that our approach yields more stable results than the other existing approaches. Furthermore, we show that such a simple approach is computationally efficient compared to the alternatives.