論文の概要: Fundamental Computational Limits in Pursuing Invariant Causal Prediction and Invariance-Guided Regularization

• arxiv url: http://arxiv.org/abs/2501.17354v1
• Date: Wed, 29 Jan 2025 00:29:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-30 15:54:23.559702
• Title: Fundamental Computational Limits in Pursuing Invariant Causal Prediction and Invariance-Guided Regularization
• Title（参考訳）: 変分因数予測と変分誘導正規化における基本計算限界
• Authors: Yihong Gu, Cong Fang, Yang Xu, Zijian Guo, Jianqing Fan,
• Abstract要約: 異種環境からの不変な予測は、純粋にデータ駆動の方法で因果関係を学ぶための扉を開く。 サンプル効率を推定できる既存の方法は指数時間アルゴリズムに基づいている。 本稿では,追加条件下での計算的および統計的に効率的に推定できる手法を提案する。
• 参考スコア（独自算出の注目度）: 11.940138507727577
• License:
• Abstract: Pursuing invariant prediction from heterogeneous environments opens the door to learning causality in a purely data-driven way and has several applications in causal discovery and robust transfer learning. However, existing methods such as ICP [Peters et al., 2016] and EILLS [Fan et al., 2024] that can attain sample-efficient estimation are based on exponential time algorithms. In this paper, we show that such a problem is intrinsically hard in computation: the decision problem, testing whether a non-trivial prediction-invariant solution exists across two environments, is NP-hard even for the linear causal relationship. In the world where P$\neq$NP, our results imply that the estimation error rate can be arbitrarily slow using any computationally efficient algorithm. This suggests that pursuing causality is fundamentally harder than detecting associations when no prior assumption is pre-offered. Given there is almost no hope of computational improvement under the worst case, this paper proposes a method capable of attaining both computationally and statistically efficient estimation under additional conditions. Furthermore, our estimator is a distributionally robust estimator with an ellipse-shaped uncertain set where more uncertainty is placed on spurious directions than invariant directions, resulting in a smooth interpolation between the most predictive solution and the causal solution by varying the invariance hyper-parameter. Non-asymptotic results and empirical applications support the claim.
• Abstract（参考訳）: 不均一環境からの不変な予測は、純粋にデータ駆動の方法で因果関係を学習する扉を開くとともに、因果発見と堅牢な移動学習にいくつかの応用がある。 しかし,ICP (Peters et al , 2016) や EILLS (Fan et al , 2024) のような,サンプル効率の高い推定が可能な既存の手法は指数時間アルゴリズムに基づいている。 本稿では,2つの環境に非自明な予測不変解が存在するかどうかを判定する決定問題は,線形因果関係においてもNPハードであることを示す。 P$\neq$NPの世界では,任意の計算効率のアルゴリズムを用いて推定誤差率を任意に遅くすることができることを示す。 このことは、因果関係の追求が、事前の前提が逸脱していない場合の関連性の検出よりも根本的に難しいことを示唆している。 最悪の場合では計算改善の見込みがほとんどないため,追加条件下での計算と統計的に効率的な推定を両立させる手法を提案する。 さらに, この推定器は, 楕円形不確かさ集合を持つ分布安定な推定器であり, より不確かさが不均一方向よりも急激な方向に配置され, その結果, 非分散ハイパーパラメータを変化させることで, 最も予測可能な解と因果解とのスムーズな補間が生じる。 非漸近的な結果と経験的応用が主張を支持している。

関連論文リスト

• Scalable method for Bayesian experimental design without integrating over posterior distribution [0.0]
  実験問題のA-最適ベイズ設計における計算効率について検討する。 A-最適性はベイズの実験設計に広く用いられ、容易に解釈できる基準である。 本研究は, A-Optimal 実験設計における新しい可能性のないアプローチを提案する。
  論文  参考訳（メタデータ） (2023-06-30T12:40:43Z)
