We study the problem of differentially private second moment estimation and present a new algorithm that achieves strong privacy-utility trade-offs even for worst-case inputs under subsamplability assumptions on the data. We call an input $(m,\beta,\beta)$-subsamplable if a random subsample of size $m$ (or larger) preserves w.p $\text{w.p} \geq 1-\beta$ the spectral structure of the original second moment matrix up to a multiplicative factor of $1\pm\beta$.
Building upon subsamplability, we give a recursive algorithmic framework similar to Kamath et al 2019, that abides by zero-Concentrated Differential Privacy (zCDP) while preserving w.h.p. the accuracy of the second moment estimation up to an arbitrary factor of $(1\pm\beta)$. We then show how to apply our algorithm to approximate the second moment matrix of a distribution $\text{D}$, even when a noticeable fraction of the input are outliers.
Blogger's Review: The proposed algorithm strikes a good balance between differential privacy and second moment estimation, especially in scenarios where outliers are present. This research provides new insights for achieving high privacy in statistical estimates and has broad application potential. The recursive framework of the algorithm also lays a solid foundation for future research.