Research map / Federated learning and privacy / Differential privacy

Optimizing Noise Distributions for Differential Privacy

ICML 2025 · Federated learning and privacy › Differential privacy · approach: Private training with public data · 0 citations (OpenAlex)

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 a convex finite-dimensional optimization, solved by preconditioned gradient descent with moments-accountant alpha tuning, to design continuous and discrete noise distributions minimizing RDP under a variance constraint, outperforming Gaussian/Laplace/Staircase/Cactus in moderate composition regimes.

Problem

Finding noise distributions that give the best (epsilon, delta)-DP guarantees for a given cost (variance) constraint and number of compositions, for both continuous and discrete queries, where the direct problem is non-convex and infinite-dimensional.

Approach

Minimize the worst-case Rényi divergence over symmetric piecewise-constant (continuous) or PMF (discrete) distributions with geometric tails, show the objective is convex in the bin probabilities, and solve with preconditioned (diagonally scaled) projected gradient descent while adapting the Rényi order alpha via the moments accountant.

Key results

• At delta=1e-6, 10 compositions, std 8, the optimized noise reaches epsilon 1.62 versus 1.76 for Laplace/Staircase and 1.74 for Gaussian/Cactus (at least 6.89% improvement).
• On three datasets with delta=1e-6 and 10 queries, replacing Gaussian with the optimized noise yields 8% to 12% MSE improvement across the tested epsilon values.
• The framework automatically recovers Cactus (large composition, alpha near 1) and Staircase (single composition, alpha to infinity) distributions in their known optimal regimes.

Measured effects reported in the paper

Surprising findings

• No single mechanism (Gaussian, Laplace, Staircase, Cactus) is best across all settings, so choosing a baseline requires testing all of them.
• Staircase sometimes outperforms the other baselines at delta=1e-6 for certain sigma and composition choices, even though it is provably optimal only in the single-composition pure DP limit.

Limitations

• The optimized noise advantage is largest in the moderate composition regime (roughly 10-40 compositions); gains are smaller elsewhere.
• Uses the simple moments accountant form for optimization, with Connect-the-Dots used only for final accounting.
• Improvement over Laplace, Cactus and Staircase is reported only indirectly; the dataset experiments compare only against Gaussian.

Experimental setup

Datasets: Breast Cancer Wisconsin (Diagnostic) Diabetes UCI Heart Disease (Cleveland)

Benchmarks: Breast Cancer Wisconsin (Diagnostic) Diabetes UCI Heart Disease (Cleveland)

Metrics: epsilon at fixed delta privacy curve comparison MSE improvement over Gaussian (%)

Baselines: Gaussian mechanism Laplace mechanism Staircase mechanism Cactus mechanism discrete Gaussian discrete Laplace

Builds on: Rényi differential privacy moments accountant Connect-the-Dots accountant Staircase mechanism Cactus mechanism

Closest papers by meaning

• Attack-Aware Noise Calibration for Differential Privacy (NeurIPS 2024 · similarity 0.88)
• Rényi Pufferfish Privacy: General Additive Noise Mechanisms and Privacy Amplification by Iteration via Shift Reduction Lemmas (ICML 2024 · similarity 0.88)
• Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.88)
• Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness (ICLR 2025 · similarity 0.87)
• The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD (ICLR 2025 · similarity 0.87)
• Faster Algorithms for User-Level Private Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.87)