# Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach

arXiv: https://arxiv.org/abs/2310.15411 · HTML: https://mlsanity.com/paper/2310.15411/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 62 references that are in the map.
- First posted on arXiv 23 Oct 2023.

## Builds on (most cited first, 25 of 25)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Stochastic Optimization with Importance Sampling](https://mlsanity.com/paper/1401.2753/) (2014)
- [Deep Bayesian Active Learning for Natural Language Processing: Results of a Large-Scale Empirical Study](https://mlsanity.com/paper/1808.05697/) (2018)
- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [Statistical-Query Lower Bounds via Functional Gradients](https://mlsanity.com/paper/2006.15812/) (2020)
- [Learning Halfspaces with Massart Noise Under Structured Distributions](https://mlsanity.com/paper/2002.05632/) (2020)
- [Efficient Learning of Linear Separators under Bounded Noise](https://mlsanity.com/paper/1503.03594/) (2015)
- [Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2012.09720/) (2020)
- [Efficient active learning of sparse halfspaces with arbitrary bounded noise](https://mlsanity.com/paper/2002.04840/) (2020)
- [Cryptographic Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2207.14266/) (2022)
- [Beyond Disagreement-based Agnostic Active Learning](https://mlsanity.com/paper/1407.2657/) (2014)
- [Neural Active Learning with Performance Guarantees](https://mlsanity.com/paper/2106.03243/) (2021)
- [Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise](https://mlsanity.com/paper/2102.05312/) (2021)
- [Efficient and Parsimonious Agnostic Active Learning](https://mlsanity.com/paper/1506.08669/) (2015)
- [Learning Halfspaces with Tsybakov Noise](https://mlsanity.com/paper/2006.06467/) (2020)
- [Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins](https://mlsanity.com/paper/2010.00539/) (2020)
- [Efficient active learning of sparse halfspaces](https://mlsanity.com/paper/1805.02350/) (2018)
- [Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability](https://mlsanity.com/paper/2006.04787/) (2020)
- [A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise](https://mlsanity.com/paper/2010.01705/) (2020)
- [Agnostic Learnability of Halfspaces via Logistic Loss](https://mlsanity.com/paper/2201.13419/) (2022)

## Built on by (most cited first, 1 of 1)

- [Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2410.01186/) (2024)

## Abstract (arXiv)

We study the problem of computationally and label efficient PAC active learning d-dimensional halfspaces with Tsybakov Noise~citeptsybakov2004optimal under structured unlabeled data distributions. Inspired by~citediakonikolas2020learning, we prove that any approximate first-order stationary point of a smooth nonconvex loss function yields a halfspace with a low excess error guarantee. In light of the above structural result, we design a nonconvex optimization-based algorithm with a label complexity of tildeO(d (frac1ε)^frac8-6α3α-1), under the assumption that the Tsybakov noise parameter α ∈ (frac13, 1], which narrows down the gap between the label complexities of the previously known efficient passive or active algorithms~citepdiakonikolas2020polynomial,zhang2021improved and the information-theoretic lower bound in this setting.