| 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 O( D ). The term 1 is analogous to the usual margin term in γ2 γ2 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 Rd and the rows of Q as “instances” in Rd, then γ is is the maximum (normalized) margin overall factorizations PQ⊤ 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 + 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). |