Research map / Adversarial robustness and security / Certified and empirical robustness
Consistent Adversarially Robust Linear Classification: Non-Parametric Setting
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a smoothed adversarial 0/1 loss estimator for linear classifiers with a sample-size- and dimension-adaptive bandwidth, proving consistency for adversarial risk under arbitrary norms in a non-parametric setting and near-minimax rates.
Problem
Learning adversarially robust linear binary classifiers without parametric or well-separation assumptions on the data distribution; the adversarial 0/1 loss is discontinuous and has no Bayes-consistent convex surrogate.
Approach
Minimize the empirical adversarial risk with the discontinuous margin loss replaced by a smoothed surrogate Q((u-eps)/h), where the bandwidth h_n shrinks with n and d, yielding a non-convex but smooth optimization problem with provable adversarial-risk consistency and rates close to sqrt(d/n).
Key results
- Theory: adversarial regret of the smoothed estimator is O(lambda(h_n) + sqrt(d log n / n)), giving O~(sqrt(d/n)) rate under Gaussian-tail smoothing and a small-ball assumption, which matches the non-parametric minimax rate for classification.
- Experiments on synthetic Gaussian data (d=20, n up to 10000) show adversarial risk approaching the Bayes-optimal linear adversarial risk as n grows, for Euclidean attacks with several strengths.
- Fixed-bandwidth estimator of Bao et al. (h=1) fails to be consistent on a 2D Gaussian example where sigma1=1, sigma2=0.1, while the adaptive-bandwidth estimator is consistent.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Choose the smoothing bandwidth as hn ≍ η⁻¹(√(d log n/n))^(1+Ω(1)) | Smoothed adversarial risk estimator · Non-parametric linear classification, arbitrary attack strength | excess adversarial risk: O(√(d log n/n)) | Helped |
| Adapt the smoothing bandwidth to sample size and dimension instead of using fixed h = 1 | Smoothed adversarial risk estimator · Two-dimensional Gaussian experiment | adversarial regret | Helped |
| Increase sample size n | Smoothed adversarial risk estimator · Gaussian and non-Gaussian experiments | adversarial risk | Helped |
Surprising findings
- Fixed-bandwidth smoothing (Bao et al. 2020) is inconsistent in a simple 2D Gaussian example, so static surrogates are not enough and the bandwidth must shrink with n.
Limitations
- Only stationary points are guaranteed by the optimizer; global optimality is observed empirically but not proven.
- Results are restricted to linear models; extension to neural networks is left open.
- Consistency requires a small-ball/regularity assumption on the conditional feature distribution, and rates depend on the function eta in that assumption.
Experimental setup
Datasets: synthetic Gaussian mixture data synthetic ReLU random-features data 2D Gaussian twonorm-style data
Benchmarks: synthetic Gaussian mixture experiment (d=20) synthetic non-Gaussian ReLU random features experiment
Metrics: adversarial risk adversarial regret
Baselines: Bao et al. 2020 fixed-bandwidth smoothed estimator (h=1) Bayes-optimal adversarial risk for linear models
Builds on: Bao et al. 2020 sigmoid-based robust surrogate Bhattacharjee et al. 2021 max-margin robust classifier Dan et al. 2020 Gaussian mixture robust classification Vapnik-Chervonenkis uniform convergence
Closest papers by meaning
- The Adversarial Consistency of Surrogate Risks for Binary Classification (NeurIPS 2023 · similarity 0.92)
- On the Existence of Consistent Adversarial Attacks in High-Dimensional Linear Classification (ICML 2026 · similarity 0.91)
- Sharp Statistical Guaratees for Adversarially Robust Gaussian Classification (ICML 2020 · similarity 0.90)
- When are Non-Parametric Methods Robust? (ICML 2020 · similarity 0.90)
- Adversarial Robustness of Nonparametric Regression (NeurIPS 2025 · similarity 0.90)
- Treatment of Statistical Estimation Problems in Randomized Smoothing for Adversarial Robustness (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.