Efficient Statistics for Sparse Graphical Models from Truncated Samples

Arnab Bhattacharyya, Rathin Desai, Sai Ganesh Nagarajan, Ioannis Panageas

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 x are generated from a Gaussian N(mu, Sigma) and observed only if they belong to a subset S of R^d. We show that mu and Sigma can be estimated with error epsilon in the Frobenius norm, using O(nz(Sigma^{-1})/epsilon^2) samples from a truncated 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 (x,y) are generated where y = + N(0,1) and (x, y) is seen only if y belongs to a truncation set S of the reals. 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 infinity-norm up to a bounded error. Similar results are also established for estimating Omega in the Euclidean norm up to arbitrary error. For both problems, our estimator minimizes the sum of the finite population negative log-likelihood function and an ell_1-regularization term.

Introduction

In high-dimensional statistics, researchers often rely on the assumption of sparsity—that only a small number of features actually matter—to make learning tractable when the number of features ($d$) exceeds the number of samples ($n$). While algorithms like Lasso are effective in standard settings, real-world data collection is often subject to truncation. For instance, sensors may only record values within a specific range, or financial datasets might exclude individuals below a certain income threshold. If a sample falls outside this "truncation set," it remains hidden.

Previous methods for estimating multivariate Gaussians from truncated samples required sample sizes scaling with $O(d^2)$, which is impractical for high-dimensional problems. This research investigates whether leveraging sparsity can drastically reduce the sample complexity of learning from truncated data.

Methodology

The authors address two core problems: learning sparse Gaussian Graphical Models (estimating the precision matrix) and sparse linear regression (variable selection). Their approach utilizes a penalized maximum likelihood estimator, combining the finite population negative log-likelihood for the truncated distribution with an $\ell_1$-regularization term to encourage sparsity.

  • For Graphical Models: A variant of the Graphical Lasso is employed. The authors prove that the truncated negative log-likelihood remains strongly convex in a neighborhood around the true parameters, allowing the $\ell_1$ penalty to successfully identify the sparse precision matrix.
  • For Linear Regression: A Truncated Lasso estimator is used. To ensure correct identification of non-zero variables (support recovery), the authors adapt the primal-dual witness method, showing that under mild assumptions regarding truncation survival probability and feature correlation, the Lasso solution's support matches the true support.

Empirical Results

The theoretical bounds were validated using synthetic datasets, specifically a 10-dimensional Gaussian distribution truncated to the interval $[-2, 2]$ with a sparse precision matrix (30 non-zero entries out of 100).

Reduction in Frobenius norm error as the number of samples increases.

Experiments confirm that the Frobenius error scales proportionally to $1/\epsilon^2$ with the number of samples. For graphical models, the sample complexity drops from $O(d^2)$ to $\tilde{O}(nz(\Sigma^{-1}))$, where $nz$ is the number of non-zero entries in the precision matrix. For sparse linear regression, the method recovers the exact support of a $k$-sparse model using just $O(k^2 \log d)$ samples.

Discussion and Limitations

A key insight is that convexity is preserved under truncation; the Hessian of the finite population negative log-likelihood matches the infinite population version, maintaining the strong convexity required for Lasso-type estimators. However, several challenges remain:

  1. Optimization Complexity: The objective function is only locally strongly convex, making algorithms like projected Stochastic Gradient Descent (SGD) highly sensitive to initialization and requiring a massive number of iterations to converge.
  2. Asymptotic Error: In linear regression, the $\ell_\infty$-error bound does not vanish as $n \to \infty$, a departure from standard Lasso behavior.
  3. Assumptions: The proofs require stronger normalization assumptions on the design matrix than typical untruncated settings.
Convergence of the Frobenius norm error over 1,000,000 iterations of projected SGD.

Future work will focus on developing faster optimization algorithms and refining error bounds for the linear regression setting.

Summary updated

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 x are generated from a Gaussian N(mu, Sigma) and observed only if they belong to a subset S of R^d. We show that mu and Sigma can be estimated with error epsilon in the Frobenius norm, using O (nz(Sigma^{-1})/epsilon^2) samples from a truncated 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 (x,y) are generated where y = + N(0,1) and (x, y) is seen only if y belongs to a truncation set S of the reals. 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 infinity-norm up to a bounded error. Similar results are also estabilished for estimating Omega* in the Euclidean norm up to arbitrary error. For both problems, our estimator minimizes the sum of the finite population negative log-likelihood function and an ell_1-regularization term.
BibTeX
@inproceedings{bhattacharyya2021efficient,
  author = {Arnab Bhattacharyya and Rathin Desai and Sai Ganesh Nagarajan and Ioannis Panageas},
  title = {{Efficient Statistics for Sparse Graphical Models from Truncated Samples}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=4ggP_EHs03},
}
Figure