An Optimal Reduction of TV-Denoising to Adaptive Online Learning
  We consider the problem of estimating a function from $n$ noisy samples whose
discrete Total Variation (TV) is bounded by $C_n$. We reveal a deep connection
to the seemingly disparate problem of Strongly Adaptive online learning
(Daniely et al, 2015) and provide an $O(n \log n)$ time algorithm that attains
the near minimax optimal rate of $\tilde O (n^{1/3}C_n^{2/3})$ under squared
error loss. The resulting algorithm runs online and optimally adapts to the
unknown smoothness parameter $C_n$. This leads to a new and more versatile
alternative to wavelets-based methods for (1) adaptively estimating TV bounded
functions; (2) online forecasting of TV bounded trends in time series.
