# A Private Approximation of the 2nd-Moment Matrix of Any Subsamplable Input

arXiv: https://arxiv.org/abs/2505.14251 · HTML: https://mlsanity.com/paper/2505.14251/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 19 references that are in the map.
- First posted on arXiv 20 May 2025.

## Builds on (most cited first, 12 of 12)

- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [CoinPress: Practical Private Mean and Covariance Estimation](https://mlsanity.com/paper/2006.06618/) (2020)
- [On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians](https://mlsanity.com/paper/2010.09929/) (2020)
- [Private and polynomial time algorithms for learning Gaussians and beyond](https://mlsanity.com/paper/2111.11320/) (2021)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [A Private and Computationally-Efficient Estimator for Unbounded Gaussians](https://mlsanity.com/paper/2111.04609/) (2021)
- [Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions](https://mlsanity.com/paper/2301.12250/) (2023)
- [Locating a Small Cluster Privately](https://mlsanity.com/paper/1604.05590/) (2016)
- [Clustering Algorithms for the Centralized and Local Models](https://mlsanity.com/paper/1707.04766/) (2017)
- [Differentially Private Covariance Revisited](https://mlsanity.com/paper/2205.14324/) (2022)
- [A Differentially Private Linear-Time fPTAS for the Minimum Enclosing Ball Problem](https://mlsanity.com/paper/2206.03319/) (2022)

## Abstract (arXiv)

We study the problem of differentially private second moment estimation and present a new algorithm that achieve strong privacy-utility trade-offs even for worst-case inputs under subsamplability assumptions on the data. We call an input (m,α,β)-subsamplable if a random subsample of size m (or larger) preserves w.p ≥ 1-β the spectral structure of the original second moment matrix up to a multiplicative factor of 1± α. Building upon subsamplability, we give a recursive algorithmic framework similar to Kamath et al 2019, that abides zero-Concentrated Differential Privacy (zCDP) while preserving w.h.p. the accuracy of the second moment estimation upto an arbitrary factor of (1±γ). We then show how to apply our algorithm to approximate the second moment matrix of a distribution D, even when a noticeable fraction of the input are outliers.