PaperlayerView exact revision on arXiv

Source-linked AI summary

Revisiting the Provable-Auditable Privacy Gap of DP-SGD

Saloni Modi, Srivi Balaji, Yusong Zhu, Gautam Kamath, Kevin Tian

arXiv:2608.28934v1cs.LG

TL;DR

The gap between theoretical and true privacy remains uncertain, while practitioners need ways to assess privacy under relevant threat models. The paper introduces a lightweight filtering framework and reports near-zero empirical privacy lower bounds with negligible utility loss in its evaluation.

  • Problem

    The gap between theoretical and true privacy remains uncertain, and practitioners need a way to assess true privacy under relevant threat models.

    Source: §1.1 · p. 4

  • Method

    The paper proposes a lightweight filtering-based wrapper to improve empirical privacy lower bounds while retaining the same provable upper bound for a wide range of DP-SGD variants.

    Source: §1.2 · p. 5

  • Results

    The filtered variant achieved εlb ≈0 under a comprehensive audit suite, with negligible utility drop from its unfiltered counterpart.

    Source: §1.2 · p. 5

  • Takeaways & Limitations

    Using εlb as an evaluation metric can motivate audit researchers and algorithm designers to expand tests beyond DP-SGD and develop stronger audits.

    Source: §1.3 · p. 7

    The empirical εlb is not a formal security guarantee against all privacy attacks; it measures vulnerability against a selected suite of representative membership inference attacks.

    Source: §1.3 · p. 6

Abstract

from arXiv · show

Differential privacy (DP) has traditionally been used to provide theoretical upper bounds on an algorithm's stability to changing its training data. In modern private machine learning applications, achieving strong tradeoffs between utility and theoretical privacy is challenging, and thus one may optimistically hope that existing theoretical privacy analyses are loose. Recent work on privacy auditing has adopted a dual viewpoint, instead lower bounding the true privacy of an algorithm by constructing empirical distinguishing events. The auditing literature has thus far yielded a pessimistic outlook on the looseness of theoretical privacy bounds for DP-SGD, the de facto private training method in modern ML, as nearly-matching empirical lower bounds have been achieved under various threat models [NHSBTJCT23, AC24, CBP25]. In this work, we propose the empirical privacy lower bound of an algorithm as a concrete metric to optimize for, complementary to the theoretical upper bound. We give a lightweight defense framework that generically augments optimization methods in the ML pipeline to have significantly-improved empirical privacy on standard benchmarks. Moreover, we show that our framework comes at no theoretical privacy cost when augmenting DP-SGD, unlike previously-proposed defenses against membership inference attacks. We evaluate our defense against a broad range of audit constructions, models, and datasets to demonstrate its flexibility.

1 Introduction

The introduction presents auditable εlb as a target complementary to theoretical εub, and proposes a filtering framework that improves empirical privacy while preserving DP-SGD’s provable privacy bound.

1 Introduction

  • Theoretical accounting upper-bounds true ε⋆, but depends on the output and threat model: audits over intermediate checkpoints may be infeasible when only the final model or limited query access is exposed.The paper notes that standard composition-based analyses cover audits depending on all intermediate models, even when those models are not published.Source: §1 · p. 4

1.1 Motivation

  • The utility–privacy tension motivates asking whether ε⋆ is below εub, but prior DP-SGD audits often found nearly tight lower bounds across threat models.The cited work includes gradient-space canaries and hidden-state audits, including input-space canaries.Source: §1.1 · pp. 4–5

1.2 Our contributions

  • They propose auditable εlb as a formal algorithm-design metric complementary to εub; optimizing over audits yields a certifiable lower bound on ε⋆, not necessarily its exact value.The strongest possible dataset, canary, and audit would make εlb and ε⋆ equal.Source: §1.2 · p. 5, §1.1 · p. 5
  • The sample-signature filtering wrapper yields audited εlb ≈0 with negligible utility drop and matches Poisson-subsampled DP-SGD’s provable εub.The proof relies on signature-based filtering preserving neighboring datasets and adaptive-composition guarantees under interleaved filtering.Source: §1.2 · pp. 5–6

1.3 Discussion

  • εlb measures vulnerability against a threat-model-aware representative audit suite, not a formal security guarantee; as audits expand, it remains a moving target.The authors say filtered models’ weak auditability may reflect either smaller ε⋆ than theory predicts or a need for stronger tests.Source: §1.3 · pp. 6–7

1.4 Prior work

  • Prior MIA defenses target εlb–utility without provable accounting; this framework adds a proof but does not yet cover non-permutation-invariant DP-FTRL.Unlike, it uses rank-based filtering and targets empirical privacy rather than utility–privacy tradeoffs.Source: §1.4 · pp. 7–8

2 Overview

The overview introduces sample-signature filtering and the audit framework, and reports lower empirical privacy lower bounds for filtered DP-SGD under input-space, hidden-state audits.

2.1 Preliminaries

  • The paper uses add/remove adjacency and Poisson-subsampled DP-SGD, which clips per-example gradients and adds Gaussian noise to their average at each step.It uses Poisson-subsampled DP-SGD in experiments rather than randomly shuffled fixed-size minibatches, for which applying the standard privacy bound is only heuristic; the analysis also discusses extensions to such alternatives.Source: §2.1 · pp. 8–10

2.2 Threat models

  • Threat models vary by access to training history (full or hidden state) and attack target (input or gradient space); the paper focuses on hidden-state, input-space attacks.The paper also examines gradient-space attacks with model-history access and the reproducibility of those attacks in input-space settings.Source: §2.2 · p. 10

2.3 Framework

  • The defense periodically filters samples using signatures based on each sample and privatized model parameters, with per-class filtering to account for class-specific score distributions.A signature does not depend on other samples except through the learned private model; per-class filtering avoids flagging classes with naturally higher gradient norms as outliers.Source: §2.3 · pp. 10, 12

2.4 Measuring empirical privacy

  • Privacy audits use dataset–canary–test triples and holdout model copies to estimate an empirical upper bound on the f-DP curve, yielding a lower bound on εlb.With limited holdout copies, Clopper–Pearson correction can loosen audits; the paper reports εlb using multiple-hypothesis-testing and GDP-extrapolation heuristics, which can inflate estimates and may lack formal guarantees.Source: §2.4 · p. 13
  • Filtered DP-SGD consistently achieves lower εlb than the unfiltered implementation against input-space, hidden-state audits across all reporting methods, formal or heuristic.The reported εlb uses both multiple-hypothesis-testing and GDP-extrapolation heuristics; Appendix J also reports estimates with and without them and under different sample splits.Source: §2.4 · p. 13

3 Privacy of Filtering via Sample Signatures

The section shows how filtering by sample signatures can preserve privacy bounds for permutation-invariant algorithms analyzed by privacy composition. It also describes applicability to shuffled-minibatch DP-SGD and future permutation-invariant variants.

3.1 Analysis

  • Sample-signature filtering preserves the same privacy bound for permutation-invariant, RDP-composed algorithms, and Algorithm 2 matches Algorithm 1’s Theorem 1 bound.The argument combines interleaved RDP composition with the fact that dropping the k highest-scored samples does not increase dataset distance when removed indices are ignored; permutation-invariance makes that index-insensitivity valid.Source: §3.1 · pp. 14–15

3.2 Variants of DP-SGD

  • Randomly shuffled-minibatch DP-SGD supports filtering after any number of gradient steps under standard RDP accounting or the in-expectation equivalent variant.The random permutation at each epoch makes the privacy framework applicable to this variant.Source: §3.2 · p. 16
  • The framework is expected to extend to future permutation-invariant DP-SGD variants whose adaptive composition proofs condition on earlier mechanism outcomes.The passage notes that such proofs are compatible with interleaved composition, which does not require the datasets for the second mechanism to be identical.Source: §3.2 · p. 16
  • A filtered variant of would inherit its RDP and PLD privacy analyses.The passage attributes this applicability to the algorithm’s permutation-invariance and the compatibility of those accounting frameworks’ adaptive-composition proofs with Lemma 4.Source: §3.2 · p. 16

4 Privacy-Preserving Empirically Private Learning · A Empirical Privacy Reporting Details

The evaluations test the filtering defense across input-space and gradient-space audits, finding lower empirical privacy loss in several settings while identifying stronger gradient-space attacks that can defeat it.

4.1 Experimental and audit setup

  • Experiments covered MNIST, CIFAR-10, and Purchase100, using 400 shadow models per audit and including augmentation multiplicity in some evaluations.The setups use CNNs for MNIST, CNN and WideResNet models for CIFAR-10, and a three-layer MLP for Purchase100; the same methodology is used to compare optimizers with and without filtering.Source: §4.1 · pp. 17–18

4.2 Input space attacks

  • εlb fell to ≈0 for MNIST-CNN and CIFAR-10-WRN-16 in almost every εub ∈{2, 4, 6, 8, 10} setting, with minimal utility impact.Reversals occurred for MNIST and CIFAR-10 on WRN-16 at εub = 2 and Purchase at εub = 6; accuracy dropped by 1.5% or less on 24 other tasks, while Purchase at εub = 10 had a larger drop.Source: §4.2 · p. 19, Figure 1 · p. 20

4.3 Label-only attack

  • TPR was 28.5% at 0.1% FPR against HAMP versus 0.95% against the filtering defense under the label-only attack.HAMP masks confidence but leaves predicted labels intact; filtering instead removes vulnerable canary samples before they are memorized.Source: §4.3 · pp. 21–22

4.2 Input space attacks

  • The defense reduced empirical privacy loss across adversarial FGSM, mislabeled in-distribution, and ClipBKD input-space canaries.The evaluation covers CIFAR-10 and MNIST; Table 2 reports empirical privacy loss under non-blank input-space attacks for εub = 10.Source: §4.2 · pp. 19–20, Table 2 · p. 22

4.4 Defense-aware input space attack

  • The learned defense-aware canary had lower εlb than the initial canary both before and after defense: 1.962 vs 2.453, then 0 vs 0.65.Optimization increased the average epoch at which the canary was dropped but did not push it beyond the 100-epoch training period.Source: Table 3 · p. 23, §4.4 · p. 23

4.5 Gradient space attacks

  • Using 500 one-hot gradient-space canaries at the minimum sixth-largest gradient norm observed across epochs, filtering five samples per class each epoch kept them just below threshold; group-privacy εlb = 27.26 with and without defense.Source: Gradient space attacks · p. 24
  • A gradient-canceling attack produced non-zero group privacy loss by filtering Group A while exposing Group B, but corresponding input-space constructions failed to replicate the attack.Input-space attempts consistently filtered only 1% of canaries because their per-sample gradient magnitudes could not be reliably controlled across epochs.Source: Table 4 · p. 24, Gradient space attacks · p. 24

A.1 Heuristic conventions and their (potential) pitfalls

This section distinguishes formal privacy-audit guarantees from two common heuristics: multiple-hypothesis testing and GDP extrapolation. It identifies when each heuristic can fail and gives counterexamples involving Poisson subsampling and hidden-state outputs.

Multiple hypothesis testing

  • A formal privacy lower bound selects a test, evaluates it on fresh holdout models, applies a Clopper–Pearson correction with failure probability γ, then converts the corrected tradeoff point into ε_lb.The authors also select hyperparameters on holdout models that are discarded before choosing audits and reporting estimates.Source: §A.1 · pp. 32–33
  • Reusing the same models to select and evaluate among tests does not guarantee the selected pair lies above the true f-DP curve with probability 1−γ; Bonferroni correction or holdouts restore formal validity.The original work prescribes the holdout strategy.Source: §A.1 · p. 32
  • Bonferroni correction yields substantially smaller, often negligible, ε_lb estimates, while holdouts retain nontrivial formal DP-SGD bounds but often worsen tightness by 3–10×.The reported trends between the authors’ algorithms and DP-SGD remain consistent with or without accounting for multiple discovery.Source: §A.1 · p. 33
  • Convexifying the tested points with their lower convex envelope does not change the computed ε_lb.Although the modification could use additional points on the f-DP curve, Lemma 6 establishes that it leaves the estimate unchanged.Source: §A.1 · p. 33

