論文の概要: Agnostic Smoothed Online Learning
- arxiv url: http://arxiv.org/abs/2410.05124v2
- Date: Fri, 11 Oct 2024 20:21:51 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-02 00:08:45.318073
- Title: Agnostic Smoothed Online Learning
- Title（参考訳）: Agnostic Smoothed Online Learning
- Authors: Moïse Blanchard,
- Abstract要約: 本稿では,$mu$の事前知識を必要とせずに,オンライン学習を円滑に行うためのサブ線形後悔を保証するアルゴリズムを提案する。
R-Coverは、次元$d$を持つ関数クラスに対して、適応的後悔$tilde O(sqrtdT/sigma)$を持つ。
- 参考スコア（独自算出の注目度）: 5.167069404528051
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Classical results in statistical learning typically consider two extreme data-generating models: i.i.d. instances from an unknown distribution, or fully adversarial instances, often much more challenging statistically. To bridge the gap between these models, recent work introduced the smoothed framework, in which at each iteration an adversary generates instances from a distribution constrained to have density bounded by $\sigma^{-1}$ compared to some fixed base measure $\mu$. This framework interpolates between the i.i.d. and adversarial cases, depending on the value of $\sigma$. For the classical online prediction problem, most prior results in smoothed online learning rely on the arguably strong assumption that the base measure $\mu$ is known to the learner, contrasting with standard settings in the PAC learning or consistency literature. We consider the general agnostic problem in which the base measure is unknown and values are arbitrary. Along this direction, Block et al. showed that empirical risk minimization has sublinear regret under the well-specified assumption. We propose an algorithm R-Cover based on recursive coverings which is the first to guarantee sublinear regret for agnostic smoothed online learning without prior knowledge of $\mu$. For classification, we prove that R-Cover has adaptive regret $\tilde O(\sqrt{dT/\sigma})$ for function classes with VC dimension $d$, which is optimal up to logarithmic factors. For regression, we establish that R-Cover has sublinear oblivious regret for function classes with polynomial fat-shattering dimension growth.
- Abstract（参考訳）: 統計学習における古典的な結果は、2つの極端なデータ生成モデルを考えるのが一般的である。
これらのモデルのギャップを埋めるために、最近の研究は滑らかなフレームワークを導入し、各イテレーションにおいて、ある固定基底測度$\mu$に対して$\sigma^{-1}$で束縛された密度を持つような分布から敵がインスタンスを生成する。
このフレームワークは、$\sigma$ の値に依存する i.i.d. と逆の場合を補間する。
古典的オンライン予測問題において、スムーズなオンライン学習の先行結果は、学習者に対して、PAC学習や一貫性文学における標準設定と対照的に、基本測度$\mu$が知られているという間違いなく強い仮定に依存している。
基本測度が未知であり、値が任意である一般的な不可知問題を考える。
この方向に沿って、Blockらは、経験的リスク最小化は、明確に定義された仮定の下で、サブリニアな後悔であることを示した。
本稿では,再帰的被覆に基づくR-Coverアルゴリズムを提案する。
分類に関して、R-Cover は VC 次元 $d$ を持つ函数クラスに対して、適応的後悔 $\tilde O(\sqrt{dT/\sigma})$ を持つことを証明している。
回帰に関して、R-Cover は多項式脂肪散乱次元成長を持つ関数類に対して、サブ線形な後悔を持つことを確かめる。
関連論文リスト
- Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - Restricted Strong Convexity of Deep Learning Models with Smooth
Activations [31.003601717265006]
本研究では,スムーズなアクティベーション機能を持つディープラーニングモデルの最適化問題について検討する。
Restricted Strong Convexity (RSC) に基づく最適化の新しい解析手法を提案する。
深層学習モデルのためのRCCに基づくGDの幾何収束性を確立するための最初の結果である。
論文 参考訳（メタデータ） (2022-09-29T21:24:26Z) - First-Order Regret in Reinforcement Learning with Linear Function
Approximation: A Robust Estimation Approach [57.570201404222935]
我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。
この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
論文 参考訳（メタデータ） (2021-12-07T00:29:57Z) - Fast Rates for Nonparametric Online Learning: From Realizability to
Learning in Games [36.969021834291745]
本稿では,仮説クラスの逐次的脂肪散乱次元の観点から,ほぼ最適誤差を導出する固有学習アルゴリズムを提案する。
この結果は、適切な学習者が準最適誤り境界を達成できるかどうかという疑問に答える。
実数値(回帰)設定では、最適誤り境界は不適切な学習者にさえ知られていなかった。
論文 参考訳（メタデータ） (2021-11-17T05:24:21Z) - Online Selective Classification with Limited Feedback [82.68009460301585]
オンライン学習モデルにおいて、予測者がインスタンスの分類を控える可能性のある選択的分類について検討する。
私たちが考慮している設定の健全な2つの側面は、データが不可避である可能性があるため、データは不可避である可能性があるということです。
smash$tildeO(T1-mu)$ over abstention against Adaptive adversaries. smash$tildeO(T1-mu)$ incurring smash$tildeO(T1-mu)$ over abstention。
論文 参考訳（メタデータ） (2021-10-27T08:00:53Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳（メタデータ） (2021-10-09T21:13:48Z) - Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。
ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。
本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
論文 参考訳（メタデータ） (2021-06-06T19:08:53Z) - Localization, Convexity, and Star Aggregation [0.0]
オフセットラデマッハ複体は、正方形損失に対する鋭く線形依存的な上界を示すことが示されている。
統計的設定では、オフセット境界は一定の均一な凸性を満たす任意の損失に一般化可能であることを示す。
論文 参考訳（メタデータ） (2021-05-19T00:47:59Z) - Estimating Stochastic Linear Combination of Non-linear Regressions
Efficiently and Scalably [23.372021234032363]
サブサンプルサイズが大きくなると、推定誤差が過度に犠牲になることを示す。
私たちの知る限りでは、線形テキスト+確率モデルが保証される最初の研究です。
論文 参考訳（メタデータ） (2020-10-19T07:15:38Z) - Statistical-Query Lower Bounds via Functional Gradients [19.5924910463796]
我々は、寛容$n- (1/epsilon)b$の統計クエリアルゴリズムは、一定の$bに対して少なくとも$2nc epsilon$クエリを使用する必要があることを示す。
実数値学習では珍しいSQ学習アルゴリズムが一般的である(相関学習とは対照的に)。
論文 参考訳（メタデータ） (2020-06-29T05:15:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。