{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:50:42Z","timestamp":1773798642541,"version":"3.50.1"},"reference-count":94,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics of OR"],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:p>In this paper, we develop two new randomized block-coordinate optimistic gradient algorithms to approximate a solution of nonlinear equations in large-scale settings, which are known as root-finding problems. Our first algorithm is nonaccelerated with constant step sizes and achieves a [Formula: see text] best-iterate convergence rate on [Formula: see text] when the underlying operator G is Lipschitz continuous and possesses a weak Minty solution, in which [Formula: see text] is the expectation and k is the iteration counter. Our second method is a new accelerated randomized block-coordinate optimistic gradient algorithm. We establish both [Formula: see text] and [Formula: see text] last-iterate convergence rates on both [Formula: see text] and [Formula: see text] for this algorithm under the co-coercivity of G. In addition, we prove that the iterate sequence [Formula: see text] converges to a solution almost surely and [Formula: see text] attains a [Formula: see text] almost sure convergence rate. Then, we apply our methods to a class of large-scale finite-sum inclusions, which covers prominent applications in machine learning, statistical learning, and network optimization, especially in federated learning. We obtain two new federated learning\u2013type algorithms and their convergence rate guarantees for solving this problem class. We test our algorithms on four numerical examples using both synthetic and real data and compare them with related methods. Our numerical experiments show some promising performance of the proposed methods against their competitors.<\/jats:p>\n                  <jats:p>Funding: This work was supported by the National Science Foundation (NSF) [Grant NSF-RTG DMS-2134107] and the Office of Naval Research [Grants N00014-20-1-2088, N00014-23-1-2588].<\/jats:p>","DOI":"10.1287\/moor.2024.0414","type":"journal-article","created":{"date-parts":[[2025,4,2]],"date-time":"2025-04-02T10:04:09Z","timestamp":1743588249000},"page":"746-782","source":"Crossref","is-referenced-by-count":2,"title":["Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems"],"prefix":"10.1287","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1077-2579","authenticated-orcid":false,"given":"Quoc","family":"Tran-Dinh","sequence":"first","affiliation":[{"name":"Department of Statistics and Operations Research, The University of North Carolina at Chapel Hill, Chapel Hill, North Carolina 27599"}]},{"given":"Yang","family":"Luo","sequence":"additional","affiliation":[{"name":"Department of Statistics and Operations Research, The University of North Carolina at Chapel Hill, Chapel Hill, North Carolina 27599"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"crossref","unstructured":"Abhishek VA, Binny S, Johan TR, Nithin R, Vishal T (2022) Federated learning: Collaborative machine learning without centralized training data.\n                      Internat. J. Engrg. Technol. Management Sci.\n                      6(5):355\u2013359.","DOI":"10.46647\/ijetms.2022.v06i05.052"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511543005"},{"key":"B3","unstructured":"Alacaoglu A, Tran-Dinh Q, Fercoq O, Cevher V (2017) Smooth primal-dual coordinate descent algorithms for nonsmooth convex optimization. Guyon I, Von Luxburg U, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds.\n                      Advances in Neural Information Processing Systems\n                      , vol. 30 (Curran Associates, Inc., Red Hook, NY), 1\u20139."},{"key":"B4","unstructured":"Arjovsky M, Chintala S, Bottou L (2017) Wasserstein generative adversarial networks.\n                      Proc. 34th Internat. Conf. Machine Learn.\n                      , vol. 70 (JMLR.org), 214\u2013223."},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01412-0"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmaa.2016.06.025"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01397082"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-48311-5"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1137\/15M1008397"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1515\/9781400831050"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623499354564"},{"key":"B12","volume-title":"Parallel and Distributed Computation: Numerical Methods","author":"Bertsekas D","year":"1989"},{"key":"B13","author":"B\u00f6hm A","year":"2023","journal-title":"Trans. Machine Learn. Res."},{"issue":"8","key":"B14","first-page":"1","volume":"24","author":"Bot RI","year":"2023","journal-title":"J. Machine Learn. Res."},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1137\/16M1080173"},{"key":"B16","volume-title":"Set-Valued Mappings and Enlargements of Monotone Operators","author":"Burachik RS","year":"2008"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1145\/1961189.1961199"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1161-4"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1044-0"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-9569-8_10"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1137\/140971233"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1137\/050626090"},{"key":"B23","unstructured":"Daskalakis C, Ilyas A, Syrgkanis V, Zeng H (2018) Training GANs with optimism.\n                      6th Internat. Conf. Learn. Representations (ICLR 2018) (Vancouver)."},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01758-4"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1007\/s11228-017-0421-z"},{"key":"B26","first-page":"1646","author":"Defazio A","year":"2014","journal-title":"Advances in Neural Information Processing Systems"},{"key":"B27","first-page":"1428","volume-title":"Conf. Learn. Theory","author":"Diakonikolas J","year":"2020"},{"key":"B28","unstructured":"Diakonikolas J, Daskalakis C, Jordan M (2021) Efficient methods for structured nonconvex-nonconcave min-max optimization.\n                      Internat. Conf. Artificial Intelligence Statist.\n                      (PMLR, New York), 2746\u20132754."},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2017.0889"},{"key":"B30","doi-asserted-by":"crossref","unstructured":"Du W, Xu D, Wu X, Tong H (2021) Fairness-aware agnostic federated learning.\n                      Proc. 2021 SIAM Internat. Conf. Data Mining\n                      (SIAM, Philadelphia), 181\u2013189.","DOI":"10.1137\/1.9781611976700.21"},{"key":"B31","volume-title":"Finite-Dimensional Variational Inequalities and Complementarity Problems","volume":"1","author":"Facchinei F","year":"2003"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1137\/130949993"},{"key":"B33","first-page":"2672","author":"Goodfellow I","year":"2014","journal-title":"Advances in Neural Information Processing Systems"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1967-11864-0"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.3390\/s22031032"},{"key":"B36","first-page":"3165","author":"Hsieh CJ","year":"2013","journal-title":"Advances in Neural Information Processing Systems"},{"key":"B37","doi-asserted-by":"crossref","unstructured":"Kairouz P, McMahan HB, Avent B, Bellet A, Bennis M, Bhagoji AN, Bonawitz K, et al. (2021) Advances and open problems in federated learning.\n                      Found Trends Machine Learn\n                      . 14(1\u20132):1\u2013210.","DOI":"10.1561\/2200000083"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01643-0"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0949-3"},{"key":"B40","unstructured":"Kone\u010dn\u1ef3 J, McMahan HB, Ramage D, Richt\u00e1rik P (2016) Federated optimization: Distributed machine learning for on-device intelligence. Preprint, submitted October 8, https:\/\/arxiv.org\/abs\/1610.02527."},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56886-2"},{"issue":"4","key":"B42","first-page":"747","volume":"12","author":"Korpelevich G","year":"1976","journal-title":"Ekonomika i Matematicheskie Metody"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1137\/20M1381678"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1996.0042"},{"key":"B45","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-39568-1"},{"key":"B46","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01599-7"},{"key":"B47","unstructured":"Lee S, Kim D (2021) Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems.\n                      Advances in Neural Information Processing Systems\n                      , vol. 34 (Curran Associates Inc., Red Hook, NY), 16924\u201316936."},{"key":"B48","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2020.2975749"},{"key":"B49","first-page":"429","volume-title":"Proceedings of Machine Learning and Systems","volume":"2","author":"Li T","year":"2020"},{"key":"B50","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-020-01617-9"},{"key":"B51","doi-asserted-by":"publisher","DOI":"10.1137\/0716071"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.1007\/BF02096261"},{"key":"B53","unstructured":"Madry A, Makelov A, Schmidt L, Tsipras D, Vladu A (2018) Towards deep learning models resistant to adversarial attacks.\n                      Proc. Internat. Conf. Learn. Representations (ICLR) (Vancouver)."},{"key":"B54","doi-asserted-by":"publisher","DOI":"10.1007\/s00245-021-09819-y"},{"key":"B55","first-page":"893","volume":"29","author":"Maing\u00e9 PE","year":"2022","journal-title":"J. Convex Anal."},{"key":"B56","doi-asserted-by":"publisher","DOI":"10.1137\/14097238X"},{"key":"B57","doi-asserted-by":"publisher","DOI":"10.1137\/18M1207260"},{"key":"B58","unstructured":"Martinez N, Bertran M, Sapiro G (2020) Minimax pareto fairness: A multi objective perspective.\n                      Internat. Conf. Machine Learn.\n                      (PMLR, New York), 6755\u20136764."},{"key":"B59","first-page":"1273","volume-title":"Artificial Intelligence Statist.","author":"McMahan HB","year":"2017"},{"key":"B60","unstructured":"Mokhtari A, Ozdaglar A, Pattathil S (2020) A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach.\n                      Internat. Conf. Artificial Intelligence Statist.\n                      (PMLR, New York), 1497\u20131507."},{"key":"B61","volume":"29","author":"Namkoong H","year":"2016","journal-title":"Advances in Neural Information Processing Systems"},{"key":"B62","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2008.2009515"},{"key":"B63","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403425629"},{"key":"B64","first-page":"543","volume":"269","author":"Nesterov Y","year":"1983","journal-title":"Soviet Math. Doklady"},{"key":"B65","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"B66","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0034-z"},{"key":"B67","doi-asserted-by":"publisher","DOI":"10.1137\/100802001"},{"key":"B68","doi-asserted-by":"publisher","DOI":"10.1137\/16M1060182"},{"key":"B69","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719468"},{"key":"B70","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01420-0"},{"key":"B71","doi-asserted-by":"publisher","DOI":"10.1137\/15M1024950"},{"key":"B72","unstructured":"Pethick T, Patrinos P, Fercoq O, Cevher V (2022) Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems.\n                      Proc. 10th Internat. Conf. Learn. Representations (ICLR 2022)\n                      (Virtual Conference: International Conference on Learning Representations)."},{"issue":"3","key":"B73","first-page":"1113","volume":"17","author":"Peypouquet J","year":"2010","journal-title":"J. Convex Anal. (Oxford)"},{"key":"B74","volume-title":"Convex Functions, Monotone Operators and Differentiability","volume":"1364","author":"Phelps RR","year":"2009"},{"issue":"5","key":"B75","first-page":"845","volume":"28","author":"Popov LD","year":"1980","journal-title":"Math. Notes Acad. of Sci. USSR"},{"key":"B76","unstructured":"Rahimian H, Mehrotra S (2019) Distributionally robust optimization: A review. Preprint, submitted August 13, https:\/\/arxiv.org\/abs\/1908.05659."},{"key":"B77","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0901-6"},{"key":"B78","doi-asserted-by":"crossref","unstructured":"Robbins H, Siegmund D (1971) A convergence theorem for non negative almost supermartingales and some applications. Rustagi JS, ed.\n                      Optimizing Methods in Statistics\n                      (Academic Press, New York), 233\u2013257.","DOI":"10.1016\/B978-0-12-604550-5.50015-8"},{"key":"B79","doi-asserted-by":"publisher","DOI":"10.1137\/0314056"},{"key":"B80","unstructured":"Rockafellar RT, Wets RJ-B, eds. (2004)\n                      Variational Analysis\n                      , vol. 317 (Springer-Verlag, Berlin)."},{"issue":"1","key":"B81","first-page":"3","volume":"15","author":"Ryu EK","year":"2016","journal-title":"Appl. Comput. Math."},{"key":"B82","doi-asserted-by":"publisher","DOI":"10.1017\/9781009160865"},{"key":"B83","unstructured":"Sharma P, Panda R, Joshi G, Varshney P (2022) Federated minimax optimization: Improved convergence analyses and algorithms.\n                      Internat. Conf. Machine Learn.\n                      (PMLR, New York), 19683\u201319730."},{"key":"B84","volume-title":"Optimization for Machine Learning","author":"Sra S","year":"2012"},{"key":"B85","unstructured":"Tarzanagh DA, Li M, Thrampoulidis C, Oymak S (2022) Fednest: Federated bilevel, minimax, and compositional optimization.\n                      Internat. Conf. Machine Learn.\n                      (PMLR, New York), 21146\u201321179."},{"key":"B86","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-023-01347-z"},{"key":"B87","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-023-00518-8"},{"key":"B88","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2022.2119233"},{"key":"B89","unstructured":"Tran-Dinh Q, Luo Y (2021) Halpern-type accelerated and splitting algorithms for monotone inclusions. Preprint, submitted October 15, https:\/\/arxiv.org\/abs\/2110.08150."},{"key":"B90","unstructured":"Tran-Dinh Q, Pham NH, Phan DT, Nguyen LM (2021) FedDR\u2014Randomized Douglas-Rachford splitting algorithms for nonconvex federated composite optimization.\n                      Advances in Neural Information Processing Systems\n                      , 1\u201339."},{"key":"B91","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012998338806"},{"key":"B92","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0892-3"},{"key":"B93","doi-asserted-by":"crossref","unstructured":"Wright SJ (2017) Optimization algorithms for data analysis.\n                      IAS\/Park City Mathematics Series\n                      , vol. 25 (American Mathematical Society, Providence, RI), 1\u201349.","DOI":"10.1090\/pcms\/025\/02"},{"key":"B94","unstructured":"Yoon T, Ryu EK (2021) Accelerated algorithms for smooth convex-concave minimax problems with O(1\/k2) rate on squared gradient norm.\n                      Internat. Conf. Machine Learn.\n                      (PMLR, New York), 12098\u201312109."}],"container-title":["Mathematics of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/moor.2024.0414","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T09:41:03Z","timestamp":1772876463000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2024.0414"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1]]},"references-count":94,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["10.1287\/moor.2024.0414"],"URL":"https:\/\/doi.org\/10.1287\/moor.2024.0414","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"value":"0364-765X","type":"print"},{"value":"1526-5471","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1]]}}}