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

• URL: http://arxiv.org/abs/2408.08868v3
• Date: Thu, 29 May 2025 20:44:31 GMT
• Title: A Hassle-free Algorithm for Private Learning in Practice: Don't Use Tree Aggregation, Use BLTs
• Authors: H. Brendan McMahan, Zheng Xu, Yanxiang Zhang,
• Abstract summary: This paper extends the recently introduced Buffered Linear Toeplitz (BLT) mechanism to multi-participation scenarios.<n>Our BLT-DP-FTRL maintains the ease-of-use advantages of tree aggregation, while essentially matching matrix factorization in terms of utility and privacy.
• Score: 4.736297244235246
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Intersection of Reinforcement Learning and Bayesian Optimization for Intelligent Control of Industrial Processes: A Safe MPC-based DPG using Multi-Objective BO [0.0]
  Model Predictive Control (MPC)-based Reinforcement Learning (RL) offers a structured and interpretable alternative to Deep Neural Network (DNN)-based RL methods.<n>Standard MPC-RL approaches often suffer from slow convergence, suboptimal policy learning due to limited parameterization, and safety issues during online adaptation.<n>We propose a novel framework that integrates MPC-RL with Multi-Objective Bayesian Optimization (MOBO)
  arXiv  Detail & Related papers  (2025-07-14T02:31:52Z)
• Optimizing Communication and Device Clustering for Clustered Federated Learning with Differential Privacy [28.120922916868683]
  We propose a secure and communication-efficient clustered federated learning (CFL) design.<n>In our model, several base stations (BSs) with heterogeneous task-handling capabilities and multiple users with non-independent and identically distributed (non-IID) data jointly perform CFL training.<n>We propose a novel dynamic penalty function assisted value multi-agent reinforcement learning (DPVD-MARL) algorithm that enables distributed BSs to independently determine their connected users.
  arXiv  Detail & Related papers  (2025-07-09T22:44:26Z)
• Scaling Probabilistic Circuits via Monarch Matrices [109.65822339230853]
  Probabilistic Circuits (PCs) are tractable representations of probability distributions.<n>We propose a novel sparse and structured parameterization for the sum blocks in PCs.
  arXiv  Detail & Related papers  (2025-06-14T07:39:15Z)
• Accelerating RL for LLM Reasoning with Optimal Advantage Regression [52.0792918455501]
  We propose a novel two-stage policy optimization framework that directly approximates the optimal advantage function.<n>$A$*-PO achieves competitive performance across a wide range of mathematical reasoning benchmarks.<n>It reduces training time by up to 2$times$ and peak memory usage by over 30% compared to PPO, GRPO, and REBEL.
  arXiv  Detail & Related papers  (2025-05-27T03:58:50Z)
• Pruning-Based TinyML Optimization of Machine Learning Models for Anomaly Detection in Electric Vehicle Charging Infrastructure [8.29566258132752]
  This paper investigates a pruning method for anomaly detection in resource-constrained environments, specifically targeting EVCI. optimized models achieved significant reductions in model size and inference times, with only a marginal impact on their performance. Notably, our findings indicate that, in the context of EVCI, pruning and FS can enhance computational efficiency while retaining critical anomaly detection capabilities.
  arXiv  Detail & Related papers  (2025-03-19T00:18:37Z)
• PLM: Efficient Peripheral Language Models Hardware-Co-Designed for Ubiquitous Computing [48.30406812516552]
  We introduce the PLM, a Peripheral Language Model, developed through a co-design process that jointly optimize model architecture and edge system constraints. PLM employs a Multi-head Latent Attention mechanism and employs the squared ReLU activation function to encourage sparsity, thereby reducing peak memory footprint. evaluation results demonstrate that PLM outperforms existing small language models trained on publicly available data.
  arXiv  Detail & Related papers  (2025-03-15T15:11:17Z)
• DMM: Distributed Matrix Mechanism for Differentially-Private Federated Learning Based on Constant-Overhead Linear Secret Resharing [51.336015600778396]
  We introduce the distributed matrix mechanism to achieve the best-of-both-worlds; better privacy of distributed DP and better utility from the matrix mechanism.<n>We accomplish this using a novel cryptographic protocol that securely transfers sensitive values across client committees of different training iterations with constant communication overhead.
  arXiv  Detail & Related papers  (2024-10-21T16:25:14Z)
• Pluto and Charon: A Time and Memory Efficient Collaborative Edge AI Framework for Personal LLMs Fine-Tuning [13.26886445965894]
  Pluto and Charon (PAC) is a time and memory efficient collaborative edge AI framework for personal LLMs fine-tuning. PAC implements a personal LLMs fine-tuning technique that is efficient in terms of parameters, time, and memory. Extensive evaluation based on prototype implementation demonstrates that PAC remarkably outperforms state-of-the-art approaches.
  arXiv  Detail & Related papers  (2024-08-20T11:30:12Z)
