An improved private mechanism for small databases

DOI10.1007/978-3-662-47672-7_82MaRDI QIDQ3448856zbMATH OpenOpenAlexFDO

Authors Aleksandar Nikolov

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

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

zbMATH Keywords

competitive analysisconvex optimizationdifferential privacy

Mathematics Subject Classification ID

Database theory (68P15) Privacy of data (68P27)

Abstract: We study the problem of answering a workload of linear queries $mathcalQ$, on a database of size at most $n=o(|mathcalQ|)$ drawn from a universe $mathcalU$ under the constraint of (approximate) differential privacy. Nikolov, Talwar, and Zhang~cite{NTZ} proposed an efficient mechanism that, for any given $mathcalQ$ and $n$, answers the queries with average error that is at most a factor polynomial in $log|mathcalQ|$ and $log|mathcalU|$ worse than the best possible. Here we improve on this guarantee and give a mechanism whose competitiveness ratio is at most polynomial in $logn$ and $log|mathcalU|$, and has no dependence on $|mathcalQ|$. Our mechanism is based on the projection mechanism of Nikolov, Talwar, and Zhang, but in place of an ad-hoc noise distribution, we use a distribution which is in a sense optimal for the projection mechanism, and analyze it using convex duality and the restricted invertibility principle.

Recommendations

• Unconditional differentially private mechanisms for linear queries
• Towards Instance-Optimal Private Query Release
• On the geometry of differential privacy

Cites work

• Advances in Cryptology – CRYPTO 2004
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Approximating hereditary discrepancy via small width ellipsoids
• Differential privacy under continual observation
• Fingerprinting codes and the price of approximate differential privacy
• scientific article; zbMATH DE number 5485440 (Why is no real title available?)
• scientific article; zbMATH DE number 5485574 (Why is no real title available?)
• Interactive privacy via the median mechanism
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• Iterative Constructions and Private Data Release
• Nearly optimal minimax estimator for high-dimensional sparse linear regression
• On the complexity of differentially private data release, efficient algorithms and hardness results
• Optimal private halfspace counting via discrepancy
• Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• Private and continual release of statistics
• Randomized rounding for the largest simplex problem
• The ellipsoid method and its consequences in combinatorial optimization
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Theory of Cryptography
• Using convex relaxations for efficiently and privately releasing marginals (extended abstract)

Cited in

(6)

• Differentially private data releasing for smooth queries
• Faster private release of marginals on small databases
• Mirror descent based database privacy
• Near-optimal differentially private mechanism for linear queries
• Structure and sensitivity in differential privacy: comparing \(K\)-norm mechanisms
• Unconditional differentially private mechanisms for linear queries

This page was built for publication: An improved private mechanism for small databases

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