Non-Convex Matrix Completion Against a Semi-Random Adversary
  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$. Even with this mild
semi-random perturbation, we can construct counter-examples where existing
non-convex algorithms get stuck in bad local optima.
  In light of the negative results, we propose a pre-processing step that tries
to re-weight the semi-random input, so that it becomes "similar" to a random
input. We give a nearly-linear time algorithm for this problem, and show that
after our pre-processing, all the local minima of the non-convex objective can
be used to approximately recover the underlying ground-truth matrix.
