Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
Authors: Akhil Jalan
Yassir Jedra
Arya Mazumdar
Soumendu Sundar Mukherjee
Purnamrita Sarkar
Venue: ICML 2025 poster (2025)
Keywords: Transfer Learning
Active Learning
Matrix Completion
Missing Not at Random
Primary area: theory->domain_adaptation_and_transfer_learning
TL;DR: Rate-optimal transfer learning for MNAR matrix completion in both the active learning and random design settings.

Abstract: We study transfer learning for matrix completion in a Missing Not-at-Random (MNAR) setting that is motivated by biological problems. The target matrix 
$Q$ has entire rows and columns missing, making estimation impossible without side information. To address this, we use
a noisy and incomplete source matrix $P$, which relates to $Q$ via a feature shift in latent space. 
We consider both the *active* and *passive* sampling of rows and columns.  We establish minimax lower bounds for entrywise estimation error in each setting. Our computationally efficient estimation framework achieves this lower bound for the active setting, which leverages the source data to query the most informative rows and columns of $Q$. This avoids the need for *incoherence* assumptions required for rate optimality in the passive sampling setting. We demonstrate the effectiveness of our approach through comparisons with existing algorithms on real-world biological datasets.

Optimal Transfer Learning for Missing Not-at-Randond Matrix Completion
Akhil Jalan'
Yassir Jedra?
Arya Mazumdar
Soumendu Sundar Mukherjee' Purnamrita Sarkar
Abstract
Pij (Ma and Chen, 2019; Bhattacharya and Chatterjee, 2022).
Various MNAR models have been formulated based on missingness structures in panel data (Agarwal et a 2023b), recommender systems (Jedra et al., 2023), and electronic health records (Zhou et al., 2023).
We study transfer learning for matrix completion in Missing Non-at- (MNAR) setting that is motivated by biological problems. The target matrix Q has entire rows and columns missing, making estimation impossible without side information. To address this, we use a noisy and incomplete source matrix P. which relates to Q via feature shift in latent space. We consider both the active and passive sampling of rows and columns. We establish minimax lower bounds for entrywise estimation eтror in each setting. Our computationally efficient estimation framework achieves this lower bound for the active setting, which leverages the source data to query the most informative rows and columns of Q. This avoids the need for incoherence assumptions required for rate optimality in the passive sampling setting. We demonstrate the effectiveness of our approach through comparisons with existing algorithms on real-world biological datasets.
Motivated by biological problems, we consider a challenging MNAR structure where most rows and columns of Q (a noisy version of Q) entirely missing. Specifically, we consider both the active sampling and passive sampling settings for Q. In active sampling, a practitioner can choose rows R and columns C' so that entries in R x C are observed. This follows experimental design constraints in metabolite balancing experiments (Christensen and Nielsen, 2000a), marker selection for single-cell RNA sequencing (Vargo and Gilbert, 2020), patient selection for companion diagnostics (Huber et al., 2022), and gene expression microarrays (Hu et al., 2021).
The requirement that entire rows and columns must be observed is due to real-world constraints, such as the use of certain assays or experimental protocols. For example, metabolite balancing is a method for measuring pairwise metabolic interactions in cells, but requires choosing of metabolites (rows & columns) beforchand (Christensen and Nielsen, 2000b). Another example comes from gene expres- sion microarray measurements, which require choice of pa- tients (rows) and genes (columns) to measure beforehand (Hu et al., 2021). We study both of these settings in Scction 3.
1. Introduction
We study transfer learning in the context of matrix comple- tion, a fundamental problem motivated by theory (Candès and Recht, 2009; Candès and Tao, 2010) and practice (Fernández- Val et al., 2021; Einav and Cleary, 2022; Gao et al., 2022).
A major body of work studies matrix completion in the Missing Completely-at-Ranteee Randoa (MCAR) setting (Jain et al., 2013; Chatterjee, 2015; Chen et al., 2020), where each entry observed i.i.d. with probability p. A more general missing- ness pattern, known as Missing Not-at-Random (MNAR), considers underlying propensity matrix Pij that the (h entry is observed independently with probability
In the passive sampling setting, the practitioner cannot choose the experiments. We model this by sampling each row (column) with probability PRow (pcol). For example, microar- ray analysis detects RNA segments corresponding to known genes by using chemical hybridization. However, rows may be missing because of a patient sample failing to hybridize, and columns may be missing because of gene probe failure (Hu al., 2021). For an illustration, see Figure
'Department of Computer Science UT Austin, USA " 'Laboratory for Information & Decision Systems (LIDS), MIT, USA 'Hahcroglu Data Science Institute & Department of Computer Science and Engineering, UC San Diego USA "Statistics and Mathematics Unit (SMU). Indian Statistical Institute. Kolkata, India Department of Statisties and Data Sciences, UT Austin, USA. Correspondence to: Akhil Jalan <akhiljalan udex.s.edu>>.
This setting is inherently difficult because there many entries (i.j) for which row i and column j are both missing in Q. Clearly, even when Q is low-rank and incoherent, estima- tion is impossible without side information (Proposition 2.... Transfer learning is necessary to achieve vanishing estima- tion error since no information about Qiz is known. Hence, we consider transfer learning in a setting where one has a noisy and masked P corresponding to a source matrix P. P
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada, PMLR 267, 2025. Copyright 2025 by the author(s).

---

Optimal Transfer Learning for Missing Not-at- Matrix Completion
and Q are related by distribution shift in their latent singular subspaces (Definition 1.2), which is common model in e.g- Genome-Wide Association Studies (McGrath et al., 2024) and Electronic Health Records (Zhou et al., 2023).
row and column are chosen. Then, we have mi in- dependent noisy observations Q ......Q.. such that:
2
Qu++
in >0,
(I)
Contributions. Below, we list our contributions:
otherwise,
(0 N(0,0))) For Sij
(i) We obtain minimax lower bounds for entrywise estimation error for both the active (Theorem 2.2) and passive sampling settings (Theorem 2.1
(ii) Passive Sampling Setting. Instead of row and column budgets, there are probabilities PRow, PCol E [0. 1] corresponding to the random row mask fm iid. Ber(prow) and column mask Mly,,, Un iddd Ber(peol). Entry (i of Q is noisily observed m7, uy y and missing otherwise.
(ii We give a computationally efficient estimation framework for both sampling settings. Our procedure is minimax optimal for the active setting (Theorem 2.6). We also establish minimax optimality for the passive setting under incoherence assumptions (Theorem 2.9).
Qis Sust if if otherwise,
(iii) We compare the performance of our algorithm with existing algorithms on real-world datasets for gene expression microarrays and metabolic modeling (Section 3).
where Ci.j L.dd (0.,0%)
1.1. Organization of the Paper
We give our main theoretical findings, including lower and upper bounds for the active and passive sampling settings, in Section 2. Next, we compare our methods against existing algorithms on real-world and synthetic datasets in Section 3. Finally, we discuss related work in Section 4 and conclusions in Section
1.0
0.8
0.8
-0.4
1.2. Notation and Problem Setup
We use lowercase letters a, b, c to denote (real) scalars, boldface y, = to denote vectors, and uppercase A, B, C to denote matrices, For 1, let [n] [n]== (I......... La be the identity matrix and (e,) the canonical basis vectors. Let vyb:=max(a.pp and a == min (in(a.b).....a.............)) For multisets S.T and A E Rmxx let A E R [ [T) be the submatrix with row and column indices in S,7 respectively, possibly with repeated entries from A. Let @ denote the tensor (Kronecker) product: for A mx ,B R (A& B) E Rm x with (A@ ())+
Figure J. The missingness matrix for gene expression levels Day 2 of sepsis study (Parnlll et al., 2013) shows entire rows (patients) and columns (genes) as missing, due e.g. probe-target hybridization failure of the Illumina HT-12 gene expression microarray (Hu et al., 2021). We mark missing entries as (white) and present entries as 1 (bluc). This motivates our missingness model (Eq. (1) and Eq. (2)).
A. Bew- We denote the Frobe- nius norm as || F, max norm || ||||mma max == max., (Aigl max, ||ATe.ll.. e.ll2.
and 2 + norm as |All2_+o are with respect to m A unless
Asymp-
are the underlying source and target matrices, related by a distributional shift in their latent singular subspaces (Definition 1.2). We observe a noisy and possibly masked P. The observation model of Q depends on which setting below we consider. We will introduce both observation models here, and discuss the estimation framework used for both models in Section 2.2.
Setup. P.QER
totics (()).o specified otherwise. Recall that, for integer n, d such that d S n, the Stiefel manifold Oaxd (Hatcher, 2002) consists of all U e such that UTU
We now define matrix incoherence, which measures how concentrated the entries of the singular vectors are.
Definition 1.1 (Incoherence). Let M be an n matrix of rank d, and write its SVD as A = U.VT. The left (resp. right) incoherence parameter of M is defined as u m ml| /d (resp. μy - parameter of M is defined as y(M):= max max(pu,,
(i) Active Sampling Setring. We have a budget of Tro rows and Toa columns. We select rows (T,....T... and columns .1.....f.... possibly at random, and with re- peats allowed. Let Mij 2 0 be the number of times both
The incoherence
2

---

Optimal Transfer Learning for Missing Not-at-Randond Matrix Completion
We now formally define the distribution shift from P to Q, which generalizes the latent space rotation model (Xu et al., 2013; McGrath et al., 2024).
An immediate consequence of the above proposition is that the minimax rate for max squared error ||Q QI max is also M(do2). We see that in both error metrics, vanishing estimation error is impossible without transfer learning.
Definition 1.2 (Matrix Transfer Model). In the matrix trans- fer model, we have source and target matrices P.Qe P.Q.RmXA Rm such that:
2.1. Lower Bound for Active Sampling Setting
(i) (LowwRaan))
for dl m An where Up E Oaod. E and Ep 2 0 is diagonal d' d.
We now give minimax lower bound for Q estimation in the active sampling setting.
(ii) (Distribution shift) There exist 7,, R Raxd such that
Theorem 2.2 (Minimax Lower Bound for -estimattio with Active Sampling). Fix m.n and 2 S d 2 mn.. Fix Fix 0 and let [St] = Toot
Q= Q RT? VI, and 0 for i 1,2.
We will define the parameter space as:
Let P Pr.q,² be the distribution of (P,Q) where P:= P and Q == Q= where Gij" ~ (0,00))
Fmm.nd
(P.Q) E mm x mmn, : PUUEPT
Q RT V U D VEOOXdVVEOOX
Let be the class of estimators which observe P, and choose row and column samples according the budgets
T.T2, 1P=0)
(3)
Trow: Taol in Eq. (1), and then return some estimator
Q DERmx,, Then, there exists absolute constant C' 0 such that minimax rate of estimation is:
Definition 1.2 requires that the d-dimensional features of rows and columns lie in shared subspace for P. Q. Consider the matrix of associations between m genetic variants (e.g. the MCIR gene) and n phenotypes (e.g. dark hair) for different populations P.Q (e.g. England and Spain) (McGrath al., 2024). The above model ensures that the latent feature vector for a genotype (resp. phenotype) in Q is linear combination of those in P.
Cdlo2 [22|
Ep p -110- QEQ(P.Q)EP....
inf sup
We prove Theorem 2.2 using a generalization of Fano's method (Verdú al., 1994). We construct family of dis- tributions indexed by d2 source/target pairs (P(+), (ife))((()))) Q(+))== The source P is the same for all s, while each pair of target matrices (((e)) differs in most 2 entries. For example, say entries (5,6) and (8,7) are different between Q()) and Q(2), Regardless of the choice of row/column samples, the average KL divergence of pair of targets is small. Ife.g the entries (3.6). (8.7) are heavily sampled, then the estimator can distinguish Q Q well, but cannot distinguish Q0)) Qii for all t,t' pairs that are equal on (5,6) and (8,7).
Note that Ti,T3 2222 are not necessarily rotations and can even be singular. We set ||T:|22 = (11) to simplify theorem statements, but it not required.
2. Main Findings
We first show that without transfer side information from the source data P - completing the target matrix Q is impossible. To this end, we present a minimax lower bound on the expected prediction error. First, we define the parameter space of matrices with bounded incoherence:
2.2. Estimation Framework
Next, we describe our estimation framework. Given P and Q[R, C). where R, can come from either the active (Eq. (I)) or passive sampling (Eq, (2)) setting, we estimate Q via the least-squares estimator.
{
T(d) mn
QERT**
X X rank (Q)
m{Q) <(log(()))))
(4)
Proposition 2.1 (Minimax Error of MNAR Matrix Com- pletion Without Transfer). Let m, 2 and d < m A n. Let V (Q, PRow PRow) where Q Tild), x² > and PRow PCal E [0,1]. LetP' denote the law the the random matrix Q defined as in Eq. (2) with oq=
Least Squares Estimator.
1. Extract features via SVD from P=OPāpP?
=a, a, and denote the expecta- tion under this law as Ev. The minimax rate of estimation is:
LLtt be the multiset of observed entries. Then solve
éq: ; =arg min deRd (U))R
Σ
ū 00, (5)
1 11Q -Q113 2 (ddo2)
inf sup inf E
QET S.a5.99
PRR
S. 99 mm
where û, du VB VZe,.
3

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
3. Estimate Q:
Active Sampling.
Given U,V, and budget T Toow: Tool.
Qu== 2 Ög
(6)
1. Compute e-approximate G-optimal designs م, for {Ūpe; : [m]] and ev E [w]} respectively, with the Frank-Wolfe algorithm (Lattimore and Szepesvári, 2020b).
This fully specifies Q in the passive sampling setting (Eq. (2)). For the active sampling setting, we must also specify how rows and columns are chosen.
2. Sample iT... snd and Jn jT 1242.
Active sampling poses two main challenges. First, it is not clear how leverage P for sampling Q because samples are chosen before observing Q, so the distribution shift from P to Q is unknown. Second, the best design depends the choice of estimator and vice versa.
Finally, we specify the assumption we need on the source data P. called Singular Subspace Recovery (SSR).
Assumption 2.5 (c-SSR). Given P E (IR U (+]) m we
)+))mxx
have access to method that outputs estimates Up Onxd and Vp E EOnx, such that:
Surprisingly. we show that for the right choice of experimen- tal design, the optimal estimatoris is precisely the least-squares estimator Q as in Eq. (6). We use the classical G-optimal design (Pukelsheim, 2006). which has been used in reinforce- ment learning achieve minimax optimal exploration (Latti- more and Szepesvári, 2020b) and optimal policies for linear Markov Decision Processes (Taupin et al., 2023).
inf || -UW SESSR
Eor and
inf JIV -VV-VVVVVVVl W SESSR WvEOexa
Definition 2.3 (e-approximate G-optimal design). Let Ac C Rd be a finite set. For distribution π - [0,1], its G-value is defined as
for some ESSR >> 0.
This assumption holds for number of models. For instance, recent works in both MCAR (Chen et al., 2020) and MNAR (Agarwal et al., 2023b; Jedra et al., 2023) settings give estimation methods for P with entry-wise error bounds. In Appendix A.2, we prove that these entry-wise guarantees, combined with standard theoretical assumptions such as incoherence, imply Assumption 2.5.
g( max a" Em(a)aa") aEA
aEA
For 0, we say is e-approximately G-optimal if
g (t) < (1+e)infg(T).
We now give main upper bound, stated in terms of max squared error. Note that our upper bound for max error immediately implies upper bounds for commonly used metrics including mean squared (Frobenius) error, root mean squared error, and mean absolute error.
= 0, we say म is simply G-optimal.
Notice that in Eq. (5), the covariates are tensor products (é, @ú,) of column and row features. The G-optimal design is useful because it respects the tensor structure of the least- squares estimator. We prove this via the
Theorem 2.6 (Generic eπror bound for active sam- pling). Let Q be the active sampling estimator with Trow: Teol 2 20dlog(m + +n). Then, for absolute constants C,C' andlall e < To
Theorem (Lattimore and Szepesvári, 2020b).
Proposition 2.4 (Tensorization of G-optimal design). Let U E pmxxd V E IR= Let be a G-optimal design for {UTe, e, : E [m]} and Ç be a G-optimal design for (VTe, e; : e [m]]. Let mi, = p(i)((j) be distri- bution on [m] [n). Then ı is a G-optimal design on SeeeU:eeiiE. [m],jjj [n]].
d dozgoogm
11 Q1 <C(1+c) P.Q
P
[Tool
row
-d [Q1(2
> -1-C((m+n)
Consider a maximally coherent P that is nonzero at entry (3,5) and zero elsewhere. Then Q is also zero outside (3,5). By the Kiefer- Wolfowitz Theorem, the G-optimal design for rows (resp. columns) samples row 3 (resp. column 5) with probability 1. So, if P is not too noisy, then the G-optimal design samples precisely the useful rows/columns.
We will discuss implications of Theorem 2.6 in Remark 2.7. First, we give some intuition. Notice that Theorem 2.6 (and Theorem 2.9) gives an error bound as sum of two terms, which depend on the sample size and cssR respectively. To see why, let Q be the set of observed entries, either a pas- sive or active sampling setting. Let û; be the covariates
In light of Proposition 2.4, we leverage the tensorization property to sample rows and columns as follows.
è

---

Optimal Transfer Learning for Missing Nondom- Matrix Completion
as in Eq. (5). The observation Qiy can be decomposed:
While the results of (Jedra et al., 2023: Chen et al., 2020) used in Remark 2.7 require incoherence, recent work also gives guarantees ESsR without incoherence assumptions, although in limited settings.
Qin+ Qis)
= 000++
Gj
+ + 1la-Qp Qij)
(8)
Remark 2.8 (Incoherence- free minimax optimality). Let P PERRXX be rank-1 1 and Hermitian, and W is Hermitian with i..d. .N(0, 0z) noise on the upper triangle. Under the assumptions of (Yan and Levin, 2024), for constant C'
misopecification
noise
where
The population estimand 0q E ERdxd which is estimated in Eq. is)
> 0, Q is minimax optimal if
QQ Pq:=W6 TT: Wv,
Clog (1ogg))(0111 00 Q1
o
where Ti, T2 are the distribution shift matrices as in Definition 1.2, and Wv.Wv E Oddd are some rotations. The misspecification error is due to the estimation error of the singular subspaces of P and depends on EsSR as follows:
|
[
Taking |SX] (logn) since d = 1, and - 10]]2=0(|PP12)) require
Coog() 0(1) sag
by ef= +e[
2.3. Passive Sampling
We next give the estimation error for the passive sampling setting. The rate almost exactly matches Theorem 2.6, but we pay extra factor due to incoherence. This is because unlike the active sampling setting, if l2 mass of the features is highly concentrated in a few rows and columns, then the passive sample will simply miss these with constant probability. To give a high probability guarantee, we require that features cannot be too highly concentrated.
Therefore e = 00(5sRRR1111 for all i, Notice the misspecification error is independent of the estimator Qq. so will not depend on sample size. This explains the appearance of the two summands in our upper bounds. The first term depends on estimation error Oς - -d. which is unique to the sampling method. The second depends on misspecification, which is common to both.
Theorem 2.9 (Generic Error Bound for Q). Let Q be as in Eq. (6) and C C> an absolute constant. Suppose P has left/right incoherence μuú JU-HY respectively, and pRow PCol are such that mR
Remark 2.7 (Minimax Optimality for MNAR and MCAR Source Data). The rate of Theorem 2.6 is canimmx--ppimma in the usual transfer learning regime when target data is noisy (aQ large) and limited ((2) : Trow Toool small).
Cdlogm 2 pu
S
poan
2 PV
Cdlogn
Let puNV. Then
Suppose P is rank d, j=-incoherent, with singular values T1 2 ... 2 od, condition number x and m = n. For the MNAR P setting, suppose each Ptj has i.i.d. additive noise N (0.of.)) with sampling sparsity factorn n -8 for 3 [0,1] and pp 01). By (Jedra et al., 2023), Q is minimax-optimal if
& doglog(m++n) PRomPcOmmn
P Q
Q1 SCu
+ + s2s111111
4p0dd
11
og Ω
2 1 =1-0(())))-))
n
where S ignores log(m + n) 01) factors. For the MCAR P setting, suppose P has additive noise (O, of.) and observed entries i.idd with probability p 2 2²d with OP BS aa(P) Vietpa" Letting [S|== [0]==n"> n PRow by (Chen et al., 2020), Q is minimax-optiman
If P is coherent, the sample complexity [ 8 PRowPeom needed to achieve vanishing estimation error in Theorem 2.9 may be large. By contrast, our active sampling with G- optimal design requires only do (Theorem 2.6). This shows the advantage of active sampling, which can query the most informative rows/columns when P is coherent.
n 1 n²
2.4. Lower Bound for Passive Sampling
|0
We give a lower bound for the passive sampling setting in terms of fixed, arbitrary mask. To exclude degenerate cases such as all entries being observed, we require the following definition.
2 = OF [R] but we report bounds with the 'In fact 6gg weaker ( [1]] for ease of reading.
5

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
Definition 2.10 (Nondegeneracy). Let p > and "......m ~ Ber(p). Let DE (0,1) jmxm be diagonal with D2 - We say (7) (m)) is p-nondeggenertte for U E Onxd if DU /Pl - vF
Table 1. Summary of real-world datascts. The 2 norms are for Up, Vp,Ve,Uo, respectively, Notice these are within [0,1] always, and - oc norm of implies maximal coherence.
10
The Matrix Bernstein incquality (Chen et al., 2021) implies that masks are nondegenerate with high probability.
DATASET
SHAPE
RANK
2 NORMS
GENE EXPR. 31 x 300
4
0.55, 0.30, 0.64, 0.38
METABOLIC
251 251
8
0.99, 0.99, 0.99, 0.99
Proposition 2.11. Under the conditions of Theorem 2.9, the event that both (nk) is pRow nondegeeeeee for Up and that f is Rondegeneeeee for Vp holds with probability 2 - 2mmmmm)mmm
Chatterjee, 2022). We tune the method by passing in the true rank of Q as well as the rank of the mask matrix. Sec- ond, we use the transfer learning method of (Levin et al., 2022b). This method is designed for matrix completion, but in missingness structure different from our MNAR setting. For shorthand, we will refer to these as BC22 and L.L122 respectively. See Appendix B for precise details of our imple- mentations. Additionally, see Appendix B.1 for comparison to a VAE baseline from (Ipsen et al., 2021).
We can state our lower bound. proved via Fano's method. Theorem 2.12 (Minimax Lower Bound for Passive Sam- F Fet, be the parameter space of Theorem 2.2.
pling). Let
Lel
Imn.d:= { (P.)) (P.Q)EFm...d Fm are
The input to each of these, as well as our passive sampling method, is the pair P.Q. The method of (Bhattacharya and Chatterjee, 2022) requires input matrices to have entries in [-1, 1] entry in absolute value, for all methods. We also com- pute the active sampling estimator by fixing the budgets Tow = m PRow Teol Tcol= PPoo throughout.
Suppose (V;))= are nondegenerate with respect to U.V respectively. Let PQQ00 mma Poa be the law of the random matrix Q generated as in Eq. (2) with a QQ
we normalize all P, Q by their maximum
There exists absolute constant C >>0 0 such that minimax rate of estimation is:
- Q12 (m))..
inf sup (P.Q)EGm...d
E Pq.o2 pRow.caal
3.1. Real World Experiments
mi
Cd PRoM mn
In this section we study real-world datasets on gene expres- sion microarrays in a whole-blood sepsis study (Parnell et al., 2013), and weighted metabolic networks of gramm-egatin bacteria (King et al., 2016). Table summarizes the datasets, and Appendix B gives more details our data preparation.
(13)3-1
We immediately obtain the same lower bound for max squared error.
Patient Gene Expression Matrices. The matrices P, represent the gene expression for patients in a sepsis study (Parnell et al., 2013). Here TQeR31x30 where P:j measures the expression level of gene j in patient on day of the study, and Q corresponds to day 2 of the study.
We see that our error rate for passive sampling in Theorem 2.9 is minimax-optimal when (1),, modulo bounds on essR as in Remark 2.7.
Unlike the lower bound for max squared error in active sampling (Theorem 2.2). Theorem 2.12 gives lower bound for the mean-squared error, which is strictly stronger. An interesting question is whether Theorem 2.12 can be generalized to incoherence greater than a constant. We leave this for future work.
Figure 2 displays the maximum squared error for range of masking probabilities on Q. We see that both active and passive sampling perform well even at small sample sizes, while the transfer bascline method (Levin et al., 2022b) achieves a worse but nontrivial maximum error.
3. Experiments
Notably, active sampling no better than passive sampling here. This makes sense because P.Q are relatively incoherent (Table 1), so theoretical guarantees are the same.
In this section, we compare both our active and passive sampling estimators against existing methods on real-world and simulated datasets.
In fact, active sampling displays higher variation in error, due to the variability in random sampling from the G-optimal design. It is known that the G-optimal design for any A C Rd has support size (dd) (Lattimore and Szepesvári, 2020a), so the sampled set of rows and columns will vary somewhat
Experimental setup. We compare against two baselines from the matrix completion literature. First, we use the MNAR matrix completion method of (Bhattacharya and
6

---

Optimal Transfer Learning for Missing Not-at- Ran-ot--andom Matrix Completion
from experiment to the next.
LLL22
BC22
Passive (Ours)
Active (Ours)
Metabolic Network Transfer
LLL22
BC22
Passive (Ours)
Active (Qurs)
Gene Expression Transfer
Max Squared Error
Max Squared Enror
10
10-1
10-1
0.2
0.4
0.5
0.6
0.8
Prob. seeing entry in
Prob. of seeing entry
Figure 3. Max-squared error of Q-Q. with the same experimental parameters Figure 2.
Figure Max-squared error Q Q. Here, Q has PRow = PCal varying along the z-axis, which displays Phow. We oq =.11, and Pis fully observed. For each method, we show the median of the 50 independent runs, well the [10,90] percentile.
of our guarantees for incoherent matrices.
Each table entry shows 2 for mean rrean-squared error across 50 independent trials. We find that for a stylized example of maximally coherent P.Q. active sampling is much better than all other methods. However, for less stylized P.Q that are still incoherent, active and passive sampling are comparable, and outperform both baselines.
Weighted Metabolic Network Adjacency Matrices. We collect weighted metabolic networks from the BiGG Genome Scale Metabolic Models repository (King et al., 2016), consistent with recent work on transfer learning for network estimation (Jalan et al., 2024). Specifically, P.Q E 2511x251 where P.j 2 0 counts the number of co-occurrences of metabolites i and j in a reaction for organism P. Qij represents same quantity in different organism Q. We use the gram-negative bacteria coli W and putida for P.Q respectively. Unlike (Jalan al., 2024), we do not need to truncate the adjacency matrices to {0.1}, allowing us to handle edge weights. This makes a difference, because without truncation the edge weights distribution is highly skewed for both P.Q (see Appendix B).
Stylized Coherent Model. For n 200,d we generate Ur, Vp E {00,1)xdd via (Up) = 1, (Vr) = 1.0 and the other entries zero. We sample the diagonal entries of Ep Rddd iid uniformly at random from [0.5.1]. Then UPEPVT and Q UT.QV.. We call this class "Coherent."
Matrix Partition Model. For less stylized class, let m 300,n = 200 5,a 0.1,b= 0.8. We generate parti- tions Up E [0,1)mmx4 V where each row is uni- formly at random from (e1,...ea) Then, Bp E [0,1]
Figure shows max squared error for range of masking probabilities on Q. We that active sampling does well, while passive sampling is very poor (note however, that pas- sive sampling does relatively well for mean mean-squared error Figure 12). This is because P.Q are almost maximally coher- ent (TTble 1), so the assumptions of our guarantee for passive sampling (Theorem 2.9) do not hold. By contrast, active sampling performs well even in this highly coherent setting.
generated by sampling Ce [0,10dx with Ci. 1.i.d & ((o.)) and
Unif
Finally, we sample permutations II, 11, {0,1)axd uniformly at random from all such per- mutations. Then, P= PpUpBpV and Q= -UUpIIy B,II VT. We call this class "Matrix Partition Model" in analogy with the Planted Partition Model (Abbe, 2017). Spectral argu- ments show that such matrices are somewhat coherent (Lee et al., 2014), although not maximally so.
3.2. Simulations
In this section, we further probe the effects of incoherence by testing on two highly coherent synthetic datasets (described below). Table displays our results, with PRow PCal =0.10 0.1, and P fully observed. Note that 2dlog" here, so PRow :Pcol are near the theoretical limit
3.3. Alltion Studies
Our main focus to understand how sample budgets Toow Tools or probabilities PRow.Pee affects the estimation error for transfer learning. We also perform ablation studies
0.1 n

---

Optimal Transfer Learning for Missing Not-at-Randond Matrix Completion
but still assumes that entries are masked independently of one another. If masking variables are dependent, then thors assume identifiability of the matrix conditioned on the masking (Agarwal et al., 2023b), or that entries in every row and column are observed (Simchowitz et al., 2023). By con- trast, we study one of the simplest possible MNAR models in which entries of Q are not independent and entire rows and columns can be missing. This MNAR model motivated by biological problems (Christensen and Nielsen, 2000a; Hu et al., 2021; I; Einav and Cleary, 2022).
Table Comparison of the errors of different approaches synthetic data.
COHERENT
PARTITION
PASSIVE (OURS)
0.084 - 0.039 x10
0.040 0.090
ACTIVE (OURS)
0.009 0.015 x10 3
1046=00001
LLL22
0.061 + 0.037 x10
0.134
BC22
0.789 0.644 x10
0.305 0.002
BC22
Passive (Ouns)
Active (Ours)
Transfer learning. Transfer learning has been well-studied in learning theory (Ben-Davil et al.,, 2006; Cortes et al., 2008; Crammer et al., 2008). Recent works address various super- vised learning (Reeve al., 2021; Cai and Wei, 2021b; Ma et al., 2023; Cai and Pu, 2024) and unsupervised learning set- tings (Gu et al., 2024; Ding and Ma, 2024). Statistical works consider minimax rates of estimation, and computationally efficient estimators to achieve such rates (Tripuraneni et al., 2020; Agarwal et al., 2023a; Cai and Wei, 2021 a; Ma et al., 2023; Cody and Beling, 2023; Cai and Pu, 2024). In applica- tions, transfer learning from data-rich to data-poor domains has applications in biostatistics (Kshirsagar, 2015; Datta et al., 2021), epidemiology (Apostolopoulos and Bessiana, 2020), computer vision (Tzeng al., 2017; Neyshabur et al., 2020), language models (Han et al., 2021), and other areas.
Transfer Error vs Additive Noise dg
10P
10
Max Squared Error
10"2
10-3
10
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Transfer learning for matrix completion typically assumes the source P and target Q are observed in an MCAR fashion, and are related through rotation in latent space (Xu et al., 2013; McGrath al., 2024; He et al., 2024). Rotational shift is special case of our distribution shift model (Def- inition 1.2), which allows for any linear shift in latent space. On the other hand, works that study transfer learning for specific classes of matrices typically assume distributional shifts that are unique to those structures, such as in latent variable networks (Jalan et al., 2024) or the log-linear word production model (Zhou et al., 2023).
Figure 4. Ablation study for the effect of additive target noise in the Matrix Partition Model. For each method, we display the median max squared error across 10 independent runs, as well as the [10,90] percentile.
to test the effect of other model parameters, such rank, dimension, noise variance, etc. Figure 4 shows the effect of target noise variance on maximum error in the Matrix Partition Model with m = 300, n 200,d = 5,a 0.1,b= 0.8.PRow = 0.5,Pca = 0.5. Due to space constraints, we defer our additional ablation studies to Appendix B.
Optimal experimental design. Choosing set of maxi- mally informative experiments is classical problem in statis- tics (Smith, 1918; Pukelsheim, 2006) with connections to active learning (Dasgupta, 2011), 1), bandits (Abbasi-Yadkori Yadkori et al., 2011) 1), and reinforcement learning (Lattimore et al., 2020). Optimal designs have been studied for domain adap- tation (Rai et al., 2010; Xie al., 2022), misspecified regres- sion (Lattimore al., 2020), and linear Markov Decision Processes (Jedra et al., 2023). In our active sampling setting, we jointly query rows and columns to observe the corre- sponding submatrix of Q, rather than one entry at a time (Chakraborty et al., 2013; Ruchansky et al., 2015; Bhargava et al., 2017). But, the optimal row queries depend on column queries (and vice versa) - so we use the tensorization prop- erty of G-optimal designs (Proposition 2.4) prove global optimality with respect to joint row/column samplers.
4. Related Work
We review the most relevant literature here. For additional discussion, we refer to the surveys (De Handschutter et al., 2021; Jafarov, 2022) for matrix completion and (Zhuang et al., 2019; Kim et al., 2022) for transfer learning.
Matrix Completion. Most matrix completion algorithms require a Missing Completely at Random (MCAR) assump- tion (Candès and Recht, 2009; Chatterjee, 2015; Davenport et al., 2014; Zhong et al., 2019), where each Qij is observed with probability independently of all others. The Miss- ing Rand-at setting allows the masking probability of Qıy to depend on the value of Qı itself (Ma and Chen, 2019; Bhattacharya and Chatterjee, 2022; Jedra et al., 2023),
8

