10 citations · 53 across the 28 of their papers we have counts for
6 papers · 1 filter
A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We study the problem of PAC learning homogeneous halfspaces in the presence of Tsybakov noise. In the Tsybakov noise model, the label of every sample is independently flipped with…
Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals
Ilias Diakonikolas, Daniel M. Kane, Nikos Zarifis
We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. In the former problem, given labeled examples from an un…
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +1
We study the problem of PAC learning one-hidden-layer ReLU networks with hidden units on under Gaussian marginals in the presence of additive label noise. For th…
Non-Convex SGD Learns Halfspaces with Adversarial Label Noise
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos +1
We study the problem of agnostically learning homogeneous halfspaces in the distribution-specific PAC model. For a broad family of structured distributions, including log-concave d…
Learning Halfspaces with Tsybakov Noise
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos +1
We study the efficient PAC learnability of halfspaces in the presence of Tsybakov noise. In the Tsybakov noise model, each label is independently flipped with some probability whic…
Learning Halfspaces with Massart Noise Under Structured Distributions
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos +1
We study the problem of learning halfspaces with Massart noise in the distribution-specific PAC model. We give the first computationally efficient algorithm for this problem with r…