An Optimal Reduction of TV-Denoising to Adaptive Online Learning
An Optimal Reduction of TV-Denoising to Adaptive Online Learning
复制标题
DOI：
--
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
Dheeraj Baby;Xuandong Zhao;Yu-Xiang Wang
中科院分区：
文献类型：
--
作者：
Dheeraj Baby;Xuandong Zhao;Yu-Xiang Wang
本文考虑了从n个噪声样本中估计一个函数的问题，其离散全变差（TV）由C_n$限定。我们揭示了与强自适应在线学习（Daniely et al，2015）的看似不同的问题的深刻联系，并提供了一个时间复杂度为O（n \log n）的算法，该算法在平方误差损失下获得了O（n^{1/3}C_n^{2/3}）的近似最小最大最优速率。由此产生的算法在线运行，并最佳地适应未知的平滑参数$C_n$。这导致了一个新的和更通用的替代小波为基础的方法（1）自适应估计电视有界函数;（2）在线预测电视有界的趋势，在时间序列。
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.