Research map / Federated learning and privacy / Differential privacy
Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation
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.
Derives sampling-free, deterministic privacy accountants for matrix mechanisms under balls-in-bins (random allocation) subsampling, combining a Rényi-divergence dynamic program with a conditional composition method, avoiding the Monte Carlo high-probability guarantees of prior work.
Problem
Privacy accounting for subsampled matrix factorization mechanisms under random allocation (balls-in-bins) batching; existing accountant is Monte Carlo based, giving only high-probability guarantees or requiring abstention, with sample cost scaling as 1/delta.
Approach
Exact Rényi divergence for the dominating pair of the balls-in-bins mixture is computed via a dynamic program exploiting cyclic banded structure of the Gram matrix (with truncation bound for non-banded matrices), and a conditional composition argument yields per-step factorizing dominating pairs that give stronger guarantees for small epsilon.
Key results
- Rényi accountant closely matches the Monte Carlo accountant in the low-privacy regime (epsilon roughly >= 2-4), while the conditional composition accountant yields tighter bounds for epsilon <= 1.
- For DP-SGD, the Rényi dynamic program reduces runtime from O(2^alpha) to O(b alpha^2) (remove direction), confirmed by wall-clock measurements.
- Sampling-free guarantees are strong enough to retain the utility benefit of correlated noise (BSR, BISR) over DP-SGD on CIFAR-10 for epsilon >= 4.
Surprising findings
- For multi-epoch DP-SGD, the conditional composition bound can degrade and provides little benefit over Rényi accounting.
Limitations
- Rényi accountant complexity is exponential in bandwidth p, trading runtime for tightness.
- Conditional composition uses a coarse good/bad partition, which can be overly pessimistic.
- The analytical tail bounds rely on a conservative linear relaxation.
Experimental setup
Datasets: CIFAR-10
Benchmarks: CIFAR-10
Metrics: noise multiplier required for (epsilon, 1e-5)-DP wall-clock runtime test accuracy
Baselines: Monte Carlo accountant (Choquette-Choo et al. 2025) Feldman & Shenfeld (2025) random allocation accountant PLD random allocation accountant (Feldman & Shenfeld 2026) DP-SGD
Builds on: Monte Carlo accountant for matrix mechanisms under balls-in-bins (Choquette-Choo DP-SGD random allocation accountant (Feldman & Shenfeld) BandMF BSR BLT PLD accounting
Closest papers by meaning
- Privacy amplification by random allocation (NeurIPS 2025 · similarity 0.92)
- Near-Exact Privacy Amplification for Matrix Mechanisms (ICLR 2025 · similarity 0.92)
- Privacy Amplification for Matrix Mechanisms (ICLR 2024 · similarity 0.92)
- Unified Mechanism-Specific Amplification by Subsampling and Group Privacy Amplification (NeurIPS 2024 · similarity 0.90)
- A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility (AAAI 2024 · similarity 0.89)
- Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.89)
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.