Agnostic Learnability of Halfspaces via Logistic Loss
Not on the map. Why?
Abstract (arXiv)
We investigate approximation guarantees provided by logistic regression for the fundamental problem of agnostic learning of homogeneous halfspaces. Previously, for a certain broad class of "well-behaved" distributions on the examples, Diakonikolas et al. (2020) proved an tildeOmega(textrmOPT) lower bound, while Frei et al. (2021) proved an tildeO(√textrmOPT) upper bound, where textrmOPT denotes the best zero-one/misclassification risk of a homogeneous halfspace. In this paper, we close this gap by constructing a well-behaved distribution such that the global minimizer of the logistic risk over this distribution only achieves Omega(√textrmOPT) misclassification risk, matching the upper bound in (Frei et al., 2021). On the other hand, we also show that if we impose a radial-Lipschitzness condition in addition to well-behaved-ness on the distribution, logistic regression on a ball of bounded radius reaches tildeO(textrmOPT) misclassification risk. Our techniques also show for any well-behaved distribution, regardless of radial Lipschitzness, we can overcome the Omega(√textrmOPT) lower bound for logistic loss simply at the cost of one additional convex optimization step involving the hinge loss and attain tildeO(textrmOPT) misclassification risk. This two-step convex optimization algorithm is simpler than previous methods obtaining this guarantee, all of which require solving O(log(1/textrmOPT)) minimization problems.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 16 of its 34 references that are in the map. First posted on arXiv 31 Jan 2022.
Builds on
16 of 34 references.
References · 16
- 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
- 2019Distribution-Independent PAC Learning of Halfspaces with Massart Noisecited by 54
- 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
- 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
- 2020Learning Halfspaces with Massart Noise Under Structured Distributionscited by 45
- 2015Efficient Learning of Linear Separators under Bounded Noisecited by 36
- 2021Early-stopped neural networks are consistentcited by 34
- 2020Non-Convex SGD Learns Halfspaces with Adversarial Label Noisecited by 30
- 2020Efficient active learning of sparse halfspaces with arbitrary bounded noisecited by 29
- 2014A PTAS for Agnostically Learning Halfspacescited by 21
- 2021Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noisecited by 18
- 2021Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noisecited by 17
4 more
- 2020Learning Halfspaces with Tsybakov Noisecited by 15
- 2020Agnostic Learning of Halfspaces with Gradient Descent via Soft Marginscited by 14
- 2020Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvabilitycited by 13
- 2020Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerancecited by 12
Built on by
Citing papers per year: 2023: 2.
2 papers.