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