Robust estimation with Lasso when outputs are adversarially contaminated

Takeyuki Sasai, Hironori FujisawaarXiv 2020 · OpenReview

Abstract

In high-dimensional statistics, the Lasso is a cornerstone for sparse variable selection. However, its performance degrades significantly in the presence of adversarial contamination. This paper investigates the "extended Lasso," a method designed to jointly estimate regression coefficients and adversarial outliers. While previous literature established initial convergence rates, recent work suggested faster rates were achievable. We provide a novel proof that confirms these sharper convergence rates by leveraging the specific geometric properties of the Huber loss function. Our approach demonstrates that the extended Lasso is nearly minimax optimal, offering a robust solution even as the number of outliers grows.

Introduction

The Lasso (Least Absolute Shrinkage and Selection Operator) has revolutionized the analysis of high-dimensional data, allowing researchers to identify a small number of relevant predictors among thousands of candidates. Despite its utility, the standard Lasso is notoriously sensitive to outliers. In many real-world applications—ranging from sensor networks to financial modeling—data may be subject to "adversarial contamination," where a subset of observations is manipulated to bias the results.

To address this, researchers have turned to the extended Lasso, which incorporates an explicit term for outliers. This paper, "Robust estimation with Lasso when outputs are adversarially contaminated" by Takeyuki Sasai and Hironori Fujisawa, provides a rigorous mathematical foundation for why this method is more effective than previously proven, offering a new proof strategy that clarifies the relationship between robust estimation and the Huber loss function.

The Problem: Adversarial Outliers

Standard linear regression assumes that noise is independent and identically distributed (i.e., Gaussian noise). Adversarial contamination is far more challenging: it assumes that an opponent can change the output values ($y$) of a certain number of samples to any value imaginable.

In 2012, Nguyen and Tran proposed an optimization framework to handle this by estimating both the true coefficients ($\beta^*$) and an outlier vector ($\theta^*$): $$\min_{\beta, \theta} \left\{ \frac{1}{2n} \|Y - X\beta - \sqrt{n}\theta\|_2^2 + \lambda_s\|\beta\|_1 + \lambda_o\|\theta\|_1 \right\}$$

While this "extended Lasso" was functional, the initial proven convergence rates were relatively slow, particularly regarding how the error scaled with the number of outliers ($o$).

Methodology: The Huber Connection

The core insight of the Sasai and Fujisawa paper lies in the equivalence between the extended Lasso and the penalized Huber loss function. The Huber loss is a hybrid objective: it behaves quadratically for small errors (like standard least squares) but transitions to a linear penalty for large errors (outliers).

The authors argue that the tuning parameter for outliers ($\lambda_o$) effectively dictates the threshold where this transition occurs. Unlike previous proofs that treated the Huber loss as a generic convex function, this research focuses on the specific "switch point" of the function. By applying tools such as Gaussian width and concentration inequalities to this specific geometry, the authors derive tighter bounds on the estimation error.

Theoretical Framework

As a theoretical study, the paper utilizes a random design framework:

  • Data Generation: Samples are drawn from Gaussian distributions ($N(0, \Sigma)$ for inputs and $N(0, \sigma^2)$ for noise).
  • Conditions: The design matrix is assumed to satisfy the Restricted Eigenvalue (RE) condition, a standard requirement for ensuring that the Lasso can accurately recover sparse signals in high dimensions.

Key Results and Convergence Rates

The primary contribution of this work is the confirmation of a sharper convergence rate for the estimation error $\|\beta^* - \hat{\beta}\|_2$: $$O\left(\sqrt{\frac{s \log d}{n}} + \frac{o}{n} \sqrt{\log \frac{n}{o} \log n}\right)$$

This result is significant for two reasons:

  1. Improvement over Nguyen and Tran (2012): The original proof suggested a rate involving $\sqrt{o/n}$. In high-dimensional settings where $n$ is large, the new $o/n$ term represents a much faster decay of error, meaning the model can tolerate a higher density of outliers.
  2. Minimax Optimality: This rate closely matches the theoretical "speed limit" (minimax rate) for robust estimation, suggesting that the extended Lasso is an essentially optimal algorithm for this class of problems.

Conclusion and Future Directions

By providing a proof centered on the unique properties of the Huber function, Sasai and Fujisawa have bridged a gap in the theoretical understanding of robust Lasso. Their work confirms that the extended Lasso is not just a heuristic for outlier detection, but a mathematically sound method that achieves near-optimal convergence.

However, limitations remain. The current proof relies on Gaussian assumptions for inputs and noise, which may not hold for "heavy-tailed" real-world data. Future research may extend these Huber-based proof techniques to other robust M-estimators and explore fixed-design matrices where the random distribution of inputs is not assumed.

Summary updated

Abstract

We consider robust estimation when outputs are adversarially contaminated. Nguyen and Tran (2012) proposed an extended Lasso for robust parameter estimation and then they showed the convergence rate of the estimation error. Recently, Dalalyan and Thompson (2019) gave some useful inequalities and then they showed a faster convergence rate than Nguyen and Tran (2012). They focused on the fact that the minimization problem of the extended Lasso can become that of the penalized Huber loss function with $L_1$ penalty. The distinguishing point is that the Huber loss function includes an extra tuning parameter, which is different from the conventional method. We give the proof, which is different from Dalalyan and Thompson (2019) and then we give the same convergence rate as Dalalyan and Thompson (2019). The significance of our proof is to use some specific properties of the Huber function. Such techniques have not been used in the past proofs.
BibTeX
@misc{sasai2020robust,
  author = {Takeyuki Sasai and Hironori Fujisawa},
  title = {{Robust estimation with Lasso when outputs are adversarially contaminated}},
  year = {2020},
  eprint = {2004.05990},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2004.05990},
}
Figure