## Abstract

In this work, we give efficient algorithms for privately estimating a Gaussian distribution in both pure and approximate differential privacy (DP) models with optimal dependence on the dimension in the sample complexity. In the pure DP setting, we give an efficient algorithm that estimates an unknown d-dimensional Gaussian distribution up to an arbitrary tiny total variation error using O(d2 logκ) samples while tolerating a constant fraction of adversarial outliers. Here, κ is the condition number of the target covariance matrix. The sample bound matches best non-private estimators in the dependence on the dimension (up to a polylogarithmic factor). We prove a new lower bound on differentially private covariance estimation to show that the dependence on the condition number κ in the above sample bound is also tight. Prior to our work, only identifiability results (yielding inefficient super-polynomial time algorithms) were known for the problem. In the approximate DP setting, we give an efficient algorithm to estimate an unknown Gaussian distribution up to an arbitrarily tiny total variation error using O(d2) samples while tolerating a constant fraction of adversarial outliers. Prior to our work, all efficient approximate DP algorithms incurred a super-quadratic sample cost or were not outlier-robust. For the special case of mean estimation, our algorithm achieves the optimal sample complexity of O(d), improving on a O(d1.5) bound from prior work. Our pure DP algorithm relies on a recursive private preconditioning subroutine that utilizes recent work of Hopkins et al. (STOC 2022) on private mean estimation. Our approximate DP algorithms are based on a substantial upgrade of the method of stabilizing convex relaxations introduced by Kothari et al. (COLT 2022). In particular, we improve on their mechanism by using a new unnormalized entropy regularization and a new and surprisingly simple mechanism for privately releasing covariances.

Original language | English (US) |
---|---|

Title of host publication | STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing |

Editors | Barna Saha, Rocco A. Servedio |

Publisher | Association for Computing Machinery |

Pages | 483-496 |

Number of pages | 14 |

ISBN (Electronic) | 9781450399135 |

DOIs | |

State | Published - Jun 2 2023 |

Externally published | Yes |

Event | 55th Annual ACM Symposium on Theory of Computing, STOC 2023 - Orlando, United States Duration: Jun 20 2023 → Jun 23 2023 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Conference

Conference | 55th Annual ACM Symposium on Theory of Computing, STOC 2023 |
---|---|

Country/Territory | United States |

City | Orlando |

Period | 6/20/23 → 6/23/23 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Differential Privacy
- High-Dimensional Statistics
- Private Statistics
- Robust Statistics