# Tackling Combinatorial Distribution Shift: A Matrix Completion Perspective

arXiv: https://arxiv.org/abs/2307.06457 · HTML: https://mlsanity.com/paper/2307.06457/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 51 references that are in the map.
- First posted on arXiv 12 Jul 2023.

## Builds on (most cited first, 5 of 5)

- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [BREEDS: Benchmarks for Subpopulation Shift](https://mlsanity.com/paper/2008.04859/) (2020)
- [Optimally tackling covariate shift in RKHS-based nonparametric regression](https://mlsanity.com/paper/2205.02986/) (2022)
- [Causal Matrix Completion](https://mlsanity.com/paper/2109.15154/) (2021)
- [Nonparametric Matrix Estimation with One-Sided Covariates](https://mlsanity.com/paper/2110.13969/) (2021)

## Built on by (most cited first, 5 of 5)

- [Robot Fleet Learning via Policy Merging](https://mlsanity.com/paper/2310.01362/) (2023)
- [Transfer Learning Beyond Bounded Density Ratios](https://mlsanity.com/paper/2403.11963/) (2024)
- [Transfer Learning for Latent Variable Network Models](https://mlsanity.com/paper/2406.03437/) (2024)
- [Optimal Transfer Learning for Missing Not-at-Random Matrix Completion](https://mlsanity.com/paper/2503.00174/) (2025)
- [Distributional Extrapolation for Interactions](https://mlsanity.com/paper/2608.19849/) (2026)

## Abstract (arXiv)

Obtaining rigorous statistical guarantees for generalization under distribution shift remains an open and active research area. We study a setting we call combinatorial distribution shift, where (a) under the test- and training-distributions, the labels z are determined by pairs of features (x,y), (b) the training distribution has coverage of certain marginal distributions over x and y separately, but (c) the test distribution involves examples from a product distribution over (x,y) that is not covered by the training distribution. Focusing on the special case where the labels are given by bilinear embeddings into a Hilbert space H: mathbbE[z mid x,y ]=langle fstar(x),gstar(y)rangle_H, we aim to extrapolate to a test distribution domain that is not covered in training, i.e., achieving bilinear combinatorial extrapolation. Our setting generalizes a special case of matrix completion from missing-not-at-random data, for which all existing results require the ground-truth matrices to be either exactly low-rank, or to exhibit very sharp spectral cutoffs. In this work, we develop a series of theoretical results that enable bilinear combinatorial extrapolation under gradual spectral decay as observed in typical high-dimensional data, including novel algorithms, generalization guarantees, and linear-algebraic results. A key tool is a novel perturbation bound for the rank-k singular value decomposition approximations between two matrices that depends on the relative spectral gap rather than the absolute spectral gap, a result that may be of broader independent interest.