Herbster, M;
Pasteris, S;
Tse, L;
(2021)
Online matrix completion with side information.
In:
Advances in Neural Information Processing Systems 33 (NeurIPS 2020).
Preview |
Text
NeurIPS-2020-online-matrix-completion-with-side-information-Paper.pdf - Published Version Download (831kB) | Preview |
Abstract
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 Õ(?D2). The term ?12 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?, where the rows of P are interpreted as “classifiers” in <d and the rows of Q as “instances” in <d, then ? is is the maximum (normalized) margin over all factorizations P Q? 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 2 O(k + l) where k is the number of distinct row factors and l 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 + l2).
| Type: | Proceedings paper |
|---|---|
| Title: | Online matrix completion with side information |
| Event: | Thirty-fourth Conference on Neural Information Processing Systems |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | https://proceedings.neurips.cc/paper/2020/hash/eb0... |
| Language: | English |
| Additional information: | This version is the version of record. For information on re-use, please refer to the publisher's terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Physics and Astronomy |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10133097 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
