3 citations · 6 across the 21 of their papers we have counts for
13 papers · 1 filter
PTF Testing Lower Bounds for Non-Gaussian Component Analysis
Ilias Diakonikolas, Daniel M. Kane, Sihan Liu +1
This work studies information-computation gaps for statistical problems. A common approach for providing evidence of such gaps is to show sample complexity lower bounds (that are s…
Linear Regression under Missing or Corrupted Coordinates
Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane +2
We study multivariate linear regression under Gaussian covariates in two settings, where data may be erased or corrupted by an adversary under a coordinate-wise budget. In the inco…
On Fine-Grained Distinct Element Estimation
Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee +3
We study the problem of distributed distinct element estimation, where servers each receive a subset of a universe and aim to compute a -approximation to…
Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination
Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane +1
We study the algorithmic problem of robust mean estimation of an identity covariance Gaussian in the presence of mean-shift contamination. In this contamination model, we are given…
Entangled Mean Estimation in High-Dimensions
Ilias Diakonikolas, Daniel M. Kane, Sihan Liu +1
We study the task of high-dimensional entangled mean estimation in the subset-of-signals model. Specifically, given independent random points in …
Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Error
Thanasis Pittas, Ankit Pensia
Algorithmic robust statistics has traditionally focused on the contamination model where a small fraction of the samples are arbitrarily corrupted. We consider a recent contaminati…
Statistical Query Lower Bounds for Learning Truncated Gaussians
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas +1
We study the problem of estimating the mean of an identity covariance Gaussian in the truncated setting, in the regime when the truncation set comes from a low-complexity family $\…
Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia +1
We study the fundamental problems of Gaussian mean estimation and linear regression with Gaussian covariates in the presence of Huber contamination. Our main contribution is the de…
A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm
Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee +2
We study the problem of list-decodable Gaussian covariance estimation. Given a multiset of points in such that an unknown fraction of points in ar…
List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering
Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar +2
We study the problem of list-decodable sparse mean estimation. Specifically, for a parameter , we are given points in , of whi…
Robust Sparse Mean Estimation via Sum of Squares
Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar +2
We study the problem of high-dimensional sparse mean estimation in the presence of an -fraction of adversarial outliers. Prior work obtained sample and computationally efficient…
Streaming Algorithms for High-Dimensional Robust Statistics
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia +1
We study high-dimensional robust statistics tasks in the streaming model. A recent line of work obtained computationally efficient algorithms for a range of high-dimensional robust…
Statistical Query Lower Bounds for List-Decodable Linear Regression
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia +2
We study the problem of list-decodable linear regression, where an adversary can corrupt a majority of the examples. Specifically, we are given a set of labeled examples $(x, y…