5 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 …