Non-Convex Matrix Completion Against a Semi-Random Adversary

Understand

Matrix completion is a well-studied problem with many machine learning applications.

• In practice, the problem is often solved by non-convex optimization algorithms.
• However, the current theoretical analysis for non-convex algorithms relies heavily on the assumption that every entry is observed with exactly the same probability $p$, which is not realistic in practice.
• In this paper, we investigate a more realistic semi-random model, where the probability of observing each entry is at least $p$.