Skip to main content

Pythia: Data dependent differentially private algorithm selection

Publication ,  Conference
Kotsogiannis, I; Hay, M; Machanavajjhala, A; Miklau, G
Published in: Proceedings of the ACM SIGMOD International Conference on Management of Data
May 9, 2017

Differential privacy has emerged as a preferred standard for ensuring privacy in analysis tasks on sensitive datasets. Recent algorithms have allowed for significantly lower error by adapting to properties of the input data. These so-called data-dependent algorithms have different error rates for different inputs. There is now a complex and growing landscape of algorithms without a clear winner that can offer low error over all datasets. As a result, the best possible error rates are not attainable in practice, because the data curator cannot know which algorithm to select prior to actually running the algorithm. We address this challenge by proposing a novel metaalgorithm designed to relieve the data curator of the burden of algorithm selection. It works by learning (from nonsensitive data) the association between dataset properties and the best-performing algorithm. The meta-algorithm is deployed by first testing the input for low-sensitivity properties and then using the results to select a good algorithm. The result is an end-to-end differentially private system: Pythia, which we show offers improvements over using any single algorithm alone. We empirically demonstrate the benefit of Pythia for the tasks of releasing histograms, answering 1- and 2-dimensional range queries, as well as for constructing private Naive Bayes classifiers.

Duke Scholars

Published In

Proceedings of the ACM SIGMOD International Conference on Management of Data

DOI

ISSN

0730-8078

ISBN

9781450341974

Publication Date

May 9, 2017

Volume

Part F127746

Start / End Page

1323 / 1337
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Kotsogiannis, I., Hay, M., Machanavajjhala, A., & Miklau, G. (2017). Pythia: Data dependent differentially private algorithm selection. In Proceedings of the ACM SIGMOD International Conference on Management of Data (Vol. Part F127746, pp. 1323–1337). https://doi.org/10.1145/3035918.3035945
Kotsogiannis, I., M. Hay, A. Machanavajjhala, and G. Miklau. “Pythia: Data dependent differentially private algorithm selection.” In Proceedings of the ACM SIGMOD International Conference on Management of Data, Part F127746:1323–37, 2017. https://doi.org/10.1145/3035918.3035945.
Kotsogiannis I, Hay M, Machanavajjhala A, Miklau G. Pythia: Data dependent differentially private algorithm selection. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. 2017. p. 1323–37.
Kotsogiannis, I., et al. “Pythia: Data dependent differentially private algorithm selection.” Proceedings of the ACM SIGMOD International Conference on Management of Data, vol. Part F127746, 2017, pp. 1323–37. Scopus, doi:10.1145/3035918.3035945.
Kotsogiannis I, Hay M, Machanavajjhala A, Miklau G. Pythia: Data dependent differentially private algorithm selection. Proceedings of the ACM SIGMOD International Conference on Management of Data. 2017. p. 1323–1337.

Published In

Proceedings of the ACM SIGMOD International Conference on Management of Data

DOI

ISSN

0730-8078

ISBN

9781450341974

Publication Date

May 9, 2017

Volume

Part F127746

Start / End Page

1323 / 1337