Auditing $f$-differential privacy in one run

Auditing $f$-differential privacy in one run

Speakers: Saeed Mahloujifar, Luca Melis, Kamalika Chaudhuri

Conference: ICML 2025

YouTube: https://slideslive.com/39044047

Overview

In an era where state-of-the-art machine learning models are increasingly vulnerable to sophisticated privacy attacks, differential privacy (DP) has emerged as the gold standard for providing robust theoretical guarantees. However, the practical verification of these guarantees, particularly for large-scale models, presents significant challenges. This talk, presented by Saeed Mahloujifar from Meta, alongside collaborators Luca Melis and Kamalika Chaudhuri, introduces a novel method for auditing $f$-differential privacy in a single training run, marking a significant advancement in the field of privacy verification.

The core of this research addresses a critical limitation of traditional privacy auditing methods, which often necessitate multiple model training runs—an impractical endeavor for modern AI models that can take months or even years to train. By building upon recent breakthroughs in one-run auditing, Mahloujifar and his team demonstrate a technique that not only provides tighter lower bounds on the true theoretical epsilon of DP-SGD but also resolves an open question regarding the Gaussian mechanism, an important benchmark in DP research. This work offers a more efficient, accurate, and scalable approach to ensuring privacy compliance in complex ML deployments.

The implications of this research are far-reaching. It empowers practitioners, infrastructure teams, and model developers to empirically verify the privacy properties of their algorithms without incurring prohibitive computational costs. By offering a nuanced view of privacy through $f$-differential privacy and a generalized "guessing game" framework, the method enhances confidence in DP implementations, helps identify potential bugs or loose theoretical analyses, and ultimately contributes to the development of more trustworthy and privacy-preserving AI systems.

Background

▶ Watch: Introduction to DP and privacy auditing (0:00)

