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

arXiv: https://arxiv.org/abs/2408.08868 · HTML: https://mlsanity.com/paper/2408.08868/

## Key facts

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

## Builds on (most cited first, 26 of 26)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [mT5: A massively multilingual pre-trained text-to-text transformer](https://mlsanity.com/paper/2010.11934/) (2020)
- [Towards Federated Learning at Scale: System Design](https://mlsanity.com/paper/1902.01046/) (2019)
- [Federated Learning for Mobile Keyboard Prediction](https://mlsanity.com/paper/1811.03604/) (2018)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Papaya: Practical, Private, and Scalable Federated Learning](https://mlsanity.com/paper/2111.04877/) (2021)
- [Federated Learning of Gboard Language Models with Differential Privacy](https://mlsanity.com/paper/2305.18465/) (2023)
- [Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams](https://mlsanity.com/paper/2202.08312/) (2022)
- [Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions](https://mlsanity.com/paper/2207.04380/) (2022)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning](https://mlsanity.com/paper/2211.06530/) (2022)
- [Can Public Large Language Models Help Private Cross-device Federated Learning?](https://mlsanity.com/paper/2305.12132/) (2023)
- [Fine-Tuning Large Language Models with User-Level Differential Privacy](https://mlsanity.com/paper/2407.07737/) (2024)
- [Mind the Privacy Unit! User-Level Differential Privacy for Language Model Fine-Tuning](https://mlsanity.com/paper/2406.14322/) (2024)
- [Learning to Generate Image Embeddings with User-level Differential Privacy](https://mlsanity.com/paper/2211.10844/) (2022)
- [Prompt Public Large Language Models to Synthesize Data for Private On-device Applications](https://mlsanity.com/paper/2404.04360/) (2024)
- [Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy](https://mlsanity.com/paper/2404.16706/) (2024)
- [Scaling up the Banded Matrix Factorization Mechanism for Differentially Private ML](https://mlsanity.com/paper/2405.15913/) (2024)
- [A Smooth Binary Mechanism for Efficient Private Continual Observation](https://mlsanity.com/paper/2306.09666/) (2023)
- [Banded Square Root Matrix Factorization for Differentially Private Model Training](https://mlsanity.com/paper/2405.13763/) (2024)
- [Private Federated Learning in Gboard](https://mlsanity.com/paper/2306.14793/) (2023)
- [Confidential Federated Computations](https://mlsanity.com/paper/2404.10764/) (2024)

## Built on by (most cited first, 9 of 9)

- [Federated Learning in Practice: Reflections and Projections](https://mlsanity.com/paper/2410.08892/) (2024)
- [Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD](https://mlsanity.com/paper/2505.12128/) (2025)
- [An Inversion Theorem for Buffered Linear Toeplitz (BLT) Matrices and Applications to Streaming Differential Privacy](https://mlsanity.com/paper/2504.21413/) (2025)
- [DP-λCGD: Efficient Noise Correlation for Differentially Private Model Training](https://mlsanity.com/paper/2601.22334/) (2026)
- [Private Continual Counting of Unbounded Streams](https://mlsanity.com/paper/2506.15018/) (2025)
- [Debiasing Federated Learning with Correlated Client Participation](https://mlsanity.com/paper/2410.01209/) (2024)
- [Securing Private Federated Learning in a Malicious Setting: A Scalable TEE-Based Approach with Client Auditing](https://mlsanity.com/paper/2509.08709/) (2025)
- [Cocoon: A System Architecture for Differentially Private Training with Correlated Noises](https://mlsanity.com/paper/2510.07304/) (2025)
- [Beyond Square Roots: A Memory-Efficient Explicit Factorization for Multi-Epoch Private Learning](https://mlsanity.com/paper/2605.18379/) (2026)

## 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.