論文の概要: Does the $\ell_1$-norm Learn a Sparse Graph under Laplacian Constrained Graphical Models?

• arxiv url: http://arxiv.org/abs/2006.14925v2
• Date: Tue, 5 Sep 2023 17:14:54 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-07 20:37:25.115870
• Title: Does the $\ell_1$-norm Learn a Sparse Graph under Laplacian Constrained Graphical Models?
• Title（参考訳）: Laplacian Constrained Graphical Modelsの下で$\ell_1$-normはスパースグラフを学ぶか?
• Authors: Jiaxi Ying, Jos\'e Vin\'icius de M. Cardoso, Daniel P. Palomar
• Abstract要約: ラプラシアン制約ガウス図形モデルの下でグラフを学習する問題を考察する。 我々は、大きな正規化パラメータが驚くほど完全なグラフ、すなわちエッジで接続されたすべてのエッジにつながることを示した。
• 参考スコア（独自算出の注目度）: 13.572602792770288
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of learning a sparse graph under the Laplacian constrained Gaussian graphical models. This problem can be formulated as a penalized maximum likelihood estimation of the Laplacian constrained precision matrix. Like in the classical graphical lasso problem, recent works made use of the $\ell_1$-norm regularization with the goal of promoting sparsity in Laplacian constrained precision matrix estimation. However, we find that the widely used $\ell_1$-norm is not effective in imposing a sparse solution in this problem. Through empirical evidence, we observe that the number of nonzero graph weights grows with the increase of the regularization parameter. From a theoretical perspective, we prove that a large regularization parameter will surprisingly lead to a complete graph, i.e., every pair of vertices is connected by an edge. To address this issue, we introduce the nonconvex sparsity penalty, and propose a new estimator by solving a sequence of weighted $\ell_1$-norm penalized sub-problems. We establish the non-asymptotic optimization performance guarantees on both optimization error and statistical error, and prove that the proposed estimator can recover the edges correctly with a high probability. To solve each sub-problem, we develop a projected gradient descent algorithm which enjoys a linear convergence rate. Finally, an extension to learn disconnected graphs is proposed by imposing additional rank constraint. We propose a numerical algorithm based on based on the alternating direction method of multipliers, and establish its theoretical sequence convergence. Numerical experiments involving synthetic and real-world data sets demonstrate the effectiveness of the proposed method.
• Abstract（参考訳）: ラプラシアン制約付きガウス図形モデルの下でスパースグラフを学習する問題を考える。 この問題は、ラプラシア制約精度行列のペナル化最大推定として定式化することができる。 古典的なグラフィカルラッソ問題と同様に、最近の研究ではラプラシアン制約付き精度行列推定のスパーシティを促進する目的で$\ell_1$-norm正規化を用いた。 しかし、広く使われている $\ell_1$-norm は、この問題におけるスパース解を与えるのに有効ではない。 経験的証拠を通して、正規化パラメータの増加に伴って非零グラフ重みの数が増加することを観測する。 理論的には、大きな正規化パラメータが驚くほど完全なグラフ、すなわちすべての頂点対がエッジによって接続されることを証明している。 この問題に対処するために,非凸スパルシティペナルティを導入し,重み付き$\ell_1$-normペナルティ化されたサブプロブレムの列を解いて,新しい推定器を提案する。 本研究では,最適化誤差と統計誤差の両方に対して非漸近的最適化性能を保証し,提案手法がエッジを高い確率で正しく回復できることを示す。 それぞれのサブプロブレムを解くために,線形収束率を満足する射影勾配降下アルゴリズムを開発した。 最後に,追加のランク制約を課すことにより,切断グラフを学習するための拡張を提案する。 本稿では,乗算器の交互方向法に基づく数値解法を提案し,その理論列収束性を確立する。 合成および実世界のデータセットを含む数値実験により,提案手法の有効性が示された。

関連論文リスト

• Network Topology Inference with Sparsity and Laplacian Constraints [18.447094648361453]
  我々はラプラシアの制約付きガウス図形モデルを用いてネットワークトポロジに取り組む。 この問題を解決するために,効率的なプロジェクションアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2023-09-02T15:06:30Z)
• Efficient Graph Laplacian Estimation by Proximal Newton [12.05527862797306]
  グラフ学習問題は、精度行列の最大極大推定(MLE)として定式化することができる。 いくつかのアルゴリズム的特徴を利用した効率的な解法を得るための2次手法を開発した。
  論文  参考訳（メタデータ） (2023-02-13T15:13:22Z)
• 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)
• Graph Polynomial Convolution Models for Node Classification of Non-Homophilous Graphs [52.52570805621925]
  本研究では,高階グラフ畳み込みからの効率的な学習と,ノード分類のための隣接行列から直接学習する。 得られたモデルが新しいグラフと残留スケーリングパラメータをもたらすことを示す。 提案手法は,非親和性パラメータのノード分類における精度の向上を実証する。
  論文  参考訳（メタデータ） (2022-09-12T04:46:55Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Sparse Graph Learning Under Laplacian-Related Constraints [23.503820266772504]
  確率変数間の条件依存を符号化するスパース精度行列のグラフラプラシアン関連制約に着目した。 我々は,ラプラシアン構造ではなく,全肯定性を強制するために広く用いられているペナル化対数類似アプローチの修正について検討した。 乗算器アルゴリズム (ADMM) の交互方向法を提示し, 制約付き最適化のために解析した。
  論文  参考訳（メタデータ） (2021-11-16T00:50:36Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• Bayesian Inference of Random Dot Product Graphs via Conic Programming [1.7188280334580195]
  本稿では,ランダムドット積グラフ(RDPG)の潜在確率行列を推定する凸コーンプログラムを提案する。 また、この手法がケイトクラブグラフと米国上院の投票グラフの潜在構造を復元することを示した。
  論文  参考訳（メタデータ） (2021-01-06T18:29:37Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)

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

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