mlsanityData to 13 Oct 2026

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

arXiv 2310.15411 ↗First posted 23 Oct 2023cs.LG stat.MLcited by 1

Not on the map. Why?

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.

Key facts. Cited by 1 paper in the map (data through 13 Oct 2026). Builds on 25 of its 62 references that are in the map. First posted on arXiv 23 Oct 2023.

Builds on

25 of 62 references.

References · 25

  1. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 718
  2. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 306
  3. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 133
  4. 2014Stochastic Optimization with Importance Samplingcited by 91
  5. 2018Deep Bayesian Active Learning for Natural Language Processing: Results of a Large-Scale Empirical Studycited by 90
  6. 2014Minimax Analysis of Active Learningcited by 61
  7. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  8. 2019Distribution-Independent PAC Learning of Halfspaces with Massart Noisecited by 54
  9. 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
  10. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  11. 2020Learning Halfspaces with Massart Noise Under Structured Distributionscited by 45
  12. 2015Efficient Learning of Linear Separators under Bounded Noisecited by 36
13 more
  1. 2020Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noisecited by 30
  2. 2020Efficient active learning of sparse halfspaces with arbitrary bounded noisecited by 29
  3. 2022Cryptographic Hardness of Learning Halfspaces with Massart Noisecited by 25
  4. 2014Beyond Disagreement-based Agnostic Active Learningcited by 22
  5. 2021Neural Active Learning with Performance Guaranteescited by 22
  6. 2021Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noisecited by 18
  7. 2015Efficient and Parsimonious Agnostic Active Learningcited by 17
  8. 2020Learning Halfspaces with Tsybakov Noisecited by 15
  9. 2020Agnostic Learning of Halfspaces with Gradient Descent via Soft Marginscited by 14
  10. 2018Efficient active learning of sparse halfspacescited by 13
  11. 2020Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvabilitycited by 13
  12. 2020A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noisecited by 13
  13. 2022Agnostic Learnability of Halfspaces via Logistic Losscited by 2

Built on by

Cited by year

Citing papers per year: 2024: 1.

1 paper.

  1. 2024Efficient PAC Learning of Halfspaces with Constant Malicious Noise Ratecited by 5