Near Instance-Optimality in Differential Privacy

Hilal Asi, John C. Duchi

This paper, "Near Instance-Optimality in Differential Privacy" by Hilal Asi and John C. Duchi, represents a significant shift in how we think about the "cost" of privacy. Traditionally, Differential Privacy (DP) focuses on worst-case scenarios, but this work proves we can do much better by looking at the specific data at hand.

TL;DR

The authors move beyond worst-case "minimax" analysis to define what it means for a private algorithm to be optimal for a specific dataset. They introduce the "Inverse Sensitivity Mechanism," a novel approach that adapts to local data properties and frequently outperforms standard techniques like smooth sensitivity by orders of magnitude.

What Problem Does This Paper Address?

In Differential Privacy, we usually add noise to a function $f(x)$ to hide the presence of any single individual. The standard "Laplace Mechanism" adds noise proportional to global sensitivity—the maximum possible change in $f$ across any two neighboring datasets in the entire universe of possibilities.

This is often incredibly conservative. If your specific dataset is "stable" (meaning small changes to the data don't change the output much), you shouldn't need as much noise. While previous frameworks like "smooth sensitivity" tried to address this, they are often complex, provide weaker $(\epsilon, \delta)$-privacy, and can still be unnecessarily noisy. The authors ask: What is the fundamental limit of privacy for a specific instance $x$, and can we build a mechanism that reaches it?

Methods

The authors bridge the gap between classical statistics and privacy theory using three main pillars:

  1. New Optimality Definitions: They define "local minimax risk" (how hard it is to estimate $f(x)$ against the toughest nearby alternative) and an analogue to the Cramér-Rao bound for unbiased private mechanisms.
  2. The Local Modulus of Continuity: They prove that the fundamental quantity governing the privacy-utility trade-off is $\omega_f(x; k)$—the maximum change in the function $f$ within a Hamming distance $k$ of the dataset $x$.
  3. The Inverse Sensitivity Mechanism: Instead of measuring how much the function changes when the data changes, this mechanism "inverts" the problem. It calculates the length $len_f(x; t)$: the minimum number of individuals you must change in $x$ to make the function output a target value $t$.
  4. For discrete outputs, they use this length as a score in an exponential mechanism.
  5. For continuous outputs, they develop a "smoothed" version ($M_{cont}$) and provide a Metropolis-Hastings sampling scheme to make it practical.

Datasets

The authors evaluated their approach on two main fronts:

  • UC Salary Dataset: A real-world dataset containing the salaries of University of California employees, used to test private median estimation.
  • Synthetic Robust Regression: A generated dataset where a linear model is subjected to uniform noise, used to compare the inverse sensitivity mechanism against private Stochastic Gradient Descent (SGD).

Key Insights and Ideas

  • Privacy is Local: The difficulty of releasing a private value isn't a property of the function alone, but of the function at a specific point. The local modulus of continuity is the "gold standard" for determining how much noise is actually necessary.
  • Super-efficiency is Impossible: You cannot design a mechanism that is "too good" at one specific dataset without it becoming disastrously bad at a neighboring one. This mathematical reality allows the authors to prove their lower bounds are "tight."
  • Sample-Monotone Functions: The authors identify a broad class of functions (including most continuous functions on convex domains, like means and medians) where their mechanism is $O(1)$-optimal. This means it achieves the best possible error up to a small constant factor.
  • Uniform Superiority: For these sample-monotone functions, the inverse sensitivity mechanism is proven to always perform as well as or better than the smooth Laplace mechanism across all possible datasets.

Key Results

  • Median Estimation: On the UC Salary dataset, the inverse sensitivity mechanism achieved a 2 to 3 order of magnitude improvement in error compared to the smooth Laplace mechanism.
  • Robust Regression: The mechanism significantly outperformed state-of-the-art private SGD (using moments accounting). In high-privacy regimes (small $\epsilon$), the gap was several orders of magnitude.
  • Asymptotic Convergence: For median estimation, the mechanism achieves the optimal statistical convergence rate of $1/\sqrt{n}$ whenever the privacy parameter $\epsilon \gg \log n / \sqrt{n}$, whereas smooth sensitivity requires a much larger $\epsilon \gg n^{-1/4}$.

Limitations and Future Work

  • Computational Overhead: While the discrete version is simple, the continuous version requires sampling from complex distributions. The authors suggest Metropolis-Hastings, but ensuring this "mixes" quickly requires the loss function to have well-behaved gradients and Hessians.
  • Smoothing Parameter: The continuous mechanism relies on a smoothing parameter $\rho$. While the authors provide a "rule of thumb" ($\rho = 1/poly(n)$), choosing the optimal $\rho$ for a specific application remains an open practical challenge.
  • Monotonicity: The most powerful optimality results depend on the function being "sample-monotone." While many statistical estimators fit this, complex black-box models might not, potentially limiting the theory's application to deep learning.

Summary updated

Abstract

We develop two notions of instance optimality in differential privacy, inspired by classical statistical theory: one by defining a local minimax risk and the other by considering unbiased mechanisms and analogizing the Cramer-Rao bound, and we show that the local modulus of continuity of the estimand of interest completely determines these quantities. We also develop a complementary collection mechanisms, which we term the inverse sensitivity mechanisms, which are instance optimal (or nearly instance optimal) for a large class of estimands. Moreover, these mechanisms uniformly outperform the smooth sensitivity framework on each instance for several function classes of interest, including real-valued continuous functions. We carefully present two instantiations of the mechanisms for median and robust regression estimation with corresponding experiments.
BibTeX
@misc{asi2020near,
  author = {Hilal Asi and John C. Duchi},
  title = {{Near Instance-Optimality in Differential Privacy}},
  year = {2020},
  eprint = {2005.10630},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2005.10630},
}
Figure