Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a new insight in proving the convergence of the training of deep learning. Taking advantage of  the notion of Rayleigh quotients, the authors show that  KL inequalities for a broader set of neural network architectures and loss functions can be obtained. Moreover, several illustrative examples are provided to demonstrate their idea. In particular, their analysis does not require over-parameterization.
strengths_and_weaknesses: My detailed comments are given as below.

Strengths:

1 This is a theoretical article on the convergence of the GD for deep learning. This topic has been intensively studied recently. Most of previous works require the over-parameterization. But this work is different, and it presents a new strategy in proving the convergence based on the Rayleigh quotients and the KL inequalities. This innovative idea has intrigued me, and I feel that this article contributes significantly to  the understanding of training dynamics of NNs.

2 One of main limitations of previous works is that their arguments require the positiveness of the NTK which further requires the over-parameterization. This paper points out that  one can bound the Rayleigh quotient of the gradient instead of lower bounding the eigenvalues of the NTK. Furthermore, the authors show the connection between the Rayleigh quotient and the KL inequalities which ensure the convergence.

3 This paper is very well written and easy to read. Several case studies are presented in Sec 4.These cases are common and representative, and make their ideas very convincing. Moreover, the proof seems clean. Although I did not thoroughly examine the proof, it provided me with several fresh perspectives.

Weaknesses:

This paper argues that the proposed new strategy can be used to prove the convergence of deep learning architectures to a zero training".  However, only two-layer NNs are discussed in case studies. Can you provide some cases to support your argument on ``the deep architectures"? 
questions: Minor issues:

1 A table of notations is preferred.

2 What does the ``uniform conditioning" (in Line 19) mean?
limitations: YES
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper presents a strategy to prove the loss convergence of gradient flow for training loss of the form $\ell(F(\theta))$, where $F$ is the vector consisting of neural net outputs on each data point, and $\ell$ maps the outputs to the final loss value (e.g., $\ell$ can be the MSE to target values). Previously NTK-based analysis assumes that the smallest eigenvalue of the NTK matrix $K = DF \cdot DF^\top$ is bounded from below, then proves the loss convergence through establishing the PL condition under this assumption. In this paper, the authors avoid the assumption on the smallest eigenvalue and instead point out a proof strategy based on Rayleigh quotients of the NTK matrix and KL condition. This strategy is then applied to prove loss convergence bounds for linear regression, linear logistic regression, and some partial results are also given for two-layer net with squared loss.
strengths_and_weaknesses: ### Strengths:

1. The proposed proof strategy does not require the smallest eigenvalue of the NTK matrix to be lower bounded, allowing analysis when the number of data is more than the number of parameters.
2. Applying the proposed proof strategy gives an alternative way to understand the loss convergence bound for linear regression.

### Weaknesses:

1. While it sounds more promising to establish loss convergence bounds beyond the over-parameterized regime, this paper does not prove any concrete theorem on nonlinear neural nets with fewer parameters than the number of data. In Sections 4.4 and 4.5, the authors give some partial results establishing loss convergence under the assumption that the gradient flow does not move far from the initial point. This assumption weakens the strength of the results because it seems to be a more interesting and important question that why gradient flow does not intend to move far away in search of a better solution. In other words, it is unclear how useful the proposed proof strategy is in terms of overcoming the various difficulties in analyzing loss convergence beyond over-parameterized regime.
2. The results on linear logistic regression are not well contextualized relative to prior works. The authors claim that the loss convergence bound in this case is new (Line 97), but it is unclear how it compares with previous works such as the $O(1/t)$ bound in Theorem 5 of [1] for binary classification (see also Appendix E for the multi-class case). These two bounds should be the same when $t \to \infty$, so the authors should compare them carefully in the non-asymptotic case.
3. The presentation of the current paper is not very understandable, since there are too many notations and the notations vary in different settings. I spent hours reading this paper to understand and memorize all these notations just to understand the basic idea. One main issue is that the definitions in Sections 2 and 3 include too many technical details that are unrelated to the idea of bounding Rayleigh quotients, e.g., the concept of D-seminorm is somewhat unnecessary because one can just replace the D-seminorm of $\nabla \ell_f$ with an expectation over the dataset, which is more accessible to the readers. To improve the presentation, I recommend the authors to either reduce the number of notations or add a warmup section that illustrates the proof strategy in a simple case (e.g., linear regression) before introducing the general setup.

[1]. https://www.jmlr.org/papers/volume19/18-188/18-188.pdf
questions: 1. I wonder if the authors have some concrete examples showing that loss convergence bounds can indeed be deduced for nonlinear neural nets beyond the over-parameterized regime (without extra assumptions).
2. How does the loss convergence bound in the linear logistic regression case compare with prior works? How much is known about the loss convergence rate of linear logistic regression in the literature?
3. When does the isolation assumption hold in Proposition 4.5?
limitations: The major limitation has already been mentioned in Weakness 1. Besides that, this paper also has some limitations that are common in many optimization papers: (1) the dynamics of SGD and gradient flow can be very different; (2) the loss function can be non-smooth.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work investigates the convergence of gradient flow to zero training (and test) loss. The main idea is to derive Kurdyka-Lojasiewicz inequality which is accomplished by lower bounding Rayleigh quotients, and several showcases of common learning problems have been analyzed by this technique. 
strengths_and_weaknesses: Overall the paper is well-written and the main messages are easy to follow. However I had problems in understanding section 4.5 and its proofs, as well as prop 4.2, and couldn't check their correctness. Other results, except for prop 4.6 which might need slight modification discussed later, seem to be correct. The main weakness can be seen in discussing the conditions under which prop 4.6 and prop 4.5 hold, as addressed in below.

