論文の概要: $ψ$DAG: Projected Stochastic Approximation Iteration for DAG Structure Learning

• arxiv url: http://arxiv.org/abs/2410.23862v1
• Date: Thu, 31 Oct 2024 12:13:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-01 16:59:49.474279
• Title: $ψ$DAG: Projected Stochastic Approximation Iteration for DAG Structure Learning
• Title（参考訳）: $$DAG:DAG構造学習のための確率近似反復計画
• Authors: Klea Ziu, Slavomír Hanzely, Loka Li, Kun Zhang, Martin Takáč, Dmitry Kamzolov,
• Abstract要約: Directed A Graphs (DAGs) の構造を学ぶことは、ノード数に応じてスケールする可能なグラフの巨大な検索空間のため、大きな課題となる。 近年の進歩は、微分可能指数関数性制約を取り入れた連続最適化タスクとしてこの問題を再定義している。 本稿では,SGD(Gradient Descent)に基づく最適化手法と統合した近似手法を用いて,DAGを学習する新しいフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 6.612096312467342
• License:
• Abstract: Learning the structure of Directed Acyclic Graphs (DAGs) presents a significant challenge due to the vast combinatorial search space of possible graphs, which scales exponentially with the number of nodes. Recent advancements have redefined this problem as a continuous optimization task by incorporating differentiable acyclicity constraints. These methods commonly rely on algebraic characterizations of DAGs, such as matrix exponentials, to enable the use of gradient-based optimization techniques. Despite these innovations, existing methods often face optimization difficulties due to the highly non-convex nature of DAG constraints and the per-iteration computational complexity. In this work, we present a novel framework for learning DAGs, employing a Stochastic Approximation approach integrated with Stochastic Gradient Descent (SGD)-based optimization techniques. Our framework introduces new projection methods tailored to efficiently enforce DAG constraints, ensuring that the algorithm converges to a feasible local minimum. With its low iteration complexity, the proposed method is well-suited for handling large-scale problems with improved computational efficiency. We demonstrate the effectiveness and scalability of our framework through comprehensive experimental evaluations, which confirm its superior performance across various settings.
• Abstract（参考訳）: 有向非巡回グラフ(DAG)の構造を学習することは、ノード数と指数関数的にスケールする可能なグラフの膨大な組合せ探索空間のため、大きな課題となる。 近年の進歩は、微分可能非巡回性制約を組み込むことで、この問題を連続的な最適化タスクとして再定義している。 これらの手法は一般に行列指数などのDAGの代数的特徴付けに頼り、勾配に基づく最適化技術を利用することができる。 これらの革新にもかかわらず、既存の手法は、DAG制約の非凸性や解数毎の計算複雑性のために、しばしば最適化の困難に直面している。 本研究では,SGD(Stochastic Gradient Descent)に基づく最適化手法と統合された確率近似手法を用いて,DAGを学習するための新しいフレームワークを提案する。 提案フレームワークでは,DAG制約を効率的に適用するための新しいプロジェクション手法を導入し,アルゴリズムが実現可能な局所最小値に収束することを保証する。 提案手法は, イテレーションの複雑さが低いため, 計算効率が向上し, 大規模問題を扱うのに適している。 本稿では,フレームワークの有効性とスケーラビリティを総合的な実験的評価によって実証し,その優れた性能を各種設定で確認する。

関連論文リスト

• Non-negative Weighted DAG Structure Learning [12.139158398361868]
  本研究は,真DAGを夜間観測から学習する問題に対処する。 本稿では, ar を返すことが保証される手法に基づく DAG 回復アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-12T09:41:29Z)
• A Full Adagrad algorithm with O(Nd) operations [4.389938747401259]
  この研究は大規模アプリケーションのための効率的で実用的なアルゴリズムを提供する。 この革新的な戦略は、一般的にフルマトリックスメソッドに関連する複雑さとリソース要求を著しく削減する。
  論文  参考訳（メタデータ） (2024-05-03T08:02:08Z)
• Optimizing NOTEARS Objectives via Topological Swaps [41.18829644248979]
  本稿では,候補アルゴリズムの集合に有効な手法を提案する。 内部レベルでは、対象が与えられた場合、オフ・ザ・アート制約を利用する。 提案手法は,他のアルゴリズムのスコアを大幅に改善する。
  論文  参考訳（メタデータ） (2023-05-26T21:49:37Z)
• An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification [97.28167655721766]
  本稿では、分散正規化損失最小化問題に対する2倍加速勾配降下法(ADSGD)を提案する。 まず、ADSGDが線形収束率を達成でき、全体的な計算複雑性を低減できることを示す。
  論文  参考訳（メタデータ） (2022-08-11T22:27:22Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。 厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。 このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
  論文  参考訳（メタデータ） (2021-11-29T15:10:09Z)
• DAGs with No Curl: An Efficient DAG Structure Learning Approach [62.885572432958504]
  近年のDAG構造学習は連続的な非巡回性制約を伴う制約付き連続最適化問題として定式化されている。 本稿では,DAG空間の重み付き隣接行列を直接モデル化し,学習するための新しい学習フレームワークを提案する。 本手法は, 線形および一般化された構造方程式モデルにおいて, ベースラインDAG構造学習法よりも精度が高いが, 効率がよいことを示す。
  論文  参考訳（メタデータ） (2021-06-14T07:11:36Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)
• On the Role of Sparsity and DAG Constraints for Learning Linear DAGs [16.97675762810828]
  ガウス系および非ガウス系におけるDAGモデルの学習におけるスパーシリティとDAG制約の役割について検討した。 確率に基づくスコア関数を提案し, 基本真理DAGと同等のDAGを学習するためには, ソフト・スパシティとDAG制約を適用するだけでよいことを示す。
  論文  参考訳（メタデータ） (2020-06-17T23:43:23Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)

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

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