論文の概要: Hold-Out Scoring for Efficient Gaussian DAG Learning

• arxiv url: http://arxiv.org/abs/2610.02785v1
• Date: Fri, 02 Oct 2026 04:20:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 00:14:30.205812
• Title: Hold-Out Scoring for Efficient Gaussian DAG Learning
• Title（参考訳）: 効率的なガウスDAG学習のためのホールドアウトスコアリング
• Abstract要約: HOSTは、部分集合探索をホールドアウトスコアと凸回帰に置き換える効率的なDAG学習アルゴリズムである。 HOSTは、優れた実行時スケーリングを示しながら、競争力のあるグラフリカバリを実現する。
• 参考スコア（独自算出の注目度）: 0.7349727826230862
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: High-dimensional Gaussian DAG learning faces a statistical-computational gap: methods with sharp sample complexity rely on computationally expensive subset search and a supplied indegree bound, whereas polynomial-time alternatives have less favorable sample complexity. We introduce HOST, an efficient DAG learning algorithm that replaces subset search with nodewise hold-out scoring and convex regression, without requiring a supplied indegree bound. Our key insight is that recovering a correct ordering does not require uniformly small estimation errors in ordering scores but only one-sided control of those errors. In the ordering step, HOST exploits the fact that score estimation using hold-out samples inflates ordering scores in expectation, which is the favorable direction for candidates that should not yet be selected. Given the ordering, HOST recovers parents by recursively removing indirect effects from total effects between two nodes. Under suitable conditions, HOST exactly recovers a $p$-node DAG of maximum indegree $d$ with sample complexity of order $d\log p$ in polynomial time. Experiments show that HOST achieves competitive graph recovery while exhibiting favorable runtime scaling.
• Abstract（参考訳）: 高次元ガウスDAG学習は統計計算のギャップに直面している: 急激なサンプル複雑性を持つ手法は計算に高価な部分集合探索と供給される無限境界に依存している。 本稿では,部分集合探索をノード単位のホールトアウトスコアと凸回帰に置き換える,効率的なDAG学習アルゴリズムであるHOSTを紹介する。 我々の重要な洞察は、正しい順序付けを復元するには、スコアの順序付けにおいて一意に小さな推定誤差を必要とせず、一方的な制御しか必要としないということである。 順序付けステップでは、ホールトアウトサンプルを用いたスコア推定が、まだ選択すべきでない候補に対して有利な方向である期待値の順序付けスコアを膨らませるという事実を利用する。 注文されたHoSTは、2つのノード間の全効果から間接的な効果を取り除き、親を回復させる。 適切な条件下では、HOSTは多項式時間で$d\log p$のオーダーのサンプル複雑性を持つ最大次数$d$の$p$ノードDAGを正確に回収する。 実験の結果、HOSTは優れたランタイムスケーリングを示しながら、競争力のあるグラフリカバリを実現していることがわかった。

関連論文リスト

• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。 得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
  論文  参考訳（メタデータ） (2025-12-01T02:52:33Z)
• Efficient Federated Learning against Byzantine Attacks and Data Heterogeneity via Aggregating Normalized Gradients [27.433334322019675]
  Federated Learning (FL)は、クライアントが生データを共有せずに、協力的にモデルをトレーニングすることを可能にする。 FLはByzantine攻撃やデータ不均一性の反復に弱いため、パフォーマンスが著しく低下する可能性がある。 フェデレート正規化勾配アルゴリズム (Federated Normalized Gradients Algorithm, NGA) を提案する。 既存手法に対するベンチマーク収束の実験結果
  論文  参考訳（メタデータ） (2024-08-18T16:50:39Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity [26.298213774857302]
  オフポリシー最適制御のための分散還元Greedy-GQ(VRGreedy-GQ)アルゴリズムを提案する。 我々はVR-Greedy-GQがオリジナルのGreedy-GQよりもはるかに小さなバイアス誤差を達成していることを示す。
  論文  参考訳（メタデータ） (2021-03-30T14:17:50Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)

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

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