論文の概要: Sample-Optimal Multi-Group Learning with an ERM Oracle

• arxiv url: http://arxiv.org/abs/2610.15916v1
• Date: Sun, 11 Oct 2026 20:56:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-19 15:19:20.317926
• Title: Sample-Optimal Multi-Group Learning with an ERM Oracle
• Title（参考訳）: ERM Oracleによるサンプル最適マルチグループ学習
• Abstract要約: マルチグループ学習では、一つの予測器は各グループのクラスにおいて最も優れた仮説と同等に振る舞う必要がある。 計算が無制限であっても、学習者ごとに$(d_G+d_H)/varepsilon2)$の値が一致することを示す。
• 参考スコア（独自算出の注目度）: 1.4371100636219536
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: In multi-group learning, a single predictor must perform nearly as well as the best hypothesis in a class on every group in a rich, possibly infinite and overlapping, collection of subpopulations. The known algorithms with the optimal sample complexity keep track of every pair of a group and a hypothesis, which is impossible for the large classes of interest, and the known oracle-based algorithms have a worse rate. We ask whether the optimal rate can be attained by a learner that accesses the classes only through an empirical risk minimization (ERM) oracle. We give an algorithm that uses $\tilde{O}((d_G+d_H)/\varepsilon^2)$ samples and polynomially many calls to a weighted ERM oracle over pairs of a group and a hypothesis, where $d_G$ and $d_H$ are the VC dimensions of the group and hypothesis classes and $\varepsilon$ bounds the excess risk on every group, weighted by its probability. We also show a matching lower bound of $Ω((d_G+d_H)/\varepsilon^2)$ samples for every learner even with unlimited computation, so oracle efficiency costs no additional samples. We also consider a natural special case in which every input belongs to at most $k$ groups and these groups can be listed. In this case, an ERM oracle for the hypothesis class alone suffices, with $\tilde{O}((d_H+\log k)/\varepsilon^2)$ samples in the agnostic setting and $\tilde{O}((d_H+\log k)/\varepsilon)$ samples when every group has a hypothesis that is correct on it.
• Abstract（参考訳）: 多群学習において、一つの予測子は、豊かで無限で重なり合うサブ集団の集合において、すべてのグループのクラスにおいて、最も優れた仮説と同等に振る舞う必要がある。 最適なサンプル複雑性を持つ既知のアルゴリズムは、グループと仮説の全てのペアを追跡するが、これは大きな関心のクラスでは不可能であり、既知のオラクルベースのアルゴリズムはより悪いレートである。 我々は,経験的リスク最小化(ERM)のオラクルを通じてのみクラスにアクセスする学習者によって,最適率が達成できるかどうかを問う。 我々は、$\tilde{O}((d_G+d_H)/\varepsilon^2)$サンプルと多項式的に、群と仮説の対上の重み付けされたERMオラクルへの多くの呼び出しをアルゴリズムに与え、$d_G$と$d_H$は群と仮説クラスのVC次元であり、$\varepsilon$はその確率によって重み付けされる全ての群に対する過剰なリスクを束縛する。 また,無制限に計算しても,学習者毎に$Ω((d_G+d_H)/\varepsilon^2)$の値が一致することを示す。 また、全ての入力が少なくとも$k$群に属し、これらの群をリストアップできるような自然な特殊ケースも検討する。 この場合、仮説クラスのみに対するERMオラクルは、アグノースティックな設定で$\tilde{O}((d_H+\log k)/\varepsilon^2)$サンプルと$\tilde{O}((d_H+\log k)/\varepsilon)$サンプルで十分である。

関連論文リスト

• Robust Learning of a Group DRO Neuron [21.632698901872843]
  任意のラベルノイズと群レベルの分布シフトの存在下で,標準2乗損失下で原始ニューロンを学習する問題について検討した。 我々のフレームワークは、任意のラベルの破損やグループ固有の分布シフトに直面して、堅牢な学習保証を提供する。
  論文  参考訳（メタデータ） (2026-01-26T04:00:53Z)
• From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards [26.147671458980117]
  我々は、入力コンテキストを、可能なアクションの集合の$m$のサブセットにマッピングするコンテキスト半帯域の問題を研究する。 文脈的包帯の原型的応用により、我々は$s$スパース体制に焦点をあてる。 本フレームワークは,二項報酬ベクトルの特別な場合として,帯域フィードバックを用いたリスト多クラス分類問題を一般化する。
  論文  参考訳（メタデータ） (2025-02-13T12:13:25Z)
• Differentially Private Worst-group Risk Minimization [17.81078463701913]
  本稿では,超過最悪の集団集団リスクを$tildeO(fracpsqrtdKepsilon + sqrtfracpK)$とするアルゴリズムを提案する。 我々の速度は、各分布がK/p$の固定サイズのデータセットによって観測されるときにほぼ最適である。
  論文  参考訳（メタデータ） (2024-02-29T18:38:20Z)
• Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity [8.100854060749212]
  本研究では,局所的な差分プライバシーの制約下での仮説選択の問題について検討する。 我々は$varepsilon$-locally-differentially-private ($varepsilon$-LDP)アルゴリズムを考案し、$Thetaleft(fracklog kalpha2min varepsilon2,1 right)$を使って$d_TV(h,hatf)leq alpha + 9 min_fin MathcalFを保証する。
  論文  参考訳（メタデータ） (2023-12-09T19:22:10Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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