Provable Guarantees for Sparsity Recovery with Deterministic Missing Data Patterns
Authors: Chuyang Ke
Jean Honorio
Venue: Accepted by TMLR ()

Abstract: We study the problem of consistently recovering the sparsity pattern of a regression parameter vector from correlated observations governed by deterministic missing data patterns using Lasso. We consider the case in which the observed dataset is censored by a deterministic, non-uniform filter. Recovering the sparsity pattern in datasets with deterministic missing structure can be arguably more challenging than recovering in a uniformly-at-random scenario. In this paper, we propose an efficient algorithm for missing value imputation by utilizing the topological property of the censorship filter. We then provide novel theoretical results for exact recovery of the sparsity pattern using the proposed imputation strategy. Our analysis shows that, under certain statistical and topological conditions, the hidden sparsity pattern can be recovered consistently with high probability in polynomial time and logarithmic sample complexity.

Published in Transactions on Machine Learning Research (02/2024)
Provable Guarantees for Sparsity Recovery with Deterministic Missing Data Patterns
Chuyang Ke
cke @purdue edu
Computer Science
Purdue Universily
Jean Honorio
jhonorio Cemmmmlll edu. on
School of Computing and Information Systems The University of Melbourne
Reviewed on OpenReview: https: // openreview. net/ forum? id- SSQQAupN17
Abstract
We study the problem of consistently recovering the sparsity pattern of regression parameter vector from correlated observations governed by deterministic missing data patterns using Lasso. We consider the case in which the observed dataset: censored by deterministic, non-uniform filter. Recovering the sparsity pattern in datasets with deterministic missing structure can be arguably more challenging than recovering in iifformly-at-randdor scenario. In this paper, we propose an efficient algorithm for missing value imputation by utilizing the topological property of the censorship filter. We then provide novel thcoretical results for exact recovery of the sparsity pattern using the proposed imputation strategy. Our analysis shows that, under certain statistical and topological conditions, the hidden sparsity pattern can be recovered consistently with high probability in polynomial time and logarithmic sample complexity.
1 Introduction
Missing entries in real-world datasets often exhibit deterministic patterns. In federated learning frameworks, sensitive features collected from clients may be censored before being sent to the central server. In electronic health record (EHRs) data, certain lab results may no longer be collected during the postoperative window. Government bureaus may censor certain fields before releasing census data. To deal with missing entries, arguably the most commonly used technique data imputation. Imputation is the process of replacing missing data in dataset with certain computed values. Common imputation strategies include filling missing entries with row column mean, median, mode, extreme values, among others. However, most imputation methods do not come with theoretical guarantees. When talking about the quality of imputation mothods, prior research mainly evaluates the accuracy boost, before and after imputation, on specific downstream test sets (Wang et al., 2019; Liu Gopalakrishnan, 2017; Myrtveit et al., 2001). These metrics being used are application-orientee. On the other hand, we consider imputation itself as the ultimate task alone (i.c., an unsupervised learning task), is well-known that under low-rank assumptions, matrix completion is possible with theoretical guarantees. The drawbacks are: 1) real world datasets might not follow the bessing-at-raddon assumption in (Candès & Recht, 2009; Candes & Plan, 2010; Recht, 2011) or the structural constraints of the deterministic missingness pattern in (Bhojanapalli & Jain, 2014; Burnwal & Vidyasagar, 2020; Chatterjee, 2020; Lee & Shraibman, 2013; Shapiro et al., 2019; Tsakiris, 2023); and most importantly, 2) matrix completion does not, give any guarantee about the downstream tasks utilizing the imputed matrix.
In this paper, we propose the class of censored supersised learning tasks, which the dataset is masked by some deterministic and non-uniform censorship filters. censorship filter removes certain entries from the true dataset, so that the observed part of the dataset contains missing entries in deterministic fashion.

---

