3 citations · 6 across the 21 of their papers we have counts for
21 papers
High-Dimensional Gaussian Mean Estimation under Realizable Contamination
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas
We study mean estimation for a Gaussian distribution with identity covariance in under a missing data scheme termed realizable -contamination model. In this model…
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…
On Learning Parallel Pancakes with Mostly Uniform Weights
Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar +2
We study the complexity of learning -mixtures of Gaussians (-GMMs) on . This task is known to have complexity in full generality. To circumvent this…
Batch List-Decodable Linear Regression via Higher Moments
Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar +2
We study the task of list-decodable linear regression using batches. A batch is called clean if it consists of i.i.d. samples from an unknown linear regression distribution. For a…
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…
Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination
Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar +2
We study Gaussian sparse estimation tasks in Huber's contamination model with a focus on mean estimation, PCA, and linear regression. For each of these tasks, we give the first sam…
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 $\…
Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation
Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee +1
We study the clustering problem for mixtures of bounded covariance distributions, under a fine-grained separation assumption. Specifically, given samples from a -component mixtu…
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…
SQ Lower Bounds for Learning Bounded Covariance GMMs
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas +1
We study the complexity of learning mixtures of separated Gaussians with common unknown bounded covariance matrix. Specifically, we focus on learning Gaussian mixture models (GMMs)…
Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia +1
We study principal component analysis (PCA), where given a dataset in from a distribution, the task is to find a unit vector that approximately maximizes the var…
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…
The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas +1
We study the problem of agnostic learning under the Gaussian distribution. We develop a method for finding hard families of examples for a wide class of problems by using LP dualit…