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 ≥ 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.