A One-Pass Private Sketch for Most Machine Learning Tasks
This work addresses the problem of inefficient DP methods for large-scale, high-dimensional data, enabling broader adoption in distributed machine learning settings, though it is incremental as it builds on general-purpose data release algorithms.
The paper tackles the challenge of scaling differential privacy (DP) for high-dimensional datasets by proposing a one-pass private sketch that supports multiple machine learning tasks, achieving competitive error bounds for DP kernel density estimation while reducing computation costs significantly compared to existing methods.
Differential privacy (DP) is a compelling privacy definition that explains the privacy-utility tradeoff via formal, provable guarantees. Inspired by recent progress toward general-purpose data release algorithms, we propose a private sketch, or small summary of the dataset, that supports a multitude of machine learning tasks including regression, classification, density estimation, near-neighbor search, and more. Our sketch consists of randomized contingency tables that are indexed with locality-sensitive hashing and constructed with an efficient one-pass algorithm. We prove competitive error bounds for DP kernel density estimation. Existing methods for DP kernel density estimation scale poorly, often exponentially slower with an increase in dimensions. In contrast, our sketch can quickly run on large, high-dimensional datasets in a single pass. Exhaustive experiments show that our generic sketch delivers a similar privacy-utility tradeoff when compared to existing DP methods at a fraction of the computation cost. We expect that our sketch will enable differential privacy in distributed, large-scale machine learning settings.