{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T04:06:15Z","timestamp":1747800375876},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T00:00:00Z","timestamp":1627603200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T00:00:00Z","timestamp":1627603200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,9]]},"DOI":"10.1007\/s10107-021-01686-3","type":"journal-article","created":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T10:06:25Z","timestamp":1627639585000},"page":"243-281","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Convergence rate of block-coordinate maximization Burer\u2013Monteiro method for solving large SDPs"],"prefix":"10.1007","volume":"195","author":[{"given":"Murat A.","family":"Erdogdu","sequence":"first","affiliation":[]},{"given":"Asuman","family":"Ozdaglar","sequence":"additional","affiliation":[]},{"given":"Pablo A.","family":"Parrilo","sequence":"additional","affiliation":[]},{"given":"Nuri Denizcan","family":"Vanli","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,30]]},"reference":[{"issue":"3","key":"1686_CR1","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s10208-005-0179-9","volume":"7","author":"P-A Absil","year":"2007","unstructured":"Absil, P.-A., Baker, C.G., Gallivan, K.A.: Trust-region methods on Riemannian manifolds. Found. Comput. Math. 7(3), 303\u2013330 (2007)","journal-title":"Found. Comput. Math."},{"key":"1686_CR2","volume-title":"Optimization Algorithms on Matrix Manifolds","author":"P-A Absil","year":"2007","unstructured":"Absil, P.-A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton (2007)"},{"issue":"1","key":"1686_CR3","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF02614432","volume":"77","author":"F Alizadeh","year":"1997","unstructured":"Alizadeh, F., Haeberly, J.-P.A., Overton, M.L.: Complementarity and nondegeneracy in semidefinite programming. Math. Program. 77(1), 111\u2013128 (1997)","journal-title":"Math. Program."},{"issue":"4","key":"1686_CR4","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1137\/S1052623499359178","volume":"10","author":"M Anitescu","year":"2000","unstructured":"Anitescu, M.: Degenerate nonlinear programming with a quadratic growth condition. SIAM J. Optim. 10(4), 1116\u20131135 (2000)","journal-title":"SIAM J. Optim."},{"key":"1686_CR5","doi-asserted-by":"crossref","unstructured":"Arora, S., Hazan, E., Kale, S.: Fast algorithms for approximate semidefiniite programming using the multiplicative weights update method. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS\u201905, pp. 339\u2013348 (2005)","DOI":"10.1109\/SFCS.2005.35"},{"key":"1686_CR6","unstructured":"Bandeira, A.S., Boumal, N., Voroninski, V.: On the low-rank approach for semidefinite programs arising in synchronization and community detection. arXiv:1602.04426 (2016)"},{"issue":"2","key":"1686_CR7","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/BF02574037","volume":"13","author":"AI Barvinok","year":"1995","unstructured":"Barvinok, A.I.: Problems of distance geometry and convex properties of quadratic maps. Discrete Comput. Geom. 13(2), 189\u2013202 (1995)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"1686_CR8","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1287\/moor.20.4.801","volume":"20","author":"JF Bonnans","year":"1995","unstructured":"Bonnans, J.F., Ioffe, A.: Second-order sufficiency and quadratic growth for nonisolated minima. Math. Oper. Res. 20(4), 801\u2013817 (1995)","journal-title":"Math. Oper. Res."},{"key":"1686_CR9","unstructured":"Boumal, N., Absil, P.-A., Cartis, C.: Global rates of convergence for nonconvex optimization on manifolds. arXiv preprint arXiv:1605.08101 (2016)"},{"key":"1686_CR10","first-page":"1455","volume":"15","author":"N Boumal","year":"2014","unstructured":"Boumal, N., Mishra, B., Absil, P.-A., Sepulchre, R.: Manopt, a Matlab toolbox for optimization on manifolds. J. Mach. Learn. Res. 15, 1455\u20131459 (2014)","journal-title":"J. Mach. Learn. Res."},{"key":"1686_CR11","unstructured":"Boumal, N., Voroninski, V., Bandeira, A.S.: The non-convex Burer\u2013Monteiro approach works on smooth semidefinite programs. In: Advances in Neural Information Processing Systems, pp. 2757\u20132765 (2016)"},{"key":"1686_CR12","doi-asserted-by":"crossref","unstructured":"Boumal, N., Voroninski, V., Bandeira, A.S.: Deterministic guarantees for Burer\u2013Monteiro factorizations of smooth semidefinite programs. arXiv preprint arXiv:1804.02008 (2018)","DOI":"10.1002\/cpa.21830"},{"key":"1686_CR13","doi-asserted-by":"crossref","unstructured":"Briat, C.: Linear Parameter-Varying and Time-Delay Systems. Springer (2014)","DOI":"10.1007\/978-3-662-44050-6"},{"key":"1686_CR14","doi-asserted-by":"crossref","unstructured":"Bri\u00ebt, J., de Oliveira Filho, F.M., Vallentin, F.: The positive semidefinite grothendieck problem with rank constraint. In: Automata, Languages and Programming, pp. 31\u201342 (2010)","DOI":"10.1007\/978-3-642-14165-2_4"},{"issue":"2","key":"1686_CR15","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s10107-002-0352-8","volume":"95","author":"S Burer","year":"2003","unstructured":"Burer, S., Monteiro, R.D.C.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95(2), 329\u2013357 (2003)","journal-title":"Math. Program."},{"issue":"3","key":"1686_CR16","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/s10107-004-0564-1","volume":"103","author":"S Burer","year":"2005","unstructured":"Burer, S., Monteiro, R.D.C.: Local minima and convergence in low-rank semidefinite programming. Math. Program. 103(3), 427\u2013444 (2005)","journal-title":"Math. Program."},{"key":"1686_CR17","unstructured":"Cifuentes, D., Moitra, A.: Polynomial time guarantees for the Burer\u2013Monteiro method. arXiv preprint arXiv:1912.01745 (2019)"},{"issue":"3","key":"1686_CR18","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/j.acha.2012.06.003","volume":"34","author":"ES Coakley","year":"2013","unstructured":"Coakley, E.S., Rokhlin, V.: A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices. Appl. Comput. Harmon. Anal. 34(3), 379\u2013414 (2013)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"1686_CR19","unstructured":"Erdogdu, M.A., Deshpande, Y., Montanari, A.: Inference in graphical models via semidefinite programming hierarchies. In: Advances in Neural Information Processing Systems, pp. 416\u2013424 (2017)"},{"key":"1686_CR20","unstructured":"Gamarnik, D., Li, Q.: On the max-cut of sparse random graphs. arXiv preprint arXiv:1411.1698 (2014)"},{"key":"1686_CR21","unstructured":"Garber, D., Hazan, E.: Approximating semidefinite programs in sublinear time. In: Proceedings of the 24th International Conference on Neural Information Processing Systems, NIPS\u201911, pp. 1080\u20131088 (2011)"},{"issue":"6","key":"1686_CR22","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"1686_CR23","unstructured":"Gurbuzbalaban, M., Ozdaglar, A., Parrilo, P.A., Vanli, N.D.: When cyclic coordinate descent outperforms randomized coordinate descent. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, and (eds.) Advances in Neural Information Processing Systems, volume\u00a030, pp. 6999\u20137007. Curran Associates, Inc. (2017)"},{"key":"1686_CR24","first-page":"03","volume":"181","author":"M Gurbuzbalaban","year":"2018","unstructured":"Gurbuzbalaban, M., Ozdaglar, A., Vanli, N.D., Wright, S.J.: Randomness and permutations in coordinate descent methods. Math. Program. 181, 03 (2018)","journal-title":"Math. Program."},{"issue":"16","key":"1686_CR25","doi-asserted-by":"publisher","first-page":"E2218","DOI":"10.1073\/pnas.1523097113","volume":"113","author":"A Javanmard","year":"2016","unstructured":"Javanmard, A., Montanari, A., Ricci-Tersenghi, F.: Phase transitions in semidefinite relaxations. Proc. Natl. Acad. Sci. 113(16), E2218\u2013E2223 (2016)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"5","key":"1686_CR26","doi-asserted-by":"publisher","first-page":"2327","DOI":"10.1137\/080731359","volume":"20","author":"M Journee","year":"2010","unstructured":"Journee, M., Bach, F., Absil, P.-A., Sepulchre, R.: Low-rank optimization on the cone of positive semidefinite matrices. SIAM J. Optim. 20(5), 2327\u20132351 (2010)","journal-title":"SIAM J. Optim."},{"key":"1686_CR27","doi-asserted-by":"crossref","unstructured":"Klein, P., Lu, H.-I.: Efficient approximation algorithms for semidefinite programs arising from MAX CUT and COLORING. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC\u201996, pp. 338\u2013347. ACM, New York, NY, USA (1996)","DOI":"10.1145\/237814.237980"},{"issue":"4","key":"1686_CR28","doi-asserted-by":"publisher","first-page":"1094","DOI":"10.1137\/0613066","volume":"13","author":"J Kuczy\u0144ski","year":"1992","unstructured":"Kuczy\u0144ski, J., Wo\u017aniakowski, H.: Estimating the largest eigenvalues by the power and Lanczos algorithms with a random start. SIAM J. Matrix Anal. Appl. 13(4), 1094\u20131122 (1992)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1686_CR29","first-page":"07","volume":"39","author":"C-P Lee","year":"2016","unstructured":"Lee, C.-P., Wright, S.J.: Random permutations fix a worst case for cyclic coordinate descent. IMA J. Numer. Anal. 39, 07 (2016)","journal-title":"IMA J. Numer. Anal."},{"key":"1686_CR30","unstructured":"Lee, J.D., Simchowitz, M., Jordan, M.I., Recht, B.: Gradient descent only converges to minimizers. In: 29th Annual Conference on Learning Theory, vol.\u00a049, pp. 1246\u20131257. PMLR (2016)"},{"key":"1686_CR31","unstructured":"Lu, Z., Xiao, L.: Randomized block coordinate non-monotone gradient method for a class of nonlinear programming. Technical Report MSR-TR-2013-66 (2013)"},{"key":"1686_CR32","unstructured":"Mei, S., Misiakiewicz, T., Montanari, A., Oliveira, R.I.: Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality. arXiv preprint arXiv:1703.08729 (2017)"},{"key":"1686_CR33","unstructured":"Montanari, A.: A Grothendieck-type inequality for local maxima. arXiv preprint arXiv:1603.04064 (2016)"},{"issue":"2","key":"1686_CR34","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-003-0387-5","volume":"96","author":"PA Parrilo","year":"2003","unstructured":"Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96(2), 293\u2013320 (2003)","journal-title":"Math. Program."},{"issue":"2","key":"1686_CR35","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1287\/moor.23.2.339","volume":"23","author":"G Pataki","year":"1998","unstructured":"Pataki, G.: On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper. Res. 23(2), 339\u2013358 (1998)","journal-title":"Math. Oper. Res."},{"key":"1686_CR36","first-page":"05","volume":"61","author":"A Patrascu","year":"2013","unstructured":"Patrascu, A., Necoara, I.: Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization. J. Glob. Optim. 61, 05 (2013)","journal-title":"J. Glob. Optim."},{"key":"1686_CR37","unstructured":"Pumir, T., Jelassi, S., Boumal, N.: Smoothed analysis of the low-rank approach for smooth semidefinite programs. In: Advances in Neural Information Processing Systems, pp. 2281\u20132290 (2018)"},{"key":"1686_CR38","first-page":"07","volume":"144","author":"P Richt\u00e1rik","year":"2011","unstructured":"Richt\u00e1rik, P., Tak\u00e1\u010d, M.: Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Math. Program. 144, 07 (2011)","journal-title":"Math. Program."},{"key":"1686_CR39","doi-asserted-by":"crossref","unstructured":"Steurer, D.: Fast SDP algorithms for constraint satisfaction problems. In: Proceedings of the Twenty-First Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 684\u2013697 (2010)","DOI":"10.1137\/1.9781611973075.56"},{"issue":"4","key":"1686_CR40","doi-asserted-by":"publisher","first-page":"1454","DOI":"10.1137\/17M1111590","volume":"38","author":"JA Tropp","year":"2017","unstructured":"Tropp, J.A., Yurtsever, A., Udell, M., Cevher, V.: Practical sketching algorithms for low-rank matrix approximation. SIAM J. Matrix Anal. Appl. 38(4), 1454\u20131485 (2017)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1686_CR41","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s10107-007-0170-0","volume":"117","author":"P Tseng","year":"2009","unstructured":"Tseng, P., Yun, S.: A coordinate gradient descent method for nonsmooth separable minimization. Math. Program. 117, 387\u2013423 (2009)","journal-title":"Math. Program."},{"issue":"1","key":"1686_CR42","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1137\/1038003","volume":"38","author":"L Vandenberghe","year":"1996","unstructured":"Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38(1), 49\u201395 (1996)","journal-title":"SIAM Rev."},{"key":"1686_CR43","unstructured":"Wang, P.-W., Chang, W.-C., Kolter, J.Z.: The mixing method: coordinate descent for low-rank semidefinite programming. arXiv preprint arXiv:1706.00476 (2017)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01686-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01686-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01686-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T15:30:35Z","timestamp":1666366235000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01686-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,30]]},"references-count":43,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["1686"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01686-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,30]]},"assertion":[{"value":"10 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}