Gradients Look Alike: Sensitivity is Often Overestimated in DP-SGD

Gradients Look Alike: Sensitivity is Often Overestimated in DP-SGD

Speakers: Anvith Thudi, Hengrui Jia, Casey Meehan, Ilia Shumailov, Nicolas Papernot

Conference: USENIX Security '24

YouTube: https://www.youtube.com/watch?v=uV_TwYbnYYE

Overview

In this USENIX Security '24 talk, Anvith Thudi presented a groundbreaking analysis challenging the conventional understanding of privacy guarantees in Differentially Private Stochastic Gradient Descent (DP-SGD). The work, titled "Gradients Look Alike: Sensitivity is Often Overestimated in DP-SGD," introduces a novel data-dependent perspective, arguing that the worst-case privacy bounds typically derived for DP-SGD can be overly pessimistic for a significant portion of training data points. This research provides the first per-instance differential privacy (DP) analysis for DP-SGD, revealing that many individual data points are considerably harder to attack than the worst-case scenarios suggest.

The core problem addressed is the discrepancy between theoretical DP guarantees and empirical observations: while DP provides strong, data-independent bounds against privacy attacks, practical attacks often fail to exploit these bounds fully for many data points. Thudi and his co-authors propose that this gap stems from an overestimation of "sensitivity"—how much a single data point can influence the model updates—when using a data-independent approach. By introducing concepts like sensitivity distributions and a new composition theorem for expected guarantees, their analysis offers a more nuanced and realistic assessment of privacy leakage on a per-instance basis, with significant implications for the efficiency and trustworthiness of private machine learning.

This work is crucial for the advancement of private machine learning, providing tools to understand and potentially optimize the trade-off between privacy and utility. By demonstrating that not all data points contribute equally to privacy leakage, it opens avenues for developing more efficient DP mechanisms and offers a deeper understanding of phenomena like memorization and unlearning in a differentially private context. The findings challenge long-held assumptions and pave the way for future research into data-dependent privacy analysis.

Background

▶ Watch: Primer on private machine learning and the adversary. (0:25)

The field of private machine learning grapples with the fundamental challenge of training models on sensitive data while protecting individual privacy. The primary adversary considered is one that, given a trained model and knowledge of the training algorithm, can infer whether a specific data point was included in the private training dataset. Preventing such membership inference attacks is a cornerstone of robust data privacy.

The de facto approach to achieving this protection is Differential Privacy (DP), a rigorous mathematical framework that quantifies the privacy loss incurred when an algorithm processes data. Specifically, this talk focuses on Renyi Differential Privacy (RDP), which requires that for any two "adjacent" datasets (differing by exactly one data point), the Renyi Divergence between the distributions of models trained on these datasets remains small. This indistinguishability property provides a strong, data-independent guarantee against privacy attacks, ensuring that the presence or absence of any single data point does not significantly alter the algorithm's output distribution.

The most common method to achieve DP in deep learning is Differentially Private Stochastic Gradient Descent (DP-SGD). Standard SGD involves sampling mini-batches, computing gradients for individual data points, and updating model parameters. To make this process differentially private, two key modifications are applied:

1. Gradient Clipping: The L2 norm of individual gradients is clipped to a predefined maximum value. This limits the maximum influence any single data point can have on the model update, ensuring that no single individual's data can disproportionately affect the training process.
2. Noise Addition: Gaussian noise is added to the aggregated, clipped gradients before the model update. This injects ambiguity, making it statistically difficult for an adversary to determine the exact gradients contributed by any specific data point, thereby masking individual contributions.

While DP-SGD provides robust privacy guarantees, a significant open problem persists: the current, worst-case analysis of DP-SGD is known to be tight for some contrived model architectures and data points. However, for most practical models and datasets, privacy attacks empirically tend to fall far short of what DP bounds allow. This suggests that the existing data-independent analysis, which considers the worst possible data point and worst possible model state, might be overly pessimistic for the majority of data points in real-world scenarios. This pessimism stems from treating the "sensitivity" (the maximum change in the output of a function when a single input is changed) to every data point as uniformly high, based on the clipping norm.

Previous attempts to explain this discrepancy have explored DP-like guarantees specific to individual data points, but these often required restrictive assumptions not met in practice. The need for a per-instance DP analysis of DP-SGD became evident: an analysis that could show, for specific pairs of adjacent datasets, that the Renyi Divergence (and thus privacy leakage) is much smaller than the worst-case bound. Such an analysis would directly imply that membership inference attacks against these particular data points would be far less successful, indicating that these points are "harder" to attack.