---

Optimal Transfer Learning for Missing Not-at-Randomt Matrix Completion
5. Conclusion and Future Work
Mengdi Wang, and Xuezhou Zhang. Provable benefits of representational transfer in reinforcement learning. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 2114-2187. PMLR, 12-15 Jul 2023a. URL
We study transfer learning for a challenging MNAR model of matrix completion. We obtain minimax lower bounds for entrywise estimation of Q in both the active (Theorem 2.2) and passive sampling settings (Theorem 2.12). We give computationally efficient minimax-optimal estimator that uses tensorization of G-optimal designs in the active setting (Theorem 2.6). Further, in the passive setting, we give a rate-optimal estimator under incoherence assumptions (Theorem 2.9). Finally, we experimentally validate our findings on data from gene expression micoarrays and metabolic modeling.
https://proceediing meaiinggsmmrr.. mlr. www.pprssssvv. agarwal23b. html..
Anish Agarwal, Munther Dahleh, Devavrat Shah, and Dennis Shen. Causal matrix completion. In The thirty sixth annual conference on learning theory, pages 3821-3826. PMLR, 2023b.
Future work could consider even more difficult missingness structures, such as when the masks (m:) (1z)}m1 are dependent. If the mask can be partitioned into subsets whose mutual dependencies are small, an Efron-Stein argument (Paulin et al., 2016) may work. Is bounded dependence necessary? Moreover, one can consider other kinds of side information, such as gene-level features in Genome-Wide Association Studies (McGrath et al., 2024). Finally, there can be other interesting nonlinear models for transfer between source and target matrices.
loannis D. Apostolopoulos and Tzani Bessiana. Covid- 19: automatic detection from x-ray images utilizing transfer learning with convolutional neural networks. Physical and Engineering Sciences in Medicine, 43:635 - 640, 2020. URL https: /atpss///app /api.. semant ccchholar. :t:p/CorpusDD:11444
Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. Advances neural information processing systems, 19, 2006.
Impact Statement
Aniruddha Bhargava, Ravi Ganti, and Rob Nowak. Active positive semidefinite matrix completion: Algorithms, theory and applications. In Artificial Intelligence and Statistics, pages 1349-1357. PMLR, 2017.
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Sohom Bhattacharya and Sourav Chatterjee. Matrix comple- tion with data-dependent missingness probabilities. IEEE Transactions on Information (ee00)666110))6662-666 2022.
Acknowledgments
AJ and PS gratefully acknowledge NSF grants 2217069, 2019844, and DMS 2109155. YJ is supported by the Knut and Alice Wallenberg Foundation Postdoctoral Scholarship Program under grant KAW 2022.0366. AM was supported by NSF awards 2217058 and 2133484. SSM was partially supported by an INSPIRE research grant (DST/INSPIRE////0118 8/002193) from the Dept. of Science and Technology, Govt. of India, Start-Up Grant from Indian Statistical Institute, and Prime Minister Farly Career Research Grant (ANRF/ECRG/2244000770)) Anusandhan National Research Foundation, Govt, of India
Tony Cai and Hongming Pu. Transfer learning for non- parametric regression: Non-asymptotic minimax analysis and adaptive procedure. arXiv preprint 2Xiv:2401.12272 2024.
T Tony Cai and Hongji Wei. Transfer learning for nonpara- metric classification: Minimax rate and adaptive classifier. The Annals of Statistics, 49(1), 2021a.
from the
T Tony Cai and Hongji Wei. Transfer learning for nonpara- metric classification: Minimax rate and adaptive classifier. The Annals of Statistics, 19(1),20216
References
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Im- proved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Found Comput Math, 9:717-772, 2009.
Emmanuel Abbe. Community detection and stochastic block models. arXiv preprint arXiv: 1703.10134. 2017.
Emmanuel J Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE trans- actions on information theory, 56(5))2053-2200) 2010.
Alekh Agarwal, Yuda Song, Wen Sun, Kaiwen Wang,

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
Shayok Chakraborty, Jiayu Zhou, Vineeth Balasubramanian, Sethuraman Panchanathan, Ian Davidson, and Jieping Ye. Active matrix completion. In 2013 IEEE 13th international conference on data mining, pages 81-90. IEEE, 2013.
Pierre De Handschutter, Nicolas Gillis, and Xavier Siebert. A survey deep matrix factorizations. Computer Science Review, 42: 42:100423, 2021.
Xiucai Ding and Rong Ma. Kernel spectral joint embeddings for high-dimensional noisy datasets using duo-landmark integral operators. arXiv preprint arXiv:2405. 12317, 2024.
Sourav Chatterjee. Matrix estimation by universal singular value thresholding. The Annals of Statistics, pages 177-214, 2015.
Tal Einav and Brian Cleary. antibody-virus mcasurements across scrological studies. Cell Systems, 13(7):561-577 2022.
Extrapolating missing
Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, and Yuling Yan. Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization. SIAM journal on optimization. 30(4):
Iván Fernández- Hugo Freeman, and Martin Weidner. Low-rank approximations of nonseparable panel models. The Econometrics Journal, 24(2):C40-CT) 2021.
3098-3121, 2020.
Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, al. Spec- tral methods for data science: A statistical perspective.
Yuan Gao, Laurence T Yang, Jing Yang. Dehua Zheng, and Yaliang Zhao. Jointly low-rank tensor completion for estimating missing spatiotemporal values in logistics systems. IEEE Transactions on Industrial Informatics, 19()):114-1822, 2022.
Foundations and Trends@ in Machine Learning, 14(5): 566-806, 2021.
Bjarke Christensen and Jens Nielsen. Metabolic Network Analysis, pages 209-231. Springer Berlin Heidelberg, Berlin, Heidelberg, 2000a. ISBN 978-3-540-48777
Yuqi Gu, Zhongyuan Lyu, and Kaizheng Wang. Adaptive transfer clustering: A unified framework. arXiv preprint arXiv:2410.21263, 2024.
9. doi: 10.1000733-540-47775-33 7. URL https: //doi. wwg/1o..g.1.ooo 1007/3-000000000 48773--877755-
Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential coding theory. 2019.
Bjarke Christensen and Jens Nielsen. Metabolic network analysis: a powerful tool in metabolic engineering. Bioanalysis and Biosensors for Bioprocess Monitoring, pages 209-231, 2000b.
Wenjuan Han, Bo Pang, and Ying Nian Wu. Robust trans- fer learning with pretrained language models through adapters. In Proceedings ofe 59th Annual Meeting the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Pro- cessing ( (Volume 2: Short Papers), pages 854-861, 2021.
Tyler Cody and Peter A. Beling. A systems theory of transfer learning, JEEE Systems Journal, 17(1):26-37,2) 2023, doi: 10.1 10.11090SSSS2222222244555
Allen Hatcher. Algebraic Topology. Cambridge University Press, 2002.
Corinna Cortes, Mehryar Mohri, Michael Riley, and Afshin Rostamizadeh. Sample selection bias correction theory. In International conference algorithmic learning theory, pages 03-53.555 Springer, 2008
Yong He, Zeyu Li, Dong Liu, Kangxiang Qin, and Jiahui Xie. Representational transfer learning for matrix completion. 2024.
urXiv preprint
Koby Crammer, Michael Kearns, and Jennifer Wortman. Learning from multiple sources. Journal of Machine Learning Research, 98), 2008
Roger A Horn and Charles Johnson. Matrix analysis.
Cambridge university press, 2012.
Taishan Hu, Nilesh Chitnis, Dimitri Monos, and Anh Dinh. Next-generation sequencing technologies: An overview. Human Immmmologyy (2011):801-11, 2021.
Sanjoy Dasgupta. Two faces of active learning. Theoreticul computer science, 4177 2011.
Cynthia Huber, Tim Friede, Julia Stingl, and Norbert Benda. Classification of companion diagnosties: work for biomarker-driven patient selection. Therapeutic Innovation & Regulatory Science, pages 1-11,2022
Abhirup Datta, Jacob Fiksel, Agbessi Amouzou, and Scott L Zeger. Regularized bayesian transfer learning for population-level etiological distributions. Biostatistics, 22(4):836-857,22) 202.
frame-
Niels Bruun Ipsen, Fierre-Alexande Mattei, and Jes Frellsen. not-miwae: Deep generative modelling with missing not at random data. In ICLR 2021 1 International Conference on Learning Representations, 2021.
Mark Davenport, Yaniy Plan, Ewout Van Den Berg, and Mary Wootters. 1-bit matrix completion. Information and Inference: Journal the the IMA, 3(3):189- 203, 2014.
10

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
Jafar Jafarov. Survey of matrix completion algorithms. arXiv preprint arXiv:2204.01532 2022. 2022.
Keith Levin, Asad Lodhia, and Elizaveta Levina. Recovering shared structure from multiple networks with unknown edge distributions. Journal of machine learning research, 23(3):1-48, 2022b.
Prateck Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low- rank matrix completion using alternating minimization. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing. pages 665-674, 2013.
Cong Ma, Reese Pathak, and Martin Wainwright. Opti- mally tackling covariate shift in regression. The Annals of Statistics, 51()):338 2023.
nonparametric
Akhil Jalan, Arya Mazumdar, Soumendu Sundar Mukherjee, and Purnamrita Sarkar. Transfer learning for latent variable network models. In The Fiiht Annual Conference on Neural Information Processing Systems, 2024.
Wei Ma and George H Chen. Missing not at random matrix completion: The effectiveness of estimating missingness probabilities under a low nuclear norm assumption. Ad- vances neural information processing systems, 32, 2019.
Yassir Jedra, Sean Mann, Charlotte Park, and Devavrat Shah. Exploiting observation bias to improve matrix completion. arXiv preprint arXiv:2306.04775 2023.
Sean McGrath, Cenhao Zhu, Min Guo, and Rui Duan. Learner: A transfer learning method for low-rank matrix estimation. arXiv preprint arXiv:2412.20605. 2024.
Jack Kiefer and Jacob Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
Behnam Neyshabur, Hanie Sedghi, and Chiyuan Zhang. What is being transferred in transfer learning? In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 512 112-523. Curran Associates, Inc., 2020.
H.E. Kim, A. Cosa-Linan, N. Santhanam, and et al. Transfer learning for medical image classification: literature review. BMC Medical Imaging, 22(1):69,
2022. doi: 10. 200111666188880--220000999333333 URL https: //doi. . org.
Grant P Parnell, Benjamin M Tang, Marek Nalos, Nicola J Armstrong. Stephen J Huang, David R Booth, and Anthony S McLean. Identifying key regulatory genes in the whole blood of septic patients to monitor underlying immune dysfunctions. Shock, (003):66--1744 2013.
Zachary A King, Justin Lu, Andreas Dräger, Philip Miller, Stephen Federowicz, Joshua A Lerman, Ali Ebrahim, Berhard O Palsson, and Nathan E Lewis. Bigg models: A platform for integrating, standardizing and sharing genome-scale models. Nucleic acids research, 44(11): D515-D522, 2016.
Daniel Paulin, Lester Mackey, and Joel A Tropp. Efron-stein inequalities for random matrices. 2016.
Yury Polyanskiy and Yihong Wu. Information theory: From coding to learning. Cambridge university press, 2024.
Meghana Kshirsagar. Combine and conquer: methods for multitask learning in biology and language. PhD thesis, Carnegie Mellon University, 2015.
Friedrich Pukelsheim. Optimal design of experiments. SIAM, 2006.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020a.
Piyush Rai, Avishek Saha, Hal Daumé III, and Suresh Venkatasubramannian. Domain adaptation meets active learning. In Proceedings of the NAACL HLL 2010 Workshop on Active Learning for Natural Language Processing, pages 27-32, 2010.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020b.
Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in rl with generative model. In International conference on machine learning, pages 5662-5670. PMLR, 2020.
Henry WJ Reeve, Timothy Cannings, and Richard J Samworth. Adaptive transfer learning. The Annals of Statisties, 49(6):3618-364) 2021.
James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Mul- tiway spectral partitioning and higher-order cheeger in- equalities. Journal of the ACM (JACM), (1)):1-330, 2014.
Natali Ruchansky, Mark Crovella, and Evimaria Terzi. Ma- trix completion with queries. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 1025-1034, 2015.
Keith Levin, Asad Lodhia, and Elizaveta Levina. Recovering shared structure from multiple networks with unknown edge distributions. The Journal of Machine Learning Research, 23(1):66-133, 2022a.
Mark Rudelson and Roman Vershynin. Hanson- -rrigtt inequality and sub- -aussia concentration. Elec- tronic Communications in Probability, 18(none):

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
9, 2013. doi: 10.1214/ECPv18-2860 URL
Bin Yu. Assouad, fano, and le cam. In Festschrifi for Lucien Le Cam: research papers in probability and stafistics, pages 423-435. Springer, 1997.
https: http://doo.ooooo wtt.loorg/...114//////
v1 8-8-.....
Max Simchowitz, Abhishek Gupta, and Kaiqing Zhang- Tackling combinatorial distribution shift: A matrix com- pletion perspective. In The Thirty Sixth Annual Conference on Learning Theory, pages 3356-3468. PMLR, 2023.
Kai Zhong. Zhao Song, Prateek Jain, and Inderjit Dhillon. Provable non-linear inductive matrix completion. Advances in Neural Information Processing Systems, 32, 2019.
Kirstine Smith. On the standard deviations of adjusted and interpolated values of an observed polynomial function and its constants and the guidance they give towards a proper choice of the distribution of observations. Biometrika, 12(1/2):1 85, 1918.
Doudou Zhou, Tianxi Cai, and Junwei Lu. Multi-source learning via completion of blockwwise overlapping noisy matrices. Journal of Machine Learning Research, 24 (21)):143,202.,
Jerome Taupin, Yassir Jedra, and Alexandre Proutiere. Best policy identification in linear mdps. In 2023 59th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1-8. IEEE, 2023.
Fuzhen Zhuang. Zhiyuan Qi, Keyu Duan, Dongbo Xi, Yongchun Zhu, Hengshu Zhu, Hui Xiong, and Qing He. comprehensive survey on transfer learn- ing. Proceedings of the IEEE, 109:43-76, 2019. URL https://api.. sttppp..eeatiiccccollrr.rrr CorpusID:207847753.
Nilesh Tripuraneni, Michael I. Jordan, and Chi Jin. On the theory of transfer learning: the importance of task diversity. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 97817 173224389
Eric Tzeng, Judy Hoffman, Kate Saenko, and Trevor Darrell. Adversarial discriminative domain adaptation. 2017 IEEE Conference Computer Vision and Pattenn Recognition (CVPR), pages 2962-2971, 2017. URL hwwp::tttps...m //ppi semant Cemanticscoolase CCrpps/DDrpu 4357800.
Alexander HS Vargo and Anna C Gilbert. A rank-based marker selection method for high throughput scrna-seq data. BMC bionffommaats, 21:1-51,2020
Sergio Verdú et al. Generalizing the fano inequality. IEEE Transactions on Information Theory, 40(44::247-1251)
1994.
Roman Vershynin. Iligh-dimensional probability: An introduction with applications in data science, volume 47.
Cambridge university press, 2018.
Binhui Xie, Longhui Yuan, Shuang Li, Chi Harold Liu, Xinjing Cheng, and Guoren Wang. Active learning for domain adaptation: An energy-based approach. In Proceedings of the AAAI conference artificial intelligence, volume 36, pages
2022.
Miao Xu, Rong Jin, and Zhi-Hua Zhou. Speedup matrix completion with side information: Application to lulti-label learning. Advances in neural information processing systems, 26, 2013.
Hao Yan and Keith Levin. Coherence-free entrywise estimation of eigenvectors low-rank signal-plus-nost matrix models. The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
12