GDP extrapolation

  • GDP extrapolation can improve audit efficiency from a single tradeoff point when the true privacy curve is GDP, but is heuristic when that premise does not hold.GDP curves are convenient for DP-SGD because the Gaussian mechanism and composition of GDP curves remain within the GDP family; prior audits use this approach.Source: §A.1 · p. 34
  • GDP curves are not closed under Poisson subsampling or marginalizing intermediate outputs, and counterexamples show these operations can produce tradeoff functions that are not μ-GDP.The counterexamples cover the subsampled Gaussian mechanism and adaptive Gaussian mechanisms that output only the final result.Source: §A.1 · pp. 34–35
  • The f-DP central limit theorem justification for GDP auditing relies on access to intermediate outputs, making it problematic under hidden-state threats; the authors therefore report GDP-based and Clopper–Pearson estimates.Prior work gives the central limit theorem, while is cited as an example of a hidden-state threat model.Source: §A.1 · p. 34

A.2 Numerical precision

Clopper–Pearson correction can weaken or erase nonzero empirical privacy signals in finite samples. The auditable range grows only logarithmically with sample size, while extreme low-count cases can retain a non-vanishing collapse gap.

A.2 Numerical precision

  • The analysis fixes γ = 0.05, applies one-sided Clopper–Pearson upper bounds to α and β without the multiple-test union bound, and enumerates count pairs at k = 200, 500, 1000, 5000, and 10000.It compares raw and corrected lower bounds for count pairs with εraw > 0.Source: §A.2 · p. 35
  • At k=200 and k=10000, the largest possible auditable εlb is around 4 and 9, respectively; as k increases, fewer observations collapse to zero and the average εraw–εcp gap decreases, but the worst collapsed εraw remains around 2.4.These numerical observations are for finite empirical lower bounds after filtering out εraw = 0 and εraw = +∞ pairs.Source: §A.2 · pp. 35–36
  • The finite auditable εlb range grows only logarithmically with sample count, so accurately auditing large ε values requires very large k.The maximum raw lower bound over finite count pairs is attained at xα = 1 and xβ = 0.Source: §A.2 · p. 36
  • For γ = 0.05, extreme low-count configurations near the binomial boundary cause non-vanishing worst-case collapse; when kδ is small, the largest integer c satisfying the condition is about 11.For γ = 0.05, the right-hand side is approximately 5.57.Source: §A.2 · p. 36

B Disparate Impact · C Alternative Input Space Audits · C.1 Single run audit

The section examines whether the filtering defense reduces utility disproportionately for minority groups and whether it improves empirical privacy in a single-run audit. On ColoredMNIST, minority-group canaries are more prone to memorization, while the defense filters about 75% of canaries in the single-run audit and substantially reduces εlb.

B Disparate Impact

  • ColoredMNIST balances majority and minority subgroups across even- and odd-digit classes using red and blue colors, making it a benchmark for fairness and spurious correlations.Source: B Disparate Impact · p. 37
  • The ColoredMNIST evaluation varies p across 99.5%, 95%, 90%, 85%, 80%, and 75%, measuring filtered samples and resulting groupwise utility.Source: B Disparate Impact · p. 37
  • The authors describe minority-group removal bias as definitional to combating sample memorization for low auditable εlb, consistent with privacy-fairness tradeoff work.Source: B Disparate Impact · p. 37
  • At p = 75%, εlb is 1.145 with a minority-group canary and 0.043 with a majority-group canary, indicating greater minority-group memorization.Source: B Disparate Impact · pp. 37–38
  • Table 5 indicates that the defense removes more minority-group samples, reducing minority-group utility disproportionately; this targeting becomes more benign as p becomes milder.Source: B Disparate Impact · p. 37, Table 5 · p. 38

C.1 Single run audit

  • The defense filters approximately 75% of canaries in the single-run audit, substantially reducing εlb.The evaluation used 500 randomly mislabeled canaries in CIFAR-10.Source: §C.1 · p. 38
  • The alternative audit uses one model-training run rather than 2T shadow models, scoring N canaries and using k+ inclusion and k− exclusion guesses to compute εlb via f-DP.Source: §C.1 · p. 38

C.2 Group privacy audit

