Reexamining Low Rank Matrix Factorization for Trace Norm Regularization
Reexamining Low Rank Matrix Factorization for Trace Norm Regularization
复制标题
DOI：
10.3934/mine.2023053
复制
发表时间：
2017-06
期刊：
影响因子：
--
通讯作者：
C. Ciliberto;Dimitris Stamos;M. Pontil
中科院分区：
文献类型：
--
作者：
C. Ciliberto;Dimitris Stamos;M. Pontil
迹范数正则化是一种广泛使用的学习低秩矩阵的方法。一个标准的优化策略是基于制定的问题，作为一个低秩矩阵分解，然而，导致一个非凸问题。在实践中，这种方法工作得很好，它通常比标准的凸解算器（如近似梯度方法）计算速度更快。然而，它不能保证收敛到全局最优值，并且优化可能被困在差的稳定点。在本文中，我们表明，它是可能的所有临界点的非凸问题的特征。这使我们能够提供一个有效的标准，以确定是否临界点也是一个全球性的极小。我们的分析提出了一种迭代元算法，该算法动态扩展参数空间，并允许优化避开任何非全局临界点，从而收敛到全局最小值。该算法可以应用于矩阵完成或多任务学习等问题，我们的分析适用于任何随机初始化的因素矩阵。最后，我们证实了良好的性能的算法在合成和真实的数据集。
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.