Published in Transactions on Machine Learning Research (02/2024)
Furthermore, we pick sparsity recovery the downstream task in our analysis. Also known as feature selection, sparsity recovery is the task of recovering the support set or sporsily pallern of vector w" E IR,, from noisy and correlated observations.
It is worth highlighting, that our goal is not to reinvent sparsity recovery or Lasso. The task itself has been extensively studied the past two decades (Marques et al., 2018; Wainwright, 2009a;b). We also need to highlight, that we are not proposing another heuristic imputation method. Such techniques (filling mean, low rank completion, to name few) have been proposed and extensively applied in the industry. Instead, are proposing unified framework for analyzing the relationship between the sparsity structure in a censored dataset with deterministic missing patterns, and the quality of sparsity recovery, in formal way with with provable gueranlees. A censorship filter applied to the dataset brings new challenges from both the algorithmic side (missing data imputation) and the statistical side (sparsity recovery guarantee), and we are interested in the synergy between these two parts.
Here we briefly discuss the implications and the related works.
Missing Data Techniques. When dealing with missing values in dataset, researchers have been using hcuristic imputation methods since the first day of machine learning. Such methods include filling missing entries with row / column mean, median, mode, extreme values, among others. Another examples include using random forests for imputation (Stekhoven & Bühlmamn, 2012; Van Buuren et al., 1999) and multiple imputation (Carpenter & Kenward, 2012; Murray, 2018). However, it is known that these imputation methods rarely have theoretical guarantees in specific machine learming tasks, including sparsity recovery. Regarding missing data patterns, Fletcher Mercaldo & Blume (2020) proposed the idea of pattern submodels, that is, training set of submodels for every possible missing value pattern in the observed data. Such approach will be computationally expensive if the missing data pattern is nontrivial. Our goal is to design imputation method, that is computationally efficient without training multiple submodels, and has theoretical guarantees in the context of sparsity recovery.
Sparsity Recovery. The problem of sparsity recovery has been studied extensively during the past 20 years. One of the most widely used algorithm is I regularized quadratic programming, also referred to as Lasso. However, most prior literature focus on the fully obscrved case. For instance, Wainwright (2009a); Meinshausen & Yu (2009) provided theoretical guarantees of sparsity recovery through Lasso when the observation matrix is fully observed. In comparison, the number of works that analyze Lasso given that the dataset is partially observed, is limited, Loh & Wainwright (2015) considered so-called corruption mechanism, such that every entry in the original dataset is observed with probability 1 1 8, and unobscrved with probability 0. Nguyen & Tran (2012) proposed a langentially related model, in which part of the cute vector unobserved. The analysis of sparsity recovery guarantee in these cases are usually straightforward, since the pattern of missing entries is uniformly distributed, thus can be viewed as extra noises in the model.
Randomness in Missing Structure. It should be highlighted, that the notion of censorship filters in our paper is different from existing discussion of missing data mechanisms in prior literature. This includes definitions such as Missing At Random (MAR), Missing Completely At Random (MCAR), and Missing Not At Random (MNAR) (Mohan et al., 2013; Little & Rubin, 2019). These mechanisms describe how the probability of observing missing entries relate to the values of the underlying true data, whereas our censorship filter is deterministic, arguably more relevant the real world.
We try to answer the following questions in this paper:
Does there exists an imputation method for missing entries, so that sparsity recovery algorithms can be applied to the imputed dataset?
Under what statistical and topological conditions can our workflow correctly and efficiently recover the sparsity pattern?
We propose a simple yet novel sparsity recovery workflow, which 1) imputes the missing entries using their most significant observed neighboring feature, and 2) runs Lasso to recover the sparse pattern using the imputed data. More importantly, our framework can be analyzed rigorously. We provide theoretical
2

---

