Advancing Differential Privacy: Where We Are Now and Future Directions for Real-World Deployment

Introduction

Over the past decade, differential privacy (DP) has become the predominant notion of privacy for both statistical data analysis and machine learning applications. Although it has seen larger adoption in academia, public services , and several industrial deployments more recently , it has not yet become a standard for data sharing use cases in companies or institutions where privacy protection is highly important. This brings two natural questions.

What are the challenges faced today by institutions that (want) adopt DP, and how can these be best mitigated?

What are the new challenges that we should expect as we move towards the next frontier, as DP is becoming a mature technology and adoption grows?

In July 2022, we organized a workshop (with the title Differential privacy (DP): Challenges towards the next frontier) with experts from industry, academia, and the public sector to seek answers to these broad questions. This document is the only public summary of the conversations from the workshop. This document is a collective viewpoint of the authors in the acknowledgment section, and does not entail any personal opinion of any individual.

Next, we provide a short overview of the topics we cover in the document.

Building privacy infrastructure for DP: At this point there are several high-profile deployments of DP in industry and in the public sector. During the course of deployments, a few common challenges evolved: a) deciding on the threat model and specific DP definition to use, b) the need to select privacy parameters and mechanism details that ensure the DP algorithm provides reasonable privacy/utility trade-offs, c) difficulty incorporating DP mechanisms into existing infrastructure that people already know and use (i.e., end-to-end), d) communicating to the user what DP provides and its “side-effects”, and e) ensuring the computation and storage costs do not disproportionately grow when compared to the non-DP baseline system. Section 2 discusses each of these challenges and provides research agendas around them that include developing methods and tools for selecting privacy parameters in a way that non-experts feel comfortable interacting with the system and exposing well-documented implementations of DP algorithms, along with the chain of trust, for external scrutiny, possibly taking the form of an open-source release of the implemented algorithm.

Improving privacy/utility trade-offs: While DP has been used in several large-scale deployments (mentioned above), many of these deployments have ended up with privacy loss parameters that provide little if any meaningful privacy, and the challenge that comes with maintaining high level of utility while preserving DP has limited its wider adoption. In the recent past, there have been research efforts to bridge this gap, especially, by using one of the following: a) public data to achieve better utility , b) designing algorithms which are data-adaptive , meaning the algorithms can achieve good utility if the data satisfies some “nice” properties, c) designing personalized DP learning algorithms which allows a part of the training procedure to be performed without adding any noise/randomness , and d) designing ML pipelines that are tailored specifically to learning with DP . Later in the document, we delve deeper into each of these aspects. When it comes to assessing privacy-utility trade-offs, note that sometimes there do not exist non-DP utility baselines to compare against. This is because certain data analyses are simply not permitted without privacy . In these cases, the ability to provide DP guarantees enables novel analyses—such as the application of ML—in settings where it was previously impossible. Later in Section 3, we explore each of these challenges, and discuss potential research questions around them. Along with addressing the challenges mentioned here, one thing that will significantly facilitate progress is the design of benchmark experiments . We will briefly touch on this aspect later in the document.

Attacks and auditing for privacy protection: Achieving a theoretical DP bound has its strong benefits but also presents certain limitations. In Section 4 we discuss in detail these limitations and the motivations and goals for developing practical privacy attacks and auditing techniques to complement DP guarantees. Currently, most of these auditing methods are based on simulating attacks. These methods can provide lower bounds on the information disclosed by the system . DP lower bounds achieved via the lines of state-of-the-art privacy attacks can provide guidance on the acceptable DP parameters, which may be significantly better than what is currently provable. On the other hand, they are lower bounds so they do not offer any guarantees when it comes to bounding the worst-case privacy risk faced by individuals participating in such ML pipelines. Hence, one has to be careful in interpreting the results of such audits, that is, the attack failure rate does not say anything about the susceptibility of the system to other attacks. We also provide examples from the literature to outline the open challenges in large-scale systems and several research directions.

A non-exhaustive exposition to DP Deployments: Most of the challenges/questions discussed in this document stems from real-world use cases of DP. provides a (non-exhaustive) survey of publicly documented deployments of DP (specifically from Google, Apple, US Census, Microsoft, Meta, and LinkedIn). We encourage the readers to follow , and the citations there for the details.

Building Differential Privacy Tooling and Infrastructure

For any technology, wider adoption often goes hand-in-hand with building a robust infrastructure that provides good solutions to a wide variety of use cases. Differential privacy is no exception: multiple existing deployments have used open-source differential privacy tools to generate aggregate statistics or synthetic data, and we can expect that infrastructure improvements would lead to even more such deployments. This section outlines some of the challenges that we have seen in the course of deploying differential privacy, then proposes a series of desiderata for differential privacy infrastructure, and finally suggests open research directions that could lead to concrete improvements in tooling for implementing differentially private systems.

In this section, we distinguish the usage of “user” and “adopter” for clarity purposes. “User” will be referred to when it is concerning the subject who owns or contributes data for which our interest is to provide privacy protection; we will try to use “adopter” as much as we can when referring to the adoption, development, and usage of the privacy-preserving system.

A number of challenges typically arise when deploying differential privacy.

Many organizations and people are grappling with complicated data privacy issues, and have some awareness that they may need to use privacy technology to solve them. But people often struggle to go from this vague awareness to a concrete idea of what approach best fits their problem. Differential privacy practitioners understand the kinds of problems that DP can solve, such as releasing aggregate statistics on sensitive data, providing internal access to run queries on sensitive data to (semi-)trusted analysts, building and deploying ML models trained on sensitive data, and safely collecting telemetry data, but the developers, policy-makers, and business leaders who need to make decisions about what to do often have a hard time understanding the differences in assumptions and threat models between these classes of use cases. Adding to this complexity, some specific data analyses are fundamentally incompatible with DP, like outlier detection. Other applications such as location-based services (e.g., contact tracing for pandemic prevention) are different from collecting aggregate statistics from mobility data since it requires fairly “precise” individual locations, while analytics is concerned about accurate aggregate information such as frequency and mobility patterns. Hence it requires extended definitions of DP (e.g., local differential privacy, geo-indistinguishability, and variants ) and specialized perturbation mechanisms to have meaningful privacy and utility guarantee . Potential adopters of DP need help understanding these nuances, mapping their threat model to a concrete approach, and choosing adequate tooling for their use case.

Although privacy researchers and practitioners understand how information about individual records can be reconstructed from released models or seemingly innocuous statistics computed on a dataset, these risks are not widely appreciated or understood. It is commonly believed that removing personally identifying information (PII) is sufficient to prevent leakage of private data. Privacy regulations such as the US medical privacy HIPAA law codify such assumptions, and such ad hoc masking techniques are prevalent in multiple industries. Thus, privacy advocates must often demonstrate the need for DP by demonstrating that alternative approaches might not be as safe as expected. This can be an uphill battle, as adopting differential privacy can lead to worse utility for the released data. This motivates increased research on auditing of privacy leakage (e.g., through privacy attacks) which we discuss in Section 4. It also should motivate differential privacy practitioners to highlight cases where DP unlocks previously-inaccessible data, as these demonstrate the opportunity for privacy technologies to enable new applications not just provide new privacy-utility tradeoffs for existing ones.

A careful modeling of trust assumptions is critical in any real-world privacy infrastructure, and DP systems are no different. Deployments must answer a number of questions: should we assume trust in a central server , how strong a potential adversary can be, or what kind of data needs protection. Threat vectors can sometimes be non-obvious: government actors, for example, can often demand existing/available data or compel organizations to implement new technical measures on top of existing systems. Insider risk is also relevant to many practical scenarios, and mitigating it requires additional protection mechanisms.

People who are not experts in differential privacy may object to a system that deliberately adds random noise to results.As an example of how adding DP noise is perceived, consider this text from Alabama’s lawsuit against the Census Bureau (which was decided in favor of the Census Bureau): “Thus, while the Bureau touts its mission “to count everyone once, only once, and in the right place,” it will force Alabama to redistrict using results that purposefully count people in the wrong place.”. Noise added to satisfy DP can also lead to strange behaviors — for example, adding noise to a count might result in negative values, some results that did not exist in the dataset might appear due to noise, or some results might be dropped due to counts not exceeding a threshold. Similarly, in machine learning with DP, it is common to observe a drop in model accuracy when learning with DP when compared to learning without DP noise. While many use cases can withstand some amount of noise, these discussions can be difficult, since the very concept of adding noise is contrary to the goals of most systems. It is worth noting that this aspect of data privacy contrasts with typical deployments of improved security practices, where data utility is still preserved, but only visible to a restricted set of approved developers.

The use of differential privacy can add significant computational overhead that might add complex engineering requirements to the vision of a product. This is particularly common for machine learning use cases. Consider the canonical DP-SGD algorithm for training ML models with DP guarantees . It includes a clipping step where individual per-example gradients are clipped to have a predefined maximum norm. But if implemented naively , this step prevents DP-SGD from leveraging the acceleration opportunities afforded by dedicated hardware, like GPUs or TPUs: averaging the gradient of multiple training examples must happen after the clipping operation, and minibatch sizes can no longer be adjusted to maximally use available hardware. It is often doable to design implementations that go around these limitations , but this requires additional work and expertise.

