Technical Summary: Trade-off Functions for DP-SGD with Subsampling based on Random Shuffling

Problem Statement

Differentially Private Stochastic Gradient Descent (DP-SGD) is the standard mechanism for training deep learning models under privacy constraints. While the $f$-Differential Privacy ($f$-DP) framework provides the tightest possible characterization of privacy guarantees through trade-off functions between false-positive and false-negative rates, existing analyses have predominantly focused on Poisson subsampling (where data points are independently included in minibatches with fixed probability).

However, practical implementations of DP-SGD and stochastic optimization typically employ random shuffling, where the dataset is permuted once per epoch and partitioned into fixed-size minibatches. This discrepancy between the analyzed algorithm (Poisson) and the deployed algorithm (shuffling) has left the privacy guarantees of real-world systems imprecisely characterized. Previous work on shuffled DP-SGD has provided only upper bounds on the trade-off function (lower bounds on privacy loss) via explicit adversarial events or numerical evaluations, lacking closed-form, transparent expressions. Furthermore, recent impossibility results indicate that for low noise multipliers ($\sigma \le 1/\sqrt{2 \ln M}$), the trade-off function is provably bounded away from the ideal random guessing diagonal ($1-a$), but the behavior in the high-noise regime remained an open question requiring a tight, closed-form analysis.

Methodology

The authors derive a tight, closed-form analysis of the trade-off function for DP-SGD with random shuffling within the $f$-DP framework. The methodology proceeds through the following stages:

1. Adversarial Reduction: The problem is reduced to a scalar hypothesis testing problem. Under the worst-case adversary model (which can isolate the contribution of a single differing record), the adversary observes $M$ rounds. Under the null hypothesis ($H_0$), all observations are pure noise $N(0, 1)$. Under the alternative hypothesis ($H_1$), exactly one round (chosen uniformly at random by the shuffling permutation) contains a shifted observation $N(1/\sigma, 1)$, while the rest remain noise.
2. Likelihood Ratio Test: By the Neyman-Pearson lemma, the optimal test thresholds the likelihood ratio, which reduces to thresholding the sample average of lognormal variables $Y_j = \exp(X_j/\sigma - 1/(2\sigma^2))$, where $X_j \sim N(0, 1)$.
3. Non-Asymptotic Analysis (Berry-Esseen): For a single epoch, the authors apply the Berry-Esseen theorem to bound the convergence rate of the sample mean of these lognormal variables to a normal distribution. This yields a concrete, non-asymptotic lower bound on the trade-off function $f(a)$ for the regime $\sigma \ge \sqrt{3/\ln M}$. The bound is expressed as $f(a) \ge 1 - a - \delta$, where $\delta$ is an explicit function of the noise multiplier $\sigma$ and the number of rounds $M$.
4. Asymptotic Analysis (Edgeworth Expansion): To improve upon the Berry-Esseen bounds, which are limited by a $O(1/\sqrt{M})$ error term, the authors introduce a proof technique based on a two-term Edgeworth expansion. This generalization of the Central Limit Theorem allows for a finer asymptotic estimate of the distribution of the sum of lognormal variables. This approach establishes the asymptotic behavior of the trade-off function as $M \to \infty$ with the number of epochs $E$ scaling as $E = c_M^2 M$ where $c_M \to 0$.

Key Contributions

1. Closed-Form Lower Bound for Single Epoch: The paper provides the first tight, closed-form lower bound for the trade-off function of shuffled DP-SGD in the high-noise regime ($\sigma \ge \sqrt{3/\ln M}$). The bound is given by:
   $$f(a) \ge 1 - a - \delta$$
   where $\delta$ is explicitly defined in terms of $\sigma$ and $M$ (Theorem 4.1). This result is tight up to constant factors within the Berry-Esseen proof framework.
2. Concrete Parameter Recommendations: The authors derive specific parameter settings for meaningful differential privacy. For a single epoch ($E=1$) with $\sigma=1$ and $\delta=10^{-2}$, they show that a dataset size of $N \approx 1.14 \times 10^7$ partitioned into $M \approx 1.14 \times 10^6$ rounds suffices. This demonstrates that meaningful privacy is achievable in federated learning settings with large datasets and a single epoch.
3. Asymptotic Gaussian-DP Characterization: Using Edgeworth expansions, the paper establishes that for fixed $\sigma$, as $M \to \infty$ and $E = c_M^2 M$ with $c_M \to 0$, the $E$-fold composed trade-off function converges uniformly to the random guessing diagonal ($1-a$). This improves the dependency on the number of epochs from the linear $O(E)$ penalty suggested by naive composition to an asymptotic $O(\sqrt{E})$ separation (Corollary 5.3).
4. Comparison with Poisson Subsampling: The authors compare their asymptotic results with the corresponding Poisson subsampling asymptotic. They find that in the low-noise limit ($\sigma \to 0$), random shuffling is asymptotically a factor of $\sqrt{2}$ closer to the ideal random guessing diagonal than Poisson subsampling, while the two regimes become equivalent in the high-noise limit ($\sigma \to \infty$).

Results

• Regime Validity: The analysis is valid for $\sigma \ge \sqrt{3/\ln M}$. This regime is complementary to the impossibility result of Ertan and van Dijk [12], which shows that for $\sigma < 1/\sqrt{2 \ln M}$, the trade-off function is bounded away from $1-a$. Together, these results map the privacy landscape of shuffled DP-SGD.
• Composition Bounds:
  • Non-Asymptotic: Iterating the single-epoch bound yields $f^{\otimes E}(a) \ge (1-\delta)^E - a$, implying a linear dependency on $E$ for the privacy loss.
  • Asymptotic: The Edgeworth-based analysis suggests a tighter dependency, where the separation from the diagonal scales as $O(\mu \sqrt{E})$ rather than $O(\mu E)$, provided $E$ scales sub-linearly with $M$.
• Practical Implications: The paper identifies the single-epoch regime as the "practical sweet spot" for shuffled DP-SGD. In federated learning scenarios where clients participate in few epochs, meaningful privacy guarantees ($\delta \approx 0.01$) are achievable with realistic dataset sizes. Conversely, the paper highlights a "multi-epoch explosion" where increasing $E$ under the linear composition bound rapidly renders the required dataset size $N$ impractical (e.g., requiring $N \sim 10^{11}$ for $E=100$).

Significance and Claims

The paper claims to provide a tight, closed-form analysis that resolves the mismatch between the algorithms analyzed in literature (Poisson) and those deployed in practice (random shuffling). By deriving transparent, interpretable bounds, the authors enable practitioners to read off parameter requirements directly without relying on opaque numerical tools.

The significance of the work lies in:

1. Bridging Theory and Practice: Validating that random shuffling, the standard in machine learning frameworks, admits a rigorous privacy analysis that is often more favorable than Poisson subsampling in low-noise regimes.
2. Defining the Privacy Landscape: Complementing existing impossibility results to define the precise noise thresholds required for meaningful privacy in shuffled DP-SGD.
3. Guiding Parameter Selection: Offering concrete formulas for selecting $M$, $N$, and $\sigma$ to achieve specific privacy budgets, particularly relevant for federated learning applications.

The authors remain modest regarding future work, noting that while the asymptotic results suggest an improved $\sqrt{E}$ dependency for multiple epochs, deriving a concrete, closed-form proof of this dependency (as opposed to the asymptotic limit) remains an open problem. Additionally, making the sequences $\delta_M$ and $\gamma_M$ in the Edgeworth expansion explicit to obtain a concrete multi-epoch bound is identified as a direction for future research.