Statistical Guarantees for Approximate Stationary Points of Shallow Neural Networks

Authors: Mahsa Taheri, Fang Xie, Johannes Lederer
Primary area: learning theory
Keywords: statistical guarantees, shallow neural networks, stationary points

Abstract:
Since statistical guarantees for neural networks are usually restricted to global optima of intricate objective functions, it is unclear whether these theories explain the performances of actual outputs of neural network pipelines. The goal of this paper is, therefore, to bring statistical theory closer to practice. We develop statistical guarantees for shallow linear neural networks that coincide up to logarithmic factors with the global optima but apply to stationary points and the points nearby. These results support the common notion that neural networks do not necessarily need to be optimized globally from a mathematical perspective. We then extend our statistical guarantees to shallow ReLU neural networks, assuming the first layer weight matrices are nearly identical for the stationary network and the target. More generally, despite being limited to shallow neural networks for now, our theories make an important step forward in describing the practical properties of neural networks in mathematical terms.

Decision: reject
Reviewer scores: 3, 6, 6, 3

Reviews and discussion:
<thread>
creation date:
1730562637068

thread_type:
official_review

<thread_object>
creator: reviewer_as1u

<content>
summary:
The paper studies the generalization risk for “reasonable” stationary points of the empirical loss function in the scenarios of two layer linear network and two layer ReLU network. With certain data assumptions and requiring a near-identity weight matrix, the paper shows bounded risk for these “reasonable” stationary points.

strengths:
An interesting consequence of the paper's theory is that if the regularization term is (close to) zero (i.e., r=0) then the generalization error/risk of these “reasonable” stationary points is exactly the same as that of the optimal. 

The theory extends from linear network to a more practical and interesting scenario – two layer ReLU network.

weaknesses:
Although at first sight the theorems and results look neat, after reading the proof, I found that these results strongly rely on the strong assumptions of data (Assumption 1) and (for ReLU network) the near-identity of weight matrix $\Theta$ (Assumption 2). Without these assumptions (or with milder assumptions) the theoretical results will break. 

Note that the setting of Assumption 1 and 2 make the network and optimization problem far from practical. For example, the weight matrix $\Theta$ is never close to identity in practice. I disagree with the paper’s claim that “(the) theories make an important step forward in describing the practical properties of neural networks…” Instead, I feel these conditions make the research direction more deviated from the goal of “describing practical properties of neural networks”. 

The paper claims “we focus on regression, which is more general and mathematically more challenging than classification”. This is incorrect. In many deep learning theories, classification turns out to be more challenging to mathematically analyze than regression problems, which is opposite to the paper’s claim. Moreover, the theories of the paper seems not applicable to classification which has a different loss function, hence it is also not reasonable to claim regression is more general than classification.  

The paper says in Line 148 that using $\ell_1$-regularization is to “to mimic deep-learning practice”. In practice, $\ell_1$-regularization is not that often used in practice, especially when compared to other regularization methods, for example, weight decay. I am wondering whether the theory still holds when a different regularization is used.

questions:
see comments in the Weaknesses section
</content>
</thread_object>

</thread>
<thread>
creation date:
1730708905030

thread_type:
official_review

<thread_object>
creator: reviewer_xwt5

<content>
summary:
This paper presents a statistical framework for analyzing shallow neural networks, offering guarantees for approximate stationary points rather than global optima. Recognizing the non-convex nature of deep learning objectives and the challenges of finding exact solutions, the authors address an important gap: They demonstrate that practical training outcomes—stationary points or points close to them—can still generalize effectively under certain conditions (Theorems 1-3). By focusing on stationary points, the paper connects statistical theory with real training outcomes, suggesting that approximate optimization may often suffice for effective generalization.

However, it’s worth noting that their analysis is limited to shallow ReLU networks, while practical applications predominantly involve deep networks. Therefore, this analysis remains a step away from the highly complex pipelines in modern deep learning. Nonetheless, as an initial study in this area, the paper is quite valuable. Overall, I think it’s a solid contribution, which is why I rate it a 6, just above the acceptance threshold.

strengths:
**Clarity:** The paper is generally well-organized, with a clear progression from theoretical background to the main results and implications. Each section is introduced with clear motivations, and notations are consistently defined.

**Significance:** This work provides crucial theoretical support for the practical success of neural networks, showing that networks trained to stationary points can perform nearly as well as those trained to global minima. However, it is important to note that the current analysis is limited to shallow ReLU networks. As an initial study in this area, the paper is highly valuable. Extending this analysis to deeper networks and other activation functions would greatly benefit the deep learning community, particularly in reinforcing the theoretical foundations of deep learning.

weaknesses:
**Empirical Limitations:** The empirical results are confined to small-scale simulations and toy models, which may limit the perceived robustness of the theoretical findings. The paper would benefit from experiments on more complex datasets.

**Assumptions for Shallow ReLU Networks:** The assumption of a nearly identity first-layer weight matrix for ReLU networks may restrict the practical relevance of Theorem 3. While the authors acknowledge this limitation, a deeper discussion of how these results might extend beyond isotropic conditions would be beneficial.

