Non-Convex Matrix Completion Against a Semi-Random Adversary

2018/03/28 by Yu Cheng, Cheng, Yu, Rong Ge +1 · 1 citation
Computer Science · #Computability, Logic, AI Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography

paper · pdf · doi:10.48550/arxiv.1803.10846

openalex publication_date 2018/03/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

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

Cited by

• The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination

Related

• Matrix Completion has No Spurious Local Minimum
• Non-Convex Optimizations for Machine Learning with Theoretical Guarantee: Robust Matrix Completion and Neural Network Learning
• Robust Matrix Completion
• Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization