Reexamining Low Rank Matrix Factorization for Trace Norm Regularization
Preprint
Abstract
Trace norm regularization is a widely used approach for learning low rank matrices. A standard optimization strategy is based on formulating the problem as one of low rank matrix factorization which, however, leads to a non-convex problem. In practice this approach works well, and it is often computationally faster than standard convex solvers such as proximal gradient methods. Nevertheless, it is not guaranteed to converge to a global optimum, and the optimization can be trapped at poor stationary points. In this paper we show that it is possible to characterize all critical points of the non-convex problem. This allows us to provide an efficient criterion to determine whether a critical point is also a global minimizer. Our analysis suggests an iterative meta-algorithm that dynamically expands the parameter space and allows the optimization to escape any non-global critical point, thereby converging to a global minimizer. The algorithm can be applied to problems such as matrix completion or multitask learning, and our analysis holds for any random initialization of the factor matrices. Finally, we confirm the good performance of the algorithm on synthetic and real datasets.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz InequalityMathematics of Operations Research, 2010
- Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexityTransactions of the American Mathematical Society, 2009
- Matrix Factorization Techniques for Recommender SystemsComputer, 2009
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse ProblemsSIAM Journal on Imaging Sciences, 2009
- Convex multi-task feature learningMachine Learning, 2008
- On the convergence of the proximal algorithm for nonsmooth functions involving analytic featuresMathematical Programming, 2007
- Summing and Nuclear Norms in Banach Space Theory1987
- Some NP-complete problems in quadratic and nonlinear programmingMathematical Programming, 1987