Research map / Federated learning and privacy / Differential privacy
Shifted Interpolation for Differential Privacy
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 convergent f-DP (exact in strongly convex case) privacy bounds for noisy gradient descent variants via shifted interpolated processes, recovering the exponential mechanism f-DP characterization.
Problem
Tight privacy accounting for noisy gradient descent and its variants (NoisyGD, cyclic and stochastic batches) in the f-DP framework, where existing f-DP bounds diverge with the number of iterations.
Approach
Constructs shifted interpolated processes that interpolate between two noisy GD trajectories on adjacent datasets, enabling a geometrically aware composition lemma that gives convergent tradeoff-function bounds, disentangling the shifted-divergence argument so it applies to f-DP.
Key results
- For regularized logistic regression on MNIST with NoisyCGD at 50/100/200 epochs, the proposed bounds give epsilon 4.34/5.60/7.58 versus 5.82/7.61/9.88 for RDP and 30.51/49.88/83.83 for GDP composition (delta=1e-5).
- The strongly convex NoisyGD bound is exact (tight) in all parameters, improving RDP by a factor of 2 per the paper's claim.
- The f-DP characterization of the exponential mechanism for strongly convex losses is recovered as a t-to-infinity limit, and extended to projected convex settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use shifted-interpolation privacy accounting instead of GDP Composition | NoisyCGD · Regularized logistic regression on MNIST, 50 epochs | ε: 30.51 -> 4.34 | Helped |
| Use shifted-interpolation privacy accounting instead of RDP | NoisyCGD · Regularized logistic regression on MNIST, 50 epochs | ε: 5.82 -> 4.34 | Helped |
| Use shifted-interpolation privacy accounting instead of GDP Composition | NoisyCGD · Regularized logistic regression on MNIST, 100 epochs | ε: 49.88 -> 5.60 | Helped |
| Use shifted-interpolation privacy accounting instead of RDP | NoisyCGD · Regularized logistic regression on MNIST, 100 epochs | ε: 7.61 -> 5.60 | Helped |
| Use shifted-interpolation privacy accounting instead of GDP Composition | NoisyCGD · Regularized logistic regression on MNIST, 200 epochs | ε: 83.83 -> 7.58 | Helped |
| Use shifted-interpolation privacy accounting instead of RDP | NoisyCGD · Regularized logistic regression on MNIST, 200 epochs | ε: 9.88 -> 7.58 | Helped |
| Increase training from 50 to 200 epochs | NoisyCGD · Regularized logistic regression on MNIST | training accuracy: 89.36 $\pm$ 0.03 -> 90.85 $\pm$ 0.02 | Helped |
| Increase training from 50 to 200 epochs | NoisyCGD · Regularized logistic regression on MNIST | test accuracy: 90.12 $\pm$ 0.04 -> 91.37 $\pm$ 0.08 | Helped |
| Use the strongly convex shifted-interpolation bound instead of composition | NoisyGD · Strongly convex, smooth losses | GDP μ: The paper says the bound is optimal for η ∈ (0, 2/(M+m)] and improves over composition for all t > 1. | Helped |
| Use the constrained convex shifted-interpolation bound instead of composition | NoisyGD · Constrained convex losses | GDP μ | Helped |
| Use shifted interpolation rather than composition-based privacy accounting | NoisyCGD · Strongly convex or constrained convex losses | GDP μ | Helped |
| Use shifted interpolation with subsampling amplification | NoisySGD · Strongly convex or constrained convex losses | f-DP | Helped |
Surprising findings
- Composition-based f-DP bounds diverge as iterations grow, while the shifted interpolation bounds converge, so long training stays bounded in privacy loss.
Limitations
- Convergent bounds for convex (non-strongly convex) unconstrained settings are not obtained; privacy diverges there.
- Stochastic batch bounds are convergent only with finite t-tau constants and computing tradeoff-function compositions is computationally burdensome.
- Requires W-infinity coupling bounds, which may not be tight for stochastic algorithms.
Experimental setup
Datasets: MNIST
Benchmarks: MNIST
Metrics: epsilon at delta=1e-5 (differential privacy) training accuracy test accuracy
Baselines: GDP composition RDP accounting (Renyi DP bounds for NoisyCGD)
Builds on: privacy amplification by iteration shifted divergences f-DP Gaussian DP composition privacy amplification by subsampling
Closest papers by meaning
- Privacy Amplification by Iteration for ADMM with (Strongly) Convex Objective Functions (AAAI 2024 · similarity 0.90)
- Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness (ICLR 2025 · similarity 0.90)
- Differentially Private Stochastic Gradient Descent with Fixed-Size Minibatches: Tighter RDP Guarantees with or without Replacement (NeurIPS 2024 · similarity 0.90)
- Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.89)
- The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD (ICLR 2025 · similarity 0.89)
- Rényi Pufferfish Privacy: General Additive Noise Mechanisms and Privacy Amplification by Iteration via Shift Reduction Lemmas (ICML 2024 · similarity 0.88)
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.