論文の概要: The Sample Complexity of Multicalibration with an ERM Oracle

• arxiv url: http://arxiv.org/abs/2610.14363v1
• Date: Fri, 09 Oct 2026 22:32:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-20 21:59:34.670494
• Title: The Sample Complexity of Multicalibration with an ERM Oracle
• Title（参考訳）: ERMオラクルを用いたマルチキャリブレーションのサンプル複雑さ
• Abstract要約: 有限クラスの場合、約$varepsilon-3サンプルは多重校正誤差$varepsilon$の予測子を学ぶために必要である。 与えられた予測子の誤差を推定するために、通常の概念はより難しいものである。 与えられた予測器のマルチキャリブレーション誤差を計算するよりも、計算的にマルチキャリブレーション予測器を学習しやすいクラスがある。
• 参考スコア（独自算出の注目度）: 1.4371100636219536
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: A predictor is multicalibrated with respect to a class of subpopulations (formally, of functions on the inputs, called auditors) if, for every subpopulation in the class and every value the predictor outputs, the average outcome among the members of that subpopulation who receive that value is close to the value itself. For finite classes, about $\varepsilon^{-3}$ samples are necessary and sufficient to learn a predictor with multicalibration error $\varepsilon$, but the algorithms that attain this rate enumerate the class, which is impossible for the large classes of interest. We ask how many samples suffice when the learner accesses the class only through an empirical risk minimization (ERM) oracle. We give an algorithm that uses $\tilde{O}(d/\varepsilon^{3})$ samples and polynomially many ERM calls, where $d$ is the VC dimension of the class. Its dependence on $\varepsilon$ is optimal for all learners. When $d$ is at least about $1/\varepsilon$, every learner that can only access the class through polynomially many ERM calls needs $\tildeΩ(d/\varepsilon^{3})$ samples. Learners with unlimited computation need only $\tilde{O}(\varepsilon^{-3}+d\varepsilon^{-2})$ samples, so the extra factor $1/\varepsilon$ on the dimension term is the price of oracle efficiency. For swap multicalibration, which allows a different function from the class for each predicted value, $\tildeΘ(d/\varepsilon^{3})$ samples are necessary and sufficient. For estimating the error of a given predictor, the ordinary notion is the harder one: the swap error can be estimated with an ERM oracle, whereas the ordinary error is NP-hard to approximate even for classes with linear-time ERM. Consequently, there are classes for which it is computationally easier to learn a multicalibrated predictor than to compute the multicalibration error of a given predictor.
• Abstract（参考訳）: 予測器は、クラス内のすべてのサブポピュレーションと予測器が出力するすべての値に対して、その値を受け取るサブポピュレーションのメンバーの平均結果が値自身に近い場合、(正式には、監査器と呼ばれる)サブポピュレーションのクラスに対して多重校正される。 有限類に対して、約$\varepsilon^{-3}$サンプルは多重校正誤差$\varepsilon$の予測子を学ぶのに十分である。 学習者が経験的リスク最小化(ERM)のオラクルを通じてのみクラスにアクセスする場合、どのくらいのサンプルが十分であるかを問う。 我々は、$\tilde{O}(d/\varepsilon^{3})$サンプルと多項式的に多くのERM呼び出しを使用するアルゴリズムを与え、$d$はクラスのVC次元である。 $\varepsilon$への依存は、すべての学習者にとって最適である。 d$が少なくとも1/\varepsilon$である場合、多項式的に多くのERM呼び出しを通してクラスにしかアクセスできないすべての学習者は、$\tildeΩ(d/\varepsilon^{3})$サンプルを必要とする。 無制限に計算できる学習者は$\tilde{O}(\varepsilon^{-3}+d\varepsilon^{-2})$サンプルしか必要としないので、次元項の1/\varepsilon$はオラクル効率の値である。 予測値ごとにクラスと異なる関数を許容する多重校正をスワップするためには、$\tilde'(d/\varepsilon^{3})$サンプルが必要である。 与えられた予測子の誤差を推定するために、通常の概念はより難しい: スワップエラーはERMオラクルで推定できるが、通常の誤差は線形時間ERMを持つクラスでもNPハードで近似できる。 その結果、与えられた予測器の多重校正誤差を計算するよりも、計算的にマルチ校正予測器を学習しやすいクラスが存在する。

関連論文リスト

• Sample-Optimal Multi-Group Learning with an ERM Oracle [1.4371100636219536]
  マルチグループ学習では、一つの予測器は各グループのクラスにおいて最も優れた仮説と同等に振る舞う必要がある。 計算が無制限であっても、学習者ごとに$(d_G+d_H)/varepsilon2)$の値が一致することを示す。
  論文  参考訳（メタデータ） (2026-10-11T20:56:51Z)
• Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure [50.58119214447535]
  マスク付き生成モデルは並列トークン予測を提供するが、正確な並列サンプリングはトークンを考慮しなければならない。 本研究は,発見を含む全評価がシーケンス長$N$のサブ線形であるかどうかを考察する。 本研究では, 森林構造を隠蔽した離散分布を, 固定された近似条件オラクルを通してアクセスする。
  論文  参考訳（メタデータ） (2026-09-29T15:39:50Z)
• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Stochastic Autoregressive Learning [14.292982828097465]
  連立自己回帰学習のためのPAC学習モデルを提案する。 自己回帰学習が決定論的理論と根本的に異なることを示す。
  論文  参考訳（メタデータ） (2026-08-07T13:40:17Z)
• Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
  我々は、前のプロパティが固定されたときに各プロパティが識別可能な$k$プロパティの列に対する多重校正について検討する。 多対数的に多くの二元群が存在するにもかかわらず、多重校正誤差$varepsilon$を達成するには$widetilde(varepsilon-(k+2))$サンプルが必要である。
  論文  参考訳（メタデータ） (2026-08-04T23:38:54Z)
• Improved Bounds for Swap Multicalibration and Swap Omniprediction [31.959887895880765]
  我々は,有界線型関数に対する$O(sqrtT)$ $ell_2$-swap多重校正誤差を効率よく実現できることを示す。 また、凸関数とリプシッツ関数のクラスに対して、$varepsilon$-swap omnipredictorを効率的に学習する、$O(varepsilon -3)$サンプル複雑性も確立する。
  論文  参考訳（メタデータ） (2025-05-27T08:29:35Z)
• Robust learning of halfspaces under log-concave marginals [6.852292115526837]
  線形しきい値関数を学習し、境界体積$O(r+varepsilon)$の分類子を半径摂動$r$で返すアルゴリズムを与える。 dtildeO(1/varepsilon2)$の時間とサンプルの複雑さはブール回帰の複雑さと一致する。
  論文  参考訳（メタデータ） (2025-05-19T20:12:16Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。 SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• 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)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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