論文の概要: Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields

• arxiv url: http://arxiv.org/abs/2109.08666v1
• Date: Fri, 17 Sep 2021 17:46:12 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-20 15:54:31.002108
• Title: Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields
• Title（参考訳）: ガウスマルコフ確率場に基づくミニマックス凹ペナルティによるスパースグラフの学習
• Authors: Tatsuya Koyakumaru, Masahiro Yukawa, Eduardo Pavez, and Antonio Ortega
• Abstract要約: 本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
• 参考スコア（独自算出の注目度）: 51.07460861448716
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper presents a convex-analytic framework to learn sparse graphs from data. While our problem formulation is inspired by an extension of the graphical lasso using the so-called combinatorial graph Laplacian framework, a key difference is the use of a nonconvex alternative to the $\ell_1$ norm to attain graphs with better interpretability. Specifically, we use the weakly-convex minimax concave penalty (the difference between the $\ell_1$ norm and the Huber function) which is known to yield sparse solutions with lower estimation bias than $\ell_1$ for regression problems. In our framework, the graph Laplacian is replaced in the optimization by a linear transform of the vector corresponding to its upper triangular part. Via a reformulation relying on Moreau's decomposition, we show that overall convexity is guaranteed by introducing a quadratic function to our cost function. The problem can be solved efficiently by the primal-dual splitting method, of which the admissible conditions for provable convergence are presented. Numerical examples show that the proposed method significantly outperforms the existing graph learning methods with reasonable CPU time.
• Abstract（参考訳）: 本稿では,データからスパースグラフを学ぶための凸解析フレームワークを提案する。 我々の問題定式化は、いわゆる組合せグラフラプラシアンフレームワークを用いたグラフィカルラッソの拡張に触発されているが、重要な違いは、より解釈性の良いグラフを得るために$\ell_1$ノルムの代わりに非凸を用いることである。 具体的には、回帰問題に対して$\ell_1$よりも低い推定バイアスでスパース解が得られることが知られている弱凸ミニマックス円錐ペナルティ($\ell_1$ノルムとHuber関数の差)を用いる。 このフレームワークでは、グラフラプラシアンは、その上三角部分に対応するベクトルの線型変換によって、最適化において置き換えられる。 モローの分解に依存した再構成により、コスト関数に二次関数を導入することで全体の凸性が保証されることを示す。 この問題は、証明可能な収束の許容条件を示す原始二分割法によって効率よく解ける。 数値的な例では、提案手法は、既存のグラフ学習法をCPU時間で大幅に上回っている。

関連論文リスト

• CLAP: Concave Linear APproximation for Quadratic Graph Matching [5.417323487240968]
  線形モデルを導入し、グラフマッチングのための新しい近似行列を設計する。 次に、元のQAPを構造制約の凹凸となる線形モデルに変換する。 このモデルはシンクホーン最適輸送アルゴリズムを用いて解くことができる。
  論文  参考訳（メタデータ） (2024-10-22T15:28:18Z)
• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• 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)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  多層グラフクラスタリングは、グラフノードをカテゴリまたはコミュニティに分割することを目指しています。 与えられた多層グラフの層をクラスタリングに親しみやすい埋め込みを提案する。 実験の結果,本手法は著しい改善をもたらすことがわかった。
  論文  参考訳（メタデータ） (2021-03-30T17:36:40Z)
• Bayesian Inference of Random Dot Product Graphs via Conic Programming [1.7188280334580195]
  本稿では,ランダムドット積グラフ(RDPG)の潜在確率行列を推定する凸コーンプログラムを提案する。 また、この手法がケイトクラブグラフと米国上院の投票グラフの潜在構造を復元することを示した。
  論文  参考訳（メタデータ） (2021-01-06T18:29:37Z)
• Multiway $p$-spectral graph cuts on Grassmann manifolds [0.3441021278275805]
  直接マルチウェイスペクトルクラスタリングアルゴリズムを$p$-norm, for $p in (1, 2]$で提案する。 グラフ $p$-Laplacian の多重固有ベクトルを計算する問題は、グラスマン多様体上の制約のない最小化問題として再キャストされる。 バランスの取れたグラフの単調な減少を監視することは、検討された$p$レベルから最高の解が得られることを保証します。
  論文  参考訳（メタデータ） (2020-08-30T16:25:04Z)
• Does the $\ell_1$-norm Learn a Sparse Graph under Laplacian Constrained Graphical Models? [13.572602792770288]
  ラプラシアン制約ガウス図形モデルの下でグラフを学習する問題を考察する。 我々は、大きな正規化パラメータが驚くほど完全なグラフ、すなわちエッジで接続されたすべてのエッジにつながることを示した。
  論文  参考訳（メタデータ） (2020-06-26T12:06:10Z)

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

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