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 paper asks whether theoretical privacy bounds accurately reflect privacy under realistic threat models, given the difficulty of utility–privacy tradeoffs and nearly tight DP-SGD audits. It proposes optimizing empirical privacy lower bounds with a lightweight filtering framework, which improves audit-based privacy while preserving DP-SGD’s provable bound. The framework achieves εlb ≈0 with negligible utility loss in the reported evaluation, but this metric remains audit-suite dependent and some commonly used DP-SGD variants fall outside the formal theorem.

  • Problem

    The paper addresses how practitioners should reason about true privacy ε⋆ under specific threat models when DP-SGD’s theoretical bounds may be loose but existing audits often approach them.

  • Method

    The paper treats the auditable lower bound εlb as an optimization metric and adds a sample-signature-based filtering wrapper whose privacy proof preserves DP-SGD’s provable εub.

  • Results

    Across a comprehensive audit suite, the filtered variant achieves εlb ≈0 with negligible utility loss while retaining the same provable εub as the corresponding DP-SGD method.

  • Takeaways & Limitations

    Empirical privacy can serve as a complementary, threat-model-aware design target, encouraging defenses and audits to evolve together beyond DP-SGD’s theoretical accounting.

  • Takeaways & Limitations

    εlb is not a formal guarantee against all attacks, depends on the current audit suite, and the main theorem does not formally apply to randomly shuffled minibatch training.

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 paper reframes empirical privacy lower bounds as an algorithm-design metric alongside theoretical DP upper bounds, then introduces a filtering framework that improves audit resistance without reducing provable privacy for DP-SGD. Its evaluations show strong empirical privacy under broad audits, while identifying threat-model and metric limitations.

  • Motivation: Current DP-SGD accounting can require εub ≈1 for 60% CIFAR-10 accuracy and εub ≈8 for accuracy above 80%.The paper contrasts these private-training results with a non-private state of the art above 99%.
  • Motivation: Empirical privacy lower bounds εlb complement theoretical upper bounds εub as a formal target for algorithm design.The paper motivates this metric because existing DP-SGD audits can approach theoretical bounds across threat models.
  • Contributions: The framework is a lightweight filtering wrapper that significantly improves εlb while retaining the same provable εub across many DP-SGD variants.Its proof uses sample signatures to preserve neighboring datasets and supports adaptive composition with interleaved filtering.
  • Results: Auditing the filtered variant with a comprehensive test suite yields εlb ≈0 with negligible utility loss relative to the unfiltered counterpart.The evaluation covers audits, models, and datasets, but current input-space audits may miss vulnerabilities revealed by stronger tests.
  • Technical rationale: The framework’s provable privacy advantage comes from sample-signature filters rather than aggregate statistics that can disrupt neighboring relationships under adaptive filtering.The paper contrasts this design with robust-statistics-inspired defenses that can fail when fewer than 1% of points are poisoned.
  • Limitations: εlb is not a formal guarantee against all privacy attacks and instead measures vulnerability to a current, threat-model-aware audit suite.Because the suite can expand, εlb is inherently a moving target; the paper also examines possible vulnerabilities under gradient-space attacks.

2 Overview

This section introduces DP, DP-SGD, privacy accounting, threat models, and the paper’s filtered DP-SGD defense based on sample signatures. It also highlights formal-accounting limitations and audit limitations, including heuristic bounds and looseness from limited holdout samples.

  • Differential privacy: DP defines a rigorous privacy notion through bounds over neighboring datasets and output events.
  • DP-SGD: DP-SGD clips per-sample gradients, averages them within a minibatch, and adds Gaussian noise before updating the model.
  • Privacy accounting: RDP-based accounting provides theoretical privacy bounds for DP-SGD, while shuffled-minibatch training commonly relies on a heuristic bound because Theorem 1 does not formally apply.
  • Filtered DP-SGD: The defense periodically filters training samples using sample signatures computed from individual samples and privatized model parameters.
  • Filtered DP-SGD: Sample signatures include gradient norms and prediction margins, with filtering selectable globally or by class.
  • Auditing limitations: Auditing can be loosened by limited holdout copies, while prior heuristic corrections may inflate estimated empirical privacy lower bounds and sacrifice formal correctness.

