Research map / Optimization / Nonconvex and smooth optimization
Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness
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.
Proves convergent Rényi DP bounds for hidden-state Noisy-SGD over a bounded domain under only Hölder-continuous gradients (no convexity or smoothness), and gives a strictly tighter bound than prior work for smooth strongly convex losses.
Problem
Privacy loss (last-iterate RDP) of Noisy-SGD / DP-SGD diverges under standard composition; existing convergent hidden-state bounds require smooth (strongly) convex losses over a bounded domain.
Approach
Extends shifted Rényi divergence analysis (privacy amplification by iteration) with forward W_infinity distance tracking, optimal allocation of shifts via Cauchy-Schwarz, and a Hölder reduction lemma so that the gradient update map need only be Hölder continuous rather than Lipschitz.
Key results
- Proves convergent RDP bound for Noisy-SGD with (L,λ)-Hölder continuous gradients over a bounded domain, without convexity or smoothness.
- Gives a strictly tighter privacy bound than Altschuler & Talwar (2022) for smooth strongly convex losses, non-asymptotically.
- Empirically estimates Hölder constants for a 2-layer MLP showing smaller Hölder constants at smaller orders λ.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow non-convex, non-smooth losses with Hölder-continuous gradients | Hidden-state Noisy-SGD · Bounded-domain full-batch Noisy-SGD | RDP privacy loss | Helped |
| Use the proposed analysis instead of prior analysis | Smooth strongly convex Noisy-SGD · Bounded-domain full-batch Noisy-SGD | RDP privacy loss | Helped |
| Track forward Wasserstein distance instead of using the domain diameter directly | Hidden-state Noisy-SGD privacy analysis · Full-batch Noisy-SGD | RDP privacy loss | Helped |
| Optimize the shift allocation across iterations | Hidden-state Noisy-SGD privacy analysis · Smooth strongly convex Noisy-SGD | RDP privacy loss | Helped |
| Apply optimized shift allocation | Hidden-state Noisy-SGD privacy analysis · Smooth non-convex Noisy-SGD | RDP privacy loss | Helped |
| Generalize the reduction analysis from smooth gradients to Hölder-continuous gradients | Hidden-state Noisy-SGD privacy analysis · Non-smooth Noisy-SGD | RDP privacy loss | Helped |
Surprising findings
- Non-convex smooth losses still admit a convergent bound better than output perturbation, but only after a longer burn-in period and with a larger final privacy loss.
Limitations
- Gradient clipping makes the update map non-smooth, so the analysis assumes Lipschitz losses to control continuity.
- Neural networks treated as whole-vector losses yield large Hölder/smoothness constants, limiting practical tightness.
- No uniform improvement over standard composition before a burn-in period.
Experimental setup
Metrics: Rényi DP epsilon bound
Baselines: standard composition output perturbation Altschuler & Talwar 2022 Ye & Shokri 2022
Builds on: privacy amplification by iteration shifted Rényi divergence analysis DP-SGD Altschuler & Talwar 2022 Ye & Shokri 2022
Closest papers by meaning
- Shifted Interpolation for Differential Privacy (ICML 2024 · similarity 0.90)
- The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD (ICLR 2025 · similarity 0.89)
- Faster Algorithms for User-Level Private Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.88)
- Optimizing Noise Distributions for Differential Privacy (ICML 2025 · similarity 0.87)
- The Privacy Power of Correlated Noise in Decentralized Learning (ICML 2024 · similarity 0.87)
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.87)
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.