Federated Nonconvex Sparse Learning

Abstract

Nonconvex sparse learning plays an essential role in many areas, such as signal processing and deep network compression. Iterative hard thresholding (IHT) methods are the state-of-the-art for nonconvex sparse learning due to their capability of recovering true support and scalability with large datasets. Theoretical analysis of IHT is currently based on centralized IID data. In realistic large-scale situations, however, data are distributed, hardly IID, and private to local edge computing devices. It is thus necessary to examine the property of IHT in federated settings, which update in parallel on local devices and communicate with a central server only once in a while without sharing local data. In this paper, we propose two IHT methods: Federated Hard Thresholding (Fed-HT) and Federated Iterative Hard Thresholding (FedIter-HT). We prove that both algorithms enjoy a linear convergence rate and have strong guarantees to recover the optimal sparse estimator, similar to traditional IHT methods, but now with decentralized non-IID data. Empirical results demonstrate that the Fed-HT and FedIter-HT outperform their competitor - a distributed IHT, in terms of decreasing the objective values with lower requirements on communication rounds and bandwidth.

References in corpus (11)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification
• Federated Optimization in Heterogeneous Networks
• Sparse Representation for Wireless Communications: A Compressive Sensing Approach
• Adaptive Federated Optimization
• Distributed Compressed Sensing For Static and Time-Varying Networks
• On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
• On Learning Discrete Graphical Models Using Greedy Methods
• Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction

Cited by in corpus (3)

• FedGiA: An Efficient Hybrid Algorithm for Federated Learning
• Communication-Efficient ADMM-based Federated Learning
• Federated Composite Optimization