論文の概要: Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity
- arxiv url: http://arxiv.org/abs/2611.03305v1
- Date: Mon, 02 Nov 2026 15:37:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-06 05:14:59.473794
- Title: Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity
- Title（参考訳）: 校正多重精度:決定論的およびランダム化されたサンプル複雑度
- Abstract要約: 校正された多重精度は、有界なテストファミリに対して、予測器をグローバルに校正し、多重精度にすることを要求する。
キャリブレーションされた多重精度は、決定論的およびランダムな予測器間の真のサンプル・複雑さの分離を示す。
log|G|asympvarepsilon-1では、ランダム化および決定論的多重精度のミニマックスレートは、多重校正のミニマックスレートと一致する。
- 参考スコア（独自算出の注目度）: 10.591062952373553
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Calibrated multiaccuracy asks that a predictor be globally calibrated and multiaccurate with respect to a bounded test family $G$; that is, its residuals should be uncorrelated with every test $g(x)\in G$. This weakening of multicalibration suffices for many applications. Its sample complexity was not known to improve on that of full multicalibration, which is $\widetildeΘ\left(\frac{\log|G|}{\varepsilon^2} + \frac{1}{\varepsilon^{3}}\right)$ when $|G|$ is at least a sufficiently large power of $\log(1/\varepsilon)$. We resolve the sample complexity of $\varepsilon$-calibrated multiaccuracy, showing that it scales as $$ \widetildeΘ\left(\frac{\log|G|}{\varepsilon^2} + \frac{1}{\varepsilon^{5/2}}\right), $$ separating it from the complexity of multicalibration. The upper bound is obtained by an algorithm that outputs a randomized predictor. For deterministic predictors, we establish the tight rate $$ \widetildeΘ\left( \frac{\log|G|}{\varepsilon^2} + \frac{(\log|G|)^{1/3}}{\varepsilon^{8/3}} \right) $$ whenever $\log|G|=Ω(\log(1/\varepsilon))$. When $\log|G|\le\varepsilon^{-1+κ}$ for any fixed $κ\in(0,1)$, this rate is polynomially larger than the rate for randomized predictors. Thus, unlike for multicalibration, calibrated multiaccuracy exhibits a genuine sample-complexity separation between deterministic and randomized predictors. The matching upper and lower bounds show that the unusual cube-root dependence on $\log|G|$ is intrinsic. At $\log|G|\asymp\varepsilon^{-1}$, the minimax rates for randomized and deterministic calibrated multiaccuracy both coincide with the minimax rate for multicalibration.
- Abstract（参考訳）: 校正された多重精度は、予測器を大域的に校正し、有界なテスト族である$G$に対して多重精度にすることを要求する; つまり、その残余はすべてのテスト $g(x)\in G$と無相関でなければならない。
この多重校正の弱さは多くの用途で十分である。
そのサンプルの複雑さは、完全な多重校正では改善されないが、$\widetilde\left(\frac{\log|G|}{\varepsilon^2} + \frac{1}{\varepsilon^{3}}\right)$は、少なくとも$|G|$が$\log(1/\varepsilon)$の十分大きなパワーであるときに、$\widetilde\left(\frac{\log|G|}{\varepsilon^2} + \frac{1}{\varepsilon^{3}}\right)$である。
我々は、$\varepsilon$-calibrated multiaccuracyのサンプル複雑性を解決し、$$$ \widetilde\left(\frac{\log|G|}{\varepsilon^2} + \frac{1}{\varepsilon^{5/2}}\right)とスケールし、$$をマルチキャリブレーションの複雑さから分離することを示した。
上限はランダム化された予測器を出力するアルゴリズムによって得られる。
決定論的予測に対しては、$$ \widetilde\left( \frac {\log|G|}{\varepsilon^2} + \frac{(\log|G|)^{1/3}}{\varepsilon^{8/3}} \right)$$$/$$\log|G|=Ω(\log(1/\varepsilon))$とする。
任意の固定された $κ\in(0,1)$ に対して $\log|G|\le\varepsilon^{-1+κ}$ が与えられたとき、この値はランダム化された予測器の速度よりも多項式的に大きい。
したがって、多重校正とは違って、校正された多重精度は、決定論的およびランダム化予測器間の真のサンプル-複雑分離を示す。
一致する上界と下界は、$\log|G|$に対する特異な立方根依存が本質的であることを示している。
$\log|G|\asymp\varepsilon^{-1}$ では、ランダム化および決定論的校正多重精度のミニマックスレートは、多重校正のミニマックスレートと一致する。
関連論文リスト
- High-dimensional online calibration from harmonic weights [26.94938196315732]
任意の凸集合$YsubseteqmathbbRd$上での多次元予測のオンライン校正について検討する。
我々のアルゴリズムは単純で、各ラウンドで調和的に滑らかな過去の結果に対して調和的に重み付けされた分布を出力する。
論文 参考訳（メタデータ） (2026-10-06T04:36:12Z) - Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
我々は、前のプロパティが固定されたときに各プロパティが識別可能な$k$プロパティの列に対する多重校正について検討する。
多対数的に多くの二元群が存在するにもかかわらず、多重校正誤差$varepsilon$を達成するには$widetilde(varepsilon-(k+2))$サンプルが必要である。
論文 参考訳（メタデータ） (2026-08-04T23:38:54Z) - The Sample Complexity of Fidelity Estimation to a Known Rank-$r$ Reference State Is $\widetildeΘ(r^2/\varepsilon^2)$ [0.0]
量子スペクトル推定の精度を一定に抑えるために、ほぼ四分法以下の$widetilde(r2)$を証明した。
また、量子スペクトル推定を一定精度で行うために、ほぼ四分法以下の$widetilde(r2)$を証明した。
論文 参考訳（メタデータ） (2026-08-03T06:43:01Z) - 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) - Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。
PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
論文 参考訳（メタデータ） (2024-10-10T06:15:42Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - The Price of Tolerance in Distribution Testing [31.10049510641336]
サンプルの複雑さは [fracsqrtnvarepsilon2 + fracnlog n cdotmaxleftfracvarepsilon2 であることが示され、この2つの既知事例の間に円滑なトレードオフをもたらす。
また、p$ と$q$ の両方が未知である寛容同値検定の問題についても同様の特徴を与える。
論文 参考訳（メタデータ） (2021-06-25T03:59:42Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。