mlsanityData to 7 Oct 2026

An Optimal Reduction of TV-Denoising to Adaptive Online Learning

arXiv 2101.09438 ↗First posted 23 Jan 2021cs.LG math.OC stat.MLcited by 9

Not on the map. Why?

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.

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

Builds on

17 of 51 references.

References · 17

  1. 2016Beyond a Gaussian Denoiser: Residual Learning of Deep CNN for Image Denoisingcited by 1,352
  2. 2013Non-stationary Stochastic Optimizationcited by 173
  3. 2018Adaptive Online Learning in Dynamic Environmentscited by 130
  4. 2015Strongly Adaptive Online Learningcited by 102
  5. 2015Online Optimization : Competing with Dynamic Comparatorscited by 99
  6. 2016Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradientcited by 65
  7. 2013Adaptive piecewise polynomial estimation via trend filteringcited by 47
  8. 2014Trend Filtering on Graphscited by 45
  9. 2013Dynamical Models and Tracking Regret in Online Convex Programmingcited by 42
  10. 2018Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descentcited by 33
  11. 2019Online Forecasting of Total-Variation-bounded Sequencescited by 30
  12. 2016Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smootherscited by 20
5 more
  1. 2020Inter-Series Attention Model for COVID-19 Forecastingcited by 18
  2. 2019Trading-Off Static and Dynamic Regret in Online Least-Squares and Beyondcited by 12
  3. 2020Adaptive Online Estimation of Piecewise Polynomial Trendscited by 11
  4. 2016Online Isotonic Regressioncited by 9
  5. 2018Graph-based regularization for regression problems with alignment and highly-correlated designscited by 5

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 4; 2023: 2; 2024: 1; 2025: 1.

9 papers.

  1. 2021Optimal Dynamic Regret in Exp-Concave Online Learningcited by 39
  2. 2022Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyondcited by 27
  3. 2023Unconstrained Dynamic Regret via Sparse Codingcited by 11
  4. 2023Online Label Shift: Optimal Dynamic Regret meets Practical Algorithmscited by 11
  5. 2022Second Order Path Variationals in Non-Stationary Online Learningcited by 7
  6. 2022Optimal Dynamic Regret in LQR Controlcited by 6
  7. 2024Efficiently Identifying Watermarked Segments in Mixed-Source Textscited by 6
  8. 2022Spatially Adaptive Online Prediction of Piecewise Regular Functionscited by 1
  9. 2025Adaptive Estimation and Learning under Temporal Distribution Shiftcited by 1