3 Privacy of Filtering via Sample Signatures

The framework combines interleaved RDP composition with a neighboring-preservation result for coupled sample-signature filtering. Under permutation invariance, filtering therefore preserves the original privacy bound and extends across several DP-SGD variants and accounting frameworks.

  • Generalized composition: Interleaved Rényi composition preserves an additive RDP bound when filtering maps neighboring datasets to neighboring datasets after the first mechanism’s output.
  • Generality: The composition strategy supports adaptive filters depending on the entire history of prior operations and can extend to basic, advanced, and PLD composition.
  • Neighboring preservation: Dropping the k largest scores from each of two coupled neighboring datasets cannot increase their Hamming distance when removed samples are treated as equivalent.
  • Neighboring preservation: Permutation invariance is required because filtering may otherwise change distances through the indices of removed samples.
  • Privacy guarantee: Combining the lemmas shows that permutation-invariant RDP-composed algorithms retain the same privacy bound under arbitrary sample-signature filtering.
  • Variants of DP-SGD: The framework applies to randomly shuffled minibatches and is expected to extend to future permutation-invariant DP-SGD variants whose accounting uses compatible adaptive-composition proofs.

4 Privacy-Preserving Empirically Private Learning

The evaluation tests the defense across datasets, model architectures, attack constructions, and threat models. It generally lowers empirical privacy loss with limited utility impact, while gradient-space attacks reveal important failure cases.

  • Experimental setup: The evaluation spans MNIST, CIFAR-10, and Purchase100 across CNN, WideResNet, and MLP architectures.The study also varies privacy budgets, training configurations, and augmentation multiplicity.
  • Experimental setup: 400 audit models per attack use 200 canary-present and 200 canary-absent training runs.The authors report that this scale reveals a substantial gap between filtered and unfiltered settings under their heuristics.
  • Input space attacks: The defense generally reduces εlb with minimal utility impact, reaching approximately 0 for MNIST CNN and CIFAR-10 WRN-16 across nearly all tested εub budgets.Alternative scoring rules, including prediction entropy and gradient kurtosis, also reduce auditable εlb for several other dataset-model combinations.
  • Input space attacks: Across FGSM, mislabeled in-distribution, and ClipBKD input attacks, the defense reduces empirical privacy loss.These constructions target harder input-space membership-inference scenarios than a blank or random canary alone.
  • Label-only attack: The defense lowers label-only attack TPR from 28.5% to 0.95% at 0.1% FPR.The authors attribute this difference to filtering vulnerable canary samples rather than merely obscuring confidence information.
  • Defense-aware input space attack: Defense-aware canary optimization lowers the initial canary's εlb from 2.453 to 0.65, while the optimized canary falls to 0.Optimization increases the average drop epoch but does not push it beyond the 100-epoch training horizon.
  • Gradient space attacks: Gradient-space attacks expose limitations: bandwidth canaries achieve group εlb = 27.26 with or without the defense, and gradient-canceling attacks produce non-zero privacy loss.Input-space attempts fail to reproduce gradient cancellation because per-sample gradient magnitudes cannot be reliably controlled across epochs.

A.1 Heuristic conventions and their (potential) pitfalls

