論文の概要: Efficient Graph Laplacian Estimation by a Proximal Newton Approach

• arxiv url: http://arxiv.org/abs/2302.06434v1
• Date: Mon, 13 Feb 2023 15:13:22 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-14 15:13:19.639745
• Title: Efficient Graph Laplacian Estimation by a Proximal Newton Approach
• Title（参考訳）: 近位ニュートン法による効率的なグラフラプラシアン推定
• Authors: Yakov Medvedovsky, Eran Treister, Tirza Routtenberg
• Abstract要約: 本稿では,ラプラシアングラフ学習問題を高精度かつ効率的に解くことを目的とする。 提案手法は,大規模ネットワークのための効率的な解法を得るために,ニュートン法に基づく。
• 参考スコア（独自算出の注目度）: 9.045332526072828
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Laplacian-constrained Gaussian Markov Random Field (LGMRF) is a common multivariate statistical model for learning a weighted sparse dependency graph from given data. This graph learning problem is formulated as a maximum likelihood estimation (MLE) of the precision matrix, subject to Laplacian structural constraints, with a sparsity-inducing penalty term. This paper aims to solve this learning problem accurately and efficiently. First, since the commonly-used $\ell_1$-norm penalty is less appropriate in this setting, we employ the nonconvex minimax concave penalty (MCP), which promotes sparse solutions with lower estimation bias. Second, as opposed to most existing first-order methods for this problem, we base our method on the second-order proximal Newton approach to obtain an efficient solver for large-scale networks. This approach is considered the most efficient for the related graphical LASSO problem and allows for several algorithmic features we exploit, such as using Conjugate Gradients, preconditioning, and splitting to active/free sets. Numerical experiments demonstrate the advantages of the proposed method in terms of \emph{both} computational complexity and graph learning accuracy compared to existing methods.
• Abstract（参考訳）: Laplacian-Constrained Gaussian Markov Random Field (LGMRF) は、与えられたデータから重み付きスパース依存グラフを学ぶための一般的な多変量統計モデルである。 このグラフ学習問題は、ラプラシア構造制約を受ける精度行列の最大極大推定(MLE)として、スパース性誘導ペナルティ項で定式化される。 本稿では,この学習問題を正確かつ効率的に解くことを目的とする。 まず、この設定で一般的に使われる$\ell_1$-normのペナルティは適切ではないため、推定バイアスの低いスパース解を促進する非凸ミニマックスペナルティ(MCP)を用いる。 第二に,本手法は既存の一階法と対照的に,第2次ニュートン法を基礎として大規模ネットワークの効率的な解法を得る。 このアプローチは、関連するグラフィカルラッソ問題に対して最も効率的であり、共役勾配の使用、事前条件付け、アクティブ/フリー集合への分割など、我々が活用するいくつかのアルゴリズム的特徴を可能にする。 数値実験により,従来の手法と比較して計算量およびグラフ学習精度の点で,提案手法の利点が示された。

関連論文リスト

• Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition [0.38233569758620056]
  一般ベイズ因子モデルにおける最大a-ポストペリオーリ推定法を提案する。 ベイジアン・ガウス混合モデルと潜在ディリクレ割り当てに対するMAP推定アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-10-24T19:57:56Z)
• DC Algorithm for Estimation of Sparse Gaussian Graphical Models [3.291862617649511]
  グラフィカルモデルのスパース推定のための合成アルゴリズムを開発した。 提案手法は,既存の手法と同等か,あるいは優れている結果に関して,特に有利であることを示す。
  論文  参考訳（メタデータ） (2024-08-08T04:05:50Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。 この問題は楕円分布のペナルティ化された最大推定値として表される。 楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
  論文  参考訳（メタデータ） (2022-10-21T13:19:45Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
  論文  参考訳（メタデータ） (2021-07-15T17:33:05Z)
• Does the $\ell_1$-norm Learn a Sparse Graph under Laplacian Constrained Graphical Models? [13.572602792770288]
  ラプラシアン制約ガウス図形モデルの下でグラフを学習する問題を考察する。 我々は、大きな正規化パラメータが驚くほど完全なグラフ、すなわちエッジで接続されたすべてのエッジにつながることを示した。
  論文  参考訳（メタデータ） (2020-06-26T12:06:10Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Efficient algorithms for multivariate shape-constrained convex regression problems [9.281671380673306]
  最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。 一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
  論文  参考訳（メタデータ） (2020-02-26T11:18:43Z)

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

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