2021/01/23 by Dheeraj Baby, Xuandong Zhao, Baby, Dheeraj +3 · 2 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Image and Signal Denoising Methods #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.2101.09438
openalex publication_date 2021/01/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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.