
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.