# An Optimal Reduction of TV-Denoising to Adaptive Online Learning

arXiv: https://arxiv.org/abs/2101.09438 · HTML: https://mlsanity.com/paper/2101.09438/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 51 references that are in the map.
- First posted on arXiv 23 Jan 2021.

## Builds on (most cited first, 17 of 17)

- [Beyond a Gaussian Denoiser: Residual Learning of Deep CNN for Image Denoising](https://mlsanity.com/paper/1608.03981/) (2016)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [Adaptive piecewise polynomial estimation via trend filtering](https://mlsanity.com/paper/1304.2986/) (2013)
- [Trend Filtering on Graphs](https://mlsanity.com/paper/1410.7690/) (2014)
- [Dynamical Models and Tracking Regret in Online Convex Programming](https://mlsanity.com/paper/1301.1254/) (2013)
- [Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent](https://mlsanity.com/paper/1803.10366/) (2018)
- [Online Forecasting of Total-Variation-bounded Sequences](https://mlsanity.com/paper/1906.03364/) (2019)
- [Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers](https://mlsanity.com/paper/1605.08400/) (2016)
- [Inter-Series Attention Model for COVID-19 Forecasting](https://mlsanity.com/paper/2010.13006/) (2020)
- [Trading-Off Static and Dynamic Regret in Online Least-Squares and Beyond](https://mlsanity.com/paper/1909.03118/) (2019)
- [Adaptive Online Estimation of Piecewise Polynomial Trends](https://mlsanity.com/paper/2010.00073/) (2020)
- [Online Isotonic Regression](https://mlsanity.com/paper/1603.04190/) (2016)
- [Graph-based regularization for regression problems with alignment and highly-correlated designs](https://mlsanity.com/paper/1803.07658/) (2018)

## Built on by (most cited first, 9 of 9)

- [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021)
- [Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond](https://mlsanity.com/paper/2201.08905/) (2022)
- [Unconstrained Dynamic Regret via Sparse Coding](https://mlsanity.com/paper/2301.13349/) (2023)
- [Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms](https://mlsanity.com/paper/2305.19570/) (2023)
- [Second Order Path Variationals in Non-Stationary Online Learning](https://mlsanity.com/paper/2205.01921/) (2022)
- [Optimal Dynamic Regret in LQR Control](https://mlsanity.com/paper/2206.09257/) (2022)
- [Efficiently Identifying Watermarked Segments in Mixed-Source Texts](https://mlsanity.com/paper/2410.03600/) (2024)
- [Adaptive Estimation and Learning under Temporal Distribution Shift](https://mlsanity.com/paper/2505.15803/) (2025)
- [Spatially Adaptive Online Prediction of Piecewise Regular Functions](https://mlsanity.com/paper/2203.16587/) (2022)

## Abstract (arXiv)

We consider the problem of estimating a function from n noisy samples whose discrete Total Variation (TV) is bounded by Cn. 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 (n1/3Cn2/3) under squared error loss. The resulting algorithm runs online and optimally adapts to the unknown smoothness parameter Cn. 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.