Private Algorithms Can Always Be Extended
read the original abstract
We consider the following fundamental question on $\epsilon$-differential privacy. Consider an arbitrary $\epsilon$-differentially private algorithm defined on a subset of the input space. Is it possible to extend it to an $\epsilon'$-differentially private algorithm on the whole input space for some $\epsilon'$ comparable with $\epsilon$? In this note we answer affirmatively this question for $\epsilon'=2\epsilon$. Our result applies to every input metric space and space of possible outputs. This result originally appeared in a recent paper by the authors [BCSZ18]. We present a self-contained version in this note, in the hopes that it will be broadly useful.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
Robust Statistical Estimators with Bounded Empirical Sensitivity
Defines empirical sensitivity and proves Ω(η + √(η d/n)) lower bound (tight up to logs) for any Gaussian mean estimator achieving optimal O(√(d/n)) ℓ₂ error.
-
Node-private community estimation in stochastic block models: Tractable algorithms and lower bounds
Develops tractable node-differentially private algorithms for community estimation in fixed-community stochastic block models together with lower bounds on the privacy parameter ε needed for consistency.
-
Tradeoffs in Privacy, Welfare, and Fairness for Facility Location
Privacy and fairness cannot both be guaranteed in facility location over all datasets, but mechanisms exist that are optimal or near-optimal on welfare and fairness for natural data while preserving worst-case differe...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.