acceptodds
Under review as a conference paper at ICLR 2027

Statistical guarantees for robust deep learning under heavy-tailed noise and covariates

Abstract

Robust loss functions are widely used in deep-learning pipelines to reduce sensitivity to outliers, heavy tails, and other forms of data corruption. In this paper, we support these empirical findings by providing statistical guarantees. We derive oracle inequalities for empirical risk minimization with Lipschitz losses over nonconvex function classes, including feedforward neural networks. Our results only require weak moment assumptions on the covariates, while remaining noise-agnostic. We also study non-Lipschitz target losses through training with Lipschitz surrogates. The resulting bounds provide guarantees for the original target risk and make explicit the estimation–approximation tradeoff, in accordance with the classical statistical robustness–efficiency perspective. The framework recovers Huber-type procedures and extends to more general losses. Numerical experiments under heavy-tailed corruption illustrate the benefits of Lipschitz surrogate training.

Primary area:
learning theory
Keywords:
robust statistical learning, empirical risk minimization, oracle inequalities, heavy-tailed data, deep neural networks, lipschitz loss

Reviews

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

This paper provides a derives excess-risk bounds for Lipschitz losses, it differs from previous works by allow relaxed assumptions enabling the use of nonconvex neural-networks and finite-sample guarantees, while assuming weak moments. The framework seems better adapted to modern neural 'norm constrained' networks that use weight decay during training. The paper provides: (i) oracle inequalities for ERM risk when using Lipschitz losses, using the Rademacher complexity of the predictive function. (ii) Guarantees on non-Lipschitz loss functions via Lipschitz surrogates. (iii) A proof that the provided ERM risk bound is sharp under the setting of the weak moment assumptions. The empirical validation sections are not at the heart of the method where the main claims regard the theorems of the paper.

The method is tested in toy settings using one-hidden layer ReLU networks, which show the empirical excess risk decreases with dataset size at rates consistent with that of the Theorem bound's exponent when training with a Huber loss (Figure 1). The paper also shows that the proposed truncation of the Barron loss allows for better test performance when training with corrupted data (Figure 2).

Critical strengths

The theorems and propositions are clearly presented and I have not found any theoretical errors in the paper (although this was done in limited time and is not my area of expertise).

The paper removes convexity assumptions on the predictive function class, which unlocks its use for neural networks provided the ERM minimizer can be reached, optimization error is left for future work.

The methods are general and encompass Lipschitz losses and certain non-Lipschitz losses via surrogates (although the latter requires extra assumptions).

Proposition 3 establishes that the sample-size and confidence dependence in the bound of Theorem 2 is sharp up to constants under the stated assumptions.

Critical weaknesses

The practical importance of the theoretical guarantees is not demonstrated enough in the paper whether through the writing or experiments. In particular, Figure 2 illustrates the benefits of robust losses but does not validate the theoretical guarantees of the paper. Moreover, I don't think the noise scheme being used in Figure 2 is compatible with the weak moments assumption of the paper.

The guarantees assume exact empirical risk minimization. Indeed, although the authors relax the assumption regarding the convexity of the predictive function, assuming exact empirical risk minimization is a limitation for practical usage of the method.

Questions for authors

Q1: Could the authors comment on the limitations regarding assuming exact empirical risk minimization for neural networks that use approximate minimizers ? Q2: During practical training tasks, the literature on Lipschitz-by-design neural networks [1,2] has shown that aLiplbMl+1a_\mathrm{Lip}^l b_\mathcal{M}^{l+1} tends to explode numerically. Can the authors estimate these values in practice for neural networks with weight decay (of a decent size for practical use), and comment on the utility or vacuousness of the resulting bounds ?

The answer to Q1 is the most important factor I will take into account when formulating my final rating. The significance of the paper relies on removing convexity assumptions, but the subsequent requirement of exact ERM may limit practical relevance of the papers guarantees.

[1] Anil, Cem, James Lucas, and Roger Grosse. "Sorting out Lipschitz function approximation." International conference on machine learning. PMLR, 2019.

