Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barriers

• URL: http://arxiv.org/abs/2604.04228v1
• Date: Sun, 05 Apr 2026 19:07:24 GMT
• Title: Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barriers
• Abstract summary: We study robust regression under a contamination model in which covariates are clean while the responses may be corrupted in an adaptive manner.<n>We show that the additional information can be carefully exploited to construct an estimator that a better estimation rate than achieves that attainable under Huber contamination.<n>Despite the improvement over the Huber model from an information-theoretic perspective, we provide formal evidence that the problem exhibits strong information-computation gaps.
• Score: 65.58071581164043
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study robust regression under a contamination model in which covariates are clean while the responses may be corrupted in an adaptive manner. Unlike the classical Huber's contamination model, where both covariates and responses may be contaminated and consistent estimation is impossible when the contamination proportion is a non-vanishing constant, it turns out that the clean-covariate setting admits strictly improved statistical guarantees. Specifically, we show that the additional information in the clean covariates can be carefully exploited to construct an estimator that achieves a better estimation rate than that attainable under Huber contamination. In contrast to the Huber model, this improved rate implies consistency even when the contamination is a constant. A matching minimax lower bound is established using Fano's inequality together with the construction of contamination processes that match $m> 2$ distributions simultaneously, extending the previous two-point lower bound argument in Huber's setting. Despite the improvement over the Huber model from an information-theoretic perspective, we provide formal evidence -- in the form of Statistical Query and Low-Degree Polynomial lower bounds -- that the problem exhibits strong information-computation gaps. Our results strongly suggest that the information-theoretic improvements cannot be achieved by polynomial-time algorithms, revealing a fundamental gap between information-theoretic and computational limits in robust regression with clean covariates.

Related papers

• Generalised Robust Bayes for Joint Inference of Model and Contamination [12.194688106820815]
  Generalised Bayesian inference (GBI) has emerged as a compelling robust alternative to standard Bayesian inference.<n>This paper introduces Hlder-Bayes, a GBI framework for joint inference of the model parameter and the contamination proportion.<n> Empirical evaluations demonstrate that Hlder-Bayes provides robust parameter inference, contamination-level recovery, and uncertainty-aware outlier detection.
  arXiv  Detail & Related papers  (2026-07-28T12:50:04Z)
• Beyond Consistency: Inference for the Relative risk functional in Deep Nonparametric Cox Models [7.2275111013288535]
  It is unclear how Cox-based optimization error propagates to population risk under partial likelihood.<n>It is also unclear how pointwise bias can be controlled, and how ensemble-based uncertainty behaves under realistic variance regimes.<n>We develop an distribution theory for deep Cox estimators that addresses these issues.
  arXiv  Detail & Related papers  (2026-03-25T01:43:12Z)
• Sharp Convergence Rates for Masked Diffusion Models [53.117058231393834]
  We develop a total-variation based analysis for the Euler method that overcomes limitations.<n>Our results relax assumptions on score estimation, improve parameter dependencies, and establish convergence guarantees.<n>Overall, our analysis introduces a direct TV-based error decomposition along the CTMC trajectory and a decoupling-based path-wise analysis for FHS.
  arXiv  Detail & Related papers  (2026-02-26T00:47:51Z)
• Penalized Empirical Likelihood for Doubly Robust Causal Inference under Contamination in High Dimensions [0.720409153108429]
  We propose a doubly robust estimator for the average treatment effect in low sample size equations.<n>We show that the proposed confidence interval remain efficient compared to those competing estimates.
  arXiv  Detail & Related papers  (2025-07-23T11:58:54Z)
• Robust Score Matching [1.2835555561822447]
  We develop a robust score matching procedure that yields consistent parameter estimates in settings where the observed data has been contaminated.<n>A special appeal of the proposed method is that it retains convexity in exponential family models.<n>Support recovery is studied in numerical experiments and on a precipitation dataset.
  arXiv  Detail & Related papers  (2025-01-09T09:46:27Z)
• Adversarial Purification by Consistency-aware Latent Space Optimization on Data Manifolds [48.37843602248313]
  Deep neural networks (DNNs) are vulnerable to adversarial samples crafted by adding imperceptible perturbations to clean data, potentially leading to incorrect and dangerous predictions.<n>We propose Consistency Model-based Adversarial Purification (CMAP), which optimize vectors within the latent space of a pre-trained consistency model to generate samples for restoring clean data.<n>CMAP significantly enhances robustness against strong adversarial attacks while preserving high natural accuracy.
  arXiv  Detail & Related papers  (2024-12-11T14:14:02Z)
• TIC-TAC: A Framework for Improved Covariance Estimation in Deep Heteroscedastic Regression [109.69084997173196]
  Deepscedastic regression involves jointly optimizing the mean and covariance of the predicted distribution using the negative log-likelihood. Recent works show that this may result in sub-optimal convergence due to the challenges associated with covariance estimation. We study two questions: (1) Does the predicted covariance truly capture the randomness of the predicted mean? Our results show that not only does TIC accurately learn the covariance, it additionally facilitates an improved convergence of the negative log-likelihood.
  arXiv  Detail & Related papers  (2023-10-29T09:54:03Z)
• Mutual Wasserstein Discrepancy Minimization for Sequential Recommendation [82.0801585843835]
  We propose a novel self-supervised learning framework based on Mutual WasserStein discrepancy minimization MStein for the sequential recommendation. We also propose a novel contrastive learning loss based on Wasserstein Discrepancy Measurement.
  arXiv  Detail & Related papers  (2023-01-28T13:38:48Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  Even simple methods like least squares can exhibit non-normal behavior when data is collected in an adaptive manner. We propose a family of online debiasing estimators to correct these distributional anomalies in at least squares estimation. We demonstrate the usefulness of our theory via applications to multi-armed bandit, autoregressive time series estimation, and active learning with exploration.
  arXiv  Detail & Related papers  (2021-07-05T21:05:11Z)
• Robust regression with covariate filtering: Heavy tails and adversarial contamination [6.939768185086755]
  We show how to modify the Huber regression, least trimmed squares, and least absolute deviation estimators to obtain estimators simultaneously computationally and statistically efficient in the stronger contamination model. We show that the Huber regression estimator achieves near-optimal error rates in this setting, whereas the least trimmed squares and least absolute deviation estimators can be made to achieve near-optimal error after applying a postprocessing step.
  arXiv  Detail & Related papers  (2020-09-27T22:48:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.