The defense substantially reduces empirical privacy loss in a group privacy audit using 500 mislabeled CIFAR-10 canaries. The audit extends LiRA with a maximum-loss score across the canary group.

C.2 Group privacy audit

  • The group privacy audit extends LiRA by scoring each model with the maximum loss across all canaries.It distinguishes models trained with the canary group from models trained without it.Source: §C.2 · p. 38
  • The evaluation uses k = 500 mislabeled canaries on CIFAR-10, and k-group privacy εlb does not formally imply a 1-group εlb that is k× smaller.The passage describes that scaling as reasonable to expect.Source: §C.2 · p. 38
  • The defense substantially reduces εlb under group privacy auditing (Table 6).The evaluation uses k-group privacy εlb.Source: Table 6 · p. 38, §C.2 · p. 38

D Sample Signatures · E Poisson vs. Shuffled Subsampling · F Interpolating Canaries

The defense remained effective across scoring functions, sampling schemes, and interpolated canary strengths, while filtering canaries too late was ineffective.

D Sample Signatures

  • The scoring functions could detect backdoor canaries that spectral methods may miss, but filtering too late was ineffective because canaries had already been memorized.The authors suggest privatized gradient ascent as a possible approach to late-stage canary detection.Source: D Sample Signatures · p. 39
  • The tested gradient-based scores included gradient cosine similarity, L2 and L∞ gradient norms, and unclipped gradient kurtosis.The norms were computed using clipped and unclipped gradients; kurtosis emphasizes heavy-tailed or outlier-like gradients.Source: D Sample Signatures · p. 39
  • Other tested scores were directional uniqueness, prediction entropy, prediction margin, and random projection variability.These measure atypical gradient direction, prediction uncertainty, the inverted true-class margin, and variability in random gradient projections, respectively.Source: D Sample Signatures · p. 39

E Poisson vs. Shuffled Subsampling

  • On MNIST, the estimated εlb gap between defense and no defense on a blank canary persisted under both Poisson sampling and shuffled subsampling.The comparison is shown in Figure 3.Source: E Poisson vs. Shuffled Subsampling · p. 39

D Sample Signatures

  • With other defense parameters fixed, the defense consistently detected and removed the canary across scoring functions, with low empirical privacy loss and similarly high utility metrics.The ablation was conducted on CIFAR-10 using a CNN.Source: D Sample Signatures · p. 39, Table 7 · p. 40

F Interpolating Canaries

  • Varying α produced no clear change in privacy loss, and the defense remained effective across blank-to-mislabeled canaries on MNIST and CIFAR-10.The canaries ranged from a pure blank image at α = 0 to a fully mislabeled image at α = 1.Source: Table 8 · p. 40, F Interpolating Canaries · p. 40

G The Privacy Onion Effect: Do We Expose Anyone Else?

The section tests whether the filtering-based defense creates a privacy-onion effect by auditing non-canary MNIST samples. The strongest non-canary audit is much weaker than fixed-canary auditing, and its holdout-corrected auditable εlb drops to 0.

G The Privacy Onion Effect: Do We Expose Anyone Else?

  • Prior work found that removing the most privacy-vulnerable samples can increase retained samples’ vulnerability, raising concern that empirical privacy may give false reassurance.That work argues practitioners should rely on algorithms with formal privacy guarantees rather than optimize empirical privacy; this section checks whether the effect occurs for the paper’s filtering-based defense.Source: G The Privacy Onion Effect: Do We… · p. 40
  • The audit used 1,000 DP-SGD shadow models at ε = 10, split evenly between training with and without a blank canary, and compared each non-canary sample’s post-defense εlb with the maximum pre-defense εlb.Per-sample losses were recorded for every MNIST training sample under each final model.Source: G The Privacy Onion Effect: Do We… · p. 40
  • The strongest adaptive non-canary audit yields a much weaker εlb than fixed-canary auditing; with holdout correction, its auditable εlb drops to 0.The comparison is reported with and without the formal holdout method; Figures 4 and 5 show the audits using the multiple-hypothesis heuristic and a holdout set, respectively.Source: G The Privacy Onion Effect: Do We… · p. 41

