5 papers
On Purely Private Covariance Estimation
Tommaso d'Orsi, Gleb Novikov
We present a simple perturbation mechanism for the release of -dimensional covariance matrices under pure differential privacy. For large datasets with at least $n\geq d^2/…
Tight Differentially Private PCA via Matrix Coherence
Tommaso d'Orsi, Gleb Novikov
We revisit the task of computing the span of the top singular vectors of a matrix under differential privacy. We show that a simple and efficient algorithm -…
Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians
Gleb Novikov
We study the problem of computationally efficient robust estimation of the covariance/scatter matrix of elliptical distributions -- that is, affine transformations of spherically s…
Robust Sparse Regression with Non-Isotropic Designs
Chih-Hung Liu, Gleb Novikov
We develop a technique to design efficiently computable estimators for sparse linear regression in the simultaneous presence of two adversaries: oblivious and adaptive. We design s…
Robust Mixture Learning when Outliers Overwhelm Small Groups
Daniil Dmitriev, Rares-Darius Buhai, Stefan Tiegel +5
We study the problem of estimating the means of well-separated mixtures when an adversary may add arbitrary outliers. While strong guarantees are available when the outlier fractio…