Differential privacy (DP) is often viewed as a "big data" tool: to hide an individual's contribution, you typically need a massive crowd so that the noise added for privacy doesn't drown out the signal. However, recent research has shown that the "privacy tax" is not just a function of dataset size, but of sensitivity. If a single outlier can wildly swing your result, you must add massive noise to protect that individual.
By framing DP through the lens of Robust Statistics, researchers have found that we can achieve high-utility privacy even on small or messy datasets. The core intuition is simple: an algorithm that is naturally resistant to outliers is inherently easier to privatize.
The Sensitivity-Privacy Link
The fundamental challenge of DP is that the amount of noise required is proportional to the global sensitivity of the function—the maximum possible change one person can cause. As Kamalika Chaudhuri and Daniel Hsu established in Convergence Rates for Differentially Private Statistical Estimation, the accuracy of a private estimator is strictly limited by its "Gross Error Sensitivity."
Standard tools like the arithmetic mean or Ordinary Least Squares (OLS) regression have high sensitivity; a single point at infinity can move the average to infinity. To make these private, you must add enough noise to cover that worst-case scenario, which often destroys the utility of the data.
Trading Means for Medians
To solve this, researchers are replacing sensitive "averaging" mechanisms with robust alternatives. In Differentially Private Simple Linear Regression, Audra McMillan, Adam Smith, and colleagues demonstrate that for small datasets, the Theil-Sen estimator—which uses the median of slopes between pairs of points—vastly outperforms OLS. Because the median is inherently robust to outliers, the "sensitivity" of the operation is lower, allowing for much less additive noise.
Similarly, Mark Bun and Thomas Steinke show in Average-Case Averages that using a trimmed mean (discarding the largest and smallest values) allows for "smooth sensitivity." This approach scales noise to the actual data distribution rather than a theoretical worst-case, making private mean estimation far more precise.
Privacy in Geometry and Iteration
This principle extends beyond simple statistics into complex optimization and geometry:
- Clustering: In problems like the Minimum Enclosing Ball, a single outlier can double the radius of a cluster. Kobbi Nissim and Uri Stemmer developed algorithms that use Locality Sensitive Hashing to filter data, creating a robust "bounding volume" that doesn't overreact to fringe points Clustering Algorithms for the Centralized and Local Models.
- High-Dimensional Learning: For the Expectation-Maximization (EM) algorithm, Linjun Zhang and Zhe Zhang utilize "hard-thresholding" to bound the influence of any single gradient update, ensuring that outliers cannot hijack the iterative learning process High-Dimensional Differentially-Private EM Algorithm.
Summary of Intuition
If an algorithm is robust, it doesn't care much about any single data point. If it doesn't care about any single data point, it is already "mostly" private. By choosing estimators that ignore outliers, we reduce the sensitivity of our queries, which in turn reduces the amount of noise we must inject to satisfy the requirements of Differential Privacy.