A Hassle-free Algorithm for Private Learning in Practice: Don't Use Tree Aggregation, Use BLTs
<|reference_start|>A Hassle-free Algorithm for Private Learning in Practice: Don't Use Tree Aggregation, Use BLTs: 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.<|reference_end|>
@article{mcmahan2024a,
    title={A Hassle-free Algorithm for Private Learning in Practice: Don't Use Tree
  Aggregation, Use BLTs},
    author={H. Brendan McMahan, Zheng Xu, Yanxiang Zhang},
    journal={arXiv preprint arXiv:2408.08868},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.08868},
    primaryClass={cs.LG}
}