論文の概要: Computational and Statistical Hardness of Calibration Distance

• arxiv url: http://arxiv.org/abs/2603.18391v1
• Date: Thu, 19 Mar 2026 01:21:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-20 17:19:05.901194
• Title: Computational and Statistical Hardness of Calibration Distance
• Title（参考訳）: 校正距離の計算と統計的硬度
• Authors: Mingda Qiao,
• Abstract要約: キャリブレーションからの距離は確率予測器の誤校正の中心尺度として現れている。 分布が一様でノイズのないラベルを持つ場合, キャリブレーション距離を正確に計算するアルゴリズムを提案する。 意外なことに、2つの仮定のどちらかが取り除かれると、問題は$mathsfNP-hardになる。
• 参考スコア（独自算出の注目度）: 5.990174495635325
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The distance from calibration, introduced by Błasiok, Gopalan, Hu, and Nakkiran (STOC 2023), has recently emerged as a central measure of miscalibration for probabilistic predictors. We study the fundamental problems of computing and estimating this quantity, given either an exact description of the data distribution or only sample access to it. We give an efficient algorithm that exactly computes the calibration distance when the distribution has a uniform marginal and noiseless labels, which improves the $O(1/\sqrt{|\mathcal{X}|})$ additive approximation of Qiao and Zheng (COLT 2024) for this special case. Perhaps surprisingly, the problem becomes $\mathsf{NP}$-hard when either of the two assumptions is removed. We extend our algorithm to a polynomial-time approximation scheme for the general case. For the estimation problem, we show that $Θ(1/ε^3)$ samples are sufficient and necessary for the empirical calibration distance to be upper bounded by the true distance plus $ε$. In contrast, a polynomial dependence on the domain size -- incurred by the learning-based baseline -- is unavoidable for two-sided estimation. Our positive results are based on simple sparsifications of both the distribution and the target predictor, which significantly reduce the search space for computation and lead to stronger concentration for the estimation problem. To prove the hardness results, we introduce new techniques for certifying lower bounds on the calibration distance -- a problem that is hard in general due to its $\textsf{co-NP}$-completeness.
• Abstract（参考訳）: Błasiok、Gopalan、Hu、Nakkiran(STOC 2023)によって導入された校正からの距離は、最近、確率的予測器の誤校正の中心尺度として現れている。 データ分布を正確に記述するか、サンプルアクセスのみを考慮し、計算の基本的問題を調査し、この量を推定する。 分布が一様でノイズのないラベルを持つ場合のキャリブレーション距離を精度よく計算し、この特別の場合、$O(1/\sqrt{|\mathcal{X}|})$ Qiao と Zheng (COLT 2024) の加算近似を改善する。 意外なことに、どちらの仮定も取り除かれると、問題は$\mathsf{NP}$-hardとなる。 一般の場合の多項式時間近似スキームにアルゴリズムを拡張する。 推定問題に対しては,実距離と実距離で上界する経験的校正距離が$ε$となるためには,$1/ε^3)$サンプルが十分かつ必要であることを示す。 対照的に、学習ベースラインによって引き起こされる領域サイズへの多項式依存は、二面推定では避けられない。 我々の正の結果は、分布と目標予測器の両方の単純なスパース化に基づいており、計算の探索空間を著しく減らし、推定問題に対するより強い集中をもたらす。 硬度の結果を証明するために、キャリブレーション距離の低い境界を証明するための新しい手法を導入する。

関連論文リスト

• High-dimensional estimation with missing data: Statistical and computational limits [13.480462575790334]
  我々は,観測結果が欠落したデータである場合の集団パラメータの計算効率を考察する。 平均$ell$法則で推定すると、常に汚染される$in (0, 1)$, (大まかに)$n gtrsim d e1/2$のサンプルは必要となる。 観測結果の欠如により線形回帰に転換し、そのようなギャップが持続しないことを示す。
  論文  参考訳（メタデータ） (2026-03-17T16:02:41Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。 得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
  論文  参考訳（メタデータ） (2025-12-01T02:52:33Z)
• Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor [9.37782111672415]
  分布の密度をサンプルから推定することは統計学の基本的な問題である。 仮説選択は、サンプルセットに加えて、$n$の候補分布が与えられる設定に対処する。 本稿では,仮説の数に関して,ほぼ直線時間で実行される中央モデルに差分プライベートなアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-01T20:46:46Z)
• Nystr\"om Kernel Mean Embeddings [92.10208929236826]
  Nystr"om法に基づく効率的な近似手法を提案する。 サブサンプルサイズの条件は標準の$n-1/2$レートを得るのに十分である。 本稿では,この結果の最大誤差と二次規則の近似への応用について論じる。
  論文  参考訳（メタデータ） (2022-01-31T08:26:06Z)
• Distributed Sparse Regression via Penalization [5.990069843501885]
  エージェントのネットワーク上の線形回帰を、(集中ノードを持たない)無向グラフとしてモデル化する。 推定問題は、局所的なLASSO損失関数の和とコンセンサス制約の2次ペナルティの最小化として定式化される。 本稿では, ペナル化問題に適用した近似勾配アルゴリズムが, 集中的な統計的誤差の順序の許容値まで線形に収束することを示す。
  論文  参考訳（メタデータ） (2021-11-12T01:51:50Z)
• 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)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

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

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