Statisticians and data scientists often want to perform exploratory data analysis to understand the data that they are working with, and choose which analyses to perform or which statistics to release. This typically involves practices like looking at small snippets of the data, which are not straightforward to adapt to differential privacy as it only naturally facilitates exposing frequent items such as n-grams , and top-$k$ results . If the data scientist does not have direct access to the data, this can lead to a bootstrapping issue: even though they could gain access to it via a DP interface, they cannot determine which queries to run. There is some work going in the direction of designing DP tools for exploratory data analysis , and existing interfaces like PSI could be a good starting point to build tooling for this use case. Further, differentially private synthetic data generation techniques could also partially address this problem. But this remains a largely unaddressed problem space.

2 Desiderata for Differential Privacy Infrastructure

In this section, we list design desiderata that we believe are particularly important to developing differential privacy infrastructure to address adopters’ needs, and contributing to the rise of practical deployments.

To effectively address real-world use cases and reach wide adoption, differential privacy infrastructure should be designed with end users, i.e. developers and data analysts, in mind. This means that a first step is to understand who the adopter of this infrastructure is. What are their goals? What do they need to achieve them? What is their initial level of expertise? Designing with non-experts adopters in mind is often a better choice: if only DP experts can use existing infrastructure, this severely limits how widely this technology can be deployed. To be beginner-friendly, tooling must have simple and elegant interfaces, with clear documentation, automatic hyper-parameter tuning, smooth onboarding experiences, and tutorials or other training videos. The path from picking up a new tool to building one’s first prototype must be as straightforward as possible. In particular, adopters should not have to understand the math behind differential privacy, or manually choose mechanisms or hyperparameters, before getting their first results.

Trust is paramount to privacy-critical software. All the infrastructure along the chain of trust should be published as open-source software. The community of DP implementers should converge on a small number of tools, centralize resources to audit and test these tools, and recommend them to potential adopters. Further, this community should grow to be a friendly and inclusive space where newcomers can ask questions and get support.

A large part of the differential privacy literature assumes that each user contributes a single data point to a dataset. This assumption is often not true: in large datasets recording user interactions with a service, each user of the service can be associated with many distinct data points . Some use cases require various other notions of privacy guarantees, like pre-aggregated data, social network data where each record is associated with multiple user identifiers, or data about heterogeneous entities (users or institutions) that require different privacy levels . Finally, some use cases for DP require quantifying the privacy guarantee associated with multiple units of privacy simultaneously, like reporting privacy budget values at the user level and at the attribute level. Support for these various possible units of privacy will likely be crucial in allowing infrastructure to address a growing variety of possible use cases.

Many potential adopters of differential privacy want to apply it to very large datasets, which cannot fit in memory on a single machine. General-purpose tooling should take this into account: DP mechanisms should be massively parallelizable whenever possible , and the overall architecture of DP software should be compatible with deployments on large clusters.

Small bugs in differential privacy software can easily lead to breaking the desired guarantees. Production tools should implement primitives carefully to mitigate known issues, like floating-point vulnerabilities . Other attacks like side-channel attacks should also be mitigated if they are part of the threat model, e.g. for interactive systems. More generally, tooling should adopt best practices in secure software design: modular design, systematic code reviews, comprehensive test coverage, regular audits, and good vulnerability management.

Many existing DP tools aim at providing end-to-end solutions (e.g., IBM’s privacy package, PSI, PINQ), but it could be more useful to separate DP accounting with the actual implementations of the algorithms that add noise. Problems associated with quality of randomness and floating-point arithmetics are best addressed in the implementation, while algorithm design and prototyping are best solved using tools such as autodp . This way, the verification of the actual implementation can be performed independently of the verification of the mathematical proof.

3 Research directions

In this section, we suggest promising research directions to address adopters’ needs regarding differentially private infrastructure.

Benchmarks are a great way of conveying utility or performance guarantees to end adopters, and to encourage further research. Differential privacy tooling often comes with onboarding examples, but these examples are often rather limited and do not include nuances like privacy budget management, or different units of privacy. Benchmarks would both help providing adopters with a more robust set of examples to explore and use as inspiration, and encourage the research community to contribute to and improve the existing infrastructure over time. These benchmarks should ideally reflect typical usage patterns of DP tooling, and they should be open to foster a culture of reproducible and transparent research.

Many algorithms in the DP literature require hyperparameters to be specified: clipping or truncation bounds, granularity levels, fraction of privacy budget for one step vs. another, and so on. These hyperparameters can be a significant hurdle for non-experts using DP tooling, and for engineers implementing these tools. A primary goal of DP infrastructure is to abstract away some of the complexity of the underlying mechanisms. The abstraction that requires someone to manually set hyperparameters is difficult to use and, worse, can lead to incorrect use of the system (e.g., resulting in a higher privacy budget than intended). Thus, whenever a newly developed DP mechanism is proposed in the literature, we encourage its authors to either suggest good default values for its hyperparameters, or develop additional DP algorithms to automatically and privately find a good value for these hyperparameters.

Data custodians and data practioners are struggling to quantify the empirical error of the DP mechanisms they are dealing with, and choose appropriate strategies and parameters. They need tools that provide them with useful error metrics, and these metrics must be displayed in a way that is immediately understandable on an intuitive level, in a visual way. There is no commonly shared understanding among DP experts about what error metrics are the most important or useful to optimize for when designing new algorithms. This leads to a significant fraction of the DP literature using error metrics that are often not the most relevant to practitioners. To change this, user research focusing on understanding and visualizing error and the uncertainty that comes with DP is of paramount importance to bridge theory and practice.

Differential privacy infrastructure is built by experts, who have a solid understanding of the fundamental concepts and at least a good familiarity with the scientific literature. But in order to reach widespread adoption, the resulting tooling must be usable by non-experts. This means it is necessary for tooling authors to regularly test the software they develop with developers, and perform usability research to improve it over time and make sure that the assumptions hold. Such formal user research studies can help identify who are the different kinds of potential adopters for DP tooling, and the existing gaps between adopter needs and feature availability and usability.

Building systems to support differentially private data analysis raises several questions. How can differential privacy infrastructure be embedded in existing data processing systems, in ways that can be easily maintained and extended over time? How does privacy budget tracking work across a large number of use cases, potentially using different units of privacy or privacy analysis technique? How can DP be integrated with other privacy-enhancing technologies and processes, like data governance, access control and monitoring, or insider risk measures? More exploratory research is needed to understand the requirements of such infrastructure improvements. Then, designing and prototyping such systems is also a worthwhile research direction.

Composition theorems are a well-researched topic of investigation in the differential privacy literature. However, most results and privacy accounting techniques assume that the composed mechanisms have a predetermined privacy budget. Recently, more complex notions of compositions have been studied: fully adaptive composition , where the privacy budget of subsequent queries can depend on the output of previous queries, and concurrent composition , where multiple analysts interact with a single DP engine in parallel. These theoretical questions have a direct impact in what privacy accounting techniques can be implemented in tooling, and there are still a number of open questions in this line of research.

Improving Privacy/Utility Trade-offs for DP Algorithms

From a theoretical standpoint, a lot of work has been done in the context of DP empirical risk minimization (DP-ERM) or DP stochastic convex optimization (DP-SCO) for convex losses. On the other hand, non-convex models, which form the crux of most real-world deployments, have not been explored at the same level. A few exceptions are . The hope is that theoretical insights in the space of non-convex models will drive the design of real systems.

From a practical standpoint, there have been recent works exploring the use of public data , as well as adding correlated noise to the DP-SGD training procedure (a.k.a. DP-follow-the-regularized-leader (DP-FTRL) ) to improve privacy/utility/compute trade-offs. These improvements are geared either towards providing a better optimization profile for DP-SGD, guided by information obtained from public data, or towards improving the computational complexity by allowing training over smaller minibatches without relying on privacy amplification. Taking the algorithmic improvements, and the improvements in the usage of public data into the design of the DP infrastructure remains largely unexplored. Some questions are:

What are the safety protections that we need when using public data, along the lines of what has been mentioned in ?

Can we assume any data available on the internet to be public?

What are the units of privacy one should consider, and design enforcement infrastructure for? For example, in the context of language models, should one consider a token, a paragraph, or the complete interaction of a single user as a single unit for privacy protection ?

Furthermore, today’s DP guarantees in the context of model training are w.r.t. a single training run. It is important to extend such guarantees to a system level guarantee for the complete DP infrastructure.

DP is often accompanied by significant loss in utility. While some of this loss is inherent, some may be incurred due to being overly cautious with what is and is not considered private. For example, suppose one wishes to learn how to diagnose patients based on a textual description of the patient. Some parts of this data may indeed be privacy sensitive: for example, characteristics of the patient and their symptoms. However, aspects such as grammar and syntax are basic parts of a language, and are not privacy sensitive. By privately training a model from scratch for this task, we are implicitly considering everything to be private. Some of these hurdles can be overcome by using public data.

We will refer to “public data” as data that is not subject to privacy constraints. Such data may be obtained from users opting out of privacy protection, or scraped from public sources on the internet. As a result, the properties of a public dataset may vary. To highlight a few, the public dataset may be unlabeled or labeled, small or large, and in- or out-of-distribution (with respect to the private dataset). The best way to employ public data will naturally depend on these attributes.

