論文の概要: DAGs with No Fears: A Closer Look at Continuous Optimization for
Learning Bayesian Networks
- arxiv url: http://arxiv.org/abs/2010.09133v1
- Date: Sun, 18 Oct 2020 22:59:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-06 03:56:10.058085
- Title: DAGs with No Fears: A Closer Look at Continuous Optimization for
Learning Bayesian Networks
- Title(参考訳): 恐れのないdag - ベイズネットワーク学習のための継続的最適化をよく見る
- Authors: Dennis Wei, Tian Gao, Yue Yu
- Abstract要約: 我々はベイズネットワーク学習のためのNOTEARSという連続最適化フレームワークを再検討する。
本論文では,NOTEARSに対するKarush-Kuhn-Tucker最適条件は,自明な場合を除いて満足できないことを示す。
ローカル検索の組み合わせは、元のNOTEARSよりも正確かつ効率的である。
- 参考スコア(独自算出の注目度): 45.3591788771536
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper re-examines a continuous optimization framework dubbed NOTEARS for
learning Bayesian networks. We first generalize existing algebraic
characterizations of acyclicity to a class of matrix polynomials. Next,
focusing on a one-parameter-per-edge setting, it is shown that the
Karush-Kuhn-Tucker (KKT) optimality conditions for the NOTEARS formulation
cannot be satisfied except in a trivial case, which explains a behavior of the
associated algorithm. We then derive the KKT conditions for an equivalent
reformulation, show that they are indeed necessary, and relate them to explicit
constraints that certain edges be absent from the graph. If the score function
is convex, these KKT conditions are also sufficient for local minimality
despite the non-convexity of the constraint. Informed by the KKT conditions, a
local search post-processing algorithm is proposed and shown to substantially
and universally improve the structural Hamming distance of all tested
algorithms, typically by a factor of 2 or more. Some combinations with local
search are both more accurate and more efficient than the original NOTEARS.
- Abstract(参考訳): 本稿では,ベイズネットワーク学習のためのNOTEARSという連続最適化フレームワークを再検討する。
まず、非環の既存の代数的特徴付けを行列多項式のクラスに一般化する。
次に,エッジ当たり1パラメータの設定に着目して,関連するアルゴリズムの挙動を説明する自明な場合を除いては,切り欠きの定式化に対するカルス・クーン・タッカー(kkt)最適条件は満足できないことを示した。
次に、等価な再構成のためにKKT条件を導出し、それらが本当に必要であることを示し、グラフから特定の辺が欠落する明示的な制約に関連付ける。
スコア関数が凸であれば、これらのKKT条件は制約の非凸性にも拘わらず局所最小性にも十分である。
kkt条件により局所探索後処理アルゴリズムが提案され、一般に2以上の係数で全てのテスト済みアルゴリズムの構造ハミング距離を実質的に普遍的に改善することが示されている。
ローカル検索の組み合わせは、元のNOTEARSよりも正確かつ効率的である。
関連論文リスト
- Karush-Kuhn-Tucker Condition-Trained Neural Networks (KKT Nets) [0.0]
本稿では,KKT(Karush-Kuhn-Tucker)条件を利用して凸最適化問題の解法を提案する。
理論学習ニューラルネットワーク(TTNN)と同様に、凸最適化問題のパラメータがニューラルネットワークに入力される。
この場合の損失関数の選択は損失であり、KKT損失と呼ばれ、ネットワークの出力がKKT条件をどのように満足するかを測定する。
論文 参考訳(メタデータ) (2024-10-21T12:59:58Z) - ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
ALEXRと呼ばれる,効率的な単ループプリマルデュアルブロックコーディネートアルゴリズムを提案する。
本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。
本稿では,ALEXRの収束速度が,検討されたcFCCO問題に対する1次ブロック座標アルゴリズムの中で最適であることを示すために,より低い複雑性境界を示す。
論文 参考訳(メタデータ) (2023-12-04T19:00:07Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Performance of $\ell_1$ Regularization for Sparse Convex Optimization [10.37112414795167]
ベクトル値特徴を持つスパース凸最適化のためのグループLASSOの最初のリカバリ保証を与える。
この結果は、一般入力インスタンス下での凸関数に対するグループLASSOの経験的成功を理論的に説明する最初のものである。
この問題に対する一般損失関数の第一結果は、強い凸性や滑らかさに制限されるだけである。
論文 参考訳(メタデータ) (2023-07-14T15:31:45Z) - Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from
KKT Conditions for Margin Maximization [59.038366742773164]
ロジスティック損失の勾配流によって訓練された線形および漏洩ReLUは、KKT条件を満たすための暗黙の偏りを持つ。
本研究では、線形分類器や2層リークReLUネットワークにおいて、これらの条件の満足度が良性オーバーフィットを意味するような設定を多数確立する。
論文 参考訳(メタデータ) (2023-03-02T18:24:26Z) - Partial Optimality in Cubic Correlation Clustering [6.372499127940625]
最適性の証明はNPハードであり、問題文の複雑さによって事実上妨げられている。
ここでは、完備グラフと立方体目的関数の特殊ケースに対する部分最適条件の確立に焦点をあてる。
さらに、これらの条件をテストするアルゴリズムを定義し、その効果を2つのデータセット上で数値的に検証する。
論文 参考訳(メタデータ) (2023-02-09T15:25:52Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。
このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文 参考訳(メタデータ) (2020-10-31T21:35:42Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。