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.
Paper
Similar papers
Peer review
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
Rating
3
Confidence
3
Soundness
3
Presentation
3
Contribution
1
Response to reviewer aS1U
We thank the reviewer for raising valuable comments and questions. Please find our responses below. We will incorporate all these changes into our main PDF. **``Near-identity assumption:''** Regarding our assumptions in the ReLU case, we would refer to our detailed discussion in the general response. **``$\ell_1$-regularization:''** As we already stated in our text, despite $\ell_1$-norm is non-smooth, it often poses very little problems in terms of computations (please see [friedman2010]). Also recently, the $\ell_1$-norm has been effectively used to promote sparsity in neural networks [lemhadri2021]. A related finding in [neyshabur2015; parhi2023] shows the equivalence of weight decay in deep learning to well-known group lasso on the network weights, which favours solutions with few active neuron connections. So our conjecture is that the results can also hold on a high level for weight decay to some extend, however, detailed studies can be considered as a future research paper. **``Classification vs Regression:''** Beyond our discussion on lines 64--68, we would refer to our general response (continue), where we provide simulations supporting a conjecture that our results might be extendable to classification. Specifically, we simulate the behavior of approximate sub-optimal solutions on the **MNIST, fashion-MNIST, and K-MNIST** dataset using **cross-entropy loss**, with a neural network consisting of $10$-layer weight matrices and ReLU activations, with network width $50$. However, at present, our theory is strictly designed to consider the regression setting, while extension to further settings like classification should ideally be the subject of another paper; therefore, it is left as future work. We also would be happy to incorporate any additional references suggested by the reviewer to strengthen our argument regarding regression versus classification settings. Thank you again. Please let us know if questions remain. [1] B. Neyshabur, R. Tomioka, and N. Srebro, “In search of the real inductive bias: On the role of implicit regularization in deep learning,” in Proc. ICLR, 2015. [2] R. Parhi and R. Nowak, “Deep learning meets sparse regularization: A signal processing perspective,” IEEE Signal Process. Mag., vol. 40, no. 6, pp. 63–74, 2023.
I thank the authors for the reply. However, they are not to the point. [Near-identity assumption] The authors' response mentioned a lot of prior research under the near-identity condition, instead of talking about whether the assumption can be relaxed or removed. After checking the proof, I don't think the results still hold in practical settings. [$\ell_1$-regularization] Again, the response mentioned many benefits (prior works) of $\ell_1$-regularization, however, there is no reason to think this regularization is general. I hope to see a response that explains dependence of the results on regularization methods. Moreover, I think the phrase "(using $\ell_1$-regularization) to mimic deep-learning practice" should be removed. [Classification vs. regression] I thank the authors for providing the simulations. However, as the authors agree, it is more like a conjecture (instead of being conclusive) that the results of the paper extends to classification. More importantly, it is not reasonab le to claim regression is more general than classification, given these "evidences". I think the best way is to remove those claims about the relationship between classification and regression.
Thank you for reading our rebuttal and your response---really appreciated. We accept your opinion, but it seems that we disagree on fundamental issues. If the expectation is an entirely complete theory that takes into account all practical aspects, then we certainly failed. However, we ourselves are not aware of any such theories---in any scientific field. Our expectation was to make a major step forward toward this ideal, in our opinion unreachable theory, and we feel that we have achieved that.
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?
Rating
6
Confidence
3
Soundness
3
Presentation
4
Contribution
3
Response to reviewer XWT5
We thank the reviewer for the positive evaluation and for raising valuable and insightful comments and questions. Please find our responses below. We will incorporate all these changes into our main PDF. **``Extending empirical studies:''** We have now added additional simulations, including evaluations on the **MNIST, fashion-MNIST, and K-MNIST** dataset using **cross-entropy loss**, with a neural network consisting of $10$-layer weight matrices and ReLU activations, with network width $50$. We also repeated the experiments with simulated data over **deep neural networks (with $4$ layers)**. Please find our detailed discussion around new experiments and results in the general response (continue) above. **``Near-identity assumption:''** Regarding the feasibility of our near-identity assumption, the possibility to relax it, and the extension of our results to more complex models, we would refer to our detailed discussion on this aspects in the general response for further clarification. **``Beyond SGD optimizer:''** We would refer to our general response (continue), where we discuss and provide additional experiments using the **Adam optimizer**. Thank you again. Please let us know if questions remain.
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.
Rating
6
Confidence
3
Soundness
3
Presentation
2
Contribution
3
We thank the reviewer for the positive evaluation and valuable comments. Please find our responses below. We will incorporate these changes into the main PDF. **``Statement of Assumption 2 and Theorem 3:''** We agree with the reviewer that the statement of Assumption 2 (as well as Theorem 3) can be improved in writing and to be revised as follows: **Assumption 2 [Model Assumptions (ReLU)]** We assume that the target function can be approximated by such a neural network, that is, there is a pair $ (\gamma^*,\Theta^*)\in B$ such that $||\gamma^*|| ,||\Theta^*|| \leq \sqrt{\log{n}}$ and $\Theta^*= \boldsymbol{I}_{w}+A$ for $A\in R^{w\times w}$, in which, $|||{A}||| \le \tau$ with $\tau\to 0$, and that $f[x]={\gamma^*}^T \sigma(\Theta^* x)$ for all $x\in R^{d}$. We use the same statement as above for Theorem 3 as well. We will apply these new changes over our main pdf file. **``Near-identity assumption:''** We acknowledge that our assumptions for ReLU setting are necessary assumptions for Theorem 3 to hold (under our current proof approach). However, we refer to our detailed discussion in the general response to clarify why these assumptions are reasonable and practical. **``Technical results:''** We have now provided a high-level overview of our proof approach in Theorem 1 (similar steps also be followed for Theorem 3) and the necessity of each technical results for each step of our main theorem for more clarification: *Step 1:* We first connect the population risk of a rescaled version of the target to the population risk of the rescaled version of the estimated network using Taylor expansion. This step involves analyzing the behavior of the Hessian matrix of the population risk along the line segment between a rescaled version of the target and the estimated network (where we employ Propostion 1 or Proposition 2 for ReLU case to address the Hessian behavior) . *Step 2:* Next, we use our definition of a stationary point, the result from previous step, and some linear algebra techniques to bound the population risk of the estimated network. This bound is expressed in terms of three factors: 1) the population risk of the target, 2) the growth of the absolute difference between the gradient vector of the empirical risk and the population risk over the estimated network, and 3) the behavior of the Hessian as described earlier. *Step 3:* The growth of the second term is addressed using tools from empirical process theory (Lemma 1). For the third term, we employ our result from Proposition 1 (or Proposition 2). Given that the Hessian matrix is positive semidefinite, we can omit the related term from our bound since it has a negative sign in front. **``Extending experiments:''** We have now extended our simulations by employing more complex networks and testing beyond our simulated data. For instance, we applied our method to the **MNIST family dataset** using **cross-entropy loss**, with a neural network consisting of 10-layer weight matrices and ReLU activations. Our results continue to support the same conclusion we aim to demonstrate (please see our general response-continue for a detailed version). We also repeated the experiments in our Section 4 with simulated data over more **deep neural networks (with $4$ layers)**. Please find our detailed discussion in the general response-continue above. **``Tuning parameter:''** As stated above, the tuning parameter should be chosen to match the scale of the effective noise (that means larger than the suprimum over the empirical process), inspired by ideas from high-dimensional statistics in linear regression (please see also the high-level overview of our proof approach for Theorem 1 above). Naturally, the ``optimal tuning parameter'' is $r=r_{orc}$, as it provides tighter bound. Thank you again. Please let us know if questions remain.
We thank the authors for the detailed responses. I think my concerns are addressed in some extent, especially the writing of the paper. I will raise the score by 1 from 5 to 6.
We deeply appreciate the reviewer for raising the score to 6. We remain open to any further feedback or suggestions.
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?
Rating
3
Confidence
3
Soundness
2
Presentation
3
Contribution
2
Response to reviewer E732
Thank you for your valuable comments: these will definitely help us improving the writeup of our paper. Please find our responses outlined below: **``Boundedness Assumption:''** First, there seems to be some confusion about the boundeness assumption. To start with, boundedness is not sufficient to prove Theorem 1 and Theorem 3: as stated in line 968, stationarity is necessary. Indeed, if it were not, then *all* points in a bounded region would be good parameters, meaning that no optimization would be necessary altogether---which is in clear contrast to deep-learning practice---and the whole idea of data science more generally. Moreover, we have devoted an entire section (Section G of the Appendix called ''ON THE REASONABILITY ASSUMPTION ON THE STATIONARY POINTS AND THE POINTS NEARBY'') to relaxations beyond the simple boundedness assumption (please see our Theorem 5). We also argue that the norm bound over the stationary point is just a multiple of the norm bound over the target, in line with [li2017], who state that ``(ReLU shallow) networks with small average spectral norm already have good performance.'' We, therefore, believe that the assumptions are much weaker than they might have appeared. **``Definition of approximate stationarity''** Regarding the alternative definition of approximate stationarity, the reviewer is correct; our definition does appear to differ from that in the literature. However, in Section H of the Appendix called “Dynamical Accessibility of Approximate Stationary Points,” we provide a detailed argument on how our definition can be connected to the concept of small gradient norms found in the literature and in general its dynamical accessibility. We also had already mentioned this point in our main text lines 236-238. **``Proof of Lemma 1:''** Regarding the question raised about our proof for Lemma 1, we try to address the confusion with raising two points: 1. Please note that as stated in our proof for Lemma 1, the assumption is that $\tilde \beta \in C_{\eta,\epsilon}$, that implies $ || \beta^* -\tilde\beta|| \le \eta$ (norm-one bounded) by the definition of $C_{\eta,\epsilon}$, in which the exact values of $\epsilon$ and $\eta$ are assigned later in the proof to make sure that $\tilde \beta \in C_{\eta,\epsilon}$ always holds. 2. Our motivation in Lemma 1 is to find an upper bound for the term inside the absolute value on the left hand side of Lemma 1 in terms of $||\beta^*-\tilde\beta||_1$ (and **not $\eta$**), that is why we go through the proof in Lemma 1. Thanks for raising this point. We will clarify these points in our proof. **``Proof of Theorem 1:''** Regarding the question, we argue that the proof of Theorem 1 can be generally written around an arbitrary point $\beta$ near the stationary point, similar to the approach in Elsener2019's proof for their Theorem 7. Ultimately, however, the goal is to compare the error at the stationary point with the target error, treating the point $\beta$ as the ground truth, since the ground truth definitely gives the smallest generalization error. This means we would upper bound the generalization error of the stationary point in terms of the error in the target, plus additional terms that account for the suboptimality of our estimator. Thank you once more for you feedback: much appreciated. We hope our responses addresse your questions; if not, please feel free to let us know.
I thank the authors for their response. My concerns are not yet fully addressed and I am grateful if the authors could provide further clarifications. - ``Boundedness Assumption:'' **"if it were not, then all points in a bounded region would be good parameters,"** Yes, this is precisely the point I am trying to make, the bound you have established would hold for the whole bounded set. Just like Rademacher bounds or VC bounds, they are _uniform bounds_ that hold for all points in the bounded parameter set. The technical tool used in your result is Lemma 2, a result that controls the probability of a supremum over the whole set: this is exactly the argument used in uniform convergence bounds. This is where my main concern lies. The suprema over sets in Lemma 2(the technical tool behind Lemma 1) is the main indication that the result presented is not dependent on the points being stationary. The theorems in the paper appear to be results for all bounded networks. - ``Definition of approximate stationarity'' I tried to give in my earlier review an example to show that the arguments in that section do not show dynamic accessibility: having a small gradient norm *does not imply* closeness to a stationary point without a gradient domination condition. For example f(x) = exp(-x^2) stationary point is at 0 but you can have very very small gradient norms far from zero. You need additional assumptions to show that your definition of stationarity can be reached. - ``Proof of Theorem 1:'' The fact that the optimality of $\beta*$ is not relevant to Theorem 1 is a further indication to me that the bound is a uniform bound. It does not appear to me that the results are showing anything specific to stationary points, but rather, are establishing a bound for all points in a bounded set. **Lemma 1** I kindly ask the authors to please clarify the proof of Lemma 1 in an updated revision. It is not possible to substitute $\eta$ (a non-random quantity) with a random quantity $\tilde{\beta}$. If one considers the role $\eta$ plays in Lemma 2, $\eta$ multiplies sums of random variables. If eta were random it would break independence of the terms. The case separation in the proof without _explicit conditioning_ does not make sense. Saying we are in case 1 is restricting the probability space. The $\mathbb{P}$ appearing in Lemma 1 would then be a conditional expectation. As it stands, I cannot ensure the correctness of Lemma 1. I thank the authors for the clarifications they could bring on these points.
Thank you for your further comments. It seems there is still misunderstanding about basic aspects; in particular, the proof of Lemma 1 is correct as is. Let us try to clarify the issues and questions one by one: **``Definition of approximate stationarity'':** First, our definition of an approximate stationary point, as outlined in Equation (7), is based on the absolute difference in objective function values. In contrast, the literature often defines approximate stationary points using norm bounds on gradient vectors. For instance, studies such as [Ghadimi, 2013] and [Lei, 2019] analyze the rates of convergence of certain optimization methods under the definition of bounds over gradient norms, subject to certain assumptions (as reviewer mentioned). These are referenced in Equations (17) and (18) of our appendix. In Section H of the appendix, we demonstrate that our definition of approximate stationary points in Equation (7) aligns with these established definitions in the literature (based on bounds over the norm of gradients). That said, the main focus of our work is not to address challenges in specific optimization algorithms nor their rates of convergence. This topic presents another direction for future research and could be explored in subsequent studies. However, our motivation in Section H is to compare our definition of approximate stationary points with those in the literature, offering valuable insights into the dynamic accessibility of the corresponding suboptimal points. **Theorem 1 and Lemma 1:** Please note that Lemma 1 is not specific to stationary points, nor does it need to be. Its purpose is to establish the optimal rates for the tuning parameter, same as the concepts in Rademacher complexity and VC-dimension computing the complexity of the network space. As reviewer mentioned, Lemma 1 can hold for all $\beta$ (not just $\tilde{\beta}$) but we specifically wrote it for $\tilde \beta$ since we need that case for the proof of Theorem 1. We would also like to emphasize that Lemma 1 and Lemma 2 are not the central components of our paper; rather, they serve as tools to determine the optimal tuning parameter by computing the complexity of the network space under consideration. But importantly, **the role of the stationary point $\tilde{\beta}$ comes in the proof of Theorem 1** (please see lines 956--971), where we exactly use the definition of stationary points. We are totally confused with the reviewers question concerning that the definition of stationary point is unnecessary for the proof of theorem 1, while we emphasize that our stationary point definition is necessary and used as mentioned above and that just bounded parameters are not enough proving Theorem 1. In short, while Lemma 1 can also hold for all points in the considered network space (as reviewer mentioned), our main results, Theorem 1 and Theorem 2 can just hold for ``stationary points'' that is the main contribution of this work. **Proof of Lemma 1:** Let's add a quick point to clarify about your concern around our proof for Lemma 1: First, we would emphasize that $\eta$ is fixed in our setting with $\eta=4\sqrt{\log n}$ (as it is stated in Line 1542) and it is not dependent on the stationary point $\tilde \beta$. Then, for fixed $\eta,\epsilon \in (0,\infty)$ and $\forall \tilde \beta \in C_{\eta,\epsilon}$, which implies $|\tilde \beta-\beta^*|\le \eta$ (please note that here for latex issues we have to employ notation $|.|$ for norm one of a vector), we have (we also assume without loss of generality that $1/n <\eta $) $$ P \bigl(Z(\tilde \beta,\beta^*) \ge 2|\tilde \beta-\beta^*| \tilde r(t)s_{C_{\eta,\epsilon}}+\tilde r(t)s_{C_{\eta,\epsilon}}/n\bigr) $$ $$ =P\bigl(|\tilde \beta-\beta^*| \le 1/n ~~ \cap ~~ Z(\tilde \beta,\beta^*) \ge 2|\tilde \beta-\beta^*| \tilde r(t)s_{C_{\eta,\epsilon}}+\tilde r(t)s_{C_{\eta,\epsilon}}/n\bigr) $$ $$ +P\bigl(1/n <|\tilde \beta-\beta^*| \le \eta ~~ \cap ~~ Z(\tilde \beta,\beta^*) \ge 2|\tilde \beta-\beta^*| \tilde r(t)s_{C_{\eta,\epsilon}}+\tilde r(t)s_{C_{\eta,\epsilon}}/n\bigr). $$ Then the rest of the proof can be concluded from our Case 1 and Case 2 in the proof of Lemma 1. We will add these points to our main text to remove confusion in our final version. We hope that these responses help to clear up the confusion. Thanks again for interacting.
General response
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.
General response (continue)
**Extending empirical studies:** We now have extended our empirical studies in three directions: *1-Beyond SGD:* Our results provide a general theory targeting stationary points independent of the specific optimization algorithm. As already discussed above, there are papers in the literature that study the convergence of gradient based methods under identity initialization [bartlett2018;li2017], which appear to support our theoretical findings. However, we are not aware of any theoretical work within the same context that specifically targets other optimization methods, such as Adam. Nonetheless, we believe the choice of optimization method can influence the results by affecting how well the final stationary points satisfy our assumption. For the sake of completeness, we have now included further simulation to assess the impact of changing the optimization method. Specifically, we replaced SGD with **Adam**, using a learning rate of $0.005$, to analyse its effect on the simulation outcomes in Table 1 (of our paper). Our results are reported in Table 1 below. These results show that the performance of SGD appears to be more aligned with our case (in comparison with Adam; compare results here with Table 1 of our paper), but in general, approximate sub-optimal solutions remain still satisfactory. ### Table 1: Employing Adam for Simulations of Section 4 | | Linear: Training Error | Linear: Test Error | ReLU: Training Error | ReLU: Test Error | |------------------------------|------------------------|--------------------|-----------------------|------------------| | Approximate Stationary Point | 1.0007 | 1.003 | 1.20 | 1.27 | *2-Conjecture for deep neural networks:* We have now extended our simulations in Table 1 (of our paper) employing neural networks with $4$ layers. Our numerical observations make this conjecture that our theory may also hold for deep networks (with possibly minor different rates), given we reached the results in Table 2 below: ### Table 2: Conjecture for Deep Neural Networks | | Linear: Training Error | Linear: Test Error | ReLU: Training Error | ReLU: Test Error | |------------------------------|------------------------|--------------------|-----------------------|------------------| | Approximate Stationary Point | 1.002 | 1.004 | 1.16 | 1.21 | *3-Beyond regression* We have now extended our simulations by employing more complex networks and testing beyond our regression simulated data. We applied our method to the **MNIST, fashion-MNIST, and K-MNIST** dataset using **cross-entropy loss**, with a neural network consisting of $10$-layer weight matrices and ReLU activations, with network width $50$. Our results continue to support the same conclusion we aim to demonstrate for approximate sub-optimal as Table 3. This observation can support the conjecture that our results can be extended for classification settings and even for deep neural networks in further studies. ### Table 3: Beyond Regression | Dataset | ReLU: Training Error | ReLU: Test Error | |----------------------------------|----------------------|------------------| |Approximate Stationary Point (MNIST) | 1.0004 | 1.39 | |Approximate Stationary Point (Fashion-MNIST) | 1.00005 | 1.40 | |Approximate Stationary Point (K-MNIST) | 1.00003 | 1.18 |
Dear Reviewers, We have updated our manuscript to incorporate your valuable suggestions, improving the quality of our paper. Specifically, we have included additional simulations and revised some sections (following our responses) to improve the clarity. To ensure we have fully addressed your concerns, we welcome your feedback and are happy to address any remaining questions or suggestions. Thank you for your thoughtful review and valuable input. Sincerely, The Authors
Dear reviewers, Thank you very much for the interactions so far. If you have any further questions about our rebuttal, we would be happy to answer them. Best regards, Authors
Meta-review
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.
Additional comments on reviewer discussion
Strong objections to acceptance were raised on account of the issues outlined above, which remained unresolved despite the discussions.