Semi-Random Noisy and One-Bit Matrix Completion With Nonconvex Primal-Dual Framework

We study low-rank matrix completion in the semi-random model, where each entry is revealed with some unknown probability at least $p$, in contrast to the standard setting with a uniform probability $p$. While prior work [CG18] has shown that the nonconvex approach succeeds in the semi-random model for quadratic loss, it remains unclear whether similar guarantees extend to more general settings, such as noisy or one-bit matrix completion. We give a nearly-linear time algorithmic framework for semi-random matrix completion with a broad family of loss functions. Our approach builds on a preprocessing step from [CG18] to restore regularity conditions failing under the semi-random setting, as well as a general primal-dual scheme of [ZWYG18], achieving nearly-linear runtime and recovery guarantees that are optimal up to logarithmic factors. As concrete corollaries, this yields nearly-linear time solutions for noisy and one-bit matrix completion under the semi-random model.