Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins
Not on the map. Why?
Abstract (arXiv)
We analyze the properties of gradient descent on convex surrogates for the zero-one loss for the agnostic learning of linear halfspaces. If mathsfOPT is the best classification error achieved by a halfspace, by appealing to the notion of soft margins we are able to show that gradient descent finds halfspaces with classification error tilde O(mathsfOPT1/2) + varepsilon in poly(d,1/varepsilon) time and sample complexity for a broad class of distributions that includes log-concave isotropic distributions as a subclass. Along the way we answer a question recently posed by Ji et al. (2020) on how the tail behavior of a loss function can affect sample complexity and runtime guarantees for gradient descent.
Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). First posted on arXiv 1 Oct 2020.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 5; 2022: 3; 2023: 3; 2024: 1; 2025: 0; 2026: 2.
14 papers.
Sort:
- 2022The Implicit Bias of Benign Overfittingcited by 38
- 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
- 2021Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descentcited by 21
- 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
- 2021Self-training Converts Weak Learners to Strong Learners in Mixture Modelscited by 19
- 2021Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noisecited by 17
- 2021Provable Robustness of Adversarial Training for Learning Halfspaces with Noisecited by 10
- 2024Distribution-Specific Auditing For Subgroup Fairnesscited by 4
- 2023What Distributions are Robust to Indiscriminate Poisoning Attacks for Linear Learners?cited by 3
- 2021AdaBoost and robust one-bit compressed sensingcited by 2
- 2022Agnostic Learnability of Halfspaces via Logistic Losscited by 2
- 2023Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approachcited by 1
- 2026Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers18 May 2026
- 2026Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals29 Apr 2026
- 2024Distribution-Specific Auditing For Subgroup Fairness27 Jan 2024
- 2023Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach23 Oct 2023
- 2023What Distributions are Robust to Indiscriminate Poisoning Attacks for Linear Learners?3 Jul 2023
- 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization2 Mar 2023
- 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descent17 Jun 2022
- 2022Agnostic Learnability of Halfspaces via Logistic Loss31 Jan 2022
- 2022The Implicit Bias of Benign Overfitting27 Jan 2022
- 2021Self-training Converts Weak Learners to Strong Learners in Mixture Models25 Jun 2021
- 2021Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent25 Jun 2021
- 2021AdaBoost and robust one-bit compressed sensing5 May 2021
- 2022The Implicit Bias of Benign Overfittingcited by 38
- 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
- 2021Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descentcited by 21
- 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
- 2021Self-training Converts Weak Learners to Strong Learners in Mixture Modelscited by 19
- 2021Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noisecited by 17
- 2021Provable Robustness of Adversarial Training for Learning Halfspaces with Noisecited by 10
- 2024Distribution-Specific Auditing For Subgroup Fairnesscited by 4
- 2023What Distributions are Robust to Indiscriminate Poisoning Attacks for Linear Learners?cited by 3
- 2021AdaBoost and robust one-bit compressed sensingcited by 2
- 2022Agnostic Learnability of Halfspaces via Logistic Losscited by 2
- 2023Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approachcited by 1
12 most cited of 14 All 14 (JSON)
- 2026Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers18 May 2026
- 2026Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals29 Apr 2026
- 2024Distribution-Specific Auditing For Subgroup Fairness27 Jan 2024
- 2023Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach23 Oct 2023
- 2023What Distributions are Robust to Indiscriminate Poisoning Attacks for Linear Learners?3 Jul 2023
- 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization2 Mar 2023
- 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descent17 Jun 2022
- 2022Agnostic Learnability of Halfspaces via Logistic Loss31 Jan 2022
- 2022The Implicit Bias of Benign Overfitting27 Jan 2022
- 2021Self-training Converts Weak Learners to Strong Learners in Mixture Models25 Jun 2021
- 2021Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent25 Jun 2021
- 2021AdaBoost and robust one-bit compressed sensing5 May 2021
12 newest of 14 All 14 (JSON)