Research map / Federated learning and privacy / Differential privacy
PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PREAMBLE, a two-server secure aggregation scheme that samples k non-zero blocks per client and secret-shares them with a block-sparse DPF, achieving Gaussian-like privacy-utility at far lower communication.
Problem
Secure aggregation of high-dimensional vectors in a two-server (Prio) setting has communication scaling with dimension, limiting private federated learning with large models.
Approach
Group coordinates into blocks, subsample k blocks per client with privacy amplification by sampling (hidden sparsity pattern), and extend tree-based distributed point functions to share k-block-sparse vectors with cuckoo-hashed correction words, costing about kB field elements of communication.
Key results
- For an 8M-dimensional vector with 64-bit field and n=100K clients at (1,1e-6)-DP, communication drops from 64MB to about 1MB while noise std increases by about 10%.
- On MNIST and CIFAR-10 DP-SGD, PREAMBLE communicates about 2e4 parameters versus roughly 6e4 for the Gaussian mechanism with a small accuracy loss.
- Block sizes in the range 2^10 to 2^13 give low error across parameter settings, and block norm clipping to sqrt(B/D) yields O(1/B) expected squared truncation error.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PREAMBLE block-sparse aggregation with sampling instead of Prio | High-dimensional vector aggregation · 8M-dimensional vector, 100K vectors, (1,10^-6)-DP | communication: 64MB -> about 1MB | Helped |
| Use PREAMBLE block-sparse aggregation with sampling instead of the Gaussian mechanism | High-dimensional vector aggregation · 8M-dimensional vector, 100K vectors, (1,10^-6)-DP | noise standard deviation: about 10% | Hurt |
| Use PREAMBLE partitioned subsampling instead of the Gaussian mechanism | Private model training · MNIST and CIFAR-10 | parameters communicated: roughly $6 \cdot 10^4$ -> around $2\cdot 10^4$ | Helped |
| Use PREAMBLE instead of the Gaussian mechanism | Private model training · MNIST and CIFAR-10 | accuracy | Helped |
| Use block-based sampling rather than full-vector communication | Private vector aggregation · Dimensions from 1M to 8M, range of ε values | communication | Helped |
Surprising findings
- Block-wise subsampling with a sparse DPF keeps the sampling noise independent of dimension, so any kB >= cn/sigma^2 suffices.
- Without hiding the sparsity pattern, the sensitivity-based bound is worse by a factor of sqrt(Delta/k), showing hiding is essential.
Limitations
- Cuckoo hashing with two hash functions gives a constant-factor communication overhead and about O(1/k) failure probability.
- Servers are assumed semi-honest while the proof system is sound only against malicious clients.
- Privacy analysis for truncated Poisson and k-out-of-Delta subsampling is only numerical or conjectured.
Experimental setup
Datasets: MNIST CIFAR-10
Benchmarks: MNIST CIFAR-10
Metrics: communication (DPF key size) per-batch noise standard deviation ratio test accuracy standard deviation of aggregate error
Baselines: Gaussian mechanism with Prio (full-vector communication) single-trusted-server sparse sampling naive DPF for sparse vectors
Builds on: Prio distributed point functions POPLAR Gaussian mechanism DP-SGD
Closest papers by meaning
- Privacy amplification by random allocation (NeurIPS 2025 · similarity 0.87)
- Private and Federated Stochastic Convex Optimization: Efficient Strategies for Centralized Systems (ICML 2024 · similarity 0.86)
- Noise-Aware Algorithm for Heterogeneous Differentially Private Federated Learning (ICML 2024 · similarity 0.86)
- Sketched Gaussian Mechanism for Private Federated Learning (NeurIPS 2025 · similarity 0.86)
- Faster Algorithms for User-Level Private Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.86)
- Mitigating the Privacy–Utility Trade-off in Decentralized Federated Learning via f-Differential Privacy (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.