1 citations · 2 across the 30 of their papers we have counts for
12 papers · 1 filter
Testable Learning of General Halfspaces under Massart Noise
Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane +1
We study the algorithmic task of testably learning general Massart halfspaces under the Gaussian distribution. In the testable learning setting, the aim is the design of a tester-l…
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…
Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
Ilias Diakonikolas, Chao Gao, Daniel M. Kane +2
We study the task of noiseless linear regression under Gaussian covariates in the presence of additive oblivious contamination. Specifically, we are given i.i.d.\ samples from a di…
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 …
Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models
Ilias Diakonikolas, Daniel M. Kane
We study the task of learning latent-variable models. A common algorithmic technique for this task is the method of moments. Unfortunately, moment-based approaches are hampered by…
Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We study the efficient learnability of low-degree polynomial threshold functions (PTFs) in the presence of a constant fraction of adversarial corruptions. Our main algorithmic resu…
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…
Testing Closeness of Multivariate Distributions via Ramsey Theory
Ilias Diakonikolas, Daniel M. Kane, Sihan Liu
We investigate the statistical task of closeness (or equivalence) testing for multidimensional distributions. Specifically, given sample access to two unknown distributions $\mathb…