An Optimal Reduction of TV-Denoising to Adaptive Online Learning

Abstract

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.

To appear at AISTATS 2021

References in corpus (1)

• First M87 Event Horizon Telescope Results. I. The Shadow of the Supermassive Black Hole

Cited by in corpus (1)

• Optimal Dynamic Regret in Exp-Concave Online Learning