Public Pretraining and Private Finetuning: If public data is plentiful, then one can use it to pretrain a model. The model weights may then be subsequently fine-tuned using a private optimizer on the sensitive dataset. This transfer learning paradigm has been highly effective in the non-private setting, giving rise to the concept of foundation models , large pre-trained models which may be adapted to a variety of downstream tasks. Though this approach requires a large amount of data, the data may be out-of-distribution or even unlabeled (which can be dealt with through self-supervised learning ). Some works privately fine-tune large language models like BERT , RoBERTa , and GPT-2 and achieve only modest drops in utility compared to the non-private setting . Other works focus on image classification, using large-scale pretraining datasets such as CIFAR-100, Places365, ImageNet, and JFTWe note that the JFT dataset is proprietary to Google and has not been made public. and fine-tuning on CIFAR-10 or ImageNet . Some recent works have investigated when and why public data helps. proposes a method to predict how useful a public dataset will be to assist a private ML task. theoretically explores instances where public pretraining is necessary to obtain good utility.

Private Learning Assisted by Public Data: Another family of techniques involves incorporating public data into the private training process itself (independent of whether pretrained weights or features are used). These generally assume that the public dataset is small, and thus pretraining would be ineffective. A prototypical example computes a low-dimensional PCA of the public gradients and projects the private gradients onto this subspace . As gradients have been empirically observed to be approximately low-dimensional, this projection preserves most of the signal while reducing the amount of noise introduced by DP-SGD. As another approach, performs mirror descent with the loss on the public data as the mirror map which results in provable benefit with the size of private data proportional to the dimension $d$. An approximation of this approach is more simply stated as performing gradient descent with both the sensitive gradients (appropriately privatized) and the public gradients simultaneously (equivalently, using the public loss as a regularizer). A slightly different approach shows that using public data to obtain an initialization in combination with an aggressive regularization centered around that initialization results in provably improvement even if a constant number of public data points are available. Finally, investigate private adaptive optimizers, where the gradient moments are estimated using the public gradients.

The PATE framework (Private Aggregation of Teacher Ensembles) employs unlabeled public data using the sample-and-aggregate paradigm . Specifically, PATE trains an ensemble of models non-privately, and then privately aggregates their predictions on unlabeled public data, which is used to train a (private) student model.

Public data can also be employed for the important task of hyperparameter selection. Technically speaking, if one trains privately multiple models on a sensitive dataset for the purpose of hyperparameter selection, the privacy analysis must account for the number of models trained. Nonetheless, the vast majority of research papers in the private machine learning literature disregard the privacy cost of determining hyperparameters and only account for training the best model. Some works highlight and offer strategies to reduce the cost of private hyperparameter selection , though these generally incur constant factor overheads in the privacy cost. Instead, one can freely use public data to select suitable hyperparameters and transfer them to the private setting of interest, see, e.g., .

Conceptually related to public data, one can also employ “public priors,” in which we make choices about the training procedure which have better inductive bias for the settings of interest. A notable example is the work of Tramèr and Boneh . By using data-independent ScatterNet features , which are known to perform well on image classification for ImageNet-like data in the non-private setting, they show improved utility for similar tasks under DP. This fits into a broader line of work in private ML that makes substitutions to components of traditional non-private training pipelines, ranging from activation functions, to pooling functions, and normalization layers .

While most of the work above is empirical in nature, there are studies that have focused on the theoretical advantages of public data. A line of works studies the sample complexity of PAC learning with access to public data , giving a reasonably tight characterization. They show that a smaller amount of public data is needed, and even unlabeled public data generally suffice. in particular focus on a PATE-like setting , where private predictions are made online for an unlabeled public dataset. Bounds on the accuracy of online predictions are quantified, as well as the accuracy of models trained using this privately labeled public data, under i.i.d. and active query assumptions. Most of these works focus on the case where the public and private distributions are identical, though introduces a mixture-based setting where the distributions may differ.

Public Data in Private Query Release: Another canonical setting for differentially private data analysis is the problem of private query release. In this setting, the data analyst is tasked with privately releasing the answers to a set of statistical queries computed with respect to a (sensitive) dataset. This general problem captures a number of important use cases. For instance, releasing private summary data for the 2020 U.S. Census can be seen as an instance of private query release. Some works study the effect of public data in these settings , both theoretically and empirically. A recent challenge organized by NIST focuses on temporal map data , and provides participants with public data from a different year to help make predictions.

Partially Public Data: One can imagine settings where certain aspects of the data are public, while others are private. For example, in computational advertising, impressions are considered public information, and only conversions are sensitive as they may reveal users’ preferences. This inspired a relaxation of differential privacy called label differential privacy , where only the labels are sensitive, while the feature vectors are not considered to be private. This non-sensitive information allows one to obtain a better prior on the label of a point, in comparison to the uniform prior in the standard privacy setting. Under this model, proposes a multi-stage training framework that progressively refines these priors.

Pitfalls of Public Data: There are a number of challenges that arise when we introduce public data into the private machine learning pipeline . One difficulty involves the fact that publicly available data may not be appropriate to treat as fully “public”. Some examples include when data is posted online illegally, without the original owner’s knowledge or consent, or for use exclusively in one particular context (concerns of contextual integrity ). It is a risk to consider models which treat such content as public. Another issue pertains to the actual utility of public data in models used for privacy-sensitive settings. By their very nature, such applications often involve data that is not well-represented in public datasets. Since many benchmarks used for private machine learning are imported from the non-private setting and resemble data that is available on the Internet (e.g., ImageNet), results on these benchmarks may be over-representing the usefulness of public data for the settings in which privacy is actually relevant.

2 Data-adaptive Differentially Private Algorithms

Currently, most of the widely used DP mechanisms are not adaptive to the dataset. For example, common use cases of the Laplace and Gaussian mechanisms add noise calibrated to the global sensitivity of the given query as determined by the worst possible pairs of neighboring input datasets. In many real-life problems, however, it is often possible to adapt to a particular dataset and add less noise when the actual input is “nice.” Classical examples of such data-adaptive approaches include smooth sensitivity and Propose-Test-Release (PTR) . These approaches aim at calibrating the noise to the local sensitivity, i.e., the maximum possible change to the query when we change a given input dataset to its neighbor.Recent work generalizes these approaches beyond local sensitivities and noise addition mechanisms. Other properties of the data such as eigenvalue conditions, sparsity, and bounded support have been shown to unlock higher utility at the same privacy budget. In the context of deep learning, a number of adaptive variants of DP-SGD were proposed to reduce the noise. We survey existing results on data-adaptive DP algorithms and outline future directions in making these algorithms practical for large-scale deployment.

Smooth Sensitivity: For several queries of interest, such as the median of scalar values, the global sensitivity of the query can be significantly larger than the local sensitivity, i.e., how much the query output can change by modifying one data point for the given dataset. However, naively adding noise proportional to the local sensitivity is not differentially private because the noise itself could reveal sensitive information, especially when the local sensitivity could change drastically as we add / remove data points (e.g., in median queries). Smooth sensitivity is the oldest and one of the most elegant ideas for designing data-adaptive DP algorithms in these situations. It involves computing exponentially smoothed upper bounds of the local sensitivity and choosing heavier-tailed noise satisfying certain dilation properties according to the smoothed local sensitivity. It remains the primary approach for obtaining data-adaptive DP algorithms with pure DP. Moreover, the smooth sensitivity approach can be generically implemented for many problems through a sample-and-aggregate scheme, which has led to the first family of asymptotically efficient statistical estimators .

On the other hand, the smooth sensitivity framework is also limited in several notable ways. It is computationally inefficient due to the need to search all neighboring datasets for many hops (though useful classes of exceptions exist). The heavy-tailed noise and overhead from sample-and-aggregate often make the method less practical on moderate-sized datasets. In addition, known smooth-sensitivity-based mechanisms also have poor dimension dependence. One notable open problem is to derive fine-grained privacy accounting for smooth sensitivity-based mechanisms with Rényi DP , $f$-DP , or privacy profiles, so they become more compatible with modern privacy accounting tools. The recent work of takes an important step in this direction by deriving a new set of qualifying noise values that come with concentrated differential privacy (zCDP) guarantees. Another open problem is to characterize the dimension dependence in smooth-sensitivity-based mechanisms.

Propose-Test-Release: Propose-Test-Release (PTR) is a viable alternative to the smooth sensitivity framework with the same goal of essentially calibrating the noise to local sensitivity. This has been adopted to solve several problems including private selection and private semi-supervised learning . The main challenge is again that the local sensitivity itself is data-dependent. PTR gets around this issue by (1) proposing an upper bound on the local sensitivity, (2) privately testing whether it is a valid upper bound on the local sensitivity for the given dataset, and then (3) releasing the private query output only if the dataset passes the test. As in the median example, this framework is powerful for computing robust statistics of samples drawn i.i.d. from a distribution, where the local sensitivity can be significantly smaller than the global sensitivity. However, designing robust estimators for standard statistical estimation problems, such as mean estimation, covariance estimation, linear regression, and principal component analysis, is challenging in high-dimensions. To this end, proposes a framework for solving these problems via a high-dimensional PTR algorithm.

