Polynomial Time Algorithms for Private Statistics

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 121 papers25 conceptsfrozen 2026-10-04

In the early days of differential privacy (DP), researchers discovered a frustrating "privacy tax." It wasn't just that adding noise made estimates less accurate; it was that the most accurate private algorithms were often impossible to actually run.

The mathematical "gold standard" for privacy is the Exponential Mechanism. It provides a way to select the best answer from a set of candidates while maintaining strong privacy, but it requires scoring every possible candidate. If you are trying to select the best subset of features in a high-dimensional model, the number of candidates is exponential. As John Duchi, Michael Jordan, and Martin J Wainwright established in Local privacy and statistical minimax rates, there are fundamental limits to how well we can estimate parameters under privacy constraints. However, their work also highlighted a looming shadow: statistical optimality does not guarantee computational efficiency.

A major thrust of recent research is closing this "computational-statistical gap"—finding algorithms that are both statistically optimal and run in polynomial time.

The Pure Privacy Bottleneck

The field distinguishes between pure differential privacy ($\epsilon$-DP) and approximate differential privacy ($(\epsilon, \delta)$-DP). Pure privacy is the stronger, more robust guarantee, but it is notoriously difficult to achieve efficiently.

As Vikrant Singhal points out in A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions, many problems have efficient solutions under approximate privacy but seem to require exponential time under pure privacy. This is because approximate privacy allows for a tiny "failure probability" ($\delta$), which lets researchers use simpler noise-addition techniques like the Gaussian mechanism. Pure privacy requires more complex distributions that are harder to sample from efficiently.

Strategies for Efficiency

To bypass the exponential wall, researchers have developed several key "intuition-building" strategies:

1. Markov Chain Monte Carlo (MCMC) Sampling

Instead of exhaustively searching an exponential space of models, we can treat the Exponential Mechanism as a probability distribution and sample from it. Ambuj Tewari and Saptarshi Roy applied this to model selection in On the Computational Complexity of Private High-dimensional Model Selection via the Exponential Mechanism. By using MCMC, they can find the "needle in the haystack" (the best features) in polynomial time without sacrificing the strong privacy of the Exponential Mechanism.

2. Random Projections and Dimensionality Reduction

High-dimensional data is the enemy of privacy because noise must be added to every dimension, quickly drowning out the signal. Huy Nguyen and Jonathan Ullman addressed this in Efficient Private Algorithms for Learning Halfspaces by using random projections. By squashing high-dimensional data into a lower-dimensional space before processing it, they achieved sample complexities that are independent of the original dimension, effectively beating the "curse of dimensionality."

3. Stability and Convexity

If an algorithm's output is "stable"—meaning a small change in the input data doesn't change the output much—it is naturally easier to make private. Hongjie Chen and colleagues leverage this in Private estimation algorithms for stochastic block models and mixture models. They use the stability of strongly convex optimization to create private versions of complex models like Gaussian Mixture Models (GMMs) that nearly match the performance of non-private versions.

Scaling to Users and Graphs

The push for efficiency also extends to how we define the "unit" of privacy. In User-level Differentially Private Stochastic Convex Optimization, Daogao Liu and Hilal Asi tackle the challenge of protecting entire users rather than single data points. This is computationally harder because a single user's contribution can be much larger than a single record's, requiring more sophisticated, yet still fast, optimization techniques.

Similarly, in graph-based data, Mark Bun and Janardhan Kulkarni showed in Differentially Private Correlation Clustering that we can avoid the $O(n^2)$ error typically associated with private graph algorithms. By "coarsening" clusters and using synthetic graph releases, they bridged the gap between theoretically possible (but slow) error rates and practical, polynomial-time execution.

Summary

The transition from "privacy as a mathematical property" to "privacy as a practical tool" requires solving the computational-statistical gap. By moving away from exhaustive search and toward clever sampling, projection, and stable optimization, researchers like Hilal Asi and Thomas Steinke are ensuring that strong privacy protections can be deployed on modern, high-dimensional datasets without requiring infinite time.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_polynomial_time_algorithms_for_private_s_b4bc1660,
  title = {Polynomial Time Algorithms for Private Statistics},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/polynomial-time-algorithms-for-private-statistics/rdr_b4bc1660aa594b289107a24ad0cf7cce},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_polynomial_time_algorithms_for_private_s_b4bc1660_v1,
  title = {Polynomial Time Algorithms for Private Statistics},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/polynomial-time-algorithms-for-private-statistics/rdr_b4bc1660aa594b289107a24ad0cf7cce/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}