Abstract

Pervasive data contamination—stemming from measurement errors, outliers, or

adversarial corruption—has motivated the development of robust statistical methods. In

this context, we propose a two-stage Adversarial Contamination-resistant Iterative Hard

Thresholding (AC-IHT) algorithm for high-dimensional regression with contamination. Our

nonconvex algorithm achieves minimax near-optimal (up to logarithmic terms) estimation

by iteratively updating the coefficient vector and the contamination vector with different

thresholding scales. We further demonstrate that our AC-IHT estimator is signal-adaptive:

under proper signal conditions, it adaptively attains a sharper estimation rate and more

accurate support recovery. Moreover, it enjoys the strong oracle property, laying a theoretical

foundation for asymptotic inference. Numerical experiments confirm its superior finitesample performance. Finally, we discuss theoretical extensions of the proposed procedure to

generalized linear models and to heavy-tailed noise settings.

Key words and phrases: Adversarial contamination, Iterative hard thresholding, Non-convex optimization, Signal adaptivity, Strong oracle property

Information

Preprint No.SS-2025-0224
Manuscript IDSS-2025-0224
Complete AuthorsShixiang Liu, Hanming Yang
Corresponding AuthorsHanming Yang
Emailsyanghanming@ruc.edu.cn

References

  1. Abramovich, F. and V. Grinshtein (2016). Model selection and minimax estimation in generalized linear models. IEEE Transactions on Information Theory 62(6), 3721 – 3730.
  2. Bellec, P. C. (2018). The noise barrier and the large signal bias of the lasso and other convex estimators. arXiv preprint arXiv:1804.01230.
  3. Bhatia, K., P. Jain, P. Kamalaruban, and P. Kar (2017). Consistent robust regression. In I. Guyon, U. V.
  4. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Advances in
  5. Neural Information Processing Systems, Volume 30. Curran Associates, Inc.
  6. Bhatia, K., P. Jain, and P. Kar (2015). Robust regression via hard thresholding. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (Eds.), Advances in Neural Information Processing Systems, Volume 28. Curran Associates, Inc.
  7. Blumensath, T. and M. E. Davies (2008). Iterative thresholding for sparse approximations. Journal of Fourier Analysis and Applications 14(5), 629 – 654.
  8. Blumensath, T. and M. E. Davies (2009). Iterative hard thresholding for compressed sensing. Applied and Computational Harmonic Analysis 27(3), 265 – 274.
  9. Butucea, C., M. Ndaoud, N. A. Stepanova, and A. B. Tsybakov (2018). Variable selection with Hamming loss. The Annals of Statistics 46(5), 1837 – 1875.
  10. Chen, M., C. Gao, and Z. Ren (2016). A general decision theory for Huber’s ϵ-contamination model. Electronic Journal of Statistics 10(2), 3752 – 3774.
  11. Chen, M., C. Gao, and Z. Ren (2018). Robust covariance and scatter matrix estimation under Huber’s contamination model. The Annals of Statistics 46(5), 1932 – 1960.
  12. Chen, Y., J. Fan, C. Ma, and Y. Yan (2021). Bridging convex and nonconvex optimization in robust pca: Noise, outliers, and missing data. The Annals of statistics 49(5), 2948 – 2971.
  13. Chinot, G. (2020). ERM and RERM are optimal estimators for regression problems when malicious outliers corrupt the labels. Electronic Journal of Statistics 14(2), 3563 – 3605.
  14. Dalalyan, A. and P. Thompson (2019). Outlier-robust estimation of a sparse linear model using ℓ1-penalized Huber's m-estimator. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (Eds.), Advances in Neural Information Processing Systems, Volume 32. Curran Associates, Inc.
  15. Efron, B., T. Hastie, I. Johnstone, and R. Tibshirani (2004). Least angle regression. The Annals of Statistics 32(2), 407 – 499.
  16. Fan, J., H. Liu, Q. Sun, and T. Zhang (2018). I-LAMM for sparse learning: Simultaneous control of algorithmic complexity and statistical error. The Annals of Statistics 46(2), 814 – 841.
  17. Fan, J., Z. Yang, and M. Yu (2023). Understanding implicit regularization in over-parameterized single index model. Journal of the American Statistical Association 118(544), 2315 – 2328.
  18. Finocchio, G., A. Derumigny, and K. Proksch (2021). Robust-to-outliers square-root lasso, simultaneous inference with a mom approach. arXiv preprint arXiv:2103.10420.
  19. Gannaz, I. (2007). Robust estimation and wavelet thresholding in partially linear models. Statistics and Computing 17, 293 – 310.
  20. Gao, C. (2020). Robust regression via mutivariate regression depth. Bernoulli 26(2), 1139 – 1170.
  21. Goldsmith-Pinkham, P., P. Hull, and M. Kolesár (2024). Contamination bias in linear regressions. American Economic Review 114(12), 4015 – 4051.
  22. Hammouda, I., M. Ndaoud, and A.-K. Seghouane (2024). Outlier-bias removal with alpha divergence: A robust non-convex estimator for linear regression. arXiv preprint arXiv:2412.19183.
  23. Han, R., L. Luo, Y. Luo, Y. Lin, and J. Huang (2026). Adaptive debiased lasso in high-dimensional generalized linear models with streaming data. Journal of the American Statistical Association 0(ja), 1 – 19.
  24. Heng, A. and H. Soh (2025). Detecting covariate shifts with vision-language foundation models. In ICLR 2025 Workshop on Foundation Models in the Wild.
  25. Huang, J., Y. Jiao, Y. Liu, and X. Lu (2018). A constructive approach to l0 penalized regression. Journal of Machine Learning Research 19(10), 1 – 37.
  26. Jain, P., A. Tewari, and P. Kar (2014). On iterative hard thresholding methods for high-dimensional m-estimation. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger (Eds.), Advances in Neural Information Processing Systems, Volume 27. Curran Associates, Inc.
  27. Kong, D., H. D. Bondell, and Y. Wu (2018). Fully efficient robust estimation, outlier detection and variable selection via penalized regression. Statistica Sinica 28(2), 1031 – 1052.
  28. Lee, Y., S. N. MacEachern, and Y. Jung (2012). Regularization of Case-Specific Parameters for Robustness and Efficiency. Statistical Science 27(3), 350 – 372.
  29. Liu, H. and R. Foygel Barber (2019). Between hard and soft thresholding: optimal iterative thresholding algorithms. Information and Inference: A Journal of the IMA 9(4), 899 – 933.
  30. Loh, P.-L. (2025). A theoretical review of modern robust statistics. Annual Review of Statistics and Its Application 12, 477 – 496.
  31. Minsker, S., M. Ndaoud, and L. Wang (2024). Robust and tuning-free sparse linear regression via square-root slope. SIAM Journal on Mathematics of Data Science 6(2), 428 – 453.
  32. Minsker, S. and Y. Shen (2025). The impact of contamination and correlated design on the lasso: An average case analysis. Statistics & Probability Letters 223, 110417.
  33. Ndaoud, M. (2019). Interplay of minimax estimation and minimax support recovery under sparsity. In A. Garivier and S. Kale (Eds.), Proceedings of the 30th International Conference on Algorithmic Learning Theory, Volume 98 of Proceedings of Machine Learning Research, pp. 647 – 668. PMLR.
  34. Ndaoud, M. (2020). Scaled minimax optimality in high-dimensional linear regression: A non-convex algorithmic regularization approach. arXiv preprint arXiv:2008.12236.
  35. Nguyen, N. H. and T. D. Tran (2013). Robust lasso with missing and grossly corrupted observations. IEEE Transactions on Information Theory 59(4), 2036 – 2058.
  36. Pensia, A., V. Jog, and P.-L. Loh (2025). Robust regression with covariate filtering: Heavy tails and adversarial contamination. Journal of the American Statistical Association 120(550), 1002 – 1013.
  37. Raskutti, G., M. J. Wainwright, and B. Yu (2011). Minimax rates of estimation for high-dimensional linear regression over ℓq-balls. IEEE Transactions on Information Theory 57(10), 6976 – 6994.
  38. Sardy, S., P. Tseng, and A. Bruce (2001). Robust wavelet denoising. IEEE Transactions on Signal Processing 49(6), 1146 – 1152.
  39. Sasai, T. and H. Fujisawa (2020). Robust estimation with lasso when outputs are adversarially contaminated. arXiv preprint arXiv:2004.05990.
  40. Sasai, T. and H. Fujisawa (2025). Outlier robust and sparse estimation of linear regression coefficients. Journal of Machine Learning Research 26(93), 1 – 79.
  41. She, Y. and A. B. Owen (2011). Outlier detection using nonconvex penalized regression. Journal of the American Statistical Association 106(494), 626 – 639.
  42. She, Y., J. Shen, and A. Barbu (2023). Slow kill for big data learning. IEEE Transactions on Information Theory 69(9), 5936 – 5955.
  43. She, Y., Z. Wang, and J. Jin (2021). Analysis of generalized Bregman surrogate algorithms for nonsmooth nonconvex statistical learning. The Annals of Statistics 49(6), 3434 – 3459.
  44. She, Y., Z. Wang, and J. Shen (2022). Gaining outlier resistance with progressive quantiles: Fast algorithms and theoretical studies. Journal of the American Statistical Association 117(539), 1282 – 1295.
  45. Shen, Y., J. Li, J.-F. Cai, and D. Xia (2025). Computationally efficient and statistically optimal robust high-dimensional linear regression. The Annals of Statistics 53(1), 374 – 399.
  46. Suggala, A. S., K. Bhatia, P. Ravikumar, and P. Jain (2019). Adaptive hard thresholding for near-optimal consistent robust regression. In A. Beygelzimer and D. Hsu (Eds.), Proceedings of the Thirty-Second Conference on Learning Theory, Volume 99 of Proceedings of Machine Learning Research, pp. 2892 – 2897. PMLR.
  47. Sun, Q., W.-X. Zhou, and J. Fan (2020). Adaptive Huber regression. Journal of the American Statistical Association 115(529), 254 – 265.
  48. Thompson, P. (2020). Outlier-robust sparse/low-rank least-squares regression and robust matrix completion. arXiv preprint arXiv:2012.06750. Shixiang Liu

Acknowledgments

The authors would like to thank the editor, associate editor, and reviewers for

their helpful comments. We are also grateful to Dr. Zhifan Li and Dr. Jie Li for

their constructive discussions.

Supplementary Materials

The online supplementary materials contain the additional numerical experiments

and all detailed proofs of our results.

Supplementary materials are available for download.