OnlineForecastingofTotal-Variation-bounded Sequences

We consider the problem of online forecasting of sequences of lengthn with total-variation at mostCn using observations contaminated by independentσsubgaussian noise. We design anO(nlogn)-time algorithm that achieves a cu-mulativesquare error of O(n1/3C2/3n σ4/3+C2n)with high probability.