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

• URL: http://arxiv.org/abs/2503.00174v1
• Date: Fri, 28 Feb 2025 20:40:00 GMT
• Title: Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
• Authors: Akhil Jalan, Yassir Jedra, Arya Mazumdar, Soumendu Sundar Mukherjee, Purnamrita Sarkar,
• Abstract summary: We study transfer learning for matrix completion in a Missing Not-at-Random (MNAR) setting motivated by biological problems.<n>The target matrix $Q$ has entire rows and columns missing, making estimation impossible without side information.<n>We consider both the active and passive sampling of rows and columns. We establish minimax lower bounds for entrywise estimation error in each setting.
• Score: 18.919769656055706
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation [48.92318828548911]
  We present LoRa-PI (Low-Rank Policy Iteration), a model-free learning algorithm alternating between policy improvement and policy evaluation steps. LoRa-PI learns an $varepsilon$-optimal policy using $widetildeO(S+Aover mathrmpoly (1-gamma)varepsilon2)$ samples where $S$ denotes the number of states (resp. actions) and $gamma$ the discount factor.
  arXiv  Detail & Related papers  (2024-10-30T20:22:17Z)
• Minimax and Communication-Efficient Distributed Best Subset Selection with Oracle Property [0.358439716487063]
  The explosion of large-scale data has outstripped the processing capabilities of single-machine systems. Traditional approaches to distributed inference often struggle with achieving true sparsity in high-dimensional datasets. We propose a novel, two-stage, distributed best subset selection algorithm to address these issues.
  arXiv  Detail & Related papers  (2024-08-30T13:22:08Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  We propose a natural algorithm that involves imputing the missing values of the matrix $XTX$. We evaluate our algorithm on one-sided recovery of synthetic data and low-coverage genome sequencing.
  arXiv  Detail & Related papers  (2023-06-06T22:35:16Z)
• Adaptive Noisy Matrix Completion [0.0]
  We assume that the matrix $mathbfM$ we target to recover is composed as low-rank matrix with addition of bounded small noise. We study this problem in adaptive setting that, we continuously estimate an upper bound for the angle with the underlying low-rank subspace and noise-added subspace.
  arXiv  Detail & Related papers  (2022-03-16T01:20:18Z)
• Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach [6.952045528182883]
  We study the Sparse Plus Low-Rank decomposition problem ( SLR ) SLR is a fundamental problem in Operations Research and Machine Learning. We introduce a novel formulation for SLR that directly models its underlying discreteness.
  arXiv  Detail & Related papers  (2021-09-26T20:49:16Z)
• Sample Efficient Linear Meta-Learning by Alternating Minimization [74.40553081646995]
  We study a simple alternating minimization method (MLLAM) which alternately learns the low-dimensional subspace and the regressors. We show that for a constant subspace dimension MLLAM obtains nearly-optimal estimation error, despite requiring only $Omega(log d)$ samples per task. We propose a novel task subset selection scheme that ensures the same strong statistical guarantee as MLLAM.
  arXiv  Detail & Related papers  (2021-05-18T06:46:48Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  We solve a weakly supervised regression problem. Under "weakly" we understand that for some training points the labels are known, for some unknown, and for others uncertain due to the presence of random noise or other reasons such as lack of resources. In the numerical section, we applied the suggested method to artificial and real datasets using Monte-Carlo modeling.
  arXiv  Detail & Related papers  (2021-04-13T23:21:01Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  We give the first relative-error algorithms for column subset selection, subspace approximation, projective clustering, and volume on turnstile streams that use space sublinear in $n$. Our adaptive sampling procedure has a number of applications to various data summarization problems that either improve state-of-the-art or have only been previously studied in the more relaxed row-arrival model.
  arXiv  Detail & Related papers  (2020-04-23T05:00:21Z)
• Optimal Exact Matrix Completion Under new Parametrization [0.0]
  We study the problem of exact completion for $m times n$ sized matrix of rank $r$ with the adaptive sampling method. We propose matrix completion algorithms that exactly recovers the target matrix.
  arXiv  Detail & Related papers  (2020-02-06T18:31:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.