論文の概要: Adversarial Laws of Large Numbers and Optimal Regret in Online Classification

• arxiv url: http://arxiv.org/abs/2101.09054v1
• Date: Fri, 22 Jan 2021 11:15:19 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-20 17:26:38.128793
• Title: Adversarial Laws of Large Numbers and Optimal Regret in Online Classification
• Title（参考訳）: オンライン分類における大数の逆法則と最適後悔
• Authors: Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, Eylon Yogev
• Abstract要約: サンプリングプロセスにおける多数の法則について検討し,それらが作用し,相互作用する環境に影響を及ぼす可能性について検討した。 我々の特徴は,統計的学習における学習可能性と一様収束の等価性のオンラインアナログとして解釈できる。
• 参考スコア（独自算出の注目度）: 32.16217148059578
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Laws of large numbers guarantee that given a large enough sample from some population, the measure of any fixed sub-population is well-estimated by its frequency in the sample. We study laws of large numbers in sampling processes that can affect the environment they are acting upon and interact with it. Specifically, we consider the sequential sampling model proposed by Ben-Eliezer and Yogev (2020), and characterize the classes which admit a uniform law of large numbers in this model: these are exactly the classes that are \emph{online learnable}. Our characterization may be interpreted as an online analogue to the equivalence between learnability and uniform convergence in statistical (PAC) learning. The sample-complexity bounds we obtain are tight for many parameter regimes, and as an application, we determine the optimal regret bounds in online learning, stated in terms of \emph{Littlestone's dimension}, thus resolving the main open question from Ben-David, P\'al, and Shalev-Shwartz (2009), which was also posed by Rakhlin, Sridharan, and Tewari (2015).
• Abstract（参考訳）: 大きな数の法則により、ある集団から十分な量のサンプルが与えられた場合、固定されたサブ集団の測度は標本の頻度によってよく推定される。 サンプリングプロセスにおける多数の法則について検討し,それらが作用し,相互作用する環境に影響を及ぼす可能性について検討した。 具体的には、ben-eliezer と yogev (2020) によって提案された逐次サンプリングモデルを検討し、このモデルで大数の一様法則を許すクラスを特徴づける: これらはちょうど \emph{online learnable} である。 我々の特徴は,統計的学習における学習可能性と一様収束の等価性のオンラインアナログとして解釈できる。 サンプル-複素性境界は、多くのパラメーターレジームに対して厳密であり、応用として、オンライン学習において最適の後悔境界を決定する。これは、'emph{Littlestone's dimension} の項で述べられており、Ben-David, P\'al, and Shalev-Shwartz (2009) から主要な開質問を解き、Rahlin, Sridharan, Tewari (2015) によっても提起された。

関連論文リスト

• Smoothed Online Classification can be Harder than Batch Classification [18.054632903107546]
  オンライン学習の円滑化は,PACモデルに基づくiidバッチ設定の学習と同じくらい容易であることを示す。 PACモデルではiidバッチ設定で学習できるが,スムーズなオンラインモデルでは学習できない仮説クラスを構築した。
  論文  参考訳（メタデータ） (2024-05-24T10:37:39Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Combating Representation Learning Disparity with Geometric Harmonization [50.29859682439571]
  本稿では,表現学習におけるカテゴリレベルの均一性を促進するために,新しい幾何調和法を提案する。 我々の提案はSSLの設定を変更せず、低コストで既存のメソッドに容易に統合できる。
  論文  参考訳（メタデータ） (2023-10-26T17:41:11Z)
• Shrinking Class Space for Enhanced Certainty in Semi-Supervised Learning [59.44422468242455]
  そこで我々はShrinkMatchと呼ばれる新しい手法を提案し、不確実なサンプルを学習する。 それぞれの不確実なサンプルに対して、元の Top-1 クラスを単に含むスランク類空間を適応的に求める。 次に、スランク空間における強と弱に強化された2つのサンプル間の整合正則化を課し、識別的表現を試みます。
  論文  参考訳（メタデータ） (2023-08-13T14:05:24Z)
• Multiclass Online Learning and Uniform Convergence [34.21248304961989]
  対戦型オンライン学習環境におけるマルチクラス分類について検討する。 任意のマルチクラスの概念クラスが、そのリトルストーン次元が有限である場合に限り、不可知的に学習可能であることを証明する。
  論文  参考訳（メタデータ） (2023-03-30T21:35:48Z)
• Centrality and Consistency: Two-Stage Clean Samples Identification for Learning with Instance-Dependent Noisy Labels [87.48541631675889]
  本稿では,2段階のクリーンサンプル識別手法を提案する。 まず,クリーンサンプルの早期同定にクラスレベルの特徴クラスタリング手法を用いる。 次に, 基底真理クラス境界に近い残余のクリーンサンプルについて, 一貫性に基づく新しい分類法を提案する。
  論文  参考訳（メタデータ） (2022-07-29T04:54:57Z)
• Breadcrumbs: Adversarial Class-Balanced Sampling for Long-tailed Recognition [95.93760490301395]
  クラスごとのサンプル数が非バランスである長尾認識の問題は、考慮されます。 これは例の繰り返しサンプリングによるものであり、特徴空間拡張によって対処できると仮定される。 トレーニング中のエポック間の機能のバックトラッキングに基づく,新たな機能拡張戦略であるemanateを提案する。 新たなサンプリング手順であるbreadcrumbは、余分な計算なしで逆のクラスバランスのサンプリングを実装するために導入された。
  論文  参考訳（メタデータ） (2021-05-01T00:21:26Z)
• Sample-efficient proper PAC learning with approximate differential privacy [51.09425023771246]
  近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。 この結果は Bun et al の質問に答えます。 (FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
  論文  参考訳（メタデータ） (2020-12-07T18:17:46Z)
• The Bures Metric for Generative Adversarial Networks [10.69910379275607]
  GAN(Generative Adversarial Networks)は、高品質なサンプルを生成する高性能な生成手法である。 実バッチの多様性と偽バッチの多様性を一致させることを提案する。 多様性マッチングはモード崩壊を著しく低減し, サンプル品質に肯定的な影響を及ぼす。
  論文  参考訳（メタデータ） (2020-06-16T12:04:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。