Non-Convex Matrix Completion Against a Semi-Random Adversary

Abstract

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.

arXiv commentadded references and fixed typos

References in corpus (13)

• Deep Learning in Neural Networks: An Overview
• A Simpler Approach to Matrix Completion
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• How to Escape Saddle Points Efficiently
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Matrix Completion has No Spurious Local Minimum
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• A nearly-mlogn time solver for SDD linear systems
• Universal Matrix Completion
• Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming
• Recovery guarantee of weighted low-rank approximation via alternating minimization

Cited by in corpus (5)

• Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric $M$-Matrices
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• Solving SDP Faster: A Robust IPM Framework and Efficient Implementation
• Fast and Near-Optimal Diagonal Preconditioning
• Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent