Defines empirical sensitivity and proves Ω(η + √(η d/n)) lower bound (tight up to logs) for any Gaussian mean estimator achieving optimal O(√(d/n)) ℓ₂ error.
Private Algorithms Can Always Be Extended
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
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.
years
2026 3representative citing papers
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.
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 differential privacy.
citing papers explorer
-
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 differential privacy.