The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise
Not on the map. Why?
Abstract (arXiv)
We study the computational complexity of adversarially robust proper learning of halfspaces in the distribution-independent agnostic PAC model, with a focus on Lp perturbations. We give a computationally efficient learning algorithm and a nearly matching computational hardness result for this problem. An interesting implication of our findings is that the L∞ perturbations case is provably computationally harder than the case 2 ≤ p < ∞.
Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). First posted on arXiv 30 Jul 2020.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 5; 2022: 6; 2023: 1; 2024: 1; 2025: 2.
15 papers.
Sort:
- 2023Cross-Entropy Loss Functions: Theoretical Analysis and Applicationscited by 206
- 2021Calibration and Consistency of Adversarial Surrogate Lossescited by 47
- 2021Benign Overfitting in Adversarially Robust Linear Classificationcited by 11
- 2021Provable Robustness of Adversarial Training for Learning Halfspaces with Noisecited by 10
- 2025Towards the Worst-case Robustness of Large Language Modelscited by 7
- 2022Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariatescited by 6
- 2022Robust Empirical Risk Minimization with Tolerancecited by 6
- 2024On the Computability of Robust PAC Learningcited by 6
- 2021Adversarial for Good? How the Adversarial ML Community's Values Impede Socially Beneficial Uses of Attackscited by 5
- 2022Outlier Robust and Sparse Estimation of Linear Regression Coefficientscited by 4
- 2022Algorithms with More Granular Differential Privacy Guaranteescited by 4
- 2021Double-Adversarial Activation Anomaly Detection: Adversarial Autoencoders are Anomaly Generatorscited by 3
3 more
- 2025Robust learning of halfspaces under log-concave marginals19 May 2025
- 2025Towards the Worst-case Robustness of Large Language Models31 Jan 2025
- 2024On the Computability of Robust PAC Learning14 Jun 2024
- 2023Cross-Entropy Loss Functions: Theoretical Analysis and Applications14 Apr 2023
- 2022When are Local Queries Useful for Robust Learning?12 Oct 2022
- 2022Robust Empirical Risk Minimization with Tolerance2 Oct 2022
- 2022Algorithms with More Granular Differential Privacy Guarantees8 Sep 2022
- 2022Outlier Robust and Sparse Estimation of Linear Regression Coefficients24 Aug 2022
- 2022Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariates15 Jun 2022
- 2022mathscrH-Consistency Estimation Error of Surrogate Loss Minimizers16 May 2022
- 2021Benign Overfitting in Adversarially Robust Linear Classification31 Dec 2021
- 2021Adversarial for Good? How the Adversarial ML Community's Values Impede Socially Beneficial Uses of Attacks11 Jul 2021
- 2023Cross-Entropy Loss Functions: Theoretical Analysis and Applicationscited by 206
- 2021Calibration and Consistency of Adversarial Surrogate Lossescited by 47
- 2021Benign Overfitting in Adversarially Robust Linear Classificationcited by 11
- 2021Provable Robustness of Adversarial Training for Learning Halfspaces with Noisecited by 10
- 2025Towards the Worst-case Robustness of Large Language Modelscited by 7
- 2022Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariatescited by 6
- 2022Robust Empirical Risk Minimization with Tolerancecited by 6
- 2024On the Computability of Robust PAC Learningcited by 6
- 2021Adversarial for Good? How the Adversarial ML Community's Values Impede Socially Beneficial Uses of Attackscited by 5
- 2022Outlier Robust and Sparse Estimation of Linear Regression Coefficientscited by 4
- 2022Algorithms with More Granular Differential Privacy Guaranteescited by 4
- 2021Double-Adversarial Activation Anomaly Detection: Adversarial Autoencoders are Anomaly Generatorscited by 3
12 most cited of 15 All 15 (JSON)
- 2025Robust learning of halfspaces under log-concave marginals19 May 2025
- 2025Towards the Worst-case Robustness of Large Language Models31 Jan 2025
- 2024On the Computability of Robust PAC Learning14 Jun 2024
- 2023Cross-Entropy Loss Functions: Theoretical Analysis and Applications14 Apr 2023
- 2022When are Local Queries Useful for Robust Learning?12 Oct 2022
- 2022Robust Empirical Risk Minimization with Tolerance2 Oct 2022
- 2022Algorithms with More Granular Differential Privacy Guarantees8 Sep 2022
- 2022Outlier Robust and Sparse Estimation of Linear Regression Coefficients24 Aug 2022
- 2022Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariates15 Jun 2022
- 2022mathscrH-Consistency Estimation Error of Surrogate Loss Minimizers16 May 2022
- 2021Benign Overfitting in Adversarially Robust Linear Classification31 Dec 2021
- 2021Adversarial for Good? How the Adversarial ML Community's Values Impede Socially Beneficial Uses of Attacks11 Jul 2021
12 newest of 15 All 15 (JSON)