1 citations · 2 across the 9 of their papers we have counts for
12 papers
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/\…
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…
Robust Mean Estimation Without Moments for Symmetric Distributions
Gleb Novikov, David Steurer, Stefan Tiegel
We study the problem of robustly estimating the mean or location parameter without moment assumptions. We show that for a large class of symmetric distributions, the same error as…
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…
Relations between randomness deficiencies
Gleb Novikov
The notion of random sequence was introduced by Martin-Loef in 1966. At the same time he defined the so-called randomness deficiency function that shows how close are random sequen…