Robust and Differentially Private Mean Estimation

  • 2021-11-24 18:52:56
  • Xiyang Liu, Weihao Kong, Sham Kakade, Sewoong Oh
  • 0


In statistical learning and analysis from shared data, which is increasinglywidely adopted in platforms such as federated learning and meta-learning, thereare two major concerns: privacy and robustness. Each participating individualshould be able to contribute without the fear of leaking one's sensitiveinformation. At the same time, the system should be robust in the presence ofmalicious participants inserting corrupted data. Recent algorithmic advances inlearning from shared data focus on either one of these threats, leaving thesystem vulnerable to the other. We bridge this gap for the canonical problem ofestimating the mean from i.i.d. samples. We introduce PRIME, which is the firstefficient algorithm that achieves both privacy and robustness for a wide rangeof distributions. We further complement this result with a novel exponentialtime algorithm that improves the sample complexity of PRIME, achieving anear-optimal guarantee and matching a known lower bound for (non-robust)private mean estimation. This proves that there is no extra statistical cost tosimultaneously guaranteeing privacy and robustness.


Quick Read (beta)

loading the full paper ...