Efficient Testable Learning of Halfspaces with Adversarial Label Noise
- URL: http://arxiv.org/abs/2303.05485v1
- Date: Thu, 9 Mar 2023 18:38:46 GMT
- Title: Efficient Testable Learning of Halfspaces with Adversarial Label Noise
- Authors: Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan Liu, Nikos
Zarifis
- Abstract summary: In the recently introduced testable learning model, one is required to produce a tester-learner such that if the data passes the tester, then one can trust the output of the robust learner on the data.
Our tester-learner runs in time $poly(d/eps)$ and outputs a halfspace with misclassification error $O(opt)+eps$, where $opt$ is the 0-1 error of the best fitting halfspace.
- Score: 44.32410859776227
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give the first polynomial-time algorithm for the testable learning of
halfspaces in the presence of adversarial label noise under the Gaussian
distribution. In the recently introduced testable learning model, one is
required to produce a tester-learner such that if the data passes the tester,
then one can trust the output of the robust learner on the data. Our
tester-learner runs in time $\poly(d/\eps)$ and outputs a halfspace with
misclassification error $O(\opt)+\eps$, where $\opt$ is the 0-1 error of the
best fitting halfspace. At a technical level, our algorithm employs an
iterative soft localization technique enhanced with appropriate testers to
ensure that the data distribution is sufficiently similar to a Gaussian.
Related papers
- Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds [9.036777309376697]
Klivans, Stavropoulos, and Vasilyan initiated the study of testable learning with distribution shift.
Their model deviates from all prior work in that no assumptions are made on $mathcalD'$.
arXiv Detail & Related papers (2024-04-02T23:34:39Z) - Testable Learning with Distribution Shift [9.036777309376697]
We define a new model called testable learning with distribution shift.
We obtain provably efficient algorithms for certifying the performance of a classifier on a test distribution.
We give several positive results for learning concept classes such as halfspaces, intersections of halfspaces, and decision trees.
arXiv Detail & Related papers (2023-11-25T23:57:45Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$.
Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
arXiv Detail & Related papers (2023-07-13T18:59:28Z) - An Efficient Tester-Learner for Halfspaces [13.13131953359806]
We give the first efficient algorithm for learning halfspaces in the testable learning model recently defined by Rubinfeld and Vasilyan (2023)
In this model, a learner certifies that the accuracy of its output hypothesis is near optimal whenever the training set passes a test.
arXiv Detail & Related papers (2023-02-28T18:51:55Z) - Testing distributional assumptions of learning algorithms [5.204779946147061]
We study the design of tester-learner pairs $(mathcalA,mathcalT)$.
We show that if the distribution on examples in the data passes the tester $mathcalT$ then one can safely trust the output of the agnostic $mathcalA$ on the data.
arXiv Detail & Related papers (2022-04-14T19:10:53Z) - Provable Robustness of Adversarial Training for Learning Halfspaces with
Noise [95.84614821570283]
We analyze the properties of adversarial learning adversarially robust halfspaces in the presence of label noise.
To the best of our knowledge, this is the first work to show that adversarial training prov yields classifiers in noise.
arXiv Detail & Related papers (2021-04-19T16:35:38Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
We study the complexity of PAC learning halfspaces in the presence of Massart (bounded) noise.
We show that there an exponential gap between the information-theoretically optimal error and the best error that can be achieved by a SQ algorithm.
arXiv Detail & Related papers (2020-12-17T16:43:11Z) - 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) - 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)
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.