Federated Optimization of ℓ0-norm Regularized Sparse Learning

Qianqian Tong, Guannan Liang, Jiahao Ding, Tan Zhu, Miao Pan, Jinbo BiAlgorithms 2022 · DOI · OpenReview

TL;DR

This paper introduces novel federated learning algorithms, Fed-HT and FedIter-HT, designed for sparse learning with decentralized, non-IID data. These methods offer improved communication efficiency and theoretical guarantees for recovering sparse models, outperforming existing distributed approaches.

What Problem Does This Paper Address?

Sparse learning, which aims to identify the most important features in high-dimensional data, is crucial across many fields. Traditional methods often assume centralized, independent and identically distributed (IID) data. However, in real-world scenarios like edge computing or distributed data analysis, data is often decentralized, non-IID, and private. This poses a significant challenge for applying existing sparse learning techniques, particularly iterative hard thresholding (IHT) methods, which are state-of-the-art for nonconvex sparse learning. The paper addresses the need for federated IHT algorithms that can handle these realistic data distributions while maintaining privacy and communication efficiency.

Methods

The paper proposes two new federated algorithms:

  • Federated Hard Thresholding (Fed-HT): This algorithm applies the hard thresholding operator at the central server after aggregating local updates from clients.
  • Federated Iterative Hard Thresholding (FedIter-HT): This more advanced method applies the hard thresholding operator to both local updates on clients and the aggregated update at the central server. This dual application aims to further reduce communication costs by ensuring that the models being communicated are already sparse.

Both algorithms are designed to work with decentralized, non-IID, and unbalanced data. The theoretical analysis provides convergence guarantees and sparsity recovery assurances, comparable to centralized IHT methods, but under these more challenging federated conditions.

Datasets

The paper evaluates its proposed methods on:

  • Simulated datasets: Two simulations (Simulation I for regression, Simulation II for classification) were generated to mimic non-IID and unbalanced data scenarios.
  • Real-world datasets:
    • E2006-tfidf (sparse linear regression)
    • RCV1 (sparse logistic regression)
    • MNIST (multi-class softmax regression)

Key Insights and Ideas

  • Dual Hard Thresholding for Efficiency: Applying hard thresholding not only at the server but also on local client updates (FedIter-HT) significantly boosts communication efficiency. This is because sparse models require less data to transmit.
  • Theoretical Guarantees for Non-IID Data: The paper provides the first theoretical analysis of IHT methods under federated, non-IID, and unbalanced data settings, demonstrating linear convergence rates and sparsity recovery.
  • Trade-off Between Convergence and Bias: The number of local iterations (K) influences the convergence rate and statistical bias. Increasing K can speed up convergence but may increase bias, suggesting a need for careful parameter tuning.
  • FedIter-HT's Advantage: FedIter-HT shows a better statistical estimation bias compared to Fed-HT, making it more robust in certain scenarios.

Key Results

  • Communication Efficiency: FedIter-HT significantly reduces communication rounds compared to a standard Distributed IHT baseline. For instance, it achieved similar objective values with 4-5 times fewer communication rounds in simulations.
  • Performance on Real-World Data: Experiments on E2006-tfidf, RCV1, and MNIST datasets showed that Fed-HT and FedIter-HT consistently outperformed the Distributed IHT baseline in terms of objective function value reduction over communication rounds.
  • Sparsity Recovery: Theoretical results guarantee that both algorithms can recover the optimal sparse estimator, even with decentralized and non-IID data.

Limitations and Future Work

  • Statistical Bias: While improved by FedIter-HT, statistical bias still exists due to the non-IID nature of the data and the inherent limitations of sparse recovery. The paper suggests this might be worth exploring further.
  • Randomness in Federated Learning: The paper notes that federated learning can exhibit more randomness when approaching the optimal solution, potentially due to client dissimilarity. This observation points to future research directions in understanding and mitigating this randomness.
  • Parameter Tuning: The performance of the algorithms is sensitive to parameters like the number of local iterations (K) and learning rates, suggesting that adaptive or automated parameter tuning could be a valuable area for future work.

Summary updated

Abstract

Regularized sparse learning with the ℓ 0 -norm is important in many areas, including statistical learning and signal processing. Iterative hard thresholding (IHT) methods are the state-of-the-art for nonconvex-constrained sparse learning due to their capability of recovering true support and scalability with large datasets. The current theoretical analysis of IHT assumes the use of centralized IID data. In realistic large-scale scenarios, however, data are distributed, seldom IID, and private to edge computing devices at the local level. Consequently, it is required to study the property of IHT in a federated environment, where local devices update the sparse model individually and communicate with a central server for aggregation infrequently without sharing local data. In this paper, we propose the first group of federated IHT methods: Federated Hard Thresholding (Fed-HT) and Federated Iterative Hard Thresholding (FedIter-HT) with theoretical guarantees. We prove that both algorithms have a linear convergence rate and guarantee for recovering the optimal sparse estimator, which is comparable to classic IHT methods, but with decentralized, non-IID, and unbalanced data. Empirical results demonstrate that the Fed-HT and FedIter-HT outperform their competitor—a distributed IHT, in terms of reducing objective values with fewer communication rounds and bandwidth requirements.
BibTeX
@article{tong2022federated,
  author = {Qianqian Tong and Guannan Liang and Jiahao Ding and Tan Zhu and Miao Pan and Jinbo Bi},
  title = {{Federated Optimization of ℓ0-norm Regularized Sparse Learning}},
  journal = {Algorithms},
  year = {2022},
  doi = {10.3390/a15090319},
}
Figure