Research map / Learning theory and algorithms / Sample complexity

Robustness Auditing for Linear Regression: To Singularity and Beyond

ICLR 2025 · Learning theory and algorithms › Sample complexity · approach: Coresets and sublinear estimation · 0 citations (OpenAlex)

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 ACRE and OHARE, efficient algorithms that give provably valid upper and lower bounds on the number of sample removals needed to shift an OLS coefficient, including one-hot-aware certification for econometrics datasets.

Problem

Certifying the robustness of OLS regression coefficients to removal of a small number of samples, where exact computation is combinatorially intractable and prior methods give only upper bounds or fail with one-hot encoded categorical features.

Approach

Decompose the effect of sample removal on OLS into a first-order term plus a higher-order correction, bound the correction via maximal subset sum norm (MSN) problems solved with Gram-matrix triangle-inequality bounds, and for one-hot features reparametrize via Gram-Schmidt "reaveraging" and combine per-bucket bounds with dynamic programming.

Key results

• On Nightlights (d=209), OHARE certifies that removing 28 or fewer samples cannot flip the sign, versus AMIP's upper bound of 136 and KZC21's 110.
• Across 13 benchmark regressions from econometrics studies, OHARE lower bounds are often 2-3x below AMIP/KZC upper bounds where no nontrivial lower bounds were previously known; e.g., OHIE Health genflip 77 vs 257.
• Theory: under well-behaved distributions, ACRE's upper/lower bound ratio is 1 + Õ((d + k√d)/n), and OHARE's is 1 + O(1/√log n).

Measured effects reported in the paper

Surprising findings

• Continuous-feature certification (ACRE) can only certify robustness to about 7 removals on the Nightlights dataset because of a country with only 8 samples, so one-hot-aware analysis is required.
• Replacing a heavy-tailed land-ownership column with a log transform substantially improved certifiable robustness in the Cash Transfer study, since a few households dominated variance.

Limitations

• Bounds are not tight on datasets with very small one-hot buckets or heavy-tailed features, where the singular-covariance analysis degrades.
• Tightness guarantees rely on distributional assumptions (well-behaved features, Gaussian noise), not general data.
• Only OLS is treated; extension to logistic regression, LASSO and other convex losses is left open.

Experimental setup

Datasets: Nightlights (Martinez) Cash Transfer (Angelucci and De Giorgi) Oregon Health Insurance Experiment (OHIE) synthetic Gaussian linear regression data

Benchmarks: Nightlights regression Cash Transfer regressions OHIE regressions synthetic dataset n=4000 d=50

Metrics: k_sign lower bound upper/lower bound ratio runtime memory

Baselines: AMIP KZC21 Freund and Hopkins spectral bound

Builds on: AMIP Freund and Hopkins spectral bound resilience

Closest papers by meaning

• Precise Accuracy / Robustness Tradeoffs in Regression: Case of General Norms (ICML 2024 · similarity 0.85)
• Robust Conformal Outlier Detection under Contaminated Reference Data (ICML 2025 · similarity 0.84)
• Adversarial Robustness of Nonparametric Regression (NeurIPS 2025 · similarity 0.84)
• Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.84)
• Beyond the Norms: Detecting Prediction Errors in Regression Models (ICML 2024 · similarity 0.83)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination (NeurIPS 2025 · similarity 0.83)