• Bypass Back-propagation: Optimization-based Structural Pruning for Large Language Models via Policy Gradient [57.9629676017527]
  We propose an optimization-based structural pruning on Large-Language Models. We learn the pruning masks in a probabilistic space directly by optimizing the loss of the pruned model. Our method operates for 2.7 hours with around 35GB memory for the 13B models on a single A100 GPU.
  arXiv  Detail & Related papers  (2024-06-15T09:31:03Z)
• Self-Augmented Preference Optimization: Off-Policy Paradigms for Language Model Alignment [104.18002641195442]
  We introduce Self-Augmented Preference Optimization (SAPO), an effective and scalable training paradigm that does not require existing paired data. Building on the self-play concept, which autonomously generates negative responses, we further incorporate an off-policy learning pipeline to enhance data exploration and exploitation.
  arXiv  Detail & Related papers  (2024-05-31T14:21:04Z)
• REBEL: Reinforcement Learning via Regressing Relative Rewards [59.68420022466047]
  We propose REBEL, a minimalist RL algorithm for the era of generative models. In theory, we prove that fundamental RL algorithms like Natural Policy Gradient can be seen as variants of REBEL. We find that REBEL provides a unified approach to language modeling and image generation with stronger or similar performance as PPO and DPO.
  arXiv  Detail & Related papers  (2024-04-25T17:20:45Z)
• Privacy Amplification for Matrix Mechanisms [18.13715687378337]
  "MMCC" is the first algorithm to analyze privacy amplification via sampling for any generic matrix mechanism. We show it leads to significant improvement in the privacy-utility trade-offs for DP-FTRL algorithms on standard benchmarks.
  arXiv  Detail & Related papers  (2023-10-24T05:16:52Z)
• Semi-Federated Learning: Convergence Analysis and Optimization of A Hybrid Learning Framework [70.83511997272457]
  We propose a semi-federated learning (SemiFL) paradigm to leverage both the base station (BS) and devices for a hybrid implementation of centralized learning (CL) and FL. We propose a two-stage algorithm to solve this intractable problem, in which we provide the closed-form solutions to the beamformers.
  arXiv  Detail & Related papers  (2023-10-04T03:32:39Z)
• (Amplified) Banded Matrix Factorization: A unified approach to private training [15.922315074913255]
  Matrix factorization (MF) mechanisms for differential privacy (DP) have substantially improved the state-of-the-art in privacy-utility-computation tradeoffs for ML applications. We show how MF can subsume prior state-of-the-art algorithms in both federated and centralized training settings.
  arXiv  Detail & Related papers  (2023-06-13T21:53:17Z)
• Energy-efficient Task Adaptation for NLP Edge Inference Leveraging Heterogeneous Memory Architectures [68.91874045918112]
  adapter-ALBERT is an efficient model optimization for maximal data reuse across different tasks. We demonstrate the advantage of mapping the model to a heterogeneous on-chip memory architecture by performing simulations on a validated NLP edge accelerator.
  arXiv  Detail & Related papers  (2023-03-25T14:40:59Z)
• Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning [18.55306294638515]
  We introduce new differentially private (DP) mechanisms for computation-based machine learning (ML) with multiple passes (epochs) over a dataset. We formalize the problem of DP mechanisms for adaptive streams with multiple participations and introduce a non-trivial extension of online matrix factorization DP mechanisms.
  arXiv  Detail & Related papers  (2022-11-12T00:41:11Z)
• Reconfigurable Intelligent Surface Assisted Mobile Edge Computing with Heterogeneous Learning Tasks [53.1636151439562]
  Mobile edge computing (MEC) provides a natural platform for AI applications. We present an infrastructure to perform machine learning tasks at an MEC with the assistance of a reconfigurable intelligent surface (RIS) Specifically, we minimize the learning error of all participating users by jointly optimizing transmit power of mobile users, beamforming vectors of the base station, and the phase-shift matrix of the RIS.
  arXiv  Detail & Related papers  (2020-12-25T07:08:50Z)
• Reduced-Dimensional Reinforcement Learning Control using Singular Perturbation Approximations [9.136645265350284]
  We present a set of model-free, reduced-dimensional reinforcement learning based optimal control designs for linear time-invariant singularly perturbed (SP) systems. We first present a state-feedback and output-feedback based RL control design for a generic SP system with unknown state and input matrices. We extend both designs to clustered multi-agent consensus networks, where the SP property reflects through clustering.
  arXiv  Detail & Related papers  (2020-04-29T22:15:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.