A Hassle-free Algorithm for Strong Differential Privacy in Federated Learning Systems

Hugh McMahan, Zheng Xu, Yanxiang ZhangEMNLP 2024 · DOI

TL;DR

This paper introduces BLT-DP-FTRL, a novel algorithm that significantly improves the privacy-utility trade-off for training language models on mobile devices using federated learning. It offers a practical and flexible solution that matches state-of-the-art performance while being easier to implement and more memory-efficient than existing methods.

What Problem Does This Paper Address?

Training language models (LMs) on mobile devices is crucial for features like auto-correction and predictive text. However, user data is highly sensitive, necessitating strong privacy guarantees. Federated Learning (FL) combined with Differential Privacy (DP) is the standard approach, but achieving a good balance between privacy and model utility (performance) is challenging. Existing DP-FTRL algorithms, while effective, often suffer from complex parameter tuning, high memory usage, or suboptimal privacy-utility trade-offs. Specifically, the paper addresses the difficulty of optimizing DP mechanisms in FL systems where client participation is sporadic and unpredictable (due to factors like charging status and network connectivity).

Methods

The core contribution is the extension of the Buffered Linear Toeplitz (BLT) mechanism to multi-participation scenarios within the DP-FTRL framework.

  • DP-FTRL: This is the foundational algorithm that combines federated learning with differential privacy. It uses a "minimum separation" (min-sep) parameter to control client participation, which is more flexible than traditional sampling methods.
  • Matrix Factorization (MF) for DP: DP-FTRL often relies on matrix factorization to generate correlated noise, which is more efficient for privacy than independent noise.
  • BLT Mechanism: This is a novel approach that uses a specific type of matrix (Toeplitz matrix) with a "buffer decay" parameter. The key innovation is that BLT allows for efficient streaming computation of correlated noise without needing to materialize the entire matrix, significantly reducing memory overhead.
  • Multi-participation Extension: The paper extends the BLT mechanism to handle scenarios with multiple clients participating over time, adapting it to the constraints of real-world FL systems. This involves optimizing BLT parameters for this specific setting.
  • Optimization: The authors use an auto-differentiation framework (JAX) and an L-BFGS optimizer to find the optimal BLT parameters that balance privacy and utility.

Datasets

  • StackOverflow dataset: Used for reproducible simulation benchmarks.
  • Four on-device language model tasks in a production FL system: These tasks involve training language models for mobile keyboard applications across different language-locale combinations (Spanish in Spain, Indonesian in Indonesia, Portuguese in Brazil, and Portuguese in Portugal).

Key Insights and Ideas

  • BLT's Flexibility is Key: The BLT mechanism's ability to handle varying min-separation values and its efficient memory usage make it highly practical for real-world FL deployments, where these parameters are often hard to estimate precisely beforehand.
  • Memory Efficiency Matters: Compared to other advanced DP mechanisms like BANDMF, BLT offers substantial memory savings, making it more feasible for resource-constrained environments like mobile devices.
  • Privacy-Utility Trade-off is Achievable: The paper demonstrates that strong DP guarantees can be achieved without sacrificing model performance, a critical hurdle for deploying private ML systems.
  • Ease of Use: BLT-DP-FTRL simplifies the process of achieving strong DP in FL, making it more accessible for practitioners.

Key Results

  • Superior Privacy-Utility: BLT-DP-FTRL achieves a better privacy-utility trade-off compared to the widely used TREEAGG mechanism and is comparable to the state-of-the-art BANDMF mechanism.
  • Memory Savings: BLT offers significant memory overhead reduction compared to BANDMF and TREEAGG-FULL, with buffer sizes of d=4 achieving competitive results.
  • Robustness: BLT demonstrates robustness to variations in min-separation and total rounds, outperforming BANDMF when these parameters differ significantly from their optimized values.
  • Production Performance: In real-world production settings, BLT-DP-FTRL achieved comparable or better learning accuracy and stronger DP guarantees than existing methods. For example, in some cases, BLT achieved DP guarantees of ε < 1, which are considered very strong.

Limitations and Future Work

  • Parameter Tuning: While BLT is easier to use, optimizing its parameters (θ, ω) can still be computationally intensive, although significantly faster than BANDMF. The paper notes that increasing buffer size 'd' doesn't always improve results and can lead to overparameterization.
  • Future Work: The authors suggest that BLT's advantages could extend to centralized settings for user-level or example-level DP. They also mention that BANDTOEP (a related mechanism) can leverage existing amplification by sampling, which could be explored further. The paper also notes that the optimal loss metric (RmsLoss vs. MaxLoss) for DP-FTRL is still an open question.

Summary updated

BibTeX
@inproceedings{mcmahan2024hassle,
  author = {Hugh McMahan and Zheng Xu and Yanxiang Zhang},
  title = {{A Hassle-free Algorithm for Strong Differential Privacy in Federated Learning Systems}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2024},
  doi = {10.18653/v1/2024.emnlp-industry.64},
}
Figure