Research map / Learning theory and algorithms / Sample complexity
Robust Nonparametric Regression under Poisoning Attack
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.
Studies robust nonparametric regression under poisoning attacks, proposing a Huber-loss weighted kernel M-estimator and a Lipschitz-projection correction that is nearly minimax optimal (up to ln N) for l2 and l_inf risk.
Problem
Nonparametric regression where an adversary can arbitrarily modify up to q of N training labels; standard kernel (Nadaraya-Watson) regression and parametric robust methods are not adequate locally.
Approach
A kernel-weighted Huber M-estimator gives a robust local estimate; a nonlinear post-hoc correction projects it onto Lipschitz functions under minimal l1 distance, removing spikes caused by concentrated attacks and achieving near-minimax rates for any q.
Key results
- Initial Huber estimator has minimax-optimal l_infinity rate and optimal l2 rate for small q, but becomes suboptimal for large q under concentrated attacks.
- Corrected (Lipschitz-projected) estimator attains l2 risk (q ln N/N)^((d+2)/(d+1)) + h^2 + ln N/(N h^d), nearly minimax optimal up to ln N for any q.
- In simulations (N=10000, averaged over 1000 trials), kernel regression and median-of-means fail under poisoning, while the corrected estimator performs well across all attack strategies.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Huber-loss initial estimator instead of kernel regression | Nonparametric regression · Synthetic data, random and one-directional attacks | root ℓ2 error | Helped |
| use Huber-loss initial estimator instead of kernel regression | Nonparametric regression · Synthetic data, concentrated attack | root ℓ2 error | Mixed |
| use corrected estimator instead of kernel regression | Nonparametric regression · Synthetic data, all three attack strategies | root ℓ2 error | Helped |
| add Lipschitz-function projection correction to the initial estimate (ablation) | Corrected estimator · Synthetic data, random attack | root ℓ2 error | No clear effect |
| add Lipschitz-function projection correction to the initial estimate (ablation) | Corrected estimator · Synthetic data, one-directional attack with large q | root ℓ2 error | Helped |
| add Lipschitz-function projection correction to the initial estimate (ablation) | Corrected estimator · Synthetic data, concentrated attack | root ℓ2 error | Helped |
| use median-of-means instead of kernel regression | Nonparametric regression · Synthetic data, poisoning attacks | root ℓ2 error | No clear effect |
| use trimmed mean instead of kernel regression | Nonparametric regression · Synthetic data, random or one-directional attack with small q | root ℓ2 error | Helped |
| use trimmed mean instead of kernel regression | Nonparametric regression · Synthetic data, other attack settings | root ℓ2 error | Hurt |
| add Lipschitz-function projection correction to the initial estimate (ablation) | Corrected estimator · Real data, all three attack types | root MSE | Helped |
| increase the Huber estimator's bandwidth to improve robustness | Initial estimator · Large-q poisoning, ℓ2 risk | ℓ2 error | Hurt |
| add Lipschitz-function projection correction to the initial estimate (ablation) | Corrected estimator · Large-q poisoning, ℓ2 risk | ℓ2 error | Helped |
Surprising findings
- Median-of-means does not improve over kernel regression in the experiments.
- The initial Huber estimator fails under concentrated attacks even though it is minimax optimal in l_infinity.
Limitations
- Corrected estimator computationally expensive for high-dimensional inputs; designed mainly for low dimensions.
- Theory relies on strong density assumption (pdf bounded below) for l_infinity and some rate results; l_infinity bound fails without it.
- Parameter choices (e.g., T ~ ln N) required by theory are not exactly used in experiments.
Experimental setup
Datasets: synthetic data (uniform in [0,1]^d, N=10000) real dataset (unspecified in main text)
Benchmarks: synthetic 1D and 2D regression under random, one-directional, and concentrated attacks
Metrics: l2 error (root) l_infinity error
Baselines: Nadaraya-Watson kernel regression median-of-means trimmed mean initial Huber estimator
Builds on: Nadaraya-Watson kernel regression Huber loss median-of-means trimmed mean
Closest papers by meaning
- Adversarial Robustness of Nonparametric Regression (NeurIPS 2025 · similarity 0.89)
- Precise Accuracy / Robustness Tradeoffs in Regression: Case of General Norms (ICML 2024 · similarity 0.85)
- Consistent Adversarially Robust Linear Classification: Non-Parametric Setting (ICML 2024 · similarity 0.85)
- Treatment of Statistical Estimation Problems in Randomized Smoothing for Adversarial Robustness (NeurIPS 2024 · similarity 0.84)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.84)
- On the Optimality of the Median-of-Means Estimator under Adversarial Contamination (NeurIPS 2025 · similarity 0.83)
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.