Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: A One-Pass Private Sketch for Most Machine Learning Tasks   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.

20
The categories of this paper are: acc-phys
14
The categories of this paper are: math-ph
15
The categories of this paper are: nucl-ex
12
The categories of this paper are: nucl-th
32
The categories of this paper are: atom-ph
34
The categories of this paper are: chem-ph
18
The categories of this paper are: econ
4
The categories of this paper are: cond-mat
27
The categories of this paper are: comp-gas
36
The categories of this paper are: cmp-lg
22
The categories of this paper are: chao-dyn
33
The categories of this paper are: plasm-ph
37
The categories of this paper are: supr-con
35
The categories of this paper are: mtrl-th
23
The categories of this paper are: solv-int
28
The categories of this paper are: alg-geom