論文の概要: Multiclass Online Learning and Uniform Convergence

• arxiv url: http://arxiv.org/abs/2303.17716v2
• Date: Fri, 7 Jul 2023 14:45:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-10 15:36:03.445294
• Title: Multiclass Online Learning and Uniform Convergence
• Title（参考訳）: 多クラスオンライン学習と一様収束
• Authors: Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, Ambuj Tewari
• Abstract要約: 対戦型オンライン学習環境におけるマルチクラス分類について検討する。 任意のマルチクラスの概念クラスが、そのリトルストーン次元が有限である場合に限り、不可知的に学習可能であることを証明する。
• 参考スコア（独自算出の注目度）: 34.21248304961989
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study multiclass classification in the agnostic adversarial online learning setting. As our main result, we prove that any multiclass concept class is agnostically learnable if and only if its Littlestone dimension is finite. This solves an open problem studied by Daniely, Sabato, Ben-David, and Shalev-Shwartz (2011,2015) who handled the case when the number of classes (or labels) is bounded. We also prove a separation between online learnability and online uniform convergence by exhibiting an easy-to-learn class whose sequential Rademacher complexity is unbounded. Our learning algorithm uses the multiplicative weights algorithm, with a set of experts defined by executions of the Standard Optimal Algorithm on subsequences of size Littlestone dimension. We argue that the best expert has regret at most Littlestone dimension relative to the best concept in the class. This differs from the well-known covering technique of Ben-David, P\'{a}l, and Shalev-Shwartz (2009) for binary classification, where the best expert has regret zero.
• Abstract（参考訳）: 不可知論的オンライン学習環境における多クラス分類について検討した。 主な結果として、任意の多重クラスの概念クラスが非可知であることと、そのリトルストーン次元が有限であることは同値である。 これは、Daniely, Sabato, Ben-David, Shalev-Shwartz (2011, 2015) によって研究され、クラス(またはラベル)の数が有界である場合のケースを扱う。 また、オンライン学習性とオンライン一様収束の分離を、連続的なRademacher複雑性が非有界な学習クラスで表すことによって証明する。 学習アルゴリズムは乗法重みアルゴリズムを使用し,標準最適アルゴリズムを小石次元のサブシーケンス上で実行することにより,専門家のセットを定めている。 最高の専門家は、クラスの最高の概念に対して、たいていのリトルストーン次元を後悔している、と主張する。 これはBen-David、P\'{a}l、Shalev-Shwartz (2009) の2進分類におけるよく知られた被覆技法とは異なる。

関連論文リスト

• Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem [26.292576184028924]
  この研究は、差分プライベート(DP)とオンライン学習との関係について研究を続けている。 一般分類タスクにおいては,DP学習性はオンライン学習性を意味することを示す。
  論文  参考訳（メタデータ） (2024-07-10T15:43:30Z)
• Simple online learning with consistent oracle [55.43220407902113]
  オンライン学習は、学習アルゴリズムが、どの時点でも、今まで見てきたすべての例に一致する関数をクラスから与えることができる、という、一貫性のあるオラクルを通じてのみクラスにアクセスすることができるモデルであると考えている。
  論文  参考訳（メタデータ） (2023-08-15T21:50:40Z)
• A Combinatorial Characterization of Supervised Online Learnability [20.291598040396302]
  本稿では,任意だが有界な損失関数に対する仮説クラスのオンライン学習可能性について検討する。 連続最小次元と呼ばれる新しいスケール感性次元を与え、オンライン学習可能性の厳密な定量的評価を与えることを示す。
  論文  参考訳（メタデータ） (2023-07-07T20:11:07Z)
• Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization [39.51923275855131]
  本研究では,テスト時間における逆例に頑健な予測器の学習問題に対して,最小限の最適学習器を提案する。 特に、強い否定的な意味で、モンタッサー、ハネケ、スレブロによって提案された頑健な学習者の亜最適性を示す。
  論文  参考訳（メタデータ） (2022-09-15T15:32:42Z)
• Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm [14.834625066344582]
  対数損失下での逐次的オンライン回帰(シーケンシャル確率代入)について検討する。 我々は、専門家のクラスで発生する過剰な損失として定義される連続したミニマックスの後悔に対して、厳密で、しばしば一致し、下限と上限を得ることに重点を置いている。
  論文  参考訳（メタデータ） (2022-05-07T22:03:00Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games [36.969021834291745]
  本稿では,仮説クラスの逐次的脂肪散乱次元の観点から,ほぼ最適誤差を導出する固有学習アルゴリズムを提案する。 この結果は、適切な学習者が準最適誤り境界を達成できるかどうかという疑問に答える。 実数値(回帰)設定では、最適誤り境界は不適切な学習者にさえ知られていなかった。
  論文  参考訳（メタデータ） (2021-11-17T05:24:21Z)
• 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)
• Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View [82.80085730891126]
  線形多クラス分類の最初の現代的精度解析を行う。 分析の結果,分類精度は分布に依存していることがわかった。 得られた洞察は、他の分類アルゴリズムの正確な理解の道を開くかもしれない。
  論文  参考訳（メタデータ） (2020-11-16T05:17:29Z)
• Active Online Learning with Hidden Shifting Domains [64.75186088512034]
  本稿では,その後悔度とラベルクエリ数とを適応的にバランスさせる,驚くほど単純なアルゴリズムを提案する。 我々のアルゴリズムは、異なる領域からの入力のインターリービングスパンを適応的に処理できる。
  論文  参考訳（メタデータ） (2020-06-25T15:23:59Z)

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

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