- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper considers deep ReLU networks trained with full batch GD for a fixed number of steps, initialized by a concrete algorithm, and proves two main theorems under a set of assumptions. The most important assumption is a realizability assumptions regarding the training sample, the initialization and the resulting tangent feature space of the network. The first theorem intuitively states that for wide enough networks, the GD trajectories have some nice properties with high probability. The second theorem uses the first one to establish upper bounds on the true error (population risk measured via logistic loss) of the network both on average and for the last GD iterate, also with high probability. The proof technique heavily relies on prior work, mainly Wu et al. (2024) and Li et al. (2026), and, in my opinoin, can be viewed as a nontrival combination of existing techniques in order to generalize very similar results for shallow networs to deep ones, and also Li et al.'s deep network results to the case of arbitrary constant learning rates. The paper also contains a set of experiments in relation with the theorems.
Critical strengths
-
The paper contains rigorosuly proven theoretical contributions that is well motivated and properly positioned in the literature. The set of premises / assumptions is clearly stated, the resulting theorems also precisely stated, there are no informal theorems. The proof of every principal statement is fully written in the Appendix (some Lemmas are cited as is). During the limited review period I could not find any serious mistake in the proof.
-
In my opinion the results in this paper are (somewhat modest*), but worthwhile theoretical contributions to the field. *depending on the NTK assumption and the width constraints
-
The results deal with deep ReLU models, with mostly standard assumptions (see my questions regarding the NTK separability assumption though), there is no direct data separability, monotone training loss, etc.
-
The full proof can be found in the appendix, and a detailed discussion on the proof technique is present in the main text (Section 4.4), in which the proof technique is compared to existing literature.
-
The paper is very easy to read.
Critical weaknesses
-
I did not find satisfactory discussion on the realisticness / standardness of the assumptions, only previous use cases of the assumptions are cited. In particular, it is very unclear why Assumption 3 (NTK sep. ) is important, how realistic it is, how easy it is to check, what motivates it and what are its disadvantages. Same for Assumption 1, although that may be more natural. I can see some related arguments here and there in Section 4.4, but not an explicit discussion.
-
The width requirements in the theorems are given implicitly in , i.e. in Theorem 1 we have sth like , and the constants (e.g. R) are compacted so it is not clear how the required value of depends on the constants that are essential in the learning framework of the paper. For example as long as my calculations are correct, eq (2) unfolds into
m \ge \frac{C_2 L^{13}(\log m)^4\log(nL/\delta)}{\gamma^8} \left[{\max\{\gamma+4\log(1+2 \eta T)+\eta \left(4+2\sqrt2\gamma+\frac{\gamma^2}{2}\right),\sqrt2}}\right]^8
This means that among others, , and enter the lower bound in some way. It is not easy to see how and I find the existing discussion (lines 309-314 and Remark 2) not comprenehsive enough. Same goes for Theorem 2.
- Same goes for the bounding constants in eq (3)-(5) and (7)-(11). The discussion on these bounds is not detailed enough, in particular their dependence on important terms, like , , .
Remark 1 and 2 are useful, but should be extended.
- The width requirement seems very unrealistic. I may be mistaken here, but for accelerated optimization with fixed margin and depth, we have sth like . Is this true, so the paper is practically in the NTK regime? As I mentioned earlier, Assumption 3 is not properly discussed, the width requirement should also be discussed not just in terms of the constant dependences (my previous points), but in terms of this point. I see Table 1 (b) with a sufficient width condition, maybe that is what should be discussed in more details?
Questions for authors
-
Please discuss Assumption 3 (and maybe Assumption 1 a little? or is it that standard?). What does it have to do with lazy / NTK regimes? Is it realistic? Can we check it for concrete training sets and initialized networks? Is there an optimal margin, can it be computed? I get that it is used in other papers, but unless I start reading those other papers, I get no insight on why this assupmtion arises and what are its properties, pros and cons, etc.
-
Similarly, please discuss the width requirement in the Theorems. Why the implicit inequality? What does it mean in terms of the other hyperparameter of the framework, e.g. , , , , etc.? There is in Table (1), how does that arise? I'm sure it can be seen from the proof, but some insights in the main text would be desirable to get the intuition. I guess this is unrealistic width, but that is okay in NTK papers. Is it the case here, too? Can there be feature learning during GD under your framework?
-
Similarly, please discuss the bounding constants in the Theorem statements.
-
In my understanding of Section 4.4, the proof is a (straightforward?) generalization of the techniques in Wu et al and Li et al. Could you point out exactly which Lemmas in the appendix contain new tricks / proof ideas / calculations that have not been seen in those papers and which are not straightforward adaptations? Based on Sec 4.4, I'd say it is Lemma 10, and the contribution of Lemmas 8-9 are a bit unclear.
-
The experiments does not seem to present anything that has not been presented before. They do not concern with the artifacts of the theorem, but they illustrate certain related phenomena on toy examples. For example, we see how the loss curves change as depth, sample size, etc. vary, but we don't see how these effects are connected to the constants in the theorems. As far as I understand, the motivating empirical behavior has been established before and the theorems are intuitively in line with those empirical findings, I just don't see how the experiments connect to the actual contribution of this paper. Do any of the experiment contain any empirical findings related to the actual results? What is the added value of these experiments? Is this what Appendix E provides? My personal opinion is that the theoretical contribution of the paper is potentially solid enough (as long as my points above can be properly addressed) without these experiments.
Response the the Authors
I thank the Authors for their hard work and addressing all the points in my review. Based on their response I think my original score of the paper is correct. Namely, the paper indeed contains a worthwhile theoretical contribution in the form of Lemma 10, and the proper adaptation of existing techniques around it to obtain the main theorems. The problem is that this contribution is well within the NTK regime with its set of assumptions, especially the sufficient condition Ω(T8) on the width for the accelerated LR choice at fixed depth, thus the significance / relevance of the contribution to the field (and not just the NTK subfield of ML theory) is still a concern to me.
I think that a theoretical paper within the NTK regime should satisfy at least one of the following,
In contrast, the paper at hand
I am open to further discussion about the points above, but only if the authors have a firm understanding that I am mistaken in any of these points above and can support their arguments with concrete references to their paper and related work. Just for the sake of trying, please do not take each other's time.
While I sincerely hope this paper succeeds at the current conference, in case it does not, I suggest TMLR / JMLR type venues for this kind of work. TMLR website explicitly says ``TMLR emphasizes technical correctness over subjective significance, to ensure that we facilitate scientific discourse on topics that may not yet be accepted in mainstream venues but may be important in the future.''