[2] Béthune, Louis, et al. "Pay attention to your loss: understanding misconceptions about lipschitz neural networks." Advances in Neural Information Processing Systems 35 (2022)

4 comments

Reviewer MpdM

Q1: Approximate empirical risk minimization

We thank the reviewer for raising this important point. Our guarantees extend to approximate empirical-risk minimizers, with an additive optimization-error term.

Indeed, the proof of Theorem 3 uses exact minimization only through the nonpositivity of the empirical excess risk relative to the oracle. Since the underlying empirical-process bound holds uniformly over F\mathcal F, for any measurable output f~∈F\tilde f\in\mathcal F of a training algorithm, with probability at least 1−t1-t,

\leq \frac{4c_h\mathfrak R_n}{t}+\Delta_n(\tilde f).$$ Here, $\Delta_n(\tilde f)$ denotes the empirical excess risk relative to $f^{\ast}$ and is bounded above by the empirical optimization error. We will provide the formal statements and proofs in a revised manuscript, which we plan to upload in the coming days. **Moment assumptions in Figure 2** We thank the reviewer for pointing out this discrepancy. *The experiments used Student-$t$ corruption with $2.1$ degrees of freedom, not $2$ as incorrectly stated in the supplement.* This is an error in the experimental description; the numerical results are therefore unchanged. For squared-loss evaluation ($r=2$), Theorem 4 requires a finite residual moment of some order $q>2$. Student-$t_{2.1}$ noise has finite absolute moments for every $q<2.1$. This choice ensures finite variance while retaining very heavy tails, providing a challenging experimental setting. Adding Gaussian noise and Bernoulli masking preserves the required finite moments, while the bounded covariates satisfy the input-moment assumptions. Thus, the Huber experiment satisfies the moment assumptions of Theorem 4. Moreover, since the additive noise is centered, independent of the covariates, and has finite variance, the clean-target MSE used for evaluation coincides with the population squared excess risk relative to $f^{\ast}$: $$E_{y,x}\left[ (y-\widehat f(x))^2-(y-f^{\ast}(x))^2\right] = E_x\left[ (\widehat f(x)-f^{\ast}(x))^2 \right].$$ Thus, the evaluation metric is directly connected to the squared-risk guarantee of Theorem 4 for Huber training. We will correct the degrees of freedom and clarify the evaluation metric in the revised manuscript. **Q2: Growth of the network-dependent constants** We agree that products of layer norms can make generalization bounds conservative for deep networks. *This dependence is not introduced by our heavy-tailed analysis:* it is inherited from the neural-network complexity bound of Golowich, Rakhlin, and Shamir (2020, Theorem 1), which already contains a product of layerwise Frobenius bounds in the bounded-input setting. Analogous spectral-norm products appear in Bartlett, Foster, and Telgarsky (2017). Our specialization therefore shares a limitation of established norm-based analyses, rather than introducing an additional norm-product penalty for heavy-tailed data. Importantly, our general oracle inequality (Theorem 3) is stated in terms of the Rademacher complexity $\mathfrak R_n$ and does not require a particular norm-product estimate. Alternative analyses exist: Schmidt-Hieber (2020), for example, obtains oracle bounds for sparse ReLU networks through sparsity and architecture rather than an explicit product of layer norms, under different boundedness and distributional assumptions. Exploring such complexity controls within our weak-moment framework is an interesting direction for future work. Moreover, existing studies report benefits in practical convolutional-network applications, including Tukey's biweight loss in pose and age estimation (Belagiannis et al., 2015) and Charbonnier loss for image super-resolution (Lai et al., 2017). These results support the practical motivation for our analysis, although they do not establish that our bounds provide tight numerical certificates. To address the reviewer's quantitative question, we plan to include additional simulations with deeper networks, reporting layer-norm products and theoretical bound magnitudes alongside empirical excess risks. This will assess how the bounds' conservativeness changes with depth.

We thank the reviewer again for the constructive comments. We have now incorporated the extension to approximate empirical-risk minimizers as Corollary 3, with a formal proof in Appendix A.11, addressing Q1.

