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

関連論文リスト

• Asymptotic Inference for Infinitely Imbalanced Logistic Regression [4.981260380070016]
  制限勾配の分散は、多数群の分布に対するマイノリティクラスの点の平均のzスコアに指数関数的に依存することを示す。 我々はモンテカルロシミュレーションで結果を確認した。
  論文  参考訳（メタデータ） (2022-04-27T23:52:42Z)
• Distributionally Robust Models with Parametric Likelihood Ratios [123.05074253513935]
  3つの単純なアイデアにより、より広いパラメトリックな確率比のクラスを用いてDROでモデルを訓練することができる。 パラメトリック逆数を用いてトレーニングしたモデルは、他のDROアプローチと比較して、サブポピュレーションシフトに対して一貫して頑健であることがわかった。
  論文  参考訳（メタデータ） (2022-04-13T12:43:12Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。 特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。 以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
  論文  参考訳（メタデータ） (2022-02-08T16:39:57Z)
• Linear Discriminant Analysis with High-dimensional Mixed Variables [11.867253994761816]
  本稿では,混合変数を用いた高次元観測の分類手法を提案する。 データを指数関数的に多くのセルに分割するという課題を克服する。 推定精度と誤分類率に関する結果が確立される。
  論文  参考訳（メタデータ） (2021-12-14T03:57:56Z)
• 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)

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

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