questions:
**Practicality of the Isotropic Weight Assumption for ReLU Networks:** Could the authors provide more context on the feasibility of using an isotropic first-layer weight matrix in practical shallow ReLU networks? Are there scenarios where this assumption might naturally hold, or is it primarily for theoretical tractability?

**Generalizability to Deeper Architectures:** Would the authors consider extending their results to deeper architectures, such as multi-layer networks with more than one hidden layer? If not, could they elaborate on the technical or computational challenges that arise when moving beyond shallow networks?

**Experiments Limited to SGD Optimization:** The authors mention in Line 2472 that the numerical results in the paper are based solely on the use of the SGD optimizer. Given the range of optimizers commonly used in practice (e.g., Adam), do the authors have insights into how different optimization algorithms might affect the empirical outcomes? Could alternative optimizers potentially achieve better performance or faster convergence at approximate stationary points?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730709014346

thread_type:
official_review

<thread_object>
creator: reviewer_vjyo

<content>
summary:
The paper aims to provide statistical guarantees for stationary points of shallow neural networks, both linear and ReLU. The study demonstrates that under certain regularization conditions, these approximate stationary points achieve near-optimal generalization comparable to global optima.

strengths:
This paper focused on approximate stationary points instead of global minima, which is more relevant to practical deep learning settings. By generalizing the result to ReLU networks, the significance of this result is enhanced. The rigorous mathematical proofs make the result quite solid.

weaknesses:
1. Some of the expressions in mathematical statements are a bit ambiguous. For example, there are "$\approx$" used in Assumption 2 and Theorem 3. I think using such notation in the explanation part is ok but in mathematical statements it should be more rigorous. I can't even find the rigorous expressions in appendix. Besides, "the second and third parts of Assumption 1 and Assumption 2" in Theorem 3 is not a precise sentence and may cause ambiguity.
2. The assumption of the part of ReLU nets seems strong since it requires that the stationary point $\tilde{\Theta}$ is close to the ground truth $\Theta^*$, which does not align with the goal of analyzing all approximate stationary points. I think more discussion about the necesity of this assumption can be added.
3. In Section 6, there are some technical results. Apart from the results, I think how these results are applied in the proof of main theorems are equally important. I cannot easily see the relation between these propositions and the main theorems of the paper so maybe some explanations are needed.
4. Although this is a theoretical paper, I think more experiment can be added. The experiments in the paper only verify the theoretical results specific to the simple architectures. Since theoretical papers aim to bring insights for more genral settings, experiments on more practical and complicated networks are good to illustrate the genral information of the theory.
5. The oracle tuning parameter $r_{orc}$ in line 190 seems vital in the theorems. How is this parameter important in the theorems and why should $r$ be larger than $r_{orc}$? Maybe there can have more discussion.

questions:
See weakness part.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730993054128

thread_type:
official_review

<thread_object>
creator: reviewer_e732

<content>
summary:
The paper establishes generalization guarantees for shallow neural networks corresponding to the stationary points of $\ell_1$-regularized regression problem. When the ground truth is a shallow neural network whose weights have a "reasonable" norm, the authors establish that, for both linear and ReLU shallow nets, the stationary points' population error is almost as good as the ground truth, as long as the stationary points are close to the ground truth.

strengths:
- The paper studies whether finding stationary points is sufficient for good performance. This is an interesting problem. 
- The paper is written clearly, especially in the appendix where each step in the proofs is described well.

weaknesses:
1. _Lack of emphasis on the boundedness assumption_: The paper uses the term reasonable stationary points in its theorem statements to indicate that the weight matrices have bounded norm. The boundedness is used repeatedly in the proofs and is the main ingredient needed for the proofs. The term "reasonable stationary point" leads the reader to believe that stationarity is an important component when only the boundedness is. The paper can be improved if the authors are clear about this fact.
2. _Stationarity is not used: The paper's results are uniform results that hold for all points in a bounded set. Indeed both the generalization results that rely on Lemma 1 are uniform generalization bounds. Stationarity is used in line 968 to introduce $\nabla \mathrm{risk}_X$ in the inequality, but the boundedness assumptions would have been sufficient to do so in my view.
3.  _Approximate stationary points_: An alternative definition of approximate stationary point is provided in the paper. Instead of small gradient norms, an approximate stationary point is defined as a point whose objective value is close to an exact stationary point. It is not clear how such a point can be obtained computationally. Without some form of gradient domination conditions, it is difficult to translate optimization results that only guarantee small gradient norms to the paper's definition of approximate stationarity. (For example, in almost flat but slightly slanted regions in the landscape, gradient norms are very small but not necessarily close to a stationary point).
4. _Imprecisitions in proofs_: I find the proof of Lemma 1 to be unclear. This relates to point 1 where the authors choose not to clearly state the boundedness assumption. In the proof $\eta$ plays the role of the bound. Unfortunately, the Case 1 Case 2 split is a little difficult to understand. $\tidle{\beta}$ depends on the data so it is a random quantity, meaning Case 1 and Case 2 are random events, are you conditioning on these events in the derivations?  The result in Lemma 1 is standard if the authors write it with clarity on their boundedness assumption.

