論文の概要: Learning Large-Scale MTP$_2$ Gaussian Graphical Models via Bridge-Block Decomposition

• arxiv url: http://arxiv.org/abs/2309.13405v2
• Date: Thu, 28 Sep 2023 16:09:31 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-29 19:41:34.908437
• Title: Learning Large-Scale MTP$_2$ Gaussian Graphical Models via Bridge-Block Decomposition
• Title（参考訳）: ブリッジブロック分解による大規模mtp$_2$ガウス図形モデルの学習
• Authors: Xiwen Wang, Jiaxi Ying, Daniel P. Palomar
• Abstract要約: より小型のサブプロブレムを用いて問題全体を等価に最適化できることを示す。 実践的な側面から、この単純で証明可能な規律は、大きな問題を小さな抽出可能なものに分解するために適用することができる。
• 参考スコア（独自算出の注目度）: 15.322124183968635
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the problem of learning the large-scale Gaussian graphical models that are multivariate totally positive of order two ($\text{MTP}_2$). By introducing the concept of bridge, which commonly exists in large-scale sparse graphs, we show that the entire problem can be equivalently optimized through (1) several smaller-scaled sub-problems induced by a \emph{bridge-block decomposition} on the thresholded sample covariance graph and (2) a set of explicit solutions on entries corresponding to \emph{bridges}. From practical aspect, this simple and provable discipline can be applied to break down a large problem into small tractable ones, leading to enormous reduction on the computational complexity and substantial improvements for all existing algorithms. The synthetic and real-world experiments demonstrate that our proposed method presents a significant speed-up compared to the state-of-the-art benchmarks.
• Abstract（参考訳）: 本稿では,階数2 (\text{mtp}_2$) の完全正の多変量ガウス図形モデルを学習する問題について検討する。 大規模なスパースグラフによく存在するブリッジの概念を導入することにより、(1)閾値付きサンプル共分散グラフ上で \emph{bridge-block decomposition} によって誘導されるいくつかの小さなサブプロブレムと(2) 対応するエントリに対する明示的な解の集合を通して、問題全体が等価に最適化可能であることを示す。 現実的な側面から、この単純で証明可能な規律は、大きな問題を小さなトラクタブルなものに分解するために適用することができ、計算複雑性の大幅な削減と既存のアルゴリズムの大幅な改善につながる。 合成および実世界の実験により,提案手法は最先端のベンチマークと比較すると,大幅な高速化を示した。

関連論文リスト

• Pushing the Limits of Large Language Model Quantization via the Linearity Theorem [71.3332971315821]
  本稿では,階層的$ell$再構成誤差と量子化によるモデルパープレキシティ増加との直接的な関係を確立する「線形定理」を提案する。 この知見は,(1)アダマール回転とHIGGSと呼ばれるMSE最適格子を用いた単純なデータフリーLCM量子化法,(2)非一様層ごとの量子化レベルを求める問題に対する最適解の2つの新しい応用を可能にする。
  論文  参考訳（メタデータ） (2024-11-26T15:35:44Z)
• Efficient Graph Laplacian Estimation by Proximal Newton [12.05527862797306]
  グラフ学習問題は、精度行列の最大極大推定(MLE)として定式化することができる。 いくつかのアルゴリズム的特徴を利用した効率的な解法を得るための2次手法を開発した。
  論文  参考訳（メタデータ） (2023-02-13T15:13:22Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。 この問題は楕円分布のペナルティ化された最大推定値として表される。 楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
  論文  参考訳（メタデータ） (2022-10-21T13:19:45Z)
• Learning Linear Models Using Distributed Iterative Hessian Sketching [4.567810220723372]
  観測データから線形システムのマルコフパラメータを学習する問題を考察する。 Hessian-Sketchingに基づくランダムに分散されたニュートンアルゴリズムは、$epsilon$-optimal Solutionを生成可能であることを示す。
  論文  参考訳（メタデータ） (2021-12-08T04:07:23Z)
• Gaussian Graphical Model Selection for Huge Data via Minipatch Learning [1.2891210250935146]
  グラフィカルモデル選択の問題を解決するために,MPGraph (Minipatch Graph) 推定器を提案する。 MPGraphは、観測とノードの両方の小さなランダムなサブセットに適合する閾値グラフ推定器の一般化である。 本アルゴリズムは有限サンプルグラフ選択の整合性を実現する。
  論文  参考訳（メタデータ） (2021-10-22T21:06:48Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  本研究では,多元的固有ベクトルを分散制約で同時に計算するTruncated Orthogonal Iterationの2つの変種を提案する。 次に,我々のアルゴリズムを適用して,幅広いテストデータセットに対するスパース原理成分分析問題を解く。
  論文  参考訳（メタデータ） (2021-03-24T23:11:32Z)
• PCA Reduced Gaussian Mixture Models with Applications in Superresolution [1.885698488789676]
  本稿は、このトピックに2倍のコントリビューションを提供する。 まず,モデルの各成分におけるデータ次元の減少と合わせてガウス混合モデルを提案する。 第2に,サンディープとヤコブのアプローチに基づく2次元および3次元材料画像の超解像化にPCA-GMMを適用した。
  論文  参考訳（メタデータ） (2020-09-16T07:33:56Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)

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

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