# Robust learning of halfspaces under log-concave marginals

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

## Key facts

- Cited by 2 papers in the map (data through 7 Oct 2026).
- Builds on 20 of its 37 references that are in the map.
- First posted on arXiv 19 May 2025.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [Planting Undetectable Backdoors in Machine Learning Models](https://mlsanity.com/paper/2204.06974/) (2022)
- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity](https://mlsanity.com/paper/2211.13312/) (2022)
- [On the Hardness of Robust Classification](https://mlsanity.com/paper/1909.05822/) (2019)
- [Efficiently Learning Adversarially Robust Halfspaces with Noise](https://mlsanity.com/paper/2005.07652/) (2020)
- [A PTAS for Agnostically Learning Halfspaces](https://mlsanity.com/paper/1410.7050/) (2014)
- [Agnostic Proper Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2102.05629/) (2021)
- [The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise](https://mlsanity.com/paper/2007.15220/) (2020)
- [On Robustness to Adversarial Examples and Polynomial Optimization](https://mlsanity.com/paper/1911.04681/) (2019)
- [Computational Limitations in Robust Classification and Win-Win Results](https://mlsanity.com/paper/1902.01086/) (2019)
- [Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin](https://mlsanity.com/paper/1908.11335/) (2019)
- [Properly learning monotone functions via local reconstruction](https://mlsanity.com/paper/2204.11894/) (2022)

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

- [Learning and Testing Convex Functions](https://mlsanity.com/paper/2511.11498/) (2025)
- [Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2605.27594/) (2026)

## Abstract (arXiv)

We say that a classifier is adversarially robust to perturbations of norm r if, with high probability over a point x drawn from the input distribution, there is no point within distance ≤ r from x that is classified differently. The boundary volume is the probability that a point falls within distance r of a point with a different label. This work studies the task of computationally efficient learning of hypotheses with small boundary volume, where the input is distributed as a subgaussian isotropic log-concave distribution over ℝd. Linear threshold functions are adversarially robust; they have boundary volume proportional to r. Such concept classes are efficiently learnable by polynomial regression, which produces a polynomial threshold function (PTF), but PTFs in general may have boundary volume Omega(1), even for r ll 1. We give an algorithm that agnostically learns linear threshold functions and returns a classifier with boundary volume O(r+varepsilon) at radius of perturbation r. The time and sample complexity of d^tildeO(1/varepsilon2) matches the complexity of polynomial regression. Our algorithm augments the classic approach of polynomial regression with three additional steps: a) performing the ℓ1-error regression under noise sensitivity constraints, b) a structured partitioning and rounding step that returns a Boolean classifier with error textsfopt + O(varepsilon) and noise sensitivity O(r+varepsilon) simultaneously, and c) a local corrector that ``smooths'' a function with low noise sensitivity into a function that is adversarially robust.