论文标题
在高维精度矩阵估计中支持恢复的元学习
Meta Learning for Support Recovery in High-dimensional Precision Matrix Estimation
论文作者
论文摘要
在本文中，我们研究了在高维精度矩阵估计中恢复支持的元学习（即，非零条目集），从而通过从其他辅助任务中汲取的信息来降低新任务中足够的样本复杂性。在我们的设置中，每个任务都有不同的随机真实精度矩阵，每个矩阵可能都有不同的支持。我们假设所有真实的精度矩阵（即，真正的支撑联盟）的支撑符号的大小很小。我们建议通过最小化$ \ ell_1 $ regularized log-determined bregman divergence来估算单个精度矩阵，从而汇总所有样本中的所有样本。我们表明，有可能，估计的单个精度矩阵的\ emph {不正确}的支持等于真正的支持联盟，前提是o（（（\ log log n）/k）$的每个任务$ n \，对于$ n $ dimensional-dimensional-dimensional-dimensional vectors和$ k $ task。也就是说，当有更多任务可用时，每个任务的样本需要更少。我们证明了必要数量的样本数量的匹配信息理论下限，即$ n \ inω（（（\ log n）/k）$，因此，我们的算法是最小值的。然后，对于新颖的任务，我们证明了$ \ ell_1 $调节的对数确定的Bregman差异的最小化，并具有额外的限制，即支持是估计的支持联盟的一个子集，可以将成功的成功支持恢复的足够样本复杂性降低到$ o（\ o（\ log（\ log）（\ s _ s _ {| s _ {\ nrew} $ {$ nrep} $ {$ {是支持联盟中的非对角线元素的数量，而稀疏矩阵的数量远小于$ n $。我们还证明了$ω（\ log（| s _ {\ text {off}} |））$的匹配信息理论下限，用于必要数量的样本。合成实验验证了我们的理论。
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 Ω((\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 $Ω(\log(|S_{\text{off}}|))$ for the necessary number of samples. Synthetic experiments validate our theory.