For Q2, we added the promised experiments with deeper networks, reporting empirical excess risks, layerwise norm products, and theoretical bound magnitudes (Figure 4, Appendix A.9). We also discuss the conservativeness of the resulting bounds.

Finally, we corrected the description of the response-noise distribution and clarified the moment assumptions underlying Figure 2.

We hope these additions address your main concerns and would appreciate your feedback on the revised manuscript.

First of all, I would like to thank the authors for the significant time and effort they put into the clear responses and their revisions of the paper. I appreciate the incorporation of minimization error in Corollary 3. My main issue remains that relaxing convexity and moment assumptions as enabled by the paper's analysis should be shown to be preferable to incorporating unknown terms like training algorithm dependent minimization error, as trading assumptions for unknown corrective terms warrants further investigations.

Therefore, I will keep my current weak reject score and invite the authors to resubmit their potentially meaningful contribution with added motivations as to why their method might be preferable over standard statistical guarantees to another venue where I think it might be appreciated.

We thank the reviewer for their further comments and respect their decision to maintain the current score.

Nonetheless, we would like to clarify one point. We believe that relaxing statistical assumptions and controlling algorithm-dependent optimization error are two distinct issues, which cannot generally be traded against each other.

Moment assumptions concern the underlying data-generating distribution, which is not under our control. In particular, heavy-tailed observations are a feature of many real datasets, and imposing stronger assumptions does not make them valid. On the other hand, optimization error depends on the training procedure and can potentially be reduced through algorithmic choices. Whether a given algorithm can be proved to achieve a sufficiently small optimization error is itself a separate question, which may depend on additional assumptions.

Importantly, our extension to approximate minimizers does not introduce an optimization-error term as a price for relaxing the statistical assumptions. This term simply accounts for inexact minimization, as it would also in more classical statistical guarantees. Our results establish statistical guarantees under weaker distributional assumptions, while leaving the analysis of specific optimization algorithms for future work.

We appreciate the reviewer's perspective and thank them again for the constructive discussion.

Reviewer_mSY8OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper derives statistical guarantees for empirical risk minimization with Lipschitz losses under weak moment assumptions, including for nonconvex neural-network classes.

The paper extends these guarantees to non-Lipschitz target losses through Lipschitz surrogates, with explicit estimation–approximation tradeoffs, think of how the Huber loss is a Lipschitz surrogate of the L2 loss.

The paper contains synthetic experiments involving heavy-tailed noise and covariates.

Critical strengths

The theoretical framework is interesting, particularly the guarantees under weak assumptions on the covariates and without moment assumptions on the noise.

The extension to Lipschitz surrogates provides a connection between robust training and evaluation with other losses.

Critical weaknesses

It is not entirely clear to me which theoretical results are fundamentally new and which follow from existing results or their application to neural networks. It seems to me that Theorem 3 relies on standard Rademacher complexity arguments, and Theorem 4 appears to specialize the preceding surrogate results. A clearer distinction or a more detailed discussion of what are the difficult parts that were understood technically would be helpful in assessing the contribution.

The experiments are limited to synthetic settings. Furthermore, Figure 2 is presented as illustrating a robustness–efficiency tradeoff, but the curves mostly increase monotonically with corruption. The tradeoff is not immediately apparent from this figure.

Questions for authors

Could the authors clarify which theoretical contributions are new, as opposed to applications or combinations of existing results?

Could the authors explain more precisely how Figure 2 illustrates the robustness–efficiency tradeoff? Would varying the truncation threshold make the tradeoff apparent?

Given the weak assumptions on the data, would it be possible to validate the results on real datasets with outliers or heavy-tailed observations?

Regarding Theorem 1, is the exponential improvement with depth (ie the condition aLipbM<1a_{\mathrm{Lip}}b_{\mathcal M}<1) meaningful and attained for real cases?

2 comments

Interpretation of the depth dependence

