Just Accepted
Clipper: Online Joint Client Sampling and Power Allocation for Wireless Federated Learning
Authors: 
Wen Xu, Ben Liang, Gary Boudreau, Hamza SokunAuthors Info & Claims
Wen Xu, Ben Liang, Gary Boudreau, Hamza SokunAuthors Info & ClaimsAccepted on 17 October 2024
Abstract
Communication overhead is a main bottleneck in federated learning (FL) especially in the wireless environment due to the limited data rate and unstable radio channels. The communication challenge necessitates holistic selection of participating clients that accounts for both the computation needs and communication cost, as well as judicious allocation of the limited transmission resource. Meanwhile, the random unpredictable nature of both the training data samples and the communication channels requires an online optimization approach that adapts to the changing system state over time. In this work, we consider a general framework of online joint client sampling and power allocation for wireless FL under time-varying communication channels. We formulate it as a stochastic network optimization problem that admits a Lyapunov-typed solution approach. This leads to per-training-round subproblems with a special bi-convex structure, which we leverage to propose globally optimal solutions, culminating in a meta algorithm that provides strong performance guarantees. We further study three specific FL problems covering multiple scenarios, namely with IID or non-IID data, whether robustness against data drift is required, and with unbiased or biased client sampling. We derive detailed algorithms for each of these problems. Simulation with standard classification tasks demonstrate that the proposed communication-aware algorithms outperform their counterparts under a wide range of learning and communication scenarios.
References
[1]
Dan Alistarh, Demjan Grubic, Jerry Z. Li, Ryota Tomioka, and Milan Vojnovic. 2017. QSGD: Communication-efficient SGD via gradient quantization and encoding. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS).
[2]
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečnỳ, Stefano Mazzocchi, Brendan McMahan, Timon Van Overveldt, David Petrou, Daniel Ramage, and Jason Roselander. 2019. Towards federated learning at scale: System design. In Proceedings of Machine Learning and Systems (MLSys).
[3]
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. 2018. Optimization Methods for Large-Scale Machine Learning. SIAM Rev. 60, 2 (2018), 223–311.
[4]
Stephen Boyd and Lieven Vandenberghe. 2004. Convex optimization. Cambridge University Press.
[5]
Zheng Chai, Ahsan Ali, Syed Zawad, Stacey Truex, Ali Anwar, Nathalie Baracaldo, Yi Zhou, Heiko Ludwig, Feng Yan, and Yue Cheng. 2020. TiFL: A Tier-Based Federated Learning System. In Proceedings of International Symposium on High-Performance Parallel and Distributed Computing (HPDC).
[6]
Mingzhe Chen, H. Vincent Poor, Walid Saad, and Shuguang Cui. 2021. Convergence Time Optimization for Federated Learning Over Wireless Networks. IEEE Transactions on Wireless Communications 20, 4(2021), 2457–2471.
[7]
Mingzhe Chen, Zhaohui Yang, Walid Saad, Changchuan Yin, H. Vincent Poor, and Shuguang Cui. 2021. A joint learning and communications framework for federated learning over wireless networks. IEEE Transactions on Wireless Communications 20, 1(2021), 269–283.
[8]
Wenlin Chen, Samuel Horváth, and Peter Richtárik. 2022. Optimal Client Sampling for Federated Learning. Transactions on Machine Learning Research(2022).
[9]
Yae Jee Cho, Jianyu Wang, and Gauri Joshi. 2022. Towards understanding biased client selection in federated learning. In Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS).
[10]
Canh T. Dinh, Nguyen H. Tran, Minh N. H. Nguyen, Choong Seon Hong, Wei Bao, Albert Y. Zomaya, and Vincent Gramoli. 2021. Federated learning over wireless networks: convergence analysis and resource allocation. IEEE/ACM Transactions on Networking 29, 1 (2021), 398–409.
[11]
Wei Guo, Ran Li, Chuan Huang, Xiaoqi Qin, Kaiming Shen, and Wei Zhang. 2022. Joint Device Selection and Power Control for Wireless Federated Learning. IEEE Journal on Selected Areas in Communications 40, 8(2022), 2395–2410.
[12]
Samuel Horváth and Peter Richtárik. 2019. Nonconvex Variance Reduced Optimization with Arbitrary Sampling. In Proceedings of International Conference on Machine Learning (ICML).
[13]
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. Da Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, AdriA Gascan, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Azgaer, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian TramAsr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. 2021. Advances and open problems in federated learning. Foundations and Trends in Machine Learning 14, 1-2 (2021), 1–210.
[14]
Faeze Moradi Kalarde, Min Dong, Ben Liang, Yahia A. Eldemerdash Ahmed, and Ho Ting Cheng. 2024. Beamforming and Device Selection Design in Federated Learning With Over-the-Air Aggregation. IEEE Open Journal of the Communications Society 5 (2024), 1710–1723.
[15]
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. 2020. SCAFFOLD: Stochastic Controlled Averaging for Federated Learning. In Proceedings of International Conference on Machine Learning (ICML).
[16]
Nikola Konstantinov and Christoph Lampert. 2019. Robust learning from untrusted sources. In Proceedings of International Conference on Machine Learning (ICML).
[17]
Mu Li, David G Andersen, Jun Woo Park, Alexander J Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J Shekita, and Bor-Yiing Su. 2014. Scaling distributed machine learning with the parameter server. In Proceedings of USENIX Symposium on Operating Systems Design and Implementation (OSDI).
[18]
Tian Li, Anit Kumar Sahu, Ameet S. Talwalkar, and Virginia Smith. 2020. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine 37 (2020), 50–60.
[19]
Bing Luo, Wenli Xiao, Shiqiang Wang, Jianwei Huang, and Leandros Tassiulas. 2022. Tackling System and Statistical Heterogeneity for Federated Learning with Adaptive Client Sampling. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM).
[20]
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. 2017. Communication-efficient learning of deep Networks from decentralized data. In Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS).
[21]
M. Neely. 2010. Stochastic network optimization with application to communication and queueing systems. Morgan & Claypool. 1–211 pages.
[22]
Takayuki Nishio and Ryo Yonetani. 2019. Client selection for federated learning with heterogeneous resources in mobile edge. In Proceedings of IEEE International Conference on Communications (ICC).
[23]
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. PyTorch: An imperative style, high-performance deep learning library. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS).
[24]
Jake Perazzone, Shiqiang Wang, Mingyue Ji, and Kevin S Chan. 2022. Communication-efficient device scheduling for federated learning using stochastic optimization. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM).
[25]
Amirhossein Reisizadeh, Isidoros Tziotis, Hamed Hassani, Aryan Mokhtari, and Ramtin Pedarsani. 2022. Straggler-Resilient Federated Learning: Leveraging the Interplay Between Statistical Accuracy and System Heterogeneity. IEEE Journal on Selected Areas in Information Theory 3, 2 (2022), 197–205.
[26]
Jinke Ren, Yinghui He, Dingzhu Wen, Guanding Yu, Kaibin Huang, and Dongning Guo. 2020. Scheduling for cellular federated edge learning with importance and channel awareness. IEEE Transactions on Wireless Communications 19, 11(2020), 7690–7703.
[27]
Sebastian U Stich. 2019. Local SGD converges fast and communicates little. In Proceedings of International Conference on Learning Representations (ICLR).
[28]
Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan S. Rellermeyer. 2020. A survey on distributed machine learning. Comput. Surveys 53, 2 (2020), 1–33.
[29]
Jianyu Wang and Gauri Joshi. 2021. Cooperative SGD: A unified framework for the design and analysis of local-update SGD algorithms. Journal of Machine Learning Research 22, 1 (2021), 9709–9758.
[30]
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. 2018. Gradient sparsification for communication-efficient distributed optimization. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS).
[31]
Han Xiao, Kashif Rasul, and Roland Vollgraf. 2017. Fashion-MNIST: A novel image dataset for benchmarking machine learning algorithms. https://github.com/zalandoresearch/fashion-mnist.
[32]
Jie Xu and Heqiang Wang. 2020. Client selection and bandwidth allocation in wireless federated learning networks: A long-term perspective. IEEE Transactions on Wireless Communications 20, 2(2020), 1188–1200.
[33]
Wen Xu, Ben Liang, Gary Boudreau, and Hamza Sokun. 2023. Probabilistic client sampling and power allocation for wireless federated learning. In Proceedings of the IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC).
[34]
Kai Yang, Tao Jiang, Yuanming Shi, and Zhi Ding. 2020. Federated Learning via Over-the-Air Computation. IEEE Transactions on Wireless Communications 19, 3(2020), 2022–2035.
[35]
Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. 2019. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology 10, 2(2019), 1–19.
[36]
Maojun Zhang, Guangxu Zhu, Shuai Wang, Jiamo Jiang, Qing Liao, Caijun Zhong, and Shuguang Cui. 2022. Communication-efficient federated edge learning via optimal probabilistic device scheduling. IEEE Transactions on Wireless Communications 21, 10(2022), 8536–8551.
[37]
Konglin Zhu, Fuchun Zhang, Lei Jiao, Bowei Xue, and Lin Zhang. 2024. Client selection for federated learning using combinatorial multi-armed bandit under long-term energy constraint. Computer Networks 250(2024), 110512.
Index Terms
- Clipper: Online Joint Client Sampling and Power Allocation for Wireless Federated Learning
Recommendations
Client Selection and Resource Allocation via Graph Neural Networks for Efficient Federated Learning in Healthcare Environments
PETRA '24: Proceedings of the 17th International Conference on PErvasive Technologies Related to Assistive EnvironmentsTwo of the most significant challenges in decentralized federated learning are resource allocation and client selection. In order to address certain aspects of these challenges, in this paper we introduce a novel approach based on graph neural networks (...
Reducing communication in federated learning via efficient client sampling
AbstractFederated learning (FL) ameliorates privacy concerns in settings where a central server coordinates learning from data distributed across many clients; rather than sharing the data, the clients train locally and report the models they learn to ...
Highlights- Federated learning systems that operate under communication constraints require careful selection of participating clients.
- Stochastic modeling via the Ornstein–Uhlenbeck process helps understand effects of various update aggregation ...
Mobility aware and energy-efficient federated deep reinforcement learning assisted resource allocation for 5G-RAN slicing
AbstractNetwork slicing is one of the foundations for the realization of 5G and beyond. However, due to the mobility of the users and the network dynamics, flexible and efficient radio access network (RAN) resource slicing is still a challenge. In this ...
Comments
Information & Contributors
Information
Published In
EISSN:2376-3647
Table of ContentsCopyright © 2024 Copyright held by the owner/author(s). Publication rights licensed to ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Online AM: 08 November 2024
Accepted: 17 October 2024
Revised: 26 August 2024
Received: 02 May 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 115Total Downloads
- Downloads (Last 12 months)115
- Downloads (Last 6 weeks)52
Reflects downloads up to 05 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in