Abstract: Federated learning(FL) is a new distributed learning framework for privacy protection,which is different from traditional distributed machine learning:1)differences in communication,computing,and storage performance among devices(device heterogeneity),2)differences in data distribution and data volume(data heterogeneity),and 3)high communication consumption.Under heterogeneous conditions,the data distribution of clients varies greatly,which leads to the decrease of model convergence speed.Especially in the case of highly heterogeneous condition,the traditional FL algorithm cannot converge and the training loss curve will fluctuate greatly with the increase of local iterations.In this work,a FL algorithm based on stratified sampling optimization(FedSSO) is proposed.In FedSSO,a density-based clustering method is used to divide the overall client into different clusters.Then,some available clients are proportionally extracted from different clusters to participate in training.Therefore,various data are involved in each training round to ensure that FL can accelerate convergence to the optimal solution.The strategy of learning rate decay and the choice of local iterations is set to ensure the convergence.The convergence of FedSSO algorithm is proved theoretically and experimentally,andthe superiority of FedSSO is demonstrated by comparing it with other FL algorithms on public MNIST,Cifar-10,and Sentiment140 datasets.

Key words: Federated learning, Privacy protection, Clustering, Stratified sampling, Distributed optimization, Convergence analysis