questions:
In my understanding, the paper aims to analyze stationary points but its results are uniform bounds that hold over a bounded ball. A sign that this is the case follows from the fact that $\beta^* = (\gamma ^*, \Theta^*)$ is not required to be the ground truth anywhere in the proof of Theorem 1 for example. The results would hold for any choice in a bounded ball. Can the authors correct my understanding by pointing me to where the optimality of $\beta^* = (\gamma ^*, \Theta^*)$ is used?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732193801764

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response

comment:
We sincerely thank all reviewers for their extensive reviews of our paper.
We are, however, a bit puzzled: key parts of our paper, including  technical aspects as well as contributions, seem to have been misunderstood.
Most probably, this was caused by us not having written the paper well enough---we apologize for this.
In the following, we try to clear up the misunderstandings.
Please let us know if you have any further questions.

We have addressed the main questions raised by the reviewers in a general response provided here. Personalized responses to the remaining questions are included individually for each reviewer.
We will incorporate the corresponding changes (additional discussions, further experiments, etc.) into the final version of our main text.

**``Near-identity assumption over the stationary point  and the target  for ReLU networks:''**

We would extend our discussion, building on Theorem 3, regarding the feasibility of the near-identity assumption for ReLU networks (on the target as well as the stationary point).
There are currently two key directions in the literature that can help to explore the feasibility of this assumption:

*1-Expressiveness of Neural Networks with Near-Identity Weights:*

These studies investigate the capacity of neural networks with weights near the identity parameterization to approximate an unknown target function $f^*$.
For instance [hardt2016] analyze the expressiveness of Residual Networks, assuming a sufficiently large number of neurons is available [hardt2016;Theorem 3.2]. 
Their result is complemented by some  empirical 
studies for  Residual Networks with weights initialized near zero, 
which aligns well with our assumption regarding the existence of a near-identity global minimum.
In essence, Residual Networks with enough neurons can express the training data under mild regularity assumptions [hardt2016]. This also aligns with our framework, as our rates grow only logarithmically in $p$, making it particularly suitable for such wide networks.
Additionally, [bartlett2018b] explore the representation of smooth functions as compositions of near-identity functions, highlighting implications for deep network optimization.

*2-Rate of convergence of optimization algorithms under identity initialization for neural networks:*

These studies target the convergence of specific optimization methods under identity initialization. 
For instance [bartlett2018]  prove the rate of convergence of gradient-based optimization under identity initialization for deep linear networks. [li2017]  analyse the convergence  of stochastic gradient descent  for shallow ReLU networks, with nearly identity initialization; they state that ``(ReLU) networks with small average spectral norm already have good performance.''

Altogether, we believe that our identity assumption makes sense not only from an expressivity standpoint  but also regarding the optimization landscape. 
This means that once near-identity global optima exist for the corresponding objective function and the convergence of the optimization algorithms is guaranteed under near-identity initialization, our assumption becomes practically feasible.
Yet, of course, it would be interesting to study the subtleties even further.
We acknowledge that these assumptions might seem restrictive. However, it is important to note that our paper is the first to specifically target stationary points for neural networks, highlighting the inherent difficulty of this problem.
A particular challenge  lies in understanding the behavior of the Hessian matrix when attempting to relax our near-identity assumption (Proposition 2). 

Essentially, Theorem 3 suggests that for a sufficiently large tuning parameter, the optimization explores locally well-curved network spaces in the vicinity of specific stationary points, such that any stationary point close to the identity matrix generalizes as effectively as a global minimum.
In fact, our work concerns local curvature around the ground truth in neural networks, which we believe is valuable given the infinite number of such ground truths in neural networks.
In contrast, globally favorable curvature is rarely practical in deep learning. Note that our current results only guarantee the optimality of specific stationary points, not all of them. This observation could guide future research on designing optimal initialization techniques for more effective optimization.
It is also worth mentioning that the main challenge in extending our results to deeper neural networks lies in exploring the local curvature of the objective function, specifically analyzing the behavior of the Hessian matrix in a local context for neural networks, which can be the topic for future papers. 

[1]: Bartlett, P.L., Evans, S.N. and Long, P.M., 2018b. Representing smooth functions as compositions of near-identity functions with implications for deep network optimization. arXiv:1804.05012.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper investigates generalization guarantees for approximate stationary points in two-layer linear and certain ReLU networks. The exploration of stationary points, considered a potentially more realistic perspective, was acknowledged by the reviewers as an important research direction. However, despite some issues, particularly regarding the clarity and completeness of proofs, being discussed and partially clarified during the review period, all reviewers expressed concerns about the assumptions being overly restrictive. Furthermore, the empirical validation was criticized for its limited scope, focusing primarily on simple architectures and datasets. The authors are encouraged to incorporate the important feedback given by the knowledgeable reviewers.