Fugu-MT 論文翻訳(概要): Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives

論文の概要: Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives

arxiv url: http://arxiv.org/abs/2307.09366v1
Date: Tue, 18 Jul 2023 15:49:02 GMT
ステータス: 処理完了
システム内更新日: 2023-07-19 13:54:49.242945
Title: Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives
Title（参考訳）: 離散最適化を伴うスパースガウス図形モデル:計算的・統計的視点
Authors: Kayhan Behdin, Wenyu Chen, Rahul Mazumder
Abstract要約: 本研究では,無向ガウス図形モデルに基づくスパースグラフの学習問題を考察する。擬似微分関数の $ell_0$-penalized バージョンに基づく新しい推定器 GraphL0BnB を提案する。実/合成データセットに関する数値実験により,本手法がほぼ最適に,p = 104$の問題を解けることが示唆された。
参考スコア（独自算出の注目度）: 8.403841349300103
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider the problem of learning a sparse graph underlying an undirected Gaussian graphical model, a key problem in statistical machine learning. Given $n$ samples from a multivariate Gaussian distribution with $p$ variables, the goal is to estimate the $p \times p$ inverse covariance matrix (aka precision matrix), assuming it is sparse (i.e., has a few nonzero entries). We propose GraphL0BnB, a new estimator based on an $\ell_0$-penalized version of the pseudolikelihood function, while most earlier approaches are based on the $\ell_1$-relaxation. Our estimator can be formulated as a convex mixed integer program (MIP) which can be difficult to compute at scale using off-the-shelf commercial solvers. To solve the MIP, we propose a custom nonlinear branch-and-bound (BnB) framework that solves node relaxations with tailored first-order methods. As a by-product of our BnB framework, we propose large-scale solvers for obtaining good primal solutions that are of independent interest. We derive novel statistical guarantees (estimation and variable selection) for our estimator and discuss how our approach improves upon existing estimators. Our numerical experiments on real/synthetic datasets suggest that our method can solve, to near-optimality, problem instances with $p = 10^4$ -- corresponding to a symmetric matrix of size $p \times p$ with $p^2/2$ binary variables. We demonstrate the usefulness of GraphL0BnB versus various state-of-the-art approaches on a range of datasets.
Abstract（参考訳）: 統計的機械学習における重要な問題である,無向ガウス図形モデルに基づく疎グラフ学習の問題を考える。 p$変数を持つ多変量ガウス分布からの$n$のサンプルが与えられると、目標は、それがスパースである(すなわち、いくつかの非零エントリを持つ)と仮定して、$p \times p$ 逆共分散行列(別名精度行列)を推定することである。我々は、擬似類似関数の$\ell_0$-penalizedバージョンに基づく新しい推定器であるgraphl0bnbを提案するが、ほとんどの初期のアプローチは$\ell_1$-relaxationに基づいている。我々の推定器は凸混合整数プログラム(MIP)として定式化することができ、市販の解法を用いて大規模に計算することは困難である。 MIP を解決するために,ノード緩和を最適化した一階法で解く,独自の非線形分岐結合(BnB)フレームワークを提案する。 BnBフレームワークの副産物として、独立性のある優れた原始解を得るための大規模解法を提案する。我々は,推定器に対する新しい統計的保証(推定と変数選択)を導き,既存の推定器によるアプローチの改善について議論する。実合成データセットに関する数値実験から,本手法がほぼ最適に,約$p=10^4$の問題を,約$p^2/2$の対称行列に対応して解くことができることが示唆された。我々は,GraphL0BnBと,さまざまなデータセットに対する最先端アプローチの有用性を示す。

関連論文リスト

Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
疎線形回帰の効率的な学習アルゴリズムは, 負のスパイクを持つスパースPCA問題を解くのに有効であることを示す。我々は,低次および統計的クエリの低い境界を減らしたスパース問題に対して補う。
論文参考訳（メタデータ） (2024-02-21T19:55:01Z)
Compressive Recovery of Sparse Precision Matrices [5.557600489035657]
我々は,$d$変数の統計的関係を,mathbbRn times d$の$n$サンプル$Xのデータセットからモデル化するグラフの学習問題を考察する。サイズ $m=Omegaleft((d+2k)log(d)right)$ ここで、$k$は基礎となるグラフのエッジの最大数である。本稿では, グラフィカルラッソに基づく反復アルゴリズムを用いて, 具体的デノイザとみなす実用的リカバリを実現する可能性について検討する。
論文参考訳（メタデータ） (2023-11-08T13:29:08Z)
An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文参考訳（メタデータ） (2023-06-30T08:34:29Z)
Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文参考訳（メタデータ） (2022-07-18T12:03:26Z)
Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。三角凸分解はその上部に対応する変換によって保証されることを示す。
論文参考訳（メタデータ） (2021-09-17T17:46:12Z)
Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably [23.372021234032363]
サブサンプルサイズが大きくなると、推定誤差が過度に犠牲になることを示す。私たちの知る限りでは、線形テキスト+確率モデルが保証される最初の研究です。
論文参考訳（メタデータ） (2020-10-19T07:15:38Z)
Convergence of Sparse Variational Inference in Gaussian Processes Regression [29.636483122130027]
計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
論文参考訳（メタデータ） (2020-08-01T19:23:34Z)
Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文参考訳（メタデータ） (2020-07-16T06:44:44Z)
FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。当社のメソッドは、最大50,000ドルという問題でテストしています。
論文参考訳（メタデータ） (2020-06-15T21:55:34Z)
Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文参考訳（メタデータ） (2020-04-16T19:16:38Z)
Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization [6.037383467521294]
我々は $ell_0$ 正規化回帰のための新しい正確な MIP フレームワークを提案する。私たちのフレームワークは、$p sim 107$までスケールでき、少なくとも5,000$xのスピードアップを達成できます。実装をツールキットL0BnBでオープンソースにしています。
論文参考訳（メタデータ） (2020-04-13T18:45:29Z)

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

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