論文の概要: Universal Rates of Empirical Risk Minimization
- arxiv url: http://arxiv.org/abs/2412.02810v2
- Date: Thu, 30 Jan 2025 15:36:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-31 15:13:06.860884
- Title: Universal Rates of Empirical Risk Minimization
- Title（参考訳）: 経験的リスク最小化の普遍的レート
- Authors: Steve Hanneke, Mingyue Xu,
- Abstract要約: 本研究では,経験的リスク (ERM) による普遍的学習の課題について検討する。
ERMによる普遍的な学習率は4つしかない、すなわち、ERMが学習可能な任意の概念クラスの学習曲線は、$e-n$、$/n$、$log(n)/n$、または任意に遅いレートで崩壊する。
- 参考スコア（独自算出の注目度）: 15.001378595582269
- License:
- Abstract: The well-known empirical risk minimization (ERM) principle is the basis of many widely used machine learning algorithms, and plays an essential role in the classical PAC theory. A common description of a learning algorithm's performance is its so-called "learning curve", that is, the decay of the expected error as a function of the input sample size. As the PAC model fails to explain the behavior of learning curves, recent research has explored an alternative universal learning model and has ultimately revealed a distinction between optimal universal and uniform learning rates (Bousquet et al., 2021). However, a basic understanding of such differences with a particular focus on the ERM principle has yet to be developed. In this paper, we consider the problem of universal learning by ERM in the realizable case and study the possible universal rates. Our main result is a fundamental tetrachotomy: there are only four possible universal learning rates by ERM, namely, the learning curves of any concept class learnable by ERM decay either at $e^{-n}$, $1/n$, $\log(n)/n$, or arbitrarily slow rates. Moreover, we provide a complete characterization of which concept classes fall into each of these categories, via new complexity structures. We also develop new combinatorial dimensions which supply sharp asymptotically-valid constant factors for these rates, whenever possible.
- Abstract（参考訳）: 経験的リスク最小化(ERM)原理は、広く使われている機械学習アルゴリズムの基礎であり、古典的なPAC理論において重要な役割を果たす。
学習アルゴリズムの性能の一般的な記述は、いわゆる「学習曲線」であり、すなわち、入力サンプルサイズの関数としての期待誤差の減衰である。
PACモデルは学習曲線の振る舞いを説明できないため、最近の研究では代替の普遍学習モデルを探り、最終的には最適な普遍学習率と一様学習率の区別を明らかにしている(Bousquet et al , 2021)。
しかし、ERMの原理に特に焦点をあてた違いの基本的な理解はいまだに開発されていない。
本稿では,ERMが実現可能な場合における普遍学習の問題について考察し,可能な普遍率について考察する。
すなわち、ERMが学習可能な概念クラスの学習曲線は、e^{-n}$, $1/n$, $\log(n)/n$または任意に遅くなる。
さらに、これらのカテゴリのそれぞれにどの概念クラスが属するかを、新しい複雑性構造を通して、完全に特徴づける。
また, 可能な限り, 急激な漸近的に有意な定数因子を供給できる新しい組合せ次元も開発する。
関連論文リスト
- Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Data [35.03888101803088]
本稿では,不均衡な分類における一般化を解析するための新しい理論的枠組みを提案する。
本稿では,2値設定と複数値設定の両方に新しいクラス不均衡なマージン損失関数を提案し,その強い$H$一貫性を証明し,それに対応する学習保証を導出する。
我々は、信頼率を組み込んだ新しい一般学習アルゴリズムIMMAXを考案し、様々な仮説集合に適用する。
論文 参考訳（メタデータ） (2025-02-14T18:57:16Z) - Proper Learnability and the Role of Unlabeled Data [10.168670899305232]
適切な学習可能性が論理的に決定不可能な問題、すなわちZFC公理に依存しない問題が存在することを示す。
そこで本研究では,PACモデルにおいて,適切な学習可能性の特性を損なう不確実性に関するすべての結果を示す。
論文 参考訳（メタデータ） (2025-02-14T18:41:53Z) - Collaborative Learning with Different Labeling Functions [7.228285747845779]
我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。
データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
論文 参考訳（メタデータ） (2024-02-16T04:32:22Z) - A Unified Generalization Analysis of Re-Weighting and Logit-Adjustment
for Imbalanced Learning [129.63326990812234]
そこで本研究では,データ依存型コンダクタンス(Data-dependent contraction)と呼ばれる手法を提案する。
この技術に加えて、不均衡学習のための微粒な一般化境界が確立され、再重み付けとロジット調整の謎を明らかにするのに役立つ。
論文 参考訳（メタデータ） (2023-10-07T09:15:08Z) - Regularization and Optimal Multiclass Learning [10.168670899305232]
この研究は、経験的リスク最小化が失敗する最も単純な設定における正規化の役割を特徴づけることである。
ワンインクルージョングラフ(OIG)を用いて、試行錯誤アルゴリズムの原理に相応しい最適な学習アルゴリズムを示す。
論文 参考訳（メタデータ） (2023-09-24T16:49:55Z) - On the Stability and Generalization of Triplet Learning [55.75784102837832]
トリプルトラーニング(トリプルトラーニング)、すなわちトリプルトデータから学ぶことは、コンピュータビジョンタスクに大きな注目を集めている。
本稿では,安定解析を利用した三重項学習の一般化保証について検討する。
論文 参考訳（メタデータ） (2023-02-20T07:32:50Z) - GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP,
and Beyond [101.5329678997916]
対話型意思決定の一般的な枠組みの下で, サンプル高能率強化学習(RL)について検討した。
本稿では,探索とエクスプロイトの基本的なトレードオフを特徴付ける,新しい複雑性尺度である一般化エルダー係数(GEC)を提案する。
低 GEC の RL 問題は非常にリッチなクラスであり、これは低ベルマン楕円体次元問題、双線型クラス、低証人ランク問題、PO-双線型クラス、一般化正規PSR を仮定する。
論文 参考訳（メタデータ） (2022-11-03T16:42:40Z) - Constrained Learning with Non-Convex Losses [119.8736858597118]
学習は現代の情報処理の中核技術になっているが、バイアス、安全でない、偏見のあるソリューションにつながるという証拠はたくさんある。
論文 参考訳（メタデータ） (2021-03-08T23:10:33Z) - Nonparametric Estimation of Heterogeneous Treatment Effects: From Theory
to Learning Algorithms [91.3755431537592]
プラグイン推定と擬似出力回帰に依存する4つの幅広いメタ学習戦略を解析する。
この理論的推論を用いて、アルゴリズム設計の原則を導出し、分析を実践に翻訳する方法について強調する。
論文 参考訳（メタデータ） (2021-01-26T17:11:40Z) - A Theory of Universal Learning [26.51949485387526]
普遍的な学習の確率は3つしかないことを示す。
任意の概念クラスの学習曲線は指数的あるいは任意に遅い速度で減衰することを示す。
論文 参考訳（メタデータ） (2020-11-09T15:10:32Z) - Probably Approximately Correct Constrained Learning [135.48447120228658]
我々は、ほぼ正しい学習フレームワーク(PAC)に基づく一般化理論を開発する。
PAC学習可能なクラスも制約のある学習者であるという意味では,学習者の導入は学習問題を難しくするものではないことを示す。
このソリューションの特性を分析し,制約付き学習が公平でロバストな分類における問題にどのように対処できるかを説明する。
論文 参考訳（メタデータ） (2020-06-09T19:59:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。