{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T08:32:48Z","timestamp":1789720368383,"version":"4.0.1"},"reference-count":72,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"name":"DOD National Defense Science and Engineering NDSEG Research Fellowship"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1924935"],"award-info":[{"award-number":["DMS-1924935"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1952339"],"award-info":[{"award-number":["DMS-1952339"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2110145"],"award-info":[{"award-number":["DMS-2110145"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2152717"],"award-info":[{"award-number":["DMS-2152717"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2152762"],"award-info":[{"award-number":["DMS-2152762"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2208361"],"award-info":[{"award-number":["DMS-2208361"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1750704"],"award-info":[{"award-number":["CNS-1750704"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1932447"],"award-info":[{"award-number":["CNS-1932447"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-2114113"],"award-info":[{"award-number":["CNS-2114113"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-SC0021142"],"award-info":[{"award-number":["DE-SC0021142"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Appl. Math."],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:p>We propose near-optimal overlay networks based on $d$-regular expander graphs to accelerate decentralized federated learning (DFL) and improve its generalization. In DFL a massive number of clients are connected by an overlay network, and they solve machine learning problems collaboratively without sharing raw data. Our overlay network design integrates spectral graph theory and the theoretical convergence and generalization bounds for DFL. As such, our proposed overlay networks accelerate convergence, improve generalization, and enhance robustness to client failures in DFL with theoretical guarantees. Also, we present an efficient algorithm to convert a given graph to a practical overlay network and maintain the network topology after potential client failures. We numerically verify the advantages of DFL with our proposed networks on various benchmark tasks, ranging from image classification to language modeling using hundreds of clients.<\/jats:p>","DOI":"10.1137\/21m1465081","type":"journal-article","created":{"date-parts":[[2022,8,18]],"date-time":"2022-08-18T09:39:41Z","timestamp":1660815581000},"page":"1558-1586","source":"Crossref","is-referenced-by-count":25,"title":["Efficient and Reliable Overlay Networks for Decentralized Federated Learning"],"prefix":"10.1137","volume":"82","author":[{"given":"Yifan","family":"Hua","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4050-1849","authenticated-orcid":true,"given":"Kevin","family":"Miller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrea L.","family":"Bertozzi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chen","family":"Qian","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4848-4791","authenticated-orcid":true,"given":"Bao","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2022,8,18]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-58986-8_14"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004965"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-020-4429-x"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008851"},{"key":"atypb6","volume-title":"Proceedings of the 25th Annual Conference on Learning Theory, JMLR Workshop and Conference Proceedings 23","author":"Balcan M. F.","year":"2012"},{"key":"atypb7","volume-title":"Practical Secure Aggregation for Federated Learning on User-Held Data, preprint, https:\/\/arxiv.org\/abs\/1611.04482","author":"Bonawitz K.","year":"2016"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144503423264"},{"key":"atypb9","volume-title":"Anonymizing Data for Privacy-Preserving Federated Learning, preprint, https:\/\/arxiv.org\/abs\/2002.09096","author":"Choudhury O.","year":"2020"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.2016.7869675"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-005-0237-z"},{"key":"atypb12","volume-title":"CBMS Reg. Conf. Ser. Math. 92","author":"Chung F. R.","year":"1997"},{"key":"atypb13","first-page":"55","volume":"6","author":"Elisseeff A.","year":"2005","journal-title":"J. Mach. Learn. Rese."},{"key":"atypb14","first-page":"17","volume":"5","author":"Erd\u00f6s P.","year":"1960","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.5"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/MLSP.2014.6958862"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.21136\/CMJ.1973.101168"},{"key":"atypb18","volume-title":"Differentially Private Federated Learning: A Client Level Perspective, preprint, https:\/\/arxiv.org\/abs\/1712.07557","author":"Geyer R. C.","year":"2017"},{"key":"atypb19","volume-title":"International Conference on Machine Learning","author":"Hardt M.","year":"2016"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2012.08.009"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"atypb22","volume-title":"Advances in Neural Information Processing Systems","author":"Jiang P.","year":"2018"},{"key":"atypb23","volume-title":"Advances and Open Problems in Federated Learning, preprint, https:\/\/arxiv.org\/abs\/1912.04977","author":"Kairouz P.","year":"2019"},{"key":"atypb24","first-page":"5132","volume-title":"International Conference on Machine Learning, PMLR","author":"Karimireddy S. P.","year":"2020"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/1993744.1993770"},{"key":"atypb26","first-page":"2133","volume-title":"Proceedings of IEEE INFOCOM, IEEE","author":"Law C.","year":"2003"},{"key":"atypb27","volume-title":"Proceedings of Machine Learning and Systems 2020 (MLSys 2020)","author":"Li T.","year":"2020"},{"key":"atypb28","volume-title":"ICLR, 2020","author":"Li X.","year":"2020"},{"key":"atypb29","volume-title":"Exploring Private Federated Learning with Laplacian Smoothing, preprint, https:\/\/arxiv.org\/abs\/2005.00218","author":"Liang Z.","year":"2020"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2020.3036948"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59410-7_33"},{"key":"atypb32","first-page":"18261","volume-title":"Curran Associates","author":"Liu Y.","year":"2020"},{"key":"atypb33","volume-title":"Enhancing the Privacy of Federated Learning with Sketching, preprint, https:\/\/arxiv.org\/abs\/1911.01812","author":"Liu Z.","year":"2019"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2005.1610546"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-2011-01359-3"},{"key":"atypb36","volume-title":"Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS 2020","author":"Marfoq O.","year":"2020"},{"key":"atypb37","first-page":"456","volume-title":"The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics","author":"McDonald R.","year":"2010"},{"key":"atypb38","first-page":"1273","volume-title":"Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (Fort Lauderdale, FL), A. Singh and J. Zhu, eds., Proc. Mach. Learn. Res. 54","author":"McMahan B.","year":"2017"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2019.00029"},{"key":"atypb40","first-page":"33","volume":"18","author":"Murty M. R.","year":"2003","journal-title":"J. Ramanujan Math. Soc."},{"key":"atypb41","first-page":"91","volume":"6","author":"Murty M. R.","year":"2020","journal-title":"Indian J. Discrete Math."},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2008.2009515"},{"key":"atypb43","volume-title":"Master's thesis","author":"Newman M. W.","year":"2001"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2019.00016"},{"key":"atypb45","volume-title":"Gradient-Leaks: Understanding and Controlling Deanonymization in Federated Learning, preprint, https:\/\/arxiv.org\/abs\/1805.05838","author":"Orekondy T.","year":"2018"},{"key":"atypb46","volume-title":"Fedsplit: An Algorithmic Framework for Fast Federated Optimization, preprint, https:\/\/arxiv.org\/abs\/2005.05238","author":"Pathak R.","year":"2020"},{"key":"atypb47","first-page":"791","volume":"4","author":"Polyak B. T.","year":"1964","journal-title":"Fiz."},{"key":"atypb48","volume-title":"Parallel Training of DNNs with Natural Gradient and Parameter Averaging, preprint, https:\/\/arxiv.org\/abs\/1410.7455","author":"Povey D.","year":"2014"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2014.2361773"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1109\/LCSYS.2021.3090652"},{"key":"atypb51","volume-title":"Adaptive Federated Optimization, preprint, https:\/\/arxiv.org\/abs\/2003.00295","author":"Reddi S.","year":"2020"},{"key":"atypb52","first-page":"2635","volume":"11","author":"Shalev-Shwartz S.","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2014.7028543"},{"key":"atypb54","first-page":"225","volume-title":"Proceedings of USENIX NSDI, USENIX","author":"Singla A.","year":"2012"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1109\/18.556667"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1544-8_25"},{"key":"atypb57","first-page":"1","volume":"21","author":"Stich S. U.","year":"2020","journal-title":"J. Mach. Learn. Res."},{"key":"atypb58","volume-title":"Proceedings of the 34th AAAI Conference on Artificial Intelligence","author":"Sun T.","year":"2021"},{"key":"atypb59","volume-title":"Decentralized Federated Averaging, preprint, https:\/\/arxiv.org\/abs\/2104.11375","author":"Sun T.","year":"2021"},{"key":"atypb60","doi-asserted-by":"publisher","DOI":"10.1109\/BigData47090.2019.9005465"},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1145\/3338501.3357370"},{"key":"atypb62","doi-asserted-by":"publisher","DOI":"10.1145\/3378679.3394533"},{"key":"atypb63","volume-title":"Cooperative SGD: A Unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms, preprint, https:\/\/arxiv.org\/abs\/1808.07576","author":"Wang J.","year":"2018"},{"key":"atypb64","doi-asserted-by":"publisher","DOI":"10.1109\/ICC47138.2019.9123209"},{"key":"atypb65","volume-title":"A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network, prepring, https:\/\/arxiv.org\/abs\/2010.01618","author":"Wang J.-K.","year":"2020"},{"key":"atypb66","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2020.2988575"},{"key":"atypb67","doi-asserted-by":"publisher","DOI":"10.1145\/3338501.3357371"},{"key":"atypb68","first-page":"7184","volume-title":"Proceedings of the 36th International Conference on Machine Learning, K. Chaudhuri and R. Salakhutdinov, eds., Proc. Mach. Learn. Res. 97","author":"Yu H.","year":"2019"},{"key":"atypb69","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2014.23"},{"key":"atypb70","volume-title":"On the Convergence of Decentralized Gradient Descent, preprint, https:\/\/arxiv.org\/abs\/1310.7063","author":"Yuan K.","year":"2013"},{"key":"atypb71","volume-title":"Deep learning with elastic averaging SGD, preprint, https:\/\/arxiv.org\/abs\/1412.6651","author":"Zhang S.","year":"2014"},{"key":"atypb72","volume-title":"FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data, preprint, https:\/\/arxiv.org\/abs\/2005.11418","author":"Zhang X.","year":"2020"}],"container-title":["SIAM Journal on Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1465081","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T11:12:49Z","timestamp":1787224369000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1465081"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8]]},"references-count":72,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["10.1137\/21M1465081"],"URL":"https:\/\/doi.org\/10.1137\/21m1465081","relation":{},"ISSN":["0036-1399","1095-712X"],"issn-type":[{"value":"0036-1399","type":"print"},{"value":"1095-712X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8]]}}}