論文の概要: 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)時系列におけるテレビの有界トレンドのオンライン予測といった新しい、より汎用的な方法がもたらされる。
関連論文リスト
- Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for
Online Convex Optimization [93.14387921542709]
非定常環境におけるオンライン凸最適化について検討する。
エンファンダイナミックな後悔をパフォーマンス指標として選びます。
本研究では,スムーズさを生かし,動的後悔の中で$T$に依存する新しいオンラインアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
バイレベル最適化は多くの応用のために機械学習への関心が高まっている。
制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
論文 参考訳（メタデータ） (2021-06-21T20:16:40Z) - Stochastic Bias-Reduced Gradient Methods [44.35885731095432]
モロー・吉田関数の任意の有界な$x_star$の低バイアスで低コストな平滑化である。
論文 参考訳（メタデータ） (2021-06-17T13:33:05Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Optimal Dynamic Regret in Exp-Concave Online Learning [28.62891856368132]
我々は、オンライン学習におけるZinkevich(2003)スタイルの動的後悔最小化の問題を検討する。
不適切な学習が許されるたびに、Strongly Adaptive のオンライン学習者は $tilde O(d3.5n1/3C_n2/3 vee dlog n)$ の動的後悔を達成する。
経路の長さ) 学習者が事前に知ることができない任意のコンパレータのシーケンス。
論文 参考訳（メタデータ） (2021-04-23T21:36:51Z) - Retrospective Approximation for Smooth Stochastic Optimization [1.0323063834827415]
我々は,普遍近似問題サイズパラダイムとしてふりかえり近似(ra)を提案する。
線形探索準探索によるRAの性能について,不条件最小二乗問題と深部畳み込みニューラルネットを用いた画像分類問題について述べる。
論文 参考訳（メタデータ） (2021-03-07T16:29:36Z) - Smoothed Analysis with Adaptive Adversaries [28.940767013349408]
オンライン問題に対する新しいアルゴリズムの保証を平滑化解析モデルで証明する。
このモデルでは、敵は各時間に一様分布の$tfrac1sigma$倍の密度関数を持つ入力分布を選択する。
本研究の結果は,アルゴリズムの決定と前回の時間ステップにおける入力の実現に基づいて,入力分布を選択可能な適応的敵に対して成り立っている。
論文 参考訳（メタデータ） (2021-02-16T20:54:49Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Strongly Adaptive OCO with Memory [49.319621885036035]
本稿では,メモリを用いたオンライン学習のための適応型アルゴリズムを提案する。
このアルゴリズムは,線形時間変化システムの制御に強い適応性を持つリセットバウンドをもたらす。
論文 参考訳（メタデータ） (2021-02-02T17:26:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。