論文の概要: Provably Adaptive Linear Approximation for the Shapley Value and Beyond

• arxiv url: http://arxiv.org/abs/2604.08438v1
• Date: Thu, 09 Apr 2026 16:38:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-10 18:34:06.028265
• Title: Provably Adaptive Linear Approximation for the Shapley Value and Beyond
• Title（参考訳）: Shapley値とBeyondに対する確率適応線形近似
• Authors: Weida Li, Yaoliang Yu, Bryan Kian Hsiang Low,
• Abstract要約: 基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
• 参考スコア（独自算出の注目度）: 73.0940890296463
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Shapley value, and its broader family of semi-values, has received much attention in various attribution problems. A fundamental and long-standing challenge is their efficient approximation, since exact computation generally requires an exponential number of utility queries in the number of players $n$. To meet the challenges of large-scale applications, we explore the limits of efficiently approximating semi-values under a $Θ(n)$ space constraint. Building upon a vector concentration inequality, we establish a theoretical framework that enables sharper query complexities for existing unbiased randomized algorithms. Within this framework, we systematically develop a linear-space algorithm that requires $O(\frac{n}{ε^{2}}\log\frac{1}δ)$ utility queries to ensure $P(\|\hat{\boldsymbolφ}-\boldsymbolφ\|_{2}\geqε)\leq δ$ for all commonly used semi-values. In particular, our framework naturally bridges OFA, unbiased kernelSHAP, SHAP-IQ and the regression-adjusted approach, and definitively characterizes when paired sampling is beneficial. Moreover, our algorithm allows explicit minimization of the mean square error for each specific utility function. Accordingly, we introduce the first adaptive, linear-time, linear-space randomized algorithm, Adalina, that theoretically achieves improved mean square error. All of our theoretical findings are experimentally validated.
• Abstract（参考訳）: シェープリーの価値とそのより広範な半値の族は、様々な帰属問題に多くの注目を集めている。 厳密な計算は一般にプレイヤー数$n$で指数関数的な数のユーティリティクエリを必要とするため、基本的で長期にわたる課題は効率のよい近似である。 大規模応用の課題に対処するため、我々は半値の効率的な近似の限界を、空間の制約として$(n)$ で検討する。 ベクトル集中の不等式に基づいて、既存の非バイアスランダム化アルゴリズムに対してよりシャープなクエリ複雑化を可能にする理論的枠組みを確立する。 このフレームワーク内では、一般に使用されるすべての半値に対して、$O(\frac{n}{ε^{2}}\log\frac{1}δ)$ユーティリティクエリーを必要とし、$P(\|\hat{\boldsymbolφ}-\boldsymbolφ\|_{2}\geqε)\leq δ$を保証する線形空間アルゴリズムを体系的に開発する。 特に,本フレームワークはOFA,非バイアスカーネルSHAP,SHAP-IQ,レグレッション調整アプローチを自然にブリッジし,ペアサンプリングが有用である場合に決定的に特徴付ける。 さらに,本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。 そこで,線形時間,線形空間のランダム化アルゴリズムであるAdalinaを導入し,平均二乗誤差を理論的に改善した。 理論的知見はすべて実験的に検証されている。

関連論文リスト

• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• A Retrospective Approximation Approach for Smooth Stochastic Optimization [0.2867517731896504]
  グラディエント(グラディエント、英: Gradient、SG)とは、最適化(SO)問題をスムーズ(ノンフィクション)な目標値で解くための補足的反復手法である。
  論文  参考訳（メタデータ） (2021-03-07T16:29:36Z)
• Robust estimation via generalized quasi-gradients [28.292300073453877]
  最近提案されたロバスト推定問題の多くが効率的に解ける理由を示す。 我々は「一般化された準次数」の存在を識別する 一般化された準勾配が存在することを示し、効率的なアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-05-28T15:14:33Z)

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

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