Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation. (arXiv:2211.00724v1 [stat.ML])

We establish a simple connection between robust and differentially-private
algorithms: private mechanisms which perform well with very high probability
are automatically robust in the sense that they retain accuracy even if a
constant fraction of the samples they receive are adversarially corrupted.
Since optimal mechanisms typically achieve these high success probabilities,
our results imply that optimal private mechanisms for many basic statistics
problems are robust.

We investigate the consequences of this observation for both algorithms and
computational complexity across different …

arxiv computation information mean privacy robustness