5 papers
Learning Intersections of Two Margin Halfspaces under Factorizable Distributions
Ilias Diakonikolas, Mingchen Ma, Lisheng Ren +1
Learning intersections of halfspaces is a central problem in Computational Learning Theory. Even for just two halfspaces, it remains a major open question whether learning is possi…
Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models
Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane +1
We study the complexity of learning real-valued Multi-Index Models (MIMs) under the Gaussian distribution. A -MIM is a function that depends only…
Faster Algorithms for Agnostically Learning Disjunctions and their Implications
Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren
We study the algorithmic task of learning Boolean disjunctions in the distribution-free agnostic PAC model. The best known agnostic learner for the class of disjunctions over $\{0,…
Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise
Ilias Diakonikolas, Mingchen Ma, Lisheng Ren +1
We study the task of Multiclass Linear Classification (MLC) in the distribution-free PAC model with Random Classification Noise (RCN). Specifically, the learner is given a set of l…
Reliable Learning of Halfspaces under Gaussian Marginals
Ilias Diakonikolas, Lisheng Ren, Nikos Zarifis
We study the problem of PAC learning halfspaces in the reliable agnostic model of Kalai et al. (2012). The reliable PAC model captures learning scenarios where one type of error is…