Published in Transactions on Machine Learning Research (02/2024)
guarantees for the quality of sparsity recovery, in terms of the topological structure of the censorship filter, using the proposed workflow. Our analysis focuses on the case with most significant. neighboring feature only, and this can be easily generalized to more neighboring features.
Summary of Our Contribution. Our work is mostly theoretical. We provide a series of novel results in this paper:
We propose a simple yet novel imputation method to fill the missing entries that are censored by an deterministic censorship filter. Our strategy computes the missing value from its most significant neighboring feature, and can be casily generalized to the case of multiple neighboring features.
We provide provable theoretical guarantees for recovery of the underlying sparsity structure using our imputation method. We analyze the statistical and topological conditions that govern efficient exact recovery. We establish the sample complexity guarantees for our workflow to succeed with high probability. Our theorems also provide guidelines for setting regularization parameters.
2 Preliminaries
In this section, we provide the formal setup of our problem and introduce all notations that will be used throughout the paper.
We first introduce the definition of censorship filters. We use (X, y, M) to denote the dataset a supervised learning task, where X 12x is the feature matrix, and E R" is the label vector. A censorship filter M E {0, 1 is a binary matrix applied to the feature matrix X. For every sample & and feature i, Xx, is missing and need
observed by the learner if and only if MR 1. In other words, entries with Mr,, to be imputed. It is worth highlighting that the censorship filter M is deterministic and non-uniform, i.e, there is no randomness in M.
2.1 Censored Sparsity Recovery Model
We now present the application of censorship filters to the task of sparsity recovery. Suppose that there exists unknown fixed vector w² RR, and w² is sparse. We denote its support set as S = {i E [p] w A 0}, and the cardinality of the support set as s S < p. Let X E RRX be the input data generated by nature, such that for every 1s E [m], sample Xx.: E R fulfills: 1) zero-mean; 2) with covariance E; 3) each Xx,s is sub-Gaussian with parameter En,.. Then the labels y E RR" are generated in the form of
Xw" +
where e E RR is the additional zero-mean sub- Gaussian noise with parameter o². It is known that in the fully observed case, the sparsity recovery of S given X and y can be achieved through solving the following 4 constrained quadratic program, known as Lasso:
minimize ur
|| yl + A|[w|1
2n
where À is the regularization parameter. Now a censorship filter M E {0, 13 is imposed on the learner, such that all entries with MR is masked and missing from X.
Our task consists of two parts. First, we want impute X from the observed part of X, such that X = XR. if My. This ensures that the observed entries are not changed. Second, we solve Lasso using the imputed matrix in the form of
1 A u| + A||wal1
minimize
(1)
2n
and we claim that the support set recovered by (1) is consistent with the ground truth. We also include the necessary definitions for completeness.
Definition A 2ero-men mean random variable æ sub- Goussion with porameter 0², if for all > 0, we have E [exp((a:) I 2xp(o212/22) /2).
3

---

Published in Transactions on Machine Learning Research (02/2024)
Definition 2. A zero-mean random vector x (21,...;Pp) :p)) is mub-Gaussian with parameter o², if for all E IRP with ||||| = 1, we have E (exp(uTx)) I exp(o²) /2).
2.2 Notations
Without specification we use lowercase letters (e.g., a, b, u, u) for scalars and vectors, and uppercase letters (e.g., A, B, C) for matrices and sets. For any natural number n, we use [n] to denote the set (l....,,)) n). We use to denote the set of real numbers. We use to denote the all-one vector, and for the all-zero vector. For any vector u, we use diag (u) denote the diagonal matrix with in the diagonal, ||u]] denote the Euclidean norm, ||ull1 to denote the 1 norm, and ||ull to denote the infinity norm. For any matrix A, we use Amin (A) to denote its smallest eigenvalue, ir (A) to denote its trace, ll All to denote its spectral norm, and ||I max; E, |At,l to denote its lx operator norm. We use o to denote the Hadamard product. We use sgn (.) to denote the sign function.
When dealing with entries in a matrix, we use notation to denote the whole row or column. For example, A1; refers to the first row of matrix A. We also use index sets subscripts to sclect submatrices. For example, As,s is the submatrix obtained by deleting all rows and columns with indices that are not in the index set S from A. When the context is clear, example is that A2 denotes the second column of A.
single subscripts to denote the choice of columns. An
We use S to denote the complement of the support set. Similarly, we use M to denote the complement of the censorship filter, algebraically M = 11 M.
In our analysis, we use Edmax == max; Σi,; to denote the maximum diagonal entry in E, and Edmia == min; E,y to denote the minimum.
For distributions, use subG to denote uub-Gaussian distribution, and subE' to denote sub- sub-Exponential distribution.
3 Algorithm
In this section, we setup our censored sparsity recovery problem and provide theoretical guarantees. We first introduce the necessary statistical assumptions and definitions.
Assumption 1 (Positive Definiteness). We assume that the population covariance matriz Σ is positive definite on the support S. In particular, we use B == Amiin > 0 to denote ils smallest eigenvalue. Assumption 2 (Mutual Incoherence). We assume that the population covariance matrix 2 fulfills the mutual incoherence condition "5..s>5 < 1 - 7, for some y E (0,
Recall that X E Raxp is the feature matrix generated by nature, and M E 10,1]axp the deterministic censorship filter. We use XM to denote the observed feature matrix, where (XM))R Xk, a if Ma and (XM)k, = denotes the missing value otherwise.
Let H E RPxp denote the sample covariance matrix. Since only XM is obsorved, zero-mean, and contains missing values, Hij is computed as Hij [M,MI, Ex.M Xx.j
We use := = E Es, to denote the (population) neighbor score of two features i and j. Intuitively, the neighbor score measures how related two features are. A higher neighbor score indicates that more related to j. Similarly,
use G.,y == H Hjjj to denote the empirical neighbor score. Let IT(i) arg max (s) Gij be the top neighbor feature of i. The intuition is that if sample has feature i missing, use its top neighbor feature II(i) to impute it. To simplify analysis we introduce the following assumption.
Assumption 3. We assume that the top neighbor feature of any missing entry is always observed, that is, assume Mg = 0 if Mr, 1.
In practice, one can use the second top feature instead (or third, fourth, etc.), the top feature not observed. The assumption only serves to simplify the proofs by reducing the number of concentrations required.
4

---

Published in Transactions on Machine Learning Research (02/2024)
We 7i to denote the (population) error ratio of feature such that 7; Enoo m()) The molivation is that the error ratio measures how much variance will be gained, if we use the imputed value instead of the true H.moo We now introduce
value in the algorithm. Similarly have the empirical error ratio 9; Hme.. censored sparsity recovery algorithu,, given the observation of the censored dataset.
Algorithm Censored Sparsity Recovery
Input: Observed dataset (XM,y), regularization parameter Output: Imputed feature matrix X, recovered model vector vi
1: Compute sample covariance matrix from XM for every feature pair (i, [p] x [p] do
3: Compute empirical neighbor score ونك = H2,/ H
end for
for every feature i [p] do
Compute top neighboring feature II( = arg jell--ll- Sr,
7: Compute empirical error ratio A H,, Hamno/Hno.au Hno).)))
end for
Initialize imputation matrix X R"x
10: for every entry (k, i) E [n] x [t] do
11: Xx,; 1 Xx,
12: end for
13: Compute imputed matrix X MoX + M
14: Solve the following Lasso program
à
minimize @
l(w) + A|[w|]i
(2)
1 Xw y/
where
I(w) 2n
Algorithm takes the observed dataset as the input and imputes the missing entries given by X. Understand- ably the imputed data X and the true data X are equivalent on the support of M. We use A to denote the imputation error matrix, defined as A = X - X. Naturally Aij = 0 if Mij = 1. After that, our algorithm solves the Lasso program (2), and the support of v gives the recovered support set S.
4 Guarantees of Censored Sparsity Recovery
4.1 Consistency of Imputation through Empirical Score
In this section, we prove consistency of our imputation step, by choosing the top neighboring feature using the empirical neighbor score as in Algorithm 1. The proofs of Theorems and Lemmas can be found in Appendix.
Here is the motivation: in Algorithm 1, we choose II(i) = arg maxje(ri-(tt Gas based on the observed samples, where ? is the empirical score. However, there is no guarantee that the order of is consistent with the underlying true Ç. Our goal is to identify the sufficient. conditions, such that arg max G.j arg max (i) Sig. Equivalently, it is desirable to ensure that, S.n10) > G.j holds if and only if G, > E.. holds with high probability for all j # i.
Our proof relies on the following lemma. The proofs can be found in Appendix.
Lemma For every feature [p], its ratio between the sample variance and population variance fulfills
Σ H S
3 2 4cxxp (-
2 a
P
2
2
512 + 2 2
dmnan
We now present the consistency guarantee for imputation method proposed in Algorithm
5

---

Published in Transactions on Machine Learning Research (02/2024)
Theorem 1. For every feature E [p], if the population neighbor score fulfills (.m(() 3G1 > [m()mmo) + |E + Emmin
for every feature j + I[)), then the sample neighbor score fulfills
P F(c.u 2is 21 512(1 40 2 dmaz
n dman
Consequently, the imputation result from the empirical score is consistent with the impatation result from the population score with high probubilily.
Remark 1. In the statement above we have coefficient of 3. This coefficient is determined by the setting t = -- Eamin in Lemma 1, and can be changed to any constant that is greater but arbitrarily close to 1. This will only affect the constant terms in the high probability statement, and the - -((xp((-n)) rate holds.
4.2 Primal-dual Witness
We prove the correctness of Algorithm 1 for recovering the true support set S, through the primal-dual witness framework and Keiis--Khnn-Tuckee (KKT) conditions at the optimum.
Step Let be the solution (primal variable) to the following restricted problem
minimize wsER"
I((ws, 0)) + A|[ws||1
(3)
with Wss- = O.
Step 2: Let 2 E IR" be the dual variable fulfilling the complementary slackness condition on S. That is, for every i 5, 24 = sgn (w:) w; * 0, and z [-],+1] otherwise.
Step 3: Solve for zs E IR= fulfill the following stationarity conditions:
[V(((s, 0)]ls + Azs = 0
(4)
[V(( 0))ls + Azge = 0
(5)
Step 4: Verify that the strict dual feasibility condition is fulfilled: E loc <
(6)
Since Step through 3 are constructive, it is sufficient to prove Step 4. If the conditions above are fulfilled, our Algorithm 1 recovers the true support with high probability, i.e., S = S, where $ is the support of the recovered vector à in (2) and S is the true support.
4.3 Verifying Strict Dual Feasibility
To verily the strict dual feasibility condition (6), we first consider the quadratic loss function Iww). Note that
1
((w)=
Aw
2n
1
Aw Xw" -cl" -cl
2n
||M o + +Mc X)w (M o X M o oXw" - e||2
2n
1
[I X)(W w²) + (M X)w (M X)w" cl2
2n
We have the gradient
Vi(w)
((M XT X) - w²) + (M o X)w - (M o X)w" c),
n

---

Published in Transactions on Machine Learning Research (02/2024)
and Hessian ( X. In particular, can define the sample covariance matrix of the imputed matrix as f = (2((w) = A
We now consider the restricted problem and the stationarity conditions. Expanding (5) leads
x [M o x)s (wg - w3)) + (M s) - (M X)s c) + Aas = 0,
n
X [ x)s(ūs wg) + (M X)sūs (M1 X)sw3 Azg= 0.
"
Next solve for On the support set we have
1
X [M X)s(ūs w3)) (M X)sus (M X)sw's -c]
28
X (M o x)s( w/))= + (M x)s( w3}) + (M o X - -M oX)s -
An
X 5 ( + (M X - M o X)sws - -c]
An
1 ww3) + Aswss c).
(7)
Similarly on the complement set have
2ge
XJ. Xs(Øs w/) + Asws c]
(8)
An
Rearranging the terms in (7) leads to ws wzz (85 - (83 (Aswz + Anzs). Plugging the last
equation into (8), we obtain 2ge = 2()) + 2(b), where we use the shorthand notation
1 IJ 1 X (x 8s) x (e Asws),
(a) = An
(9)
(0) 8 -
(10)
It remains to verify the strict dual feasibility condition || 1loo = || + 260||| < 1. This can be further
broken down into two parts: first prove that || 7/4, and then prove 11 11. 7/4.
4.4
Bound of 2a))
In this section analyze the upper bound of || For every feature E S and sample & E [n]] we define the following variance proxy
hr = o² x E(+p
(+ ( M)) + Mi,)
iEs
and
(x) == Mx E., + +(1 Mx.) 7 Em
assuming (x)) O. We also denote the maximum variance proxy
Amax max hgs
Imax
max max 9k (i), kg
kEn
across all sample [n). We now provide the statement of the theorem. Theorem 2. By selling the regularization parameter
A 20h Imax/yy
have |=<0)]| <7/4 with probability at least 1 O((p 8) exp(-n)).
7

---

Published in Transactions on Machine Learning Research (02/2024)
Remark 2. Our proofs of Theorem 2 and Theorem 3 to bound 2(*) and 209) rely on the careful analysis of the sub-Gaussian condition of the imputed matrix. Techniques from prior literature do not work in our model, because our missing structure M is deterministic and cannot be reduced to some uniformly random noise. For instance, one classic technique is to write Xg. as a predictor of Xg using the conditional covariance matrix (Wainwright, 2009a). This does not work in our case, because X (imputed matrix) will not cancel with the complement projection on X (original matrix).
Remark 3. One may note that the magnitude of |e - Aswğll is directly related to the quality of regression in the proof above. Intuitively, the whole term measures the noise level in our algorithm: for the noise generated by nature, and Asws for the imputation noise, consisting of the imputation error on the support Ag and the ground truth w/.. This provides the insight, that if the magnitude of w is large, censored sparsity recovery will be harder because of higher imputation noise level.
Proof. Here we consider every feature j S It is worth noting that by definition, &s - is an orthogonal projection matrix to the column space of X, thus for simplicity, we denote the projection Pxg= == Xx) Using Cauchy-Schware inequality and the fact that the norm of orthogonal projection matrix is bounded above by 1, we obtain
(a)
Xxs
(1 -Pxs) (e Aswz))
( 1 (a- 1c-40 (.-Asws)) >| |
(T Pxs)
An
(E Aswğ)
-|,8,)
Xn
||&
||e Asw3ll
An
We proceed to bound ||c Asw3ll || for each entry. For every sample & N, we have
Ck Au,
C₁
Σ
AR
iE9
Σ
(8g,
XR,))u
6k
iES
Ck
(Xa,s XR,))
ieS
6k
( Xk.)
IES
Under the assumption of Xt.; ~ subG(o& subG(o?): note that the entrywise imputation error *.X,.n - Xx,s is sub-Gaussian with parameter (f)E)()) + Ex As a result, e - -R.sw's is sub- Gaussian with parameter h?.
Since samples are independently generated across all k's, we know that c- Agw is a sub Gaussian vector with parameter at most h where hmax maxke]m] ha. Then, by Lemma 4, for all & we have
p P(le plle- Asw > h (n + nt + 22) se
Setting / = and laking square roots, this leads to
P { ||e Aswsll > hmax v 5n Se
8

---

Published in Transactions on Machine Learning Research (02/2024)
Next we bound | For every sample h, Xx.5 is sub- Gaussin with parameter ox Ma. = 1, or with parameter ox E otherwise. In particular, the latter is bounded by foo with probability least 1 1 (exx((nn)) using Lemma Put together, X is subsSanssian with parameter at most gx) Since samples are independently generated across all k's, we know that X3 a sub-Gaussian vector with parameter most Xmax(j) = maxken (x()).. Then, by Lemma 4, for all >> 0 we have
P{
P
Imax gmnxx (n) + 2v 21) se
Setting & = n, this leads to
{[| Imax (j)v5n S sen
P
Combining both parts above, with probability at least 1 - -(exx((x-)) we require that
(a)
|| Asw3ll ||
An
Mimax V5n Imna ())
An
mas (i)
Our goal is to ensure that 2) (a)
is less than 7/4 for all j E S Thus, the high probability sufficient condition
is
20 20 Imax (//7.
Taking union bound for all j E S leads to the final result.
4.5 Bound of (b)
Here we provide the upper bound for 2(0), Our analysis relies on the following auxillary lemma.
Lemma 2. Under the mild condition 7 6/7, the sample covariance matrix H. fulfills the reutual incoherence
condition
Hss: Hss.ssHsss
< 7722,
00
with probability at least 1- (s(p - 3) exp
(- ) -0 exp
(32
(
8'-2n (2n2" "-11-]3
))
Theorem Under the mild condition 7
<
6/7, we have ||=00)||
S - 7/4 with probability at least
1 1- 1-00 s) exp (- (- -0 -0(32 (s²exp exp
g2,2n )) - 0 (s2exp
(1111//233 ))
92,2n
(11
Proof. Note that
(0)
xJ 1JJA&((XJ -1
20
x 8J.85(82 (8. 8z)
|28|l0c
8J. 88 8s)
H.. 8.8
+
(fss - -
+ Hs s (1 H
+ +|| Hs s Hg
We use the shorthand notation denote the last four terms above, where HH, = Hss HH2 =
(ffses- H5,, HH3 Hs.s (f= Hgg)), and HHa (As.s Hs -13b), respectively.

---

Published in Transactions on Machine Learning Research (02/2024)
Next we bound
|| through |HH4| Regarding HH1, by Lemma 2, with probability at least " )) we have || 51-7/2.
- O 5) exp
0
8² exp
For H2; using Lemma 7, with probability at least 1 - 0 (s² exp (- 89721 x0(1-1/232) )),
we have
HH22ll
Hss.- - Hs..s 5.8
V8
Alses Hsss
H
5.8
2/3
AAss.s Hs,s
<
8
12
Similarly for H3,, with probability of the same order we have
H Ha oo <
Hs H -.
H - fls,s) 11 5,5)
Hss.s H
Hs.s H
A 8.8
< 4/5(1 - 7/2)
Hs.5 - Hs.s
B
12
For H4, with probability of the same order we have
HH S
As
H
A A5. H
0
88
Ass
.
Hsss
Ass.
32
Y
<
12
where the last inequality holds if x2 < 12 (1 - 7/22), which is always true since y is bounded between O and 1.
Combining all four terms above using a union bound, with probability least 1-0 (s(p 8) exp
(- 0²'0
O ( 2 exp
-( )) (s² exp
82 )) we have || I + 12
+ 12
= 7.
13(1~1/2
4.6 Main Result
Armed with the previous results, we present our main contribution. That is, we show that Algorithm recovers the true support with high probability.
Theorem 4. Under the mild condition 7 < 6/7 and by setting the regularization parameter
A 20h 9max/
Algorithm 1 recovers the true support set with high probability, i.e., S S, where S is the support of the recovered vector it in (2) and S is the true support.
Proof. Straightforwardly, by considering the discussion on Section 4.2 and Section 4.3, as well by invoking Theorem 1, Theorem Theorem and Lemma 6.
10

---

Published in Transactions on Machine Learning Research (02/2024)
5 Discussions
In this section, validate the proposed Algorithm 1 through synthetic experiments.
Experiment 1: We test four imputation strategies in the task of censored sparsity recovery, including our method, imputation by zero, imputation by mean, and imputation by median. We generate w" such that features in the support are randomly drawn in -0.25 U [0.25, 1]. X is generated from Gaussian dis, with mean and covariance E. We set the diagonal of Σ to 1, and the off-diagonal to 0.8. We control the number of samples n 1000, number of features p 50, and size of support 10. The variable is the percentage of missing entries in observed X. We plot the probability of censored sparsity recovery P { = 5}
=} and the loo distance || w' loo between the recovered and the true vector, against the percentage of missing entries, in Figure 1a and Figure 1b, respectively. Each trial is run 100 times. Tt can be seen that our imputation strategy outperforms the others on both metrics.
Probability of Sparsity Recovery
Our Method
Zero
0.8
Mean
Median
L-Infinity Distance
0.6
0.6
0.4
0.4
Our Method
0.2
0.2
Zero
Median
0.6
Percentage of Censored Entries
Percentage Censored Entries
(a) Probability of Recovery
(b) loo Distance
Figure Validation across different numbers of missing entries. Our algorithm achieved recovery when 20% of entries are censored with probability at least one half, while other approaches failed with high probability. The vector recovered by our algorithm is also closer to the ground truth.
Experiment 2: We fix the percentage of missing entries to be 20%, and run the same experiment with different n, p, and 8. To present the results, we define a weighted constant = log Tlggsip-a which is derived from the high probability bound in Theorem 2 and 3. We plot the probability of censored sparsity recovery { = S and the foo distance || wolloo between the recovered and the true vector, against C' in Figure and Figure 2b, respectively. Fach trial run 100 times. From Figure 2a, one can see that our method achieved recovery with probability tending to if C' is large enough. This matches our prediction in Theorem 2 and 3.
Experiment 3: One of our contributions, is that we focus on the case when the missing data pattern is deterministic. As highlighted above, our analysis provides exact sparsity recovery guarantees when the missing data admit a nontrivial deterministic pattern. In contrast, low-rank matrix completion either assumes that the entries are missing at random, or imposes some structural constraints to the deterministic missingness pattern, both of which might not be followed by real world datascts. To illustrate this, we consider the case where the observed entries follow chain graph pattern (Figure 3a), where each white entry observed and black entry is not observed. Note that the features the two sides are not observed at the same time. This is common in many real world scenarios. For example, in medical data, certain lab tests serve the same purpose and thus are not conducted at the same time.
In this experiment, we demonstrate that our workflow performs better than low-rank matrix completion, when the observed entrics follow deterministic chain graph pattern as in Figure 3a. The chain width ranges from to 20. We control the parameters by setting n 200, p = 50, and s 10. The other settings are the same in previous experiments. We plot the lo distance || w= be between the recovered and the true vector,
11

---

Published in Transactions on Machine Learning Research (02/2024)
Probability Sparsity Recovery
Our Method
Our Method
0.8
Mean
Mean
L-Infinity Distance
0.6
0.6
0.4
0.4
-6
-2
2
Value
C Value
(a) Probability of Recovery
(b) 1oo
Distance
Figure 2: Validation different C, weighted sample size. Our algorithm achieved recovery C' is large enough,
matching our theoretical findings.
Graph
Chain Graph
Our Methoc
ow Rank Misssooree
2.5
L-frfnity Disennee
MICEForest
50
50
2-
Sampies
Ssmples
100
100
0.4
04
150
160
200
10
20
40
50
200
10
20
50
0
20
Foatures
Foaturns
Chain Graph Wath
(a) Chain Structure
(b) 1ce Distance
Figure 3: Validation across different C, a weighted sample size. Our algorithm achieved recovery C' is large enough,
matching theoretical findings.
against the chain width in Figure 3b. Each trial run 10 times. From Figure 3b, one can that our method is robust than the matrix completion approach when the dataset admits deterministie chain graph pattern. MissForest (Stekhoven & Bühlmann, 2012) and MICEForest (Van Buuren et al., 1999) are better than matrix completion, but slightly worse than our relatively simpler imputation technique. On the other hand, MissForest and MICEForest. are far more complex to study theoretically. Thus, our relatively simpler imputation technique allows for good experimental results, together with a strong theoretical gnarantee of support recovery.
6 Concluding Remarks
In this paper we proposed the idea of censored supervised learning, which a censorship filter masks the dataset in deterministic, non-uniform way. We analyzed the specific of censored sparsity recovery, and provided imputation strategies and thcoretical guarantees.
We currently use the top neighboring feature to impute the missing value in our algorithm. As future direction, this can be extended to the second, third, ..., neighboring features in a weighted fashion. Another possible option is to take y into account. in the imputation step.
Morcover, would be interesting see if similar strategics and analysis will follow, for other supervised learning tasks masked by some censorship filters. Most of these problems, though commonly encountered in real world applications, do not have theoretical guarantees about imputation quality.
12

---

Published in Transactions on Machine Learning Research (02/2024)
References
Srinadh Bhojanapalli and Prateek Jain. Universal matrix completion. In Proceedings of the 31st International Conference on Machine Learning, volume 32, pp. 1881-1889, 2014.
Shantanu Prasad Burnwal and Mathukumalli Vidyasagar. Deterministic completion of rectangular matrices using Asymmetric Ramanujan graphs: Exact and stable recovery. IEEE Transactions on Signal Processing, 0433834-8845 2020.
Emmanuel Candes and Yaniv Plan. Matrix completion with noise. Proceedings of the IEEE, 98(6))925-933 2010.
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics, 9(6):717- 772, 2009.
James Carpenter and Michael Kenward. Multiple impulation and its application. John Wiley & Sons, 2012.
Sourav Chatterjee. A deterministic theory of low rank matrix completion. IEEE Transactions on Information Theory, (0(12):8046-80555) 2020.
Sarah Fletcher Mercaldo and Jeffrey D Blume, Missing data and prediction: the pattern submodel. Bio- statistics, 21(2)233-225) 2020.
Daniel Hsu, Sham Kakade, and Tong Zhang. A tail inequality for quadratic forms of subgaussian random vectors. Electronic Communications in Probability, 17:1-6, 2012.
Troy Lee and Adi Shraibman. Matrix completion from any given set of observations. In Advances in Neural Information Processing Systems, volume 26, 2013.
Roderick JA Little and Donald B Rubin. Statistical analysis with missing data, volume 793. John Wiley & Sons, 2019.
Yuzhe Liu and Vanathi Gopalakrishnan. An overview and evaluation of recent machine learning imputation methods using cardiac imaging data. Dala, 2(1):8, 2017.
Po-Ling Loh and Martin J Wainwright. Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima. The Journal of Machine Learning Research, 16(1):559 616, 2015.
Flaine Crespo Marques, Nilson Maciel, Lirida Naviner, Hao Cai, and Jun Yang. A review of sparse recovery algorithms. IEEE access, 7:1300 1322, 2018.
Nicolai Meinshausen and Bin Yu. Lasso-type recovery of sparse representations for high-dimensional data. The annals of statistics, 37 37(1)2246 270, 2009.
Karthika Mohan, Judea Pearl, and Jin Tian. Graphical models for inference with missing data. In Proceedings of the 26th International Conference on Neural Information Processing Systems- Volume 1, pp. 1277 1285, 2013.
Jared S Murray. Multiple imputation: a review of practical and theoretical findings. Statistical Science, 33 125 2018.
Ingunn Myrtveit, Erik Stensrud, and Ulf H. Olsson. Analyzing data sets with missing data: An empirical eval- uation of imputation methods and likelihood-based methods. IEFE Transactions on Software Engineering, 27(11)9999 1013, 2001.
Nam H Nguyen and Trac D Tran. Robust lasso with missing and grossly corrupted observations. IEEE transactions information theory, 59(4):2036 2058, 2012.
Pradcep Ravikumar, Martin Wainwright, Garvesh Raskutti, and Bin Yu. High-dimensional covariance estimation by minimizing 11-penalized log-determinant divergence. Electronic Journal of Statistics, 5: 935 385-980, 2011.
13

---

Published in Transactions on Machine Learning Research (02/2024)
Benjamin Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12(104): 3413-3430, 2011.
Alexander Shapiro, Yao Xie, and Rui Zhang. Matrix completion with deterministic pattern: A geometric perspective. IEFE Transactions on Signal Processing, 67(4):1088-110) 011110888110,,,,, 2019.
Daniel J. Stekhoven and Peter Bühlmann. MissForest: non-parametric missing value imputation for mixed-type data. Bioinformatics, 28(1):112 118, 2012.
Manolis C. Tsakiris. Low-rank matrix completion theory via Plücker coordinates. IEEE Transactions Pottern Analysis and Machine Intelligence, 45(8):10084 10099, 2023.
S. Van Buuren, Н. C. Boshuizen, and D. Knook. Multiple imputation of missing blood pressure covariates in survival analysis. Statistics in Medicine, 18(6):681-6944 1999.
Martin J Wainwright. Sharp thresholds high-dimensional and noisy sparsity recovery using 1l-constrained quadratic programming (Lasso). IEEE Iransactions on information theory, 55(5):2183 2202, 2009a.
Martin J Wainwright. Information-theorett limits on sparsity recovery in the high-dimensional and noisy setting. IEFE Iransactions on information theory, 55(12):5728 5741, 2009b.
Xiaojic Wang, Rui Zhang, Yu Sun, and Jianzhong Qi Doubly robust joint learning for recommendation data missing not at random. In International Conference on Machine Learning, pp. 6638 6647. PMLR, 2019.
14


Reviews:
[{"review_id": "hIxP235yIE", "reviewer": "Reviewer_GeJb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe highlight on the theoretical guarantees for exact sparsity recovery and the establishment of sample complexity guarantees provides a clear indication of the paper's main contributions.\n\nWeaknesses:\n\n1. Comparison with other imputation methods: One significant concern is about experimental comparisons. The paper compares the proposed method with very simple imputation techniques. The paper indeed needs to compare its proposed method with more advanced or state-of-the-art imputation methods to convincingly demonstrate its effectiveness and superiority.\n\n2. Theoretical contributions: While the paper is more theoretically-oriented, it is not clear what new contributions it is making in terms of theoretical techniques. The proof of the theoretical results is mainly based on primal-dual witness construction techniques, which have been developed well in previous work [1].\n\n[1] Wainwright, M.J.. Sharp thresholds for High-Dimensional and noisy sparsity recovery using $\\ell_{1} $-Constrained Quadratic Programming (Lasso). IEEE transactions on information theory, 55(5), pp.2183-2202, 2009.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an efficient algorithm for missing value imputation using the topological property of the censorship filter. The authors provide theoretical guarantees for the exact recovery of the sparsity pattern using their imputation strategy, demonstrating that, under certain statistical and topological conditions, the underlying sparsity pattern can be consistently recovered with high probability.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "There are several areas of the paper that require significant improvement.\n\n1. To enhance the experimental results, the authors should compare their method with a wider variety of imputation techniques, especially those relevant to the problem context as outlined in the paper. This would provide a more in-depth understanding of how the proposed method compares to existing techniques.\n\n2. The authors should highlight more clearly the unique insights or techniques they are introducing in this field of research. If there are novel aspects to how they're applying the primal-dual witness construction approach to this particular problem, these should be emphasized and discussed in more detail.\n\n3. The paper would be greatly enriched by a more comprehensive discussion of its limitations.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KbxulueicA", "reviewer": "Reviewer_SnfY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "My biggest concern is the considered setting: deterministic censorship filter instead of \"usual\" missing data at random.\nAs stated in the article this setting is very relevant, and that's why it has already been extensively studied under the name of inpainting. It seems to me that the article is completely missing this part of the literature, see for instance [3] or [4] for a review.\n\nExperimentally:\n- As far as I understand, the imputation algorithm is completely decorrelated from the algorithm applied after, so why not compare it to very standard imputation techniques such as MissForest [1] or MICE-Forest [2]\n\n- Lasso techniques are usually applied when the number of feature $p$ is much larger than the number of samples $n$, hence the proposed imputation technique seems to require $n \\times p^2$ compute\n\n- If all the features are normalized, i.e., $\\| X_j \\|$, it seems to me that the feature that will correlate the most with $j$, will be $j$, and thus assumption 3 requires the missing entry to be observed. Could you comment on this?\n\n\n[1] Stekhoven, D.J. and Bühlmann, P., 2012. MissForest—non-parametric missing value imputation for mixed-type data. Bioinformatics, 28(1), pp.112-118.\n\n[2] Van Buuren, S., Boshuizen, H.C. and Knook, D.L., 1999. Multiple imputation of missing blood pressure covariates in survival analysis. Statistics in medicine, 18(6), pp.681-694.\n\n[3] Yun, T., Jung, H. and Son, J., 2023. Imputation as Inpainting: Diffusion models for SpatioTemporal Data Imputation.\n\n[4] Elharrouss, O., Almaadeed, N., Al-Maadeed, S. and Akbari, Y., 2020. Image inpainting: A review. Neural Processing Letters, 51, pp.2007-2028.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose an algorithm to input missing data.\nThen, under standard restricted strong convexity and mutual incoherence assumption, they derive sparse recovery properties when a Lasso is applied to the inputted data.\nThe authors validate their claims on synthetic data: they empirically show that their algorithm yields better sparsity recovery compared to the usual mean and median imputation techniques.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Perform a literature review on inpainting and compare with previous results\n- At least add MICE and Miss Forest in the experiments\n- A standard inpainting technique would be nice as well", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "hZWztCCbDK", "reviewer": "Reviewer_7JCj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a paper whose prior versions I have reviewed twice, once for NeurIPS '22 and once for ICML '23. I personally find the problem interesting and important, and the theoretical contribution worth of publication. Also, the presentation of the current manuscript has been improved with respect to earlier versions (this was one of the main critiques).\n\nThe authors seem to have ignored several suggestions that were given to them, such as 1) specific suggestions for improving clarity, 2) discussing the literature more deeply, and 3) improving the strength of their experiments. Since the contribution is mostly theoretical and the TMLR insists on clarity, 1) and 2) are more serious than 3). Regarding clarity 1) please see the easily fixed points 2 and 3 in the next box. Regarding literature 2), I am very surprised that the authors have chosen to persist on the following writing (even though this was pointed out to them by multiple reviewers), which gives a false impression to the non-expert reader but also does injustice to several existing works on low-rank matrix completion which do give theoretical guarantees under deterministic observation patterns:\n\nA) First paragraph of the introduction (page 1): \"...matrix completion is possible with theoretical guarantees (Candes & Recht, 2009). The drawbacks are: 1) the missing-uniformly-at-random assumption is highly ideal for real-world datasets and ...\"\nB) Experiment 3 (page 12): \"In contrast, low rank matrix completion assumes that the entries are missing uniformly at random, which is highly ideal for many real world datasets.\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the problem of sparse linear regression with missing data. Specifically, the objective is to estimate the support of the sparse regression vector $w \\in \\mathbb{R}^p$ from knowledge of the measurements $y \\in \\mathbb{R}^n$ together with an incomplete version $X \\odot M$ of the input data matrix $X \\in \\mathbb{R}^{n \\times p}$; here $M$ is a deterministic $\\{0,1\\}$-matrix that can be thought of as a masking filter. The paper develops theoretical guarantees for the successful recovery of the support of $w$, upon running Lasso on $(\\hat{X},y)$, where $\\hat{X}$ is an imputed version of the incomplete matrix $X \\odot M$, obtained by a simple process.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please revise the writing regarding A) and B) above. \n\n2. The output of Algorithm 1 is the imputed matrix \\hat{X} and the estimated model vector \\tilde{w}. Thus when it is written in the beginning of section 4.2 that the correctness of Algorithm 1 is going to be proved, the reader understandably may think that error bounds for the imputation error and the estimation of w are going to be given. However, all that is being done is to prove that the support of \\tilde{w} is the correct one. Please revise the writing to explain what is you mean by \"We prove the correctness of Algorithm 1\". \n\n3. This is a comment that was given in prior reviews but ignored by the authors: There should be a theorem saying that \"if conditions such and such hold, then the support of \\tilde{w} given by Algorithm 1 is equal to the support of \\tilde{w*}\". Currently no such theorem exists.", "broader_impact_concerns": "-", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of sparse linear regression with missing data, where the feature matrix is assumed to be incomplete.
The main contribution of this paper is the theoretical analysis to guarantee the successful recovery of support by a simple two-stage approach (imputing feature matrix with missing data + standard Lasso).

All three reviewers acknowledge the theoretical contributions of this paper and recommend its acceptance. The primary concerns raised by the reviewers pertain to the paper's lack of discussion with existing works and its writing clarity. During the author-reviewer discussion period, the authors merely responded to the reviewers without submitting a revision. Subsequently, the authors submitted a revised version addressing these comments. After reviewing the revision, I concur with the reviewers' recommendation to accept the paper. I also have additional two very minor comments regarding the writing and related work:
1. The title of section 4.3 does not seem to perfectly reflect its content. The beginning of section 4.3 is not well connected to the previous sections; the authors may consider adding a sentence such as, "To verify the strict dual feasibility condition (6), "

2. The authors may also briefly discuss the following related work on low-rank matrix completion with deterministic patterns:  

M.C. Tsakiris. Low-rank matrix completion theory via Plucker coordinates, IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 2023.
Decision: Accept (poster)