The vanilla PTR is not very user-friendly for a number of reasons. First, it needs to propose a bound, rather than computing one from the data. Second, the generic construction of the “private test” in Step (2) is a “distance test” that requires computing the nearest dataset (in terms of number of datapoint modifications) that violates the proposed local sensitivity bound, and thus is not computationally efficient in general. For statistical estimation problems, the computational complexity of PTR often grows exponentially in the ambient dimension. For these reasons, typical adoption of PTR is either for low-dimensional problems– studies trimmed mean, median, and short-cut regression and study robust mean and median–or have exponential run-times, e.g., mean estimation , covariance-aware mean estimation , depth-based medians , and general statistical estimation . For the special case of covariance-aware mean estimation, recent breakthroughs in managed to achieve the optimal sample complexity with an efficient algorithm, which previously was only possible with exponential-time algorithms based on PTR in . Several other private statistical estimation problems exhibit computational gap, where exponential time algorithms achieve strictly better sample complexity compared to efficient counterparts. It remains open whether these gaps can be closed with the tools from .

PTR-like Mechanisms: There are a number of variants of data-adaptive mechanism design that leverage PTR-like ideas, but do not suffer from the aforementioned limitations. They are less widely applicable than the vanilla (distance-test-based) PTR, but are computationally efficient when they qualify. These approaches include privately bounding local sensitivity which avoids the “propose” step of PTR, and privately testing the stability margin which avoids the part that adds noise, and thus also works for non-numeric queries. A concise treatment of these methods is given in [313, Section 3]. These methods allow PTR to be applied with less overhead to learning algorithms. Notable example applications include private topic models (LDA) with spectral methods and model agnostic private learning (a variant of PATE). Recently, PTR and PTR-like mechanisms were generalized to cover data-adaptive algorithm design beyond noise-adding mechanisms . Their approach, known as Generalized PTR, modifies the three steps of the vanilla PTR as follows: (1) it proposes native parameters $\phi$ of a randomized algorithm $\mathcal{M}_{\phi}$ rather than an upper bound of the local sensitivity; (2) it privately tests whether the resulting data-dependent privacy parameter ($\varepsilon$ as a function of a particular input dataset and $\phi$) is below a prescribed budget; (3) it executes the algorithm with the proposed parameters only if it passes the test. This allows a PTR-like procedure to be derived for mechanisms such as posterior sampling, objective perturbation, PATE, and so on.

Data-adaptive DP algorithms via data-dependent DP losses: Recall that data-adaptive DP algorithms aim at “adding a smaller amount of noise” when the dataset is “nice”. The flipside of data-adaptive DP algorithm design is what is known as data-dependent DP losses $\varepsilon(\text{Data})$, which aims at quantifying how much smaller the privacy loss incurred by a “nice” dataset is when we add a fixed amount of noise . The latter scheme fixes the accuracy while allowing the privacy loss to vary, thus can be appealing in applications where preserving utility is more important than ensuring (a fixed level of) privacy . Different from the standard “accuracy first” setting, the privacy losses are data-dependent now, thus considered sensitive information. To address this issue, proposes a smooth sensitivity-based method to release the data-dependent Rényi DP parameters. Strictly speaking, even if data-dependent DP losses are released privately, the overall algorithm is still not a data-adaptive DP algorithm. shows that one can always construct such a data-adaptive DP algorithm with any prescribed privacy budget by a simple post-processing procedure that abstains unless a high probability private upper bound of the data-dependent DP loss is smaller than the given privacy budget.

Related to this idea, proposes to maintain a privacy accountant for each individual in the dataset and to remove data points whose personalized differential privacy budget is used up. This approach, known as an individual Rényi filter, ensures a worst-case DP bound while allowing the algorithm to run longer than the worst case. Unlike the PTR and smooth sensitivity frameworks, this approach does not need to explicitly test any data-adaptive properties, thus could be a promising approach for more applications. An interesting open problem is to design the equivalent of the individual Rényi filter for per-instance DP losses (instead of the personalized DP losses).

Statistical Estimation: Private statistical estimation problems are arguably one of the most prominent applications of data-adaptive DP algorithms. These tasks (e.g., private mean estimation) are, in general, impossible for worst-case datasets. To see why, observe that the mean of a dataset is arbitrarily sensitive to the addition or removal of a single extreme outlier. Even worse, the worst-case sensitivity is large for every dataset, even otherwise “well-behaved” datasets. This is in contrast to, e.g., the median, where the statistic is insensitive for well-concentrated datasets. To resolve this tension, it is common to make distributional assumptions, such as sub-Gaussianity or bounded moments of the underlying distribution . Some works require minimal knowledge of underlying distribution parameters (e.g., which moment of a distribution is bounded), and instead adapt to them .

A line of work explores the connections between robust and private statistics. Intuitively, both types of estimators should be insensitive to modifications of parts of the dataset, but formalizing connections has proven to be more challenging. Dwork and Lei introduced the aforementioned PTR framework, with which they demonstrated that robust statistics are particularly amenable to privatization. obtained rate-optimal bounds using smooth sensitivity by leveraging ideas from robust statistics. Some works use similar ideas in the multivariate setting, either privatizing multivariate medians (e.g., the Tukey median ) or more generally employing PTR-based ideas . Other works employ recent advances in efficient multivariate robust statistics to the domain of privacy . A number of recent works employ the exponential mechanism in combination with robust statistics in a manner referred to as the inverse-sensitivity mechanism , allowing one to convert a robust estimator into a private one . Reductions in the other direction, that privacy implies robustness, are also known . However, due to important technical caveats we omit here, these reductions between robustness and privacy are far from an equivalence. Further understanding the connections between robustness and privacy remains an exciting direction for further investigation.

Most work in this area is largely theoretical. Some works attempt to produce practical tools for private estimation . Finally, a recent line of work shows how to privately learn critical parameters and tuning the bias-variance trade-off from data to improve overall utility . Proper tuning, while time-consuming leads to large empirical utility gains. Building better and more practical estimators, particularly based on recent advances through connections with robust statistics, is another interesting direction forward for the field.

Data-adaptive algorithms in DP-SGD and its variants: Attempts to obtain data-adaptive DP algorithms for deep learning tasks are often variants of DP-SGD that involve data-adaptive choices of its hyperparameters (e.g., learning rate, weight decay, pre-conditioner , clipping threshold , privacy budget allocation , and so on), sometimes in every iteration. These methods are not traditionally considered data-adaptive DP algorithms, but we believe they not only are but also might be among the best of such algorithms in practice whenever they are applicable. Some of these data-adaptive choices are consequences of adaptive composition [e.g. 343, 344]. Others require an additional privacy budget to be allocated for making these choices [e.g. 33] — much like most other recipes for data-adaptive DP algorithms that we have seen earlier. We will discuss a few representative methods below.

Private gradient descent methods require clipping the norm of each sample gradient in order to control the sensitivity. However, the ideal norm-clipping threshold is challenging to know a priori and may even change dramatically over the iterations. overcome such challenges by finding a threshold adaptive to the distribution of the norm of the gradients in each mini-batch, while spending a small fraction of the privacy budget in the process. Theoretically showing the gain of such adaptive clipping requires some statistical assumptions on the data, such as those typically assumed in statistical estimation problems. For example, for linear regression, uses adaptive norm-clipping to achieve improved sample complexities compared to gradient descent with non-adaptive clipping in and other approaches that use adaptive regularizers but are not based on gradient descent . The state-of-the-art sample complexity for DP linear regression is achieved in using a novel adaptive norm-clipping, which also provides robustness against label corruption. Beyond adapting to the gradient norm only, a more sophisticated clipping method that adapts to the geometry of the gradients is critical in achieving optimal sample complexity in principal component analysis . A natural question to ask is if such methods can be applied to private structured estimation problems to give similar gains, such as sparse linear regression and sparse principal component analysis .

In practice, spending privacy budget on adaptive clipping can be costly, especially if one desires more sophisticated adaptive methods. A series of works achieves significant gains by using in-distribution public data, i.e., examples sampled from the same distribution as the training data but do not require privacy. use more sophisticated clipping that adapts to the geometry of the gradients, project the gradient to a lower dimensional subspace, and use public data to compute the statistics of past gradients in the Adam optimizer.The main idea is to find better adaptive methods using the public data to avoid spending the privacy budget. However, these approaches suffer significantly when there is a distribution shift in the public data. It remains an important open question whether one can harness the benefit of public data with adaptive DP-SGD using out-of-distribution public data. We refer to Section 3.1 for an extensive summary of the use of public data.

A line of work improves the DP-SGD by carefully allocating the privacy budget per iteration. is the first to propose the adaptive privacy budget strategy, where it uses a smaller privacy budget for gradients with large norms and a larger privacy budget for gradients with small norms. provides a dynamic privacy budget allocation method with the assistance of a public validation dataset. Specifically, it checks the validation accuracy periodically during the training process, and when the validation accuracy stops increasing, it triggers the privacy budget to increase for subsequent epochs. However, this line of work critically relies on the convexity of the problem. It remains an interesting open question whether similar adaptive schemes can be applied to improve more general non-convex optimization.

