論文の概要: Optimizing NOTEARS Objectives via Topological Swaps

• arxiv url: http://arxiv.org/abs/2305.17277v1
• Date: Fri, 26 May 2023 21:49:37 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-30 20:41:30.517603
• Title: Optimizing NOTEARS Objectives via Topological Swaps
• Title（参考訳）: トポロジカルスワップによるnotears目標の最適化
• Authors: Chang Deng, Kevin Bello, Bryon Aragam, Pradeep Ravikumar
• Abstract要約: 本稿では,候補アルゴリズムの集合に有効な手法を提案する。 内部レベルでは、対象が与えられた場合、オフ・ザ・アート制約を利用する。 提案手法は,他のアルゴリズムのスコアを大幅に改善する。
• 参考スコア（独自算出の注目度）: 41.18829644248979
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, an intriguing class of non-convex optimization problems has emerged in the context of learning directed acyclic graphs (DAGs). These problems involve minimizing a given loss or score function, subject to a non-convex continuous constraint that penalizes the presence of cycles in a graph. In this work, we delve into the optimization challenges associated with this class of non-convex programs. To address these challenges, we propose a bi-level algorithm that leverages the non-convex constraint in a novel way. The outer level of the algorithm optimizes over topological orders by iteratively swapping pairs of nodes within the topological order of a DAG. A key innovation of our approach is the development of an effective method for generating a set of candidate swapping pairs for each iteration. At the inner level, given a topological order, we utilize off-the-shelf solvers that can handle linear constraints. The key advantage of our proposed algorithm is that it is guaranteed to find a local minimum or a KKT point under weaker conditions compared to previous work and finds solutions with lower scores. Extensive experiments demonstrate that our method outperforms state-of-the-art approaches in terms of achieving a better score. Additionally, our method can also be used as a post-processing algorithm to significantly improve the score of other algorithms. Code implementing the proposed method is available at https://github.com/duntrain/topo.
• Abstract（参考訳）: 近年,非凸最適化問題の興味深いクラスが,有向非巡回グラフ(DAG)の学習において出現している。 これらの問題は与えられた損失やスコア関数を最小化することを含み、グラフ内のサイクルの存在を罰する非凸連続制約の対象となる。 本研究では,この非凸プログラムのクラスに関連する最適化課題について検討する。 これらの課題に対処するために,非凸制約を新しい方法で活用する2レベルアルゴリズムを提案する。 アルゴリズムの外層は、DAGのトポロジ的順序内のノードのペアを反復的に交換することで、トポロジ的順序を最適化する。 このアプローチの重要な革新は、イテレーション毎にペアをスワップする候補セットを生成する効果的な方法の開発である。 内部レベルでは、トポロジカルな順序を与えると、線形制約を扱うことができるオフ・ザ・シェルフソルバを利用する。 提案アルゴリズムの主な利点は, 局所最小点やKKT点を従来よりも弱い条件下で見つけることが保証され, 低いスコアで解を求めることである。 広範な実験により,本手法は,よりよいスコアを得るという点で最先端のアプローチよりも優れていることが証明された。 さらに,後処理アルゴリズムとして利用することで,他のアルゴリズムのスコアを大幅に改善することができる。 提案するメソッドを実装するコードは、https://github.com/duntrain/topoで利用可能である。

関連論文リスト

• A Penalty-Based Guardrail Algorithm for Non-Decreasing Optimization with Inequality Constraints [1.5498250598583487]
  伝統的な数学的プログラミングの解法は制約付き最小化問題を解くのに長い計算時間を必要とする。 ペナルティに基づくガードレールアルゴリズム(PGA)を提案する。
  論文  参考訳（メタデータ） (2024-05-03T10:37:34Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimization [27.07082875330508]
  制約のない不等式問題は、マルチクラスネイマンオラクルのような多くの機械学習問題をモデル化するために用いられる。 このような緩やかな規則性の条件下では、値損失の交互化と制約違反の低減のバランスをとることは困難である。 本稿では,新しい不等式制約問題アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-12T16:30:34Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Accelerated Algorithms for Convex and Non-Convex Optimization on Manifolds [9.632674803757475]
  距離における凸問題と非最適化問題の解法を提案する。 提案アルゴリズムは,目的関数における複雑性のレベルに適応する。
  論文  参考訳（メタデータ） (2020-10-18T02:48:22Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

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

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