A new complexity metric for nonconvex rank-one generalized matrix completion. (English) Zbl 07915915
Summary: In this work, we develop a new complexity metric for an important class of low-rank matrix optimization problems in both symmetric and asymmetric cases, where the metric aims to quantify the complexity of the nonconvex optimization landscape of each problem and the success of local search methods in solving the problem. The existing literature has focused on two recovery guarantees. The RIP constant is commonly used to characterize the complexity of matrix sensing problems. On the other hand, the incoherence and the sampling rate are used when analyzing matrix completion problems. The proposed complexity metric has the potential to generalize these two notions and also applies to a much larger class of problems. To mathematically study the properties of this metric, we focus on the rank-1 generalized matrix completion problem and illustrate the usefulness of the new complexity metric on three types of instances, namely, instances with the RIP condition, instances obeying the Bernoulli sampling model, and a synthetic example. We show that the complexity metric exhibits a consistent behavior in the three cases, even when other existing conditions fail to provide theoretical guarantees. These observations provide a strong implication that the new complexity metric has the potential to generalize various conditions of optimization complexity proposed for different applications. Furthermore, we establish theoretical results to provide sufficient conditions and necessary conditions for the existence of spurious solutions in terms of the proposed complexity metric. This contrasts with the RIP and incoherence conditions that fail to provide any necessary condition.
MSC:
| 65F55 | Numerical methods for low-rank matrix approximation; matrix compression |
| 15A83 | Matrix completion problems |
| 65K10 | Numerical optimization and variational techniques |
| 90C26 | Nonconvex programming, global optimization |
References:
| [1] | Agarwal, A.; Anandkumar, A.; Jain, P.; Netrapalli, P., Learning sparsely used overcomplete dictionaries via alternating minimization, SIAM J. Optim., 26, 4, 2775-2799, 2016 · Zbl 1358.90104 · doi:10.1137/140979861 |
| [2] | Ahn, K., Suarez, F.: Riemannian perspective on matrix factorization. arXiv preprint arXiv:2102.00937 (2021) |
| [3] | Aigner, M., Turán’s graph theorem, Am. Math. Mon., 102, 9, 808-816, 1995 · Zbl 0843.05053 |
| [4] | Ajayi, T., Mildebrath, D., Kyrillidis, A., Ubaru, S., Kollias, G., Bouchard, K.: Provably convergent acceleration in factored gradient descent with applications in matrix sensing. arXiv preprint arXiv:1806.00534 (2018) |
| [5] | Allen-Zhu, Z., Li, Y.: Neon2: Finding local minima via first-order oracles. Adv. Neural Inform. Process. Syst. 31 (2018) |
| [6] | Bi, Y., Lavaei, J.: On the absence of spurious local minima in nonlinear low-rank matrix recovery problems. In: International Conference on Artificial Intelligence and Statistics, pp. 379-387. PMLR (2021) |
| [7] | Bi, Y., Zhang, H., Lavaei, J.: Local and global linear convergence of general low-rank matrix recovery problems. In: Proceedings of 36th AAAI Conference on Artificial Intelligence (AAAI), pp. 1-9. Vancouver, Canada (2022) |
| [8] | Burer, S.; Monteiro, RD, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math. Program., 95, 2, 329-357, 2003 · Zbl 1030.90077 · doi:10.1007/s10107-002-0352-8 |
| [9] | Candès, EJ; Li, X.; Ma, Y.; Wright, J., Robust principal component analysis?, J. ACM (JACM), 58, 3, 1-37, 2011 · Zbl 1327.62369 · doi:10.1145/1970392.1970395 |
| [10] | Candes, EJ; Li, X.; Soltanolkotabi, M., Phase retrieval via wirtinger flow: theory and algorithms, IEEE Trans. Inform. Theory, 61, 4, 1985-2007, 2015 · Zbl 1359.94069 · doi:10.1109/TIT.2015.2399924 |
| [11] | Candes, EJ; Plan, Y., Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements, IEEE Trans. Inform. Theory, 57, 4, 2342-2359, 2011 · Zbl 1366.90160 · doi:10.1109/TIT.2011.2111771 |
| [12] | Candès, EJ; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 6, 717-772, 2009 · Zbl 1219.90124 · doi:10.1007/s10208-009-9045-5 |
| [13] | Candès, EJ; Tao, T., The power of convex relaxation: near-optimal matrix completion, IEEE Trans. Inform. Theory, 56, 5, 2053-2080, 2010 · Zbl 1366.15021 · doi:10.1109/TIT.2010.2044061 |
| [14] | Cartis, C.; Gould, NI; Toint, PL, Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results, Math. Program., 127, 2, 245-295, 2011 · Zbl 1229.90192 · doi:10.1007/s10107-009-0286-5 |
| [15] | Charisopoulos, V.; Chen, Y.; Davis, D.; Díaz, M.; Ding, L.; Drusvyatskiy, D., Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence, Found. Comput. Math., 21, 6, 1505-1593, 2021 · Zbl 1480.65100 · doi:10.1007/s10208-020-09490-9 |
| [16] | Chen, J.; Li, X., Model-free nonconvex matrix completion: local minima analysis and applications in memory-efficient kernel PCA, J. Mach. Learn. Res., 20, 142, 1-39, 2019 · Zbl 1441.62157 |
| [17] | Chen, J.; Liu, D.; Li, X., Nonconvex rectangular matrix completion via gradient descent without \(\ell_{2,\infty }\) regularization, IEEE Trans. Inform. Theory, 66, 9, 5806-5841, 2020 · Zbl 1448.90078 · doi:10.1109/TIT.2020.2992234 |
| [18] | Chen, Y.; Chi, Y., Harnessing structures in big data via guaranteed low-rank matrix estimation: recent theory and fast algorithms via convex and nonconvex optimization, IEEE Signal Process. Mag., 35, 4, 14-31, 2018 · doi:10.1109/MSP.2018.2821706 |
| [19] | Chen, Y.; Chi, Y.; Fan, J.; Ma, C., Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval, Math. Program., 176, 1, 5-37, 2019 · Zbl 1415.90086 · doi:10.1007/s10107-019-01363-6 |
| [20] | Chen, Y.; Chi, Y.; Fan, J.; Ma, C.; Yan, Y., Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization, SIAM J. Optim., 30, 4, 3098-3121, 2020 · Zbl 1477.90060 · doi:10.1137/19M1290000 |
| [21] | Chen, Y.; Fan, J.; Ma, C.; Yan, Y., Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data, Ann. Stat., 49, 5, 2948-2971, 2021 · Zbl 1486.62181 · doi:10.1214/21-AOS2066 |
| [22] | Chi, Y.; Lu, YM; Chen, Y., Nonconvex optimization meets low-rank matrix factorization: an overview, IEEE Trans. Signal Process., 67, 20, 5239-5269, 2019 · Zbl 1543.90234 · doi:10.1109/TSP.2019.2937282 |
| [23] | Chou, H.H., Gieshoff, C., Maly, J., Rauhut, H.: Gradient descent for deep matrix factorization: dynamics and implicit bias towards low rank. arXiv preprint arXiv:2011.13772 (2020) |
| [24] | Fattahi, S., Sojoudi, S.: Exact guarantees on the absence of spurious local minima for non-negative rank-1 robust principal component analysis. J. Mach. Learn. Res. (2020) · Zbl 1499.62199 |
| [25] | Ge, R., Jin, C., Zheng, Y.: No spurious local minima in nonconvex low rank problems: a unified geometric analysis. In: International Conference on Machine Learning, pp. 1233-1242. PMLR (2017) |
| [26] | Ge, R., Lee, J.D., Ma, T.: Matrix completion has no spurious local minimum. Adv. Neural Inform. Process. Syst. 2981-2989 (2016) |
| [27] | Hardt, M.: Understanding alternating minimization for matrix completion. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 651-660. IEEE (2014) |
| [28] | Hardt, M., Wootters, M.: Fast matrix completion without the condition number. In: Conference on Learning Theory, pp. 638-678. PMLR (2014) |
| [29] | Hou, T.Y., Li, Z., Zhang, Z.: Fast global convergence for low-rank matrix recovery via riemannian gradient descent with random initialization. arXiv preprint arXiv:2012.15467 (2020) |
| [30] | Jain, P., Meka, R., Dhillon, I.: Guaranteed rank minimization via singular value projection. Adv. Neural Inform. Process. Syst. 23 (2010) |
| [31] | 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, pp. 665-674. (2013) · Zbl 1293.65073 |
| [32] | Jin, C., Ge, R., Netrapalli, P., Kakade, S.M., Jordan, M.I.: How to escape saddle points efficiently. In: International Conference on Machine Learning, pp. 1724-1732. PMLR (2017) |
| [33] | Jin, C., Netrapalli, P., Jordan, M.I.: Accelerated gradient descent escapes saddle points faster than gradient descent. In: Conference On Learning Theory, pp. 1042-1085. PMLR (2018) |
| [34] | Lee, J.D., Simchowitz, M., Jordan, M.I., Recht, B.: Gradient descent only converges to minimizers. In: Conference on Learning Theory, pp. 1246-1257. PMLR (2016) |
| [35] | Levin, E., Kileel, J., Boumal, N.: The effect of smooth parametrizations on nonconvex optimization landscapes. arXiv preprint arXiv:2207.03512 (2022) |
| [36] | Li, X.; Zhu, Z.; Man-Cho So, A.; Vidal, R., Nonconvex robust low-rank matrix recovery, SIAM J. Optim., 30, 1, 660-686, 2020 · Zbl 07175265 · doi:10.1137/18M1224738 |
| [37] | Li, Y., Ma, T., Zhang, H.: Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations. In: Conference On Learning Theory, pp. 2-47. PMLR (2018) |
| [38] | Luo, Y., Li, X., Zhang, A.R.: Nonconvex factorization and manifold formulations are almost equivalent in low-rank matrix optimization. arXiv preprint arXiv:2108.01772 (2021) |
| [39] | Ma, J., Fattahi, S.: Sign-rip: a robust restricted isometry property for low-rank matrix recovery. arXiv preprint arXiv:2102.02969 (2021) |
| [40] | Ma, Z., Bi, Y., Lavaei, J., Sojoudi, S.: Sharp restricted isometry property bounds for low-rank matrix recovery problems with corrupted measurements. arXiv preprint arXiv:2105.08232 (2021) |
| [41] | Netrapalli, P., Jain, P., Sanghavi, S.: Phase retrieval using alternating minimization. Adv. Neural Inform. Process. Syst. 26 (2013) |
| [42] | Netrapalli, P., Un, N., Sanghavi, S., Anandkumar, A., Jain, P.: Non-convex robust PCA. Adv. Neural Inform. Process. Syst. 27 (2014) |
| [43] | Recht, B.; Fazel, M.; Parrilo, PA, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 3, 471-501, 2010 · Zbl 1198.90321 · doi:10.1137/070697835 |
| [44] | Renegar, J., Linear programming, complexity theory and elementary functional analysis, Math. Program., 70, 1, 279-351, 1995 · Zbl 0855.90085 · doi:10.1007/BF01585941 |
| [45] | Renegar, J., Condition numbers, the barrier method, and the conjugate-gradient method, SIAM J. Optim., 6, 4, 879-912, 1996 · Zbl 0872.65048 · doi:10.1137/S105262349427532X |
| [46] | Stöger, D., Soltanolkotabi, M.: Small random initialization is akin to spectral learning: optimization and generalization guarantees for overparameterized low-rank matrix reconstruction. Adv. Neural Inform. Process. Syst. 34 (2021) |
| [47] | Sun, J.; Qu, Q.; Wright, J., Complete dictionary recovery over the sphere I: overview and the geometric picture, IEEE Trans. Inform. Theory, 63, 2, 853-884, 2016 · Zbl 1364.94164 · doi:10.1109/TIT.2016.2632162 |
| [48] | Sun, J.; Qu, Q.; Wright, J., A geometric analysis of phase retrieval, Found. Comput. Math., 18, 5, 1131-1198, 2018 · Zbl 1401.94049 · doi:10.1007/s10208-017-9365-9 |
| [49] | Sun, R.; Luo, ZQ, Guaranteed matrix completion via non-convex factorization, IEEE Trans. Inform. Theory, 62, 11, 6535-6579, 2016 · Zbl 1359.94179 · doi:10.1109/TIT.2016.2598574 |
| [50] | Tong, T.; Ma, C.; Chi, Y., Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent, J. Mach. Learn. Res., 22, 150, 1-63, 2021 · Zbl 07415093 |
| [51] | Tong, T.; Ma, C.; Chi, Y., Low-rank matrix recovery with scaled subgradient methods: fast and robust convergence without the condition number, IEEE Trans. Signal Process., 69, 2396-2409, 2021 · Zbl 1543.65063 · doi:10.1109/TSP.2021.3071560 |
| [52] | Tong, T., Ma, C., Prater-Bennette, A., Tripp, E., Chi, Y.: Scaling and scalability: provable nonconvex low-rank tensor estimation from incomplete measurements. arXiv preprint arXiv:2104.14526 (2021) |
| [53] | Tu, S., Boczar, R., Simchowitz, M., Soltanolkotabi, M., Recht, B.: Low-rank solutions of linear matrix equations via procrustes flow. In: International Conference on Machine Learning, pp. 964-973. PMLR (2016) |
| [54] | Wei, K.; Cai, JF; Chan, TF; Leung, S., Guarantees of riemannian optimization for low rank matrix recovery, SIAM J. Matrix Anal. Appl., 37, 3, 1198-1222, 2016 · Zbl 1347.65109 · doi:10.1137/15M1050525 |
| [55] | Wei, K., Cai, J.F., Chan, T.F., Leung, S.: Guarantees of riemannian optimization for low rank matrix completion. Inverse Probl. Ima. 14(2) (2020) · Zbl 1439.65059 |
| [56] | Yalcin, B., Zhang, H., Lavaei, J., Sojoudi, S.: Factorization approach for low-complexity matrix completion problems: exponential number of spurious solutions and failure of gradient methods. In: International Conference on Artificial Intelligence and Statistics, pp. 1-9. PMLR (2022) |
| [57] | Yi, X., Park, D., Chen, Y., Caramanis, C.: Fast algorithms for robust pca via gradient descent. Adv. Neural Inform. Process. Syst. 29 (2016) |
| [58] | Yurtsever, A.; Tropp, JA; Fercoq, O.; Udell, M.; Cevher, V., Scalable semidefinite programming, SIAM J. Math. Data Sci., 3, 1, 171-200, 2021 · Zbl 1470.90068 · doi:10.1137/19M1305045 |
| [59] | Zhang, H., Bi, Y., Lavaei, J.: General low-rank matrix optimization: geometric analysis and sharper bounds. Adv. Neural Inform. Process. Syst. 34 (2021) |
| [60] | Zhang, H., Yalcin, B., Lavaei, J., Sojoudi, S.: A new complexity metric for nonconvex rank-one generalized matrix completion. arXiv preprint arXiv:2204.02364 (2022) |
| [61] | Zhang, J., Fattahi, S., Zhang, R.: Preconditioned gradient descent for over-parameterized nonconvex matrix factorization. Adv. Neural Inform. Process. Syst. 34 (2021) |
| [62] | Zhang, RY; Sojoudi, S.; Lavaei, J., Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery, J. Mach. Learn. Res., 20, 114, 1-34, 2019 · Zbl 1440.90056 |
| [63] | Zheng, Q., Lafferty, J.: A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements. In: Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume 1, pp. 109-117 (2015) |
| [64] | Zhu, Z.; Li, Q.; Tang, G.; Wakin, MB, Global optimality in low-rank matrix optimization, IEEE Trans. Signal Process., 66, 13, 3614-3628, 2018 · Zbl 1414.90297 · doi:10.1109/TSP.2018.2835403 |
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.
