{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:18:14Z","timestamp":1757618294937,"version":"3.44.0"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:00:00Z","timestamp":1750291200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:00:00Z","timestamp":1750291200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2025,8]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Unbalanced dimensions are crucial characteristics in various minimax optimization problems, such as few-shot learning (Cortes and Mohri in Adv Neural Inf Process Syst 16, 2003; Ying et al. in Adv Neural Inf Process Syst 29, 2016) and fairness-aware machine learning (Lowd and Meek, in: Proceedings of the eleventh ACM SIGKDD international conference on knowledge discovery in data mining, 2005; Zhang et al., in: Proceedings of the 2018 AAAI\/ACM conference on AI, ethics, and society, 2018). In this paper, we propose a communication-efficient second-order method named  (Partially Approximate Newton methods for Distributed minimAx) to solve problems with unbalanced dimensions.  requires almost the same per-iteration communication cost as the first-order methods by utilizing the special problem structure in its design for data exchange between the client and server. More importantly, it exhibits a superior linear-quadratic convergence rate and significantly reduces the total number of communication rounds through the efficient use of second-order information. We also develop  based on the framework of , which further reduces the computation cost of the latter one by performing sketching operations on each client. Through comprehensive theoretical analysis and empirical evaluations, we demonstrate the superior performance of the proposed methods compared to existing state-of-the-art methods.\n<\/jats:p>","DOI":"10.1007\/s10994-025-06813-1","type":"journal-article","created":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T12:41:59Z","timestamp":1750336919000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Panda: partially approximate newton methods for distributed minimax optimization with unbalanced dimensions"],"prefix":"10.1007","volume":"114","author":[{"given":"Minheng","family":"Xiao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chengchang","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cheng","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John C. S.","family":"Lui","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sen","family":"Na","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,6,19]]},"reference":[{"key":"6813_CR1","unstructured":"Adil, D., Bullins, B., Jambulapati, A., & Sachdeva, S. (2022). Line search-free methods for higher-order smooth monotone variational inequalities. arXiv preprint arXiv:2205.06167"},{"key":"6813_CR2","series-title":"ser. Classics in Applied Mathematics","volume-title":"Dynamic noncooperative game theory","author":"T Basar","year":"1999","unstructured":"Basar, T., & Olsder, G. J. (1999). Dynamic noncooperative game theory. ser. Classics in Applied MathematicsSIAM."},{"key":"6813_CR3","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s101070100286","volume":"92","author":"A Ben-Tal","year":"2002","unstructured":"Ben-Tal, A., & Nemirovski, A. (2002). Robust optimization-methodology and applications. Mathematical Programming, 92, 453\u2013480.","journal-title":"Mathematical Programming"},{"key":"6813_CR4","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1145\/1961189.1961199","volume":"2","author":"C-C Chang","year":"2011","unstructured":"Chang, C.-C., & Lin, C.-J. (2011). LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2, 27\u201312727.","journal-title":"ACM Transactions on Intelligent Systems and Technology"},{"key":"6813_CR5","unstructured":"Chavdarova, T., Gidel, G., Fleuret, F., & Lacoste-Julien, S. (2019). Reducing noise in gan training with variance reduced extragradient. Advances in Neural Information Processing Systems, 32."},{"issue":"6","key":"6813_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3019134","volume":"63","author":"K L Clarkson","year":"2017","unstructured":"Clarkson, K. L., & Woodruff, D. P. (2017). Low-rank approximation and regression in input sparsity time. Journal of the ACM (JACM), 63(6), 1\u201345.","journal-title":"Journal of the ACM (JACM)"},{"key":"6813_CR7","unstructured":"Cortes, C., & Mohri, M. (2003). Auc optimization vs. error rate minimization. Advances in neural information processing systems, 16."},{"issue":"1","key":"6813_CR8","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1109\/MSP.2017.2765202","volume":"35","author":"A Creswell","year":"2018","unstructured":"Creswell, A., White, T., Dumoulin, V., Arulkumaran, K., Sengupta, B., & Bharath, A. A. (2018). Generative adversarial networks: An overview. IEEE Signal Processing Magazine, 35(1), 53\u201365.","journal-title":"IEEE Signal Processing Magazine"},{"key":"6813_CR9","first-page":"1387","volume-title":"International conference on artificial intelligence and statistics","author":"Y Deng","year":"2021","unstructured":"Deng, Y., & Mahdavi, M. (2021). Local stochastic gradient descent ascent: Convergence analysis and communication efficiency. International conference on artificial intelligence and statistics (pp. 1387\u20131395). PMLR."},{"key":"6813_CR10","volume-title":"Finite-dimensional variational inequalities and complementarity problems","author":"F Facchinei","year":"2003","unstructured":"Facchinei, F. (2003). Finite-dimensional variational inequalities and complementarity problems. Springer."},{"issue":"2","key":"6813_CR11","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1287\/moor.2022.1275","volume":"48","author":"R Gao","year":"2022","unstructured":"Gao, R., & Kleywegt, A. (2022). Distributionally robust stochastic optimization with wasserstein distance. Mathematics of Operations Research, 48(2), 603\u2013655.","journal-title":"Mathematics of Operations Research"},{"key":"6813_CR12","unstructured":"Hsieh, Y.-G., Iutzeler, F., Malick, J., & Mertikopoulos, P. (2019). On the convergence of single-call stochastic extra-gradient methods. Advances in Neural Information Processing Systems, 32."},{"key":"6813_CR13","unstructured":"Huang, K., & Zhang, S. (2022). An approximation-based regularized extra-gradient method for monotone variational inequalities. arXiv preprint arXiv:2210.04440"},{"issue":"2","key":"6813_CR14","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/s10915-022-01819-6","volume":"91","author":"K Huang","year":"2022","unstructured":"Huang, K., Zhang, J., & Zhang, S. (2022). Cubic regularized newton method for the saddle point models: A global and local convergence analysis. Journal of Scientific Computing, 91(2), 60.","journal-title":"Journal of Scientific Computing"},{"key":"6813_CR15","unstructured":"Islamov, R., Qian, X., Hanzely, S., Safaryan, M., & Richt\u00e1rik, P. (2022). Distributed Newton-type methods with communication compression and bernoulli aggregation. Transactions on Machine Learning Research"},{"key":"6813_CR16","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"W B Johnson","year":"1984","unstructured":"Johnson, W. B., & Lindenstrauss, J. (1984). Extensions of Lipschitz maps into a Hilbert space. Contemporary Mathematics, 26, 189\u2013206.","journal-title":"Contemporary Mathematics"},{"key":"6813_CR17","first-page":"747","volume":"12","author":"GM Korpelevich","year":"1976","unstructured":"Korpelevich, G. M. (1976). The extragradient method for finding saddle points and other problems. Matecon, 12, 747\u2013756.","journal-title":"Matecon"},{"key":"6813_CR18","first-page":"555","volume":"3","author":"GR Lanckriet","year":"2002","unstructured":"Lanckriet, G. R., Ghaoui, L. E., Bhattacharyya, C., & Jordan, M. I. (2002). A robust minimax approach to classification. Journal of Machine Learning Research, 3, 555\u2013582.","journal-title":"Journal of Machine Learning Research"},{"issue":"3","key":"6813_CR19","first-page":"1452","volume":"12","author":"T Le Quy","year":"2022","unstructured":"Le Quy, T., Roy, A., Iosifidis, V., Zhang, W., & Ntoutsi, E. (2022). A survey on datasets for fairness-aware machine learning. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 12(3), 1452.","journal-title":"Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery"},{"key":"6813_CR20","unstructured":"Lin, T., & Jordan, M.I. (2022). Perseus: A simple high-order regularization method for variational inequalities. arXiv preprint arXiv:2205.03202"},{"key":"6813_CR21","first-page":"6083","volume-title":"International conference on machine learning","author":"T Lin","year":"2020","unstructured":"Lin, T., Jin, C., & Jordan, M. (2020). On gradient descent ascent for nonconvex-concave minimax problems. International conference on machine learning (pp. 6083\u20136093). PMLR."},{"key":"6813_CR22","unstructured":"Liu, C., & Luo, L. (2022). Regularized newton methods for monotone variational inequalities with holders continuous jacobians. arXiv preprint arXiv:2212.07824"},{"key":"6813_CR23","doi-asserted-by":"crossref","unstructured":"Liu, C., Bi, S., Luo, L., & Lui, J. C. (2022). Partial-quasi-newton methods: Efficient algorithms for minimax optimization problems with unbalanced dimensionality. In Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining (pp. 1031\u20131041).","DOI":"10.1145\/3534678.3539379"},{"key":"6813_CR24","doi-asserted-by":"crossref","unstructured":"Liu, C., Chen, L., Luo, L., & Lui, J. (2024). Communication efficient distributed newton method with fast convergence rates. In Proceedings of the 29th ACM SIGKDD conference on knowledge discovery and data mining.","DOI":"10.1145\/3580305.3599280"},{"key":"6813_CR25","first-page":"3975","volume":"35","author":"C Liu","year":"2022","unstructured":"Liu, C., & Luo, L. (2022). Quasi-newton methods for saddle point problems. Advances in Neural Information Processing Systems, 35, 3975\u20133987.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"6813_CR26","first-page":"11056","volume":"33","author":"M Liu","year":"2020","unstructured":"Liu, M., Zhang, W., Mroueh, Y., Cui, X., Ross, J., Yang, T., & Das, P. (2020). A decentralized parallel algorithm for training generative adversarial nets. Advances in Neural Information Processing Systems, 33, 11056\u201311070.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"6813_CR27","doi-asserted-by":"crossref","unstructured":"Lowd, D., & Meek, C. (2005). Adversarial learning. In Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining (pp. 641\u2013647).","DOI":"10.1145\/1081870.1081950"},{"key":"6813_CR28","first-page":"36667","volume":"35","author":"L Luo","year":"2022","unstructured":"Luo, L., Li, Y., & Chen, C. (2022). Finding second-order stationary points in nonconvex-strongly-concave minimax optimization. Advances in Neural Information Processing Systems, 35, 36667\u201336679.","journal-title":"Advances in Neural Information Processing Systems"},{"issue":"1","key":"6813_CR29","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1137\/14097238X","volume":"25","author":"Y Malitsky","year":"2015","unstructured":"Malitsky, Y. (2015). Projected reflected gradient methods for monotone variational inequalities. SIAM Journal on Optimization, 25(1), 502\u2013520.","journal-title":"SIAM Journal on Optimization"},{"key":"6813_CR30","doi-asserted-by":"crossref","unstructured":"Meng, X., & Mahoney, M. W. (2013). Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In Proceedings of the forty-fifth annual ACM symposium on theory of computing (pp. 91\u2013100).","DOI":"10.1145\/2488608.2488621"},{"key":"6813_CR31","unstructured":"Mishchenko, K., Kovalev, D., Shulgin, E., Richt\u00e1rik, P., & Malitsky, Y. (2020). Revisiting stochastic extragradient. In International conference on artificial intelligence and statistics (pp. 4573\u20134582). PMLR"},{"issue":"1\u20132","key":"6813_CR32","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/s10107-022-01913-5","volume":"201","author":"S Na","year":"2023","unstructured":"Na, S., Derezi\u0144ski, M., & Mahoney, M. W. (2023). Hessian averaging in stochastic newton methods achieves superlinear convergence. Mathematical Programming, 201(1\u20132), 473\u2013520.","journal-title":"Mathematical Programming"},{"key":"6813_CR33","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s10957-009-9522-7","volume":"142","author":"A Nedi\u0107","year":"2009","unstructured":"Nedi\u0107, A., & Ozdaglar, A. (2009). Subgradient methods for saddle-point problems. Journal of Optimization Theory and Applications, 142, 205\u2013228.","journal-title":"Journal of Optimization Theory and Applications"},{"key":"6813_CR34","unstructured":", Nouiehed, M., Sanjabi, M., Huang, T., Lee, J. D., & Razaviyayn, M. (2019). Solving a class of non-convex min-max games using iterative first order methods. Advances in Neural Information Processing Systems, 32."},{"issue":"1","key":"6813_CR35","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1137\/20M1320651","volume":"31","author":"A Rodomanov","year":"2021","unstructured":"Rodomanov, A., & Nesterov, Y. (2021). Greedy quasi-newton methods with explicit superlinear convergence. SIAM Journal on Optimization, 31(1), 785\u2013811.","journal-title":"SIAM Journal on Optimization"},{"key":"6813_CR36","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-018-1346-5","volume":"174","author":"F Roosta-Khorasani","year":"2019","unstructured":"Roosta-Khorasani, F., & Mahoney, M. W. (2019). Sub-sampled newton methods. Mathematical Programming, 174, 293\u2013326.","journal-title":"Mathematical Programming"},{"key":"6813_CR37","first-page":"1000","volume-title":"International conference on machine learning","author":"O Shamir","year":"2014","unstructured":"Shamir, O., Srebro, N., & Zhang, T. (2014). Communication-efficient distributed optimization using an approximate newton-type method. International conference on machine learning (pp. 1000\u20131008). PMLR."},{"key":"6813_CR38","first-page":"6060","volume":"35","author":"Z Sun","year":"2022","unstructured":"Sun, Z., & Wei, E. (2022). A communication-efficient algorithm with linear convergence for federated minimax learning. Advances in Neural Information Processing Systems, 35, 6060\u20136073.","journal-title":"Advances in Neural Information Processing Systems"},{"issue":"2","key":"6813_CR39","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/S0363012998338806","volume":"38","author":"P Tseng","year":"2000","unstructured":"Tseng, P. (2000). A modified forward-backward splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization, 38(2), 431\u2013446.","journal-title":"SIAM Journal on Control and Optimization"},{"key":"6813_CR40","first-page":"3608","volume-title":"International conference on machine learning","author":"S Wang","year":"2017","unstructured":"Wang, S., Gittens, A., & Mahoney, M. W. (2017). Sketched ridge regression: Optimization perspective, statistical perspective, and model averaging. International conference on machine learning (pp. 3608\u20133616). PMLR."},{"key":"6813_CR41","unstructured":"Wang, S., Roosta, F., Xu, P., & Mahoney, M. W. (2018). Giant: Globally improved approximate newton method for distributed optimization. Advances in Neural Information Processing Systems, 31."},{"key":"6813_CR42","first-page":"4800","volume":"33","author":"Y Wang","year":"2020","unstructured":"Wang, Y., & Li, J. (2020). Improved algorithms for convex-concave minimax optimization. Advances in Neural Information Processing Systems, 33, 4800\u20134810.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"6813_CR43","doi-asserted-by":"crossref","unstructured":"Ye, H., He, C., & Chang, X. (2022). Accelerated distributed approximate newton method. IEEE Transactions on Neural Networks and Learning Systems","DOI":"10.1109\/TNNLS.2022.3151736"},{"issue":"1","key":"6813_CR44","first-page":"5627","volume":"21","author":"H Ye","year":"2020","unstructured":"Ye, H., Luo, L., & Zhang, Z. (2020). Nesterov\u2019s acceleration for approximate newton. The Journal of Machine Learning Research, 21(1), 5627\u20135663.","journal-title":"The Journal of Machine Learning Research"},{"issue":"1","key":"6813_CR45","first-page":"3067","volume":"22","author":"H Ye","year":"2021","unstructured":"Ye, H., Luo, L., & Zhang, Z. (2021). Approximate newton methods. The Journal of Machine Learning Research, 22(1), 3067\u20133107.","journal-title":"The Journal of Machine Learning Research"},{"key":"6813_CR46","volume-title":"Stochastic online AUC maximization","author":"Y Ying","year":"2016","unstructured":"Ying, Y., Wen, L., & Lyu, S. (2016). Stochastic online AUC maximization. NIPS."},{"key":"6813_CR47","unstructured":"Zhang, S., Choudhury, S., Stich, S. U., & Loizou, N. (2024). Communication-efficient gradient descent-accent methods for distributed variational inequalities: Unified analysis and local updates. In The twelfth international conference on learning representations"},{"key":"6813_CR48","doi-asserted-by":"crossref","unstructured":"Zhang, B. H., Lemoine, B., & Mitchell, M. (2018). Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI\/ACM conference on AI, ethics, and society (pp. 335\u2013340).","DOI":"10.1145\/3278721.3278779"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-025-06813-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-025-06813-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-025-06813-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T20:31:06Z","timestamp":1757190666000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-025-06813-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,19]]},"references-count":48,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["6813"],"URL":"https:\/\/doi.org\/10.1007\/s10994-025-06813-1","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"type":"print","value":"0885-6125"},{"type":"electronic","value":"1573-0565"}],"subject":[],"published":{"date-parts":[[2025,6,19]]},"assertion":[{"value":"31 January 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 February 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 May 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"174"}}