Efficient Statistics for Sparse Graphical Models from Truncated Samples

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

Introduction

Selection bias is a fundamental challenge in statistics, occurring when data is observed only within a specific range or subset of the population. In high-dimensional settings, this "truncation" problem becomes particularly acute. Standard statistical tools often fail because the missing data is not missing at random; rather, the truncation process shifts the mean and warps the covariance of the observed distribution.

This paper addresses the problem of high-dimensional estimation from truncated samples, focusing on two classical problems: the inference of sparse Gaussian graphical models (GGMs) and support recovery in sparse linear models. While recent work has established methods to un-bias samples for general multivariate Gaussians, those approaches typically require a sample complexity that scales quadratically with the dimension ($d^2$). This paper demonstrates that if the underlying model is sparse, parameters can be recovered with a sample complexity that scales with the model's sparsity rather than its total dimensionality.

Problem Formulation

Consider a $d$-dimensional sample ${\bf x}$ generated from a Gaussian distribution $\mathcal{N}(\mu, \Sigma)$. In the truncated setting, ${\bf x}$ is observed only if it belongs to a subset $S \subseteq \mathbb{R}^d$. The set $S$ is assumed to have a non-trivial measure under the unknown distribution but is otherwise arbitrary. To facilitate estimation, the authors assume access to a membership oracle for $S$, which can determine whether any given point $x$ lies within the truncation set.

For sparse linear regression, samples $({\bf x}, y)$ are generated such that $y = {\bf x}^\top{{\Omega}^*} + \mathcal{N}(0,1)$, but the pair is only observed if the response $y$ falls within a truncation set $S \subseteq \mathbb{R}$. The goal is to recover the support of the sparse vector ${\Omega}^*$, where the number of non-zero entries is $k \ll d$.

Methodology

The proposed estimators minimize the sum of the finite population negative log-likelihood of the truncated distribution and an $\ell_1$-regularization term (Lasso).

1. Sparse Gaussian Graphical Models

The authors employ a "Graphical Lasso" approach for GGMs. The precision matrix (the inverse covariance $\Sigma^{-1}$) represents the graph structure, where non-zero entries correspond to edges between variables. Although the log-likelihood for truncated data is mathematically complex, the authors prove it remains locally strongly convex near the true parameters. By applying an $\ell_1$ penalty, the estimator effectively "zeros out" insignificant entries in the precision matrix, identifying the underlying graph structure.

2. Sparse Linear Regression

For linear models, a similar Lasso-style penalty is applied to the regression coefficients. The authors utilize the primal-dual witness method—a sophisticated technique in high-dimensional statistics—to establish the conditions under which the estimator correctly identifies the "support" (the set of active features) of the model.

Key Theoretical Insights

Sparsity and the Curse of Dimensionality

The core contribution of this work is the reduction of sample complexity. For GGMs, the complexity is reduced from $O(d^2)$ to $\tilde{O}(\frac{\textrm{nz}(\Sigma^{-1})}{\epsilon^2})$, where $\textrm{nz}$ denotes the number of non-zero entries. For sparse linear regression, the authors show that $O(k^2 \log d)$ samples are sufficient to recover the support of ${\Omega}^*$ in the $\ell_\infty$-norm up to a bounded error.

Hessian Consistency and Local Convexity

A critical observation in the paper is that the finite population log-likelihood (based on $n$ samples) and the infinite population version share the same Hessian. This implies that the geometric curvature required for optimization is preserved even with limited data. However, unlike the standard Lasso, the truncated version is not globally strongly convex. The objective is well-behaved only within a specific radius around the true parameters, which necessitates careful initialization or specific regularization tuning.

Experimental Validation

The theoretical findings were validated using synthetic datasets:

  • GGM Simulation: A 10-dimensional Gaussian distribution truncated to the interval $[-2, 2]$, with a precision matrix designed to have 30 non-zero entries out of 100.
  • Linear Regression Simulation: Synthetic sparse vectors were used to generate responses truncated by a set $S$.

Results confirmed that the Frobenius norm error decreases at the expected rate of $1/\sqrt{n}$. Furthermore, the Hamming distance—measuring the discrepancy between the estimated and true graph edges—dropped to zero as the number of iterations and samples increased.

Conclusion and Future Work

This research provides the first sample-efficient algorithms for learning sparse models under selection bias. While the sample complexity is optimized, the authors note that computational complexity remains a hurdle. The current use of projected Stochastic Gradient Descent (SGD) is sensitive to initialization due to the local nature of the objective's convexity.

Future research directions include the development of polynomial-time algorithms that do not require "near-truth" initialization and the establishment of finite-sample bounds for the structure of GGMs rather than just parameter values.

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 ${\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.
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