Data Privacy: Frontiers and Barriers of Differential Privacy

Local Differential Privacy (LDP) offers strong privacy guarantees without requiring users to trust external parties. However, LDP applies uniform protection to all data features, including less sensitive ones, which degrades performance of downstream tasks. To overcome this limitation, we propose a Bayesian framework, Bayesian Coordinate Differential Privacy (BCDP), that enables feature-specific privacy quantification. This more nuanced approach complements LDP by adjusting privacy protection according to the sensitivity of each feature, enabling improved performance of downstream tasks without compromising privacy. We characterize the properties of BCDP and articulate its connections with standard non-Bayesian privacy frameworks. We further apply our BCDP framework to the problems of private mean estimation and ordinary least-squares regression. The BCDP-based approach obtains improved accuracy compared to a purely LDP-based approach, without compromising on privacy. 

Composition is a key desiderata for a differential privacy (DP) flavor because it ensures a controlled degradation of the total privacy loss as additional statistics are released. However, ever since Pufferfish DP flavors were first introduced in 2012 it has remained an open problem whether these flavors – which take a Bayesian viewpoint by incorporating into DP the attacker's uncertainty in the confidential data – satisfy composition. In this work, we resolve this question by proving that a Pufferfish flavor satisfies composition if and only if it is equivalent to a pure ε-DP flavor. Therefore, the generalization of DP to Pufferfish privacy is incompatible with the desiderata of composition. Furthermore, we determine that a Pufferfish mechanism composes with itself if and only if it satisfies pure ε-DP – i.e. if and only if it does not make use of the attacker's uncertainty in the data generation mechanism. This result establishes that any class of composable mechanisms which satisfy Pufferfish – such as those found in existing literature – in fact satisfy the stronger condition of pure ε-DP. In intuitive terms, we show that a composable mechanism cannot reuse the "noise" provided by the attacker's Bayesian model of the confidential data: only fresh noise counts when it comes to composition.  

Mean estimation is a fundamental task in statistics and a focus within differentially private statistical estimation. While univariate methods based on the Gaussian mechanism are widely used in practice, more advanced techniques such as the exponential mechanism over quantiles offer robustness in the strong contamination model and improved performance, especially for small sample sizes. Tukey depth mechanisms carry these advantages to multivariate data, providing similar strong theoretical guarantees. However, practical implementations fall behind these theoretical developments.
In this talk, I will discuss first steps to bridge this gap by implementing the (Restricted) Tukey Depth Mechanism, a theoretically optimal mean estimator for multivariate Gaussian distributions, yielding improved practical methods for private mean estimation. The implementations enable the use of these mechanisms for small sample sizes or low-dimensional data. Additionally, I will present variants of these mechanisms that use approximate versions of Tukey depth, trading off accuracy for faster computation. We demonstrate their efficiency in practice, showing that they are viable options for modest dimensions. Given their strong accuracy and robustness guarantees, we contend that they are competitive approaches for mean estimation in this regime. Finally, I will discuss future directions for improving the computational efficiency of these algorithms by leveraging fast polytope volume approximation techniques, paving the way for more accurate private mean estimation in higher dimensions, as well as conjectured barriers toward this goal.

This talk is based on joint work with Gavin Brown.