The rapid advancement of machine learning, particularly in areas like diffusion image models, production language models, and self-supervised learning (SSL) representation models, has unfortunately been accompanied by a surge in sophisticated privacy attacks. These attacks, ranging from membership inference (determining if an individual's data was used in training) to attribute inference (deducing sensitive attributes of training data) and reconstruction attacks (recreating training data), highlight the inherent vulnerability of complex models to data leakage. The standard response to mitigate these risks has been the adoption of differential privacy (DP).

Differential privacy provides a rigorous mathematical framework to quantify and limit the information an adversary can infer about any individual's data within a training set. Specifically, an algorithm satisfying $\epsilon$-$\delta$ DP guarantees that its output distribution remains statistically close when a single record is added to or removed from the training dataset. This strong guarantee directly translates into resilience against the aforementioned practical privacy attacks, making DP a highly desirable property for privacy-preserving machine learning. Historically, the paradigm involved proving DP guarantees for an algorithm, which would then implicitly assure protection against known attacks.

However, in recent years, the field has seen a shift towards privacy auditing. Instead of solely relying on theoretical proofs, auditing approaches work in reverse: they start by deploying practical attacks (like membership inference) against a trained model to empirically infer information about its true privacy posture. This process yields lower bounds on the actual privacy level of the algorithms. Privacy auditing serves several crucial purposes:

1. Verification of Correctness: It helps audit and verify the correctness of theoretical analyses and implementations of DP algorithms. If empirically observed privacy lower bounds are higher than theoretical predictions, it signals a potential bug or an incorrect analysis.
2. Tightness of Analysis: It helps assess the tightness of theoretical analyses for DP mechanisms. A significant gap between observed empirical privacy and theoretical DP predictions indicates looseness in the theoretical bounds.
3. Empirical Privacy Metric: For scenarios where strong theoretical DP guarantees are difficult to obtain or prove, auditing provides a valuable empirical privacy metric—a unified, practical measurement of privacy concerns based on state-of-the-art attacks.

Despite its benefits, traditional privacy auditing, often termed many-run auditing, faces a critical scalability challenge. Because differential privacy is a distributional guarantee, verifying it empirically typically requires running the mechanism (i.e., training the model) multiple times with slightly perturbed datasets to understand the output distribution. For modern, large-scale AI models, where a single training run can take months or even years, performing thousands of such runs for auditing is computationally prohibitive and often impossible. This limitation severely restricts the applicability of comprehensive privacy auditing in real-world, production-scale ML environments.

This challenge was partially addressed by the groundbreaking work of Steinke et al. (NeurIPS 2023), which introduced the concept of one-run auditing. Their work surprisingly demonstrated that it is possible to achieve a high-probability lower bound on a mechanism's privacy by running it only once. The key innovation lies in injecting controlled randomness into the input dataset itself, rather than repeatedly running the mechanism. The probabilistic bound is then derived based on the entropy injected into the dataset. While a significant step forward, this initial one-run auditing method had its own limitations, particularly in its tightness and applicability to certain DP mechanisms like the Gaussian mechanism, leaving room for further refinement and improvement.

Key Findings

▶ Watch: Transition from many-run to efficient one-run auditing (4:00)

The research presented by Mahloujifar et al. significantly advances the state of one-run privacy auditing, building upon and substantially improving the foundational work of Steinke et al. The core contributions and key findings of this study can be summarized as follows:

Firstly, the team developed a method that achieves tighter analysis for one-run auditing, leading to demonstrably better lower bounds on the true theoretical epsilon of DP-SGD. By refining the analytical framework, their approach provides a more accurate estimation of privacy guarantees, reducing the gap between empirically observed privacy and the theoretically predicted values. This improvement is crucial for practical applications, as tighter bounds offer greater confidence in the privacy assurances of deployed models.

A pivotal aspect of their work is the shift in focus from standard differential privacy (DP) to $f$-differential privacy. While DP imposes a linear relationship on the probabilities of outputs from adjacent datasets, $f$-DP offers a more generalized and nuanced perspective by allowing an arbitrary tradeoff function between these probabilities. This broader framework enables a more detailed and accurate characterization of a mechanism's privacy properties, which is essential for achieving tighter bounds in auditing.

The experimental results, particularly on the CIFAR dataset using DP-SGD, clearly illustrate these improvements. When comparing their auditing method (represented by the orange curve) against that of Steinke et al. (the blue curve), their approach consistently yields lower bounds that are closer to the true epsilon values (the dashed line). While a gap may still exist for larger epsilon values, the consistent improvement demonstrates the enhanced accuracy and reliability of their technique.

A particularly significant finding is the resolution of an open question posed by Steinke et al. concerning the Gaussian mechanism. The previous one-run auditing method struggled to provide tight approximations for this mechanism, with the approximated privacy values exhibiting an unstable pattern and failing to converge to the true privacy cost. In contrast, Mahloujifar et al.'s method successfully closes this gap, achieving much tighter privacy estimations for the Gaussian mechanism and, crucially, demonstrating that their method converges to the true privacy in the limit. This convergence property is a strong indicator of the theoretical soundness and practical efficacy of their refined auditing technique.

Finally, the researchers introduced a more general version of the "guessing game" setup previously used in one-run auditing. Their generalized game allows for more than two samples (denoted as k samples) within each data bucket used for constructing the audited dataset. Through ablation studies, they showed that increasing the number of examples k in each bucket leads to progressively better privacy estimations. This provides an additional control mechanism for scaling experiments and improving auditing accuracy without necessarily increasing the total number of "canaries" or samples injected into the dataset, offering greater flexibility and efficiency in the auditing process.

Technical Deep Dive

▶ Watch: Our work improves one-run auditing for DP-SGD (5:30)

The technical innovations presented in "Auditing $f$-differential privacy in one run" revolve around two main pillars: the adoption of $f$-differential privacy as the target privacy notion and the development of a generalized guessing game framework for empirical auditing.

At its core, differential privacy (DP) quantifies privacy by bounding the ratio of probabilities of any output occurring when an individual's data is either included or excluded from the dataset. Mathematically, for an $(\epsilon, \delta)$-DP mechanism $M$, for any two adjacent datasets $D$ and $D'$ (differing by one record) and any event $S$ in the output space, we have $P[M(D) \in S] \le e^\epsilon P[M(D') \in S] + \delta$. This implies a linear relationship in the logarithmic scale between the probabilities.

$f$-differential privacy, introduced by Dong et al., offers a more granular and comprehensive view of privacy. Instead of a single $(\epsilon, \delta)$ pair, it characterizes the privacy loss distribution using a tradeoff function $f$. This function describes the maximum probability of an event occurring in one dataset, given its probability in an adjacent dataset. Unlike the linear bound imposed by standard DP, $f$-DP allows for an arbitrary, potentially non-linear, relationship, thereby providing a more nuanced and tighter characterization of privacy loss, especially in scenarios where the privacy loss distribution is not uniform or Gaussian-like. The ability to target $f$-DP allows the auditing method to capture more intricate privacy properties and achieve tighter bounds.

The empirical auditing is conducted using a novel guessing game setup, which is a generalization of the method proposed by Steinke et al. The setup proceeds as follows:

1. Data Buckets: The process begins with m distinct buckets of data. Each bucket j contains k distinct records or samples. These k samples within a bucket are all potential candidates for inclusion in the training set, but only one will be chosen.
2. Dataset Construction: A training dataset D is constructed by sampling exactly one example from each of the m buckets, chosen completely at random. For instance, from bucket 1, one sample s_1 is chosen; from bucket 2, s_2 is chosen, and so on, until s_m from bucket m. The resulting dataset D = {s_1, s_2, ..., s_m} is then fed to the mechanism (e.g., a DP-SGD training algorithm).
3. Controlled Entropy: The key insight here is that this construction injects a significant and precisely controlled amount of entropy into the dataset D. The attacker knows the entire set of m buckets and their contents (k samples each). What the attacker does not know is the specific random choice made from each bucket to form D.
4. Attacker's Goal: The attacker's objective is to reconstruct the exact dataset D that the model was trained on. Since the attacker knows all possible choices for each bucket, their task is to guess which specific k samples were chosen.
5. Performance Metric: Unlike traditional membership inference, where success is a binary (boolean) outcome, the success of the attacker in this guessing game is measured by an integer score: the number of correctly guessed samples. If the attacker correctly identifies i samples out of m, their score is i. This provides a richer signal for auditing than a simple pass/fail.

The core mathematical underpinning of this auditing method is encapsulated in a main theorem that establishes an implication of $f$-DP on the probabilities associated with these guessing games. While the full details are complex and involve intricate probabilistic analysis, the high-level idea is to recursively relate the probability of making exactly i correct guesses (P_i) to the probability of making exactly i-1 correct guesses (P_{i-1}).

Specifically, the theorem provides bounds or relations between P_i and P_{i-1} under the assumption of $f$-DP. If a mechanism satisfies $f$-DP, then there should be a bounded relationship between the likelihood of an attacker guessing i items correctly and i-1 items correctly. By observing the empirical distribution of correct guesses (i.e., the histogram of P_i values from many attack attempts), one can invert this relationship to derive a lower bound on the true $f$-DP parameters of the mechanism. The recursive nature of this relationship allows for the propagation of bounds across different numbers of correct guesses, ultimately yielding a comprehensive privacy audit. This recursive formulation is crucial for leveraging the integer-valued success metric effectively and for achieving tighter bounds than methods that rely on simpler binary success metrics. The exact formulation of the theorem involves careful handling of probabilities and the properties of the tradeoff function f, which are elaborated in the full paper and poster presentation.

Experimental Setup & Results

▶ Watch: Leveraging f-differential privacy for nuanced auditing (6:50)

The empirical validation of the proposed $f$-differential privacy auditing method was conducted across several key scenarios, demonstrating its effectiveness and superiority over prior one-run auditing techniques. The experiments focused on auditing DP-SGD (Differentially Private Stochastic Gradient Descent), a widely used mechanism for achieving DP in deep learning, for which true epsilon-delta DP values can often be calculated, providing a strong benchmark for comparison.

Datasets and Mechanisms:

The primary dataset used for evaluating the method was CIFAR-10 (implied, as CIFAR is a common benchmark for image classification and DP-SGD), a standard dataset for image classification tasks. The experiments also included a crucial evaluation on the Gaussian mechanism, which served as an ideal setting for Steinke et al.'s work but also highlighted a significant gap in their method's ability to provide tight approximations.

Attack Strategy:

The auditing process utilized both black-box and white-box attacks. Black-box attacks assume no knowledge of the model's internal parameters, relying solely on its inputs and outputs. White-box attacks, conversely, have full access to the model's architecture, weights, and internal states. This dual-pronged approach ensures a comprehensive evaluation of the auditing method's robustness across different threat models. The core of the attack was the generalized guessing game described in the technical deep dive, where the attacker's goal is to reconstruct the randomly assembled training dataset D.

Baselines and Metrics:

The performance of the new auditing method was directly compared against the baseline established by Steinke et al. (NeurIPS 2023), the pioneering work in one-run privacy auditing. The primary metric for comparison was the lower bound on the true theoretical epsilon values of the DP-SGD mechanism.

Headline Results:

1. CIFAR Dataset Performance:

• The talk presented a snapshot of results for the CIFAR dataset, illustrating the improvement. The graph typically shows three curves: the true epsilon values (dashed line), the lower bounds obtained by Steinke et al.'s method (blue curve), and the lower bounds obtained by the new method (orange curve).
• The results clearly demonstrated that the proposed auditing method (orange curve) consistently yielded tighter lower bounds on the true epsilon compared to Steinke et al.'s method (blue curve). For certain epsilon values, the new method even achieved an almost exact match with the true epsilon. While a gap between the audited lower bound and the true epsilon still existed for larger epsilon values, the overall trend showed a substantial reduction in this gap, indicating a more accurate and reliable privacy estimation.

1. Resolution of Gaussian Mechanism Open Question:

• A significant outcome was addressing an open problem from Steinke et al.'s work regarding the Gaussian mechanism. Steinke et al. observed that their method struggled to provide tight approximations for the Gaussian mechanism; as the number of "canaries" (or injected entropy) increased, their approximated privacy kept increasing, then decreasing, never converging to the true privacy cost.
• The new method successfully closed this gap. Experiments showed that by using their technique, much tighter privacy estimations were achieved for the Gaussian mechanism. Crucially, unlike the baseline, their method demonstrated convergence to the true privacy in the limit as the amount of injected entropy (e.g., number of canaries) was increased. This convergence is a strong theoretical and empirical validation of the method's robustness and accuracy.

1. Ablation on Number of Samples per Bucket (k):

• The generalized guessing game introduced the parameter k, representing the number of distinct samples within each bucket from which one is randomly chosen. An ablation study was performed to understand the impact of varying k.
• The results indicated a positive correlation: increasing the number of examples k in each bucket led to progressively better privacy estimations. This finding highlights a new knob for scaling experiments and improving auditing accuracy. It suggests that by carefully designing the data buckets with a larger k, one can achieve more precise privacy bounds without necessarily increasing the total number of records in the dataset or the number of distinct "canaries," offering flexibility in experimental design.

In summary, the experimental results rigorously validate the proposed auditing method's ability to provide tighter and more reliable lower bounds on $f$-differential privacy, particularly for DP-SGD. The resolution of the Gaussian mechanism challenge underscores its theoretical strength, while the ablation studies on k demonstrate practical avenues for optimizing auditing performance.

Practical Implications

▶ Watch: Novel 'guessing games' setup for one-run auditing (8:00)

The "Auditing $f$-differential privacy in one run" research carries profound practical implications for the development, deployment, and verification of privacy-preserving machine learning systems, particularly in large-scale industrial settings.

For Practitioners and Infrastructure Teams:

The most immediate and significant implication is the dramatic reduction in the computational burden associated with privacy auditing. Traditional auditing, requiring multiple training runs, is simply infeasible for modern, complex AI models that can take months or even years to train a single instance. This work effectively democratizes privacy auditing for such models. Infrastructure teams can now integrate robust privacy verification into their MLOps pipelines without incurring prohibitive costs or timelines. This means that models can be audited for privacy compliance with a single training run, enabling faster iteration cycles and more frequent privacy checks throughout the model lifecycle. This capability is critical for companies deploying large language models, foundational models, or other computationally intensive AI systems where privacy is a core concern.

For Model Builders and Deployers:

Model builders gain a more precise and reliable tool for understanding the privacy posture of their algorithms. The method provides tighter empirical lower bounds on the true epsilon of DP-SGD, offering a more accurate assessment of the privacy guarantees being achieved. This is invaluable for:

• Verification of Implementation Correctness: If the empirically derived lower bounds are significantly higher than theoretically predicted values, it serves as a strong indicator of potential bugs or misconfigurations in the DP implementation. This allows developers to catch and rectify errors before deployment, preventing unintended privacy leaks.
• Assessment of Theoretical Tightness: Conversely, if a large gap exists between empirical observations and theoretical predictions, it suggests that the theoretical analysis might be loose. This insight can guide researchers towards developing tighter analytical bounds, improving the efficiency of DP mechanisms by allowing for less noise injection for the same privacy level.
• Unified Empirical Privacy Metric: In scenarios where deriving exact theoretical DP guarantees is challenging or impossible, the empirical privacy metric derived from this auditing method provides a practical, unified, and understandable measure of privacy risk, grounded in state-of-the-art attacks. This can inform decisions about model deployment and help communicate privacy assurances to stakeholders.

Tradeoffs and Limitations:

While revolutionary, the method, like any advanced technique, comes with its own set of tradeoffs and considerations:

• Data Preparation Overhead: The "guessing game" setup requires a specific way of preparing the training data by creating m buckets, each with k distinct samples. This might introduce additional data engineering overhead compared to standard training pipelines. However, this is likely a minor overhead compared to the cost of multiple full model training runs.
• Gap for High Privacy Budgets: As noted in the experimental results, for very large epsilon values (indicating less strict privacy), a gap between the audited lower bound and the true epsilon might still persist. While improved, the method may not achieve perfect tightness across the entire spectrum of privacy budgets.
• Assumptions on Attacker Knowledge: The auditing method assumes a specific attacker model (one who knows the buckets but not the random choice from each). While this is a reasonable and strong adversary for auditing purposes, it's important to understand the specific threat model being evaluated.
• Controlled Randomness: The injection of randomness into the input dataset, while crucial for one-run auditing, must be carefully managed. While designed to preserve the overall data distribution, any unintended side effects on model utility or training stability would need to be monitored. However, the talk suggests this is a controlled process with known entropy.

In essence, this work empowers organizations to bridge the gap between theoretical privacy guarantees and practical empirical verification, making it feasible to build and deploy privacy-preserving AI systems with greater confidence and efficiency. It shifts the paradigm from an expensive, multi-run endeavor to a single-run, scalable solution, directly addressing one of the most pressing challenges in privacy-preserving machine learning.

Key Takeaways

• One-run privacy auditing is now feasible and crucial: The research demonstrates that robust privacy auditing, previously requiring computationally prohibitive multiple model training runs, can now be achieved in a single run, making it practical for large-scale, modern AI models.
• Improved tightness for DP-SGD: The new method provides significantly tighter lower bounds on the true epsilon of DP-SGD, particularly on datasets like CIFAR, offering more accurate and reliable empirical privacy estimations compared to prior one-run techniques.
• Targeting $f$-differential privacy: By focusing on $f$-differential privacy, a more general and nuanced privacy notion, the method captures a richer characterization of privacy loss, contributing to the improved accuracy of the audit.
• Resolution of the Gaussian mechanism challenge: The work successfully addresses an open question from previous research, showing that the new method achieves much tighter privacy estimations for the Gaussian mechanism and, unlike prior work, converges to the true privacy in the limit.
• Generalized "guessing game" framework: The introduction of a more general guessing game, allowing for k distinct samples per bucket, provides flexibility and an additional mechanism to scale experiments and achieve better privacy estimations.
• Significant practical implications: This advancement drastically reduces the computational cost of privacy auditing, enabling practitioners and infrastructure teams to efficiently verify DP implementations, identify bugs, and assess the tightness of theoretical analyses in real-world ML deployments.

About the Speaker(s)

The research presented in "Auditing $f$-differential privacy in one run" is a collaborative effort by Saeed Mahloujifar, Luca Melis, and Kamalika Chaudhuri. All three researchers are affiliated with Meta, a leading technology company known for its extensive research and development in artificial intelligence and machine learning. Saeed Mahloujifar, who presented the talk, is a key contributor to this work, representing the team's efforts in advancing the field of privacy-preserving machine learning. Their collective expertise at Meta underscores the industry's commitment to addressing critical challenges in AI privacy and developing practical solutions for real-world applications.