The section formalizes pitfalls in empirical privacy auditing, especially when heuristic audit procedures lack statistical or structural validity. It contrasts formal corrections with GDP-based shortcuts and gives counterexamples to unsupported GDP assumptions.

  • Audit validity: Auditing guarantees require explicit justification because common practices may be heuristic rather than formally valid.The section emphasizes identifying when audit procedures' guarantees apply and provides counterexamples for invalid heuristics.
  • Multiple hypothesis testing: Holdout evaluation preserves formal validity, whereas selecting and evaluating the same tests requires multiple-testing correction.Bonferroni correction or holdout models are presented as formal fixes for multiple hypothesis testing.
  • Multiple hypothesis testing: Bonferroni correction can make εlb estimates negligible, while holdout auditing remains nontrivial but often worsens tightness by 3-10×.The section cautions against treating uncorrected εlb estimates at face value when multiple discovery is not accounted for.
  • Convexification: Convexifying the f-DP curve does not change the computed εlb, despite potentially exposing additional candidate points.Lemma 6 establishes equality between the original and convexified computations under its stated assumptions.
  • GDP extrapolation: GDP extrapolation is analytically convenient for Gaussian mechanisms and composition, but it is only heuristic when the true f-DP curve is not GDP.The section identifies failures under Poisson subsampling and hidden-state marginalization.
  • GDP extrapolation: The Gaussian mechanism with Poisson subsampling and adaptive Gaussian composition with only the final output do not always yield a µ-GDP trade-off.These counterexamples directly challenge treating GDP structure as preserved under those operations.

A.2 Numerical precision

The section analyzes finite-sample and numerical limits on empirical privacy lower bounds. It shows that CP corrections can collapse raw estimates and that auditable εlb grows only logarithmically with sample size.

  • Correction effects: Auditing procedures compute raw and Clopper-Pearson-corrected lower bounds from empirical FPR-FNR counts.The analysis restricts attention to observations with finite positive raw lower bounds before examining correction effects.
  • Sample-size limits: The largest finite auditable εlb grows only logarithmically, from around 4 at k = 200 to around 9 at k = 10000.This sample-size ceiling implies that accurately auditing large ε values requires very large k.
  • Correction effects: As k increases, fewer nonzero raw observations collapse to zero after CP correction, but the worst-case collapsed raw value remains around 2.4.The persistent worst case is associated with extreme low-count configurations near the binomial boundary.
  • Boundary effects: For γ = 0.05, the collapse threshold is approximately 5.57, with the largest qualifying count near c = 11.These values arise when kδ is small.
  • Boundary effects: The collapse gap persists when kδ remains small relative to c and disappears only around k ≳ 10^6 for δ = 10^-5 and c ≈ 11.In pure DP with δ = 0, the gap persists for every finite k.
  • Additional analyses: The appendices extend the numerical analysis through audits, filtering ablations, subsampling comparisons, canary variants, and increased trial counts.These include alternative input-space audits, sample signatures, non-canary samples, and GDP versus CP reporting.

B Disparate Impact

The disparate-impact evaluation finds that filtering disproportionately removes minority-group samples and reduces minority-group utility, though the effect becomes milder as subgroup imbalance decreases. Minority canaries also show substantially greater memorization than majority canaries.

  • Evaluation setup: The ColoredMNIST evaluation varies p from 99.5% to 75% and measures subgroup removal and groupwise utility.The dataset contains symmetric majority and minority subgroups across two digit classes.
  • Removal disparities: The defense targets minority groups more than majority groups, producing a disparate reduction in minority-group utility.The targeting effect becomes more benign as p becomes milder.
  • Memorization disparities: Minority-group canaries yield εlb = 1.145 versus εlb = 0.043 for majority-group canaries, indicating greater minority memorization.The comparison is performed on ColoredMNIST at p = 75%.

C.2 Group privacy audit

The defense is evaluated against group privacy by auditing models trained with and without a group of 500 mislabeled CIFAR-10 canaries. It substantially reduces empirical privacy loss under this threat model, although the measured group bound does not formally imply a proportionally smaller individual bound.

  • The audit uses the maximum loss across all canaries to distinguish models trained with versus without the canary group.
  • The evaluation uses k = 500 mislabeled canaries on CIFAR-10 and reports k-group privacy εlb.
  • The defense substantially reduces εlb under group privacy, but this result does not formally imply a k-times-smaller 1-group privacy bound.

D Sample Signatures

