A Nonconvex Optimization Framework for Low Rank Matrix Estimation
We study the estimation of low rank matrices via nonconvex optimization. Compared with convex relaxation, nonconvex optimization exhibits superior empirical performance for large scale instances of low rank matrix estimation. However, the understanding of its theoretical guarantees are limited. In this paper, we define the notion of projected oracle divergence based on which we establish sufficient conditions for the success of nonconvex optimization. We illustrate the consequences of this general framework for matrix sensing and completion. In particular, we prove that a broad class of nonconvex optimization algorithms, including alternating minimization and gradient-type methods, geometrically converge to the global optimum and exactly recover the true low rank matrices under standard conditions.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
We propose a unified framework for estimating low-rank matrices through nonconvex optimization based on gradient descent algorithm. Our framework is quite general and can be applied to both noisy and noiseless observatio…
Matrix CompletionConvexity in Disguise: A Theoretical Framework for Nonconvex Low-Rank Matrix Estimation
Nonconvex methods have emerged as a dominant approach for low-rank matrix estimation, a problem that arises widely in machine learning and AI for learning and representing high-dimensional data. Existing analyses for the…
Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation
We present a unified framework for low-rank matrix estimation with nonconvex penalties. We first prove that the proposed estimator attains a faster statistical rate than the traditional low-rank matrix estimator with nuc…
Matrix CompletionNonconvex Matrix Completion with Linearly Parameterized Factors
Techniques of matrix completion aim to impute a large portion of missing entries in a data matrix through a small portion of observed ones. In practice including collaborative filtering, prior information and special str…
Collaborative FilteringMatrix CompletionModel-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA
This work studies low-rank approximation of a positive semidefinite matrix from partial entries via nonconvex optimization. We characterized how well local-minimum based low-rank factorization approximates a fixed positi…
ClusteringDimensionality ReductionMatrix Completion