Research map / Adversarial robustness and security / Certified and empirical robustness
Precise Accuracy / Robustness Tradeoffs in Regression: Case of General Norms
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.
Derives near-exact formulas for the optimal adversarial risk of accurate linear regression models under general attack norms and feature covariances, showing when robustness is free versus when a tradeoff with accuracy is unavoidable.
Problem
How small can the adversarial (test-time attack) risk of a linear regression model be while keeping its standard risk within a given tolerance, for arbitrary attack norms and feature covariance matrices?
Approach
Shows that the optimal robust model is a regularized estimate of the generative model (proximal operator with ridge parameter λ = r^2, or λopt(r, ϵ) under an accuracy constraint), with multiplicative-constant characterizations of the optimal adversarial risk via Lagrangian duality rather than Gordon's comparison inequality, valid for general norms and covariances.
Key results
- Theorem 3.1: with ridge-type parameter λ = r^2, the proximal estimator attains the optimal adversarial risk up to absolute constants for any attack norm.
- Free lunch threshold for isotropic Euclidean attacks is ϵFL(r) = r^2/(1+r^2), so no accuracy-robustness tradeoff is needed above this excess-risk level.
- For polynomial spectral decay with δ in (0,1], accurate models (ϵ > 0) are non-robust (Eopt(r, ϵ) = Θ(1)) while robustness is achievable (Eopt(r) = o(1)); δ = 1 marks a phase transition.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the regularized model wprox(r²) instead of an arbitrary linear model | Linear regression under general attack norms and covariance matrices · General-norm attacks | adversarial risk | Helped |
| Allow excess standard-risk tolerance ε at least εFL(r) | Linear regression under general attack norms and covariance matrices · General-norm attacks | adversarial risk | Helped |
| Increase the excess standard-risk tolerance below the free-lunch threshold | Linear regression under general attack norms and covariance matrices · General-norm attacks | adversarial risk | Mixed |
| Use a regularized estimate of the generative model, with λ = λopt(r, ϵ) | Linear regression under general attack norms and covariance matrices · Accuracy-constrained robustness | adversarial risk | Helped |
| Use the generative model w0 rather than the optimally robust model | Sparse ground truth with isotropic covariance and ℓp attacks · Sparse ground truth; p ∈ [1, ∞), r ≍ 1/s1/q, or p = ∞, r ≍ 1/s | adversarial risk: Eopt(r) = od(1), and Eopt(r, ϵ) = Θ((1 − ϵ)²) | Hurt |
| Require excess-risk tolerance ε < 1 for polynomially decaying spectral conditions with δ ∈ [0, 1] | Linear regression with Euclidean-norm attacks · Polynomial spectral decay, 0 ≤ δ ≤ 1 | adversarial risk: Eopt(r) = o(1), Eopt(r, ϵ) = Θ(1) | Mixed |
| Use a smooth ground-truth model with source exponent δ > 1 | Linear regression with Euclidean-norm attacks · Polynomial spectral decay, δ > 1 | robustness-accuracy tradeoff: δ = 1 | Helped |
| Use the generative model w0 rather than the optimal robust model | Linear regression with Euclidean-norm attacks · Polynomial spectral decay, 0 ≤ δ < 1 | adversarial risk: Eopt(r) = σ² + r²(1−θ); E(w0, r, ϵ) = Θ(1) | Hurt |
| Use the generative model w0 rather than the optimal robust model | Linear regression with ℓ∞ attacks · Harmonic ground truth, Σ = Id, 1/√d ≤ r = o(1) | adversarial risk: Eopt(r) ≍ σ² + r² log(1/r)² | Hurt |
| Use the regularized model rather than the generative model for well-conditioned problems at small attack strengths | Linear regression under general attack norms · Well-conditioned problems | adversarial risk | No clear effect |
Surprising findings
- The generative model w0 itself can be non-robust under small imperceptible attacks in non-smooth regimes, including in estimated kernel-regime neural networks on MNIST and FashionMNIST (δ ≈ 0.038 and 0.16).
Limitations
- Results are asymptotic (d to infinity) and hold up to absolute multiplicative constants.
- Analysis is restricted to linear models and Gaussian features; extension to neural networks is left as a heuristic kernel-regime argument.
- Some bounds become vacuous in ill-conditioned settings (large η0), e.g., polynomial decay with δ slightly above 1.
Experimental setup
Datasets: simulated Gaussian linear regression data
Benchmarks: simulated linear regression experiments (sparse ground truth, polynomial spectral decay, harmonic ground truth)
Metrics: adversarial risk standard excess risk
Baselines: Xing et al. 2021 ridge characterization Javanmard et al. 2020 isotropic Pareto curves ordinary least squares estimator
Builds on: Scetbon & Dohmatob 2023 Xing et al. 2021 Javanmard et al. 2020 Javanmard & Soltanolkotabi 2022
Closest papers by meaning
- Understanding and Mitigating the Tradeoff between Robustness and Accuracy (ICML 2020 · similarity 0.91)
- Theoretically Principled Trade-off between Robustness and Accuracy (ICML 2019 · similarity 0.91)
- Robustness May Be at Odds with Accuracy (ICLR 2019 · similarity 0.90)
- Fantastic Robustness Measures: The Secrets of Robust Generalization (NeurIPS 2023 · similarity 0.90)
- Adversarial Robustness of Nonparametric Regression (NeurIPS 2025 · similarity 0.88)
- On the Alignment between Fairness and Accuracy: from the Perspective of Adversarial Robustness (ICML 2025 · similarity 0.88)
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.