mlsanityData to 7 Oct 2026

Efficiently Learning Adversarially Robust Halfspaces with Noise

arXiv 2005.07652 ↗First posted 15 May 2020cs.LG cs.DS stat.MLcited by 22

Not on the map. Why?

Abstract (arXiv)

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. In the presence of random label noise, we give a simple computationally efficient algorithm for this problem with respect to any ℓp-perturbation.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). First posted on arXiv 15 May 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 7; 2023: 2; 2024: 0; 2025: 2; 2026: 2.

22 papers.

Sort:

  1. 2023Cross-Entropy Loss Functions: Theoretical Analysis and Applicationscited by 206
  2. 2021Adversarial Robustness with Semi-Infinite Constrained Learningcited by 39
  3. 2022Probabilistically Robust Learning: Balancing Average- and Worst-case Performancecited by 36
  4. 2021Adversarially Robust Learning with Unknown Perturbation Setscited by 24
  5. 2021Excess Capacity and Backdoor Poisoningcited by 24
  6. 2021Robust learning under clean-label attackcited by 15
  7. 2022A Characterization of Semi-Supervised Adversarially-Robust PAC Learnabilitycited by 13
  8. 2021Benign Overfitting in Adversarially Robust Linear Classificationcited by 11
  9. 2023Adversarial Resilience in Sequential Prediction via Abstentioncited by 11
  10. 2021Provable Robustness of Adversarial Training for Learning Halfspaces with Noisecited by 10
  11. 2022Adversarially Robust Learning with Tolerancecited by 9
  12. 2022Adversarially Robust PAC Learnability of Real-Valued Functionscited by 8
10 more
  1. 2022Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariatescited by 6
  2. 2022Outlier Robust and Sparse Estimation of Linear Regression Coefficientscited by 4
  3. 2022Boosting Barely Robust Learners: A New Perspective on Adversarial Robustnesscited by 3
  4. 2025Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarkscited by 2
  5. 2025Robust learning of halfspaces under log-concave marginalscited by 2
  6. 2021Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversariescited by 1
  7. 2021Self-Training of Halfspaces with Generalization Guarantees under Massart Mislabeling Noise Modelcited by 1
  8. 2026Distribution-Free Sequential Prediction with Abstentionscited by 1
  9. 2026Bagging Robustly Learns VC Classes with Linear Sample Complexitycited by 1
  10. 2021On the (Un-)Avoidability of Adversarial Examplescited by 0