# Efficient Statistics for Sparse Graphical Models from Truncated Samples

arXiv: https://arxiv.org/abs/2006.09735 · HTML: https://mlsanity.com/paper/2006.09735/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2020.

## Built on by (most cited first, 5 of 5)

- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [Learning from Censored and Dependent Data: The case of Linear Dynamics](https://mlsanity.com/paper/2104.05087/) (2021)
- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [Perfect Sampling from Pairwise Comparisons](https://mlsanity.com/paper/2211.12868/) (2022)
- [Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample](https://mlsanity.com/paper/2509.20993/) (2025)

## Abstract (arXiv)

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(μ,Sigma) and observed only if they belong to a subset S subseteq ℝd. We show that μ and Sigma can be estimated with error ε in the Frobenius norm, using tildeOleft(fractextrmnz(Sigma-1)ε2right) samples from a truncated N(μ,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^topOmega^* + N(0,1) and (bf x, y) is seen only if y belongs to a truncation set S subseteq ℝ. 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(k2 log d) samples are needed to estimate Omega^* in the ℓ_∞-norm up to a bounded error. For both problems, our estimator minimizes the sum of the finite population negative log-likelihood function and an ℓ1-regularization term.