論文の概要: On Model Selection Consistency of Lasso for High-Dimensional Ising
Models on Tree-like Graphs
- arxiv url: http://arxiv.org/abs/2110.08500v1
- Date: Sat, 16 Oct 2021 07:23:02 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-19 15:00:18.679049
- Title: On Model Selection Consistency of Lasso for High-Dimensional Ising
Models on Tree-like Graphs
- Title(参考訳): 木状グラフ上の高次元イジングモデルに対するラッソのモデル選択整合性について
- Authors: Xiangming Meng and Tomoyuki Obuchi and Yoshiyuki Kabashima
- Abstract要約: 近傍型最小絶対収縮・選択演算子(Lasso)を用いた高次元イジングモデル選択の問題点を考察する。
常磁性相の任意の木様グラフに対して、サンプルサイズ$n=Omega(d3logp)$で一貫したモデル選択が達成できることは厳密に証明されている。
ラッソの人気と効率性を考えると、厳密な解析はイジングモデル選択における実践的利用の理論的裏付けとなる。
- 参考スコア(独自算出の注目度): 13.14903445595385
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of high-dimensional Ising model selection using
neighborhood-based least absolute shrinkage and selection operator (Lasso). It
is rigorously proved that under some mild coherence conditions on the
population covariance matrix of the Ising model, consistent model selection can
be achieved with sample sizes $n=\Omega{(d^3\log{p})}$ for any tree-like graph
in the paramagnetic phase, where $p$ is the number of variables and $d$ is the
maximum node degree. When the same conditions are imposed directly on the
sample covariance matrices, it is shown that a reduced sample size
$n=\Omega{(d^2\log{p})}$ suffices. The obtained sufficient conditions for
consistent model selection with Lasso are the same in the scaling of the sample
complexity as that of $\ell_1$-regularized logistic regression. Given the
popularity and efficiency of Lasso, our rigorous analysis provides a
theoretical backing for its practical use in Ising model selection.
- Abstract(参考訳): 本稿では,近隣の最小絶対収縮・選択演算子(Lasso)を用いた高次元イジングモデル選択の問題を考える。
イジングモデルの集団共分散行列上のいくつかの穏やかなコヒーレンス条件の下では、パラ磁性相の任意の木状グラフに対して、サンプルサイズ$n=\omega{(d^3\log{p})} で一貫したモデル選択が達成され、ここで$p$ は変数の数、$d$ はノード次数である。
同じ条件がサンプル共分散行列に直接課されると、縮小されたサンプルサイズ $n=\omega{(d^2\log{p})}$ suffices が示される。
Lassoとの一貫性のあるモデル選択のための十分な条件は、サンプル複雑性のスケーリングにおいて$\ell_1$-regularized logistic regressionと同じである。
ラッソの人気と効率性を考えると、厳密な分析は、イジングモデル選択における実践的利用の理論的裏付けとなる。
関連論文リスト
- Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳(メタデータ) (2024-03-08T18:50:19Z) - KL-Entropy-Regularized RL with a Generative Model is Minimax Optimal [70.15267479220691]
モデル強化学習のサンプル複雑性を,生成的分散自由モデルを用いて検討・解析する。
我々の分析は、$varepsilon$が十分小さい場合、$varepsilon$-optimal Policyを見つけるのが、ほぼ最小の最適化であることを示している。
論文 参考訳(メタデータ) (2022-05-27T19:39:24Z) - What Makes A Good Fisherman? Linear Regression under Self-Selection Bias [32.6588421908864]
古典的な自己選択の設定では、ゴールは、観測値$(x(i), y(i))$から同時に$k$モデルを学ぶことである。
本研究では,モデルが線形であるこの問題の最も標準的な設定に対して,計算的かつ統計的に効率的な推定アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-05-06T14:03:05Z) - Universal and data-adaptive algorithms for model selection in linear
contextual bandits [52.47796554359261]
モデル選択の最も単純な非自明な例を考える: 単純な多重武装バンディット問題と線形文脈バンディット問題とを区別する。
データ適応的な方法で探索する新しいアルゴリズムを導入し、$mathcalO(dalpha T1- alpha)$という形式の保証を提供する。
我々のアプローチは、いくつかの仮定の下で、ネストされた線形文脈包帯のモデル選択に拡張する。
論文 参考訳(メタデータ) (2021-11-08T18:05:35Z) - On the Power of Preconditioning in Sparse Linear Regression [24.140675945592704]
プレコンディショニングされたラッソは、大まかな線形回帰問題をほぼ最適に解くことができることを示す。
最適条件のラッソに対して証明が難しいランダム設計のインスタンスを初めて構築する。
論文 参考訳(メタデータ) (2021-06-17T02:12:01Z) - The Lasso with general Gaussian designs with applications to hypothesis
testing [21.342900543543816]
ラッソは高次元回帰法である。
ラッソ推定器は、$n$と$p$の両方が大きい状態において正確に特徴づけられることを示す。
論文 参考訳(メタデータ) (2020-07-27T17:48:54Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳(メタデータ) (2020-07-15T03:25:24Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳(メタデータ) (2020-05-26T17:53:18Z) - Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。
アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。
ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
論文 参考訳(メタデータ) (2020-02-20T10:50:58Z) - Eigen-Stratified Models [0.0]
階層化されたモデルは、選択されたカテゴリ機能に任意の方法で依存し、$K$の値を取り、他の$n$の機能に線形に依存する。
グラフ上の特徴値に対するラプラシア正規化は、成層モデルの性能を大幅に向上させることができる。
論文 参考訳(メタデータ) (2020-01-27T16:26:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。