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.

arXiv commentTo appear at AISTATS 2021

References in corpus (8)

• Beyond a Gaussian Denoiser: Residual Learning of Deep CNN for Image Denoising
• First M87 Event Horizon Telescope Results. I. The Shadow of the Supermassive Black Hole
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• Optimal rates for total variation denoising
• Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers
• The DFS Fused Lasso: Linear-Time Denoising over General Graphs
• Dynamic Regret of Strongly Adaptive Methods
• Trading-Off Static and Dynamic Regret in Online Least-Squares and Beyond

Cited by in corpus (1)

• Optimal Dynamic Regret in Exp-Concave Online Learning