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

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 \geq 1-β the spectral structure of the original second moment matrix up to a multiplicative factor of 1\pm α. 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\pmγ). 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.