论文标题
部分矩阵完成
Partial Matrix Completion
论文作者
论文摘要
矩阵完成问题旨在根据一组可能的嘈杂条目重建一个低级别矩阵。先前的工作考虑通过保证概括错误完成整个矩阵。但是，在不同条目中，完成精度可能会大不相同。这项工作建立了一个新的部分矩阵完成框架，其目标是确定可以高信任完成的大量条目。我们提出了一种有效的算法，具有以下可证明的保证。从未知和任意分布中访问样品，它保证了：（a）在完成的条目中高精度，以及（b）基础分布的高度覆盖率。我们还考虑了此问题的在线学习变体，我们根据迭代梯度更新提出了一种低regret算法。包括初步的经验评估。
The matrix completion problem aims to reconstruct a low-rank matrix based on a revealed set of possibly noisy entries. Prior works consider completing the entire matrix with generalization error guarantees. However, the completion accuracy can be drastically different over different entries. This work establishes a new framework of partial matrix completion, where the goal is to identify a large subset of the entries that can be completed with high confidence. We propose an efficient algorithm with the following provable guarantees. Given access to samples from an unknown and arbitrary distribution, it guarantees: (a) high accuracy over completed entries, and (b) high coverage of the underlying distribution. We also consider an online learning variant of this problem, where we propose a low-regret algorithm based on iterative gradient updates. Preliminary empirical evaluations are included.
