Match Made with Matrix Completion: Efficient Learning under Matching Interference

• URL: http://arxiv.org/abs/2601.06982v1
• Date: Sun, 11 Jan 2026 16:33:01 GMT
• Title: Match Made with Matrix Completion: Efficient Learning under Matching Interference
• Authors: Zhiyuan Tang, Wanning Chen, Kan Xu,
• Abstract summary: We show that standard nuclear norm regularization remains theoretically effective under matching interference.<n>We develop a novel double-enhanced'' estimator, based off the nuclear norm estimator, with a near-optimal entry-wise guarantee.
• Score: 3.4439950003681417
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Matching markets face increasing needs to learn the matching qualities between demand and supply for effective design of matching policies. In practice, the matching rewards are high-dimensional due to the growing diversity of participants. We leverage a natural low-rank matrix structure of the matching rewards in these two-sided markets, and propose to utilize matrix completion to accelerate reward learning with limited offline data. A unique property for matrix completion in this setting is that the entries of the reward matrix are observed with matching interference -- i.e., the entries are not observed independently but dependently due to matching or budget constraints. Such matching dependence renders unique technical challenges, such as sub-optimality or inapplicability of the existing analytical tools in the matrix completion literature, since they typically rely on sample independence. In this paper, we first show that standard nuclear norm regularization remains theoretically effective under matching interference. We provide a near-optimal Frobenius norm guarantee in this setting, coupled with a new analytical technique. Next, to guide certain matching decisions, we develop a novel ``double-enhanced'' estimator, based off the nuclear norm estimator, with a near-optimal entry-wise guarantee. Our double-enhancement procedure can apply to broader sampling schemes even with dependence, which may be of independent interest. Additionally, we extend our approach to online learning settings with matching constraints such as optimal matching and stable matching, and present improved regret bounds in matrix dimensions. Finally, we demonstrate the practical value of our methods using both synthetic data and real data of labor markets.

Related papers

• Online Inference of Constrained Optimization: Primal-Dual Optimality and Sequential Quadratic Programming [55.848340925419286]
  We study online statistical inference for the solutions of quadratic optimization problems with equality and inequality constraints.<n>We develop a sequential programming (SSQP) method to solve these problems, where the step direction is computed by sequentially performing an approximation of the objective and a linear approximation of the constraints.<n>We show that our method global almost moving-average convergence and exhibits local normality with an optimal primal-dual limiting matrix in the sense of Hjek and Le Cam.
  arXiv  Detail & Related papers  (2025-11-27T06:16:17Z)
• Statistical Inference for Matching Decisions via Matrix Completion under Dependent Missingness [6.28693385008859]
  We propose an algorithm for non-optimal entry for three canonical mechanisms, i.e. one-to-one, one-sided matching with one-sided random arrival, and two-sided random arrival.<n>Our empirical experiments demonstrate that the proposed approach provides accurate estimation valid confidence intervals and efficient evaluation.
  arXiv  Detail & Related papers  (2025-10-30T13:31:32Z)
• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
  We study the generalized linear bandit (GLB) problem, a contextual multi-armed bandit framework that extends the classical linear model by incorporating a non-linear link function.<n>GLBs are widely applicable to real-world scenarios, but their non-linear nature introduces significant challenges in achieving both computational and statistical efficiency.<n>We propose a jointly efficient algorithm that attains a nearly optimal regret bound with $mathcalO(1)$ time and space complexities per round.
  arXiv  Detail & Related papers  (2025-07-16T02:24:21Z)
• A Linearized Alternating Direction Multiplier Method for Federated Matrix Completion Problems [2.2217927229805032]
  Matrix completion is fundamental for predicting missing data with a wide range of applications in personalized healthcare, e-commerce, recommendation systems, and social network analysis.<n>Traditional matrix completion approaches typically assume centralized data storage.<n>We propose textttFedMC-ADMM for solving federated matrix completion problems.
  arXiv  Detail & Related papers  (2025-03-17T01:57:06Z)
• Understanding and Scaling Collaborative Filtering Optimization from the Perspective of Matrix Rank [39.857011461812014]
  Collaborative Filtering (CF) methods dominate real-world recommender systems.<n>We study the properties of the embedding tables under different learning strategies.<n>We propose an efficient warm-start strategy that regularizes the stable rank of the user and item embeddings.
  arXiv  Detail & Related papers  (2024-10-15T21:54:13Z)
• Synergistic eigenanalysis of covariance and Hessian matrices for enhanced binary classification [72.77513633290056]
  We present a novel approach that combines the eigenanalysis of a covariance matrix evaluated on a training set with a Hessian matrix evaluated on a deep learning model. Our method captures intricate patterns and relationships, enhancing classification performance.
  arXiv  Detail & Related papers  (2024-02-14T16:10:42Z)
• Adversarial Online Collaborative Filtering [20.931533714651376]
  We investigate the problem of online collaborative filtering under no-repetition constraints. We design and analyze an algorithm that works under biclustering assumptions on the user-item preference matrix. We show that this algorithm exhibits an optimal regret guarantee, while being fully adaptive.
  arXiv  Detail & Related papers  (2023-02-11T19:30:55Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  Existing primal-dual algorithms for constrained online learning problems rely on two fundamental assumptions. We show how such assumptions can be circumvented by endowing standard primal-dual templates with weakly adaptive regret minimizers. We prove the first best-of-both-worlds no-regret guarantees which hold in absence of the two aforementioned assumptions.
  arXiv  Detail & Related papers  (2023-02-02T16:30:33Z)
• Online Statistical Inference in Decision-Making with Matrix Context [5.2071564436846245]
  We propose an online procedure to conduct statistical inference with adaptively collected data.<n>Standard low-rank estimators are biased and cannot be obtained in a sequential manner.<n>Existing approaches in sequential decision-making algorithms fail to account for the low-rankness and are also biased.
  arXiv  Detail & Related papers  (2022-12-21T22:03:06Z)
• Practical Approaches for Fair Learning with Multitype and Multivariate Sensitive Attributes [70.6326967720747]
  It is important to guarantee that machine learning algorithms deployed in the real world do not result in unfairness or unintended social consequences. We introduce FairCOCCO, a fairness measure built on cross-covariance operators on reproducing kernel Hilbert Spaces. We empirically demonstrate consistent improvements against state-of-the-art techniques in balancing predictive power and fairness on real-world datasets.
  arXiv  Detail & Related papers  (2022-11-11T11:28:46Z)
• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion [60.52730146391456]
  We propose a new non scalable low-rank regularizer called "nuclear Frobenius norm" regularizer, which is adaptive and sound. It bypasses the computation of singular values and allows fast optimization by algorithms. It obtains state-of-the-art recovery performance while being the fastest in existing matrix learning methods.
  arXiv  Detail & Related papers  (2020-08-14T18:47:58Z)

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.