論文の概要: Optimal Deterministic Multicalibration and Omniprediction

• arxiv url: http://arxiv.org/abs/2606.20557v1
• Date: Thu, 18 Jun 2026 17:59:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-19 18:23:40.053695
• Title: Optimal Deterministic Multicalibration and Omniprediction
• Title（参考訳）: 最適決定論的多重校正とOmniprediction
• Authors: Georgy Noarov, Aaron Roth,
• Abstract要約: モデルが校正された場合、群重みの集合に$G$で多重校正される。 決定論的予測子は、ミニマックス最適$widetilde O(varepsilon-3)$ sample complexity rateに達することが知られている。
• 参考スコア（独自算出の注目度）: 11.731410573120856
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A model is multicalibrated on a collection of group weights $G$ if it is calibrated -- i.e. unbiased even conditional on its prediction -- not just overall, but also after reweighting contexts by each $g \in G$. It is a useful property for many downstream applications and is a basic desideratum of trustworthy machine learning. Before this work, all predictors known to attain the minimax-optimal $\widetilde O(\varepsilon^{-3})$ sample complexity rate for $\varepsilon$-multicalibration were randomized, while deterministic predictors were known only with substantially worse sample complexity. Whether randomization is necessary for optimal sample complexity in multicalibration was explicitly asked by [CLNR26] and implicitly in several prior works. We resolve this open problem by giving a minimax-optimal multicalibration algorithm that outputs a deterministic predictor. We then generalize the algorithm to produce optimal deterministic predictors that satisfy outcome indistinguishability (OI) with respect to finite or finitely covered collections of tests. As an application, this also gives deterministic omnipredictors and panpredictors with optimal sample complexity, resolving open problems posed by [OKK25] and [BHHLZ25].
• Abstract（参考訳）: モデルが群重みの集合上で多重校正されるのは、それが校正された場合、つまり、その予測に条件付きでも偏りがない場合、G$であり、また、各$g \in G$によるコンテキストの再重み付けの後にである。 多くのダウンストリームアプリケーションにとって有用な特性であり、信頼できる機械学習の基本的なデシラタムである。 この研究の前には、すべての予測器が極小最大値=\widetilde O(\varepsilon^{-3})$サンプルの複雑さ率を$\varepsilon$-multicalibrationの確率化し、決定論的予測器はより悪いサンプルの複雑さでしか知られていなかった。 マルチキャリブレーションにおける最適なサンプル複雑性にランダム化が必要かどうかを, [CLNR26] によって明示的に問うとともに, いくつかの先行研究において暗黙的に問うた。 我々は,決定論的予測器を出力する最小最適多重校正アルゴリズムを提供することにより,この問題を解決する。 次にアルゴリズムを一般化して、有限あるいは有限にカバーされたテストの集合に対して、結果の不一致(OI)を満たす最適な決定論的予測子を生成する。 応用として、このことは [OKK25] と [BHHLZ25] によって引き起こされるオープンな問題を解決し、最適なサンプルの複雑さを持つ決定論的全予測子と汎予測子を与える。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Multicalibration yields better matchings [18.479215073073693]
  不完全な予測器が与えられた場合、最適下決定規則は誘導された誤りを補うことができ、したがって標準最適規則よりも優れる。 以下のプロパティで、特定のマルチキャリブレーションされた予測子$hat $を構築する方法を示す。 hat $の出力に基づいて最適なマッチングを選択することは、オリジナルの予測子に適用された$mathcal C$の最良の決定ルールと競合する。
  論文  参考訳（メタデータ） (2025-11-14T15:45:07Z)
• Efficiently Solving Discounted MDPs with Predictions on Transition Matrices [6.199300239433395]
  生成モデルに基づくDMDP(Discounted Markov Decision Processs)について検討した。 DMDPの解法において,遷移行列上での予測がサンプル効率をいかに向上させるかを検討するための新しい枠組みを提案する。
  論文  参考訳（メタデータ） (2025-02-21T09:59:46Z)
• Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications [79.53938312089308]
  MIDX-Samplerは、逆多重インデックスアプローチに基づく新しい適応型サンプリング戦略である。 本手法は, サンプリングバイアス, 勾配バイアス, 収束速度, 一般化誤差境界などの重要な問題に対処するため, 厳密な理論的解析によって裏付けられている。
  論文  参考訳（メタデータ） (2025-01-15T04:09:21Z)
• Optimal Algorithms for Augmented Testing of Discrete Distributions [25.818433126197036]
  予測器は3つのプロパティテストタスクすべてに必要なサンプル数を実際に削減できることを示す。 我々のアルゴリズムの重要な利点は、予測の精度への適応性である。 アルゴリズムによって達成されるサンプルの複雑さの改善は、情報理論的に最適であることを示すために、より低い境界を提供する。
  論文  参考訳（メタデータ） (2024-12-01T21:31:22Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Conformalization of Sparse Generalized Linear Models [2.1485350418225244]
  等角予測法は、任意の有限サンプルサイズに対して有効である$y_n+1$の信頼セットを推定する。 魅力的ではあるが、そのような集合の計算は多くの回帰問題において計算不可能である。 経路追従アルゴリズムが共形予測集合を正確に近似する方法を示す。
  論文  参考訳（メタデータ） (2023-07-11T08:36:12Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Stochastic Proximal Gradient Algorithm with Minibatches. Application to Large Scale Learning Models [2.384873896423002]
  非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。 我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
  論文  参考訳（メタデータ） (2020-03-30T10:43:56Z)

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

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