Stable Minima are Implicitly Robust Learners against Sparse Outliers

Overparameterized neural networks trained in practice often do not overfit label noise. They are also surprisingly robust to label corruption, where a few responses are entirely wrong. A common belief attributes both to the stable minima that large learning rates select. Gradient descent with step size $\eta$ is linearly stable only at minima whose loss Hessian has largest eigenvalue at most $2/\eta$. For label noise this belief has some theoretical support: stable minima of two-layer ReLU networks have bounded weighted variation, and this bound yields generalization from noisy labels. For label corruption much less is known. We study two-layer ReLU networks under squared loss when a small fraction of the responses is shifted by additive outliers of any amplitude, and ask what a stable minimum learns from such data. Our main result concerns the interior of a sample drawn uniformly from a ball of intrinsic dimension $m$. Consider a stable minimum whose outputs stay bounded on the training points, and suppose the clean signal is simple enough to be representable under the stability constraint. With high probability, fitting the outliers lowers its training loss by at most an error term of order $n^{-(m+3)/(2m+3)}$ up to log factors, at fixed corruption rate and amplitude. Conversely, a stable minimum whose loss comes down to the level set by the outliers alone has learned the clean signal, up to an error of the same order. A larger step size tightens both bounds. The geometric condition cannot be dropped: on a sphere, stable minima can interpolate arbitrary labels. Simulations with certified error bounds support these predictions. The argument extends to logistic loss with label flips.