Designing Differentially Private Estimators in High Dimensions
This addresses computational and privacy barriers for high-dimensional data analysis, though it appears incremental by building on recent robust statistics work.
The paper tackles the problem of differentially private mean estimation in high dimensions, where existing methods suffer from computational intractability or excessive privacy loss. It develops a computationally tractable algorithm with dimension-independent privacy loss that significantly outperforms classic methods on synthetic data.
We study differentially private mean estimation in a high-dimensional setting. Existing differential privacy techniques applied to large dimensions lead to computationally intractable problems or estimators with excessive privacy loss. Recent work in high-dimensional robust statistics has identified computationally tractable mean estimation algorithms with asymptotic dimension-independent error guarantees. We incorporate these results to develop a strict bound on the global sensitivity of the robust mean estimator. This yields a computationally tractable algorithm for differentially private mean estimation in high dimensions with dimension-independent privacy loss. Finally, we show on synthetic data that our algorithm significantly outperforms classic differential privacy methods, overcoming barriers to high-dimensional differential privacy.