{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T06:50:55Z","timestamp":1782283855902,"version":"3.54.5"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T00:00:00Z","timestamp":1776643200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T00:00:00Z","timestamp":1776643200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Stochastic bilevel optimization finds widespread applications in machine learning, including meta-learning, hyperparameter optimization, and neural architecture search. To extend stochastic bilevel optimization to distributed data, several decentralized stochastic bilevel optimization algorithms have been developed. However, existing methods often suffer from slow convergence rates and high communication costs in heterogeneous settings, limiting their applicability to real-world tasks. To address these issues, we propose two novel decentralized stochastic bilevel gradient descent algorithms based on simultaneous and alternating update strategies. Our algorithms can achieve faster convergence rates and lower communication costs than existing methods. Importantly, our convergence analyses do not rely on strong assumptions regarding heterogeneity. More importantly, our theoretical analyses clearly disclose how the computation and communication regarding the Hessian-inverse-vector product under the heterogeneous setting affects the convergence rate. To the best of our knowledge, this is the first time such favorable theoretical results have been achieved with mild assumptions in the heterogeneous setting. Furthermore, we demonstrate how to establish the convergence rate for the alternating update strategy when combined with the variance-reduced gradient. Finally, experimental results confirm the efficacy of our algorithms.<\/jats:p>","DOI":"10.1007\/s10994-026-07040-y","type":"journal-article","created":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T09:43:47Z","timestamp":1776678227000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Communication Complexity of Decentralized Stochastic Bilevel Optimization"],"prefix":"10.1007","volume":"115","author":[{"given":"Yihan","family":"Zhang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"My T.","family":"Thai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jie","family":"Wu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hongchang","family":"Gao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,4,20]]},"reference":[{"key":"7040_CR1","unstructured":"Chen, X., Huang, M., & Ma, S. (2022). Decentralized bilevel optimization. arXiv preprint arXiv:2206.05670"},{"key":"7040_CR2","unstructured":"Chen, X., Huang, M., Ma, S., & Balasubramanian, K. (2022). Decentralized stochastic bilevel optimization with improved per-iteration complexity. arXiv preprint arXiv:2210.12839"},{"key":"7040_CR3","unstructured":"Chen, T., Sun, Y., & Yin, W. (2021). Tighter analysis of alternating stochastic gradient method for stochastic nested problems. arXiv preprint arXiv:2106.13781"},{"key":"7040_CR4","unstructured":"Chen, Y., Yuan, K., Zhang, Y., Pan, P., Xu, Y., & Yin, W. (2021). Accelerating gossip sgd with periodic global averaging. In: International Conference on Machine Learning, 1791\u20131802. PMLR"},{"key":"7040_CR5","unstructured":"Cutkosky, A., & Orabona, F. (2019). Momentum-based variance reduction in non-convex sgd. Advances in neural information processing systems 32"},{"key":"7040_CR6","doi-asserted-by":"crossref","unstructured":"Dagr\u00e9ou, M., Ablin, P., Vaiter, S., & Moreau, T. (2022). A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. arXiv preprint arXiv:2201.13409","DOI":"10.52202\/068431-1936"},{"key":"7040_CR7","unstructured":"Dagr\u00e9ou, M., Moreau, T., Vaiter, S., & Ablin, P. (2023). A lower bound and a near-optimal algorithm for bilevel empirical risk minimization. arXiv e-prints, 2302."},{"key":"7040_CR8","unstructured":"Defazio, A., Bach, F., & Lacoste-Julien, S. (2014). Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems 27"},{"key":"7040_CR9","unstructured":"Dong, Y., Ma, S., Yang, J., & Yin, C. (2023). A single-loop algorithm for decentralized bilevel optimization. CoRR abs\/2311.08945 arXiv:2311.08945"},{"key":"7040_CR10","unstructured":"Fang, C., Li, C.J., Lin, Z., & Zhang, T. (2018). Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. Advances in Neural Information Processing Systems 31."},{"key":"7040_CR11","doi-asserted-by":"crossref","unstructured":"Feurer, M., & Hutter, F. (2019). Hyperparameter optimization. In: Automated Machine Learning, 3\u201333. Springer International Publishing Cham","DOI":"10.1007\/978-3-030-05318-5_1"},{"key":"7040_CR12","unstructured":"Franceschi, L., Donini, M., Frasconi, P., & Pontil, M. (2017). Forward and reverse gradient-based hyperparameter optimization. In: International Conference on Machine Learning, 1165\u20131173. PMLR"},{"key":"7040_CR13","unstructured":"Franceschi, L., Frasconi, P., Salzo, S., Grazzi, R., & Pontil, M. (2018). Bilevel programming for hyperparameter optimization and meta-learning. In: International Conference on Machine Learning, 1568\u20131577. PMLR"},{"key":"7040_CR14","unstructured":"Gao, H. (2022). On the convergence of momentum-based algorithms for federated stochastic bilevel optimization problems. arXiv preprint arXiv:2204.13299"},{"key":"7040_CR15","unstructured":"Gao, H., Gu, B., & Thai, M.T. (2023). On the convergence of distributed stochastic bilevel optimization algorithms over a network. In: International Conference on Artificial Intelligence and Statistics, 9238\u20139281. PMLR"},{"key":"7040_CR16","unstructured":"Ghadimi, S., & Wang, M. (2018). Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246"},{"key":"7040_CR17","unstructured":"Hong, M., Wai, H.-T., Wang, Z., & Yang, Z. (2020). A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint arXiv:2007.05170"},{"key":"7040_CR18","unstructured":"Huang, F. (2022). Fast adaptive federated bilevel optimization. arXiv preprint arXiv:2211.01122"},{"key":"7040_CR19","unstructured":"Huang, F., Gao, S., Pei, J., & Huang, H. (2020). Accelerated zeroth-order momentum methods from mini to minimax optimization. arXiv e-prints, 2008"},{"key":"7040_CR20","unstructured":"Ji, K., Yang, J., & Liang, Y. (2021). Bilevel optimization: Convergence analysis and enhanced design. In: International Conference on Machine Learning, 4882\u20134892. PMLR"},{"key":"7040_CR21","unstructured":"Khanduri, P., Zeng, S., Hong, M., Wai, H.-T., Wang, Z., & Yang, Z. (2021). A near-optimal algorithm for stochastic bilevel optimization via double-momentum. Advances in Neural Information Processing Systems 34"},{"key":"7040_CR22","unstructured":"Li, J., Huang, F., & Huang, H. (2022). Local stochastic bilevel optimization with momentum-based variance reduction. arXiv preprint arXiv:2205.01608"},{"key":"7040_CR23","doi-asserted-by":"publisher","first-page":"7426","DOI":"10.1609\/aaai.v36i7.20706","volume":"36","author":"J Li","year":"2022","unstructured":"Li, J., Gu, B., & Huang, H. (2022). A fully single loop algorithm for bilevel optimization without hessian inverse. Proceedings of the AAAI Conference on Artificial Intelligence, 36, 7426\u20137434.","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"7040_CR24","unstructured":"Liu, H., Simonyan, K., & Yang, Y. (2018). Darts: Differentiable architecture search. arXiv preprint arXiv:1806.09055"},{"key":"7040_CR25","doi-asserted-by":"crossref","unstructured":"Liu, Z., Zhang, X., Khanduri, P., Lu, S., & Liu, J. (2022). Interact: achieving low sample and communication complexities in decentralized bilevel learning over networks. In: Proceedings of the Twenty-Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, 61\u201370.","DOI":"10.1145\/3492866.3549721"},{"key":"7040_CR26","doi-asserted-by":"crossref","unstructured":"Lu, S., Cui, X., Squillante, M.S., Kingsbury, B., & Horesh, L. (2022). Decentralized bilevel optimization for personalized client learning. In: ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5543\u20135547. IEEE","DOI":"10.1109\/ICASSP43922.2022.9746612"},{"issue":"76","key":"7040_CR27","first-page":"1","volume":"26","author":"Y Niu","year":"2025","unstructured":"Niu, Y., Xu, J., Sun, Y., Huang, Y., & Chai, L. (2025). Distributed stochastic bilevel optimization: Improved complexity and heterogeneity analysis. Journal of Machine Learning Research, 26(76), 1\u201358.","journal-title":"Journal of Machine Learning Research"},{"key":"7040_CR28","unstructured":"Rajeswaran, A., Finn, C., Kakade, S.M., & Levine, S. (2019). Meta-learning with implicit gradients. Advances in neural information processing systems 32"},{"key":"7040_CR29","first-page":"24313","volume":"34","author":"A Spiridonoff","year":"2021","unstructured":"Spiridonoff, A., Olshevsky, A., & Paschalidis, Y. (2021). Communication-efficient sgd: From local sgd to one-shot averaging. Advances in Neural Information Processing Systems, 34, 24313\u201324326.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"7040_CR30","unstructured":"Tarzanagh, D.A., Li, M., Thrampoulidis, C., & Oymak, S. (2022). Fednest: Federated bilevel, minimax, and compositional optimization. In: International Conference on Machine Learning, 21146\u201321179. PMLR"},{"key":"7040_CR31","unstructured":"Xin, R., Das, S., Khan, U.A., & Kar, S. (2021). A stochastic proximal gradient framework for decentralized non-convex composite optimization: Topology-independent sample complexity and communication efficiency. arXiv preprint arXiv:2110.01594"},{"key":"7040_CR32","unstructured":"Xin, R., Khan, U., & Kar, S. (2021). A hybrid variance-reduced method for decentralized stochastic non-convex optimization. In: International Conference on Machine Learning, 11459\u201311469. PMLR"},{"key":"7040_CR33","unstructured":"Yang, J., Ji, K., & Liang, Y. (2021). Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems 34"},{"key":"7040_CR34","doi-asserted-by":"crossref","unstructured":"Yang, S., Zhang, X., & Wang, M. (2022). Decentralized gossip-based stochastic bilevel optimization over communication networks. arXiv preprint arXiv:2206.10870","DOI":"10.52202\/068431-0018"},{"key":"7040_CR35","doi-asserted-by":"publisher","first-page":"20865","DOI":"10.1609\/aaai.v38i18.30076","volume":"38","author":"X Zhang","year":"2024","unstructured":"Zhang, X., Mancino-Ball, G., Aybat, N. S., & Xu, Y. (2024). Jointly improving the sample and communication complexities in decentralized stochastic minimax optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 38, 20865\u201320873.","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"7040_CR36","doi-asserted-by":"publisher","first-page":"62912","DOI":"10.52202\/079017-2010","volume":"37","author":"S Zhu","year":"2024","unstructured":"Zhu, S., Kong, B., Lu, S., Huang, X., & Yuan, K. (2024). Sparkle: a unified single-loop primal-dual framework for decentralized bilevel optimization. Advances in Neural Information Processing Systems, 37, 62912\u201362987.","journal-title":"Advances in Neural Information Processing Systems"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-026-07040-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-026-07040-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-026-07040-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T06:33:47Z","timestamp":1782282827000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-026-07040-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,20]]},"references-count":36,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["7040"],"URL":"https:\/\/doi.org\/10.1007\/s10994-026-07040-y","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,20]]},"assertion":[{"value":"11 October 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 March 2026","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 March 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 April 2026","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 have no conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval and Consent to Participate"}},{"value":"All authors have reviewed this paper and agreed to publish this paper.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for Publication"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Materials Availability"}},{"value":"The code is based on the standard Pytorch and MPI.","order":6,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code Availability"}}],"article-number":"101"}}