Skip to main content

Non-Convex Matrix Completion Against a Semi-Random Adversary

Publication ,  Conference
Cheng, Y; Ge, R
Published in: Proceedings of Machine Learning Research
January 1, 2018

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 crucially on the assumption that each entry of the matrix 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.

Duke Scholars

Published In

Proceedings of Machine Learning Research

EISSN

2640-3498

Publication Date

January 1, 2018

Volume

75

Start / End Page

1362 / 1394
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Cheng, Y., & Ge, R. (2018). Non-Convex Matrix Completion Against a Semi-Random Adversary. In Proceedings of Machine Learning Research (Vol. 75, pp. 1362–1394).
Cheng, Y., and R. Ge. “Non-Convex Matrix Completion Against a Semi-Random Adversary.” In Proceedings of Machine Learning Research, 75:1362–94, 2018.
Cheng Y, Ge R. Non-Convex Matrix Completion Against a Semi-Random Adversary. In: Proceedings of Machine Learning Research. 2018. p. 1362–94.
Cheng, Y., and R. Ge. “Non-Convex Matrix Completion Against a Semi-Random Adversary.” Proceedings of Machine Learning Research, vol. 75, 2018, pp. 1362–94.
Cheng Y, Ge R. Non-Convex Matrix Completion Against a Semi-Random Adversary. Proceedings of Machine Learning Research. 2018. p. 1362–1394.

Published In

Proceedings of Machine Learning Research

EISSN

2640-3498

Publication Date

January 1, 2018

Volume

75

Start / End Page

1362 / 1394