I like the argument that Prop 3.1 makes the loss evolution more tractable using the function $\phi$. Indeed in line 164 you provide $\phi$ when PL condition is satisfied and further in section 4.3 provide example for multi-class logistic regression. In Prop 3.3 you argue that functional-space KL inequality is easier to obtain and together with Rayleigh quotient bound they imply parametric-space KL inequality, hence able to use the convergence result of Prop 3.1. The techniques employed throughout Prop 3.4-3.6 to split the Rayleigh quotient bound seems powerful and its first simple use is shown in linear models with quadratic loss in Prop 4.1.

I would also like to know about any previous work that analyzes Cross-entropy minimization with linear models, assuming you are not the first paper to consider it. 

Overall the references include major important works in related areas, and some of them deal with Gradient Descent and overparameterized models. Please pinpoint the works that do not have overparametrized assumptions and if possible, compare your work to them. For example in line 150, you mention that "this was introduced as an extension to PL inequality for linear convergence ...". Please include as many references as possible that revolve around using inequalities in Kurdyka [1998]. One suggestion is to defer the proof of prop 4.1 to appendix so that you have more space.
questions: Typo:
line 319, "be compact". line 703, "has a ...". line 730, equation (1), it should be "l.h.s $\leq \frac{\eta}{2}$". in equation just before line 737, it might be $\frac{\eta}{2} + \frac{R}{\sqrt{k}}$, which yields $\sqrt{k}\geq 2R/\eta$. line 360, "there there". line 545, there might be an error in calculating first component of the gradient.

Questions and suggestions:

1- Proof and statement of Prop 4.6 needs revision. First I can't find a proof that $\theta(\mathbb{R}_+)\subseteq \mathcal{B}(\theta_0,R)$ if $\theta$ is a gradient flow, and in fact you just assume this condition holds in line 745 without proving it and further in line 328 you defer its proof to future work. Please indicate what is the difficulty in proving it. Most importantly, in the beginning of page 27, the conclusion in the 3rd line $\cdots \geq \frac{1}{\lVert \nu_0 \rVert^2}(\mathcal{L}(\theta_0) +0 - \epsilon)^2 $ does not seem correct because $a\geq b $ does not imply $a \geq b$. However it seems that there is a fix for that because you just need to consider $\lVert \nabla \mathcal{L}(w,a) \rVert_2 \geq \cdots \geq \frac{1}{\lVert \nu_0 \rVert}(\mathcal{L}-\epsilon)$. Even with this change, the argument in line 751 needs explanation on how you use prop 3.1 to show $\overset{\sim}{\mathcal{L}}(\theta)$ converges to zero. One way I can think of is to use $\phi(u)=-\frac{1}{u}$ which is a strictly increasing differentiable function on positive real numbers and $\phi'(u)=\frac{1}{u^2}$ and it gives $\lVert \nabla \tilde{\mathcal{L}}(\theta) \rVert^2 \geq \mu \tilde{\mathcal{L}}(\theta)^2$ which is true here as you assume $\mathcal{L}(\theta_t)\geq \epsilon$. Hence by showing that $\mathcal{L}(\theta_t)$ converges to $\eta\leq \epsilon$, it follows that $\mathcal{L}(\theta_t) - \epsilon$ is negative for large enough t, and hence $a \geq b$ does not imply $a^2 \geq b^2$ with $a=\lVert \nabla \mathcal{L}(\theta) \rVert$ and $b=\kappa (\mathcal{L}(\theta) - \epsilon)$. Finally I would like to know about rate of convergence by using Prop 3.1. It seems to me Prop 3.1 can only be used to show contradiction, i.e. $\eta\leq\epsilon$, and I'm wondering if $\lVert \nabla \mathcal{L}(\theta) \rVert \geq \kappa (\mathcal{L}(\theta) - \epsilon) $ can be used with prop 3.1 to give any rate of convergence.

2- (when) is the $\kappa$-isolated condition in line 307 satisfied? I couldn’t find how it is proved anywhere in the Proof section, and stating under which conditions it is satisfied seems crucial. Also please discuss how fast is the convergence rate of prop 4.5.

3- It is true that existing a "non-zero" $\epsilon$-separating ray leads to unique label in softmax classifier and also interesting that separating ray with zero loss implies dirac labels. Please cite any existing work that considers this separating ray assumption, assuming you are not the first one.

4- in line 590, is the conclusion $\nabla \ell(u): x\rightarrow \nabla \ell_x(u(x))$ a result of Lemma A.1?

5- in line 583, please explain more thoroughly how "convergence of positive r.v.s in expectation to zero leads to some subsequence converging a.e. to zero".


limitations: The limitations concerning conditions under which prop 4.6 holds is discussed in lines 328-331. However I couldn't find how $\kappa$-isolated in line 307 and $\epsilon$-separating ray in line 309 are satisfied. It is strongly suggested to discuss these in the appendix.
review_title: null

Meta-review: metareview: This paper proposes a new method for proving the convergence of gradient flow to zero loss by leveraging Rayleigh quotients to establish KL inequalities, a strategy that can apply even without overparameterization. The reviewers found the paper to be well written and generally easy to follow, despite a few concerns about burdensome notation. The discussion highlighted a few minor technical issues which were addressed in the revision. Overall the consensus is that this paper provides valuable new tools and the results will be of interest to the theory community, so I recommend acceptance.

confidence: Less certain
Decision: Accept