Research map / Adversarial robustness and security / Certified and empirical robustness
Adversarial Robustness of Nonparametric Regression
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.
Shows that cubic smoothing splines are robust to adversarial response corruption in second-order Sobolev regression (vanishing error when q=o(n)), and gives matching minimax lower bounds showing linear corruption makes consistent estimation impossible.
Problem
Estimating a nonparametric regression function in the second-order Sobolev space when an adversary can arbitrarily corrupt up to q of n responses, measured by worst-case L2 and L-infinity errors.
Approach
Shows the classical cubic smoothing spline, with proper regularization lambda, is adversarially robust by bounding the deviation from its clean-data counterpart via the equivalent-kernel approximation of the smoothing spline weights, and pairs this with a two-function hypothesis-testing lower bound.
Key results
- Cubic smoothing spline achieves R_2 and R_infinity -> 0 when q = o(n) under the stated lambda choices (e.g., lambda=(q/n)^{4/3} for q>=n^{0.4}).
- Minimax lower bounds of order (q/n)^3 + n^{-4/5} for R_2 and (q/n)^2 + (log n/n)^{3/4} for R_infinity imply no estimator is consistent when q = Theta(n).
- Experiments on f(x)=x sin x and an MLP target show empirical rates consistent with the upper bounds, with the concentrated attack causing the largest error.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use cubic smoothing splines under q = Θ(n^β), with β ≤ 0.4 | Second-order Sobolev regression · Adversarial corruption | R₂: O(n^{-4/5}) | Helped |
| Increase corruption scaling to q = Θ(n^β), β > 0.4 | Cubic smoothing spline · Second-order Sobolev regression | R₂ convergence rate: O(n^{-4/5}) -> O(n^{-4/3(1-β)}) | Hurt |
| Use cubic smoothing splines under q = Θ(n^β), with β ≤ 0.5 | Second-order Sobolev regression · Adversarial corruption | R∞: O(n^{-3/5}) | Helped |
| Increase corruption scaling to q = Θ(n^β), β > 0.5 | Cubic smoothing spline · Second-order Sobolev regression | R∞ convergence rate: O(n^{-3/5}) -> O(n^{-6/5(1-β)}) | Hurt |
| Use concentrated corruption instead of random or greedy corruption | Cubic smoothing spline · Regression experiments under uniform and Gaussian designs | Estimation error | Hurt |
| Allow q = o(n) adversarially corrupted samples | Cubic smoothing spline · Second-order Sobolev regression | R₂ and R∞: R₂ → 0; R∞ → 0 | Helped |
| Allow q = Θ(n) adversarially corrupted samples | Any estimator · Second-order Sobolev regression | R₂ and R∞ | Hurt |
Surprising findings
- Classical smoothing splines are optimal in terms of the maximum tolerable number of corruptions, despite Nadaraya-Watson being fragile to a single corruption.
Limitations
- Empirical rates are not expected to match the minimax lower bounds, which concern worst-case functions.
- Gap between achieved rates and minimax outer bounds for intermediate corruption levels (log_n q between 2/5 and 1 for R_2).
Experimental setup
Datasets: synthetic regression data (f(x)=x sin x; three-layer MLP target)
Metrics: R_2 risk R_infinity risk empirical convergence rate
Baselines: Nadaraya-Watson estimator Zhao et al. M-estimator NW variant
Builds on: smoothing spline theory equivalent kernel approximation (Silverman) Zhao et al. adversarial kernel regression
Closest papers by meaning
- Consistent Adversarially Robust Linear Classification: Non-Parametric Setting (ICML 2024 · similarity 0.90)
- Robust Nonparametric Regression under Poisoning Attack (AAAI 2024 · similarity 0.89)
- Precise Accuracy / Robustness Tradeoffs in Regression: Case of General Norms (ICML 2024 · similarity 0.88)
- Treatment of Statistical Estimation Problems in Randomized Smoothing for Adversarial Robustness (NeurIPS 2024 · similarity 0.88)
- Certified Adversarial Robustness via Randomized $\alpha$-Smoothing for Regression Models (NeurIPS 2024 · similarity 0.88)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.86)
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.