H Increasing the Trial Count · I Additional Hyperparameter Tuning

On MNIST with a blank canary, increasing the experiment to 1000 shadow models left the empirical privacy-bound gap between defense and non-defense settings consistent with the 400-model experiments.

H Increasing the Trial Count

  • The 1000-model MNIST experiment used a blank canary and compared εlb and model utility across defense and non-defense settings.The primary experiments used 400 shadow models, 200 per condition; fewer trials yield looser Clopper-Pearson confidence intervals for empirical privacy bounds.Source: H Increasing the Trial Count · p. 41
  • The εlb gap between defense and non-defense settings remained consistent when MNIST experiments increased from 400 to 1000 shadow models.The scaled-up experiment used 500 shadow models per condition; Table 9 reports empirical privacy loss for MNIST (CNN) with 1000 shadow models.Source: Table 9 · p. 41, H Increasing the Trial Count · p. 41

I.1 Global Filtering Ablation · I.2 Varying Local Filtering Defense Bandwidth Ablation

Global filtering achieved similar empirical privacy and test accuracy to per-class filtering across tested bandwidths, while local filtering reduced empirical privacy loss across all tested bandwidths. The results leave filtering strategy and bandwidth as choices practitioners can tune to dataset characteristics and computational or utility constraints.

I.1 Global Filtering Ablation

  • The global-filtering experiment compared top-k selection across the dataset with top-k selection within each class, testing k ∈ {10, 25, 50} samples per epoch.Its default per-class setting, k = 5 across 10 classes, filtered 50 samples per epoch in total.Source: §I.1 · p. 41
  • The experiments favored local filtering in light of prior work, which found backdoor data poisons had a stronger signature relative to samples in the same class.The comparison used a blank input space canary on MNIST.Source: §I.1 · p. 41
  • Global filtering achieved similar empirical privacy and test accuracy to per-class filtering across all tested bandwidth configurations.The comparison was conducted on MNIST using a blank input space canary.Source: §I.1 · p. 41, Table 10 · p. 42
  • Practitioners can choose global or local filtering based on implementation convenience or dataset characteristics rather than privacy-utility tradeoffs alone.Global filtering may limit total discarded samples, while local filtering may be preferred when class imbalance is a concern.Source: §I.1 · p. 41

I.2 Varying Local Filtering Defense Bandwidth Ablation

  • Local filtering reduced empirical privacy loss across all tested bandwidths, although the degree of reduction varied with k.The study tested k ∈ {1, 2, 3, 4, 5} on CIFAR-10 using a blank canary and gradient-norm based local filtering.Source: §I.2 · p. 42, Table 11 · p. 42
  • Practitioners should tune local-filtering bandwidth alongside computational and utility constraints because k affected empirical privacy.The experiments suggest future work could explore per-epoch adaptive schedules that switch between global and local filtering based on training dynamics.Source: §I.1 · p. 41, §I.2 · p. 42

I.3 Varying Filter Frequency Ablation

On CIFAR-10 with a CNN and blank-input canary, more frequent filtering achieved the lowest empirical privacy lower bound, while less frequent filtering increased it; utility remained stable.

I.3 Varying Filter Frequency Ablation

  • εlb was 0.43 with the most frequent filtering and peaked at 1.39 when filtering every 10 epochs.The defense was tested every k epochs for k ∈ {1, 5, 10, 20}.Source: §I.3 · p. 42
  • Filtering frequency had a meaningful effect on empirical privacy outcomes, while utility metrics remained stable across configurations.The experiment used CIFAR-10/CNN with a blank input space canary.Source: §I.3 · p. 42
  • The results suggest practitioners should prefer more frequent filtering when empirical privacy is a priority.Frequency may matter more for complex canaries or auditing threat models where trainers aim to limit discarded samples; adaptive per-epoch scheduling is a direction for future work.Source: §I.3 · p. 42

J Full Empirical Privacy Results Across Audit Methods

The section uses GDP no-holdout auditing as its primary empirical privacy metric and reports additional results across auditing configurations, datasets, models, and attack settings.

J Full Empirical Privacy Results Across Audit Methods

Related papers

Loading 2608.28934v1…