Towards Instance-Optimal Private Query Release

DOI10.1137/1.9781611975482.152MaRDI QIDQ5236341zbMATH OpenOpenAlexFDO

Authors Jarosław Błasiok, Mark Bun, Aleksandar Nikolov, Thomas Steinke

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.03763

Mathematics Subject Classification ID

Privacy of data (68P27)

Abstract: We study efficient mechanisms for the query release problem in differential privacy: given a workload of $m$ statistical queries, output approximate answers to the queries while satisfying the constraints of differential privacy. In particular, we are interested in mechanisms that optimally adapt to the given workload. Building on the projection mechanism of Nikolov, Talwar, and Zhang, and using the ideas behind Dudley's chaining inequality, we propose new efficient algorithms for the query release problem, and prove that they achieve optimal sample complexity for the given workload (up to constant factors, in certain parameter regimes) with respect to the class of mechanisms that satisfy concentrated differential privacy. We also give variants of our algorithms that satisfy local differential privacy, and prove that they also achieve optimal sample complexity among all local sequentially interactive private mechanisms.

Recommendations

• Exploiting metric structure for efficient private query release
• Fast private data release algorithms for sparse queries
• Differentially private data releasing for smooth queries
• Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy
• Near-optimal differentially private mechanism for linear queries
• Faster private release of marginals on small databases
• A semantic-preserving differentially private method for releasing query logs

Cited in

(5)

• Constrained-based differential privacy: releasing optimal power flow benchmarks privately
• Faster private release of marginals on small databases
• An improved private mechanism for small databases
• Exploiting metric structure for efficient private query release
• General Gaussian noise mechanisms and their optimality for unbiased mean estimation

This page was built for publication: Towards Instance-Optimal Private Query Release

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236341)