Summary: We conclude the discussion on data-adaptive DP algorithms by remarking that the design of such algorithms is still an art that needs to be done on a case-by-case basis. It requires domain knowledge in identifying what “nice” properties of a dataset to exploit. It is also more delicate and error-prone than non-adaptive DP algorithms. Nevertheless, going data-adaptive is a crucial step in bringing DP algorithms to an acceptable level of utility in applications. We believe more work is needed on this problem before we can converge on a handful of best practices.

3 Mitigating Heterogeneous Privacy/Utility Trade-offs

The noise added to achieve differential privacy could have a larger impact on the utility of marginalized subpopulations because they are more prone to the uncertainty induced by noise. When making decisions based on differentially private data summaries, under-represented groups may suffer from a larger utility loss . A similar phenomenon also exists in differentially private machine learning applications. Machine learning algorithms are known to have unfair performance for groups that are under-represented in training data . Unfortunately, learning with differential privacy could exacerbate such unfairness. The accuracy drop associated with differential privacy turns out to be higher for under-represented groups, i.e., “the poor get poorer” . Under-represented groups thus suffer from worse privacy/utility trade-offs.

Mitigating heterogeneous privacy/utility trade-offs is an active research topic . propose a post-processing ‘repair’ algorithm to improve the fairness of decision-making. show that the gradient bias in private learning is an important source of disproportionate impacts and propose mitigations correspondingly. compare PATE with DP-SGD and show PATE has less impact than DP-SGD.

Although the above line of work has considerably mitigated the disproportionate impacts under various settings, another line of work theoretically shows that unfairness in accuracy is inevitable in some data distributions. show there exist data distributions on which enforcing fairness for a private algorithm would necessarily result in trivial accuracy. further study this tension under the assumption that the data has a long-tailed structure. Their work suggests that, for a non-trivial target accuracy, one has to tradeoff between privacy and fairness. validate the theory on several real-world datasets and show that relaxing the target overall accuracy is an effective method to improve fairness.

4 Building Information Theoretic Understanding of Differential Privacy

In addition to developing better algorithms, it is crucial to understand the fundamental limits arising from imposing DP constraints. Several methods have been proposed to lower bound the accuracy of algorithms for central DP. Fingerprinting is a versatile approach under approximate DP that has established strong lower bounds for various problems, such as attribute mean estimation , ERMs , and private selection . Private Assouad’s method is particularly useful for problems with discrete domains, such as distribution estimation . For the special case of $\delta=0$ (i.e., pure DP), the packing argument , as well as its probabilistic version, private Fano’s inequality , is a geometric approach that can provide tight lower bounds for $(\varepsilon,0)$-DP. Notably, the proof of this approach is relatively straightforward and aligns well with non-private proof techniques .

Local differential privacy (DP) has also been a focus of research, with initial work proposing private versions of Le Cam, Fano, and Assouad, subsequently improved and generalized upon by . Additionally, proposed a lower-bounding technique based on Chi-squared contraction which yielded tight lower bounds for distribution estimation and identity testing .

Despite the progress made in understanding DP lower bounds, several challenges remain to be addressed which we discuss next.

More complicated scenarios: Despite significant progress in proving lower bounds, most research has focused on relatively straightforward scenarios such as mean estimation , hypothesis testing , and ERM . Consequently, the issue of deriving strong lower bound results for more intricate scenarios, such as graph problems and online learning , persists as a compelling challenge.

Interacting with other constraints: Previous literature has typically examined privacy as the sole constraint and investigated the trade-off between privacy and utility. However, in real-world applications, privacy is not the only constraint and often interacts with other limitations such as computational complexity , interactivity , communication , fairness , interpretability , robustness of statistical estimation , robustness against data poisoning , and robustness against adversarial examples . Understanding how privacy interacts with these other constraints remains a complex task.

Instance-optimal lower bounds: The minimax framework is usually the first thing that comes to mind when measuring the utility of statistical estimation tasks. However, this worst-case optimality is practically meaningless and result in unnecessary noise being added to the system when the global sensitivity is far larger than the local sensitivity. Therefore, researchers have begun exploring instance optimality , a framework which seeks to optimize the loss for each individual dataset. While this approach has demonstrated potential, there is still a necessity for algorithm and lower bound advancements, making it an exciting and demanding area of research.

Choosing the right privacy metric: The DP framework is characterized by its concrete privacy semantics, derived from the its “differential” interpretation. Notwithstanding, there exists a variety of DP variants, encompassing pure DP and $(\varepsilon,\delta)$-DP, alongside divergence-based DP definitions such as Rényi DP and truncated concentrated DP , and $f$-DP , which are interpreted directly through a hypothesis-testing viewpoint. Among these, some DP metrics excel in terms of interpretability, while others possess more information-theoretic characteristics, making them well-suited for applications requiring tight privacy bounds, such as hyperparameter tuning and information-theoretic tradeoffs between privacy and utility . We posit that an advantageous research direction entails developing a framework for determining the most suitable privacy definition for a given task.

Balancing Privacy Parameters: A widely acknowledged challenge in implementing DP mechanisms stems from the necessity to use a large $\varepsilon$ parameter to ensure an exceedingly small $\delta$ parameter, in order to preclude the “release-one-at-random” mechanism . In particular, it is common practice to set the $\delta$ parameter significantly smaller than the reciprocal of the dataset size. Contrary to the “release-one-at-random” mechanism, numerous practical mechanisms allow for a smooth tradeoff between the two privacy parameters. This observation implies that the need for such a small $\delta$ might not be essential and, if so, a considerably smaller $\varepsilon$ parameter could be employed, potentially fostering a wider appreciation of DP within practitioners and stakeholders. As such, it is imperative to rigorously and comprehensively address the selection of the $\delta$ parameter as an important research direction.

Better toolbox: Lastly, even though lower bound proof has seen significant accomplishments, we still need better tools to address existing limitations. For instance, the fingerprinting lemma’s inability to handle discrete inputs, and the private Assouad’s method is imprecise for certain typical problems, such as Gaussian mean estimation. Moreover, for packing lower bounds, it only applies when $\delta$ is exceptionally small. Furthermore, the majority of prior tools have focused on asymptotic analysis, which overlooks the significance of constants. As our comprehension of the asymptotic case has advanced, there is a pressing need for tools with improved constants.

Privacy Attacks and Auditing as a Measure of Protection

The fundamental goal of differential privacy is to prevent the leakage of private information to an adversary. DP achieves this goal by providing a provable guarantee, a generic bound on privacy leakage that makes few assumptions about an adversary’s goals and capabilities. This approach has a number of limitations.

First, the DP bound may not inform stakeholders of the degree to which the system of interest is initially vulnerable to concrete attacks against the privacy of data: this may make it difficult to assess the privacy risks prior to deploying a DP algorithm—and later on to measure the gains and benefits of deploying an algorithm that does provide DP guarantees.

Second, because the bound is agnostic to the adversary’s capabilities, it may be too conservative or inaccurate in some settings. This is for instance the case if the threat model for a particular system does not allow for some of the adversaries that are captured by the DP definition. In some cases, the bound given for a DP algorithm may even be incorrect due to the complication of implementing the DP algorithms. There are well-documented instances , where the implementation of the DP algorithm did not match the algorithmic description, which makes all of the formal guarantees provided by DP proofs meaningless.

Third, differential privacy captures only one very specific notion of privacy as defined by the neighboring data sets used in the inference bound. As pointed out by , differential privacy does not provide any guarantees for arbitrary data release, where the predefined neighborhood notion can become vacuous. That is, it can reveal dataset and population statistics and properties of data distributions , which may be an important privacy consideration when the training dataset or distribution itself is not public. Hence, there may be settings where additional definitions, audits, or analyses may be necessary to ensure a model does not violate disclosure requirements in ways that are not captured by differential privacy. For example, one may consider using Pufferfish privacy which is a more general privacy framework and has been used to capture protection of correlated data and protection of dataset-level information .

These limitations motivate the need for an evaluation of privacy that is based on empirical analyses of the underlying systems. The pioneering work of initiated the study of empirical evaluation of privacy for simple mechanisms, which is subsequently analyzed and improved in . The important issue of which two neighboring datasets to use in the empirical measurements has not been systematically addressed in these works. Today, these analyses are often done in the form of simulated attacks where an analyst defines an attacker with goals and resources and attempts to execute an attack that can measure leakage from the target system. Such attack-based evaluations or auditing provide results that are complementary to the theoretical DP guarantees.

In this section, we distinguish privacy attacks and auditing by their intent. A privacy attack is conducted by an adversary to reveal private information, while a privacy audit is conducted by the system designer to anticipate the privacy leakage present in the system. An audit can be seen as a way of anticipating the threat of privacy attacks, and techniques used for privacy attacks can also be used to conduct audits.

2 Attack Algorithms

There are several types of attacking algorithms that are often used for privacy auditing, here we give a brief overview of two of those. We encourage the readers to explore some of the classic attacks in the DP literature and (their implications in the context of US Census ) for a broader exposure.

aim to infer whether a data point was used to train a target machine learning model or not. These attacks can lead to substantial privacy concerns for the individuals involved. For instance, upon ascertaining that a clinical record was used in training a model associated with a specific disease, membership inference attacks may deduce, with a high probability, that the individual linked to the clinical record has the disease. Prior works have shown that attackers can effectively launch MIA by solely relying on the prediction vector of a data point from a machine learning model; These attacks typically exploit subtle differences in the model’s performance on in-sample (training) data versus out-of-sample (non-training) data. Recent studies further demonstrate the possibility of MIA in more constrained settings, where the target model provides only the predicted label to the attacker. Other works demonstrated MIA in aggregated data release settings .