We thank the reviewer for highlighting this point. The decreasing factor should not be interpreted as a general statistical advantage of greater depth. When aLipbM<1a_{\mathrm{Lip}}b_{\mathcal M}<1, the output envelope of the constrained class also decreases with depth. This does not establish improved prediction of a fixed target as depth increases.

A more informative regime is ReLU networks with layerwise Frobenius norms bounded by 11: under this restriction on the candidate class, the exponential norm factor disappears, leaving only O(ℓ+1)O(\sqrt{\ell+1}) depth dependence through κℓ,p\kappa_{\ell,p}.

We will revise the discussion following Theorem 1 accordingly. The additional depth experiments and discussion proposed in our response to Reviewer MpdM's Q2 will further address this issue.

Novelty and contribution

We thank the reviewer for requesting a clearer distinction between the different contributions. We agree that Theorem 3 builds on standard Rademacher-complexity arguments, while Theorem 4 specializes our general surrogate principle to norm-constrained neural networks and power losses.

The main contribution of Theorem 3 is the resulting noise-agnostic oracle guarantee for potentially nonconvex classes, without convexity or Bernstein assumptions. Its neural-network specialization (Theorem 1) provides explicit weak-moment rates using the complexity estimate of Golowich et al. (2020).

Our second contribution is the general surrogate principle, which provides guarantees under the original non-Lipschitz target loss and quantifies the estimation–approximation tradeoff. Theorem 4 makes this principle explicit for generalized Huber training, including an optimized truncation level.

We will clarify this distinction between general results, specializations, and existing technical ingredients in the revised manuscript.

We would be grateful to know whether the proposed clarifications and additional experiments would address your concerns, or whether there are other aspects you would particularly like us to investigate or clarify.

Robustness–efficiency tradeoff in Figure 2 We thank the reviewer for this suggestion. We agree that Figure 2 primarily illustrates the relative robustness of different training losses as the corruption probability increases, rather than directly displaying the estimation–approximation tradeoff induced by the truncation threshold τ\tau.

In our theoretical analysis, increasing τ\tau reduces the approximation error while increasing the Lipschitz constant of the surrogate, and consequently the estimation term. For Huber training, this also corresponds to moving from a more L1L_1-like objective toward squared-loss training.

We plan to extend the numerical experiment by varying τ\tau across several contamination levels, while keeping the remaining experimental settings fixed. This will allow us to assess how the choice of threshold affects clean-target prediction error and provide a more direct empirical illustration of the robustness–efficiency tradeoff.

We will clarify the interpretation of the current Figure 2 and incorporate the additional results in the revised manuscript.

Real-data validation We thank the reviewer for this suggestion. The practical benefits of robust losses in deep learning have already been demonstrated in several real-world applications, including human pose and age estimation (Belagiannis et al., 2015), image super-resolution (Lai et al., 2017), and other computer-vision tasks (Barron, 2019).

Our main contribution is theoretical, and our synthetic experiments are designed to investigate the statistical guarantees under controlled distributional assumptions. In particular, knowing the true regression function allows us to evaluate the oracle-centered excess risk directly, which is generally not possible with real datasets.

Nevertheless, we agree that further empirical validation would strengthen the paper. We plan to extend our experiments to deeper neural networks, examining the relationship between empirical excess risk, sample size, and the network-dependent constants in our theoretical bounds. This will also address the questions about practical bound magnitudes and depth dependence raised by Reviewer MpdM.

We will include these additional results and clarify the motivation for our experimental design in the revised manuscript.

We thank the reviewer again for the helpful suggestions. We have clarified the distinction between our statistical contributions and the existing technical ingredients in the Introduction.

We have also added an experiment varying the truncation threshold across contamination levels (Figure 3), which provides a more direct illustration of the robustness–efficiency tradeoff. In addition, the new depth experiment (Figure 4, Appendix A.9) examines the practical magnitude and limitations of the theoretical bounds.

We hope these revisions address your main concerns, and we would welcome your further feedback.

