\ell_1-regression with Heavy-tailed Distributions

Lijun Zhang, Zhi-Hua Zhou

Introduction

In classical linear regression, data is typically assumed to be "well-behaved," meaning it follows a sub-Gaussian distribution or is strictly bounded. Under these conditions, Empirical Risk Minimization (ERM) performs exceptionally well. However, real-world data in fields like finance, insurance, and environmental science often features "heavy tails"—extreme events and outliers that occur much more frequently than a normal distribution would predict.

When data is heavy-tailed, standard ERM becomes unreliable because a single extreme outlier can catastrophically pull the model away from the true underlying trend. While previous research has developed robust methods for $\ell_2$-regression (squared loss) to estimate the mean, this paper tackles $\ell_1$-regression (absolute loss), which estimates the conditional median. The median is naturally more resistant to outliers than the mean, making $\ell_1$-regression a preferred choice for robust modeling. Until now, however, its theoretical guarantees under heavy-tailed distributions were largely missing.

Proposed Method: Truncated Minimization

To address the challenge of both inputs and outputs being heavy-tailed, the authors propose a truncated minimization problem. Instead of minimizing the standard sum of absolute errors, the model passes the errors through a non-linear "truncation function," denoted as $\psi(\cdot)$.

Inspired by the work of Olivier Catoni, this function acts as a "soft cap." It allows small errors to pass through almost linearly but squashes very large errors, preventing any single data point from having an overwhelming influence on the model. The new objective function is formulated as:

$$\min_{\mathbf{w} \in \mathcal{W}} \frac{1}{n\alpha} \sum_{i=1}^{n} \psi\left(\alpha|y_i - \mathbf{x}_i^\top \mathbf{w}|\right)$$

Here, $\alpha$ is a tuning parameter that controls the scale of truncation. While the resulting objective is non-convex, it is quasiconvex (specifically, a sum of quasiconvex functions). This structural property means it can still be optimized using modern techniques like Normalized Gradient Descent (NGD).

Key Theoretical Insights and Results

This paper is a theoretical study focused on proving mathematical guarantees rather than empirical benchmarking. It yields several major insights:

  • High Probability without Exponential Moments: Most machine learning proofs require "exponential moment conditions" (assuming data decays quickly at the tails). This paper proves that it is possible to achieve a high-probability risk bound using only second-order moments (finite variance).
  • Optimal Excess Risk Bound: The authors prove an excess risk bound of $\tilde{O}(\sqrt{d/n})$, where $d$ is the dimensionality and $n$ is the number of samples. This matches the optimal rates traditionally found only in "nicer," well-behaved data settings.
  • Input vs. Output Sensitivity: A surprising finding is that if the input features ($\mathbf{x}$) are bounded, standard ERM is actually competent for $\ell_1$-regression even if the outputs ($y$) are heavy-tailed. Because the $\ell_1$ loss is Lipschitz continuous, it naturally limits how much a wild output can swing the gradient. The truncation method is primarily necessary when the inputs are also heavy-tailed.
  • Generalization to Other Losses: The truncation analysis is not limited to regression; it can be extended to any Lipschitz loss, including the hinge loss and logistic loss frequently used in classification tasks.

Limitations and Future Work

While the paper establishes strong theoretical foundations, it leaves a few practical challenges for future research:

  1. Algorithmic Implementation: The paper focuses heavily on proofs. While NGD is suggested to solve the objective, the authors do not provide a specific, optimized algorithm or code for immediate practical deployment.
  2. Parameter Tuning: The optimal truncation parameter $\alpha$ depends on knowing the variance of the data, which is often unknown in real-world scenarios. Finding a way to adaptively tune $\alpha$ without prior knowledge remains an open challenge.
  3. Computational Complexity: Although the problem is quasiconvex, it is still more computationally demanding than standard convex $\ell_1$-regression. Developing highly efficient solvers for large-scale, heavy-tailed problems will be a critical next step for practitioners.

Summary updated

Abstract

In this paper, we consider the problem of linear regression with heavy-tailed distributions. Different from previous studies that use the squared loss to measure the performance, we choose the absolute loss, which is capable of estimating the conditional median. To address the challenge that both the input and output could be heavy-tailed, we propose a truncated minimization problem, and demonstrate that it enjoys an $O(\sqrt{d/n})$ excess risk, where $d$ is the dimensionality and $n$ is the number of samples. Compared with traditional work on $\ell_1$-regression, the main advantage of our result is that we achieve a high-probability risk bound without exponential moment conditions on the input and output. Furthermore, if the input is bounded, we show that the classical empirical risk minimization is competent for $\ell_1$-regression even when the output is heavy-tailed.
BibTeX
@inproceedings{zhang2018ell,
  author = {Lijun Zhang and Zhi-Hua Zhou},
  title = {{\textbackslash\{\}ell\_1-regression with Heavy-tailed Distributions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=B14iHDb_bS},
}
Figure