Robust learning of halfspaces under log-concave marginals

2025/05/19 by Jane Lange, Lange, Jane, Arsen Vasilyan +1 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine Learning and ELM

paper · pdf · doi:10.48550/arxiv.2505.13708

openalex publication_date 2025/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 Ω(1), even for r ≪ 1. We give an algorithm that agnostically learns linear threshold functions and returns a classifier with boundary volume O(r+ε) at radius of perturbation r. The time and sample complexity of d^O(1/ε²) matches the complexity of polynomial regression. Our algorithm augments the classic approach of polynomial regression with three additional steps: a) performing the ℓ₁-error regression under noise sensitivity constraints, b) a structured partitioning and rounding step that returns a Boolean classifier with error \textsfopt + O(ε) and noise sensitivity O(r+ε) simultaneously, and c) a local corrector that ``smooths'' a function with low noise sensitivity into a function that is adversarially robust.

Citations

• A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
• Properly learning monotone functions via local reconstruction
• Planting Undetectable Backdoors in Machine Learning Models
• Agnostic Proper Learning of Halfspaces under Gaussian Marginals
• The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise
• Efficiently Learning Adversarially Robust Halfspaces with Noise
• On Robustness to Adversarial Examples and Polynomial Optimization
• On the Hardness of Robust Classification
• Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin
• VC Classes are Adversarially Robustly Learnable, but Only Improperly
• Certified Adversarial Robustness via Randomized Smoothing
• Computational Limitations in Robust Classification and Win-Win Results
• The total variation distance between high-dimensional Gaussians with the same mean
• Adversarial examples from computational constraints
• Certified Robustness to Adversarial Examples with Differential Privacy
• Learning Geometric Concepts with Nasty Noise
• Explaining and Harnessing Adversarial Examples
• A PTAS for Agnostically Learning Halfspaces
• Log-concavity and strong log-concavity: a review
• Intriguing properties of neural networks
• Space-efficient Local Computation Algorithms
• Fast Local Computation Algorithms
• Interpolating Thin-Shell and Sharp Large-Deviation Estimates For Isotropic Log-Concave Measures
• A concentration theorem for projections

Cited by

• Learning and Testing Convex Functions

Related

• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
• Provable Robustness of Adversarial Training for Learning Halfspaces with\n Noise
• Reliable Learning of Halfspaces under Gaussian Marginals
• A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
• Hardness of learning noisy halfspaces using polynomial thresholds