The sample-signature defense identifies high-risk samples using per-sample scoring functions and filters them during training. Across scoring choices and sampling settings, it generally preserves utility while reducing empirical privacy loss, including for varied canary strengths.

  • Sample Signatures: Filtering canaries too late is ineffective because they may already have been memorized, motivating early detection during training.
  • Sample Signatures: The CIFAR-10 ablation compares gradient, directional, and prediction-based scoring functions, including L∞ gradient norm, gradient kurtosis, entropy, and margin.
  • Sample Signatures: The defense consistently detected and removed canaries across scoring functions, while empirical privacy loss remained low and utility metrics stayed similarly high.
  • Sample Signatures: Varying canary interpolation strength did not produce a clear change in privacy loss, and the defense remained effective across constructions.

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

The privacy-onion analysis tests whether filtering the most vulnerable canary could increase the vulnerability of retained samples. In the reported MNIST experiments, the strongest non-canary audit was weaker than the fixed canary audit, reaching zero under the holdout evaluation.

  • The analysis addresses the privacy-onion concern that removing vulnerable samples might increase the vulnerability of retained samples.
  • The experiment trains 1000 shadow models, half with and half without a blank canary, to compare post-defense audits across MNIST samples.
  • The strongest adaptively chosen non-canary audit produces a much weaker εlb than the fixed canary audit.
  • With the formal holdout false-discovery correction, the auditable εlb of the best non-canary audit drops to 0.

H Increasing the Trial Count

The study increases the number of shadow-model trials to tighten empirical privacy estimation on MNIST. It compares εlb and model utility for defense and non-defense settings under the larger sample regime.

  • The scaled-up MNIST experiment uses 1000 shadow models, with 500 models per canary-included or canary-excluded condition.
  • The higher-trial experiment compares empirical privacy loss εlb and model utility between defense and non-defense settings.
  • Table 9 reports empirical privacy loss on MNIST with 1000 shadow models.

I.1 Global Filtering Ablation

The MNIST experiments compare global filtering with per-class filtering for a blank input-space canary. Global filtering achieved similar empirical privacy and test accuracy across bandwidth configurations, leaving the choice to implementation or dataset considerations.

  • Experimental setup: The experiments compare global top-k filtering across the dataset with local top-k filtering within each class on MNIST.The evaluation uses a blank input-space canary and emphasizes local filtering because prior work found stronger within-class poison signatures.
  • Results: Global filtering achieved similar empirical privacy and test accuracy to per-class filtering across all bandwidth configurations.
  • Practical implication: Filtering strategy can therefore be selected based on implementation convenience or dataset characteristics rather than privacy-utility tradeoffs alone.Global filtering may limit discarded samples, whereas local filtering may help when class imbalance is a concern.

I.3 Varying Filter Frequency Ablation

The ablation varies how often filtering is applied during CIFAR-10/CNN training. More frequent filtering produced the lowest empirical privacy loss, while filtering every 10 epochs produced the highest reported loss.

  • Experimental setup: The experiment applies filtering every k epochs for k ∈ {1, 5, 10, 20} on CIFAR-10 with a CNN and a blank input-space canary.
  • Results: More frequent filtering achieved the lowest empirical εlb of 0.43.
  • Results: Filtering every 10 epochs produced the highest reported empirical privacy loss, 1.39.

J Full Empirical Privacy Results Across Audit Methods

The paper reports empirical εlb primarily with GDP no-holdout auditing and supplements it with multiple holdout settings and CP analyses. Across the broader audit results, the filtered DP-SGD variant consistently achieves lower empirical εlb than the unfiltered implementation across input-space and hidden-state audits.

  • Reporting protocol: The primary metric is εlb from GDP no-holdout auditing, supplemented by GDP and CP results across multiple holdout fractions.GDP uses 25%, 50%, and 75% shadow-model holdouts; CP includes no holdout and the same holdout levels.
  • Scope: The audit-results appendix covers privacy budgets, datasets, architectures, sampling methods, attack types, canary strengths, filtering frequencies, bandwidths, and defense-aware settings.The listed tables include GDP and CP-related configurations alongside multiple attack and ablation families.
Loading 2608.28934v1…