論文の概要: Multicalibration yields better matchings

• arxiv url: http://arxiv.org/abs/2511.11413v1
• Date: Fri, 14 Nov 2025 15:45:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-17 22:42:18.689443
• Title: Multicalibration yields better matchings
• Title（参考訳）: 多重校正はより良いマッチングをもたらす
• Authors: Riccardo Colini Baldeschi, Simone Di Gregorio, Simone Fioravanti, Federico Fusco, Ido Guy, Daniel Haimovich, Stefano Leonardi, Fridolin Linder, Lorenzo Perini, Matteo Russo, Niek Tax,
• Abstract要約: 不完全な予測器が与えられた場合、最適下決定規則は誘導された誤りを補うことができ、したがって標準最適規則よりも優れる。 以下のプロパティで、特定のマルチキャリブレーションされた予測子$hat $を構築する方法を示す。 hat $の出力に基づいて最適なマッチングを選択することは、オリジナルの予測子に適用された$mathcal C$の最良の決定ルールと競合する。
• 参考スコア（独自算出の注目度）: 18.479215073073693
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Consider the problem of finding the best matching in a weighted graph where we only have access to predictions of the actual stochastic weights, based on an underlying context. If the predictor is the Bayes optimal one, then computing the best matching based on the predicted weights is optimal. However, in practice, this perfect information scenario is not realistic. Given an imperfect predictor, a suboptimal decision rule may compensate for the induced error and thus outperform the standard optimal rule. In this paper, we propose multicalibration as a way to address this problem. This fairness notion requires a predictor to be unbiased on each element of a family of protected sets of contexts. Given a class of matching algorithms $\mathcal C$ and any predictor $γ$ of the edge-weights, we show how to construct a specific multicalibrated predictor $\hat γ$, with the following property. Picking the best matching based on the output of $\hat γ$ is competitive with the best decision rule in $\mathcal C$ applied onto the original predictor $γ$. We complement this result by providing sample complexity bounds.
• Abstract（参考訳）: 基礎となる文脈に基づいて、実際の確率重みの予測にのみアクセス可能な重み付きグラフのベストマッチングを見つける問題を考える。 予測器がベイズ最適であれば、予測重みに基づく最良のマッチングを計算するのが最適である。 しかし、実際には、この完璧な情報シナリオは現実的ではありません。 不完全な予測器が与えられた場合、最適下決定規則は誘導された誤りを補うことができ、したがって標準最適規則よりも優れる。 本稿では,この問題に対処する手段として,マルチキャリブレーションを提案する。 この公平性の概念は、予測者が保護されたコンテキストの集合の族の各要素に偏りを持たない必要がある。 マッチングアルゴリズムのクラスが$\mathcal C$と任意の予測器が$γ$のエッジウェイトを与えられた場合、以下の特性を持つ特定の多重校正予測器$\hat γ$を構築する方法を示す。 最高のマッチングを$\hat γ$の出力に基づいて選択することは、オリジナルの予測子に$\mathcal C$を適用した場合の最良の決定ルールと競合する。 この結果を補うために、サンプルの複雑性境界を提供する。

関連論文リスト

• Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment [54.787826863212146]
  推論時間計算は、言語モデルのパフォーマンスをスケールするための強力な軸を提供する。 我々は, (i) 応答品質, (ii) 計算量の観点から, 推論時アライメントアルゴリズムの性能を解析する。 我々は$textttInferenceTimePessimism$を紹介した。これは推論時間計算の故意使用を通じて報酬ハッキングを緩和する新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2025-03-27T18:00:08Z)
• Fair Secretaries with Unfair Predictions [12.756552522270198]
  予測値が少なくとも$maxOmega (1), 1 - O(epsilon)$倍の候補を受け入れることを約束しているにもかかわらず、アルゴリズムが最良の候補を受け入れる確率がゼロであることを示し、ここでは$epsilon$が予測誤差である。 私たちのアルゴリズムと分析は、既存の作業から分岐し、結果のいくつかを単純化/統一する、新たな"ペギング(pegging)"アイデアに基づいている。
  論文  参考訳（メタデータ） (2024-11-15T00:23:59Z)
• Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
  本稿では,閾値演算による予測値がS$変化の程度を測るマージン補数の概念を導入する。 適切な因果仮定の下では、予測スコア$S$に対する$X$の影響は、真の結果$Y$に対する$X$の影響に等しいことを示す。
  論文  参考訳（メタデータ） (2024-05-24T11:22:19Z)
• Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits [85.27420062094086]
  Implicitly Normalized Forecaster (INF) は、敵対的マルチアームバンディット(MAB)問題に対する最適解であると考えられている。 重み付き設定のMAB問題に対するクリッピング(INFclip)を用いたINFの新バージョン"Implicitly Normalized Forecaster"を提案する。 INFclipは線形重み付きMAB問題に対して最適であり、非線形問題に対して有効であることを示す。
  論文  参考訳（メタデータ） (2023-05-11T12:00:43Z)
• Mixing predictions for online metric algorithms [34.849039387367455]
  我々は予測を組み合わせるアルゴリズムを設計し、このような動的組み合わせと競合する。 我々のアルゴリズムは、バンディットのような方法で予測者にアクセスするように適応することができ、一度に1つの予測者しかクエリできない。 我々の下界の1つが予想外の意味を持つのは、$k$-server問題に対する定式化のカバーに関する新しい構造的洞察である。
  論文  参考訳（メタデータ） (2023-04-04T13:18:00Z)
• Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
  多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。 我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。 V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-19T01:09:24Z)
• Online Optimization with Untrusted Predictions [7.895232155155041]
  本稿では, オンライン最適化の課題について検討し, 意思決定者は, ラウンドごと, 非競争的打撃コスト, ラウンド間切替コストの合計に対して, 一般的な計量空間内の点を選択する必要がある。 本稿では,新しいアルゴリズムであるAdaptive Online Switching (AOS)を提案し,予測が完全であれば$tildecalO(alphadelta)$が不正確であっても$tildecalO(alphadelta)$であることを示す。
  論文  参考訳（メタデータ） (2022-02-07T21:08:02Z)
• Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations [78.23408201652984]
  トップk予測は、マシンラーニング・アズ・ア・サービス、レコメンダ・システム、Web検索など、多くの現実世界のアプリケーションで使用されている。 我々の研究はランダム化平滑化に基づいており、入力をランダム化することで、証明可能なロバストな分類器を構築する。 例えば、攻撃者がテスト画像の5ピクセルを任意に摂動できる場合に、ImageNet上で69.2%の認定トップ3精度を達成する分類器を構築することができる。
  論文  参考訳（メタデータ） (2020-11-15T21:34:44Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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