Learning Halfspaces with Massart Noise Under Structured Distributions

• URL: http://arxiv.org/abs/2002.05632v1
• Date: Thu, 13 Feb 2020 17:02:37 GMT
• Title: Learning Halfspaces with Massart Noise Under Structured Distributions
• Authors: Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis
• Abstract summary: We solve the problem of learningspaces with Massart noise in the distribution-specific PAC model. We give the first efficient algorithm for a broad family problem with respect to log-con.
• Score: 46.37328271312332
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 respect to a broad family of distributions, including log-concave distributions. This resolves an open question posed in a number of prior works. Our approach is extremely simple: We identify a smooth {\em non-convex} surrogate loss with the property that any approximate stationary point of this loss defines a halfspace that is close to the target halfspace. Given this structural result, we can use SGD to solve the underlying learning problem.

Related papers

• Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time [8.419603619167813]
  We give a Gaussian-time algorithm for learning high-dimensional halfspaces with margins in $d$-dimensional space to within desired TV distance. Notably, our algorithm does not need labels and establishes unique (and efficient) identifiability of the hidden halfspace. We improve on this by providing polytime guarantees based on Total Variation (TV) distance, in place of existing moment-bound guarantees that can be super-polynomial.
  arXiv  Detail & Related papers  (2023-11-02T17:51:10Z)
• Agnostic Proper Learning of Halfspaces under Gaussian Marginals [56.01192577666607]
  We study the problem of agnostically learning halfspaces under the Gaussian. Our main result is the em first proper learning algorithm for this problem.
  arXiv  Detail & Related papers  (2021-02-10T18:40:44Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  We study the problem of PAC learning homogeneous halfspaces in the presence of Tsybakov noise. Our algorithm learns the true halfspace within any accuracy $epsilon$.
  arXiv  Detail & Related papers  (2020-10-04T22:19:06Z)
• Non-Convex SGD Learns Halfspaces with Adversarial Label Noise [50.659479930171585]
  We show the solution to the problem of learning surrogate learning homogeneous halfspaces in the distribution-specific model. In any convex distributions, we show that the misclassification error inherently leads to misclassification error of halfspace.
  arXiv  Detail & Related papers  (2020-06-11T18:55:59Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)
• Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability [39.01599245403753]
  In particular, we study the problem of learning halfspaces under Massart noise with rate $eta$. We show any SQ algorithm requires super-polynomially many queries to achieve $mathsfOPT + epsilon$. We also study our algorithm for learning halfspaces under Massart noise empirically and find that it exhibits some appealing fairness properties.
  arXiv  Detail & Related papers  (2020-06-08T17:59:11Z)
• Efficiently Learning Adversarially Robust Halfspaces with Noise [69.01459748050453]
  We study the problem of learning adversarially robust halfspaces in the distribution-independent setting. In the realizable setting, we provide necessary and sufficient conditions on the adversarial perturbation sets under which halfspaces are efficiently robustly learnable.
  arXiv  Detail & Related papers  (2020-05-15T17:13:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.