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.
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