# Matrix Completion with Heterogonous Cost

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 41 references that are in the map.
- First posted on arXiv 23 Mar 2022.

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

- [CurricularFace: Adaptive Curriculum Learning Loss for Deep Face Recognition](https://mlsanity.com/paper/2004.00288/) (2020)
- [Riemannian Adaptive Optimization Methods](https://mlsanity.com/paper/1810.00760/) (2018)
- [On the adequacy of untuned warmup for adaptive optimization](https://mlsanity.com/paper/1910.04209/) (2019)
- [Low-Rank Matrix and Tensor Completion via Adaptive Sampling](https://mlsanity.com/paper/1304.4672/) (2013)
- [Fast Exact Matrix Completion with Finite Samples](https://mlsanity.com/paper/1411.1087/) (2014)
- [On the Power of Adaptivity in Matrix Completion and Approximation](https://mlsanity.com/paper/1407.3619/) (2014)
- [Noise-Tolerant Life-Long Matrix Completion via Adaptive Sampling](https://mlsanity.com/paper/1612.00100/) (2016)
- [Matrix completion with queries](https://mlsanity.com/paper/1705.00399/) (2017)
- [Optimal Exact Matrix Completion Under new Parametrization](https://mlsanity.com/paper/2002.02431/) (2020)
- [Adaptive Sampling Distributed Stochastic Variance Reduced Gradient for Heterogeneous Distributed Datasets](https://mlsanity.com/paper/2002.08528/) (2020)
- [Lifelong Matrix Completion with Sparsity-Number](https://mlsanity.com/paper/2203.07637/) (2022)
- [Adaptive Noisy Matrix Completion](https://mlsanity.com/paper/2203.08340/) (2022)
- [Fast Exact Matrix Completion: A Unified Optimization Framework for Matrix Completion](https://mlsanity.com/paper/1910.09092/) (2019)

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

- [Survey of Matrix Completion Algorithms](https://mlsanity.com/paper/2204.01532/) (2022)
- [Matrix Completion with Sparse Noisy Rows](https://mlsanity.com/paper/2204.01530/) (2022)

## Abstract (arXiv)

The matrix completion problem has been studied broadly under many underlying conditions. The problem has been explored under adaptive or non-adaptive, exact or estimation, single-phase or multi-phase, and many other categories. In most of these cases, the observation cost of each entry is uniform and has the same cost across the columns. However, in many real-life scenarios, we could expect elements from distinct columns or distinct positions to have a different cost. In this paper, we explore this generalization under adaptive conditions. We approach the problem under two different cost models. The first one is that entries from different columns have different observation costs, but, within the same column, each entry has a uniform cost. The second one is any two entry has different observation cost, despite being the same or different columns. We provide complexity analysis of our algorithms and provide tightness guarantees.