Optimal Transfer Learning for Missing Not-at-Random Matrix Completion

Akhil Jalan, Yassir Jedra, Arya Mazumdar, Soumendu Sundar Mukherjee, Purnamrita Sarkar · 2025

Read Optimal Transfer Learning for Missing Not-at-Random Matrix Completion by Akhil Jalan, Yassir Jedra, Arya Mazumdar, Soumendu Sundar Mukherjee, Purnamrita Sarkar (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-00174.txt.

Introduction

Akhil Jalan and co-authors study how to fill in a table of values when whole rows and columns are missing, in a 2025 paper. The gaps are not random: some entries are far more likely to be seen than others, a pattern drawn from biology problems. A target table with full rows missing cannot be solved alone, so the team borrows a noisy, partial source table linked to the target by a shift in hidden traits.

The authors prove lower bounds on the best possible error, for both planned and unplanned sampling of rows and columns. Their method reaches that bound in the planned case by asking for the most telling rows first. Tests on real biology data sets favor their approach over older ones.

Catalog record

CREATORAkhil Jalan, Yassir Jedra, Arya Mazumdar, Soumendu Sundar Mukherjee, Purnamrita Sarkar
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE84 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-00174

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Optimal Transfer Learning for Missing Not-at-Random Matrix Completion Akhil Jalan, Yassir Jedra, Arya Mazumdar, Soumendu Sundar Mukherjee, Purnamrita Sarkar 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 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 P , which relates to Q 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 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. 1 Introduction We study transfer learning in the context of matrix completion, a fundamental problem motivated by theory [ 17 , 18 ] and practice [ 28 , 27 , 31 ] . A major body of work studies matrix completion in the Missing Completely-at-Random (MCAR) setting [ 41 , 12 , 10 ] , where each entry is observed i.i.d. with probability p . A more general missingness pattern, known as Missing Not-at-Random (MNAR), considers an underlying propensity matrix p_{ij} so that the (i,j)^{th} entry is observed independently with probability p_{ij} [ 51 , 6 ] . Various MNAR models have been formulated based on missingness structures in panel data [ 3 ] , recommender systems [ 40 ] , and electronic health records [ 75 ] . Motivated by biological problems, we consider a challenging MNAR structure where most rows and columns of \widetilde{Q} (a noisy version of Q ) are entirely missing. Specifically, we consider both the active sampling and passive sampling settings for \widetilde{Q} . In active sampling, a practitioner can choose rows R and columns C so that entries in R\times C are observed. This follows experimental design constraints in metabolite balancing experiments [ 15 ] , marker selection for single-cell RNA sequencing [ 70 ] , patient selection for companion diagnostics [ 34 ] , and gene expression microarrays [ 33 ] . In the passive sampling setting, the practitioner cannot choose the experiments. We model this by sampling each row (column) with probability p_{\textup{Row}} ( p_{\textup{Col}} ). For example, microarray 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 [ 33 ] . For an illustration, see Figure 1 . This setting is inherently difficult because there are many entries (i,j) for which row i and column j are both missing in \widetilde{Q} . Clearly, even when Q is low-rank and incoherent, estimation is impossible without side information (Proposition 2.1 ). Transfer learning is necessary to achieve vanishing estimation error since no information about Q_{ij} is known. Hence, we consider transfer learning in a setting where one has a noisy and masked \widetilde{P} corresponding to a source matrix P . P and Q are related by a distribution shift in their latent singular subspaces (Definition 1.2 ), which is a common model in e.g. Genome-Wide Association Studies [ 53 ] and Electronic Health Records [ 75 ] . Contributions. Below, we list our contributions: (i) We obtain minimax lower bounds for entrywise estimation error for both the active (Theorem 2.2 ) and passive sampling settings (Theorem 2.12 ). (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 ). (iii) We compare the performance of our algorithm with existing algorithms on real-world datasets for gene expression microarrays and metabolic modeling (Section 3 ). Figure 1 : The missingness matrix for gene expression levels on Day 2 of a sepsis study [ 56 ] shows entire rows (patients) and columns (genes) as missing, due to e.g. probe-target hybridization failure of the Illumina HT-12 gene expression microarray [ 33 ] . We mark missing entries as 0 (white) and present entries as 1 (blue). This motivates our missingness model (Eq. ( 1 ) and Eq. ( 2 )). Setup. P,Q\in\mathbb{R}^{m\times n} 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 \widetilde{P} . The observation model of \widetilde{Q} depends on which setting below we consider: (i) Active Sampling Setting. We have a budget of T_{\textup{row}} rows and T_{\textup{col}} columns. We select rows i_{1},\dots,i_{T_{\textup{row}}} and columns j_{1},\dots,j_{T_{\textup{col}}} , possibly at random, and with repeats allowed. Let n_{ij}\geq 0 be the number of times both row i and column j are chosen. Then, we have n_{ij} independent noisy observations \widetilde{Q}_{i,j}^{(1)},\dots,\widetilde{Q}_{i,j}^{(n_{ij})} such that: \displaystyle\tilde{Q}_{i,j}^{(t)}=\begin{cases}Q_{ij}+\zeta_{i,j}^{(t)}&\text{if }n_{ij}>0,\\ \star&\text{otherwise},\end{cases} (1) For \zeta_{i,j}^{(t)}\mathop{\sim}\limits^{i.i.d}\mathcal{N}(0,\sigma_{Q}^{2}) . (ii) Passive Sampling Setting. Instead of row and column budgets, there are probabilities p_{\textup{Row}},p_{\textup{Col}}\in[0,1] corresponding to the random row mask \eta_{1},\dots,\eta_{m}\overset{i.i.d.}{\sim}\mathrm{Ber}(p_{\textup{row}}) and column mask \nu_{1},\dots,\nu_{n}\mathop{\sim}\limits^{i.i.d}\mathrm{Ber}(p_{\textup{col}}) . Entry (i,j) of Q is noisily observed if \eta_{i}=\nu_{j}=1 , and missing otherwise. \displaystyle\tilde{Q}_{ij}=\begin{cases}Q_{ij}+\zeta_{i,j}&\text{if }\eta_{i}=\nu_{j}=1,\\ \star&\text{otherwise},\end{cases} (2) where \zeta_{i,j}\mathop{\sim}\limits^{i.i.d}\mathcal{N}(0,\sigma_{Q}^{2}) . 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 5 . 1.2 Notation and Problem Setup We use lowercase letters a,b,c to denote (real) scalars, boldface \bm{x},\bm{y},\bm{z} to denote vectors, and uppercase A,B,C to denote matrices. For n\geq 1 , let [n]:=\{1,\dots,n\} , I_{n} be the identity matrix and (\bm{e}_{i})_{i=1}^{n} the canonical basis vectors. Let a\lor b:=\max\{a,b\} and a\land b:=\min\{a,b\} . For multisets S,T and A\in\mathbb{R}^{m\times n} , let A[S,T]\in\mathbb{R}^{\left|S\right|\times\left|T\right|} be the submatrix with row and column indices in S,T respectively, possibly with repeated entries from A . Let \otimes denote the tensor (Kronecker) product: for A\in\mathbb{R}^{m\times n},B\in\mathbb{R}^{s\times t} , (A\otimes B)\in\mathbb{R}^{ms\times nt} with (A\otimes B)_{i(r-1)+v,j(s-1)+w}=A_{ij}B_{vw} . We denote the Frobenius norm as \|A\|_{F} , max norm as \|A\|_{\textup{max}}:=\max_{i,j}\left|A_{ij}\right| , and 2\to\infty norm as \|A\|_{2\to\infty}:=\max_{i}\|A^{T}\bm{e}_{i}\|_{2} . Asymptotics O(\cdot),o(\cdot),\Omega(\cdot),\omega(\cdot) are with respect to m\land n unless specified otherwise. Recall that, for integer n,d such that d\leq n , the Stiefel manifold \mathcal{O}^{n\times d} [ 32 ] consists of all U\in\mathbb{R}^{n\times d} such that U^{T}U=I_{d} . We now define matrix incoherence, which measures how concentrated the entries of the singular vectors are. Definition 1.1 (Incoherence) . Let M be an m\times n matrix of rank d , and write its SVD as M=U\Sigma V^{\top} . The left (resp. right) incoherence parameter of M is defined as \mu_{U}=m\|U\|_{2\to\infty}^{2}/d (resp. \mu_{V}=n\|V\|_{2\to\infty}^{2}/d ). The incoherence parameter of M is defined as \mu(M):=\max\{\mu_{U},\mu_{V}\} . We now formally define the distribution shift from P to Q , which generalizes the latent space rotation

Read the complete text