An Optimal Reduction of TV-Denoising to Adaptive Online Learning
This provides a new and versatile alternative to wavelet-based methods for adaptively estimating TV-bounded functions and online forecasting of TV-bounded trends in time series, addressing a specific domain problem.
The paper tackles the problem of estimating a function from noisy samples with bounded total variation by connecting it to adaptive online learning, resulting in an O(n log n) time algorithm that achieves a near minimax optimal rate of ~O(n^{1/3} C_n^{2/3}) under squared error loss.
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.