Quartic first-order methods for low-rank minimization. (English) Zbl 1470.90050
Summary: We study a general nonconvex formulation for low-rank minimization problems. We use recent results on non-Euclidean first-order methods to provide efficient and scalable algorithms. Our approach uses the geometry induced by the Bregman divergence of well-chosen kernel functions; for unconstrained problems, we introduce a novel family of Gram quartic kernels that improve numerical performance. Numerical experiments on Euclidean distance matrix completion and symmetric nonnegative matrix factorization show that our algorithms scale well and reach state-of-the-art performance when compared to specialized methods.
MSC:
| 90C06 | Large-scale problems in mathematical programming |
| 90C26 | Nonconvex programming, global optimization |
Keywords:
Bregman first-order methods; low-rank minimization; Burer-Monteiro; matrix factorization; Euclidean distance matrix completionReferences:
| [1] | Candès, E.J., Recht, B.: Exact Matrix Completion Via Convex Optimization. Found Comput Math, 9(6), (2009) · Zbl 1219.90124 |
| [2] | Cai, Jian-Feng; Candès, Emmanuel J.; Shen, Zuowei, A Singular Value Thresholding Algorithm for Matrix Completion, SIAM Journal on Optimization, 20, 4, 1956-1982 (2010) · Zbl 1201.90155 · doi:10.1137/080738970 |
| [3] | Jain, P., Netrapalli, P., Sanghavi, S.: Low-rank Matrix Completion using Alternating Minimization. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, pages 665—-674, (2013) · Zbl 1293.65073 |
| [4] | Recht, Benjamin; Fazel, Maryam; Parrilo, Pablo A., Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization, SIAM Review, 52, 3, 471-501 (2007) · Zbl 1198.90321 · doi:10.1137/070697835 |
| [5] | Mishra, B., Meyer, G., Sepulchre, R.: Low-rank optimization for distance matrix completion. In Proceedings of the IEEE Conference on Decision and Control, pages 4455-4460, (2011) |
| [6] | Fang, H.R., O’Leary, D.P.: Euclidean distance matrix completion problems. Optimization Methods and Software, 27(4):695-717, (2012) · Zbl 1252.49046 |
| [7] | Candès, Emmanuel J.; Li, Xiaodong; Soltanolkotabi, Mahdi, Phase retrieval via wirtinger flow: Theory and algorithms, IEEE Transactions on Information Theory, 61, 4, 1985-2007 (2015) · Zbl 1359.94069 · doi:10.1109/TIT.2015.2399924 |
| [8] | Chen, Y., Wainwright, M.J.: Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. arXiv preprintarXiv:1509.03025, (2015) |
| [9] | Burer, S., Monteiro, R.D.C.: Local Minima and Convergence in Low-Rank Semidefinite Programming. Mathematical Programming, 103(3):427-444, (2005) · Zbl 1099.90040 |
| [10] | Tu, S., Boczar, R., Simchowitz, M., Soltanolkotabi, M., Recht, B.: Low-rank Solutions of Linear Matrix Equations via Procrustes Flow. In Proceedings of the 33rd International Conference on International Conference on Machine Learning, pages 964-973, (2016) |
| [11] | Bhojanapalli, S.: Anastasios Kyrillidis, and Sujay Sanghavi. Dropping Convexity for Faster Semi-definite Optimization. JMLR: Workshop and Conference Proceedings, 40:1-53, (2016) |
| [12] | Zhao, Tuo; Wang, Zhaoran; Liu, Han, A Nonconvex Optimization Framework for Low Rank Matrix Estimation, Advances in Neural Information Processing Systems, 28, 559-567 (2015) |
| [13] | Sun, Ruoyu; Luo, Zhi-Quan, Guaranteed Matrix Completion via Nonconvex Factorization, IEEE Transactions on Information Theory, 62, 11, 6535-6579 (2016) · Zbl 1359.94179 · doi:10.1109/TIT.2016.2598574 |
| [14] | Zheng, Q., Lafferty, J.: Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent. arXiv preprintarXiv:1605.07051, (2016) |
| [15] | Park, D., Kyrillidis, A.: Constantine Caramanis, and Sujay Sanghavi. Finding low-rank solutions to matrix problems , efficiently and provably. arXiv preprintarXiv:1606.03168v1, (2016) |
| [16] | Zheng, Q., Lafferty, J.: A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements. In Advances in Neural Information Processing Systems 28, (2015) |
| [17] | Ge, R., Lee, J.D., Ma, T.: Matrix Completion has No Spurious Local Minimum. Advances in Neural Information Processing Systems, pages 2973-2981, (2016) |
| [18] | Bauschke, Heinz H.; Bolte, Jérôme; Teboulle, Marc, A Descent Lemma Beyond Lipschitz Gradient Continuity: First-Order Methods Revisited and Applications, Mathematics of Operations Research, 42, 2, 330-348 (2017) · Zbl 1364.90251 · doi:10.1287/moor.2016.0817 |
| [19] | Bolte, Jérôme; Sabach, Shoham; Teboulle, Marc; Vaisbourd, Yakov, First order methods beyond convexity and lipschitz gradient continuity with applications to quadratic inverse problems, SIAM Journal on Optimization, 28, 3, 2131-2151 (2018) · Zbl 1402.90118 · doi:10.1137/17M1138558 |
| [20] | Lin, C-J.: Projected Gradient Methods for Nonnegative Matrix Factorization. Neural Computation, (2007) · Zbl 1173.90583 |
| [21] | Van Nguyen, Quang, Forward-backward splitting with bregman distances, Vietnam Journal of Mathematics, 45, 3, 519-539 (2017) · Zbl 1371.90106 · doi:10.1007/s10013-016-0238-3 |
| [22] | Haihao, Lu; Freund, Robert M.; Nesterov, Yurii, Relatively-Smooth Convex Optimization by First-Order Methods, and Applications, SIAM Journal on Optimization, 28, 1, 333-354 (2018) · Zbl 1392.90090 · doi:10.1137/16M1099546 |
| [23] | Nesterov, Yurii, Introductory lectures on convex optimization: A basic course (2003), US: Springer, US · Zbl 1086.90045 |
| [24] | Auslender, Alfred; Teboulle, Marc, Interior gradient and proximal methods for convex and conic optimization, SIAM Journal on Optimization, 16, 3, 697-725 (2006) · Zbl 1113.90118 · doi:10.1137/S1052623403427823 |
| [25] | Hanzely, F., Richt, P., Xiao, L.: Accelerated Bregman proximal gradient methods for relatively smooth convex optimization. ArXiv preprintarXiv:1808.03045v1, (2018) |
| [26] | Mukkamala, M.C., Ochs, P., Pock, T., Sabach, S.: Convex-Concave Backtracking for Inertial Bregman Proximal Gradient Algorithms in Non-Convex Optimization. arXiv preprintarXiv:1904.03537, (2019) |
| [27] | Meka, R., Jain, P., Dhillon, I.S.: Guaranteed Rank Minimization via Singular Value Projection. NIPS, (2010) |
| [28] | Nesterov, Y.: Gradient methods for minimizing composite objective function. CORE Report, (2007) |
| [29] | Bolte, Jérôme; Daniilidis, Aris; Lewis, Adrian, The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems, SIAM Journal on Optimization, 17, 4, 1205-1223 (2007) · Zbl 1129.26012 · doi:10.1137/050644641 |
| [30] | Ding, C., He, X., Simon, H.: On the Equivalence of Nonnegative Matrix Factorization and Spectral Clustering. In Proceedings of the 2005 SIAM ICDM, number 4, pages 126-135, (2005) |
| [31] | He, Zhaoshui; Xie, Shengli; Zdunek, Rafal; Zhou, Guoxu; Cichocki, Andrzej, Symmetric nonnegative matrix factorization: Algorithms and applications to probabilistic clustering, IEEE Transactions on Neural Networks, 22, 12, 2117-2131 (2011) · doi:10.1109/TNN.2011.2169087 |
| [32] | Kuang, Da; Yun, Sangwoon; Park, Haesun, SymNMF: nonnegative low-rank approximation of a similarity matrix for graph clustering, Journal of Global Optimization, 62, 3, 545-574 (2015) · Zbl 1326.90080 · doi:10.1007/s10898-014-0247-2 |
| [33] | Kim, Jingu; Park, Haesun, Fast Nonnegative Matrix Factorization: An Active-set-like Method and Comparisons, SIAM Journal on Scientific Computing, 33, 6, 3261-3281 (2013) · Zbl 1232.65068 · doi:10.1137/110821172 |
| [34] | Andrzej Cichocki and Anh Huy Phan, Fast local algorithms for large scale nonnegative matrix and tensor factorizations (2009), Communications and Computer Sciences: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences |
| [35] | Vandaele, Arnaud; Gillis, Nicolas; Lei, Qi; Zhong, Kai; Dhillon, Inderjit, Efficient and non-convex coordinate descent for symmetric nonnegative matrix factorization, IEEE Transactions on Signal Processing, 64, 21, 5571-5584 (2016) · Zbl 1414.94636 · doi:10.1109/TSP.2016.2591510 |
| [36] | Songtao, Lu; Hong, Mingyi; Wang, Zhengdao, A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization : Convergence Analysis and Optimality, IEEE Transactions on Signal Processing, 65, 12, 2572-2576 (2017) · Zbl 1414.94392 |
| [37] | Zhu, Z., Li, X., Liu, K., Li, Q.: Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization. In Advances in Neural Information Processing Systems 31, (2018) |
| [38] | Bezanson, Stefan Karpinski Jeff; Edelman, Alan; Shah, Viral B., Julia : A Fresh Approach to Numerical Computing, SIAM Review, 59, 1, 65-98 (2017) · Zbl 1356.68030 · doi:10.1137/141000671 |
| [39] | Cai, D., Wang, X., He, X.: Probabilistic dyadic data analysis with local and global consistency. In Proceedings of the 26th Annual International Conference on Machine Learning (ICML’09), pages 105-112, (2009) |
| [40] | Cai, D., Mei, Q., Han, J., Zhai, C.: Modeling hidden topics on document manifold. In Proceeding of the 17th ACM conference on Information and knowledge management (CIKM’08), pages 911-920, (2008) |
| [41] | Cai, D., He, X., Zhang, W.V., Han, J.: Regularized locality preserving indexing via spectral regression. In Proceedings of the 16th ACM conference on Conference on information and knowledge management (CIKM’07), pages 741-750, (2007) |
| [42] | Cai, Deng; He, Xiaofei; Han, Jiawei, Document clustering using locality preserving indexing, IEEE Transactions on Knowledge and Data Engineering, 17, 12, 1624-1637 (2005) · doi:10.1109/TKDE.2005.198 |
| [43] | Zhu, Z., Li, X., Liu, K., Li, Q.: Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization. NIPS, (2018) |
| [44] | Hou Duo Qi and Xiaoming Yuan, Computing the nearest Euclidean distance matrix with low embedding dimensions, Mathematical Programming, 147, 1-2, 351-389 (2013) · Zbl 1304.49051 |
| [45] | Dokmanic, Ivan; Parhizkar, Reza; Ranieri, Juri; Vetterli, Martin, Euclidean Distance Matrices: Essential theory, algorithms, and applications, IEEE Signal Processing Magazine, 32, 6, 12-30 (2015) · doi:10.1109/MSP.2015.2398954 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
