acceptodds
Withdrawn from ICLR 2027

Stable Minima are Implicitly Robust Learners against Sparse Outliers

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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 is linearly stable only at minima whose loss Hessian has largest eigenvalue at most . 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 . 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 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.

Primary area:
learning theory
Keywords:
Stable Minima, Edge of Stability, Robust Learners, Sparse Outliners

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 2 reviews, above 0% of the others.
Reviewer_3SqyOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

This paper shows that stability condition for gradient descent in terms of the Hessian (∇2⪯2/η\nabla^2 \preceq 2/\eta) bounds the ability for an overparameterized neural network to interpolate noisy training data. It follows a line of work by Liang et al. to identify a "deep" region in the feature space where the stability condition on the Hessian implies that the "weight" of kinks in this region cannot be too large. The main result of this work is Theorem 5, which is a lower bound for L^2 training error in this deep region assuming the true labels correspond to a teacher network that satisfies the stability condition. This lower bound is the sum of the added label noise, the training error against teacher, and a negative term representing a remainder. The paper extends this result by considering logistic loss and teacher networks outside of the class. It also considers a concrete data distribution (uniform on the sphere) and shows that the deep region is non-empty with high probability in this region.

Critical strengths

The question under study is interesting. The technical results are clearly stated.

Critical weaknesses

The main result of the paper is extremely constrained and not properly contextualized. The claim made by the title is not supported by the text of the paper. The authors only bound the training loss on the deep region, which results in the following limitations not considered by the paper:

  1. The deep region is a subset of the interior of the convex hull of the training point. It is shown (Proposition 6) that this region is nonempty given n>cmn > c_m where mm is the dimension, but in the proof it is shown that cmc_m is exponential in mm. This is not an artifact of the proof, as it is known that in general exponentially many points can be sampled uniformly in the ball before one will lie in the convex hull of the rest. This dependence is not made explicit in the paper, and can only be seen by looking at the proofs.
  2. There are multiple competing constraints on the quantity TT that defines the deep region, and the authors do not consider how these constraints interact. Two such constraints are as follows.
    • The bound on nTn_T in Proposition 6 is vacuous unless T≤m−m/2T \leq m^{-m/2}. For an appreciable fraction of the points to remain in the deep set, TT must be even smaller.
    • Proposition 6 says that g^\min_{\mathcal{D}} may be as small as O(T)O(T). The reciprocal of g^\min_{\mathcal{D}} appears in the upper bound for the remainder in Theorem 5. If TT is too small, this bound can be larger than Ω(nTαm/βm)\Omega(n_T^{\alpha_m/\beta_m}) and the result of Theorem 5 is vacuous.

The authors do correctly identify that these terms involve little dependence on nn. If nn is large enough relative to mm, then there is a TT that can be found to produce a non-vacuous bound that covers an appreciable fraction of the dataset. However, it is unclear in what regimes relating nn and mm that this is true, and what value of TT needs to be selected. As stated, it appears that nn needs to grow as Ω(mm)\Omega(m^m), which is a very strong condition even for modest dimensions. The experiments do not address these concerns, as they only ever consider data with intrinsic dimension 1.

Questions for authors

In the setting where data is drawn uniformly from the ball:

  1. How does the bound in Theorem 5 look with the dimension dependence made specific?
  2. What is the tradeoff between the bound in Theorem 5 and the size of the deep set?

Additionally, I suggest that future work might consider settings where the tradeoffs involved in selecting TT can be analyzed directly other than data drawn uniformly from the ball.

Reviewer_PpugOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This is a theory paper. In this paper the authors aims to show for a simplified two-layer ReLU network and assumed geometry of training data, its stable minima are robust against sparse outliers. Overall, I find the paper difficult to follow and the contributions questionable. And I find the validation to be limited and not convincing.

Critical strengths

None

Critical weaknesses

I find the paper difficult to follow. Even for a theory paper, the basic ideas and contributions should be written in a form that is understandable to the general audience of ICLR. The current writing is full of jargons and perhaps only accessible to aficionados.

  1. The paper did not give clear definitions of what sparse outliers are and what learners are considered robust. The proofs given in the paper do not clearly support the claims of the paper regarding the sparse outliers and robust learners.

  2. The experimental validation section of the paper does not provide clear and direct support of the major claims of the paper, namely stable minima of the model are robust against sparse outliers.

Questions for authors
  1. What are the main results of this study? The information provided in the abstract is messy.

  2. Can you please explicitly provide your definition of "sparse outliers"?

  3. Can you please explicitly provide your definition of "robust learners"?

  4. Can you please reformulate your proofs or reasoning so that they clearly show the robustness against sparse outliers?

  5. Can you please number the equations sequentially in the paper?

  6. Can you please provide a discussion on the limitations of this study?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.