mlsanityData to 7 Oct 2026

A Hassle-free Algorithm for Private Learning in Practice: Don't Use Tree Aggregation, Use BLTs

arXiv 2408.08868 ↗First posted 16 Aug 2024cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

The state-of-the-art for training on-device language models for mobile keyboard applications combines federated learning (FL) with differential privacy (DP) via the DP-Follow-the-Regularized-Leader (DP-FTRL) algorithm. Two variants of DP-FTRL are used in practice, tree aggregation and matrix factorization. However, tree aggregation suffers from significantly suboptimal privacy/utility tradeoffs, while matrix mechanisms require expensive optimization parameterized by hard-to-estimate-in-advance constants, and high runtime memory costs. This paper extends the recently introduced Buffered Linear Toeplitz (BLT) mechanism to multi-participation scenarios. Our BLT-DP-FTRL maintains the ease-of-use advantages of tree aggregation, while essentially matching matrix factorization in terms of utility and privacy. We evaluate BLT-DP-FTRL on the StackOverflow dataset, serving as a re-producible simulation benchmark, and across four on-device language model tasks in a production FL system. Our empirical results highlight the advantages of the BLT mechanism and elevate the practicality and effectiveness of DP in real-world scenarios.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 26 of its 37 references that are in the map. First posted on arXiv 16 Aug 2024.

Builds on

26 of 37 references.

References · 26

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2019Advances and Open Problems in Federated Learningcited by 3,021
  3. 2016Deep Learning with Differential Privacycited by 2,682
  4. 2020mT5: A massively multilingual pre-trained text-to-text transformercited by 1,813
  5. 2019Towards Federated Learning at Scale: System Designcited by 826
  6. 2018Federated Learning for Mobile Keyboard Predictioncited by 565
  7. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  8. 2021A Field Guide to Federated Optimizationcited by 312
  9. 2021Practical and Private (Deep) Learning without Sampling or Shufflingcited by 169
  10. 2021Papaya: Practical, Private, and Scalable Federated Learningcited by 89
  11. 2023Federated Learning of Gboard Language Models with Differential Privacycited by 64
  12. 2022Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streamscited by 59
14 more
  1. 2022Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributionscited by 50
  2. 2023(Amplified) Banded Matrix Factorization: A unified approach to private trainingcited by 49
  3. 2022Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learningcited by 48
  4. 2023Can Public Large Language Models Help Private Cross-device Federated Learning?cited by 30
  5. 2024Fine-Tuning Large Language Models with User-Level Differential Privacycited by 28
  6. 2022Learning to Generate Image Embeddings with User-level Differential Privacycited by 23
  7. 2024Mind the Privacy Unit! User-Level Differential Privacy for Language Model Fine-Tuningcited by 21
  8. 2024Prompt Public Large Language Models to Synthesize Data for Private On-device Applicationscited by 17
  9. 2024Efficient and Near-Optimal Noise Generation for Streaming Differential Privacycited by 17
  10. 2023A Smooth Binary Mechanism for Efficient Private Continual Observationcited by 12
  11. 2024Banded Square Root Matrix Factorization for Differentially Private Model Trainingcited by 12
  12. 2024Scaling up the Banded Matrix Factorization Mechanism for Differentially Private MLcited by 12
  13. 2023Private Federated Learning in Gboardcited by 5
  14. 2024Confidential Federated Computationscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 5; 2026: 2.

9 papers.

  1. 2024Federated Learning in Practice: Reflections and Projectionscited by 15
  2. 2025Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGDcited by 7
  3. 2025An Inversion Theorem for Buffered Linear Toeplitz (BLT) Matrices and Applications to Streaming Differential Privacycited by 3
  4. 2025Private Continual Counting of Unbounded Streamscited by 2
  5. 2024Debiasing Federated Learning with Correlated Client Participationcited by 1
  6. 2025Cocoon: A System Architecture for Differentially Private Training with Correlated Noisescited by 1
  7. 2026DP-λCGD: Efficient Noise Correlation for Differentially Private Model Trainingcited by 1
  8. 2025Securing Private Federated Learning in a Malicious Setting: A Scalable TEE-Based Approach with Client Auditingcited by 0
  9. 2026Beyond Square Roots: A Memory-Efficient Explicit Factorization for Multi-Epoch Private Learningcited by 0