5 citations · 7 across the 8 of their papers we have counts for
9 papers · 1 filter
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…
SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions
Ilias Diakonikolas, Daniel Kane, Lisheng Ren +1
We study the complexity of Non-Gaussian Component Analysis (NGCA) in the Statistical Query (SQ) model. Prior work developed a general methodology to prove SQ lower bounds for this…
Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals
Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren
We study the task of agnostically learning halfspaces under the Gaussian distribution. Specifically, given labeled examples from an unknown distribution on $\mathb…
SQ Lower Bounds for Learning Single Neurons with Massart Noise
Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren +1
We study the problem of PAC learning a single neuron in the presence of Massart noise. Specifically, for a known activation function , the learner is…
Cryptographic Hardness of Learning Halfspaces with Massart Noise
Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi +1
We study the complexity of PAC learning halfspaces in the presence of Massart noise. In this problem, we are given i.i.d. labeled examples $(\mathbf{x}, y) \in \mathbb{R}^N \times…