Adversarial Robustness of Nonparametric Regression

• URL: http://arxiv.org/abs/2505.17356v1
• Date: Fri, 23 May 2025 00:18:20 GMT
• Title: Adversarial Robustness of Nonparametric Regression
• Authors: Parsa Moradi, Hanzaleh Akabrinodehi, Mohammad Ali Maddah-Ali,
• Abstract summary: We characterize the adversarial robustness in nonparametric regression, assuming the regression function belongs to the second-order Sobolev space.<n>We show that, perhaps surprisingly, the classical smoothing spline estimator, when properly regularized, exhibits robustness against adversarial corruption.
• Score: 14.20104019605888
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we investigate the adversarial robustness of regression, a fundamental problem in machine learning, under the setting where an adversary can arbitrarily corrupt a subset of the input data. While the robustness of parametric regression has been extensively studied, its nonparametric counterpart remains largely unexplored. We characterize the adversarial robustness in nonparametric regression, assuming the regression function belongs to the second-order Sobolev space (i.e., it is square integrable up to its second derivative). The contribution of this paper is two-fold: (i) we establish a minimax lower bound on the estimation error, revealing a fundamental limit that no estimator can overcome, and (ii) we show that, perhaps surprisingly, the classical smoothing spline estimator, when properly regularized, exhibits robustness against adversarial corruption. These results imply that if $o(n)$ out of $n$ samples are corrupted, the estimation error of the smoothing spline vanishes as $n \to \infty$. On the other hand, when a constant fraction of the data is corrupted, no estimator can guarantee vanishing estimation error, implying the optimality of the smoothing spline in terms of maximum tolerable number of corrupted samples.

Related papers

• Multivariate root-n-consistent smoothing parameter free matching estimators and estimators of inverse density weighted expectations [51.000851088730684]
  We develop novel modifications of nearest-neighbor and matching estimators which converge at the parametric $sqrt n $-rate.<n>We stress that our estimators do not involve nonparametric function estimators and in particular do not rely on sample-size dependent parameters smoothing.
  arXiv  Detail & Related papers  (2024-07-11T13:28:34Z)
• Robust deep learning from weakly dependent data [0.0]
  This paper considers robust deep learning from weakly dependent observations, with unbounded loss function and unbounded input/output. We derive a relationship between these bounds and $r$, and when the data have moments of any order (that is $r=infty$), the convergence rate is close to some well-known results.
  arXiv  Detail & Related papers  (2024-05-08T14:25:40Z)
• Byzantine-resilient Federated Learning With Adaptivity to Data Heterogeneity [54.145730036889496]
  This paper deals with Gradient learning (FL) in the presence of malicious attacks Byzantine data. A novel Average Algorithm (RAGA) is proposed, which leverages robustness aggregation and can select a dataset.
  arXiv  Detail & Related papers  (2024-03-20T08:15:08Z)
• Asymptotic Characterisation of Robust Empirical Risk Minimisation Performance in the Presence of Outliers [18.455890316339595]
  We study robust linear regression in high-dimension, when both the dimension $d$ and the number of data points $n$ diverge with a fixed ratio $alpha=n/d$, and study a data model that includes outliers. We provide exacts for the performances of the empirical risk minimisation (ERM) using $ell$-regularised $ell$, $ell_$, and Huber losses.
  arXiv  Detail & Related papers  (2023-05-30T12:18:39Z)
• The Adaptive $τ$-Lasso: Robustness and Oracle Properties [12.06248959194646]
  This paper introduces a new regularized version of the robust $tau$-regression estimator for analyzing high-dimensional datasets.<n>The resulting estimator, termed adaptive $tau$-Lasso, is robust to outliers and high-leverage points.<n>In the face of outliers and high-leverage points, the adaptive $tau$-Lasso and $tau$-Lasso estimators achieve the best performance or match the best performances of competing regularized estimators.
  arXiv  Detail & Related papers  (2023-04-18T21:34:14Z)
• Near Optimal Private and Robust Linear Regression [47.2888113094367]
  We propose a variant of the popular differentially private gradient descent (DP-SGD) algorithm with two innovations. Under label-corruption, this is the first efficient linear regression algorithm to guarantee both $(varepsilon,delta)$-DP and robustness.
  arXiv  Detail & Related papers  (2023-01-30T20:33:26Z)
• Retire: Robust Expectile Regression in High Dimensions [3.9391041278203978]
  Penalized quantile and expectile regression methods offer useful tools to detect heteroscedasticity in high-dimensional data. We propose and study (penalized) robust expectile regression (retire) We show that the proposed procedure can be efficiently solved by a semismooth Newton coordinate descent algorithm.
  arXiv  Detail & Related papers  (2022-12-11T18:03:12Z)
• SLOE: A Faster Method for Statistical Inference in High-Dimensional Logistic Regression [68.66245730450915]
  We develop an improved method for debiasing predictions and estimating frequentist uncertainty for practical datasets. Our main contribution is SLOE, an estimator of the signal strength with convergence guarantees that reduces the computation time of estimation and inference by orders of magnitude.
  arXiv  Detail & Related papers  (2021-03-23T17:48:56Z)
• Online nonparametric regression with Sobolev kernels [99.12817345416846]
  We derive the regret upper bounds on the classes of Sobolev spaces $W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$. The upper bounds are supported by the minimax regret analysis, which reveals that in the cases $beta> fracd2$ or $p=infty$ these rates are (essentially) optimal.
  arXiv  Detail & Related papers  (2021-02-06T15:05:14Z)
• Error bounds in estimating the out-of-sample prediction error using leave-one-out cross validation in high-dimensions [19.439945058410203]
  We study the problem of out-of-sample risk estimation in the high dimensional regime. Extensive empirical evidence confirms the accuracy of leave-one-out cross validation. One technical advantage of the theory is that it can be used to clarify and connect some results from the recent literature on scalable approximate LO.
  arXiv  Detail & Related papers  (2020-03-03T20:07:07Z)
• Understanding and Mitigating the Tradeoff Between Robustness and Accuracy [88.51943635427709]
  Adversarial training augments the training set with perturbations to improve the robust error. We show that the standard error could increase even when the augmented perturbations have noiseless observations from the optimal linear predictor.
  arXiv  Detail & Related papers  (2020-02-25T08:03:01Z)

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.