Research map / Federated learning and privacy / Differential privacy
Private Lossless Multiple Release
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.
Introduces lossless multiple release, where differentially private releases with arbitrary privacy parameters can be produced in any order with total privacy loss set by the least private release, and gives constructions for Gaussian, Laplace, Poisson, factorization, and sparse histogram mechanisms.
Problem
Gradual release (Koufogiannis et al.) only allows increasing privacy parameters in order; releasing multiple DP outputs at different privacy levels usually costs composition privacy. The paper asks whether multiple releases at different privacy budgets, in arbitrary order, can be made with no accura
Approach
Correlate releases by treating them as a Markov chain of additive noise: each new release is sampled conditioned on its two adjacent stored releases, using convolution-preorder bridging distributions. For Gaussian noise this reduces to inverse-variance weighting plus fresh noise, so each new release only needs the two neighboring stored releases.
Key results
- Gaussian lossless multiple release gives each release exactly the variance of a single release at its own rho (variance 1/(2rho)) while the joint privacy loss is max of the budgets, verified empirically over 10^6 repetitions with no utility loss versus independent releases.
- Lossless multiple release holds for any independent additive noise mechanism whose noise family satisfies a convolution preorder, extended by invertible post-processing; weakly lossless version covers non-invertible post-processing such as thresholding.
- Efficient weakly lossless gradual release for sparse Gaussian histograms samples (k+c)m Gaussians, where k is support size, c is number of zero counts that ever exceed threshold, and m is number of rounds, independent of dimension d in the sense of not sampling noise for all zero entries.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use lossless multiple release instead of independent Gaussian releases | Gaussian mechanism · Gaussian noise variance experiment | variance | Helped |
| Increase the number of independent Gaussian releases | Independent Gaussian mechanism · Gaussian noise variance experiment | variance | Hurt |
Limitations
- Exponential mechanism and report noisy max lack known lossless multiple release constructions
- Discrete Gaussian and finite-precision implementations are not covered; Poisson suggested as a workaround
- Storing past releases is required (state grows with number of releases)
Experimental setup
Metrics: variance of noise
Baselines: independent releases with composition epsilon-doubling
Builds on: Koufogiannis et al. gradual release Whitehouse et al. Gaussian gradual release factorization mechanism Gaussian sparse histograms (stability histograms)
Closest papers by meaning
- Private Hyperparameter Tuning with Ex-Post Guarantee (NeurIPS 2025 · similarity 0.88)
- Purifying Approximate Differential Privacy with Randomized Post-processing (NeurIPS 2025 · similarity 0.85)
- Universal Exact Compression of Differentially Private Mechanisms (NeurIPS 2024 · similarity 0.85)
- Approximate Differential Privacy of the $\ell_2$ Mechanism (ICML 2025 · similarity 0.84)
- Privacy Amplification Persists under Unlimited Synthetic Data Release (NeurIPS 2026 · similarity 0.84)
- Optimizing Noise Distributions for Differential Privacy (ICML 2025 · similarity 0.84)
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.