論文の概要: The Sample Complexity of Multicalibration

• arxiv url: http://arxiv.org/abs/2604.21923v1
• Date: Thu, 23 Apr 2026 17:59:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-24 14:40:06.823102
• Title: The Sample Complexity of Multicalibration
• Title（参考訳）: マルチキャリブレーションのサンプル複雑さ
• Authors: Natalie Collina, Jiuyao Lu, Georgy Noarov, Aaron Roth,
• Abstract要約: バッチ設定におけるマルチキャリブレーションのミニマックスサンプル複雑性について検討する。 学習者は未知の分布からサンプルを$n$ i.i.d.d.で観測し、予想エラー(ECE)によって測定された集団の多重校正誤差が与えられたグループに対して少なくとも$varepsilon$である予測器を出力しなければならない。 重み付き$L_p$マルチキャリブレーションの計量を1le p le 2$, 最適3/p$に対して設定する。
• 参考スコア（独自算出の注目度）: 9.852468478532652
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the minimax sample complexity of multicalibration in the batch setting. A learner observes $n$ i.i.d. samples from an unknown distribution and must output a (possibly randomized) predictor whose population multicalibration error, measured by Expected Calibration Error (ECE), is at most $\varepsilon$ with respect to a given family of groups. For every fixed $κ> 0$, in the regime $|G|\le \varepsilon^{-κ}$, we prove that $\widetildeΘ(\varepsilon^{-3})$ samples are necessary and sufficient, up to polylogarithmic factors. The lower bound holds even for randomized predictors, and the upper bound is realized by a randomized predictor obtained via an online-to-batch reduction. This separates the sample complexity of multicalibration from that of marginal calibration, which scales as $\widetildeΘ(\varepsilon^{-2})$, and shows that mean-ECE multicalibration is as difficult in the batch setting as it is in the online setting, in contrast to marginal calibration which is strictly more difficult in the online setting. In contrast we observe that for $κ= 0$, the sample complexity of multicalibration remains $\widetildeΘ(\varepsilon^{-2})$ exhibiting a sharp threshold phenomenon. More generally, we establish matching upper and lower bounds, up to polylogarithmic factors, for a weighted $L_p$ multicalibration metric for all $1 \le p \le 2$, with optimal exponent $3/p$. We also extend the lower-bound template to a regular class of elicitable properties, and combine it with the online upper bounds of Hu et al. (2025) to obtain matching bounds for calibrating properties including expectiles and bounded-density quantiles.
• Abstract（参考訳）: バッチ設定におけるマルチキャリブレーションのミニマックスサンプル複雑性について検討する。 学習者は未知の分布からサンプルを$n$ i.i.d.d.で観測し、集団の族に対して少なくとも$\varepsilon$である(おそらくランダム化される)予測器を出力しなければならない。 すべての固定された $κ> 0$ に対して、体制 $|G|\le \varepsilon^{-κ}$ において、$\widetilde'(\varepsilon^{-3})$ のサンプルが必要で十分であることが証明される。 下界はランダム化された予測器に対しても保持され、上界はオンライン・バッチ・リダクションによって得られたランダム化された予測器によって実現される。 これは、マルチキャリブレーションのサンプルの複雑さと、$\widetilde'(\varepsilon^{-2})$のスケールの限界キャリブレーションの複雑さを区別し、オンライン設定では、オンライン設定のようにバッチ設定では平均ECEマルチキャリブレーションが困難であることを示し、オンライン設定では厳密に難しい限界キャリブレーションとは対照的に、バッチ設定では平均ECEマルチキャリブレーションが困難であることを示している。 対照的に、$κ= 0$ の場合、多重校正のサンプルの複雑さは、鋭いしきい値現象を示す$\widetilde'(\varepsilon^{-2})$ のままである。 より一般的には、重み付き$L_p$マルチキャリブレーション計量に対して、最大で3/p$の最適指数を持つ上界と下界の整合性を確立する。 また、下界テンプレートを通常の利得可能な性質のクラスに拡張し、Hu et al (2025) のオンライン上界と組み合わせて、期待値や有界密度量子量を含む特性を校正するための整合境界を求める。

関連論文リスト

• Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes [32.65125292684608]
  ランダム化しきい値クエリのみに基づく適応型平均推定器を提案する。 我々の推定器のサンプル複雑性は、余分な乗法的な$O(log(/))$ペナルティを持つ。 しきい値クエリとより一般的な間隔クエリの両方において、任意の非適応推定器のサンプル複雑性は線形にスケールしなければならない。
  論文  参考訳（メタデータ） (2026-04-09T04:49:21Z)
• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  自己蒸留(英: Self-distillation, SD)とは、教師自身の予測と地道の混合で学生を訓練する過程である。 任意の予測リスクに対して、各正規化レベルにおいて、最適に混合された学生がリッジ教師に改善されることが示される。 本稿では,グリッド探索やサンプル分割,再構成なしに$star$を推定する一貫したワンショットチューニング手法を提案する。
  論文  参考訳（メタデータ） (2026-02-19T17:21:15Z)
• Optimal Lower Bounds for Online Multicalibration [9.852468478532652]
  期待される多重校正誤差に対して$(T2/3)$低い境界を3つの非結合二元群を用いて証明する。 次に、文脈に依存するが学習者の予測には依存しない群関数のより難しい場合の下位境界に目を向ける。
  論文  参考訳（メタデータ） (2026-01-08T18:59:32Z)
• Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity [32.65125292684608]
  1ビット通信制約を用いた分散平均推定問題について検討する。 私たちの推定器は、有界平均$-lambda le mathbbE(X) le lambda $)と変数$mathrmVar(X) le sigma2$)を持つすべてのディストリビューションに対して$(epsilon, delta)$-PACです。
  論文  参考訳（メタデータ） (2025-09-26T06:22:57Z)
• Settling the Sample Complexity of Model-Based Offline Reinforcement Learning [50.5790774201146]
  オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。 事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。 モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
  論文  参考訳（メタデータ） (2022-04-11T17:26:19Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)
• Private Mean Estimation of Heavy-Tailed Distributions [10.176795938619417]
  差分的にプライベートな分布の平均推定におけるミニマックスサンプルの複雑さについて, 新たな上限値と下限値を与える。 $n = Thetaleft(frac1alpha2 + frac1alphafrack-1varepsilonright)$サンプルは必要で、$varepsilon$-differential privacyの下で$alpha$-accuracyと見積もるのに十分である。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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