- 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 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
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 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, for any measurable output f~∈F of a training algorithm, with probability at least 1−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.