have become an increasing threat in machine learning, as adversaries seek to undermine the security and privacy of training data by retrieving the original examples or uncovering sensitive information embedded within them. Model inversion attack demonstrates that a “representative” face image corresponding to a person (a class) can be reconstructed from a face recognition model given the name of the person (the class label) and white-box access to the model. While the membership inference attack recovers the “existence” information of a target data point, model inversion attack recovers the visual property or features of a target class (which can correspond to a person).

Point-wise reconstruction of an individual training data point is an even more severe type of leakage than recovering the “representative” data. Recent studies have showcased the feasibility of extracting individual private image data from trained image classifiers . However, these findings rely on strong assumptions concerning model architectures (e.g., simple CNN models with a few layers) or the attacker’s capabilities (e.g., the attacker knows all but one training example and aims to reconstruct the remaining one). In the context of generative models, the attacks can be made more potent. Prior work demonstrates the ability to extract high-fidelity text or images by prompting a trained language model or diffusion model. These findings emphasize the potential security and privacy risks associated with the memorization of training data in generative models.

Data extraction attacks could become increasingly powerful when side-channel leakages are present. For instance, it has been demonstrated that private image and text data can be extracted during Federated Learning, assuming that the attacker has white-box access to the model being trained and the exchanged gradients. This further highlights the importance of addressing potential security vulnerabilities of data leakage in distributed learning environments.

3 Interpretation of attack and auditing results

As outlined above, attacks provide complementary metrics to evaluate the privacy of an algorithm—in addition to the $\varepsilon$ parameter obtained when analyzing the DP guarantees provided by the algorithm. However, the success (or lack thereof) of an attack is not a direct substitution for criterion based on a value of $\varepsilon$ for a DP bound. Therefore, attacks provide lower bounds on privacy: their failure is a necessary condition to obtain a privacy-preserving algorithm. Yet, the failure of attacks is not a sufficient condition: a novel attack may, later on, be proposed and result in a higher lower bound, demonstrating that the privacy leakage of the algorithm had previously been underestimated. Instead, the bound provided by a DP analysis provides an upper bound: the value of $\varepsilon$ being sufficiently close to 0 provides a sufficient condition for the algorithm to preserve privacy. That said, attacks do provide insights into the sources of leakage in a system that handles data and can inform the calibration of mechanisms that provide DP guarantees—with the caveats described above.

Guaranteeing DP for any mechanism requires i) bounding the sensitivity of the mechanism, and ii) incorporating calibrated randomness into it. There is a line of works showing the mitigation (to a large extent) of state-of-the-art attacks by just using the sensitivity-bounding step. While this by itself does not provide any DP, one can then start injecting randomness such that the mechanism can provide “weak” DP but is resistant to the best-known auditing techniques (e.g., ). There is one major advantage of sensitivity-bounded approaches over ad-hoc measures for privacy protection: they give a clear path towards achieving a DP guarantee using amenable randomization procedures, which can then provide provable protection against membership inference attacks.

There are also approaches that attempt to find an intermediate point between the evaluation of a particular attack strategy and solely relying on the DP bound. Recently, a line of work has been proposed to derive bounds on the success of a particular class of attacks—regardless of the particular attack strategy employed. For instance, if we want to reason about membership inference adversaries without having to instantiate a particular attack, we could derive a bound on the success of any membership inference adversary . These bounds can be derived from DP bounds themselves . Bounds on classes of attacks provide a way to interpolate between the DP analysis and auditing through concrete attack instantiations. In particular, this approach does not introduce an arms race as new attack strategies are developed.

The literature on inference attacks has proposed several attacks which are not directly related to differential privacy. This includes property inference attacks, where an adversary seeks to learn statistical information about a model’s dataset , and attribute inference, where an adversary attempts to use a model to learn a sensitive feature from a nonsensitive feature . Differential privacy is not designed to defend against either of these attacks, and, in the case of attribute inference, there has been debate as to the severity of the privacy violation in an attribute inference attack . Care should be taken to not conflate success of these attacks with a violation of the privacy guarantees provided by differential privacy. Future research may also investigate user perceptions of these different privacy violations and techniques to mitigate them.

4 Benchmarking Datasets

While performing various attack algorithms, the community has realized that many datasets that are commonly used as benchmarking datasets for ML task performance are not necessarily relevant to the privacy problem. For example, privacy methods and attacks performed on typical ML datasets, such as CIFAR-10, may be difficult to generalize to other domains, such as tabular data. Hence there is a need to identify and surface more accessible datasets that can enable us to compare different kinds of attacks or auditing exercises, facilitating an understanding of improved attacks or privacy-preserving methods, ideally with diverse sources to represent a broader set of applications.

There exists tabular data like the US Censushttps://github.com/zykls/folktables, Locationshttps://github.com/jinyuan-jia/MemGuard/tree/master/data/location, Purchase-100https://codalab.lisn.upsaclay.fr/competitions/8553, and Texas hospitalshttps://github.com/bargavj/Texas-100X. These are public datasets that contain private features, making them appropriate for testing risk of releasing models trained on similar sensitive datasets. For specialized domains, there are MIMIC datasethttps://physionet.org/content/mimiciv/2.2/, which is a critical care dataset containing a large number of patients commonly used in health research, epidemiology, and ML. Mobility data is also highly sensitive, and there exist public mobility datasets such as GeoLifehttps://www.microsoft.com/en-us/research/publication/geolife-gps-trajectory-dataset-user-guide/ from Microsoft Research Asia which covers trajectories of 178 different users. However, there does not exist a large scale public mobility dataset.

We call for the community to contribute more towards these datasets for both ML and non-ML problems, helping us to establish a common ground to quickly improve both DP algorithms and attacks.

5 Open challenges and research directions

Although privacy attacks and auditing have gained increasing interest from academia and industry, due to their more intuitive interpretation and practical benefits, it is still a relatively new domain and there are many important open challenges that need more research.

While privacy attacks and audits have the possibility of offering rich information about the privacy of the system, a large-scale deployment requires more research. As discussed above in Section 4.3, we believe that auditing through privacy attacks is a good complement to DP guarantees but does not offer a complete replacement. This leaves us with a number of open questions: can we rely on the outputs of current attacks to make important decisions, such as deciding not to require DP for a certain component? Can we leverage the practical attacks to decide on an “acceptable” privacy unit or privacy parameter values? If yes, what are the suitable metrics and thresholds? If not, how could we develop attacks that provide some solid basis for such decisions? Some attempts were discussed in to derive an empirical epsilon value as an outcome of the auditing results. With these kinds of metrics, the question remains on whether we should leverage them and how to leverage them properly for decision making.

Moreover, in real-life applications, we face more scaling challenges. On one hand, powerful state-of-art attacking algorithms are often too expensive in computation cost, thus difficult to deploy to a system with high requirements for freshness and latency. At the same time, if we would like to audit or attack systems or ML models that are processing a large amount of data (e.g., high capacity models trained on gigantic datasets), we may only afford to do it once or, for its equivalence, with only a subset of data, which then undermines the strength of the auditing results, since as we have discussed attack results only represent lower bounds.

There are several promising directions to pursue here. Is there a possibility of understanding models that are trained on incremental data to identify subsets of future training data or specific types of leakage that we can focus on rather than looking at all possible leakage profiles? Are there potential approximations to robust attacks that we think meaningfully work for models trained on “reasonable” inputs that we can reuse across model training and re-calibrate with heavier attacks periodically? Some practical approaches entail deploying simpler, less computationally heavy attacks which may not be the strongest while calibrating them using SOTA attacks in a less frequent way. This is not a perfect solution, and if the goal is to increase the adoption of attacks as auditing measures, we should continue to research more effective attacks with cost constraints in mind.

5.2 Auditing ML pipelines

For ML pipelines specifically, an additional difficulty with auditing is that auditing supposes that the inputs and outputs of the system accessible to the adversary are clearly identified. This may not always be the case in ML pipelines. For example,

Continual learning and recurrent training: In typical production settings, several ML models are trained and released daily or more frequently. These are often trained in an incremental fashion we are constantly updating models with new data (as it is collected). It can also be the case when we need to delete data from previously trained models (as may be required for privacy-related reasons such as “the right to be forgotten” as required by GDPR and discussed in the literature on machine unlearning ). This has been shown to increase privacy leakage compared to a single model release .

Hyperparameter tuning: is a common component of machine learning pipelines, which as we discussed previously, has the potential to increase privacy leakage because of repeated accesses to the same training data required to compare the model’s performance for different candidate values of the hyperparameters that need to be tuned. Some techniques have been designed to mitigate this issue .

These different scenarios can result in the adversary having access to intermediate states of the model, or to periodic releases of the model trained on related datasets. While differential privacy’s postprocessing and composition properties make it particularly attractive for use in such systems, auditing generally does not benefit from the same properties. Changes in the adversary’s access to the system may thus invalidate the results of prior audits. Thus research needs to answer a number of questions such as (1) how leakage measured by audits of individual components of a broader ML pipeline need to be composed, (2) how frequently these audits need to be repeated, (3) do we need to develop attacks that specifically target more complex releases, such as continuous/periodic releases of models/statistics, or releases of complex ML bundles that include multiple versions of a model and summary statistics computed on the same dataset.

