論文の概要: On the Computational Complexity of Performative Prediction

• arxiv url: http://arxiv.org/abs/2601.20180v1
• Date: Wed, 28 Jan 2026 02:26:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-29 15:46:06.733623
• Title: On the Computational Complexity of Performative Prediction
• Title（参考訳）: 数式予測の計算複雑性について
• Authors: Ioannis Anagnostides, Rohan Chauhan, Ioannis Panageas, Tuomas Sandholm, Jingming Yan,
• Abstract要約: 我々は、$$-performatively stable pointの計算がPPAD完全であることを示す。 我々の重要な技術的貢献の1つは、PPAD-hardnessの結果を一般的な凸領域に拡張することである。
• 参考スコア（独自算出の注目度）: 59.584063949469645
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Performative prediction captures the phenomenon where deploying a predictive model shifts the underlying data distribution. While simple retraining dynamics are known to converge linearly when the performative effects are weak ($ρ< 1$), the complexity in the regime $ρ> 1$ was hitherto open. In this paper, we establish a sharp phase transition: computing an $ε$-performatively stable point is PPAD-complete -- and thus polynomial-time equivalent to Nash equilibria in general-sum games -- even when $ρ= 1 + O(ε)$. This intractability persists even in the ostensibly simple setting with a quadratic loss function and linear distribution shifts. One of our key technical contributions is to extend this PPAD-hardness result to general convex domains, which is of broader interest in the complexity of variational inequalities. Finally, we address the special case of strategic classification, showing that computing a strategic local optimum is PLS-hard.
• Abstract（参考訳）: パフォーマンス予測は、予測モデルのデプロイが基礎となるデータ分布をシフトする現象をキャプチャする。 単純な再学習力学は、性能効果が弱い場合(ρ<1$)に線形収束することが知られているが、レジーム$ρ> 1$の複雑さは開き目になった。 ε$-performatively stable point は PPAD-complete であり、従って一般サムゲームにおいて Nash equilibria に相当する多項式時間であり、$ρ= 1 + O(ε)$ である。 この誘引性は、2次損失関数と線形分布シフトを持つ表面上は単純な設定でも持続する。 我々の重要な技術的貢献の1つは、このPPAD完全性の結果を一般凸領域に拡張することであり、これは変分不等式の複雑さに対するより広範な関心である。 最後に、戦略的分類の特別な事例に対処し、戦略的局所最適化の計算がPSS-hardであることを示す。

関連論文リスト

• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  ハーフスペースの交叉学習は計算学習理論における中心的な問題である。 たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。 本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-11-13T00:28:24Z)
• Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits [58.63897489864948]
  結果に基づくフィードバックによる強化学習は、根本的な課題に直面します。 適切なアクションにクレジットを割り当てるには? 本稿では,一般関数近似を用いたオンラインRLにおけるこの問題の包括的解析を行う。
  論文  参考訳（メタデータ） (2025-05-26T17:44:08Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds [12.699376765058137]
  勾配降下法(SGD)は、おそらく現代の機械学習において最も一般的な最適化法である。 SGDを交換せずにサンプリングするSGDが分析されたのはごく最近のことだ。 データマトリックスに依存し、既存の境界によって予測されるものよりも決して悪くない、きめ細かい複雑性境界を証明します。
  論文  参考訳（メタデータ） (2023-06-21T18:14:44Z)
• Sample Complexity of Variance-reduced Distributionally Robust Q-learning [17.96094201655567]
  本稿では,分散性に頑健なQ-ラーニングアルゴリズムと,分散性に欠けるロバストなポリシーを効果的に学習できる分散性のあるQ-ラーニングアルゴリズムを2つ提案する。 一連の数値実験により、分布シフトの処理におけるアルゴリズムの理論的発見と効率性が確認された。
  論文  参考訳（メタデータ） (2023-05-28T19:40:46Z)
• Non-reversible Parallel Tempering for Deep Posterior Approximation [26.431541203372113]
  並列テンパリング(英: Parallel tempering、PT)は、マルチモーダル分布のシミュレーションのためのゴートワークホースである。 一般的な決定論的偶律(DEO)スキームは、非可逆性を利用して通信コストを$O(P2)$から$O(P)$に下げることに成功した。 我々は、非可逆性を促進するためのDECスキームを一般化し、幾何学的停止時間に起因するバイアスに対処するためのいくつかの解決策を提案する。
  論文  参考訳（メタデータ） (2022-11-20T01:18:40Z)
• The Heavy-Tail Phenomenon in SGD [7.366405857677226]
  最小損失のHessianの構造に依存すると、SGDの反復はエンフェビーテールの定常分布に収束する。 深層学習におけるSGDの行動に関する知見に分析結果を変換する。
  論文  参考訳（メタデータ） (2020-06-08T16:43:56Z)

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

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