Research map / Learning theory and algorithms / Sample complexity
Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
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.
Shows optimal private vector mean estimation in the shuffle model needs about min(nε²,d) messages per user (near-matching upper and lower bounds), gives a single-message protocol with near-tight MSE, and studies robustness to malicious users.
Problem
Private vector mean/sum estimation of unit-norm user vectors in the shuffle model of differential privacy: how many messages per user are needed for optimal error, and what is the optimal error with a single message per user; also robustness to malicious users.
Approach
A multi-message protocol that applies a Kashin representation to spread vector energy across coordinates and runs a 1-D optimal shuffle-DP mechanism per coordinate, plus a matching combinatorial reconstruction-attack lower bound showing Omega(min(nε²,d)/log n) messages are necessary; for one message, a bucketized randomized-response protocol with a matching lower bound.
Key results
- Multi-message protocol achieves MSE Õ(d/ε²) using Õ(min(nε²,d)) messages per user, matching central-model optimal error up to logarithms.
- Any unbiased or summation shuffle protocol achieving O(d/ε²) error must send Ω(min(nε²,d)/log n) messages per user.
- Single-message protocol achieves MSE O(d n^{d/(d+2)} ε^{-4/(d+2)}), and any single-message shuffle protocol incurs Ω(d n^{d/(d+2)}) MSE, tight for constant ε.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Kashin-based multi-message protocol | Vector aggregation in the multi-message shuffle model · Vector aggregation | mean squared error | Helped |
| Use the Kashin-based multi-message protocol | Vector aggregation in the multi-message shuffle model · Vector aggregation | messages per user | Helped |
| Limit each user to one message | Vector aggregation in the shuffle model · Vector aggregation | mean squared error | Hurt |
| Use bucket-based randomized response with coordinate rounding | Vector aggregation in the single-message shuffle model · Vector aggregation | mean squared error | Helped |
| Require an optimal-rate unbiased or summation protocol | Vector aggregation in the multi-message shuffle model · Vector aggregation | messages per user | Hurt |
| Allow k malicious users in a single-shuffler summation mechanism | Vector summation · Vector summation, one shuffler | additive error mean squared error | Hurt |
| Use a separate shuffler for each coordinate | Multi-shuffler protocol · Vector summation, malicious users | induced mean squared error | Helped |
Surprising findings
- Optimal multi-message error requires many messages per user (up to d), so the natural extension of 1-D protocols is not enough; a single shuffler lets a single malicious user induce error Omega(d/log^2(nd)).
- Under a single shuffler, malicious users can add error far larger than their unit-norm input, whereas separate shufflers per coordinate limit this to O(k).
Limitations
- Multi-message protocol's message count is only optimal up to logarithmic factors, and the lower bound applies only to unbiased or summation protocols.
- Single-message upper and lower bounds match only for constant ε (the ε-dependence differs in general).
Experimental setup
Metrics: mean squared error messages per user
Baselines: GKMPS 1-D multi-message protocol single-message real summation protocol (Cheu et al.) multi-shuffler model
Builds on: Kashin representation GKMPS 1-D optimal shuffle protocol amplification via shuffling PrivUnit
Closest papers by meaning
- A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility (AAAI 2024 · similarity 0.87)
- Privacy amplification by random allocation (NeurIPS 2025 · similarity 0.87)
- Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under Streaming Differential Privacy (ICML 2024 · similarity 0.86)
- Lightweight Protocols for Distributed Private Quantile Estimation (ICML 2025 · similarity 0.86)
- Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.86)
- Universal Exact Compression of Differentially Private Mechanisms (NeurIPS 2024 · similarity 0.85)
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.