Learning High-dimensional Gaussians from Censored Data
Arnab Bhattacharyya, Constantinos Daskalakis, Themis Gouleakis, Yuhao Wang · 2025
Read Learning High-dimensional Gaussians from Censored Data by Arnab Bhattacharyya, Constantinos Daskalakis, Themis Gouleakis, Yuhao Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-19446.txt.
Introduction
Arnab Bhattacharyya and three colleagues design algorithms that learn a high-dimensional Gaussian distribution when parts of each sample are missing, in a 2025 paper. The missingness is not random: a known rule decides which coordinates get hidden based on the values themselves. The team studies two versions of the problem, self-censoring and linear thresholding.
In the self-censoring case, each coordinate shows only when its value falls in an allowed set. Their algorithm recovers the distribution from a polynomial number of samples, provided coordinate pairs are seen often enough. For threshold rules they give an efficient mean estimator under similar visibility conditions. The work matters for data sets where sensors or surveys drop entries in patterned ways.
Catalog record
| CREATOR | Arnab Bhattacharyya, Constantinos Daskalakis, Themis Gouleakis, Yuhao Wang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-19446
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning High-dimensional Gaussians from Censored Data Arnab Bhattacharyya, Constantinos Daskalakis, Themis Gouleakis, Yuhao Wang Abstract We provide efficient algorithms for the problem of distribution learning from high-dimensional Gaussian data where in each sample, some of the variable values are missing. We suppose that the variables are missing not at random (MNAR) . The missingness model , denoted by 𝕊 ( 𝐲 ) \mathbb{S}(\mathbf{y}) , is the function that maps any point 𝐲 ∈ ℝ d \mathbf{y}\in\mathbb{R}^{d} to the subsets of its coordinates that are seen. In this work, we assume that it is known. We study the following two settings: (i) [ Self-censoring ] An observation 𝐱 \mathbf{x} is generated by first sampling the true value 𝐲 \mathbf{y} from a d d -dimensional Gaussian 𝒩 ( 𝝁 ∗ , 𝚺 ∗ ) \mathcal{N}(\bm{\mu}^{*},\mathbf{\Sigma}^{*}) with unknown 𝝁 ∗ \bm{\mu}^{*} and 𝚺 ∗ \mathbf{\Sigma}^{*} . For each coordinate i i , there exists a set S i ⊆ ℝ d S_{i}\subseteq\mathbb{R}^{d} such that x i = y i x_{i}=y_{i} if and only if y i ∈ S i y_{i}\in S_{i} . Otherwise, x i x_{i} is missing and takes a generic value (e.g “?”). We design an algorithm that learns 𝒩 ( 𝝁 ∗ , 𝚺 ∗ ) \mathcal{N}(\bm{\mu}^{*},\mathbf{\Sigma}^{*}) up to TV distance ε \varepsilon , using poly ( d , 1 / ε ) \textup{poly}\left(d,1/\varepsilon\right) samples, assuming only that each pair of coordinates is observed with sufficiently high probability. (ii) [ Linear thresholding ] An observation 𝐱 \mathbf{x} is generated by first sampling 𝐲 \mathbf{y} from a d d -dimensional Gaussian 𝒩 ( 𝝁 ∗ , 𝚺 ) \mathcal{N}(\bm{\mu}^{*},\mathbf{\Sigma}) with unknown 𝝁 ∗ \bm{\mu}^{*} and known 𝚺 \mathbf{\Sigma} , and then applying the missingness model 𝕊 \mathbb{S} where 𝕊 ( 𝐲 ) = { i ∈ [ d ] : 𝐯 i T 𝐲 ≤ b i } \mathbb{S}(\mathbf{y})=\{i\in[d]:\mathbf{v}_{i}^{T}\mathbf{y}\leq b_{i}\} for some 𝐯 1 , … , 𝐯 d ∈ ℝ d \mathbf{v}_{1},\dots,\mathbf{v}_{d}\in\mathbb{R}^{d} and b 1 , … , b d ∈ ℝ b_{1},\dots,b_{d}\in\mathbb{R} . We design an efficient mean estimation algorithm, assuming that none of the possible missingness patterns is very rare conditioned on the values of the observed coordinates and that any small subset of coordinates is observed with sufficiently high probability. 1 INTRODUCTION Missing data is a quite prevalent factor contributing to bias in statistical inference. It arises from various causes, such as limitations in instruments leading to unreliable data, incomplete data collection resulting in missing relevant information, societal biases influencing the suppression of observations, behavioral biases leading to subjects dropping out of studies or avoiding survey questions, ethical, legal, or privacy considerations restricting the utilization of collected data, and other similar factors. Unfortunately training models without consideration of missing data can lead to models that incorporate biases in the training data and make incorrect predictions, which may in turn reinforce those biases when the models are deployed. Since the early days of statistics, missing data has been a well-known challenge in statistical inference, which occurs in a variety of domains, such as biology, physics, clinical trial design, genetics, economics, survey research, and the social sciences. It has motivated a vast effort towards developing methodologies that are more robust to missing data. As example, we refer the reader to some of the early works in statistics [ Gal98 , Pea02 , PL08 , Lee14 , Fis31 ] , some standard references in statistics and econometrics [ Tob58 , Ame73 , HW77 , Hec79 , HM98 , LR19 ] , works targeting missing data in specific domains [ War92 , BK96 , TCS+01 , ABM08 , HK10 ] , books overviewing this literature [ Mad86 , B+96 , BC14 ] , and finallly some recent work in computer science [ MPT13 , DGTZ18 , DGTZ19 , DRZ20 , DKTZ21 , DSYZ21 , KTZ19 , FKT20 , Ple21 ] . The effect that data misssingness has on statistical inference depends heavily on the missingness model. In general, missingness models in which the value of some datapoint influences whether or not it will be missing from the dataset are harder to deal with compared to models in which this happens randomly. Techniques that have been extensively researched in scenarios where missingness either does not depend on the data or only depends on the observed data are referred to as missing completely at random (MCAR) and missing at random (MAR) respectively [ Rub76 , Tsi06 , LR19 ] . In problems where missing entries depend on the underlying values which are themselves censored, known as missing not at random (MNAR), is substantially more difficult and less explored [ RG97 , RR97 , SRR99 , SMP15 , ALJY20 ] . The MNAR model is quite often relevant in practical applications. For example, the depression registry for mental health status is more likely to have missing questionnaires leading to the self-censoring missingness [ CMW+21 ] . Data are missing by design due to the limitations of measurement resources, or the treatment discontinuation when participants go off-control due to the lack of tolerability [ LDC+12 ] . The goal of this work is to advance our understanding of density estimation in the non-asymptotic sample regime when data is missing not at random. In particular, we consider the standard task of high-dimensional Gaussian distribution estimation, albeit in settings where every sample of the Gaussian may have a subset of its coordinates censored and which subset this is depends on the sample itself. We consider two models for how the censoring may depend on the sample: • Self-censoring model (see Section 1.1.1 ): in this model, a sample \mathbf{y} is drawn from an underlying Gaussian distribution {\cal N}({\bm{\mu}}^{*},{\mathbf{\Sigma}}^{*}) , and each coordinate y_{i} of this sample is censored (i.e. replaced with a ‘?’) depending on whether or not it satisfies a coordinate-specific Boolean predicate, i.e. whether S_{i}(y_{i})=1 or not. • Linear thresholding model (see Section 1.1.2 ): in this more challenging model, whether or not each coordinate is seen depends on whether the whole sample satisfies a coordinate-specific predicate. Our goal in both cases is to identify conditions on the predicates and the underlying distribution under which their parameters can be estimated computationally and sample-efficiently in each of the aforedescribed models. Our work advances prior research on Gaussian estimation in the presence of MNAR data in the non-asymptotic sample regime along the following axes: • Gaussian estimation under censoring (see e.g. the classical works of [ Gal98 , Pea02 , PL08 , Fis31 ] and the ensuing literature): Prior work on this problem in the non-asymptotic sample regime studies the “all-or-nothing setting,” where either all coordinates or no-coordinate can be observed [ DGTZ18 ] . They also require that some absolute constant fraction of the Gaussian can be observed. In comparison to this work, we allow heavily corrupted data where no such constant fraction exists where no coordinate is missing. However, we allow the predicate determining the censoring of coordinate i to either be very general but only dependent on this coordinate (self-censoring model), or depend on all coordinates but be simpler, namely a hyperplane (linear-thresholding model). • Gaussian estimation under self-selection (see e.g. the classical work of [ Roy51