9 papers
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…
Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination
Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane +1
We study the basic task of mean estimation in the presence of mean-shift contamination. In the mean-shift contamination model, an adversary is allowed to replace a small constant f…
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…
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…
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 …
Efficient Testable Learning of General Halfspaces with Adversarial Label Noise
Ilias Diakonikolas, Daniel M. Kane, Sihan Liu +1
We study the task of testable learning of general -- not necessarily homogeneous -- halfspaces with adversarial label noise with respect to the Gaussian distribution. In the testab…
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…
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…
Online Robust Mean Estimation
Daniel M. Kane, Ilias Diakonikolas, Hanshen Xiao +1
We study the problem of high-dimensional robust mean estimation in an online setting. Specifically, we consider a scenario where sensors are measuring some common, ongoing phen…