論文の概要: An Alternative Graphical Lasso Algorithm for Precision Matrices
- arxiv url: http://arxiv.org/abs/2403.12357v1
- Date: Tue, 19 Mar 2024 02:01:01 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-20 15:51:27.207682
- Title: An Alternative Graphical Lasso Algorithm for Precision Matrices
- Title(参考訳): 精度行列に対する代替的なグラフラッソアルゴリズム
- Authors: Aramayis Dallakyan, Mohsen Pourahmadi,
- Abstract要約: 本稿では,スパース精度行列を推定するためのDP-GLassoアルゴリズムを提案する。
正規化された正規対数型は自然に凸関数を最小化しやすい2つの和に分解するが、そのうちの1つはラッソ回帰問題である。
提案アルゴリズムは,最適化対象とする精度行列を最初から備えており,DP-GLassoアルゴリズムの良好な特性をすべて保持している。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: The Graphical Lasso (GLasso) algorithm is fast and widely used for estimating sparse precision matrices (Friedman et al., 2008). Its central role in the literature of high-dimensional covariance estimation rivals that of Lasso regression for sparse estimation of the mean vector. Some mysteries regarding its optimization target, convergence, positive-definiteness and performance have been unearthed, resolved and presented in Mazumder and Hastie (2011), leading to a new/improved (dual-primal) DP-GLasso. Using a new and slightly different reparametriztion of the last column of a precision matrix we show that the regularized normal log-likelihood naturally decouples into a sum of two easy to minimize convex functions one of which is a Lasso regression problem. This decomposition is the key in developing a transparent, simple iterative block coordinate descent algorithm for computing the GLasso updates with performance comparable to DP-GLasso. In particular, our algorithm has the precision matrix as its optimization target right at the outset, and retains all the favorable properties of the DP-GLasso algorithm.
- Abstract(参考訳): Graphical Lasso (GLasso) アルゴリズムはスパース精度行列の推定に高速で広く用いられている(Friedman et al , 2008)。
高次元共分散推定の文献における中心的な役割は、平均ベクトルのスパース推定のためのラッソ回帰に匹敵する。
最適化対象、収束、正定性、性能に関する謎は、Mazumder and Hastie (2011) で発見され、解決され、提示された。
精度行列の最後の列の新たな、わずかに異なる逆行列を用いて、正規化された正規対数のような自然に分離された2つの凸関数の和がラッソ回帰問題であることを示す。
この分解は、GLassoの更新をDP-GLassoに匹敵する性能で計算するための、透過的でシンプルな反復ブロック座標降下アルゴリズムを開発する鍵となる。
特に,本アルゴリズムは最適化対象として最適化行列を持ち,DP-GLassoアルゴリズムの良好な特性をすべて保持している。
関連論文リスト
- Differentially Private Optimization with Sparse Gradients [60.853074897282625]
微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。
これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
論文 参考訳(メタデータ) (2024-04-16T20:01:10Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Fast Algorithms for Directed Graph Partitioning Using Flows and
Reweighted Eigenvalues [6.094384342913063]
我々は,有向エッジ拡張に対する$O(sqrtlogn)$-approximationとCheeger型保証を実現するために,ほぼ線形時間アルゴリズムを導出する。
これは、有向グラフ分割のための最もよく知られたアルゴリズムを得るための、原始二重フローベースのフレームワークを提供する。
論文 参考訳(メタデータ) (2023-06-15T13:41:17Z) - Fast Computation of Optimal Transport via Entropy-Regularized
Extragradient Methods [98.85583323658366]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - Adaptive Zeroth-Order Optimisation of Nonconvex Composite Objectives [1.7640556247739623]
ゼロ階エントロピー合成目的のためのアルゴリズムを解析し,次元依存性に着目した。
これは、ミラー降下法と推定類似関数を用いて、決定セットの低次元構造を利用して達成される。
勾配を改善するため、Rademacherに基づく古典的なサンプリング法を置き換え、ミニバッチ法が非ユークリ幾何学に対処することを示す。
論文 参考訳(メタデータ) (2022-08-09T07:36:25Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳(メタデータ) (2021-09-10T07:01:15Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳(メタデータ) (2020-06-24T07:40:31Z) - 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) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳(メタデータ) (2020-06-10T15:00:09Z) - Stochastic Coordinate Minimization with Progressive Precision for
Stochastic Convex Optimization [16.0251555430107]
凸最適化のための反復座標最小化(CM)に基づくフレームワークを開発した。
最適精度制御と結果の順序-最適後悔性能を確立する。
提案アルゴリズムは,大規模最適化のためのCMのスケーラビリティと並列性特性を継承し,オンライン実装に適したアルゴリズムである。
論文 参考訳(メタデータ) (2020-03-11T18:42:40Z) - Estimating Multiple Precision Matrices with Cluster Fusion
Regularization [0.90238471756546]
異なるクラスから複数の精度行列を推定するペナライズされた可能性を提案する。
既存の手法の多くは、精度行列間の関係に関する情報を含まないか、あるいはこの情報を先入観として要求する。
論文 参考訳(メタデータ) (2020-03-01T01:03:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。