Beyond direct privacy implications, a per-instance DP analysis has broader relevance in trustworthy machine learning. For example, memorization, where a model learns specific details about a training point such that its removal significantly degrades performance, can be seen as a privacy vulnerability. A strong per-instance DP guarantee for a data point would imply it cannot be memorized, as its presence or absence has minimal impact on the model. Similarly, in unlearning—the process of removing the influence of a specific data point from a trained model—if a data point already has good per-instance DP, the models trained with or without it are already similar, effectively meaning the point is "unlearned" by default. This foundational work thus aims to provide the first such per-instance analysis, shedding light on these critical aspects of private and trustworthy AI.

Key Findings

▶ Watch: The open problem: why privacy attacks often fail. (3:00)

The talk presents several pivotal findings that fundamentally shift the understanding of privacy in DP-SGD:

1. First Per-Instance DP Analysis for DP-SGD: The most significant contribution is the development of the first analysis capable of quantifying differential privacy guarantees for individual data points within the DP-SGD framework. This moves beyond the traditional worst-case, data-independent bounds to provide a more granular and realistic assessment of privacy leakage.

1. Introduction of Sensitivity Distributions: To achieve per-instance analysis, the authors introduce a novel quantity called sensitivity distributions. Unlike the classical approach that assumes a fixed, worst-case sensitivity for all data points based on the clipping norm, sensitivity distributions capture the actual similarity of gradient updates between adjacent datasets. This allows for a more accurate, data-dependent estimation of privacy leakage at each step of DP-SGD.

1. New Composition Theorem for Expected Guarantees: The classical DP composition analysis considers the worst-case model at each step, leading to overestimation. This work introduces a new composition theorem that accounts for the expected per-step guarantees over the distribution of models encountered during training. This theorem incorporates a free variable P that allows interpolation between high-moment (worst-case) and low-moment (expectation) analyses, providing a more refined composition of privacy budgets.

1. Significant Overestimation of Sensitivity: The empirical results derived from this new analysis definitively show that for many data points, the per-instance privacy guarantees are substantially better (i.e., less privacy leakage) than the original data-independent bounds. On average, the rate of privacy accumulation for 500 random data points was found to be less than half of the data-independent bound by the end of training. For the best 10th percentile of points, the per-instance privacy was orders of magnitude better, even on a log scale.

1. Counter-Intuitive Privacy Phenomena: The research uncovers a surprising effect: training with weaker data-independent guarantees (e.g., less noise) can sometimes lead to improved per-instance privacy for certain data points. This occurs because less noise allows models to converge faster to states where they are less sensitive to many data points, thereby reducing their individual privacy leakage.

1. Correlation with Classification Performance: The analysis revealed that data points which are correctly classified consistently exhibit better per-instance privacy guarantees, on average, compared to incorrectly classified points, regardless of the training stage. This suggests that "easy" data points are inherently more private.

Technical Deep Dive

▶ Watch: Broader impact: per-instance DP implies no memorization/unlearning. (4:00)

The core innovation of this work lies in revisiting and refining the two fundamental steps of DP-SGD analysis: bounding per-step divergence and bounding the overall composition of these divergences.

Revisiting Per-Step Divergence

The classical analysis of DP-SGD's per-step privacy leakage is based on the assumption that every data point has the same maximum impact, determined by the clipping norm (the fixed value to which gradients are clipped). This means the sensitivity—how much the model update can change if one data point is swapped—is considered constant and maximal for every data point. This approach, while providing a robust upper bound, overlooks a crucial aspect: if many other data points in the dataset induce similar gradient updates to the one being considered, then removing or swapping that single data point might not significantly alter the overall distribution of updates. Consequently, the privacy leakage for that specific step would be much lower than the worst-case fixed sensitivity suggests.

To address this, the authors introduce a new quantity called sensitivity distributions. Instead of a single fixed sensitivity value, this approach models the sensitivity as a random variable that accounts for the actual distribution of updates within the mini-batch and across adjacent datasets. Specifically, a sensitivity distribution is derived by comparing mini-batches sampled from one dataset to a corresponding mini-batch from an adjacent dataset (differing by one point). This comparison focuses on the difference in magnitude of updates versus the magnitude of their difference, often involving quadratic terms. If the gradient updates from both adjacent datasets are consistently similar, this sensitivity distribution would yield values close to zero, indicating minimal privacy leakage.

Formally, the per-step leakage of DP-SGD is bounded by the expectation of this random variable, or more precisely, its log expectation exponential, which effectively captures higher moments of the distribution. By considering these moments, the analysis moves beyond a simple expectation to account for the variability and potential worst-case scenarios within the distribution, but still in a data-dependent manner. This refined per-step analysis demonstrates that for many random data points, the per-step privacy guarantees are significantly better than the data-independent bound, observed consistently at the beginning, middle, and end of training. This finding illustrates that "data sets mask updates," meaning the collective behavior of other data points can effectively hide the contribution of an individual.