• A Learning-Based Optimal Uncertainty Quantification Method and Its Application to Ballistic Impact Problems [1.713291434132985]
  本稿では、入力(または事前)測度が部分的に不完全であるシステムに対する最適(最大および無限)不確実性境界について述べる。 本研究では,不確実性最適化問題に対する学習基盤の枠組みを実証する。 本手法は,工学的実践における性能証明と安全性のためのマップ構築に有効であることを示す。
  論文  参考訳（メタデータ） (2022-12-28T14:30:53Z)
• Data-Driven Influence Functions for Optimization-Based Causal Inference [105.5385525290466]
  統計的汎関数に対するガトー微分を有限差分法で近似する構成的アルゴリズムについて検討する。 本研究では,確率分布を事前知識がないが,データから推定する必要がある場合について検討する。
  論文  参考訳（メタデータ） (2022-08-29T16:16:22Z)
• Posterior and Computational Uncertainty in Gaussian Processes [52.26904059556759]
  ガウスのプロセスはデータセットのサイズとともに違法にスケールする。 多くの近似法が開発されており、必然的に近似誤差を導入している。 この余分な不確実性の原因は、計算が限られているため、近似後部を使用すると完全に無視される。 本研究では,観測された有限個のデータと有限個の計算量の両方から生じる組合せ不確実性を一貫した推定を行う手法の開発を行う。
  論文  参考訳（メタデータ） (2022-05-30T22:16:25Z)
• Accelerated and instance-optimal policy evaluation with linear function approximation [17.995515643150657]
  既存のアルゴリズムはこれらの下界の少なくとも1つと一致しない。 我々は,両下界を同時に一致させる高速時間差分アルゴリズムを開発し,インスタンス最適性という強い概念を実現する。
  論文  参考訳（メタデータ） (2021-12-24T17:21:04Z)
• Learning to Estimate Without Bias [57.82628598276623]
  ガウスの定理は、重み付き最小二乗推定器は線形モデルにおける線形最小分散アンバイアスド推定(MVUE)であると述べている。 本稿では、バイアス制約のあるディープラーニングを用いて、この結果を非線形設定に拡張する第一歩を踏み出す。 BCEの第二の動機は、同じ未知の複数の推定値が平均化されてパフォーマンスが向上するアプリケーションにおいてである。
  論文  参考訳（メタデータ） (2021-10-24T10:23:51Z)
• Variance Minimization in the Wasserstein Space for Invariant Causal Prediction [72.13445677280792]
  そこで本研究では,ICPで行ったアプローチを,予測器数で線形にスケールする一連の非パラメトリックテストとして再検討する。 これらのテストはそれぞれ、最適輸送理論の道具から導かれる新しい損失関数の最小化に依存している。 我々は,本手法が同定可能な直接原因の集合を回復できるという軽微な仮定の下で証明し,他のベンチマーク因果探索アルゴリズムと競合することを示す。
  論文  参考訳（メタデータ） (2021-10-13T22:30:47Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Multivariate Probabilistic Regression with Natural Gradient Boosting [63.58097881421937]
  多変量予測分布の条件パラメータを非パラメトリックにモデル化したNatural Gradient Boosting (NGBoost) 手法を提案する。 提案手法は頑健で, 広範囲なチューニングを伴わず, 推定対象分布に対してモジュール構造であり, 既存の手法と比較して競争力がある。
  論文  参考訳（メタデータ） (2021-06-07T17:44:49Z)
• Non-Asymptotic Performance Guarantees for Neural Estimation of $\mathsf{f}$-Divergences [22.496696555768846]
  統計的距離は確率分布の相似性を定量化する。 このようなデータからの距離を推定する現代的な方法は、ニューラルネットワーク(NN)による変動形態のパラメータ化と最適化に依存する。 本稿では,このトレードオフを非漸近誤差境界を用いて検討し,SDの3つの一般的な選択に焦点をあてる。
  論文  参考訳（メタデータ） (2021-03-11T19:47:30Z)

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

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