論文の概要: Efficient Swap Multicalibration of Elicitable Properties

• arxiv url: http://arxiv.org/abs/2511.04907v1
• Date: Fri, 07 Nov 2025 01:14:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-10 21:00:44.635382
• Title: Efficient Swap Multicalibration of Elicitable Properties
• Title（参考訳）: 有効スワップ多重校正法
• Authors: Lunjia Hu, Haipeng Luo, Spandan Senapati, Vatsal Sharan,
• Abstract要約: [NR23] は任意のプロパティのマルチキャリブレーションとプロパティのエリケーションとの間に驚くべき関係を確立しました。 本稿では,グループメンバシップ関数から任意の有界仮説クラスへの帰納的プロパティに対する多重校正を一般化する。
• 参考スコア（独自算出の注目度）: 41.64272548564929
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multicalibration [HJKRR18] is an algorithmic fairness perspective that demands that the predictions of a predictor are correct conditional on themselves and membership in a collection of potentially overlapping subgroups of a population. The work of [NR23] established a surprising connection between multicalibration for an arbitrary property $\Gamma$ (e.g., mean or median) and property elicitation: a property $\Gamma$ can be multicalibrated if and only if it is elicitable, where elicitability is the notion that the true property value of a distribution can be obtained by solving a regression problem over the distribution. In the online setting, [NR23] proposed an inefficient algorithm that achieves $\sqrt T$ $\ell_2$-multicalibration error for a hypothesis class of group membership functions and an elicitable property $\Gamma$, after $T$ rounds of interaction between a forecaster and adversary. In this paper, we generalize multicalibration for an elicitable property $\Gamma$ from group membership functions to arbitrary bounded hypothesis classes and introduce a stronger notion -- swap multicalibration, following [GKR23]. Subsequently, we propose an oracle-efficient algorithm which, when given access to an online agnostic learner, achieves $T^{1/(r+1)}$ $\ell_r$-swap multicalibration error with high probability (for $r\ge2$) for a hypothesis class with bounded sequential Rademacher complexity and an elicitable property $\Gamma$. For the special case of $r=2$, this implies an oracle-efficient algorithm that achieves $T^{1/3}$ $\ell_2$-swap multicalibration error, which significantly improves on the previously established bounds for the problem [NR23, GMS25, LSS25a], and completely resolves an open question raised in [GJRR24] on the possibility of an oracle-efficient algorithm that achieves $\sqrt{T}$ $\ell_2$-mean multicalibration error by answering it in a strongly affirmative sense.
• Abstract（参考訳）: マルチキャリブレーション[HJKRR18]は、予測器の予測が自身で正しい条件付きであり、集団の潜在的重複するサブグループの集合におけるメンバシップを要求するアルゴリズムフェアネスの観点である。 NR23] の作業は、任意のプロパティに対する多重校正(平均値または中央値)とプロパティの校正(英語版)の間の驚くべき接続を確立した: プロパティ $\Gamma$ がマルチ校正可能であることと、それが指定可能である場合に限り、そのディストリビューションの真のプロパティ値が分布上の回帰問題を解くことによって得られるという概念である。 オンライン設定では、[NR23] は、グループメンバーシップ関数の仮説クラスと、予測者と敵対者の間の相互作用のラウンドの後に、$\Gamma$に対する$\sqrt T$$\ell_2$-multicalibration誤差を達成する非効率アルゴリズムを提案した。 本稿では,グループメンバシップ関数から任意の有界仮説クラスへの帰納性$\Gamma$に対する多重校正を一般化し,[GKR23]に従うようなより強い概念を導入する。 次に,オンライン学習者へのアクセスが与えられると,有界な逐次ラデマッハ複雑性を持つ仮説クラスに対して,高い確率でT^{1/(r+1)}$$$\ell_r$-swap多重校正誤差(r\ge2$)を達成できるオラクル効率アルゴリズムを提案する。 例えば$r=2$の場合、これは$T^{1/3}$$\ell_2$-swap多重校正誤差を達成し、問題[NR23, GMS25, LSS25a]の既定境界を著しく改善し、$\sqrt{T}$$$\ell_2$-mean多重校正誤差を強く肯定的な意味で答えることで、[GJRR24]で提起された開問題を完全に解決するオラクル効率アルゴリズムを意味する。

関連論文リスト

• Improved Bounds for Swap Multicalibration and Swap Omniprediction [31.959887895880765]
  我々は,有界線型関数に対する$O(sqrtT)$ $ell_2$-swap多重校正誤差を効率よく実現できることを示す。 また、凸関数とリプシッツ関数のクラスに対して、$varepsilon$-swap omnipredictorを効率的に学習する、$O(varepsilon -3)$サンプル複雑性も確立する。
  論文  参考訳（メタデータ） (2025-05-27T08:29:35Z)
• Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Bias [21.64772960240025]
  問題の次元が$d$になるにつれて、所望の誤差内で収束を保証するのに必要なイテレーションの数が増加することを示す。 私たちが取り組んだ重要な技術的課題は、収束を測定するための$W_2,ellinfty$メートル法に一段階の縮約性がないことである。
  論文  参考訳（メタデータ） (2024-08-20T01:24:54Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。 3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。 我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• The Scope of Multicalibration: Characterizing Multicalibration via Property Elicitation [12.197909808303411]
  連続スカラー分布特性に対して$Gamma$ と $Gamma$ が選択可能である場合に限り、多重校正予測器を作成可能であることを示す。 負の面から、非楕円性連続特性に対して、真の分布予測器でさえ校正されない単純なデータ分布が存在することを示す。
  論文  参考訳（メタデータ） (2023-02-16T18:59:16Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Conditional Uncorrelation and Efficient Non-approximate Subset Selection in Sparse Regression [72.84177488527398]
  相関性の観点からスパース回帰を考察し,条件付き非相関式を提案する。 提案手法により、計算複雑性は、スパース回帰における各候補部分集合に対して$O(frac16k3+mk2+mkd)$から$O(frac16k3+frac12mk2)$に削減される。
  論文  参考訳（メタデータ） (2020-09-08T20:32:26Z)

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

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