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 $\tilde{O}(D/\gamma^2)$. The term $1/\gamma^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 \times n$ matrix into $P Q^\intercal$ where the rows of $P$ are interpreted
as "classifiers" in $\mathcal{R}^d$ and the rows of $Q$ as "instances" in
$\mathcal{R}^d$, then $\gamma$ 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 \in O(k + \ell)$ where $k$ is the number of distinct row
factors and $\ell$ 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(k^2 + \ell^2)$.

本文研究了在线的二进制矩阵完成算法，证明了相应的错误界和遗憾界。同时，通过引入最大化边界变量 γ 和拟维数项 D，衡量了与边缘和附带信息的质量和数量相关的算法结果。

带有辅助信息的在线矩阵补全

Online Matrix Completion with Side Information

We present a brief survey of existing mistake bounds and introduce novel
bounds for the Perceptron or the kernel Perceptron algorithm. Our novel bounds
generalize beyond standard margin-loss type bounds, allow for any convex and
Lipschitz loss function, and admit a very simple proof.

本文概述了现有的误差界限，并引入了感知器或核感知器算法的新界限。我们的新界限一般化超出了标准的边际损失型界限，允许任何凸和 Lipschitz 损失函数，并且具有非常简单的证明。