論文の概要: 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)時系列におけるテレビの有界トレンドのオンライン予測といった新しい、より汎用的な方法がもたらされる。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Distributed Extra-gradient with Optimal Complexity and Communication
Guarantees [60.571030754252824]
複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。
モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。
そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
論文 参考訳（メタデータ） (2023-08-17T21:15:04Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive
Regret Bounds [27.92755687977196]
本稿では,2つの階層の環境に適応する線形帯域幅アルゴリズムを提案する。
高いレベルでは、提案アルゴリズムは様々な種類の環境に適応する。
提案アルゴリズムは、最適動作に対する累積損失のすべてに依存する、データ依存の後悔境界を有する。
論文 参考訳（メタデータ） (2023-02-24T00:02:24Z) - Optimal Stochastic Non-smooth Non-convex Optimization through
Online-to-Non-convex Conversion [56.92236659731376]
本稿では,新しい解析手法を用いて,未知の非平滑な目的を最適化するアルゴリズムを提案する。
決定論的二階スムーズな目的のために、先進的な楽観的なオンライン学習技術を適用することで、新しい$O(delta0.5)All$が最適または最もよく知られた結果の回復を可能にする。
論文 参考訳（メタデータ） (2023-02-07T22:09:20Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。