New Composition Theorem for Expected Guarantees

The second challenge in DP-SGD analysis is composition: how do the privacy guarantees from individual steps accumulate over many training iterations? The classical approach to composition typically considers the worst-case model state at each step of training and then simply sums up the worst-case per-step guarantees. This method is straightforward but highly pessimistic because the actual model states encountered during training might rarely be the "worst-case" scenarios that maximize privacy leakage. Moreover, the model weights themselves are a distribution due to the randomness inherent in SGD (mini-batch sampling, noise addition), making the per-step guarantees (which depend on the current model state) also a distribution. The classical analysis effectively "throws away" this distribution by only considering its most unfavorable realization.

The authors propose a novel composition theorem that can handle expected per-step guarantees. Instead of summing worst-case bounds, this theorem sums the expected per-step privacy leakage, which is a more realistic representation of what happens over many training steps. Crucially, this theorem bounds the overall divergence after N steps of DP-SGD by the sum of the log expectation exponentials of the per-step guarantees.

A key feature of this new composition theorem is the introduction of a free variable P. This parameter allows for interpolation between different moments of the per-step leakage distribution. When P is chosen to emphasize high moments, the analysis leans towards a worst-case scenario, akin to traditional bounds. When P emphasizes lower moments, it provides a bound closer to the average or expected privacy leakage. This flexibility offers a more nuanced understanding of privacy accumulation. Furthermore, the theorem implicitly weighs initial steps higher, capturing the intuition that divergences occurring early in training have a more profound and lasting impact on the final model and its privacy properties compared to divergences later in training.

By combining the refined per-step analysis (using sensitivity distributions) with this new composition theorem (for expected guarantees), the researchers provide a powerful framework for obtaining per-instance DP guarantees that are significantly tighter and more realistic than previous data-independent bounds. This integrated approach allows for a precise quantification of how much more private specific data points are compared to the overly pessimistic worst-case estimates.

Demo / Proof of Concept

▶ Watch: Key innovation: introducing sensitivity distributions for analysis. (5:20)

While the talk did not feature a live, interactive "demo" in the traditional sense, the authors presented compelling empirical results and experimental validation of their new data-dependent analysis. These results serve as a proof of concept, demonstrating the significant practical implications of their theoretical advancements.

The primary demonstration involved comparing the per-instance privacy guarantees derived from their analysis against the original data-independent bounds. This comparison was performed on a dataset, evaluating the accumulation rate of privacy leakage over the course of training for many individual data points.

The findings were illustrated through plots:

1. Average Accumulation Rate: For 500 randomly selected data points, the researchers plotted the rate at which privacy leakage accumulated according to their per-instance analysis versus the data-independent bound. The results showed that, on average, the accumulation rate of per-instance guarantees was far smaller than that of the data-independent bound. By the end of training, the average per-instance guarantee was roughly less than half of the original data-independent guarantee. This quantitatively supports the claim that sensitivity is often overestimated.
2. Best 10th Percentile: The picture became even more striking when focusing on the 10th percentile of data points exhibiting the best (lowest) privacy leakage. For these points, the rate of accumulation of per-instance privacy was orders of magnitude better than the data-independent bound, as demonstrated on a log scale. This highlights that a significant subset of data points enjoys exceptionally strong privacy protection, far beyond what general bounds would suggest.
3. Counter-Intuitive Phenomenon: A particularly interesting result was the observation that training with weaker data-independent guarantees (e.g., by adding less noise to the gradients, which typically means less privacy) could actually lead to more per-instance privacy for these "best" points. The explanation offered is that less noise allows the model to converge more quickly to states where its parameters are less sensitive to many individual data points. In these more stable, converged states, the gradients from different data points become more similar, thereby reducing the per-instance sensitivity and thus enhancing per-instance privacy. This challenges the simplistic notion that more noise always equals more privacy.
4. Correlation with Classification: The experiments also investigated the characteristics of data points that achieve better privacy. Across all stages of training, points that were correctly classified consistently exhibited better (lower) per-instance privacy guarantees, on average, compared to incorrectly classified points. This suggests that data points that are "easy" for the model to learn and classify are also inherently more private, possibly because their gradients align well with the overall training objective, making their individual contributions less distinct.

These empirical validations underscore the practical utility and insights gained from their novel theoretical framework, providing concrete evidence that the existing worst-case bounds often paint an overly pessimistic picture of privacy in DP-SGD.

Defensive Implications

▶ Watch: Demonstrating significantly improved per-step privacy guarantees. (6:20)

The findings from this data-dependent analysis of DP-SGD have several crucial implications for defenders and practitioners working with private machine learning:

1. Re-evaluating Worst-Case Assumptions: Defenders should understand that the traditional, data-independent DP guarantees, while robust, are often overly pessimistic for a substantial portion of the training data. This means that for many individual data points, the actual privacy risk might be significantly lower than the worst-case epsilon suggests. This does not invalidate DP, but it provides a more nuanced understanding of where the actual risks lie.

1. Targeted Privacy Protection: The ability to identify data points with inherently better or worse per-instance privacy (e.g., correctly classified vs. incorrectly classified points) could inform more targeted defensive strategies. For instance, if certain types of "difficult" or misclassified data points are consistently less private, defenders might consider applying additional privacy mechanisms specifically to these subsets or investigating why they are more vulnerable.

1. Optimizing DP Parameters (with Caution): The discovery that training with weaker data-independent guarantees (less noise) can sometimes lead to improved per-instance privacy for certain points opens up a complex optimization space. In scenarios where a defender is particularly concerned about the privacy of a specific subset of "easy" data points, they might explore tuning DP parameters (like noise levels or clipping norms) differently. However, this must be approached with extreme caution, as reducing overall noise will reduce the worst-case guarantee, and the benefits for per-instance privacy are not universal across all data points. A global reduction in privacy parameters could inadvertently expose other, more sensitive data points.

1. Implications for Memorization and Unlearning: The direct link between good per-instance DP and reduced memorization/unlearning burden is a powerful insight. If a defender can establish that certain data points already possess strong per-instance DP, it implies that the model has not "memorized" them in a privacy-violating way, and they are effectively "unlearned" by default. This could potentially reduce the computational overhead required for explicit unlearning mechanisms for such points.

1. Security Risks of Revealing Per-Instance Guarantees: A critical warning articulated by the speakers is that data-dependent guarantees have inherent insecurity issues if revealed. Publicly disclosing the exact per-instance privacy guarantee for a specific data point (e.g., "this point has 10^-9 better privacy") itself constitutes a privacy leak. Such information could be used by an adversary to narrow down the possible characteristics of that data point, as only a few points might exhibit such extreme privacy levels. Therefore, while this analysis is invaluable for understanding and improving DP mechanisms internally, the specific per-instance epsilon values should not be directly exposed.

1. Future Tool Development: This research lays the groundwork for developing new tools and methodologies for auditing and evaluating the actual privacy leakage in DP-SGD models. Such tools could help practitioners get a more realistic picture of privacy, potentially enabling them to deploy models with a better privacy-utility trade-off, provided the computational cost of running such an analysis can be reduced.

In summary, this work provides defenders with a more sophisticated understanding of DP-SGD's privacy landscape, moving beyond blanket guarantees to a nuanced, data-aware perspective. While offering potential avenues for optimization and improved trustworthiness, it also emphasizes the critical need for careful consideration of the security implications when working with data-dependent privacy metrics.

Key Takeaways

• Sensitivity Overestimation: Traditional worst-case analysis of DP-SGD significantly overestimates the privacy leakage (sensitivity) for many individual data points in practical settings.
• Novel Per-Instance Analysis: The talk introduces the first per-instance DP analysis for DP-SGD, utilizing sensitivity distributions and a new composition theorem for expected per-step guarantees to provide tighter privacy bounds.
• Enhanced Privacy for Many Points: Empirical results demonstrate that many data points enjoy significantly better (lower) per-instance privacy leakage compared to the pessimistic data-independent bounds, with some points being orders of magnitude more private.
• Counter-Intuitive Noise-Privacy Relationship: In a surprising finding, reducing overall noise (weaker data-independent privacy) can, for certain data points, lead to improved per-instance privacy by enabling faster model convergence to less sensitive states.
• "Easy" Points Are More Private: Data points that are correctly classified by the model tend to exhibit better per-instance privacy guarantees, suggesting a correlation between learnability and privacy.
• Computational Cost & Security Warning: While powerful for analysis, the current per-instance analysis is computationally expensive. Crucially, revealing specific per-instance privacy guarantees to an adversary can itself be a privacy leak and should be avoided.

About the Speaker(s)

The talk "Gradients Look Alike: Sensitivity is Often Overestimated in DP-SGD" was presented by Anvith Thudi. This work is a collaborative effort with Hengrui Jia, Casey Meehan, Ilia Shumailov, and Nicolas Papernot. Anvith Thudi delivered the presentation, outlining the research and its implications. Hengrui Jia (also referred to as "Nick") and Ilia Shumailov were noted to be in the audience, available for questions and further discussion. Nicolas Papernot, a recognized expert in differential privacy and machine learning security, is also a key contributor to this joint research. The speakers are researchers who have collaborated on this significant advancement in the understanding and application of differential privacy in machine learning. Specific affiliations (titles, companies/universities) were not provided in the transcript or metadata bundle.