論文の概要: 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) によっても提起された。

関連論文リスト

• Sampling in Constrained Domains with Orthogonal-Space Variational Gradient Descent [13.724361914659438]
  多様体上のサンプリングのための直交空間勾配流(O-Gradient)を設計した新しい変分フレームワークを提案する。 我々は、O-Gradient が目標制約分布に収束し、弱条件下では、$widetildeO (1/textthe number of iterations)$$で収束することを証明した。
  論文  参考訳（メタデータ） (2022-10-12T17:51:13Z)
• Centrality and Consistency: Two-Stage Clean Samples Identification for Learning with Instance-Dependent Noisy Labels [87.48541631675889]
  本稿では,2段階のクリーンサンプル識別手法を提案する。 まず,クリーンサンプルの早期同定にクラスレベルの特徴クラスタリング手法を用いる。 次に, 基底真理クラス境界に近い残余のクリーンサンプルについて, 一貫性に基づく新しい分類法を提案する。
  論文  参考訳（メタデータ） (2022-07-29T04:54:57Z)
• Distributionally Robust Models with Parametric Likelihood Ratios [123.05074253513935]
  3つの単純なアイデアにより、より広いパラメトリックな確率比のクラスを用いてDROでモデルを訓練することができる。 パラメトリック逆数を用いてトレーニングしたモデルは、他のDROアプローチと比較して、サブポピュレーションシフトに対して一貫して頑健であることがわかった。
  論文  参考訳（メタデータ） (2022-04-13T12:43:12Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。 特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。 以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
  論文  参考訳（メタデータ） (2022-02-08T16:39:57Z)
• Divide-and-Conquer Hard-thresholding Rules in High-dimensional Imbalanced Classification [1.0312968200748118]
  高次元の線形判別分析(LDA)における不均衡クラスサイズの影響について検討した。 マイノリティ・クラスと呼ばれる1つのクラスのデータの不足により、LDAはマイノリティ・クラスを無視し、最大誤分類率を得ることを示す。 そこで本研究では,不等式化率の大きな差を低減させる分割・対数法に基づくハードコンカレンスルールの新たな構成法を提案する。
  論文  参考訳（メタデータ） (2021-11-05T07:44:28Z)
• 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)

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

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