A Pairwise Pseudo-likelihood Approach for Matrix Completion with Informative Missingness
Authors: Jiangyuan Li
Jiayi Wang
Raymond K. W. Wong
Kwun Chuen Gary Chan
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Identifiability; missing not at random; U-statistics
Primary area: other

Abstract: While several recent matrix completion methods are developed to deal with non-uniform observation probabilities across matrix entries, very few allow the missingness to depend on the mostly unobserved matrix measurements, which is generally ill-posed. We aim to tackle a subclass of these ill-posed settings, characterized by a flexible separable observation probability assumption that can depend on the matrix measurements. We propose a regularized pairwise pseudo-likelihood approach for matrix completion and prove that the proposed estimator can asymptotically recover the low-rank parameter matrix up to an identifiable equivalence class of a constant shift and scaling, at a near-optimal asymptotic convergence rate of the standard well-posed (non-informative missing) setting, while effectively mitigating the impact of informative missingness. The efficacy of our method is validated via numerical experiments, positioning it as a robust tool for matrix completion to mitigate data bias.

A Pairwise Pseudo-likelihood Approach for Matrix Completion with Informative Missingness
Jiangyuan Li
Jiayi Wang"
Department of Statistics Texas A&M University College Station, TX 77843 jiangyuanli$te iataan..uuu....... edu
Department of Mathematical Sciences University of Texas at Dallas Richardson, TX 75080 j jiayi. waggiiiaggguu
Raymond K. W. Wong Department of Statistics Texas A&M University College Station, TX 77843 raywong@tamu,co edu
Kwun Chuen Gary Chan Department of Biostatistics University of Washington Seattle, WA 98195
kcgchan edu
Abstract
While several recent matrix completion methods are developed to deal with non- uniform observation probabilities across matrix entries, very few allow the missing- ness to depend on the mostly unobserved matrix measurements, which is generally ill- ill-posed. We aim tackle subclass of these ill-posed settings, characterized by flexible separable observation probability assumption that can depend on the matrix measurements. We propose regularized pairwise pseudo-likelhhood approach for matrix completion and prove that the proposed estimator can asymptotically recover the low-rank parameter matrix up to identifiable equivalence class of a constant shift and scaling, at a near-optimal asymptotic convergence rate of the standard well-posed (non-informative missing) setting, while effectively mitigating the impact of informative missingness. The efficacy of our method is validated via numerical experiments, positioning robust tool for matrix completion mitigate data bias.
Introduction
The goal of matrix completion is to recover target matrix from its noisy and incomplete measure- ments. It is modern high-din high-dimensional missing data problem. Despite various significant advances made in the last two decades [e.g., 7, 17, 20, 18), many works on matrix completion still focus on the missing-at- at-random mechanism. Although such an assumption is doubtful in many real-life applications, there very few options available for more general missing data mechanism, espe- cially those with theoretical guarantees. This work aims to provide principled and theoretically well-supported alternative method for miising--ot--t--raddo settings, where missingness could depend on the measurements that are mostly unobserved.
A usual assumption to allow for succeeding matrix completion is that the unknown matrix is low- rank or approximately low-rank. The noiseless setting has been studied in [7] using nuclear norm minimization. The vast majority of existing theories on matrix completion assume that entries revealed with a constant probability with respect to both entry location and measurement value.
'quual contribution
NNo at Google
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Recent approaches to handling entries revealed with nonuniform probabilities, depending on the entry location, have shown the strength to improve matrix completion with solid theoretical guarantees [e.g.. 31, 11, 28, 25, 23, 35]. These works aim to mitigate the effects due to the non-uniformity in observation probabilities [30]. When additional row/column attributes are available, it is also possible to use this additional information for handling the non-uniform missing [e.g., 24]. Although the non-uniform missing mechanism is quite flexible, it is fundamentally different from the missing-not at-random mechanism. The key difference is whether the missing probability depends on the possibly setting, the
unobserved measurement, which we will highlight below. In missing-not----ranee methods developed for the non-uniform missing mechanism could still be biased in matrix recovery. See Section 6 for a numerical example. The method we propose in this work not only deals with (a flexible subclass of) missing-nok -ot--ott-ttte atrano- settings, but it is also applicable in the non-uniform missing settings mentioned above.
In the missing data literature, sielihooddbasse methods for miising-nntt-t-rarme involve specifying a parametric distribution of the missing data mechanism. However, this assumption should be used with caution, it is highly sensitive and may easily induce a misspecified model, resulting in biased estimation and inaccurate results. To circumvent such issues, it is preferable to adopt a missingness assumption as flexible and generally applicable as possible. This type of assumption, often referred to as an unspecified missing data mechanism [37], avoids explicitly specifying parametrie model. Instead of using the full likelihood for estimation, certain unspecified missing-note nossin--ot-at-random assumption allows for the derivation of a non- non-standard likelihood [22], which serves the foundation for subsequent estimation. Such non-standard likelihood approaches have been used in regression analysis [32] and variable selection when confronted with informative missing [37]. One disadvantage of this approach is that not all the unknown parameters estimable due to certain non-identification issues [16, 22].
setrings commonly
approach [22] to matrix completion with a mild separable informative missingness assumption (see Assumption 2.1 in Section 2), which is very flexible and generally applicable. While not all the parameters are estimable, we can identify the dispersion-scalle missingness. This shows great promise to be applied in practice, for example, in recommendation systems where the rankings of entries are of interest.
In this work, we extend the pairwise
matrix up to a constant shift without suffering from bias due to informative
Apart from the informative missing mechanism, our matrix completion method is based on the exponential family model, which has received extensive attention within the matrix completion litera- ture for its efficacy in modeling non-Gaussian data, particularly discrete data. Notably, researchers have investigated its application in specific scenarios such as one-bit matrix completion [10] and multinomial matrix completion [4, 19J. The application of the exponential family model also extends to accommodating unbounded non-Gaussian observations, including Poisson matrix completion [8] and exponential family matrix completion [13, 21].
Overall, the combination of the separable missing-not att-at-random mechanism and the exponential family model allows the proposed method to be applicable in a wide range of settings. We summarize the major contributions of this work as follows.
1. We formulate the pairwise pseudo-likelihood likelihood approach for matrix completion under in- formative missingness and exponential family model. To the best of our knowledge, the pairwise
approach has never been adopted in the matrix completion setup before. As opposed to the classical applications of pairwise pseudo-likelihood that assume i.i.d. sampling, matrix completion problems exhibit non-identical and nigh-dimensional sampling structure.
2. We investigate the identifiability issues of the crucial separable missingness structures (Assumption 2.1) which lies at the core of the pairwise pseudo-likelihood approach.
3. We provide a non-trivial convergence analysis of the proposed estimator up to an identifiable equivalence class. Such analysis involves novel concentration analysis of matrix-valued U-statistics where existing works on this type of concentration is sparse.
To the best of our knowledge, we are one of the first works that consider the missing not at random (MNAR) setting in matrix completion and provide solid theoretical guarantees. [2] claims that they can deal with the MNAR setting. However, they assume selections and noise are independent conditioned on latent factors, shown in their Assumption 2. On the contrary, our
Related Work:

---

setting allows missingness to depend on noise. [15] also addresses informative missingness in matrix completion. However, they require additional covariate information to complete the matrix. Compared to the above two works, our setting is more general as we do not require independence between selections and noise given the true matrix, and we do not need additional covariate information. However, we do require independence across entries given the true matrix. while [2] allows selection to be dependent among different entries. Regarding to the thcoretical bounds, [2] requires additional technical conditions to develop finite sample error bounds, and their bound is point-wise, i.e., the bound is for a given location i. [15] also requires additional conditions on the likelihood and restricted eigenvalues to obtain convergence. Our error bound is developed under relatively weak conditions and achieves the minimax convergence rate.
Models
Let A,
(A.
1 E m be the matrix of interest, which is related to the observation
through generalized linear model. More specifically, we posit that the measurements Ys, of the (i.j)-th entry possesses probability density/mass function of the exponential family form:
[Ax,5i - G( G(Ar.5)) G(Asss)
Vi ~ Su)( (+), fis(y) (U))A,,))) = M(: M(v:d+))s)) )exp
(I)
Φ+
where h IR R$ and G R R are the base measure function and log- ong-pattiionn function associated with the canonical representation, and o. > 0 is the dispersion parameter. Note that this family of distributions covers a wide variety of popular distributions including Bernuull,, Gaussian, and Poisson distributions. For matrix completion problems, we do not have measurements from every single entry. Let Tip be the observation indicator variable of the (i, entry, with value 1 if Yi, is observed and otherwise. We assume that ((Yij, Túy) : = 1,..., mı;j = 1,..., m2) are independent.
-wap--aa-aa--aaaaataaat (USR) mechanism is regarded as one of the simplest missing structures for matrix completion. Under USR, Pr(T., 1|Y,,) is a constant across all j, which implies that the observation indicator Ti is independent of the measurement Y,y. While this has been widely used to simplify theoretical analyses in many prior ground works [c.g.. 7, 6, 17]. USR is strong assumption that can be violated in many applications. To address this issue, a few analyses and methods [e.g., 31, 11, 28, 18, 4, 25, 23, 35) have been developed based on the non-uniform missing structures, where Pr(T.j = 1[,,)) = bij for 0 < by S 1. Here the observation probabilities are allowed to differ across i, j, but the missingness remains independent of the measurement Yij. In this paper, we relax this restriction and allow whether an entry is observed or not to depend on the corresponding possibly unobserved measurement, leading to a challenging missing-not-at-roan (MNAR) setup
Matrix completion under general MNAR is ill ill-posed, leading to non-identifiability of A, (even under standard low-rank assumption). Indeed, general MNAR is ill-posed [33] not only in matrix completion, but also in regression [28, 31] and statistical inference [26] in general. However, some additional structure imposed within the MNAR setting can ensure identifiability. To proceed, we make the following assumption, which corresponds to flexible subclass of MÑAR settings. This assumption makes it possible to identify A, up to some equivalence relations (see Section 3).
Assumption 2.1. The observation probability is separable in the following sense: Pr(T;j 1\ (iys(Y)) for some 4aj E (0, 1] and some non-negative function s(-) : R IR+
As will be made clear later, the proposed technique does not require the knowledge of s(.) and (4aj):
A similar condition has been widely used in various regression problems [c.g.. 22, 29, 37]. These works posit an i.i.d. setup with additional covariates, while our setup does not imply identically distributed assumption across locations and has no covariates. Moreover, in our setup, it is not possible to observe replicates in the same location, while the i.i.d. setup generally allows replicates. Assumption 2.1 is flexible and widely applicable. Not only does it accommodate USR, also includes non-uniform missing mechanism as a special case, where we can set s(.) = 1 and leave (tiz) } variable to account for the non-uniform missing. Obviously, as the observation probability is allowed to depend on possibly unobserved Y.j. it also includes many MNAR settings.
Clearly, we only have access to the observed data, i.e., Yi, conditional on Tú 1. To estimate A., we first look at the observed data likelihood of the (i, entry: Pr(Yi Tig A; ø) for
3

---

A E R and Φ > 0. By the Bayes' Theorem and Assumption 2.1,
Pr(T., fYg A, Φ) Pr(Yo]TT = L:A, Φ) JPr(T, = (Y, O)dY.
(((s I s(y) (v: A, O)dy
(Y, = (A
o),
where b, (A, Φ) = 1/ s (1y(f ( d) We see that the conditional likelihood involves unknown functions s(-) and (.), which makes the estimation of A. difficult. To address this issue, adopt a licelo-ikeeihood approach [22] based on local ranks.
Pseudo-likelihood approach
Let & = (ei,.... Cn) S (1..... mi} x (1....,m2 be lexicographically ordered set of n unique locations ((i.j) Tip = -. (Indeed, the specific choice of ordering does not matter.) Let the corresponding measurements be Y = (YI,..., Yn) = (Ye....., Ye,) and the observation indicator be T (Ti...., Tn)) (Te,...., Te..). ). We also write A = Aec for h -,...,.0 the vector Y into two vectors: the order statistics Yo) (Y())..., Y(n)) and the rank statistics R R= (R...... Rm). Precisely, Yoj is the j-th smallest entry in Y and Rş is the rank of the k-th entry in Y. To motivate the proposed pseudolikelihood in (3), we first consider the conditional likelihood based on the full rank statistics given the observed data:
n. We decompose
I (Yk) (Yn (Yk; A)
Pr(R (1) T 1;A,
Exes II s (( tex fee (YT(R); A,
I e A v
(2)
ExeeIIk exp( A Y /8)
where is the set of all one-to-one maps from [L....,m} {L..... n2,, i.c., permutations. We notice that (2) does not involve unknown components s(-) and fay due to the separable assumption (Assumption 2.1), and does not depend on the base measure h--) and the log-partition function G(-). However, (2) is computationally infeasible due to the summation over all permutations. The proposed pairwise pseudo-likelihood likelihood consider local ranks for pairs of observations. For any k and k', let R
denote the local rank statistic of Y2 and Yv among the pair (Ýx, Yv.) We denote Y (R.K*) as the local order statistics (min Yr, Yvr J, max(Ye, Ye, Yx.)). Instead of the full conditional probability (2), we consider the product of all possible combinations of the local rank conditional probability on observations:
II Pr(R The X (K.))) Ih Tw 1; の) kek
AeYa Ae
exp
A A 1
A AcYp+Ai
kek 1 + exp(- (Yr Vx - )/)/
Rcck exp
+ exp
Similar to (2), this pairwise peeudo-likelihood (3) (of A and Φ) does not contain unknown functions and quantities. However, unlike (2), it does not involve all permutations and is therefore significantly easier to compute.
The negative logarithm of the pairwise pseudo-likelihood reads
Σ
log(1 + PAw (b)AA))
ISACk'RR
where REE (o-1)) = exp(-(f, estimating A, (and (i.) via minimizing (4).
(0-10- - - - We notice two immediate issues with
Scale Equivalence: The values of (4) evaluated at any two pairs (A1, Φ1) and (Az, d2y) are the same '
when of A₁ o5 Ag. Therefore, (4) does not have the ability to distinguish between these pairs.

---

In other words, if Φ. > is unknown, (4) would not be able to identify elements in the equivalence class of A, under equivalence relation: A c, for any ci 0. Instead, we try estimate the dispersion-scaled matrix Φ, A, Therefore, we consider
((A) Σ log(1 + RaK (A)).
1skck'sn
However, this does not solve all the identifiability issues, and, indeed, cannot identify shift- equivalence class described below.
Shift Equivalence: Let J be matrix with all entries being one. Consider A + 62J for any E IR. Then
((A + (2J) = REE ((A + c2J)) = exp(-(22 (A, + +2 - Av - cc)) e V A = ((A).
Combining the scale and shift equivalence, we only estimate A, up to equivalence relation A ~ C1A + C2J for any C1 > 0 and C2 E R, which we will refer to as scale-shift equivalence. We remark that the scale-shift equivalence still allows the identification of much useful information from A., such as ranking an arbitrary set of entries of A. For example, in recommender system applications, one is mostly interested in the ranking within each row/column. Among the elements in the scale-shift equivalence class, we choose to estimate the following representer
A. - A, (J, 6 A,
(J, 6, A.)
J.
(J.J)
M1
by imposing the constraint (J, A) = 0 in the optimization. Here (A, B) = En, Aig Big for any matrices A, B E Rm X
Overall, propose the following penalized pairwise pseudo-likelihood estimator
À argmin
((A) A ||
(J.A)=0.JAll
where ||A and |A max,, Ag) represent the nuclear norm and the entrywise max norm of matrix A respectively, and a, À 2 0 are tuning parameters. We also use ||A]| denote the Frobenius norm a matrix A. Nuclear norm regularization has been commonly used to promote low-rankness in the estimation [25, 24, 14). Since É is convex, this optimization convex. The discussion of the optimization algorithm given in Appendix C. One natural question is whether there would be further hidden identifiability issues beyond scale-shift equivalence. In Section we will provide a finite-sample error bound of the proposed estimator (6) based on the pairwise pseudo- likelhood,, which indicates convergence to A., eliminating the possibility of additional identifiability issues.
Identifiability based on separable assumption
One of the major difficulties associated with informative missing is non-identifiability. We first emphasize the ainiieetiffiabiiityy for constant shift not an artifact the pseudo-likelihon approach. The root cause is the informative missingness (Assumption 2.1). Here is simple univariate example inspired from [27] to illustrate this point. Suppose we observe from two data-generating models, whose observations are identical in distributions.
Model I: ()-1,1) with observation probability Pr(Ti 1|Y; y)
exp(y) I+exp(y)) then
Pr( = 1, = pw(y 1) exp(y)
exp(y)'
where (.v(-) is the p.d.f. of standard normal distribution.
Model H: Y2 NO0 1) with observation probability Pr(T2 1|12 y) eexp(-1/1)
expí ()(--) I +exp(--))
then
Pr(T, 1, = y) pN(Y 1) - exp(y + 11 exp(-r)
exp(-y)
=v 1) exp(y) Pr 1,Y =)) exp(y)
5

---

Extending to the matrix form, the observation probabilities of the following two models, where Y1, 22 E I xm3 are exactly the same. Model I: vee(Y,) ( t1,5 1 for any
(i,j) and (1) = exp(y) Model II: vec(Y2) ~ (NO, I), f2,53 = 1 for any (i.5) and s2(v) 1+exp(y)'
exp(-v) exp( exp(-1/2) exp(-11/21+eppt-->> 1exp((-))
As such, under Assumption 2.1, we cannot identify the constant shift. We note that, low-rank assumption generally would not provide enough additional information to eliminate this identifiability issue, as constant shift corresponds to at most rank-1 perturbation.
The identification of the dispersion parameter is a difficult task because of the fact that at most one observation is available for each entry. Interestingly, we have shown in the Appendix (Theorem B.2), under Assumption 2.1, the identification of the dispersion parameter is actually feasible in Gaussian distributions with replicates. However, it ís unclear whether the dispersion parameter can be identified in a typical matrix complction setup, which often does not allow replicates. That said, previous works exponential family matrix completion [21, 13] assume the dispersion parameter is known, under which there would not be a related identifiability issue.
5 Theoretical guarantee
Recall that A, E R=ixm=, We denote some convenient notation for dimensions, i.e., m min(m, m2), M max(mi, (greater) than up to an absolute multiplicative constant. We write a = if a S b and b Z a. Further- more, define πL min.g[mi],j[mm) Pr(Ti,- = 1) and गe = (m.XxeEmm..JEmmmm Pr(Ti; 1). We use [n] to represent (1...., n for integer n. In this section, we derive the convergence of I| - A.lle. Recall that A,, defined in (5), is the representer in the equivalence class of A..
mi + m2g We use the notation S (2) to denote less
Assumption 5.1. The following conditions hold.
(C1) There exists an absolute constant p >> 0 such that TT /TL S p.
(C2) There exists a constant B such that ||| 00 I B almost surely.
(C3) There exists some constant 0 (where x can depend on |.A.1lo)) such that B B(Zz,ey) 2 for any i, [mi]] j.j' E [m2]] where
exp((Y,) - I+ exp((Y) (ui) - A)
Eizzy = (Yi - Yuy) x
Condition (C1) is posited to avoid some specific entries being sampled with very low probability in relative sense, where the trace-norm penalization fails to work [1 31]. Note that both my and T allowed to diminish to zero m1, M2 oo, but Condition (C1) implies that their diminishing orders are the same. Condition (C2) is a technical assumption for analyzing the concentration inequalities of the involved U-statistics in pairwise pseudolikelihood. Note that this does not violate the parametric assumption on the distribution of Y. For example, truncated normal distribution satisfies both. We leave the extension a light-tail type of assumption for future work. Condition (C3) is a technical condition, and is used in deriving the (expected) Hessian of the loss function with respect A (see (8) in Appendix A). Note that (expected) Hessian of the loss is often important for deriving the convergence rate and so it is reasonable that a related term shows up in our condition. Indeed, this assumption Here, we provide further discussion to show that it indeed a mild condition. Intuitively, it posits a positive lower bound for an expectation of a squared random variable. This expectation is always non- non-negative and zero only when Z,j,''' is exactly zero almost everywhere. For noisy matrix completion settings, this assumption is very mild because, when there are noises, this variable is not exactly zero almost surely. Next, we show that with the exponential family model, we can explicitly characterize k. First note that when
< a as assumed in Theorem 5.3 and || S B as in Condition (C2), we have EZ2 3 2 exp(da
|
(e) IE (Y2 + Y YY.r 2 )}. Recall the density of Yo, (1), one can derive Var(Y,))
exp(4aB) [exxp(aaB]]= (Var(Y.)) + Var(Yez)) GH (A,, )o, where G"(.) nonnegative, from the well-known variance formula for exponential family. Therefore one can take x = min:,j exp(4a11)
[[+exp[aaB]]+ (((.G(AA.))))

---

Lemma 5.2. We have E E(VE(A.)) = O, where E(-) is the expectation under the true parameter A..
Theorem 5.3. Assume rank((.) I r and || S a for some positive constants r, > O, under Assumptiins 2.1 and 5.1, if we further assume may 2 llog(d)) ) and X x
Ba log(d) [mim2Ty / M then with probability al least 1 - 6/d, the following holds:
A - A. A.l P
B B"logd 2 R²
Mr
B² log(d)
S max
pV m1
m2
my L
K
Our result implies that the penalized pairwise pseudolikelihood approach can consistently estimate A.. Note that the difference between rank and rank at most 1. So a low-rank assumption on A, automatically translates to low-rank assumption on A.. Most existing work present the upper bound concerning the number of observed entries n and treat the matrix completion as trace regression problem [e.g. 28, 18, 5, 25]. One can take n. as 77, in their bound to compare their results with ours. Similar to the bound established in [18], our bound has two components and matches with the rates in their upper bound (up to some constants and logarithmic factor). [17] and [28] show a bound that has the same order as the first term (up to some constants and logarithmic factor) with some additional assumptions. [17] adopts the uniform sampling and boundedness of the condition number for ||A. ||. [28] assumes that the sampling distribution follows a product distribution and the "spikiness ratio" (see aspp in [28] is bounded. Besides the above matrix completion methods that use the nuclear norm regularization, the estimators utilizing the max- max-norm regularization [e.g. 5, 35] establish the same bound as the second term(up to constants and logarithmic factor) when they assume the max-norm of A, is bounded. While the aforementioned methods address various missing mechanisms, it is important emphasize that none of them can handle MNAR setting, where the missingness may depend on the observations. However, our method can tackle such informative missingness. It is interesting to see that our error bound resembles the same convergence rate as [18] (minimax optimal rate) up to a logarithmic order, despite that our setup allows MNAR mechanism.
In terms of theoretical analysis, the most notable distinction between estimator with other existing ones lies in the objective function. The pairwise pscudo-likelihood we employ imposes unique theoretical challenges. Firstly, the gradient and Hessian are longer straightforward as those in the commonly used squared loss or negative log- likeelooloood loss (for exponential family). We carefully derive these two terms, expressing them as pairwise summations (see exact forms in Eq. (8) and Eq. (9)). Secondly, the elements in these pairwise summations are not mutually independent, posing difficulties in establishing the concentration inequality to bound them. Indeed, we need to develop corresponding theoretical tools for tackling the corresponding matrix concentration of a matrix-valued U-statistics. To address this challenge, we leverage the grouping lemma (Lemma A.5) to decouple these summations into different groups where mutual independence holds within each group. To obtain the efficient grouping, the decoupling is applied Additionally, while the trace regression model provides convenient tool for analyzing the sampling distribution, it implicitly assumes "sampling with replacement", i.e., every entry can be observed repeatedly. We adopt the framework of the Bernoulli model for the observation indicator to avoid the issue. However, theoretical analysis become more challenging. A conditional argument (see the conditional event & in (10)) is developed to address the discrepancy between these two frameworks. In addition, Lemma A.6 established to marginalize the conditional event.
those observed entries.
Finally, we remark that, while pseudo-likelihood approaches have been applied in regression analy- sis [32] and variable selection [37] deal with informative missingness, such analyses mainly focus on i.i.d. design and usually make direct restricted eigenvalue condition of the hhigh-dmmensional) Hessian matrix. In our problem, the eigenvalue condition related to the observation probabilities. As in typical analysis of matrix completion, one is interested in the dependence on these probabilities, as they are allowed to diminish as m1, my > oc. As such, we also analyze the corresponding restricted eigenvalue bound, under the complicated grouping nature and identifiability issue. By adapting the techniques aforementioned, we provide rigorous convergence result non-i.i.d. design, which involves analyzing the concentration of a matrix-values U-statistics (i.e., the Hessian matrix). This analysis distinguishes our work from a mere application of standard likudo-lieelhhod theory, and the techniques used in the proof contribute to the field on their merit.
7

---

6 Numerical experiments
We conduct the following simulation study demonstrate the efficacy of the proposed method. We generate a 50 x 50 matrix A, with rank = 5. The observations Yú, are generated from a Gaussian distribution with mean A,,sy and variance o² independently. In our study, we have settings with different variances o². The probability of each entry being observed is related to the value of the entry itself: P(T. 1|Mry) 1/[1 + exp(3X,)]] Since the observation probability is smaller for larger Yj, there exists a distinctive distributional shift between the observed and unobserved entries, as shown in Figure
Observed (Unobserved entries
TRMSE for different variances
unoiserved
125
observed
100
Count
VFW
11 7
-6
-4
-2
0.0
0.2
0.1
0.6
0.3
1.0
Figure 1: Observation bias with variance o² 1. Figure 2: TRMSE with standard error for differ-
ent variances o² 0.0, 0.2, 0.4, 0.6, 0.8, 1.0.
We use the observed entries as training data and equally split the unobserved data as validation and test data. We compare our method with SoftImpute [26]. CZ [5], MFW [35] and SNN [2]. The validation data is used for hyper-parameter tuning in each method. Since the objective function is convex the proposed method, we only tune the regularization parameter X, and fix the number of iterations as 7 = 100 and step size 7) 1.0 in Algorithm 1. We use the output of SoftImpute [26] with the same regularization parameter as a warm-up initialization to shorten the training time. For SoftImpute [26]. CZ [5] and MFW [35]. we tune the hyper-parameters involved in the optimization and regularization as suggested. As for SNN [2], we choose uniform weights and spectral threshold suggested in [12], and choose the number of neighbors between and 2. Due to the identifiability issue, the validation data also used to learn a shift and scale parameter (via a simple linear regression) for the proposed method, which is then used in reporting error metrics on test data.
True entries
Soft Impute
Max Norm
150
1000-
Count
Count
100
400-
300-
30
01
Model Free Weighting
Synthetic NN
Pseudolikelhhodd
200
200
200-
150
150
Count
Count
100
100-
50
0
Figure The recovered entries by existing methods are left skewed with σ2
Before getting into the error metric, simple check on the bias of each method is via histograms. We pick one run with o² = and plot the distribution of recovered entries without any transformation for each method, as shown in Figure 3. It shows that only the proposed method is able to mitigate
8

---

Table Computational time comparison with o² =
Methods
Time (s)
Soft Impute
0.01 0.005
Max Norm (CZ)
0.22 = 0.09
Model Free Weighting (MFW)
1.90 0.75
Synthetic NN (SNN)
15.23 + 1.39
Pseudolikelihood
8.67 1.23
the observational bias due to the underlying informative missing structure, and exhibits symmetric distribution, while the distributions generated by other methods are left-skewed, due to the left- skewness of distribution of the observed entries.
We added comparisons of the computational time regarding the setting in Figure 2 (o² 1). The computational times are listed in Table 1. While incorporating more complex missing mechanisms, our method and SNN also take the most time. One practical way to speed up the computation of our method is to use stochastic version of Algorithm (i.c., training in batches). The focus of this paper is more on the robust recovery when encountering informative missing, and less on the computational efficiency with the knowledge that it could be theoretically slower than other SVD-based methods. However, our method is still faster than SNN, where both methods consider more complex missing mechanisms. Given the promising statistical properties of the proposed method, future direction is to develop scalable algorithms for the proposed estimator or its variants.
To further validate the effectiveness of the proposed method, we vary the variances o² in the simulation. This setting is designed to differentiate non-uniform missingness and informative missingness. When the variance is small, the informative missingness is less severe. and non-uniform missingness might be used to approximately describe the missing mechanism. When the variance is large, the observational probability is more affected by the outcome in typical informative missingness setting. We choose the variances d² = 0.0, 0.2, 0.4, 0.6, 0.8, 1.0. For each setting, repeat the simulation 9 times and report the average test root mean squared errors (TRMSE) with standard errors, shown in Figure 2. We see that as the variance gets larger, there is a larger improvement in the proposed method with the design account for informative missing over other methods. SNN [2] performs the worst when the variance is large, as it mainly borrows information on observed entries which introduces substantial bias. It demonstrates the robustness of the proposed method in difficult settings where the missing structure is informative.
7 Real data application
In this section, we use three data examples illustrate the robust performance of the proposed method. These are the Tobacco Dataset [9], Coat Shopping Dataset [30] and Yahoo! Webscope Dataset'. These datasets have been used prior works for the demonstration of matrix completion methods [e.g., 2, 35]. Due to space limitation, we refer the readers to Appendix C.2 for more detailed discussions of the datasets and our analyses. Following the details of the implementation Section 6, we report the results in Table 2. For the Coat Shopping Dataset and Yahoo! Webscope Dataset, evaluations are based on associated test sets from the original data sources. As for the Tobacco Dataset, following
[2], the missing data are randomly generated 100 times according to cigarette sales. Here is a summary of the results.
Tabacco Dataset. As we can see from Table 2, our method only performs worse than SNN for this MNAR dataset, with significantly smaller TRMSE than the other three methods. Note that this synthetic missing data, the way to generate missingness is adapted from the SNN paper. When one entry is missed in Tobacco dataset, the entries in the following period are also missed. This does not satisfy the assumption of our work. So it is not surprising to see our method perform sub-optimality. However, the performance of our method still remains strong.
'https://xebscop: san.ccoppp..ddoo....o.oo.ooooo.. yahoo, cww catalog. pap"

---

Table Test root mean squared errors (TRMSE) for Tabacoo Dataset, Coat Shopping Dataset, and Yahoo! Webscope Dataset. For Tabacoo Dataset, the average of TRMSE with standard errors (SE) in parentheses under 100 random missing data generations are presented.
Method
Tabacco Dataset
Coat Shopping Dataset
Yahoo! Webscope Dataset (subset)
SoftImpute
19.20 (0.28)
1.41
1.84
CZ.
20.45 (0.51)
1.19
1.58
MFW SNN Pscudolikelihood
15.89 (0.24)
1.07
1.28
12.09 (0.16)
2,06
1.27
14.14 (0.36)
1.20
1.12
Coat Shopping Dataset. As Table 2 shows, SNN performs much worse than the remaining methods for this dataset. MFW has the smallest TRMSE. Our method has smaller errors than SoftImpute and has comparable performance to CZ.
Yahoo! Webscope Dataset.
Due its large size and simplify the computation, we conducted selection procedure to reduce the size of the matrix. Please see details in Appendix C.2 about how obtain the subset of the matrix. From Table 2, we can see that the two methods (SNN and our method) that are designed for MNAR have better performance than the remaining methods, and our method has the smallest TRMSE.
Overall, our method performs robustly well across all these three datasets. In our comparison, a few alternatives perform very well in example, but badly in another. For example, SNN has an excellent performance in the Tobacco Dataset while performing very poorly in the Coat Shopping Dataset. The robust performance of our method appealing in practice, the missing mechanism is often unknown.
Conclusion
In this paper, we tackle the matrix completion problem where missingness could depend on the possibly unobserved measurements, constituting a challenging missing-not not-at-random setting. The proposed method is developed under flexible separable missingness assumption, which allows us to develop a pairwise pseudo likellhod approach. Corresponding identification investigated. We also provide a non-trivial convergence analysis, well some numerical experiments to illustrate the efficacy of the proposed estimation. Due to the flexibility in both the missing structure (separable missingness) and measurement model (exponential family model), the proposed technique would be useful a wide range of applications.
The grouping nature of the proposed method poses an additional burden in computation, particularly when dealing with a large number of observed entries. For future works, we consider adapting the stochastic grouping idea to reduce the computational cost and exploring its application in large-scale recommender systems.
Acknowledgements
The authors thank the reviewers for their helpful comments and suggestions. Portions of this research were conducted with the advanced computing resources provided by Texas A&M High Performance Research Computing. The work of Jiayi Wang partly supported by the National Science Foundation (DMS 2401224...7.). The work of Raymond K. W. Wong is partly supported by the National Science Foundation (DMS-1711952 and CCF-1934904) The work of K. C. G. Chan is partly supported by the National Science Foundation (DMS-1711952).
References
[1] Abadie, A., A. Diamond, and J. Hainmueller (2010). Synthetic control methods for comparative case studies: Estimating the effect of california's tobacco control program. Journal of the American statistical Association 10504 493-505.
10

---

[2] Agarwal, A.. M. Dahleh, D. Shah, and D. Shen (2023, 12-15 Jul). Causal matrix completion. G. Neu and L. Rosasco (Eds.). Proceedings of Thirty Sixth Conference on Learning Theory. Volume 195 of Proceedings of Machine Learning Research, pp. 3821-3826. PMLR.
[3] Bühlmann, P. and S. Van De Geer (2011). Statistics for high-dimensional data: methods, theory and applications. Springer Science Business Media.
[4] Cai, T. and W.-X. Zhou (2013). A max-norm constrained minimization approach to 1-bit matrix completion. J. Mach. Learn. Res. 14(1), 3619-3647.
[5] Cai, T. and W.-X. Zhou (2016). Matrix completion via max-norm constrained optimization. Electronic Journal of Statistics 10(1), 1493-1525.
[6] Candes, E. J. and Y. Plan (2010). Matrix completion with noise. Proceedings of the IEEE 98(6), 925-936.
[7] Candès, E. J. and B. Recht (2009). Exact matrix completion via convex optimization. Foundations of Computtational mathematics 9(6), 717-772.
[8] Cao, Y. and Y. Xie (2015). Poisson matrix recovery and completion. IEEE Transactions on Signal Processing 64(6), 1609-1620.
[9] Council, T. T. and T. I. (Washington (1997). The Tax Burden on Tobacco, Volume 32. Tobacco Institute.
[10] Davenport, M. A., Y. Plan, E. Van Den Berg, and M. Wootters (2014). 1-bit matrix completion. Information and Inference: A Journal of the IMA 3(3), 189-223.
[11] Foygel, R., O. Shamir, N. Srebro, and R. R. Salakhutdinov (2011). Learning with the weighted trace-norm under arbitrary sampling distributions. Advances in neural information processing systems 24, 2133-2141.
[12] Gavish, M. and D. L. Donoho (2014). The optimal hard threshold for singular values is 4/ 33. IEEE Transactions on Information Theory 60(8), 5040-5054
[13] Gunasekar, S., P. Ravikumar, and J. Ghosh (2014). Exponential family matrix completion under structural constraints. In International Conference on Machine Learning, pp. 1917-1925. PMLR.
[14] Hu, Z., Nie. R. Wang, and X. Li (2021). Low rank regularization: A review. Neural Networks 136, 218-232.
[15] Jin, H., Y. Ma, and F. Jiang (2022). Matrix completion with covariate information and informa- tive missingness. Journal of Machine Learning Research 23(180), 1-62.
[16] Kalbfleisch, J. D. (1978). Likelihood methods and nonparametric tests. Journal of the American Statistical Association 73(361), 167-170.
[17] Keshavan, R. H. A. Montanari, and S. Oh (2010). Matrix completion from few entries. IEEE transactions on information theory 56(6), 2980-2998.
[18] Klopp. O. (2014). Noisy low-rank matrix completion with general sampling distribution. Bermoulli 20(1), 282-303.
[19] Klopp, O., K. Lounici, and A. B. Tsybakov (2017). Robust matrix completion. Probability Theory and Related Fields 169, 523-564.
[20] Koltchinskii, V., K. Lounici, and A. B. Tsybakov (2011). Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion. The Annals of Statistics 39(5), 2302-2329.
[21] Lafond, (2015). Low rank matrix completion with exponential family noise. Conference on Learning Theory, pp. 1224-1243. PMLR.
[22] Liang, K.-Y. and J. Qin (2000). Regression analysis under non-standard situations: a pair- wise pseudolikelihood approach. Journal of the Royal Statistical Society: Series (Statistical Methodology) 62(4), 773-786.

---

[23] Ma, W. and G. H. Chen (2019). Missing not at random in matrix completion: The effectiveness of estimating missingness probabilities under a low nuclear norm assumption. Advances in neural information processing systems 32, 14871-14880
[24] Mao, X., S. X. Chen, and R. K. W. Wong (2019). Matrix completion with covariate information. Journal of the American Statistical Association 114(525), 198-210.
[25] Mao, X., R. K. Wong, and S. X. Chen (2021). Matrix completion under low-rank missing mechanism. Statistica Sinica 3 (4), 2005-2030.
[26] Mazumder, R., T. Hastie, and R. Tibshirani (2010). Spectral regularization algorithms for learning large incomplete matrices, The Journal of Machine Learning Research 11, 2287-2322.
[27] Miao, W., P. Ding, and Z. Geng (2016). Identifiability of normal and normal mixture models with nonignorable missing data. Journal of the American Statistical Association / ///6)))), 1673-1683.
[28] Negahban, S. and M. Wainwright (2012). Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. The Journal of Machine Learning Research 13(1), 1665-1697.
[29] Ning, Y., T. Zhao, and H. Liu (2017). A likelihood ratio framework for high-dimensional semiparametric regression. The Annals of Statistics 45(6). 2299-2327.
[30] Schnabel, T., Swaminathan, Singh, N. Chandak, and T. Joachims (2016). Recommenda- tions as treatments: Debiasing learning and evaluation. In international conference on machine learning, pp. 1670-1679. PMLR.
[31] Srebro, and R. R. Salakhutdinov (2010). Collaborative filtering in a non-uniform world: Learning with the weighted trace norm. Advances in neural information processing systems 23, 2056-2064.
[32] Tang, G., R. J. Little, and E. Raghunathan (2003). Analysis of multivariate missing data with nonignorable nonresponse. Biometrika 90(4), 747-764.
[33] Tang, N. and Y. Ju (2018). Statistical inference for nonignorable missing-data problems: selective review. Statistical Theory and Related Fields 2(2), 105-133.
[34] Tropp, J. A. (2012). User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics 12, 389 434.
[35] Wang, J., R. K. W. Wong, X. Mao, and K. C. G. Chan (2021). Matrix completion with model-free weighting. In International Conference Machine Learning, pp. 10927-10936. PMLR.
[36] Wang. J., R. K. W. Wong, and X. Zhang (2022). Low-rank covariance function estimation for multidimensional functional data. Journal of the American Statistical Association / 1/7(588), 809-822.
[37] Zhao, J., Y. Yang, and Y. Ning (2018). Penalized pairwise pseudo likelihood for variable selection with nonignorable missing data. Statistica Sinica 28(4). 2125-2148.
12

---

A Proof of Theorem 5.3
We provide the proof of our theoretical results and discussion about identifiability and pscudo- likelihood approach below. The proof follows the roadmap from [18] to construct the convergence, whereas the details differ because we deal with matrix-valued U U-statistic type estimator. We mainly rely on Lemma S. 3.4. from [36] to decouple the dependence in U-statistic structure. See Lemma A.5 in Section A.4.
We start by rewriting the pairwise pseudo-likelihodd as
((A)
E
to ( AM
1skck'sn
Σ
TyTTy (VVeeg Yowe
S 154. mma Smz
where YAr Yx Yv Yi Yo Yyney, and ((f) log(1 + exp(t)). Simply.
we obtain that (t) = exp(t)/(1 exp(t)). (1) = exp(t)/((1 + exp(t))²} and vt exp(
Therefore, the first and second order derivatives of ((A)
V((A)=
Σ
Ti x {( (Yyvy - 1) Boyerr
(8)
and (²((A)
Σ
Toy (Yiye Aiye vec voc )02)
ISi Sid'sm
where Enjry- E,j Eyyr, Eiy E m xm2 is the canonical basis with value 1 the (i, j-th entry and elsewhere, vec(X) is the standard vectorization of matrix X and y = vv for v E R m0
A.1
Lemmas about gradient
Note that
Re (A.)
(((A.)=-
Σ
(Yn Vrx) Eeg.)
+ Rise (A.)
1skcksn
(A.)
Σ
(Vig - -Fr Drg
1+ Rigay (A.)
(1 J'mlm [x(ma]
((.))
1
Σ
1 Raj,y (A.) (Yij - Yoy. - TT
Rig.er (A+)
Tiy Try.
2
(1.f) xmmmma
where (i,j) < (i'j'))
means (i.j) appears before (i',j") with the same ordering rule within E, e.g..
dictionary order.
Proof of Lemma 5.2. Note that
Rag. (A.)
B(VE(A.)) =
Σ
(Yig -Ye))(E E
+ Rig (A.)
Jem ((d)<(('
Σ
Rejay (Ax)
(Ves Vey) Ery) Túi Top =1
-
E
I Reg,y (A.)
(15).66' J je))(mms]xxxm [mm]] (1.5)=(E'
13

---

The proof of R. (A.)) 14 ( (Yig (ey))E., Egy) Tij Tay = 1] directly follows
Theorem 4.1 from [29].
To simplify the notation, we denote
Rig (A.) (Yis Yyr))EE; Evy TijjeT
Sigry + Rig.eg (A+) (A.)
Recall that m min m2),e d = my + m2, M = max m2). Ykl < B almost surely. Lemma A.1. With the condition that may Z log(d?). We have
Pr { (E ~ V (og(d) mmm2Tu v MTU } S
3
Denote
Rig. (A.)
Ciy = 1 Rag.y (A.)
(Vis - Pez)).
First of all, we can verify that
E(Cg,eyTTyTey (E
[Ts = 1, 1,T = 1]} O.
Define the event
E 1 Tr = with sampling matrices X X
(10)
where X En for some index (in.)s)) h == =,.,.., n. Without loss of generality, we consider the case when is even. Therefore, by Lemma A.5, we have the following decomposition.
n-1
VE(A) 8 Σ
Σ
CR, - X
9-1 (KAA)),
where CR.K' = Cinsindy Juc Within every group Gg. there is no repeated index. Therefore, every element the group Gg independent of other elements in Gg conditioned on E.
E(CK, () = 0,
Vk, -.,..., n.
Next, we use Matrix Bernstein's inequality to bound || ((,,)e IX - Xw1ll conditioned on the event E.
Take Sk.K/ Ck
X and we have
E
Σ
S ST. |
(K.R))
E[ Σ
C2 KX, - XxIIx, 1
< B²
Σ
X - X
(K.
))
< 2
Σ X X X
Σ Xx
Xx X3 Xxxxx]]
(KL
(K.K
Take is and jı as the corresponding row index and column index for Xa such that Xx Eigdin
Σ
X + X
Σ
E
=1
(K,
14

---

The last inequality is due to the fact that the diagonal matrices have the operator norm 1.
Σ X
X & Σ
+ X x
Σ
21 - j.
(K.AEE,
(K,K))G,
(K,
Then
E Σ
SK R.k 1
S B² 1+
Σ (K:R))G,
21 2 jmc}
(R.K))GG
Similarly,
E
Σ
S 1
S B²
1+ Σ
21c = im}
(K,
(k,k')EG,
Take
Sn.g max Σ
21 = ji
Σ
21 = it
(11)
(K.
(K:
Then by Theorem 6.1 from [34], we have
Pr
Σ
SE.
2 c (2 + En.g) + log(m1m2)) E
(K,K))E9
<dexpf -12 (2lo(m1122) + +2 2log(d)) = ((m
(m1m²)22 2d
for some constant e > O.
Note that ||VE(A))] | 3 < En groups, obtain
EiK,ney Skx
By applying the union bound over all the
g=
R-1 2 2c 2
Pr VE(AA))
(2 (2oloog())))) + 2 log(m m2)l 8 {]
(m1mg)2d
(mjm2)d
1=
Marginalize the event & and we have
Pr
(((A.))
B² + En.g) (olg(( + 2 logg(mm log(m1m22) 5 (mima)dd
9=1
Note that
B² + (2)g(()) + 2 log(mimz)
n
v B2 log(d) + log(m)m2))
B2 (2 log(d) log(m)ma))
< (n- 1) B log(d) 2lggmmmm)) + B²(2log(d) + 2 blog(mm
Σ Sm.a)
G
I nv B log(d) 2ogogmm (m) + Vrn
B² (2(2lgg(d) + log(m1 (mmmmmmm)
Σ Eng))
15

---

Therefore, we have
Pr [[((A.)] TI [2 12 log(d) log(m)ma) + Vn, 22 log(d) + log (ogmmmmm mmmmmmm)
{n.g)
(m1m2)d
By Lemma A.6, we adopt the bound for and Mg=1 En. and further obtain that
Pr
|| /B
log(d) 22 2 mm))
3mimgat + /3mmm2 / 2m m2M
$
exp(-m1m2TT) + 2M mxp(-m
(m m2 d
Pr<1]Ve(A,)]] 2 v Bd (log(d) + log(m1
miman Maao
(m) exp(-m1122m) 2M exp(-mmaat
With the condition that may log(d') We have
Pr [((AA))] 2 / 12 log(d) + mm) mimmnt / M
}
3 d'
The conclusion follows by assimilating universal constants in 2.
A.2 Lemmas about Hessian
0(1) =xp((=(xx(xxx(((()))) *0(1) ((p(()/(((+exp(()))) Recall that v+() (x0p0)0000=0())))+x(x))))))))))) It simple to verify [v((()) 1, (() S 0.25 and vi" (1) exp(()((
and 115" (t) < 0.1.
The Hessian matrix reads
V(((A)=
Σ WYYowwy
vec (i)(ei))))))) 02
1skck's
(Yn -Yx)² exp - (A - An))
Σ In
(1 exp((X) - Yx. - Axr)))² vec Ex - )
1
exp((Y,) (Arr Avy.))
TofTey (Yig )2p))
(1 +1+expo ex+eep((Ys) - Yerr)((s - Av ))}² vec(Ei) E 62
2
(f.) d )E (e(mi]x (ma)
1
Σ
TiyTey 22g, vec(Eis -Eryy )02
2
(6 J')(mm))xmm
where
exp((Y)g - (Ag) 1+ exp((V,) Yep [Ais Avy))
Zizzz (Yiz - Yeg)
Lemma A.2. For any U E mmx such that (J, U) 0, and assume that B(Z 0,3 K, (i..)), e [mi] x [ma] when || I for some constant a > O, we have that
>
Evec(U) V'((A)vec(U) kmimani |
16

---

Proof. We derive the quadratic form first and take the expectation to obtain that
Eu (AA)u-(
Σ
E (Us) U2z) )3
Σ
B(TiJToy:(U; - Uvg )2}
2
2 L
Σ
(Ug--U:)) - U.y.))
2 kTL
Σ
U3 + U23 UU,
(6J) (')
m2 ||
We now start to lower bound u <2E(A)u. We consider the following constraint set
U xm2 (J,U) (J,
Still, we derive the argument by conditioning on the event & defined in (10).
vee())) (U)
Σ
Zusiseee (Uinin U Usgin
K, I.....
where (kk) is the entry where Eigci
By Lemma A.5, WLOG, we assume n is even. We decompose the summation into
Σ
Σ
Besreserr (Uesh D
g=1 (H,
where within every group Gg. there is no repeated index. Denote
Eg
Σ
kk Zu.eeeeeee (Xx Xxr).
(KA,
where Sk. are independent Radamacher variables. For convenience, denote vec(U) Rmima for any m X
Lemma A.3. For all U C. the following holds
( Eu" (2((AAu] 2 B² Immmmoe/Me MTu +B² with probability at least 1 3/d.
Proof. Denote
C UU EC: |U] ST). Iu (aA(A -u Eu
WT sup UEC(T)
Let Vmay/TL /T. By Lemma A.4, we have with probability at least 1/d,
u v Eu T ((((A) 2 8 (m ) (m
Next, we focus on the case when U 2 We will show that the probability of the following bad event is small
= {EU E such that |uT})((A)u Eu (2E(A)u) Z BB||U Vlog(d)) [mmmztT MTg |U]| 2 v).
17

---

We use a standard peeling argument. For 1 E N set
S = {U e C(r) C(r):avv |U]| d'ttv}.
For each T > v, define the following event
B EU St such that Iu (() Eu ( 2 B²I|U1I log(d) mimzat v MTy
-I log(d }. we have that
By lemma A.4, with probability smaller than (m, exp
may
Wr > B²T V log(d)
mim22u V MAU
Therefore, obtain that
Pr(Bi) S (m exp {
(a²" log(d")
mTv
Using the union bound, we have
0(aa" log(d
Pr(B)= <
Pr(Bi) D
(m1m2) exp
+ +1/d
may
1=1
-(uP)TL log( (dd))1 1/d
mm m22) exp
mRTU
[(o))T log (d (dd))) l0g(a) 1/d
(mim7)) exp
< (m1m2) (2f-22og(a) log(d")) 1/d < 2/d.
Combine two cases, and the conclusion follows.
We now make up the concentration property on WT.
Lemma A.4. Conditioned on event E, For any T > v, we denote
C(T) = (U |U11 ST} and WT = sup
UEC(T)
When T S VITV / Ti, we have
P
P(r 2 B²
S 1/d.
When T 2 //mu//T. By laking
Toglog dy we have mimany
-T n
P P(Wr 2 BTT log(d) mmmmmu MMuu)) S (m1m2) exp
log(d))
miu
Proof. Still, without generality, we focus the case when is even. Recall that conditioned on event E, we have
Wr = sup UEC(n.)
u VT Eu V((())u
Σ
72 Aaseeiii (Uiese Unrry 12 R. Σ
Σ
22 Priieiii (Uraja UUeriv
sup Uec(r:T)
g (k,
(K.K")EG,
Σ (k.,')EG,
Prgjedsiv (Ureje Uneesee 2- E Σ
(U )
sup g UeC(r,T)
18

---

and
2g.T
sup UEC(r.3))
Σ
Dusiniiee (Usnda Uigiee )2= E Σ
D Dusiesibr (Uinda Usee (R,R))GG,
Note that conditioned on the event &, within each grouping Gg- every term 2 Z Jecie (Uiuia Us is independent of the others. The standard symmetrization trick still applies here,
EZgTT | S 2E sup UEC(T)
Σ (R.,
EKIK Zieje Seriw (Usese - Usarsw)2
Since [Zigiol - 2B and || = 1, 72 in (Uigja Uigio) S 16B² for every (k, k).. Therefore, d(u) = u², lo(u) d(v)] s uu + 1 |l vl S 8B/uu v). The contraction inequality yields
EZg.T E S 2E sup UEC(T)
Σ (H.
Ek, Z Tuiiniii (Uiiia Dew
16BE sup UEC(T)
Σ (NEG
Eke Zindniiris (Uinón Unuise)
16BE
sup UEC(T)
Σ (ke
Ek Zisieiee X 1 1
16BE
sup UeC(T)
Σ (K.A))EG
Sh,k' Trnsengrii (Xs xxx); U
E
S 16BE
Σ
Ekik Zis (Xs - Xxr) 31
sup UEC(T)
|U||
S 16BTE (1 ||واl |E).
Take (U) = Z2 Zugia Aniin (Unie - U1 EZ, Swrd (Uaui ) Note that
Diriniwie (Useie UNNio )21 11BB
Then
E (U) sup sup Nr (U))(33))) S
(k.k') (EC(T)
By Massart's concentration inequality (e.g., Theorem 14.2 [3]). We have that conditioning on event E, for any t > O.
Pr
sup UEC(T) 1/2 exp(-(nn/2))
Σ
Bakk (U)/(32B²)
> E
sup UEC(T) n/2 (K,A")EG,
Σ
nae (U)/(3BB2)
+t
(K,K")
Pr
sup UEC(T) n2/ (k,
Σ
na.k (U) > E
sup
Σ TU)
+ 32B²t
$ <cxp(-(n/2)2
n/2
UEC(T)
Pr (2g,T > B.Zg 16nB²1) S /16).
19

---

Apply a union bound, we have
Pr
WT E r + 16n(n- 1)Bat 8 s (n - 1)exp(-nt(/10
Next, we marginalize the event E.
Pr
WT
B.g + 16n 16n
s B[mexp(-nn' //6]///]]]]] & ( (mxx))[(exp((nll -n1]/16))
$ (m1m²) (nn) /16) & exp(-m
Next, we considering bounding Eg=1 R.Z.Tr. Note that
R-
Σ ال & |}
EZgT & 16BTE
By using similar argument in Lemma A.I, we are able to show that for any x > 0,
mmmmmmu / MaOO) } J expll=loo(d""
Pr
|E 2 xv Ba log(d)
Therefore,
EZg.r E 16BºT /og(d) mmmmzt / MTU
9=1
Combining the result from Lemma A.6, we have
Pr (Tr Z BºT /lg(d)) mmmmzt / Mao] + (m122m022 BB1) s (m1m2) expp-mmmmm. /16). 2/16))
When T VIITu/T TL, have
Pr Wr 2
s 1/d.
When T / /TTu/ RL, By taking
d have mimaae
-TT TL
log(d?) }.
Pr Pr(WT 2 BTT /lg((d) [mimant v Mar) < (m1m22) exp
A.3 Proof of Theorem 5.3
Proof. It follows from the definition of the estimator À that
((A) + || s ((A.) A A.ll.
cquivalently
((A) - ((A.) S > (1114.11.-1
which implies
vec(A (V((A.), vec(A Ā - A.)) + vec(A A A.) ( - -A)) -1
where Á = tĀ, (1 - t)A for some & [0.
Let's denote A A Á.
20

---

From Lemma A.3 and Lemma A.2, we have
A 11 log(d)
m1 v MTU
B log(d) (m)mm))))))))))))mmmm))))))))
km.mya - llg(dd Mim2TU V MTu
B² ( 1/2
with probability at most 3/dd
Therefore with probability most 3/d.
km1m2 L
S B'| || (lg(d)
m1 v Mau
+ B²
+vec(A A.) (oooooo A A.)
S B² A 1l log(d)
Mim2gUU V Mau
(mim2TT)) +\ (11..11 -|21)) + All
BB (111mmm()) (m
Let {ug E IR"") } and {Vi. E ] be the left and right singular vectors of A, respectively. For any matrix A E I Xm2, we let (A) S I and col(A) S R denote its row space and column space respectively. Let the column and row span of A, U col( A.) span uN} and V. row(A.) span(v respectively. Define
M {A row(A) (A) V., col(A) C..).
M (A (A) v.t, col(A) C C
It is easy to see that M S M, but M # M. The subspace compatibility of M is upper bounded by /2,, i.e.
|A|l |
S V2r.
sup AEM((0)
We observe that
A
A.
A M
+ A M= |1, 2 A. A M 11-1-1114 = -IIA. A M 1111-114 A
By choosing
> 2( V ( || + B2 /lg(d) [mimmTu V (T)) ) we have
kmjm2 2
13
(IV || + B² log (d) mi / MMU) (1 Ml
+ +(II Ml1. - | R |l,) + B log ((
$ 3A A + B² log (m ( (m 33 + B² P
Then, we could derive
3\v2r 2r
Ba
(mm
A
1 S
|||F +
kmimaTi
km1ma
X2r
Ba log(d)
TU
| S max
m2
mmmo(Km,mmm?)
K
TL
MiMpAL
Due to Lemma A.1,
Pr [IEE Z / B2 [lgg(d) + log (m m mim2Tu / MTT $
3
d
we can take A x (B² log(d)
[mimg V MTU ) and with probability at least 1 6/ d, we have
B log df2
π
Mr
Ba log(d)
T
max
V
71172
m. M12
K
mi 722
21

---

A.4 Auxiliary lemmas
Lemma A.5. For any collection of individual index pairs : sn].
(a) (From Lemma S.4. in [36]) When is even, that within each group, there are n/2 pairs and no repeuted individuals.
decompose it into (n 1) groups such
(b) When n is odd, we can decompose into n groups such that within each group, there are (n - 1 pairs and no repeated individuals.
Proof. The proof for part (a) is done in [36].
For part (b), when odd, we consider an extra index + and add all the pairs { 11
j S n to the original collection. For the new collection of individual index pairs {(,j'): : S < j' S n + }}. since n + is even, we can apply part (a) and get n groups such that within each group, there are (n 1)/2 pairs and no repeated individuals. Therefore, every index appears in each group exactly once. each group, we remove the pair with n + it. We now obtain n groups such that within each group, there are (n - 1)/2 pairs and repeated individuals for the collection of individual index pairs ((ig'' S < K S n).
Recall that
Zij,y (Yi) Yey)² (Yr)) - Ar )/2)
1 1 eXp((V1) - Yey) - Avr ))
Σgg Σ
Egg Tyg Zig,es (Eij Eggr)
for any collection of non-overlap index pairs.
We analyze the upper bound for E. ||El to prove Corollary 5.3.
Lemma A.6. Take Eis Teg and En.g defined in (11). We huve
Pr
n
2 el
Rid)
s exp(-m)m25L)
ijj
1-- 1
Pr
En,g > 2m, mmmmmnMr Σ
< 2M cxp
{ mmm
Proof. Note that Ti, are independent Bernoulli random variables and En Eis Tags We apply Chernoff's inequality and obtain
Emes) (e(Ens Tis)
Pr (n 2) S expl-
t
for any / En. Take = ElEi, Te.) and we have
Pr
2 el Σ Ti.s)
I expl-
Σ
Test pxpp-mm,man
in
i.
Note that
Eng
max
Σ ket
1ff i Σ 1ijx jut
Regf-
mg
max
To
TofTe
1=1 j#j
J=1
22

---

We consider bounding Ei=1
TiyTig. Similarly, without loss of generality, we assume is even, and by Lemma A.5, we can decompose
ma
m2
m1
Σ
Σ
Σ
TiJT,y)
1
g=1
(J")EC;
Within every group Gy every pair Ti Tor is independent of others. Then we apply Bernstein inequality to bound Σ E (uneea TigT.
-12/2
Pr
Σ
Σ (J''E,',
TTjTy
Σ Σ
T 2t
$ cxp
1111 Ei=1
LiSD)E ET
+t
i=1
i= (..D)
-t/1
I exp
Take / = mymmn we have
mi
Pr
Σ Σ
TijTig 2miman
I exp f m33
(12)
i=1 (JJ'E,
Take a union bound over g I,..., m 1, we have
Pr
TijTey > 2m1m2(m2 - 1)=7
I m2 exp { - m1
m2
Pr
Σ
Σ
TrJTy > 2mim2
$ M exp 1
:=1
With the same argument, we have
Pr
Σ
Toy
> m
<Mexp (-mmm//aa7///3
j=1ip Eppta
And therefore
Pr
Σ
Eng mm
< 2M exp (-mimmnt/3)
B Identifiability of dispersion parameter in Gaussian distributions
Assume Yı N (Hurs with missing mechanism:
Pr(Ti 1|Y =v) - cigss1))
(13)
where Cij, s(.) E 1).
Lemma B.I. Assume that
Cijs(y)
bij lim cijs(y) bly.
lim dlys'(y)
s())
where big, byy can not be both 0 or simultaneously.
23

---

If a # o', then for any (ey. G.j s(y), sy(),, at least one of the following two statements holds:
Cajs(y)
lim
to0 or 0
(14)
+0+00
y 13
2 (v)
uii
())((y)
lim
a
-0 or 0.
(15)
y nig
S (1)
Proof. We observe that
Mii
(1j(())
(a²-o²))
(d""u-0'''
2²p²²
0² 0
exp
y-
d (1)
2022 020²2
202 (l,s'(u)
Gys(y) With assumption, assume limg- [v] by and limy-+-o
( ('
blg.
When bij E (0, oo), if a > o', when + co, (14) converges to oo.. If a < <o', when - 00, (14) converges to O.
When bij = and b/ * 0, o < o', when y + oc, (14) converges to is still true. If > o', when y + -o, (15) converges to oc. as b/ # O.
When bij- and 8/ * xc, if o', when y + oc, (14) converges to co. still holds. If < o', when y oo, (15) converges to as 8/g # oc.
Theorem B.2. Assume at most one of lim syy) 0 and limt-+oo s(y) = 0 is true, o² is identifiabl.
Proof. Proof by contradiction. Suppose that there are two sets of parameters satisfying the same observed distribution:
Φ
y Mij
cijs(V)
1
("-
(D-M/)
y 1/3
dlss(1).
o
0¹
Therefore,
y Pii
Cif syjs(1)
p (0,
plg
S5 (y)
Φ
However, if a * o', by Lemma B.1, we know that the left-side will converge to 0 or co, which violates the above equation. Thus, we must have o'. o² is identifiable.
C Algorithm and experiments
Note that the objective function and the constraint set are both convex, and the constraint set is closed convex set. So (6) is convex optimization problem. To deal with the constraint A, one can use the Alternating Direction Method Multipliers (ADMM) to tackle it. However, the computation of ADMM can be slow in practice. We propose practically more efficient algorithm based on the idea of proximal gradient descent with an additional projection as detailed in Algorithm GitHub?. In the algorithm, POCS is the projection onto two convex sets {A (J, A) = 0} and (A ||A|] < a} (see Algorithm 2). The notation Sx(-) is the soft- ooftthhresholdigg operator defined by SA = UD where DA = diag((d, - A)+...., (d, - })+] with 4 = max(t, 0), and U diag id,,..,,d, V is the singular value decomposition of A.
1. The code is publicly available the intersection
24

---

Algorithm Projected gradient descent
Initialize: Initialize (0) randomly, set learning rate 7)- for = T
((1) (z) (()(
Q(t) = S (K(t))
A(t 1) (OC)(Q(())
end for
Algorithm 2 POCS
Initialize: Input matrix Q E 1mmxxma t t= O. while Q' #Q do
Q'
Q 0=0 Q
j=1 Qi.
mymg
0 = (12 S S
Qi, + (1iisl > sign (Qis)
end while
Due to space constraints, we present the test mean absolute errors (TMAE) curve (Figure 4) for simulation setting in Section 6. Note that the trend consistent on both TRMSE and TMAE with multiple runs.
C.1 More simulation: missing on small entries
We conduct simulation studies in higher dimensions with different missing mechanism where the observation probability reads
Pr(T, 1l I+ exp--333(X 2))
which means larger potential observations imply higher observation probabilities, as shown in Figure 5. We generate 100 x 100 matrix A, with rank 5. The observations Y.j are generated from a Gaussian distribution with mean A.,, and variance 1 independently. Note that compared with experiments shown in Section 6, the dimension is larger and the observation probability is flipped.
As shown in Figure 6, other methods suffer from a severe observation bias, and the recovered entries are right-skewed, whereas the distribution of true entries is symmetric. Our method alleviates the observation bias and recovers the symmetric pattern of the distribution on recovered entries. The test root mean squared errors (TRMSE) and test mean absolute enrors (TMAE) of recovered entries are reported Table 3. The experiments are repeated with runs, and the standard deviation of both metrics is included. Our method shows significant advantage when the observation bias persists.
TMAE for different variances
2.0
1.5
1.0
0.5
MFW
C2
0.0
Our
0.0
0.2
0.4
0.6
0.8
1.0
Figure 4: TMAE with standard error for different variances o² 0.0, 0.4.0. 1.0.
25

---

Observed Unobserved entries
140
unobserved
120
observed
100
Count
00-
40
-10
10
Figure 5: Distribution of observed and unobserved entries, implying the existence of observation
bias.
Method
TRMSE
TMAE
SoftImpute
1.3973 + 0.0844
1.014 + 0.0636
CZ
1.410 = 0.0938
1.0177 + 0.0752
MFW
2.6763 = 0.0864
2.2405 + 0.0728
SNN
5,8402 5.5596
2.7677 + 0.1323
Our method
0.6482 = 0.0396
0.4920 + 0.0237
Table 3: Test root squared errors (TRMSE) and test mean absolute errors (TMAE) with standard deviations.
True entries
Soft Impute
Max Norm
800
GUD
400
1000
Count
Count
A00
500
200-
-5
Model Free Weighting
Synthetic NN
Pseudolikelihodd
800
400-
Count
200-
2004
Figure 6: The recovered entries are right skewed from other methods.
C.2 Real data application: more details
In this section, we use three data examples to illustrate the robust performance of the proposed method. Similar to the implementation procedures Section 6, we equally separate half the testing data points and use them as the validation dataset to tune the hyperparameters for all the methods mentioned in Section and learn the shift and scale parameters for the proposed method. Then we used the remaining half of the test data points to evaluate their performance.
26

---

C.2.1 Tobacco Dataset
This dataset available in Table 1I in [9] and has been widely studied for synthetic control methods le.g. IJ. From Table 11 in [9], we can obtain the Tax-Paid Per Capita Sales in Number of Packs for 51 states across the US from the year 1950 the year 2014. California implemented a large-scale tobacco control program in 1988 and we consider it as the "treated" state. We take the remaining 50 states as the control states, For the detailed background, we refer readers to [1] and [2].
We collect data from the year 1970 to the year 2000 and restrict our focus to the 50 control states, which results in 50 by 31 matrix. Following the same experimental setup in [2], we generate MNAR data. We introduce "interventions" " to a subset of states in 1989 based on their change in the mean of cigarette sales during 1989-2000 versus that during 1970-1988. See details of the intervention probabilities in Section 6.3 in [2]. As long as an intervention is adopted for state i, all sales under control after 1988 are unobserved, i.e. T = 0 for j 19. And we take Yi j 19 as the test data points.
Table 2 provides the results for five methods under 100 randomizations the intervention based on the intervention probability for every state. As we can see, our method only performs worse than SNN for this MNAR dataset, with significantly smaller TRMSE than the other three methods. Note that in order to compare the errors, we need to perform a transformation on our estimated matrix. For this study, the untransformed data for every state during these 30 years. For example, as illustrated in Figure 7, using untransformed estimated results from our method, we are able to capture the overall trend of the sales change for state KS across 30 years. Our method can capture the increasing trend of sales for the state KS after the year 1988.
also provide valuable information about the trend of sales change
Observed
Our method (untrandforme)
SVN
Softimpute
MFW
204
220
220
332
200
300
65.2
300
180
110
340
07.5
178
05.0
160
100
1300
2000
2000
1370
1080
3300
2008
13700
3000
2000
2070
3390
2000
2000
2000
1890
1550
2000
3390
2008
Figure 7: The first plot shows the observed sales for State KS across 30 years. The second plot is the untransformed estimated sales by our method from 1970 to 2000. The rest four plots the estimated sales from SNN, SoftImpute, CZ, and MFW from 1970 to 2000 for the state KS.
C.2.2 Coat Shopping Dataset
This dataset is available at https://wwwd cs. www.cooeleeduecciiiiiooeeoleaeee adu/"sschaabss/marr It contains ratings from 290 Turkers on inventory of 300 items [30]. The training set contains 6960 self-selected ratings and the test set consists of 4640 entries. This dataset has been used as an illustration for the nonuniform missingness [e.g. 30, 35].
As Table 2 shows, SNN performs lot worse than the remaining methods for this dataset. MFW has the smallest TRMSE. Our method has smaller errors than Softlmpute and has comparable performance to CZ.
C.2.3 Yahoo! Webscope Dataset
sandboxx yahoo. wwt.coooccccao hamm/caalogg... phppdaattpppdaaapeepee r&did-3, which contains ratings from 15,400 users on 1000 songs. The IDs for users and songs are randomly assigned. The training set includes approximately 300,000 ratings from these 15,400 users. The ratings from the training set are collected during the normal use of Yahoo! Music services for each user. The test set was constructed by surveying the first 5,400 users. And each surveyed user provides ratings for exactly 10 additional songs.
This dataset is available at battps://webstt
27

---

Due to its large size and to simplify the computation, we conducted a selection procedure to reduce the size of the matrix. First, we focus on the users with ID 1-50, 5401-5550, and songs with ID 1 1-250, which results in matrix where we have 50 surveyed users and 150 unsurveyed users. Next, we construct the training (test) matrix from the original training (test) dataset with selected user IDs and selected song IDs. Then, we remove those users and songs that have no single observation in the training matrix. In the end, we obtain a matrix with 199 users and 219 songs.
From Table 2, we can see that the two methods (SNN and our method) that are designed for MNAR have better performance than the remaining methods, and our method has the smallest TRMSE.
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main contributions are adequately described in the abstract and introduc-
tion.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitation of this work such the identifiability issue is discussed in
Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model cell-speciiiiatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
29

---

Answer: [Yes]
Justification: The theoretical assumptions and proofs are provided Section and Appendix
A main contribution of this work.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide a complete description of experiments Section 6&7 and Ap- pendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
30

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The data used in the paper has been cited and linked properly (Section 7). The implementation detail has been described in detail in Appendix and the code will be made available on GitHub after acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/ public/guides//0/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /nips. cwtppblic/guiiee..e wwwlc//ggus///eeeee httpg/ddddddeeduubiiiiiiiieaaaee sondeSuubisssionooll.
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/ettails
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
All the training and test details can be found in Section 6&7 and Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The error bars and statistical significance has been shown and discussed in Section and Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
31

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
The experiments performed in the paper don't Itn't require intense computer resources, and can be reproduced on personal computer.
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: / http///eerrippppeeee httpppp....c..ttctctcccieiieeee.
Answer: [Yes]
Justification: This work abides by the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
32

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The assets (data) used in the paper open for non-commercial use by academics and have been properly credited Section 7.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
33

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
34

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "IbFkdRtlY5", "reviewer": "Reviewer_1V66", "summary": "Current matrix completion approaches mostly deal with non-uniform sampling scenarios. However, few  approaches can allow the missingness to depend on the mostly unobserved matrix measurements. In this paper, the authors propose a regularized pairwise pseudo-likelihood approach for matrix completion in this scenario. The proposed estimator can recover the low-rank parameter matrix asymptotically up to an identifiable equivalence class of a constant shift and scaling, at a near-optimal asymptotic convergence rate of the standard well-posed setting, while effectively mitigating the impact of informative missingness.", "questions": "1)\tI still am unclear about the meaning of “informative missingness”, could the author give a more detailed definition and a concrete example? \n\n2)  Are the authors the first to consider this informative missingness setting in matrix completion? And are there any other methods to address informative missingness aimed at matrix completion? And How to evaluate the strengths and weaknesses of these methods ( including the method proposed in this paper).\n\n3)\tWhat is the difference between the pseudo-likelihood method and Bayes modeling?\n\n4)\tPlease provide a comparison of the computational time between the proposed method and the previous algorithms for matrix completion tasks. This is crucial as people often deal with high-dimensional and massive datasets, where computational efficiency is a key factor. If possible, please also provide the errors (TRMSE) versus the iterations/time during the trajectories.\n\n\n5)\tIt might be challenging to effectively identify whether a scenario qualifies as \"informative missingness\" and apply this approach. For instance, on the Tabacco Dataset, the method does not outperform the SNN method. Is this result arise from this phenomenon/dataset that doesn’t belong to the “informative missingness” scenario? How to identify a phenomenon/dataset belonging to the “informative missingness” scenario?", "limitations": "1) I'm uncertain about the article's claim that \"informative missingness\" is widespread and significant in real-world situations. It might be challenging to effectively identify whether a scenario qualifies as \"informative missingness\" and apply this approach. For instance, on the Tabacco Dataset, the method does not outperform the SNN method. This dataset may not fall into the “informative missingness” scenario. How to identify whether a phenomenon is \"informative missingness\"?\n\n2) There is not an extensive literature review on informative missingness in matrix completion or other related problems, please provide a detailed literature review about informative missingness and related approach comparisons. \n\n3)  In line 350, the author says the proposed method's grouping nature adds an extra computational burden and I am not sure whether this approach is computationally efficient in practice.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper considers the matrix completion problem under the informative missing scenario and applies the pseudo-likelihood method to matrix completion for the first time, which is relatively novel. This approach can effectively mitigate the impact of informative missingness with some theoretical guarantees.", "weaknesses": "However, there is a lack of literature review related to the informative missing setting and a lack of comparison with related methods aimed at the informative missing setting, making it difficult to accurately evaluate the contribution. \n\nAlso, I am unsure if these scenarios are widely applicable. In the experimental section, the proposed method does not achieve the best results on some datasets. For instance, on the Tabacco Dataset, the method does not outperform the SNN method. \n\nLastly, in line 350, the author says the proposed method's grouping nature adds an extra computational burden, thus this approach seems not to be computationally efficient.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the effort you have spent reviewing our paper.\n\n**Q1: Could the author give a more detailed definition of informative missingness and a concrete example?**\n\n**A:** We used “informative missingness” to refer to what statisticians often called Missing Not At Random (MNAR) assumption [LR], in which the probability of missingness can depend on the value of the variable that is not observed.  In ratings of movies, for example, people are more likely to watch movies that they may like due to unknown preferences and those preferences would also affect the rating, the missing probability is therefore likely dependent on ratings which may be unobserved.\n\n**Q2: Are the authors the first to consider this informative missingness setting in matrix completion? And are there any other methods to address informative missingness aimed at matrix completion? And How to evaluate the strengths and weaknesses of these methods?**\n\n**A:** Please see our global rebuttal about related works and theoretical evaluation. As for evaluating the numerical performance of these methods, we require independent sampling of validation data or known generating mechanisms. In the simulation study, we generate data under the condition satisfied for our setting, and we have the validation data to evaluate the completion errors. Our methods outperform other methods. In the Tabacco real data, we create the missing mechanism following the steps described in [2], which satisfies the conditions in [2] but violates the assumption in our setting, and our method still gives robust performance. Please see more details in the global rebuttal as well.\n\n**Q3: What is the difference between the pseudo-likelihood method and Bayes modeling?**\n\n**A:** The pseudo-likelihood is not a full likelihood that is used in conventional Bayesian modeling.  Indeed, Bayesian modeling for the missing not at random settings will require parametric modeling of the full distribution of the outcomes and missingness mechanism, which is usually viewed as a daunting task.  Because of identifiability issues, the result from Bayesian modeling will typically depend heavily on the prior used, which is another undesirable feature. The pseudo-likelihood used eliminates unknown $t_{ij}$ and function $s(\\cdot)$, which allow us to focus on the estimation of the target matrix.\n\n**Q4: Please see our global rebuttal.**\n\n**Q5: It might be challenging to effectively identify whether a scenario qualifies as \"informative missingness\" and apply this approach. For instance, on the Tabacco Dataset, the method does not outperform the SNN method. Is this result arise from this phenomenon/dataset that doesn’t belong to the “informative missingness” scenario? How to identify a phenomenon/dataset belonging to the “informative missingness” scenario?**\n\n**A:**  Yes, you are right that it is challenging to effectively identify informative missingness / missing not at random (MNAR). Indeed, it is known in the missing data literature that available data is generally unable to distinguish between missing at random and among MNAR models [4, 5]. As in page 4 of [D], \"It is impossible to test whether the MAR condition is satisfied, and the reason should be intuitively clear. Because we do not know the values of the missing data, we cannot compare the values of those with and without missing data to see if they differ systematically on that variable.\" Therefore, a fundamental limitation in any missing data analysis is that the missing mechanism has to be somewhat assumed. Given this fundamental challenge, our goal here is to adopt a flexible enough missing mechanism so that the methods still work for a wide range of scenarios to alleviate the concerns of mis-specifying missing mechanisms.\n\nThe separable assumption that we assumed indeed includes uniform missing, missing-at-random and the focused MNAR assumption [BH] as special cases, and has been argued as a general but workable assumption [34]. For matrix completion, the separable assumption that we use in this work is already fairly relaxed compared to those in the missing data literature, since each entry could have a complicated observation probability based on its location as well as a function on the potential observation (even though it could be missing). In terms of location dependence, it is allowed to be completely flexible. Among matrix completion methods (especially those with theoretical guarantees), our assumption covers the uniform missing and missing-at-random settings, which is the focus of most matrix completion literature. In other words, in terms of the applicability of the missingness assumption, our work is generally more applicable than many existing literature that assumes uniform missing and missing-at-random settings. When those settings fail, our assumption could still hold and our method will still have theoretical guarantee while others may fail.\n\nAs for the Tabacco dataset, we note that the way to generate missingness is adapted from the SNN paper. SNN is well-designed for the underlying missing mechanism. When one entry is missed in Tobacco dataset, the entries in the following period are also missed. This does not satisfy the assumption of our work. So it is not surprising to see our method perform sub-optimality. However, the performance of our method still remains strong. This example can be used to illustrate a situation where the assumption of our method fails.\n\n**References:**\n\n[LR] Little R J A, Rubin D B. Missing data in large data sets. Statistical Methods and the Improvement of Data Quality. Academic Press, 1983: 215-243.\n\n[D] Allison, P.D. (2002) Missing Data, Quantitative Applications in the Social Sciences, Thousand Oaks, CA:SAGE.\n\n[LR2] Little R. J. and Rubin D. B. (2019) Statistical analysis with missing data, Hoboken, NJ:Wiley.\n\n[BH] Gomer B. and Yuan K.H. (2021) Subtypes of the missing not at random missing data mechanism. Psychological Methods, 26(5), 559-598.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "EGzT6llN0m", "reviewer": "Reviewer_Pbx3", "summary": "The paper proposes a novel matrix completion method where the entries are missing not at random. The author(s) tackle the problem using a penalized pairwise pseudo-likelihood approach. The key contributions of the paper are (a) a flexible separable observation probability assumption that depend on the measurements and (b) to provide a novel asymptotic result concerning the concentration bound on the proposed estimator. The success of the proposed method is validated via numerical experiments and on three real data analysis.", "questions": "I have the following queries for the authors-\n\n(a) In assumption 2.1 is it required to have $s(Y_{ij})$ distinct at least for one pair $(i,j)$ and $(i^{'},j{'})$ ? Otherwise we may end up with a situation where the assumption 2.1 is another variant of non-uniform missing structure scenario.\n\n(b) Why do we need the constraint $\\ || A || \\_{\\infty} \\leq a $ in the optimization described in (6) ?\n\n(c) Computational cost vs performance gain should be examined in both real data and simulations to understand the efficacy of the proposed method.\n\n(d) One thing that comes out in Table 1 tobacco dataset is that the standard error of pairwise pseudo-likelihood is the second highest among all the methods. It may be interesting to check through the simulations if the standard error of pairwise pseudo-likelihood  is in general remain high?", "limitations": "The authors have adequately addressed the limitations of the work.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main contribution highlighted in the work is how to perform matrix completion when the entries are not missing at random (MNAR). The fundamental assumption on the observation probability given the measurements is based on a separability assumption which tacitly helps avoiding the non-identifiability issue typically faced in MNAR setting.\n\nSome other strengths of the paper are the following-\n\n(a) novel use of pairwise pseudo-likelihood approach to solve the missing completion problem in MNAR setting\n\n(b) novel theoretical result concerning the concentration bound on the proposed matrix estimator\n\n(c) well written clarification (with appropriate examples) of the non-identifiability issue in the MNAR setting", "weaknesses": "Following are some of the weaknesses of the paper\n\n(a)  A bit more discussion on how the constants $\\kappa$ and $\\rho$ influence the right hand bound on equation (7) would be insightful.\n\n(b) Some comparison of the computational times of the competing approaches vs the proposed approach would be helpful.\n\n(c) In the simulations, apart from Gaussian distribution mechanism, it would have been interesting to see situations where observations have been generated from a skewed distribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for the constructive feedback and review.\n\n**Weakness: A bit more discussion on how the constants $\\kappa$ and $\\rho$ influence the right hand bound on equation (7) would be insightful.**\n\n**A:** \nThanks for the suggestion. When $\\kappa$ is small, it means there exists one pair of indices such that $E((Y_{ij}-Y_{i’j’})^2)$ (other parts of $E [Z^2_{i,j,i’,j’}]$ is positive) is close to 0, and it falls into the difficult case to identify either of them. For $\\rho \\in [1, \\infty)$, when $\\rho=1$, it refers to the uniform missing setting, which is the simplest setting to deal with.  When $\\rho$ gets larger, there is more variability among $\\pi_{i,j}$ and so the bound in (7) is larger. \n\n**Q1: In assumption 2.1 is it required to have $s(Y_{ij})$ distinct at least for one pair $(i,j)$ and $(i’,j’)$? Otherwise we may end up with a situation where the assumption 2.1 is another variant of non-uniform missing structure scenario.**\n\n**A:** It’s correct that if $s(Y_{ij})$ are all the same, the missing mechanism is degenerated to non-uniform missing. But we don’t require that assumption that at least a pair of $s(Y_{ij})$ are distinct. Here the implication is that our method also applies to non-uniform missing scenarios. The fact that our method works for a wide range of scenarios is practically appealing.\n\n**Q2: Why do we need the constraint $|A|_\\infty \\leq a$  in the optimization described in (6)?**\n\n**A:** This constraint was used in our theoretical analysis, and is common in matrix completion literature such as [5] and [32] cited in the paper. Practically, the effect of this constraint is mild or non-existent, as it is common to pick a very large $a$. Indeed, some prior works might drop this constraint completely in the practical algorithm, which typically speeds up the optimization. \n\n**Q3: Please see our global rebuttal for question/weakness on numerical experiments.**\n\n**Q4: One thing that comes out in Table 1 tobacco dataset is that the standard error of pairwise pseudo-likelihood is the second highest among all the methods. It may be interesting to check through the simulations if the standard error of pairwise pseudo-likelihood is in general remain high?**\n\n**A:** That is a good point. We actually included standard errors in simulations. There are error bars in Figure 2, but they are small and hard to recognize. We will make it more obvious in the revision. We also had a table in the Appendix showing the standard errors (Table 2 in Appendix C). The standard error of pairwise pseudolikelihood is small. The performance issue in Tobacco dataset might be because the assumption of the proposed method is not satisfied  (if one entry is missed, the subsequent entries are also missed)", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "gZ5gl7o36o", "reviewer": "Reviewer_CJYv", "summary": "This paper describes a method for estimating missing values of a given non-completed matrix in a situation called MNAR, where the probability distribution for the observation depends on both the matrix index and the matrix value. \n\nThey propose a nonparametric method to prevent bias due to model selection. While missing value estimation in MNAR situations is generally an ill-posed problem, they removed the ill-posedness by imposing appropriate assumptions. This assumption decouples the probability of observation of the $(i,j)$ element of the matrix into an index depending part $t_{ij}$ and a non-negative function $s(Y_{ij})$ of the matrix value $Y_{ij}$, that is, $Pr(i,j)=t_{ij} s(Y_{ij})$, which makes $s$ and $t$ not appear explicitly in the conditional likelihood. \n\nThe paper carefully discusses the difficulties of scale equivalence and shift equivalence that arise when formulating the optimization problem naively under the assumption. The authors also obtain an upper bound on the error of the missing estimation in the Frobenius norm under reasonable assumptions. According to the author's description in L19, methods for estimating missingness in MNAR with such theoretical guarantees are very limited. Finally, they experimentally verified the usefulness of the proposed method on real and synthetic data.", "questions": "- L88: I would like to confirm the meaning of “independent” here. You mean $Y_{ij}$ and $T_{ij}$ are not independent of each other, but the tuple $(Y_{ij}, T_{ij})$ is independent of $(Y_{kl}, T_{kl})$ for all $k$ and $l$. Is that right?\n\n- In Appendix B, why do they use the symbol $a(y)$ instead of $s(y)$?\n\n[Edit: after rebuttal]\nAs the authors addressed my comments appropriately, I raised my score from 6 to 7.", "limitations": "The authors adequately addressed the limitations related to shift equivalence and scale equivalence in Section 3.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- They seem to have established a nonparametric method to prevent model bias.\n \n- They theoretically derived an upper bound on the error in missing values estimation. Since low-rank matrix completion is a well-known NP-hard problem, I believe their error bound has an important contribution to the machine learning community.\n\n- A general theory is developed since almost no assumptions are imposed on the nonnegative functions $s$ and $t$. For example, their theory can also deal with non-uniform missing settings.\n\n- The missing value estimation problem is formulated as a convex optimization problem. This is a very nice contribution. \n\n- It is elegant that $s$ and $t$ do not appear explicitly in the conditional likelihood due to their appropriate assumption.", "weaknesses": "-\tThe biggest concern is that the source code is not available. For example, the paper does not explain how to implement POCS in Algorithm 1. In this situation, there is still a concern about reproducibility without the source code. According to the checklist, the computations can be performed on a personal computer, yet it is better to describe the experimental environment, preferably identifying the operating system, RAM, and programming language.\n-\tIt is worth highlighting that their contribution is to remove ill-posedness through the appropriate assumption. However, it is necessary to define the term \"ill-posed\" properly and to prove why assumption 1 makes the missing value estimation a well-posed problem. Please let me know if I miss something at this point.\n-\tAlthough the experimental results with real data are not promising, this should not be a reason for rejection, given the theoretical guarantees and other strong contributions.\n\nCitations:\n- L166: please cite something to support your claim “Nuclear norm regularization has been commonly used to promote low-rankness in the estimation”.\n- L100: please cite something to support your claim “Matrix completion under general MNAR is ill-posed”.\n\nNotation:\n- For probability distribution, the authors use multiple symbols such as $P$, $Pr$, $p$, and $\\mathbb{P}$. I did not get how the authors make the difference among them. \n- Some symbols are not defined clearly. \n   - L161: I could not find the definition of the inner product between two matrices.\n   - L177: What is the symbol “N”? Also, in L178, the authors said, “phi is the pdf,” but I think phi is the dispersion parameter. Please let me know if I misunderstood something.\n   - L199: It is better to state clearly that $[n]$ is the set of natural numbers less than or equal to a natural number $n$.\n\nMinor comments:\n- What is the definition of the non-negative function in L106? $s:\\mathbb{R}\\rightarrow\\mathbb{R}^+$? If so, please write it clearly. \n- The computational complexity of the proposed method should be described.\n- L82: In my understanding, $Y_{ij}$ is assumed to be sampled from $f_{ij}(y \\mid A, \\phi)$. So, if they write $Y_{ij} \\sim f_{ij}(y \\mid A, \\phi) = \\dots $ in Equation (1), it is very kind to readers.\n- L196: It would be kind to note again that $m_1$ and $m_2$ are the sizes of the matrix A.\n- L656: $T_{i,j}$ → $T_{ij}$, $Y_{i,j}$ → $Y_{ij}$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review of our paper. \n## Weakness\n\n**W1: Please see our global rebuttal.**\n\n**W2: It is worth highlighting that their contribution is to remove ill-posedness through the appropriate assumption. However, it is necessary to define the term \"ill-posed\" properly and to prove why assumption 1 makes the missing value estimation a well-posed problem. Please let me know if I miss something at this point.**\n\n**A:** Here, ill-posedness refers to the non-identifability issue.The informative missing usually introduces an ill-posed problem not only in matrix completion but also in typical regression (see [14] and [20] cited in the paper). We would like to clarify that we didn’t claim the ill-posedness is completely removed. With assumption 2.1, the problem still possesses some identifiability issues as we mentioned in Section 4 (constant shift and scaling). We show that the proposed pseudolikelihood can recover the remaining identifiable equivalence class  (at a near-optimal asymptotic convergence rate of the standard well-posed (non-informative missing) setting). The problem is still ill-posed, however with pseudolikelihood, we can recover some useful information from it. A contribution of our work is to provide a solid understanding of what is identifiable and can be recoverable reliably.  \n\n\n**W3: Although the experimental results with real data are not promising, this should not be a reason for rejection, given the theoretical guarantees and other strong contributions.**\n\n**A:** Thanks for valuing our contributions. For the experiment results, we would like to add some additional insight. Our method targets the challenging MNAR setup where many existing methods fail. But, there is no free lunch. To avoid the bias caused by the MNAR, the proposed method in principle avoids using certain information in the data. Although it alleviates bias under complex missing mechanisms, one more crucial impact that we showed in our work is that the proposed method cannot identify shift-scale equivalence. In general, it is expected that the proposed estimator is less efficient compared to some existing methods under MAR or uniform missingness. This efficiency loss is a price that we pay for the robustness against the violation of restrictive missingness assumptions like MAR and uniform missingness. In other words, we expect our method to behave like the following. For uniform or MAR missingness, our method would be less efficient but remains competitive. For (strong/moderate degree of) MNAR under pairwise missingness, our method would perform better than many existing methods. More importantly, many existing methods would be inconsistent in general. In the experiments, our method performs robustly well for all three datasets, while a few alternatives perform very well in one, but very badly in another dataset. This aligns with the above explanation.\n\n**W4: Citations**\n\n**A:** Thanks for pointing it out. We will explicitly cite related works [23, 24] in the paper to support the claim “the nuclear norm regularization has been commonly used to promote low-rankness” and add a review paper [Hu] to it. General MNAR is ill-posed not only in matrix completion but also in regression [27, 30] and statistical inference [25] in general. A review paper [Tang] will be added too.\n\n**W5: Notation**\n\n**A:** We are sorry for the notation errors in the paper. \nYes P, Pr, p and $\\mathbb{P}$ are all for probability distribution. We will unify the notation to Pr in the paper. \nWe will add the definition of the inner product between two matrices “$\\langle A, B  \\rangle = \\sum_{i,j} A_{i,j} B_{i,j}$ for any matrices $A,B \\in \\mathbb{R}^{n_1\\times n_2}$”  in the beginning of Page 5. \nWe use N to denote the normal distribution. We will change it to $\\mathcal{N}$ to make it more clear. Also, we will replace the notation $\\phi$ with $p_{\\mathcal{N}}$ for p.d.f. of standard normal distribution, to avoid notation abuse.\nWe will add the definition of [n] as you mentioned in the beginning of Section 5. \n\n**W6: Minor comments**\n\n**A:** Thank you so much for the careful checking. We will make corresponding changes.  We will add formal definition of nonnegative function: $s: \\mathbb{R} \\rightarrow \\mathbb{R}^+$ in L106. We will add $Y_{ij} \\sim f_{ij}(y\\mid A,\\phi)$ in L82. We will remind readers that $m_1$ and $m_2$ are the dimensions of matrix $A$ in the beginning of Section 5. Also, we will change the notation $T_{i,j}$ and $Y_{i,j}$ to $T_{ij}$ and $Y_{ij}$ respectively. \n\n## Questions \n\n**L88 and Appendix B**\n\n**A:** Yes. The independent means $(Y_{i,j}, T_{i,j})$ and $(Y_{k,l}, T_{k,l})$ are independent of each other for $i\\neq k$ or $j\\neq l$. We will modify $a(y)$ to $s(y)$ in Appendix B to unify the notation.\n\n## References\n\n[Hu] Zhanxuan H., Feiping N., Rong W., and Xuelong L. (2021). Low rank regularization: A review. Neural Networks.\n\n[Tang] Niansheng T., and Yuanyuan J. (2018). Statistical inference for nonignorable missing-data problems: a selective review. Statistical Theory and Related Fields.", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:
We’d like to thank the efforts of all reviewers. The reviews are insightful and constructive to improve our work. We address some common questions in this global rebuttal and leave other questions in the detailed response to each reviewer.

We first discuss **the related works and evaluation of strength and weaknesses of them**. To the best of our knowledge, we are one of the first several works that consider the missing not at random setting in matrix completion and have solid theoretical guarantees. [2] claims that they can deal with MNAR setting. However, they assume selections and noise are independent conditioned on latent factors, as shown in their Assumption 2. On the contrary, our setting allows missingness to depend on noise. [HYF] also deals with informative missing in matrix completion. However, they need additional covariate Information to complete the matrix. 
To evaluate the theoretical strengths and weaknesses of these methods, one way is to compare the assumptions for the proposed methods. Compared to the above two works, our setting is more general as we do not require the independence between selections and noise given the true matrix and we do not need additional covariate information. However, we do require that $T_{i,j}$ is independent of $T_{k,l}$ for $i\neq j$ or $k\neq l$, while [2] allows selection to be dependent among different entries. Another way to evaluate is to compare the theoretical bound for the proposed estimators. [2] need additional technical conditions to develop finite sample error bound, and their bound is point-wise, i.e., the bound is for a given location $||\hat A_{i,j} - A_{i,j}||$. [HYF] also needs additional conditions for the likelihood and restricted eigenvalues in order to obtain the convergence. Our error bound is developed under relatively weak conditions and achieves the minimax convergence rate. 

Regarding the concerns of the **computational time**, we conducted a **computational complexity** analysis of our method. Note that the computational complexity of the pairwise pseudolikelihood is $O(n^2)$, where $n=|\mathcal{E}|$, the number of observations. The gradient of it is therefore $O(n^2)$ from Eq. (8). The soft thresholding operator relies on the SVD with a possibly non-low rank matrix, which takes $O(m_1 m_2 m)$ Flops. POCS (projection onto convex sets) takes $O(m_1 m_2)$. Combining them all, our algorithm takes $O(n^2 + m_1 m_2 m)$ Flops at each iteration. When the matrix has less observed entries, the second term dominates and our algorithm is as efficient as other SVD based methods. However, when the matrix has relatively more observed entries, the first term dominates, which could scale as $O(m_1^2 m_2^2)$ in the worst case. 


We added **comparisons of the computational time** regarding the setting in Figure 2 ($\sigma^2=1$). The computational times are listed as follows. While incorporating more complex missing mechanisms, our method and SNN also take the most time. One practical way to speed up the computation of our method is to use a stochastic version of Algorithm 1 (i.e., training in batches). The focus of this paper is more on the robust recovery when encountering informative missing, and less on the computational efficiency with the knowledge that it could be theoretically slower than other SVD based methods. But our method is still faster than SNN, where both methods consider more complex missing mechanisms. Given the promising statistical properties of the proposed method, a future direction is to develop scalable algorithms for the proposed estimator or its variants. 

|    | Time (s) |
| -------- | ------- |
| SoftImpute  |  0.01$\pm$0.005   |
| CZ | 0.22$\pm$0.09     |
| MFW    |  1.90$\pm$0.75  |
|SNN| 15.23$\pm$1.39|
|Ours| 8.67$\pm$1.23|

We’d like to add more details about our **experimental environment**. The experiments were run on a MacBook Pro, 2021 with Apple M1 Pro chip and 16GB RAM. The POCS (projection onto convex sets) in our algorithm is the projection onto the intersection of the nuclear norm ball and centered hyperplane. Both projection can be achieved quite effectively via truncating large values and eliminating the mean of all the entries. The POCS here refers to running these two projections iteratively until convergence. We will clearly describe these steps in the revision.


We originally planned to make the source code public on GitHub after the review period. We'd like to provide an anonymous repo about the implementation details for review purpose now. The rebuttal policy prevents us from sharing a link here. We have shared it with AC via a separate comment and you may request it upon your needs. 

## References

[HYF] Jin H, Ma Y, Jiang F. Matrix completion with covariate information and informative missingness. Journal of Machine Learning Research, 2022, 23(180): 1-62.

Meta-review: Good paper.
Decision: Accept (spotlight)