---

Optimal Transfer Learning for Missing Ron-at- Matrix Completion
A. Proofs and Additional Results
A.I. Preliminaries
We will repeatedly make use of the vectorization operator.
Definition A.1 (Vectorization). For X E Rn the vectorization vec(X) E Rnd the vector whose first n entries correspond the first column of X, and next n entries correspond the second column of X, and so on.
We vectorize matrix products follows.
Lemma A.2 ((Horn and Johnson, 2012)). Let A, be matrices of shapes such that AX is well-defined. Then:
Pec(AXB)=(B3' (b=)))))))))))(x(( (A).
A.2. From Entrywise Guarantees SSR
We prove that Assumption 2.5 follows from entrywise estimation guarantees on the source. Proposition A.3. Let P an n matrix of rank r. Let E> and P be rank-r estimate of P. satisfying
P
Pllmas Se||
(9)
Consider the SVDs P P-UEV and P-USVT
Then, it holds that
||U -
min WeOrx-
(2/ v2) mmnl 12-000)|| Pllmax
(r(P)
min WEO
V--W 12-000000
12-000
(2+ mn VV 12
max
(P)
provided that /mnee| max <
(P(
Below, we give result showing that entry-wise guarantees imply subspace recovery in the two-to-infinity guarantee.
Proof. We will only prove the result concerning the left subspaces U and Ü. Our first step is relate the errors ÜR-U U and UUTÜ-E U. We will introduce in our computations the sign matrix? of RTUT Ü, namely sgn(U Ú) which is rotation matrix. We have
|UW $ |Ussnn(U Ū) -0 1|2
min WeD
< <I Ū)- 2-+00 12 U Ul)
Moreover, we also know (e.g., Lemma 4.15 (Chen 2021)) that
U-gn(nn U) [l)ln(
and using the Theorem Davis- Kahan we obtain
V2IIM- -M Mlop or(M)
(gn
Thus, we conclude that
/ 2- M -MIlog
min Weo
JWW (UW-012--0 < |U (U(
-00
(10)
(,(M)
"The sign matrix n x matrix with SVDU2EZZ is given by -x
13

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
Next, we show that minw |UW -VV-0]1 -Ü can be well controlled by the error M M-M. M.. On the one hand, we have triangular inequality, and noting that UU M and θ M
M that
IIUU ((UT-00T))
M 2- 2
|0U M M-00 M +1IUU (M-M)ll2
112-00 $ | - M 2- + 11 - MMpap
On the other hand, we have
I1U0 2- -100))00))) 1/20000
= =KKU(110)-0)310-0
> -10
2 -012- (M) -|U((U -I)((U)))- 112 MMMMII MM llpp o,
where in the last incquality we used Weyl's inequality: (M) or (M) S IIM M to obtain
MMM-MMMM -M lop. We combine the above inequalities
|M JM-M
LU 12 M MMppp O)(UTT)) M- M lap
10(0-0))0012-00
(,(M)
If the following condition holds
(r(MM
JM-MM]a 1lpp S wmmmmMMM M- -M max S
2
then
| -00
[ -MM-Mpp + 12u00l2 MMMMI|MMMMMM
MM lop
M
1
T 00-0011 -11
(M)
which in turn gives
M M 2 00 + +21
1|2 MMM|laa
-
(11)
(r(M)
In summary we conclude that
2 M .o +(2 v2) 12 MM M-M |
NUW-Ülea < W
min
(12)
(M
Using the inequalities
M M 122- S SV -MMMMMMM IImax
and [ M 1lop S ////| Mmn|MMM Imaxx
we can express our bounds as
(2 mn IUU ) -MM max (r(M)
min Wedrx.
|UW-
(13)
simple calculation also gives the following.
Proposition A.4. Suppose Ù Omxr satisfies Assumption 2.5 with bound ESSR, and the population incoherence is ny m m Then Ú is yn-ncooherentt for S 2py 2r2
14

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
A.3. Proof of Proposition 2.1
We require the following special case of Hoeffding's inequality.
i.i.d Lemma A.S. Let X1 Xn ~ Bernoull(p). Then:
logn
X
p
S 2n
n
The following concentration is standard.
Lemma A.6. Let S" Then:
logn
P|| 00 201
- 10100n111/)
Proof. By Hoeffding's 's inequality,
2/2
P
Σ X;
up
21
S
2exp
7
Let t= nlogn. The conclusion follows.
Finally, we require the following version of the Hanson- Mrisont inequality.
Theorem A.7 (Rudeelson and Vershynin, 2013) Theorem 2.1). Let A e g be fixed and E R random vector with i..dd mean zero entries with variance 1 and | llv < K for all i. Then there exists constant c such that any t 0,
el2
<2exp
We are ready to state our lower bound.
Proof of Proposition 2.1. Let ii.... Ud E R. be generated with iid (0, 1 entries and Ui,... E R be generated with iid (O, 4 entries. Let Q Σ - u.
We first analyze the incoherence of Q. We analyze the left- cef--incoheeence Fix E [m] and let y (UTe:). Then we apply Theorem A.7 with æ vmn and A= V. to obtain that || = <*
with probability 21-n 10 for absolute constant C" > 0. Since x has iid ((,1 entries, the Orlicz norm constant is at most 2. Taking
a union bound over all i, it follows that: IIVMVU
logn 2 11-O(nn1
It follows that the left incoherence is at most (loggn with high probability. An identical application of Theorem A.7 with A = U implies that the right-ine iethtinncoherence is at most (loggm). Let E' be the event that Q is Ollo((nVm) incoherent. Let
Q be the random matrix generated as above, conditioned on E'. Note that [PE" 2 o(1)
Next, let / [m],J/ [n] be the rows and columns of that are seen in Q. Then by Lemma A.5, //| < + /mlogmand 0.99 with probability 2 1 1-2n 2m -2 Let E be the event that the bounds on I and J both hold.
J. None the entries of Q in the htth row or gth column are seen. Therefore, since m - 1 3(m) and n- |/| 2 (m)), and since PP(E"]= > o(1, there exists constant C' such that for all E [d]. Var(u, ()) 2 C.
Consider E [m]] /
Therefore, since u t Ui... are independent, for any Q, have: - 2 (ar(Que
Var
Cd
15

---

Optimal Transfer Learning for Missing Not-t-nRoon Matrix Completion
-Q- Therefore, if we condition &, then [Im][/]2 ((m) and |n] m.
cd for constant
Since 1 22n 2m 2 conclude that:
QQ-Q1
2
1
1
11-
mmn
mm
cd
2
A.4. Proof Theorem 2.2
We require a version Fano's 's theorem given in Theorem (Verdú et al., 1994).
Theorem A.8 (Generalized Fano). Let P a family of probability measures, (D,d) a metric space, and P +D D a map that extracts the parameters of interest. Let'L CP be a finite subset of size M. Suppose >> is such for any distinct H,,Hy E H.
d(O(H.).(H,))) 2a.
And, suppose that 3 >> 0 is such that:
M M
log2+ M
ΣΣ
Then,
inf sup ([((0(P)0)22((1-3 0 PEP
We also require standard expression for the KL divergence of a pair of multivariate Gaussians. Lemma A.9. Let p.p' E Id be distinct and covariance given as:
The KL divergence of two multivariate Gaussians sharing the same
(T.N(
'
We now prove our lower bound.
of Theorem 2.2. Let U Rmxd V E Raa be such that U, and Vμ for E [d], and all other entries are zero. Let P-UVT, We construct hypothesis space H ((()))
( (()) :ij E [d] of size d2 where p(i) (((()) =m as follows. For all members ij, set p(i)) = Next, let R(V) = ye,e, for to be specified later. se ((t) = =UR
First, notice for any (r,s) (i.j) that:
(((s) m =72
Next, consider the KL divergences between pair of hypotheses. Let (P(t), Q(i1) be the distribution of the data under hypothesis (p(U)) (Qi)). ). Since p(() = p(() P for all (i.j), we must simply bound (L()(t) ((rs)) for each pair (ij.rs). Now, let R TT
(1) (6i) be the row and column sampling distributions (possibly deterministic) respectively, based on
the source data ((()) Since p(o) p(ú) for all (i.j) we know that there is a pair of distributions TR.TC such that (19) Rt
- (i)) नC for all (i.j). In other words the sampling cannot depend on the hypothesis index (i.j).
Next, we analyze K ((())) ())))) Each distribution depends on the randomness TR as well as the Gaussian noise. Let R.C' be the random multisets of rows and columns generated by n according to the prescribed row/column budgets. By the chain rule for KL divergences (Theorem 2.15 of (Polyanskiy and Wu, 2024)), we have:
(L(()) ((()))))(()))))
KL R.C
16

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
((1) (i8) Note that the marginal term involving " = versus " = zero, because the distributions are equal for ij.rs.
(ra) (rs)
Next, for E [m], v E [n], let naw R, C) be the number of times that (u, v) is sampled in R. C. Notice that ER,c(n [R, (00 So, by Lemma A.9,
Nuv (R,C)
E KL (,00), R.C
-(rr))
E
uv
(mi (R,C) +u (RC)))
E
2
+
Hence, the average KL divergence for all pairs is:
1 E E -()))) d (w)EldPasss)
Σ
Σ (ma())))())+++)()m)))))
oz
(1
Σ (L+dMn(((Tc(i)
o% d4
7 1
22t
0 d4
2 2 [
ogd d2
_et og [2]
og.e
By Theorem A.8, we conclude that for d 2, the minimax rate of estimation is least -----
100 [
A.5. Proof of Proposition 2.4
We use the classical characterization of G-optimal designs due to Kiefer and Wolfowitz.
Theorem A.10 (Kiiffer and Wolfowitz, 1960)). Let v be a distribution on a fiite space A ARd, The following are equivalent:
π is G-optimal.
[(x)==() -d.
For
x maximizes logdet V (T).
We now prove the tensorization of G-optimal designs.
Proposition A.11 (Restatement of Proposition 2.4), Let p be a G-optimal design for (0fe;:i [m]] and be G-optimal
design for (vee, : E [n]}. Let (i.,)) =(()((s) be a distribution on [m] x [n]. Then v is G-optimal design (V Wyee, : [m]].
17

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
Proof. Let L [n]. Then by the Kiefer-Wolfowine theorem,
m
(Vee)
(EcoVVeee & (EN(TBe)TT) (BBe00Fe)) (Vpe (
max
(Vi,, )" (=<OV)ee)))) (
@ " (77
max ()
(V)e,)) Σ [ -max
(Ve))(()es)" (E(()Beeef(t)) (UBes)
(C(o)o(()
dd?
Where the last step follows from G-optimality of p and Ç. By Theorem A.10, x is G-optimal.
A.6. Proof of Theorem 2.6
We first prove useful error decomposition.
Proposition A.12 (Decomposition), Let tr Omxd Ono be the estimates of the left/right singular vectors of P. Then there exist matrices Wv, Wr (d, such that if T2 are the distribution shift matrices as in Definition 1.2, and if = (=(WTT))R(T Wy), then:
Wv) +E
Where the E-error depends on the estimator error of P.
F:= UU= +H0-0--wWW--NNHHH-000-----------
Proof. Let E Raxd be the distributional shift matrices from Definition 1.2 such that VpT..
Let Wy be the solution to the Procrustes problem:
Wy arg inf weodxa
And similarly,
Wy = arg inf Weodx VPW- -WWl-ll2--s
Next, let Z = and M- W ZWy. Further, let A -p and Dy -Vp-vpVppp Then, can write as:
Q= Q=UPTIR(VPT2))
=UTZVZ
=U
-UUD+AOWE2WW((V--AN"
-ÜPMVT+E
Where E contains the cross-terms:
B-AoMV7 -
So we are done.
18

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
We require strong form of matrix concentration due (Taupin 2023).
Lemma A.13 (Design Matrix Concentration). Let be an e-approximate G-optimal design on a finite set A C R.. Let p. 0 and t 2 2(1(+c) + 3p )dlog(())) ( Suppose ! a.. is the multiset of samples drawn i..d. from n, and ler W.- ==== Then;
P ( p) E aala)aa" :W: Σ acA
aaa)aa" 21-6
aEA
In particular, since à is c-approximately G-optimal,
d
|aal 5 (1+e]d
P
max dEA
21-8
(1+p)
(1 p)
We also require the following standard bound the maximum of Gaussians.
Lemma A.14 ((Vershynin, 2018) 2.5.10). Let XX, Lid N(0.0²). Then for all u 0,
u²
PlmaxX? log)n))))) S sexp(
20
Proof Theurem 2.6. We first introduce some notation. Let Sy,SS, be the multisets of rows/columns sampled and - S.. Let 1b, = V e, and sp; ÜU... Then, let d.s = V
@bpe; "
wb @ Pk. and W Eisenn Notice that:
W Σ
Σ spipp? VES.
jES.
Therefore, let W1 Eyes, o and W2 = Eies, PppT for shorthand. Then W-1 1 exists iff WT! .W2' exist. By Lemma A.13, both WT WW, exist with probability at least 1 (m++ since S,,S, are both large enough by assumption.
Therefore, conditioning on the inverses existing, if we solve the least-squares system, we obtain M e dxd such that:
vec(M
Σ
JEE
Recall from Proposition A.12 that Q where Eig -ei the misspecification error. Therefore, we bound the error of Q- as:
Qu - Qi -PM
(M-M)++ -M +ey
Fiji+ Fezii
E := 87/ veol MM)
E2
19

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
Let Gij A (0,,00) be the additive noise for Qiz. Then, Qis = 0 vec +Gy. Hence we can write En as:
E
okel
T
Pijoi
87
-1
37 vec((M
tEE
SEEn
Pke
Pij P1) 1
Σ
bi (M) + (co)
the vec
yEE
Di (5g (Ex++Giss))
sjen
-T.
Σ
+
( )
" Gis
HE
ijER
ieE
Fogke+ Paske
We analyze F. first. Let = Lijen Φi, Gij- For any k,E, we wish to bound o.... Notice that a multivariate Gaussian with mean O. Its covariance therefore:
Faw 1
ΣΣ W-1 b. W " E -1
SEEREER
tjEn
Hence 2 is scalar Gaussian with mean zero and variance - that we can tensorize the quadratic form as:
We next bound this quadratic form. Notice W- -d w-
We apply Lemma A.13 each term in the product. With probability 1 2(m + n)- 2, for Sr both of size least 20dlog( 2d m4n).
(2+
1 - | 1pxll w,-
|S
Conditioning this event, the variance of de w is at most
(1+e)d
[ for [0|=|S+|[SAA Therefore, by Lemma A. 14,
(2+2c)o d2
P
max kE(m],(E(m)
< 20log(mm)
< 8 (mn)
[2
Finally, we analyze the error term Es.te. By the Cauchy- wwwwazz
E3juel S
( 1/2
Σ 2/21/2
NER
Den
20

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
First,
Σdi-
-ah=> Σ SoWWWLL
8 Pij
S
VE
iE
Σ
1 W
ijen
= tr
Σ
27
W
S
Ijen
S W w-1)
(2+
[
For the other term,
23 1/2
$ 1/2
max Etj 'e
It follows that E 2e- Je-dmax..enne)) The conclusion follows.
A.7. Proof of Theorem 2.9
We require the following concentration result to control the sizes of masks.
Lemma A.15 (Bernoulli Concentration). Let XI,..,,, did
Bernoulily) (0,1). Then ip 10logn,
P Σ (X, pp) p)
2 np
In ww1)
2
Proof. By the scalar Bernstein inequality (Lemma A.16), we have for B= and Ç n=
np that:
72/2
[P
Σ (X; - p)
2 5 2expl
(BTT//3)
Let ==p/=2 Then
=expe -10
P
Σ (Xi-P)
logn)
2n (/4
We are ready to prove the estimation error for passive sampling.
2.9. Following the notation of the proof of Theorem 2.6, want to bound E3 and F. However, rather than using G-optimality to bound quadratic forms of the type oue W 1 we will apply spectral concentration via Proposition A.17.
21

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
To this end, condition on the events that V > Pize: and Uf Pau By Proposition A.4 and Proposition A.17, 2
2
the events occur simultaneously with probability 2 1 1- 2-m22)mmmm)- -10, Then W-1 exists and W-1 for all k, by incoherence,
T. Therefore,
Prum Poa
Oke W 215
4
@
PRoW PCol
4
140% |
PRowPCol
4
m²n2
PRowPCol
4
pdl
PRow PCol mi
Hence, by Lemma 1.14
4
udd2
Easkel 2 2201og( 20log(mn))0
I (0mAA))-1+(mm
max [ [m()
PColPCol mn
Next, we analyze E3. Let Ozy= = = W P.j. Letp=q=2. By the Cauchy-Schward Schwarh inequality, ineuuaaay
EEskel S
Σ
a4 2/p
+1 1/
ijen
KE
First, we have:
Σ
2
Σ
1T
W W-1 P/.
tEE
IEE
Σ
Pig P13
W 11 Pre W-1
ier
=tr
Σ
Φ T W (eeebeeW-
IyE
ke W-1
tr
W @nd
4qd
PRowPCol
On the other hand,
1/2
< /1/22/2
max eaj ien
eE
Notice E[[[]] - PCC. By Lemma A.15, with probability > 11-4 1114(mAn)-aa) w(1)
S 4 PROw PC
Therefore, with probability 21 1114(mAn)-2
3
1
PRow MM
2
The conclusion follows.
22

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
A.8. Proof of Proposition 2.11
We require the following version of the Matrix Bernstein Inequality (Chen al., 2021).
Lemma A.16 (Matrix Bernstein Inequality). Suppose that {Y; = L......n m are independent mean-zero random matrices of size di d2, such that |Yil[2 S B almost surely for all i, and Ç max(
Then,
72/2
P
Y F=
2T
(d1
CTBB/3
We now prove nondegeneracy of masks with high probability. Proposition A.17 (Spectral Concentration), Suppose that Vp and Up are jAv -t--cohinno respectively, Let LerTI (0,1) be the random matrix with diagonal entries V/...,y and similarly let 11 E {0,1) jmmm have diagonal entries Tmm Then, assuming that jvv S 100dlogn
Pea" and Jay S
Phan
have:
100dlogn'
P(ÜT1IAÜp== ž PROW
/ / 1
Pp
Proof.
Suppose that Vp has rows y/.....y ERd. Then,
n Vr v..."
Poot for shorthand. Notice Let 0; = /ryi. Let Pcul - =[vs]. We use Pcot Therefore,
=la, since VTV, - Ia.
Euviof ppld = I (v=- p)d
Let - (x:)))))) Note that [[ Next, let uy= By incoherence, ||Y:|l2 1 Sdd for all i. Further,
max [
Y |1 Σ
Yill =
||E| -||||
Y22112
=p(1 (((1-))] p) > 10,111 1,
<p(1 p) p)mpdl
y. l12
=p(1 121--p1- p) p)dd
Thus, by Lemma A.16, for B = pud and (o01-p)mpdd, we have:
27 < 2ncxp - 72/2
Y
BBTB/3
Setting 7=
implies that:
Eu.uoT =m 21-n
IP
S. yn
wuddlgg then pm Pcol n/2. We conclude that 111011 An identical argument gives PCol
P(UTNnuP = PROW /2 2 1 m 110
23

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
Corollary A.18. Under the ussumptions of Proposition A.17, the design matrix for passive sampling has rank de with probability least 1 - 22mmAn)-10
Proof. Let [m]] x [n]] be the set indices corresponding to the observed entries of Q. Let Po E {0,1312/xmm be the coordinate projection. The design matrix is precisely Pu(Vp&Up). Then, notice that:
= [[ = =VA
By Proposition A.17, this matrix has rank at least d' with probability 21 21-2(mAn)
A.9. Proof of Theorem 2.12
We require the the Gilbert- Varshamov code (Guruswami et al., 2019).
Theorem A.19 (Gilbert- Varbbrt-Varshhmoy). Let be a prime power: For 0 <<E< 2=1 there exists an e-balanced code C' C. 17 with rate ())
We will use the following version of Fano's inequality.
Theorem A.20 (Generalized Fano Method, (Yu, 1997)). Let P a family of probability meusures, (D pseudo-metric space, and ::P >DD a map that extracts the parameters of interest. For a distinguished P PEP, let be the data and 0:= be an estimator for (P)).
Letr 2 and P, C.P be a finite hypothesis class of size Let a,,, be such that for all i and all E.
((O(P.).0(P))))
Then
maxlE (0(((x))0(()))) jE(r)
0r 1
Br + log2
logr
We can now prove Theorem 2.12.
Proof Theorem 2. 12. Let CC (0,1) be the 0.1-baladced Gilbert-Varshman code in Theorem A. Let Let U,V e Rxa be Stiefel matrices with incoherence parameter == O(1). Let P=UEpV' for diagonal Ep > 0 to be specified later. Let 5q > 0 be a positive real to be specified later.
We will construct family of source/target pairs indexed by similar (Jalan al., 2024). For w E.C, let B E dRdx be defined
V mm
Wii = 0
B Bwijj" =
2d
v +ōQ) Wij =1
d
Then define (P..Qu.):PPUUBB..
For a fixed w E C, the distribution of the data (Ar, Q) depends on the random noise and masking of both Ap, Q. Let DR E [0,1) and De E {0, [0,1)axn be the diagonal matrices corresponding to the row/column masks for Q, and let Ge Rmxx have iid (0,02)) entries. Then DDD
Now, will apply Theorem A.20 to lower bound E
IQ Qw Dc Fix any DR supp(E:), e supp(E2.
Let Pu.Quu denote the distribution the data when the population matrices are Pw: Qu and we condition on the Q- Q-makk matrices Dc.
24

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
By Theorem 19 the hypothesis space indexed by C' such that log(C))) C1d dl for absolute constant C > 0. Next, for distinct w.w. ECC,
SKI(QuI
= (L((DesDaNN((CHHH))))0))0))a
Notice that we do any properties of Pau Pa' w', and in particular allow for deterministic Pu. Pw =P.
Since DD,DR are fixed, this is simply the KL divergence of two multiariate Gaussians with the same covariance but different means. Therefore, by Lemma A.9, we have that:
vec(Qu "oBaD
1
DR(Qu0 Qw: Delli
ΦQ
[B - Bw ) Dell.
|R DcV - B 11?
5prow PCol
mn
)d
4 d2
SprowPcatnnn
In the penultimate step, we used the fact that DR Du Eupp((E)))
Next, for any distinct w.w' E C, by Theorem A.19 we have that Pi.je(d] (wis w 0.11. 0.1. Therefore,
11Q - Qw 11 = =Iu(B -B V
= 11B - -Bu )|F
8 mn 1/2
2 SQ vm
10
In the notation of Theorem A.20, we have:
0 dQ V mn
B, Poakoo
Since log((CT) 2 CidZ, we set 0q constants C,,
Cid0og
Poamm so that that
8, C
Therefore, by Theorem A.20, for absolute
C2a
min
E
11 Qw
Do
D
mn
mn
Cg02
Cad oz PRowPCollTir
The conclusion follows.
25

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
B. Additional Experiments and Details
Compute environment. We run all experiments on a Linux machine with 378GB of CPU/RAM. The total compute time across all results in the paper was less than hours.
Dataset details. For the gene expression experiments, we gather whole-blood sepsis gene expression data sampled by (Par- nell et al., 2013), available at ht https: /www. ncbi nnm. nih. gwv.goo///eeeeeeeee yyeo/query query aacc. ogi Pacc=gse5 2ess555544 4. We take the intersection of rows and columns present days and 2 of the study, and then filter by the 300 most expressed columns (genes) on day 1, to obtain P.Q E R31x300 Here Pij is the expression level of gene for patient i on day 1, and Qij is the same on day 2.
For the metabolic networks experiments, we access the BiGG genome-scale metabolic models datasets (King et al., 2016) at http: /bwgg. ucsd. edu. We use the same set of shared metabolites for IWFL.1322 (the source species P) and IJN 1463 (the target species Q) (Jalan et al., 2024). The resulting networks are weighted undirected graphs with adjacency matrices P.Q 225 x251 where P. counts the number of co-occurrences of metabolites i.j in iWFL1372, and Qip does the same for IJN1463.
Details of the baselines. For the method of (Bhattacharya and Chatterjee, 2022), we use the estimator from their Section 2.2, but modify step (3) to truncate to the true rank d, and in step (6) truncate to the true rank of the propensity matrix whose (i.j) entry is mJ.y.. The propensity rank is always in our case. This the estimator QBC22 E m"
For the method of (Levin et al., 2022b), we use the estimator from their Section 3.3, with weights wp based on estimated bub-gamma parameters of the noise for P.Q. Then, let Q'' E 1.m X be:
Ps +
Qs
2u
0/j =
up+we Poj
up uptwQ
otherwise
We return the rank-d SVD truncation of Q' as QULLZZ ER
We will discuss additional ablation experiments in Section B.2, and experiments on the real-world data in Section B.3.
B.1. Comparison to the not-MIWAE Method
In this section, we present additional experiments to compare our methods against the not-M/WAE method of (Ipsen et al., 2021). Specifically, we compare our active and passive sampling methods on Max Squared Error, Mean Squared Error (MSE), Mcan Absolute Error (MAE), and Root Mean Squared Error (RMSE). For ease of comparison, we report the results of Figure (gene expression transfer) and Figure (metabolic transfer) again the tables below. The MAE/RMSE numbers, and the results of the not-M/WAE method, are new.
For the gene expression transfer problem (Figure 2), methods out- nut--perfommao now-M with PRow Pcol =0.5. We train not-M/WAE until convergence, with the latent dimension equal to the true matrix rank of Q, and batch size of 32. For gene expression data, the errors are reported in in Table 3 below.
Method
MSE
Max Squared Error
MAE
RMSE
Passive (Ours)
0.004385
0.300035
0.044493
0.055198
Active (Ours)
0.018225
0.372105
0.103285
0.114654
LLL22
0.151792
0.626293
0.343497
0.389449
BC22
0.570254
1.000000
0.678862
0.754897
MOt-MIWAE
0.207850
1.000000
0.415913
0.455765
Table 3, Performance comparison different methods setting Figure with Prow -cw 0.5.
Next, we perform the same experiment for the metabolic transfer problem (Figure 3) in Table 4.
Note that our methods may perform better because not-MIWAE is a non transfer baseline. This further emphasizes the significance of the transfer setting, which our methods capture, as well the method of (Levin et al., 2022a).
26

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
Method
MSE
Max Squared Error
MAE
RMSE
Passive (Ours)
0.000217
1.292995
0.000934
0.014638
Active (Ours)
0.000024
0.294249
0.000669
0.004883
LLL22
0.000360
0.651176
0.006931
0.018147
BC22
0.003790
1.000000
0.021086
0.055543
not-MIWAE
0.006666
1.000000
0.030307
0.076831
Table 4. Performance comparison of different methods in the setting of Figure with PRow = pca =.5.
B.2. Ablation Studies
Throughout this section we use the Partitioned Matrix Model with a= 0. 1.11bb=0, 0.8 from Section For each setting, we hold all parameters fixed and vary one parameter pto observe the effect of all algorithms on both Max Sqaured Error and Mean Squared Error. The default settings are:
Matrices
PRQmmmx mx with m = 200.
The parameters 0.8,6=..11 in the Partitioned Matrix Model.
Additive noise for @ (V0.o3) with oq =01..
The rank is d=5.
PRow = PCol 0.5, the probability of seeing any entry of Q is 0.25.
For all experiments, we test for 10 independent trials at each parameter setting and display the median error of each method, along with the [10,90] percentile.
Figure shows that all methods do poorly in max error when is masked. Our methods are best mean-squares error. This is because the Matrix Partition Model is highly coherent, be shown from spectral partitioning arguments (Lee et al., 2014). Therefore, the max-squared error is high, would expect from Remark 2.7 and the results of (Chen et al., 2020).
LLL22
BC22
Passive (Ours)
Active (Ours)
10a1
10
Squared
Squared
10a2
10-3
10
10a4
10
10a
do
do
Figure test effect of growing the target additive noise parameter aq.
27

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
LLL22
BC22
Passive (Ours)
Active (Ours)
-0
Squared Eror
Mean Squared
10
6 10
4 10
4 10
1x-2
0.10
0.15
0.20
0.25
0.30
0.35
0.40
0.45
0.50
0.10
0.15
0.20
0.25
0.30
0.35
0.40
0.45
0.50
Op
dp
Figure We test the effect of growing the target additive noise parameter p. Each entry of P observed with i.idd additive noise noise (0,o.))
LLL.2
BC:22
Passive
Active (Ours)
10
10-2
10
10-3
10-9
1
1
10a4
100
150
200
300
400
100
150
200
250
300
350
Figure 7. We test the effect of growing n for P.Q E 300
B.3. Additional Real-World Experiments
We first display the weighted adjacency matrices for P,Q for the metabolic networks setting of Section 3 as Figure 10 and Figure 11. It evident that the edge weights show significant skew. Note that the colorbar for both visualizations is logarithmically scaled.
Next, we report mean-squie -quared error for the same experimental settings discussed in Section 3. Figure 13 shows the results for gene expression. Figure 12 shows the results for metabolic data; notably, despite poor performance in max-squared error, the passive sampling estimator is reasonably good in equared error, although not good as the active sampling estimator.
28

---

Optimal Transfer Learning for Missing Non-oo- Matrix Completion
LLL22
BC22
Passive (Ours)
Active (Ours)
10a4
10-1
10"2
Squared
10a2
10
10a4
10"4
1
Matrix Rank
Matrix Rank
Figure 8. We effect rank.
BC22
Passive (Ours)
Active (Ours)
10a
10-1
Mean Squared Error
Max Squared Error
10-2
10-3
8 10
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Prob. seeing entry
Prob. seeing entry
Figure We test the effect masking entries of P in Missing Completely-att Ran-ooo setup with probability p. Note that the emrrs for active and passive sampling are almost identical, so we use different markers (circle and triangle resp.) to distinguish them. We see that methods do better in squared error (left) while is poor for all methods (right).
29

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
Weighted Metabolic Network of E. Coli W
13
26
102
39
52
65
10
78
91
104
100
117
130
143
156
10
169
182
195
10-2
208
8
221
234
247
0
12
24
36
48
60
72
84
96
108
120
132
144
156
168
180
192
204
216
228
240
Figure 10.
The matrix in the setting of Figure
30

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
Weighted Metabolic Network of P. putida KT2440
13
26
102
39
SALI
52
65
101
78
91
104
117
100
130
143
156
10-1
169
182
195
10-2
208
221
234
247
0
12
12
24
36
48
60
72
84
96
108
120
132
144
156
168
180
192
204
216
228
240
Figure 11. The target matrix Q in the setting of Figure 3.
31

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
LLL22
BC22
Passive (Ours)
Active (Ours)
Metabolic Network Transfer
10-2
Mean Squared Error
10-3
10-4
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
Prob. of seeing entry in Q
Figure 12. The mean-squared error of each Q Q the setting of Figure 3.
32

---

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
LLL22
BC22
Passive (Ours)
Active (Ours)
Gene Expression Transfer
100
Mean Squared Error
10-1
10-2
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
Prob. of seeing entry in Q
Figure 13. The mean-squared error of each Q Q the setting of Figure
33


Reviews:
[{"review_id": "ZeNCeFhIK0", "reviewer": "Reviewer_XH4Z", "summary": "The authors study matrix completion in the MNAR setting under transfer learning. They establish minimax bounds for entry-wise estimation of target values under both active and passive sampling settings. Additionally, they propose a computationally efficient minimax-optimal estimator—leveraging the tensorization of G-optimal designs for active sampling—and a rate-optimal estimator for passive sampling. Experiments on two simulated datasets and two real-world datasets demonstrate the effectiveness of their method compared to two baseline approaches.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback, and for highlighting that our paper is well written and presents a sound theoretical framework. We address their comments below. \n\n## The manuscript contains results for a non-transfer MNAR baseline (BC22).\n\nThe method of BC22 (IEEE Transactions on Information Theory, 2022) is an MNAR imputation method (lines 302-305, left). The manuscript includes this method for all experiments. \n\n## Our methods outperform not-MIWAE on MAE, RMSE, MSE, and Max Error. \n\nAs the Reviewer suggests, we perform new experiments to compare our methods against the not-MIWAE method of Ipsen et al. 2020. Below, we present the comparison of our active and passive sampling methods on Max Squared Error, Mean Squared Error (MSE), Mean Absolute Error (MAE), and Root Mean Squared Error (RMSE). For ease of comparison, we report the results of Fig. 2 (gene expression transfer) and Fig. 3 (metabolic transfer) again in the tables below. The MAE/RMSE numbers, and the results of not-MIWAE, are new. \n\nFor the gene expression transfer problem (Figure 2), our methods out-perform not-MIWAE with $p_{\\textup{Row}} = p_{\\textup{Col}} = 0.5$. We train not-MIWAE until convergence, with the latent dimension equal to the true matrix rank of $Q$, and a batch size of 32. \nFor gene expression data, the errors are: \n| Method | MSE | Max Squared Error | MAE | RMSE |\n|--------|-------|-----------|-----|------|\n| Passive (Ours) | **0.004385** | **0.300035** | **0.044493** | **0.055198** |\n| Active (Ours) | *0.018225* | *0.372105* | *0.103285* | *0.114654* |\n| LLL22 | 0.151792 | 0.626293 | 0.343497 | 0.389449 |\n| BC22 | 0.570254 | 1.000000 | 0.678862 | 0.754897 |\n| not-MIWAE | 0.207850 | 1.000000 | 0.415913 | 0.455765 |\n\nNext, we perform the same experiment for the metabolic transfer problem (Figure 3). \n| Method | MSE | Max Squared Error | MAE | RMSE |\n|--------|-------|-----------|-----|------|\n| Passive (Ours) | *0.000217* | 1.292995 | *0.000934* | *0.014638* |\n| Active (Ours) | **0.000024** | **0.294249** | **0.000669** | **0.004883** |\n| LLL22 | 0.000360 | *0.651176* | 0.006931 | 0.018147 |\n| BC22 | 0.003790 | 1.000000 | 0.021086 | 0.055543 |\n| not-MIWAE | 0.006666 | 1.000000 | 0.030307 | 0.076841 |\n\nAs Reviewer XH4Z suggests, our methods may perform better because not-MIWAE is a non-transfer baseline. This further emphasizes the significance of the transfer setting, which our methods capture, as well as the method of LLL22. \n\nWe will include both the suggested baseline (not-MIWAE), and the suggested error metrics (MAE and RMSE) in the revision. \n\n## Our methods out-perform others under new evaluation metrics (MAE and RMSE). \n\nSee the above table. We will include these new metrics in the revision to give a more comprehensive assessment of model performance.\n\nAs the reviewer correctly notes, our main focus is on Max Squared Error, which is a commonly used evaluation metric due to its sensitivity to extreme deviations; this is biologically significant.", "claims_and_evidence": "The theoretical results are well established and proved.", "methods_and_evaluation_criteria": "The paper reports Mean Squared Error (MSE) for tasks involving gene expression microarrays and metabolic modeling. Max Squared Error (MSE_max) might be commonly used in these domains due to its sensitivity to extreme deviations, which can be biologically significant. It might be helpful for the authors to adopt other evaluation metrics (e.g., Mean Absolute Error (MAE), and Root Mean Squared Error (RMSE) ) for a more comprehensive assessment of model performance.", "theoretical_claims": "Yes, I mainly check the theorem mentioned in the main paper.", "experimental_designs_or_analyses": "In the experimental design, it would be valuable to include results for a non-transfer setting. Specifically, evaluating state-of-the-art imputation methods when trained solely on Q would provide a useful baseline. If the proposed method outperforms these non-transfer baselines, it would further highlight the significance of studying the transfer setting and demonstrate its practical advantages. I encourage the authors to consider this comparison to strengthen their empirical evaluation.", "relation_to_broader_scientific_literature": "I think this paper help to establish the theoretical and practical approach for matrix complete under transfer setting.", "essential_references_not_discussed": "I think it would the best if the author discuss more about missing data imputation method under MNAR in the literature.", "other_strengths_and_weaknesses": "Strengths: The paper is well written and presents a sound theoretical framework.\nWeaknesses: The baseline methods in the experimental section are somewhat limited. While I acknowledge that few methods specifically address matrix completion in the transfer setting, it would be beneficial to incorporate baseline methods from the MNAR imputation literature—such as not-MIWAE [1]—to establish a stronger point of comparison. Evaluating these methods using only data from Q would help demonstrate the best possible performance without transfer, thereby further emphasizing the significance of the transfer setting.\n\n[1] Ipsen, N.B., Mattei, P., & Frellsen, J. (2020). not-MIWAE: Deep Generative Modelling with Missing not at Random Data. ArXiv, abs/2006.12871.", "other_comments_or_suggestions": "None", "questions_for_authors": "Refer to Experimental Designs Or Analyses about the evaluation criterion.", "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": "gMDl13VoHu", "reviewer": "Reviewer_hEy4", "summary": "This paper studies a problem in which there are two matrices $P$ and $Q$ of the same dimension, where a noisy version of $P$ is observed and a noisy and partial view of $Q$ is observed. $P$ is known to be low-rank, and the two matrices are related via distribution shift. The objective is to recover the matrix $Q$ using this additional knowledge. The authors study two settings, one in which there is a budget to sample noisy entries of $Q$ (active sampling) and one in which, according to some distribution, noisy entries of $Q$ are revealed. An estimation algorithm for $Q$ is given, and analysis is provided for the estimation error of both settings.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback, and for highlighting that our paper has strong empirical results, and is comprehensive in its analysis of an interesting problem. We address their comments below. \n\n## We will reorganize the writing to first introduce the estimation framework, and then separately discuss the active and passive sampling settings. \n\nOur estimation framework (Section 2.2) involves first learning features from the source matrix via SVD, and then estimating the target matrix via least-squares. This estimation framework applies to both the active sampling (lines 85-96, left) and passive sampling (lines 97-109, left) settings. To improve readability, we will reorganize the problem setup in the revision to first introduce the estimation framework, and then discuss both the active and passive sampling settings. We thank the reviewer for this valuable suggestion.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes, and Figure 2 shows that that this method outperforms other methods as well.", "theoretical_claims": "The theoretical claims appear to be correct.", "experimental_designs_or_analyses": "Yes, the experiments appear to be sound and valid.", "relation_to_broader_scientific_literature": "The problem analyzed in this paper is motivated by problems that arise in biology. The authors emphasize its relation to tasks such as various key biology and medical problems, for which this paper may be useful.", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "Strengths:\n* The paper is comprehensive in its analysis of an interesting problem and studies two different settings, the passive and active sampling settings. As expected, the active sampling setting is easier. Minimax lower bounds and generic error bounds are given for both settings. Further, the solution is computationally efficient.\n* This paper generalizes on previous results by allowing for any kind of distribution shift rather than simply a rotational shift.\n* Empirically, there are strong results. The results appear to be complete and well-described.\nWeaknesses:\n* To improve readability, it would be better to first introduce the estimation framework, and then separately discuss active and passive learning settings.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "n/a", "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": "H7kwncg6al", "reviewer": "Reviewer_zFpJ", "summary": "This paper studies transfer learning for matrix completion in a Missing Not-at-Random (MNAR) setting, which is motivated by biological problems. The problem is challenging because entire rows and columns of the target matrix are are missing, making direct estimation impossible. This paper introduces a source matrix. This paper provides lower bounds for estimation error in both active and passive sampling settings. The proposed model is an efficient model that is minimax-optimal in the active setting and rate-optimal in the passive setting.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback, and for highlighting the relevance of our problem (MNAR matrix completion with transfer learning) to biological applications. We address their comments below. \n\n## Our minimax results guide algorithm design. \n\nThe practical significance of our minimax lower bounds for MNAR matrix completion is that *no method* can achieve a better estimation error than ours. So, the error guarantees in Theorems 2.6 and 2.9 are unimprovable in our setting. \n\n## Exact selection of rows and columns (in active sampling) *is realistic* for the biological settings we study. \n\nThe choice of exact rows and columns to query matches experimental design constraints in multiple settings (lines 9-16, right). Our model is designed to capture these settings. These include (i) metabolite balancing experiments (Christensen and Nielsen, 2000), (ii) gene expression microarrays (Hu et al. 2021), (iii) marker selection for single-cell RNA sequencing (Vargo and Gilbert, 2020) and (iv) patient selection for companion diagnostics (Huber et al. 2022). In Section 3.1, we study precisely the first two settings listed in the introduction: metabolic (Fig. 3) and gene expression (Fig. 2) data. \n\nSome settings, such as electronic health records (Zhou et al. 2023), have different experimental design constraints (lines 46-49, right). Our model would not apply to these settings. \n\nIn the revision, we will include additional details on experimental protocols for metabolite balancing and gene expression microarray experiments, as suggested. \n\n## Our MNAR model captures the missingness structure of the biological datasets we study. \n\nOur passive sampling model (lines 97-109, left) matches the row/column missingness structure present in gene expression data (Fig. 1, and lines 16-24, right) and metabolic network data (lines 330-342, left). We focus on these settings in our real-world experiments (Section 3.1). \n\nFor other kinds of data, other missigness structures may be present (lines 46-49, right). Our methods can be applied to *any* missingness structure, but we analyze the specific MNAR settings of the paper due to their biological importance. \n\nIf the Reviewer has particular missingness structures in mind, we are happy to discuss the applicability of our methods to those settings. \n\n## The distribution shift model is realistic for the datasets we study. \n\nThe matrix transfer model (Definition 1.2) is commonly used in the biological literature, such as in Genome-Wide Association Studies (see McGrath et al. 2024 and references therein). Our real-world experiments (Section 3.1) further validate that it is appropriate for gene expression (Fig. 2) and metabolic (Fig. 3) transfer problems. \n\nNo model applies perfectly to real-world data. It would be interesting to study other models of distribution shift, as we have stated (lines 437-439, right). \n\n## Our methods can be applied without any structured transfer assumptions. \n\nEven if Definition 1.2 does not hold, our method can be applied. However, we only analyze its theoretical properties under Definition 1.2. \n\n## Our methods *can* use noisy SVD estimates.\n\nWe do not assume clean SVD features for either the source matrix $P$ or target matrix $Q$. The source matrix, which follows Assumption 2.5, can be noisily observed in an MCAR or MNAR fashion (lines 167-172, right). The target matrix is observed with additive noise and has missing rows and columns for both active and passive sampling (lines 79-109, left). \n\n## Our active sampler *does not* assume idealized G-optimal design. \n\nWe compute an $\\epsilon$-approximate G-optimal design (Definition 2.3) with convex optimization. Specifically, we use the Franke-Wolfe algorithm which runs in polynomial time (Lattimore and Szepesvari 2020). Setting $\\epsilon = 0.05$ is sufficient (Theorem 2.6). A perfect $G$-optimal design is not needed. \n\n## We will add graph-based and VAE-based references in the revision. \n\nWe will discuss VAE-based methods and graph-based methods in the revision, including but not limited to the (see discussion with Reviewer XH4Z) of Ipsen et al. 2020, as well as [1-2] for VAE, and Jalan et al. (NeurIPS 2024) and [3-4] for graphs. \n\n[1] Ghalebikesabi, Sahra, et al. \"Deep generative missingness pattern-set mixture models.\" International conference on artificial intelligence and statistics. PMLR, 2021.\n\n[2] Cai, Hongmin, et al. \"Realize generative yet complete latent representation for incomplete multi-view learning.\" IEEE Transactions on Pattern Analysis and Machine Intelligence46.5 (2023): 3637-3652.\n\n[3] Wang, Yao, et al. \"Matrix Completion with Graph Information: A Provable Nonconvex Optimization Approach.\" arXiv preprint arXiv:2502.08536 (2025).\n\n[4] Zhan, Tong, et al. \"Collective Matrix Completion via Graph Extraction.\" IEEE Signal Processing Letters (2024).\n\n## All algorithms are polynomial-time. \n\nWe use well-studied polynomial-time algorithms (SVD, least-squares, and Franke-Wolfe).", "claims_and_evidence": "1. The proposed estimator is minimax-optimal for the active setting, while in real-world applications, exact optimization of sample selection is impractical. \n2. The transfer learning framework effectively corrects for the missingness structure in MNAR settings. However, the distribution shift model is restrictive.", "methods_and_evaluation_criteria": "1. The paper defines active and passive sampling settings, but the evaluation assumes clean singular value decomposition (SVD) features can always be extracted, which is unrealistic in noisy biological data.\n2. Active sampling relies on an idealized G-optimal design, which assumes one can perfectly select the most informative rows/columns, an unrealistic assumption in biological experiments.", "theoretical_claims": "1. Minimax lower bounds for MNAR matrix completion are presented, but the practical significance of these bounds is unclear.\n2. The paper proves optimality under restrictive assumptions, while real-world missingness mechanisms are more complex.", "experimental_designs_or_analyses": "1. The paper evaluates on only two datasets, which is insufficient for demonstrating broad applicability.\n2. The paper does not evaluate how well the method generalizes across different datasets or varying missingness patterns.", "relation_to_broader_scientific_literature": "This paper studies transfer learning for matrix completion in a Missing Not-at-Random (MNAR) setting, which is motivated by biological problems.", "essential_references_not_discussed": "Graph-based and VAE-based matrix completion methods should be discussed.", "other_strengths_and_weaknesses": "Strengths:\n1. The problem of MNAR matrix completion with transfer learning is relevant in biological applications.\n2. The theoretical analysis of estimation error bounds contributes to the understanding of MNAR matrix recovery.\n\nWeaknesses:\n1. The method is largely a combination of existing techniques.\n2. Real-world applicability is questionable, from my perspective, the active sampling strategy is difficult to implement practically.\n3. The assumptions about the structured linear feature shifts between source and target matrices is restrictive.", "other_comments_or_suggestions": "1. Discuss practical limitations of active sampling and whether it can be applied in real experimental settings.\n2. Provide more details on implementation choices, such as hyperparameter tuning and computational complexity.", "questions_for_authors": "1. What happens if the structured transfer assumption (Definition 1.2) does not hold?\n2. Can the active sampling method be realistically implemented in biological experiments?\n3. How robust is the method to different missingness mechanisms?", "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": "JWql7WtVQa", "reviewer": "Reviewer_nRTL", "summary": "This paper studies the problem of matrix completion with missing not-at-random mechanisms, where the observation pattern is row/columns-wise. Under such missing/observation family, the authors establish the minimax lower bound for entrywise estimation error. With side information, the authors propose a computationally efficient estimation framework which achieves the optimal rate under mild assumptions. The effectiveness of proposed method is demonstrated on both simulated data and real-world genomic and metabolic datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback, and for highlighting that our claims are supported by rigorous theoretical investigations and numerical experiments. We will fix typos in the revision, and we address all other comments below. \n\n## Our methods perform best under new evaluation metrics (MAE and RMSE). \n\nAs the Reviewer suggests, we perform new experiments to compare our active and passive sampling methods on Mean Absolute Error (MAE), Root Mean Squared Error (RMSE), as well as the the previously presented metrics of Max Squared Error, and Mean Squared Error (MSE). For ease of comparison, we report the results of Fig. 2 (gene expression transfer) and Fig. 3 (metabolic transfer) again in the tables below. The MAE/RMSE numbers are new. \n\nFor the gene expression transfer problem (Figure 2), our methods continue to out-perform baselines with $p_{\\textup{Row}} = p_{\\textup{Col}} = 0.5$. \nFor gene expression data, the errors are: \n| Method | MSE | Max Squared Error | MAE | RMSE |\n|--------|-------|-----------|-----|------|\n| Passive (Ours) | **0.004385** | **0.300035** | **0.044493** | **0.055198** |\n| Active (Ours) | *0.018225* | *0.372105* | *0.103285* | *0.114654* |\n| LLL22 | 0.151792 | 0.626293 | 0.343497 | 0.389449 |\n| BC22 | 0.570254 | 1.000000 | 0.678862 | 0.754897 |\n\nNext, we perform the same experiment for the metabolic transfer problem (Figure 3). \n| Method | MSE | Max Squared Error | MAE | RMSE |\n|--------|-------|-----------|-----|------|\n| Passive (Ours) | *0.000217* | 1.292995 | *0.000934* | *0.014638* |\n| Active (Ours) | **0.000024** | **0.294249** | **0.000669** | **0.004883** |\n| LLL22 | 0.000360 | *0.651176* | 0.006931 | 0.018147 |\n| BC22 | 0.003790 | 1.000000 | 0.021086 | 0.055543 |\n\nWe will include the suggested error metrics (MAE and RMSE) in the revision. \n\n## Our theoretical upper bounds on Max Squared Error also imply upper bounds on Frobenius error, RMSE, and MAE. \n\nThe max-squared error bounds (Theorem 2.6 and Theorem 2.9) immediately imply bounds on Frobenius error, because $\\frac{1}{mn} \\Vert \\hat Q - Q \\Vert_{F}^2 \\leq \\Vert \\hat Q - Q \\Vert_{max}^2$. \n\nSimilarly, both the RMSE and the MAE are upper-bounded by the Max Absolute Error, which can be bounded via Theorems 2.6 and 2.9. \n\nWe will include this discussion in the revision. \n\n## Our experiments are conducted on datasets where the primary interest is the recovery of entries. \n\nOur real-world experiments (Section 3.1) on gene expression (Fig. 2) and metabolic (Fig. 3) data are on datasets where the primary interest is recovery of missing entries (Parnell et al. 2013, King et al. 2016, Jalan et al. 2024). \n\n## We mask matrix entries to compare estimated vs. ground-truth values. \n\nIn each experiment, we mask entries of $Q$ for which the ground-truth is known, so that we can compare the estimated $\\hat Q_{ij}$ to the ground truth value $Q_{ij}$. We mask according to the active and passive sampling frameworks (lines 302-320, left). \n\nThere are many entries of $P, Q$ for which the ground truth is unknown. Without knowing the ground truth, we cannot report estimation error. Therefore we do not perform estimation experiments on missing entries for which ground-truth values are not known.", "claims_and_evidence": "The claims are supported by rigorous theoretical investigations and numerical experiments.", "methods_and_evaluation_criteria": "The theoretical results are developed mostly in $max$ (entrywise $L_\\infty$) norm. It would be interesting to see the discussion in other forms (in an average sense, like Frobenius norm or entrywise $L_1$ norm). In numerical experiments, such metrics are also interesting and informative to see (RMSE, MAE, etc).", "theoretical_claims": "I didn't go through the detailed proofs, but the ideas and discussions presented in the main body are sound to me.", "experimental_designs_or_analyses": "If I understand it correctly, there's no real missing in the real world experiments. Are the missed entries synthetic? It would enhance the significance of this work if the experiments are conducted on datasets where the primary interest is the recovery of entries.", "relation_to_broader_scientific_literature": "The presented method works effectiveness for biological findings.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "No.", "other_comments_or_suggestions": "line 1422, \"do poorly in max errow\"", "questions_for_authors": "No", "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:

Meta-review: This paper studies matrix completion in a novel framework that incorporates missingness of entire rows or columns with some side information available in the form of an out-of-domain source matrix. The results include both upper and lower bounds in both passive and active sampling regimes, where the latter refers to a situation where the learner is able to select a certain quota of full rows and columns to observe. Like the "MNAR" literature, the results are "out of distribution" in the sense that the upper bounds manage to control the recovery error in terms of the maximum error on any entry, even in though the sampling distribution is nonuniform.  The reviewers unanimously agree the paper makes a strong contribution and should be accepted. I also find the results very interesting and powerful.  It would be interesting to compare the results to the existing generalization analyses for IMC in the distribution-free  i.i.d. sampling regime, where the performance measure is defined in-distribution (in expectation over the sampling distribution).
Decision: Accept (poster)