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

There is much empirical evidence that item-item collaborative filtering works
well in practice. Motivated to understand this, we provide a framework to
design and analyze various recommendation algorithms. The setup amounts to
online binary matrix completion, where at each time a random user requests a
recommendation and the algorithm chooses an entry to reveal in the user's row.
The goal is to minimize regret, or equivalently to maximize the number of +1
entries revealed at any time. We analyze an item-item collaborative filtering
algorithm that can achieve fundamentally better performance compared to
user-user collaborative filtering. The algorithm achieves good "cold-start"
performance (appropriately defined) by quickly making good recommendations to
new users about whom there is little information.

本研究提供了一个设计和分析各种协同过滤推荐算法的框架，研究发现相比于用户 - 用户协同过滤，基于商品 - 商品的过滤算法表现得更好，并能够以快速的速度为缺乏信息的新用户提供良好的推荐表现，该过滤算法的具体实现是在线二进制矩阵填充。