論文の概要: Efficient Statistics for Sparse Graphical Models from Truncated Samples
- arxiv url: http://arxiv.org/abs/2006.09735v1
- Date: Wed, 17 Jun 2020 09:21:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-19 20:45:53.964710
- Title: Efficient Statistics for Sparse Graphical Models from Truncated Samples
- Title（参考訳）: 切り抜きサンプルからのスパースグラフモデルの効率的な統計
- Authors: Arnab Bhattacharyya and Rathin Desai and Sai Ganesh Nagarajan and
Ioannis Panageas
- Abstract要約: i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。
疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
- 参考スコア（独自算出の注目度）: 19.205541380535397
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study high-dimensional estimation from truncated samples.
We focus on two fundamental and classical problems: (i) inference of sparse
Gaussian graphical models and (ii) support recovery of sparse linear models.
(i) For Gaussian graphical models, suppose $d$-dimensional samples ${\bf x}$
are generated from a Gaussian $N(\mu,\Sigma)$ and observed only if they belong
to a subset $S \subseteq \mathbb{R}^d$. We show that ${\mu}$ and ${\Sigma}$ can
be estimated with error $\epsilon$ in the Frobenius norm, using
$\tilde{O}\left(\frac{\textrm{nz}({\Sigma}^{-1})}{\epsilon^2}\right)$ samples
from a truncated $\mathcal{N}({\mu},{\Sigma})$ and having access to a
membership oracle for $S$. The set $S$ is assumed to have non-trivial measure
under the unknown distribution but is otherwise arbitrary.
(ii) For sparse linear regression, suppose samples $({\bf x},y)$ are
generated where $y = {\bf x}^\top{{\Omega}^*} + \mathcal{N}(0,1)$ and $({\bf
x}, y)$ is seen only if $y$ belongs to a truncation set $S \subseteq
\mathbb{R}$. We consider the case that ${\Omega}^*$ is sparse with a support
set of size $k$. Our main result is to establish precise conditions on the
problem dimension $d$, the support size $k$, the number of observations $n$,
and properties of the samples and the truncation that are sufficient to recover
the support of ${\Omega}^*$. Specifically, we show that under some mild
assumptions, only $O(k^2 \log d)$ samples are needed to estimate ${\Omega}^*$
in the $\ell_\infty$-norm up to a bounded error.
For both problems, our estimator minimizes the sum of the finite population
negative log-likelihood function and an $\ell_1$-regularization term.
- Abstract（参考訳）: 本稿では,切断試料からの高次元推定について検討する。
基本的な問題と古典的な問題に焦点をあてる。
(i)疎ガウス図形モデルの推論と
(ii)スパース線形モデルの復元を支援する。
(i) ガウスのグラフィカルモデルに対して、$d$-次元のサンプル${\bf x}$ がガウスの$n(\mu,\sigma)$ から生成され、それらが$s \subseteq \mathbb{r}^d$ に属する場合にのみ観測されるとする。
これは$\tilde{o}\left(\frac{\textrm{nz}({\sigma}^{-1})}{\epsilon^2}\right)$が$\mathcal{n}({\mu},{\sigma})$と切り換えられた$\mathcal{n}({\mu},{\sigma})$からのサンプルを使って、フロベニウスのノルムで$\epsilon$をエラーとして推定でき、$s$で会員オラクルにアクセスすることができることを示している。
集合 $s$ は未知分布の下で非自明な測度であると仮定されるが、それ以外は任意である。
(ii) スパース線型回帰に対しては、$({\bf x},y)$ が生成されるが、$y = {\bf x}^\top{{\Omega}^*} + \mathcal{N}(0,1)$ と $({\bf x}, y)$ は、$y$ が truncation set $S \subseteq \mathbb{R}$ に属する場合にのみ見られる。
我々は、${\omega}^*$ が sparse で、サポートセットのサイズが $k$ である場合を考える。
我々の主な成果は, 問題次元$d$, サポートサイズ$k$, 観測値$n$, および, サンプルの特性, および${\Omega}^*$の支持を回復するのに十分なトラニケーションについて, 正確な条件を確立することである。
特に、いくつかの穏やかな仮定の下では、境界付きエラーまで$\ell_\infty$-normで${\omega}^*$を見積もるためには、サンプルは$o(k^2 \log d)$だけである。
どちらの問題に対しても、この推定器は有限集団負対同値関数と$\ell_1$-regularization項の和を最小化する。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Learning linear dynamical systems under convex constraints [4.4351901934764975]
線形力学系を単一軌道の$T$サンプルから同定する問題を考察する。
A*$は、制約のない設定に必要な値よりも$T$小さい値を確実に見積もることができる。
論文 参考訳（メタデータ） (2023-03-27T11:49:40Z) - Statistically Optimal Robust Mean and Covariance Estimation for
Anisotropic Gaussians [3.5788754401889014]
強い$varepsilon$-contaminationモデルでは、元のガウスサンプルのベクトルの$varepsilon$分を他のベクトルに置き換えたと仮定する。
我々は、少なくとも1-デルタの確率で満足するコフラ行列 $Sigma の推定器 $widehat Sigma を構築する。
論文 参考訳（メタデータ） (2023-01-21T23:28:55Z) - Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。
温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
論文 参考訳（メタデータ） (2022-05-06T19:24:44Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Nonasymptotic one-and two-sample tests in high dimension with unknown
covariance structure [0.0]
テストの問題は、$mu が 0 に対して $eta-閉である場合、すなわち $|mu| geq (eta + delta)$ に対して $|mu| leq eta である。
本研究の目的は,I型とII型の両方の誤差を所定のレベルで制御できるように,最小分離距離$の漸近的上下境界を求めることである。
論文 参考訳（メタデータ） (2021-09-01T06:22:53Z) - Self-training Converts Weak Learners to Strong Learners in Mixture
Models [86.7137362125503]
擬似ラベルの $boldsymbolbeta_mathrmpl$ が,最大$C_mathrmerr$ の分類誤差を達成可能であることを示す。
さらに、ロジスティックな損失に対して勾配降下を実行することで、ラベル付き例のみを使用して、分類誤差が$C_mathrmerr$で擬ラベルの $boldsymbolbeta_mathrmpl$ が得られることを示す。
論文 参考訳（メタデータ） (2021-06-25T17:59:16Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z) - Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication
Time [14.990725929840892]
ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。
我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
論文 参考訳（メタデータ） (2020-06-23T20:21:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。