Fugu-MT 論文翻訳(概要): An Optimal Reduction of TV-Denoising to Adaptive Online Learning

論文の概要: An Optimal Reduction of TV-Denoising to Adaptive Online Learning

arxiv url: http://arxiv.org/abs/2101.09438v2
Date: Tue, 26 Jan 2021 06:55:03 GMT
ステータス: 処理完了
システム内更新日: 2021-03-19 10:49:10.872173
Title: An Optimal Reduction of TV-Denoising to Adaptive Online Learning
Title（参考訳）: 適応型オンライン学習におけるテレビデオライジングの最適削減
Authors: Dheeraj Baby and Xuandong Zhao and Yu-Xiang Wang
Abstract要約: 離散的総変動(TV)が$C_n$で有界であるノイズの多いサンプルから関数を推定する問題を検討する。我々は,2乗誤差損失下での最適値が$tilde O (n1/3C_n2/3) に近い最小値が得られる$O(n log n)$ timeアルゴリズムを提供する。これは、(1)テレビの有界関数を適応的に推定するためのウェーブレットベースの方法、(2)テレビの有界傾向のオンライン予測に新しくより汎用性の高い代替手段をもたらす。
参考スコア（独自算出の注目度）: 36.95254034901115
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
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.
Abstract（参考訳）: 離散的トータル変分(TV)を$C_n$で有界とする$n$ノイズサンプルから関数を推定する問題を考察する。我々は、Strongly Adaptive Online Learning(Daniely et al, 2015)の一見異なる問題との深い関係を明らかにし、O(n \log n)$ time algorithm を提供し、最小値の最大値である$\tilde O (n^{1/3}C_n^{2/3})$を2乗誤差損失下で達成する。その結果得られるアルゴリズムはオンライン上で動作し、未知の滑らかさパラメータ$c_n$に最適適応する。これにより、(1)テレビの有界関数を適応的に推定するwaveletsベースの方法、(2)時系列におけるテレビの有界トレンドのオンライン予測といった新しい、より汎用的な方法がもたらされる。