論文の概要: Sample Complexity of Multicalibration for Multilevel Properties
- arxiv url: http://arxiv.org/abs/2608.04288v1
- Date: Tue, 04 Aug 2026 23:38:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-06 14:48:43.66186
- Title: Sample Complexity of Multicalibration for Multilevel Properties
- Title（参考訳）: マルチレベル特性のためのマルチキャリブレーションのサンプル複雑さ
- Authors: Jiuyao Lu, Krishnakumar Balasubramanian, Aleksandr Podkopaev, Shiva Prasad Kasiviswanathan,
- Abstract要約: 我々は、前のプロパティが固定されたときに各プロパティが識別可能な$k$プロパティの列に対する多重校正について検討する。
多対数的に多くの二元群が存在するにもかかわらず、多重校正誤差$varepsilon$を達成するには$widetilde(varepsilon-(k+2))$サンプルが必要である。
- 参考スコア（独自算出の注目度）: 52.27687531970317
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Calibration requires a predictor to be unbiased after conditioning on its own predictions. Multicalibration asks for this guarantee simultaneously across a collection of groups. Many prediction tasks ask for several related features of the same conditional outcome distribution: variance is defined relative to the mean, skewness relative to both mean and variance, and conditional value at risk relative to a quantile. We study multicalibration for a sequence of $k$ properties in which each property is identifiable once the preceding properties are fixed. This framework includes Bayes pairs but does not require the properties to arise from a single loss. For every fixed $k\ge2$, we establish matching upper and lower sample-complexity bounds up to logarithmic factors under regularity conditions. Even with only polylogarithmically many binary groups, achieving multicalibration error $\varepsilon$ requires $\widetildeΩ(\varepsilon^{-(k+2)})$ samples. Conversely, for any finite group family $\mathcal G$, we give a randomized learner using $O(\varepsilon^{-(k+2)}+\varepsilon^{-2}\log|\mathcal G|)$ samples. Thus the sample complexity is $\widetildeΘ(\varepsilon^{-(k+2)})$ for polynomial-size group families. We instantiate the theory for three canonical examples.
- Abstract（参考訳）: キャリブレーションは、予測器が自身の予測を条件付けした後、バイアスを取らなければならない。
マルチキャリブレーションは、この保証を複数のグループに同時に要求する。
多くの予測タスクは、同じ条件付き結果分布のいくつかの関連する特徴を要求している: 分散は平均に対して、平均と分散の両方に対して、歪度は平均と分散に対して、そして、量子化に対するリスクにおいて、条件付き値が定義される。
我々は、前のプロパティが固定されたときに各プロパティが識別可能な$k$プロパティの列に対する多重校正について検討する。
このフレームワークはベイズ対を含むが、1つの損失から生じる性質を必要としない。
固定された $k\ge2$ に対して、正則性条件下での対数的因子に上限付けられた上と下のサンプル-複素性を確立する。
多対数的に多くの二元群が存在するにもかかわらず、多重校正誤差$\varepsilon$を達成するには$\widetildeΩ(\varepsilon^{-(k+2)})$サンプルが必要である。
逆に、任意の有限群族 $\mathcal G$ に対して、$O(\varepsilon^{-(k+2)}+\varepsilon^{-2}\log|\mathcal G|)$サンプルを用いてランダムに学習する。
したがって、サンプルの複雑さは多項式サイズの群族に対して$\widetilde'(\varepsilon^{-(k+2)})$である。
3つの正準例についてその理論をインスタンス化する。
関連論文リスト
- Is Spurious Correlation Removal Always Learnable? [56.28155520961125]
不変学習は、構造が統計的に識別可能であっても失敗することがある。
ブラックボックスサンプリング可能な教師付きスパースリカバリプリミティブの下では、実証可能な多次元環境が存在する。
合成および実際のデータセットは、予測されたギャップと遷移を示し、単純な多様性診断を動機付ける。
論文 参考訳（メタデータ） (2026-06-11T05:49:43Z) - Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。
これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
論文 参考訳（メタデータ） (2026-05-22T15:05:33Z) - The Sample Complexity of Multicalibration [9.852468478532652]
バッチ設定におけるマルチキャリブレーションのミニマックスサンプル複雑性について検討する。
学習者は未知の分布からサンプルを$n$ i.i.d.d.で観測し、予想エラー(ECE)によって測定された集団の多重校正誤差が与えられたグループに対して少なくとも$varepsilon$である予測器を出力しなければならない。
重み付き$L_p$マルチキャリブレーションの計量を1le p le 2$, 最適3/p$に対して設定する。
論文 参考訳（メタデータ） (2026-04-23T17:59:01Z) - The Sample Complexity of Simple Binary Hypothesis Testing [7.127829790714167]
単純な二項仮説テストのサンプルの複雑さは、いずれの設定でも$p$と$q$の2つの分布を区別するのに必要となる最小のi.d.サンプルである。
i) all $0 le alpha, beta le 1/8$ in the pre-free set, and (ii) all $delta le pi/4$ in the Bayesian set。
論文 参考訳（メタデータ） (2024-03-25T17:42:32Z) - Testing with Non-identically Distributed Samples [19.421846478881363]
本研究では,サンプルが独立に分布するが同一に分布しない設定に対して,サブ線形サンプル特性試験と推定が適用範囲について検討する。
それぞれの分布から$c=1$のサンプルが与えられた場合、$k$の線形なサンプル数が必要であることを示す。
2つの分布の「クローズネス」をテストする問題に我々の手法を拡張します。
論文 参考訳（メタデータ） (2023-11-19T01:25:50Z) - 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) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。