1 citations · 2 across the 9 of their papers we have counts for
9 papers · 1 filter
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 -…
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/\…
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…
Sparse PCA Beyond Covariance Thresholding
Gleb Novikov
In the Wishart model for sparse PCA we are given samples drawn independently from a -dimensional Gaussian distribution , where $β> 0…
Higher degree sum-of-squares relaxations robust against oblivious outliers
Tommaso d'Orsi, Rajai Nasser, Gleb Novikov +1
We consider estimation models of the form , where is some -dimensional signal we wish to recover, and is symmetrically distributed noise that may be unbounded…
Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers
Tommaso d'Orsi, Chih-Hung Liu, Rajai Nasser +3
We develop machinery to design efficiently computable and consistent estimators, achieving estimation error approaching zero as the number of observations grows, when facing an obl…
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov +1
We study efficient algorithms for Sparse PCA in standard statistical models (spiked covariance in its Wishart form). Our goal is to achieve optimal recovery guarantees while being…
Consistent regression when oblivious outliers overwhelm
Tommaso d'Orsi, Gleb Novikov, David Steurer
We consider a robust linear regression model , where an adversary oblivious to the design may choose to corrupt all but an fractio…