Take the example of unlearning mentioned above. Recent research shows how the vulnerability of a particular data point to membership inference is relative to other points contained in the training set of the model . This means that unlearning some of the training points can alter a particular data point’s vulnerability to membership inference attacks. Put another way, audits based on membership inference need to be repeated regularly if the model’s training set is updated.

While the prior were examples of pipelines which can make privacy worse, there are also situations where limited access to the system may be conjectured to improve privacy leakage. Consider two examples of limited information access:

“Label only access” restricts an adversary to only having the label outputs of a query to the target model. This is common in many deployments; in spam detection, for example, an adversary can only see whether a spam message is classified as spam or not, and cannot see the spam classifier’s predicted probability. Given that many privacy attacks rely on access to the probabilities returned by a model, it is natural to think that privacy attacks can be made impossible through this obscurity. However, it is now known that such restrictions do not prevent leakage: show that attacks are possible in this threat model, by querying in the neighborhood of a target example. This is evidence that such obscurity claims should be justified as well with adaptive attacks.

“Final step access” is where a model is produced with a chain of multiple algorithms, and an adversary can only access the output of the final step. This is a common assumption, for example, in nonconvex model training with differential privacy, where differential privacy guarantees are proven for an adversary with access to all iterations of training. It is known that an adversary with all iterates of training is stronger than an adversary with access to only the last iterate, when models are convex . However, there is currently only empirical evidence that this relaxed threat model improves privacy in the more general nonconvex setting, which may be overturned by stronger attacks.

5.3 Auditing Tools beyond attacks

Attacks and auditing discussed thus far assume fairly comprehensive access to the model and it is not clear if such audits can be extended to settings where the auditor has more limited access to the ML model. Take the example of a non-profit organization, how can they audit the claims of privacy made for a model without direct access to the model? Taking things a step further, how can the output of such audits be used as the input to decisions made by policymakers? The end goal of such a process would be to decide whether an observed privacy loss/leakage is acceptable. That is, gather (1) evidence to decide whether or not it is safe to release a model; (2) evidence to show if an adjustment to improve privacy reduced leakage and by how much; (3) to produce a report for a policy committee to make decisions on privacy parameters, privacy-utility tradeoffs. If such decisions rely on the result of auditing through attacks against the ML model, how can we (1) meaningfully report the outcome, and (2) increase understanding of what evidence from one attack means about other attacks?

Given the goals of auditing we stated in Section 4.1, it is however clear that attacks are necessary but not sufficient as an auditing tool. For example, attacks do not always help find bugs in code-implementing algorithms—even when these algorithms come with a privacy proof. What can we do to audit model internals, rather than just attempting attacks? Are there ways to quantify expected leakage by training models on different data and comparing them? It is clear that research needs to develop techniques that audit implementations and data, rather than just models. Similarly, it would be useful to develop auditing tools that provide explanations as to how privacy is protected by the corresponding system–rather than simply provide a quantitative assessment of privacy.

Beyond DP: Modeling Privacy for Real-world Scenarios

We have so far focused on the importance of preserving user privacy by applying differential privacy to statistical data analyses and machine learning applications. As discussed in prior sections, differential privacy sets a formal limit on any user’s influence on the outcome of a computation.

In an ideal world, each actor in the system would learn nothing more than the differentially private output of the computation needed to play their role. For example, if an analyst only needs to determine whether a particular quality metric exceeds a desired threshold in order to authorize deploying the model to end users, then in an idealized world, only a differentially private version of that bit of information would be available to the analyst; such an analyst would need access to neither the training data nor the model parameters, for instance. Similarly, end users enjoying the user experiences powered by the trained model might only require differentially private predictions from the model and nothing else. More importantly, in such a world, each user contributing data would know how their data is being used, what it is being used for, and what level of DP is being enforced, and they would have the ability to verify or falsify these claims.

However, it is clear that DP alone is not enough to achieve the above idealized world. Indeed, DP does not describe where the user data is stored, how it is accessed, or who has access to it. Further, DP does not specify how the privacy guarantees are communicated with or verified by the user. In fact, DP serves a particular privacy principle, the data anonymization principleThe term data anonymization is used loosely here, in order to be consistent with colloquial usage. The term anonymization does not have any specific technical meaning associated to it.,but as the above idealized scenario indicates, there are other important privacy principles including transparency and consent into how data is used, or data minimization approaches that appropriately restrict access to raw data and intermediate computations . In this section, we will overview these privacy principles and describe how they combine with DP to provide “Privacy in Depth” guarantees for real-world scenarios.

We start by discussing a privacy principle focused on data minimization: collecting whatever is necessary for a specific computation (focused collection), processing a user’s data as early as possible (early aggregation), limiting access to data at all stages (access controls), and discarding both collected and processed data as soon as possible (minimal retention). That is, data minimization implies restricting access to all data to the smallest set of people possible, often accomplished via security mechanisms, such as encryption at rest and on the wire, access-control lists, and more nascent technologies such as secure multiparty computation and trusted execution environments, to be discussed later.

These processes are perhaps best embodied via federated learning and analytics . Critically, data collection and aggregation are inseparable in the federated approach—purpose-specific transformations of client data are collected for immediate aggregation, with analysts having no access to per-user messages. FL can be combined with DP and empirical privacy auditing, treated in detail in Section 4, to ensure released aggregates are sufficiently anonymous.

2 Communicating the guarantees of differential privacy

DP has seen wide deployment across industry and government organizations as the gold standard of privacy-preserving data analysis, but its mathematical precision makes its privacy guarantees difficult to understand. Simply describing it as “the gold standard” instills confidence but does not provide information about the nature of the privacy guarantees. On the other hand, describing it as “a bound on the worst-case ratio of the probability of a particular output of a randomized algorithm across two neighboring database” is equally meaningless to those unfamiliar with the definition or without a mathematical background. How, then, should DP be explained to end-users and other stakeholders who may not already be experts in DP? How can these people be empowered to make informed choices about the data protections afforded to their data and the data of others, in relation to the use of DP systems?

The challenges of explaining the guarantees of DP without using mathematics is especially salient when communicating to end-users, who are not assumed to have any mathematical background and require extremely brief descriptions, such as those on a billboard or an in-browser pop-up. Additionally, the protections provided by differential privacy are not absolute and require contextualization to understand their exact meaning. For example, the $\varepsilon$ parameter quantifies privacy loss in the worst-case over all pairs of neighboring databases, but does not provide instance-specific guarantees that match the decisions faced by users in practice: e.g., when a user knows the realization of her own data and must decide whether or not to participate in a DP system. For complex data such as mobility trajectory, or health data, “what” is being protected or the “neighboring pair” that defines the indistinguishability can be also nuanced. E.g., it may be one location coordinate at a time, one entire trajectory, or a spatiotemporal activity of a user (stay at a place, or move from home to office).

The challenge of effectively communicating the nuanced technical guarantees of differential privacy to the individuals whose data will be used in DP systems, is a subject of ongoing work and will be a critical challenge to solve in the future of DP systems deployed in practice.

Recent work of showed through a series of user studies that end-users of DP systems care about the kinds of information leaks against which differential privacy protects and are more willing to share their private information when the risks of these leaks are less likely to happen. However, also showed that current in-the-wild descriptions of DP let users to have haphazard and incorrect privacy expectations about protections from these leaks. These incorrect expectations persisted when comparing against the ground truth protections in both the local and central models of DP.

Since most existing in-the-wild descriptions of DP can apply equally well to both the local and central models – e.g., describing DP as “the gold standard” or saying that it “injects statistical noise” – it makes sense that end-users would not be able to distinguish between the two models based only on these descriptions. Future work is needed to develop new DP descriptions that help end-users accurately distinguish between the privacy guarantees offered by these different models of DP, such as that proposed in .

Non-technical methods for explaining the $\varepsilon$ value are critical for meaningful explanations of the privacy guarantees, since ranging $\varepsilon$ from 0 to $\infty$ can respectively range the privacy guarantees from “perfect privacy” to “no privacy”. Simply stating that a system satisfies DP without specifying the $\varepsilon$ value used provides no meaningful information to end-users. However, simply informing end-users of the $\varepsilon$ value without providing guidance on the meaning or interpretation of this parameter is equally meaningless. End-users typically do not reason about privacy in the way quantified by $\varepsilon$, and people are known to struggle at reasoning about risks from low-probability events .

Recent work of developed and evaluated methods for explaining the probabilistic privacy guarantees to end-users: two that communicate the relative odds of various outcomes with and without the user’s data, and one offering concrete examples of outputs sampled from DP mechanisms with the appropriate $\varepsilon$. Odds-based explanation methods were found to be more effective than output-based methods, as well as existing DP explanation methods that do not explicitly describe $\varepsilon$.

