# Online Matrix Completion with Side Information

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2019.

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

- [Generalization Bounds for Inductive Matrix Completion in Low-noise Settings](https://mlsanity.com/paper/2212.08339/) (2022)
- [Adversarial Online Collaborative Filtering](https://mlsanity.com/paper/2302.05765/) (2023)
- [Online Multi-Label Classification under Noisy and Changing Label Distribution](https://mlsanity.com/paper/2410.02394/) (2024)

## Abstract (arXiv)

We give an online algorithm and prove novel mistake and regret bounds for online binary matrix completion with side information. The mistake bounds we prove are of the form tildeO(D/γ2). The term 1/γ2 is analogous to the usual margin term in SVM (perceptron) bounds. More specifically, if we assume that there is some factorization of the underlying m × n matrix into P Q^intercal where the rows of P are interpreted as "classifiers" in Rd and the rows of Q as "instances" in Rd, then γ is the maximum (normalized) margin over all factorizations P Q^intercal consistent with the observed matrix. The quasi-dimension term D measures the quality of side information. In the presence of vacuous side information, D= m+n. However, if the side information is predictive of the underlying factorization of the matrix, then in an ideal case, D ∈ O(k + ℓ) where k is the number of distinct row factors and ℓ is the number of distinct column factors. We additionally provide a generalization of our algorithm to the inductive setting. In this setting, we provide an example where the side information is not directly specified in advance. For this example, the quasi-dimension D is now bounded by O(k2 + ℓ2).