論文の概要: Meta Learning for Support Recovery in High-dimensional Precision Matrix
Estimation
- arxiv url: http://arxiv.org/abs/2006.12598v2
- Date: Sun, 21 Feb 2021 17:14:04 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-18 05:11:53.942385
- Title: Meta Learning for Support Recovery in High-dimensional Precision Matrix
Estimation
- Title（参考訳）: 高次元精度行列推定におけるメタ学習による回復支援
- Authors: Qian Zhang and Yilin Zheng and Jean Honorio
- Abstract要約: 高次元精度行列推定における支援のためのメタラーニング(非ゼロ成分の集合)について検討する。
我々の設定では、各タスクは異なるランダムな真の精度行列を持ち、それぞれが異なる可能性がある。
我々は,Omega(log N)/K)$$nのサンプル数に対して,一致する情報理論の下界を証明した。
- 参考スコア（独自算出の注目度）: 31.41834200409171
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study meta learning for support (i.e., the set of non-zero
entries) recovery in high-dimensional precision matrix estimation where we
reduce the sufficient sample complexity in a novel task with the information
learned from other auxiliary tasks. In our setup, each task has a different
random true precision matrix, each with a possibly different support. We assume
that the union of the supports of all the true precision matrices (i.e., the
true support union) is small in size. We propose to pool all the samples from
different tasks, and \emph{improperly} estimate a single precision matrix by
minimizing the $\ell_1$-regularized log-determinant Bregman divergence. We show
that with high probability, the support of the \emph{improperly} estimated
single precision matrix is equal to the true support union, provided a
sufficient number of samples per task $n \in O((\log N)/K)$, for
$N$-dimensional vectors and $K$ tasks. That is, one requires less samples per
task when more tasks are available. We prove a matching information-theoretic
lower bound for the necessary number of samples, which is $n \in \Omega((\log
N)/K)$, and thus, our algorithm is minimax optimal. Then for the novel task, we
prove that the minimization of the $\ell_1$-regularized log-determinant Bregman
divergence with the additional constraint that the support is a subset of the
estimated support union could reduce the sufficient sample complexity of
successful support recovery to $O(\log(|S_{\text{off}}|))$ where
$|S_{\text{off}}|$ is the number of off-diagonal elements in the support union
and is much less than $N$ for sparse matrices. We also prove a matching
information-theoretic lower bound of $\Omega(\log(|S_{\text{off}}|))$ for the
necessary number of samples. Synthetic experiments validate our theory.
- Abstract（参考訳）: 本稿では,新しいタスクにおける十分なサンプル複雑性を低減し,他の補助タスクから得た情報を用いて,高次元精度行列推定における支援のためのメタ学習(すなわち非ゼロエントリの集合)について検討する。
我々の設定では、各タスクは異なるランダムな真の精度行列を持ち、それぞれが異なる可能性がある。
すべての真の精度行列(すなわち、真のサポートユニオン)の支持の和の和は小さいと仮定する。
異なるタスクから全てのサンプルをプールすることを提案し、$\ell_1$-regularized log-determinant Bregman divergence を最小化して単精度行列を推定する。
高確率で、推定された単精度行列の支持は真の支持結合に等しいことを示し、n 次元ベクトルと $k$タスクに対して、タスク当たりのサンプル数が $n \in o((\log n)/k)$ であることを示した。
つまり、より多くのタスクが利用可能になった場合、タスク毎のサンプルを少なくする。
我々は、必要なサンプル数に対して一致する情報理論上の下限を証明し、これは$n \in \omega((\log n)/k)$である。
すると、新しいタスクでは、$\ell_1$-regularized log- determinant bregman の最小化と、サポートが推定されたサポートユニオンのサブセットであるという追加の制約により、サポートが成功するサポートリカバリの十分なサンプルの複雑さを $o(\log(|s_{\text{off}}|))$ where $|s_{\text{off}}|$ がサポートユニオンの非対角要素の数であり、スパース行列に対して$n$ 以下となることが証明される。
また、必要なサンプル数に対して$\omega(\log(|s_{\text{off}}|))の一致した情報理論下限を証明します。
合成実験は我々の理論を検証する。
関連論文リスト
- Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。
本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文 参考訳（メタデータ） (2024-08-10T04:26:19Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Meta Learning for High-dimensional Ising Model Selection Using
$\ell_1$-regularized Logistic Regression [28.776950569604026]
高次元イジングモデルに関連するグラフを推定するメタ学習問題を考察する。
我々のゴールは、新しいタスクの学習において補助的なタスクから学んだ情報を用いて、その十分なサンプルの複雑さを減らすことである。
論文 参考訳（メタデータ） (2022-08-19T20:28:39Z) - Meta Sparse Principal Component Analysis [31.403997435274604]
高次元主成分分析における支援のためのメタラーニング(非零成分集合)について検討した。
補助的なタスクから学習した情報を用いて,新しいタスクにおける十分なサンプルの複雑さを低減する。
論文 参考訳（メタデータ） (2022-08-18T16:28:31Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Multiple Support Recovery Using Very Few Measurements Per Sample [33.20967869233738]
我々は$mathbbRd$で複数のスパースサンプルの線形測定にアクセスできる。
これらのサンプルは$ell$グループに分割することができ、同じグループに属する同じサポートを持つサンプルがある。
サンプルあたりの$m$測定の予算について、その目標は、$ell$の基盤となるサポートを回復することである。
論文 参考訳（メタデータ） (2021-05-20T16:02:27Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。