Reviewer_QJBtOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This article explores generalization guarantees for data with heavy-tailed noise. The authors establish that, under a Lipschitz loss and suitable assumptions on the predictor class and inputs, the expected loss difference of a learned predictor relative to an oracle is bounded with high probability. This allows for meaningful learning guarantees without requiring finite moments of the response noise.

They also study whether training with a robust loss can provide guarantees under a different evaluation loss, such as squared error. That extension involves a tradeoff and stronger moment assumptions. They construct the robust training loss by keeping the original loss up to a cutoff and extending it linearly beyond that point, limiting its sensitivity to large errors.

The authors also give a lower-bound example showing that their empirical-risk estimation bound has unavoidable dependence on sample size and confidence under the stated moment assumptions.

Critical strengths
  • The general results do not require a convex function class or the Bernstein condition (often seen in fast rates for excess risk bounds). This makes them a good fit for norm-constrained feedforward neural networks. With finite input variance (but potentially large response variance), the bounds achieve the standard n−1/2n^{-1/2} rate; with only a finite pp-th input moment for 1<p<21<p<2, they give the slower rate n−(p−1)/pn^{-(p-1)/p}.

  • The truncation framework uses a surrogate Lipschitz loss with an explicit moment-dependent cutoff choice \tau. Here increasing tau raises the estimation error while lowering the surrogate approximation error. The main proof steps appear sound to me.

Critical weaknesses

The main observation is that, under a Lipschitz loss, the difference between two predictors’ losses can be bounded independently of the response noise. The remaining arguments appear to use standard proof tools. The theoretical results are sound to the best of my knowledge but it is unclear if they are sufficiently substantial.

Questions for authors
  • The experiments use a fixed cutoff of τ=3σ\tau=3\sigma, where sigma is the response noise scale. How should the cutoff be chosen when σ\sigma is unknown?

Minor comment: Please use h(⋅)h(\cdot) consistently for losses; the paper alternates between h[] and h(). This article could also benefit from a consistent style for subscripts and choice of norm indexes.

2 comments

Novelty and contribution

We agree that our analysis relies on established empirical-process techniques, including symmetrization, contraction, and existing neural-network complexity estimates. Our contribution lies in the statistical guarantees obtained under substantially weaker assumptions, rather than in developing a new concentration inequality.

In particular, our oracle inequalities apply to nonconvex neural-network classes under only finite pp-th moments of the covariates, without imposing moment conditions on the response noise. Moreover, the surrogate framework extends these guarantees to non-Lipschitz target risks through an explicit estimation–approximation tradeoff. We believe that establishing these results within a unified framework provides a useful theoretical contribution to robust deep learning.

We would appreciate your feedback on whether these clarifications and planned revisions address your main concerns, or whether there are specific aspects of our contribution that you would like us to elaborate on further.

Choice of the tuning parameter

We thank the reviewer for raising this practical question. The truncation level τˉ∗\bar\tau^* derived in Theorem 4 minimizes the theoretical upper bound, but depends on distributional quantities that are generally unknown. Importantly, the oracle inequality itself holds for any fixed τ>0\tau>0; the theoretical choice is not required for its validity.

In practice, when the noise scale σ\sigma is unknown, a natural strategy is to estimate the residual scale robustly and select τ\tau over a grid of candidate values using validation data. A formal guarantee for such a data-dependent selection procedure would require additional analysis, which is beyond the scope of the current results.

We will clarify this distinction in the revised manuscript and investigate the sensitivity of the empirical performance to the truncation threshold.

Minor notation inconsistencies

We thank the reviewer for pointing out these notation inconsistencies. We will standardize the notation for loss functions, subscripts, and norm indices throughout the revised manuscript.

We thank the reviewer again for the feedback. We have clarified the scope and novelty of our contributions in the Introduction, distinguishing the statistical guarantees from the established techniques used in their proofs.

Regarding the truncation threshold, we have added a discussion of its practical selection (Section 3.4), together with a new experiment illustrating sensitivity to the threshold under different contamination levels (Figure 3).

We have also addressed the notation inconsistencies noted in the review.

We hope these revisions address your concerns and would welcome any further feedback.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.