Leave-one-out Approach for Matrix Completion: Primal and Dual Analysis
This provides improved theoretical guarantees for matrix completion algorithms, addressing a foundational problem in machine learning with applications in recommendation systems and data imputation, though it is incremental in refining existing methods.
The paper tackles low-rank matrix completion by introducing a Leave-one-out analysis technique to obtain fine-grained entrywise bounds for iterative stochastic procedures, establishing the first convergence guarantee for Projected Gradient Descent without regularization and showing nuclear norm minimization recovers a matrix with O(μr log(μr) d log d) observed entries, which is optimal in dimension and independent of condition number.
In this paper, we introduce a powerful technique based on Leave-one-out analysis to the study of low-rank matrix completion problems. Using this technique, we develop a general approach for obtaining fine-grained, entrywise bounds for iterative stochastic procedures in the presence of probabilistic dependency. We demonstrate the power of this approach in analyzing two of the most important algorithms for matrix completion: (i) the non-convex approach based on Projected Gradient Descent (PGD) for a rank-constrained formulation, also known as the Singular Value Projection algorithm, and (ii) the convex relaxation approach based on nuclear norm minimization (NNM). Using this approach, we establish the first convergence guarantee for the original form of PGD without regularization or sample splitting}, and in particular shows that it converges linearly in the infinity norm. For NNM, we use this approach to study a fictitious iterative procedure that arises in the dual analysis. Our results show that \NNM recovers an $ d $-by-$ d $ rank-$ r $ matrix with $\mathcal{O}(μr \log(μr) d \log d )$ observed entries. This bound has optimal dependence on the matrix dimension and is independent of the condition number. To the best of our knowledge, this is the first sample complexity result for a tractable matrix completion algorithm that satisfies these two properties simultaneously.