This initial work suggests a promising path for future explanatory tools. Future work should extend this line of inquiry to both develop improved methods for communicating the privacy guarantees, as well as methods for evaluating efficacy of new methods. Equipped with effective explanations of DP that enable end-users to understand the privacy guarantees they are being offered through DP systems, researchers can also elicit their preferences over the $\varepsilon$ values in different contexts of data use to understand the trade-off faced by consumers between privacy (as measured by $\varepsilon$), accurate analysis of their data, and utility (as measured by money). Such understanding would be extremely valuable to DP practitioners, who must tune the $\varepsilon$ to balance privacy needs of users with accuracy needs of analysis, and can possibly compensate end-users for their privacy loss, either directly with payments or indirectly through improved services.

Beyond the $\varepsilon$ value used in a DP system, other details of the implementation affect the privacy guarantees provided to users, such as the $\delta$ value, the algorithm used, how the privacy budget is composed across multiple accesses of the user’s data. For example, one call to the Randomized Response Mechanism with $\varepsilon=10$ may be different in the eyes of an end-user from 10 calls to the Gaussian Mechanism, each with $\varepsilon=1$.

These description tools may draw influence from existing work on privacy nutrition labels (e.g., ) that will highlight salient privacy features of a technical system. In the context of DP, this may include general privacy properties of DP, as well as details of a specific DP implementation, such as local/central privacy, the DP algorithm and its privacy parameter $(\varepsilon,\delta)$, and information about privacy budget composition across multiple queries.

Disclosing the $\varepsilon$ value and other relevant hyperparameters of their DP system will allow companies and other organizations to improve transparency to end-users, such as the “Epsilon registry” proposed in ; such disclosures will only be meaningful when end-users are also given means of interpreting the parameters and their impact on real-world privacy guarantees. Beyond simply informing end-users of the privacy they will receive, organizations should provide end-users with meaningful choices so that users can have more control over their own data. These user-centric controls may be related to DP – such as choosing the $\varepsilon$ value that their data will receive, or choosing whether their data are collected under the local or central model – or beyond the scope of DP – such as opting out of data collection without opting out of the service, or invoking the GDPR’s “right to be forgotten”.

2.2 Communication to other stakeholders

In addition to communicating to end-users, there are many other stakeholders involved in the implementation of differential privacy in practice. These other stakeholders represent the metaphorical DP supply chain, including engineers who must implement and test DP systems, data curators who must manage access to databases through DP systems, executives who must decide whether DP systems should be used in their organizations, lawyers who must determine which DP systems are compliant with laws and regulations, and policymakers who have the power to enact new regulations surrounding the use of DP systems. While each of these stakeholders has their own relevant areas of expertise, they are not assumed to be experts and differential privacy, and will need explanatory tools to aid them in making informed decisions surrounding the use of differential privacy. Suggestions for future explanatory methods tailored to each audience are briefly described below.

Engineers – and their managers – must implement and test DP algorithms for the private analysis needs of their organizations and teams. This involves both ensuring that the algorithms and their privacy guarantees are correct, as well as making more nuanced decisions, such as managing privacy composition across multiple queries and choosing the per-query $\varepsilon$ based on use-case specific privacy and accuracy needs. These engineers are expected to have a high level of technical knowledge, coming both from formal academic training and on-the-job experience. However, unless they have previously worked on privacy products, most of these engineering teams are unfamiliar with both verifying correctness of DP guarantees and the privacy-accuracy consequences of various parameter choices.

One partial solution is developing open source DP libraries and repositories that are vetted by experts, such as . While these libraries will not be able to provide code for every possible DP algorithm, they will provide a foundation of verified-correct DP algorithms that can be used as building block in larger, more complex DP systems. Additionally, the DP community should develop a visual analysis tool that enables the engineer to visualize the privacy and accuracy guarantees that result from different $\varepsilon$ values. A partial version of this tool already exists in , but adding additional features, such as different types of queries with different sensitivities, composition across multiple queries, and allowing the engineer to specify their own data format (such as number of features and range of data values) will bring the visualization closer to the needs of practice.

Data curators are charged with facilitating access to datasets when such data are needed, and also governing appropriate use of the datasets. These maybe internal-facing curators, such as committee inside an organization allocating access to data for other teams within the organization, or external-facing curators, such as the U.S. Census Bureau’s Federal Statistical Research Data Centers , which provide regulated access to confidential data collected by federal statistical agencies. Data curators are accustomed to determining when access to protected dataset should be allowed or not, which typically include administrative application, review, and approval processes. However, recent work showed the novel challenges arise when data curators integrate differential privacy into their process.

For example, when engineers or data analysts are interested in identifying a dataset that is useful for their analysis task, the curator may wish to provide a summary of the metadata associated with each potential dataset. Since these metadata maybe provided many times to many different analysts, several questions arise: what metadata should be provided and at what level of privacy in order to provide useful information about the applicability of the dataset to the specific task, while not exhausting the privacy budget. Additionally, as multiple analysts access the same dataset, the curator may be required to manage the overall privacy budget of the dataset, and choose the privacy budget allocated to each analyst. These privacy budgets could be uniform to reduce the curator’s overhead, or they could vary based on the relative importance of the analysis task, or based on the level of trust (e.g., higher levels of oversight may enable larger privacy budgets). For these and other real-world challenges faced by data curators adopting DP into their data management process, the DP community can provide explanatory methods and best practice documents as guidance for data curators.

Even when engineering and research teams are convinced of the virtues of DP, high-level executives are the ones who are empowered to decide whether of not DP systems should be used in their organizations. The incentives, goals, and perspective of these executives may differ substantially from those of their more technical employees. Executives are not typically focused on adopting cutting-edge privacy tools like DP, but instead on improving performance of their organization along key corporate metrics, such as revenue, market share, or consumer satisfaction.

For this audience, the language of privacy-accuracy tradeoff – which is commonly used in technical descriptions of DP – may be unappealing, as it implies that introducing DP necessarily harms accuracy and potentially key performance metrics that rely on data. Instead, one can expect a more amenable response from language that emphasizes the benefits of DP, such as improved trust from users , improved quality of data collected from users , and protection against practical attacks (as discussed in Section 4 and data leaks . Additionally, executives will be more likely to choose to adopt novel privacy tools if there is clear demand from the organization’s users, and if it is clear that doing so will be compliant with current and future privacy laws. Aside from a new notable exceptions, privacy is not a dimension along which companies compete. Increased pressure from users, perhaps as a result of the steps described in Section 5.2.1, may change this. Steps for improving the connection between DP tools and privacy laws are discussed next.

Before an organization can adopt DP, corporate and privacy lawyers are left with the difficult task of determining whether a particular DP system – or perhaps DP in general – is compliant with all privacy laws. Unfortunately, current privacy laws do not provide explicit guidance on this question, so legal scholarship is required to interpret the language of each relevant privacy law. This introduces several challenges, including: (1) the mathematically nuanced language of DP is very different from the language of the law, (2) the continuous $\varepsilon$ privacy parameter must be reconciled with binary compliance requirements of the law, and (3) the legal landscape of privacy is a patchwork of geographic- and domain-specific regulations, rather than a single consistent privacy law.

Some progress has been made on the first challenge by , which provides a minimally-technical survey of DP basics in language that is familiar to legal scholars. Other partial progress has been made in clearly articulating that DP satisfies the privacy requirements of specific privacy laws and that it provides protections commonly required in privacy laws . Much more work is needed in this direction to provide comprehensive and easily available answers to lawyers for the questions they face surrounding the use of DP in real-world systems.

If current privacy laws are determined to be unclear or underspecified – or alternatively, as new technological advances are made in the field of privacy – then regulators and policymakers are charged with developing new regulations to guide and govern the use of DP in practice. One major challenge is that there is not consistent guidance from the DP community on best practices for the use of DP. The most notable issue is the question of appropriate choice of $\varepsilon$ (see Section 5.2.1 for more discussion). It is widely agreed that the choice of $\varepsilon$ should vary with the context of use, and should balance privacy and accuracy needs of the application domain. However, there is no concrete legal or numerical guidance on how these considerations should translate into a choice of appropriate $\varepsilon$ value .

The DP community can contribute to improved technical guidance for policymakers by engaging more directly with the policy and regulatory communities. This may include work that is typically considered to be outside the workload of an academic or industry researcher, such as writing white papers or responding to government requests for public comments, Advance Notice of Proposed Rulemaking, or Requests for Information. This may also include developing educational programs targeted specifically at regulators, to equip them with the necessary knowledge to make policy decisions that are informed and consistent with the best technical practices.

Acknowledgements

List of workshop participants, beyond the ones mentioned on the title page: Borja Balle, Will Bullock, Nicholas Carlini, Graham Cormode, Kamalika Chaudhuri, Seyi Feyisetan, Miguel Guevara, Monika Henzinger, James Honaker, Huseyin A. Inan, Krishnaram Kenthapadi, Aleksandra Korolova, Sara Krehbiel, Janardhan Kulkarni, Ravi Kumar, Mathias Lecuyer, Chen-Kuei Lee, Brendan McMahan, Gerome Miklau, Ilya Mironov, Milad Nasr, John Nguyen, Oana Niculaescu, Ananth Raghunathan, Aaron Roth, Mikhail Rudoy, Michael Shoemate, Adam Smith, Thomas Steinke, Mukund Sundararajan, Om Thakkar, Florian Tramèr, Praneeth Vepakomma, Steven Wu.

References