ReLU Regression with Massart Noise

Ilias Diakonikolas, Jong Ho Park, Christos Tzamos

Abstract

Fitting Rectified Linear Units (ReLUs) is a fundamental task in modern deep learning, yet standard optimization methods often fail when data is corrupted by noise. This paper introduces the first computationally efficient algorithm for ReLU regression that achieves exact parameter recovery under the Massart noise model. By utilizing a radial-isotropic transformation and a novel separation oracle for the Ellipsoid method, the proposed approach can perfectly reconstruct a model's parameters even when an adversary corrupts nearly half of the labels. Our results demonstrate that robustness in regression depends significantly on the geometric properties of the data distribution rather than strict probabilistic assumptions.

Introduction

In the realizable setting, fitting a ReLU function $f(x) = \max(0, w \cdot x)$ is straightforward. However, real-world datasets are frequently subject to noise. While adversarial (agnostic) noise often makes the problem computationally intractable without restrictive assumptions, and simple random noise fails to capture complex corruptions, the Massart noise model offers a compelling middle ground. In this setting, an adversary can flip any label with a probability $\eta < 1/2$. The challenge addressed in this work is whether the original parameters $w^*$ can be recovered efficiently without assuming the data follows a perfect bell curve.

Methodology

The proposed algorithmic framework rests on three primary pillars designed to handle the non-convexity of ReLU regression and the presence of malicious noise.

1. Radial-Isotropic Transformation

Standard regression techniques are sensitive to outliers, particularly those far from the origin. To mitigate this, the authors employ a preprocessing step that transforms the data into a radial-isotropic position. This "democratizes" the data, ensuring that all points are unit-norm and distributed evenly across all directions, preventing any single outlier from exerting disproportionate influence on the solution.

Algorithm 1: Linear function recovery via radial isotropy

2. The Ellipsoid Method and Separation Oracles

Unlike linear regression, ReLU regression is non-convex. To navigate this landscape, the authors utilize the Ellipsoid method. They developed a novel separation oracle—a subroutine that, given a guess, identifies a "cutting plane" to iteratively narrow the search space toward the true parameters $w^*$. A key insight is that under radial isotropy, the $\ell_1$-minimizer (absolute error) aligns with the $\ell_0$-minimizer (mistake count), facilitating exact recovery.

3. Recursive Subspace Decomposition

In cases where data is heavily concentrated on a specific flat surface (subspace), the algorithm recursively breaks the problem down, solving for the components of $w^*$ piece by piece to maintain robustness.

Results and Evaluation

The algorithm was evaluated using both synthetic and real-world datasets to test its recovery capabilities under varying noise levels.

  • Synthetic Data: Using a mixture of Gaussians designed to be "unfriendly" to standard regression, the algorithm maintained a near 100% Exact Recovery Rate even as the noise level $\eta$ approached 0.4 (where 0.5 is the theoretical limit of impossibility).
  • Drug Discovery Dataset: On a real-world dataset containing 3,084 training points and 410 dimensions, the "Rescaled L1" approach significantly outperformed Ridge and standard $\ell_1$ regression. While baseline methods collapsed as noise intensified, the radial-isotropic approach remained stable and accurate.

Discussion and Conclusion

The core contribution of this work is the demonstration that exact recovery is possible with minimal distributional assumptions—specifically, only requiring "anti-concentration" (the data must not be degenerate). This shifts the focus from the probability distribution of the data to its underlying geometry.

While the Ellipsoid method ensures polynomial-time convergence, it is computationally more intensive than first-order methods like Stochastic Gradient Descent (SGD). Future research will focus on adapting these geometric insights into faster optimization frameworks and extending the methodology from single ReLUs to multi-layer neural networks where neurons interact.

Summary updated

Abstract

We study the fundamental problem of ReLU regression, where the goal is to fit Rectified Linear Units (ReLUs) to data. This supervised learning task is efficiently solvable in the realizable setting, but is known to be computationally hard with adversarial label noise. In this work, we focus on ReLU regression in the Massart noise model, a natural and well-studied semi-random noise model. In this model, the label of every point is generated according to a function in the class, but an adversary is allowed to change this value arbitrarily with some probability, which is {\em at most} $\eta &lt; 1/2$. We develop an efficient algorithm that achieves exact parameter recovery in this model under mild anti-concentration assumptions on the underlying distribution. Such assumptions are necessary for exact recovery to be information-theoretically possible. We demonstrate that our algorithm significantly outperforms naive applications of $\ell_1$ and $\ell_2$ regression on both synthetic and real data.
BibTeX
@inproceedings{diakonikolas2021relu,
  author = {Ilias Diakonikolas and Jong Ho Park and Christos Tzamos},
  title = {{ReLU Regression with Massart Noise}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=Uy02ln1K7H},
}

Loading related content...

Figure