Authors: Hilal Asi and John C. Duchi (Stanford University)
Presented at: NeurIPS 2020
Introduction
A fundamental tension in Differential Privacy (DP) lies in providing robust privacy guarantees without destroying the utility of the underlying data. Traditional DP frameworks often rely on worst-case scenarios, applying a "one-size-fits-all" noise mechanism that can severely degrade performance on "easier," well-behaved datasets. This paper tackles this inefficiency by developing new, computationally efficient approximations for the inverse sensitivity mechanism. By moving beyond worst-case (minimax) analysis, the authors enable differentially private algorithms to adapt to the specific hardness of a given data instance, achieving near-optimal rates for high-dimensional problems like Principal Component Analysis (PCA) and linear regression.
The Limits of Global Sensitivity
Standard DP approaches typically add noise to a query result based on Global Sensitivity—the maximum possible change in the output if a single individual's data is altered. However, global sensitivity is inherently pessimistic. For many real-world datasets, the actual Local Sensitivity (how much the output changes given the specific dataset at hand) is significantly lower.
While alternative frameworks like smooth sensitivity and propose-test-release were designed to exploit local sensitivity, they come with notable drawbacks. They frequently require adding noise from heavy-tailed distributions (such as the Cauchy distribution), which results in poor high-probability bounds. Furthermore, they are often computationally intractable for complex, vector-valued functions. This paper bridges the gap between theoretical "instance-optimality"—being as accurate as possible for every specific dataset—and practical, efficient implementation in high dimensions.
Approximating Inverse Sensitivity
To overcome these limitations, the authors build upon the Inverse Sensitivity Mechanism. Rather than adding noise to a pre-computed answer, this mechanism defines a probability distribution over the output space where the density is proportional to $e^{-\text{len}(x;t)}$. Here, the "path-length" ($\text{len}$) represents the minimum number of individuals one would have to change in the dataset $x$ to force the function to output $t$.
Because calculating this exact path-length is typically NP-hard, the authors introduce two novel approximation frameworks:
- Local Sensitivity Approximation: This method bounds the path-length using only the local sensitivities at varying distances from the current dataset. The authors provide an efficient sampling algorithm utilizing truncated Gamma distributions.
- Gradient/Hessian-Based Approximation: Designed for optimization problems like Empirical Risk Minimization (ERM), this approach uses Taylor expansions of the loss function. By analyzing the Gradient and Hessian, the algorithm estimates the stability of the optimal solution, allowing it to inject noise precisely calibrated to the geometry of the optimization landscape.
Key Insights and Theoretical Breakthroughs
The paper provides rigorous mathematical proofs and analyzes performance on fundamental statistical models, yielding several critical insights:
- Minimax is Overly Pessimistic: The authors prove that standard minimax lower bounds fail to accurately reflect the limits of privacy for well-behaved data. Their instance-specific mechanisms can significantly outperform these bounds on many practical instances.
- Exponential vs. Heavy Tails: Unlike smooth sensitivity, which relies on heavy-tailed noise, the approximate inverse sensitivity mechanism utilizes noise with exponentially decaying tails. This drastically improves utility, meaning the private answer is far more likely to be tightly clustered around the true answer.
- The Geometry of Privacy: For vector-valued functions, the "hardness" of an instance is intrinsically tied to its modulus of continuity. By understanding the local geometry via the Hessian, high-dimensional vectors can be released with substantially less noise than previously assumed.
Applications and Results
The theoretical frameworks translate into tangible improvements for fundamental machine learning tasks:
- Principal Component Analysis (PCA): The authors introduce a pure $(\epsilon, 0)$-differentially private algorithm for PCA that achieves a sample complexity of $O(d)$. This is a major breakthrough, matching the optimal known rates for PCA and improving upon previous state-of-the-art smooth sensitivity methods that required $O(d^{1.5})$.
- Linear Regression: The Hessian-based mechanism achieves an excess loss that adapts to the eigenvalue decay of the data. On "natural" instances with rapid eigenvalue decay, this method offers up to an $O(d)$ improvement in error over standard private ERM methods.
- Unbounded-Range Mean Estimation: The framework successfully develops private mechanisms for estimating the average of a distribution without a known range.
Limitations and Future Directions
While a significant step forward, the proposed methods have limitations. The Hessian-based approach requires computing and inverting matrices, which can be computationally expensive for extremely high-dimensional feature spaces. Additionally, the gradient-based approximations rely on smoothness assumptions—specifically, that loss functions are twice-differentiable and possess certain Lipschitz properties—making them difficult to apply directly to non-smooth models like ReLU neural networks. Finally, the paper focuses primarily on "pure" $\epsilon$-DP; extending these instance-optimal concepts to approximate $(\epsilon, \delta)$-DP (or Rényi DP) could potentially yield even tighter utility bounds in future research.
Summary updated