Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies generalization and optimization of kernel-based and one-hidden layer neural network models. The convergence guarantee is shown for a Uniform-LGI loss function in Theorem 1. Then, in Theorem 2 the paper proves a generalization guarantee assuming a particular parametric model in Equation (3). Finally, the paper applies these results to p-norm regression, kernel regression, and one hidden layer neural network learning problems.  
main_review: The paper develops a convergence and generalization analysis of machine learning models under Uniform-LGI loss functions. The concept of Uniform-LGI loss functions extends the well-known PL condition in the optimization literature and as the paper shows leads to a nice theoretical setting for analyzing the optimization and generalization aspects of different machine learning models. The paper shows applications of the framework to norm-p regression and kernel regression problems as well as one-hidden-layer neural network learning problems.

Overall I think this is an interesting work which shows some insightful generalization results under Uniform-LGI loss functions. My main concern with the paper is that while the paper's title, abstract, and introduction claim that the analysis helps to understand the connection between the length of optimization and the generalization error of learned models, the theoretical results in Theorems 2-5 seem to only bound the generalization error of the final model and do not have anything to say about how the generalization error changes during training the model. I, therefore, suggest the authors either clearly explain how the theorems analyze the role of optimization length in the final generalization performance or change the title and introduction appropriately to reflect the main contributions of the work. 

In addition to the above comment, I am wondering whether the gradient flow simplification in Equation (1) results in a realistic analysis of gradient-based optimization in non-convex deep learning problems. It seems to me that the analysis may not be suitable for stochastic gradient methods which have been shown to achieve a significantly better generalization performance than full-batch gradient descent modeled in the paper. As my final comment, the paper has no numerical results validating the theoretical generalization bounds over standard supervised learning problems. Therefore, it is unclear whether the theory results are useful to bound the generalization error of practical deep learning experiments.
summary_of_the_review: The paper shows several interesting generalization results for Uniform-LGI loss functions. While the paper proves several insightful generalization bounds, it seems Theorems 2-5 do not explain the connection between the optimization length and generalization error. Also, the paper has no numerical results validating the generalization results.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a framework to analyze both optimization and generalization properties under the Uniform-LGI condition (Def 1). From my understanding, the main results consist of two parts:

* Optimization: define the Uniform-LGI as an extension of the PL condition, prove the corresponding convergence result with a sublinear rate, and bound the optimization path length.
* Generalization: use the Rademacher complexity to estimate the generalization error. The Rademacher complexity scales with the diameter of the parameter set, thus can be bounded by the optimization path length, which connects with the optimization results.

Then the paper apply this framework to three application models: first establish the Uniform-LGI, then calculate the optimization path length and estimate the generalization error.
main_review: This paper is well organized following the approach from optimization to generalization. The theorems and proofs are clearly stated and easy to follow. However, my main concern is that it seems to put two separate results (one for optimization and the other for generalization) together directly, and the novelty of each of the two results may not be significant enough. Also, the results may not support the claim “short optimization paths lead to good generalization” exactly.

For the optimization part, the definition of the Uniform-LGI (with parameter $\theta$) is inspired by the original Lojasiewicz inequality, and the proof of convergence is straightforward and similar to Bolte et al. (2007). Nevertheless, I think it is good to introduce the result to the community as an extension to the widely-used PL condition. The sublinear convergence rate is also interesting. It would be better to have more applications satisfying the Uniform-LGI but not the PL condition. In Section 4 only the $l_p$ linear regression has $\theta > 1/2$, and the other two models still fall into the PL condition.

For the generalization part, the estimation of generalization error follows the Rademacher approach. The proof is nontrivial while the idea is not complicated: the Rademacher complexity scales with the diameter of the parameter set, i.e., the optimization path length. To claim “short optimization paths lead to good generalization”, I may expect a path-based generalization bound; ~~I think the good generalization here comes more from the good “local landscape” (Uniform-LGI) rather than the “path”.~~ (Edit: my statement was not accurate—Theorem 2 does not require the Uniform-LGI. I mean the generalization bound does not depend on the whole optimization path, but only the endpoint, and the generalization is good if the endpoint falls in a small region.)

In addition, I think the numerical result in Figure 1 may not illustrate the relationship between the optimization path length and generalization—the larger $\sigma$ in the initialization (Appendix A) leads to both larger optimization path length and larger generalization gap. I think it would be more fair to compare them with the same $\sigma$ in the initialization.

**Update**

I appreciate the detailed response from the authors and the careful improvement of the manuscript. Here is my summary of the contributions of the paper:
* Optimization: it is good to propose the Uniform-LGI as an extension of the PL condition and show the sublinear rate. However, the Uniform-LGI is similar to the original Lojasiewicz inequality, and the proof is straightforward (similar to Bolte et al., 2007?).
* Generalization: Theorem 2 is equivalent to the following: given a region $S$ with radius $R$, with probability $1 - \delta$ over the training samples, for all $w \in S$, the generalization gap $$L_D(w) - L_n(w) \le \frac{A R + B \sqrt{3(p + q) + \log(2 / \delta)}}{\sqrt n}$$ where $A$ depends on the Lipschitz constants in $S$ and $B$ depends on the upper bound of $l$. Similar approach is taken by some previous work (e.g., Allen-Zhu et al., 2019); nevertheless, it is good to state the result precisely. I think the result would be better summarized as “small parameter region leads to good generalization bound”, and this is not surprising as the Rademacher complexity increases w.r.t. $R$.

Therefore, I would like to keep my original score given my concern about the significance of the novelty.
summary_of_the_review: The paper is well organized and clearly written. It is interesting to introduce the Uniform-LGI as an extension to the PL condition. However, I think the novelty of each of the two main results is not significant enough, and putting them together may not support the claim “short optimization paths lead to good generalization” exactly.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors study the connection between optimization and generalization for gradient flow (GF) on loss functions that satisfy a global version of the Lojasiewicz gradient inequality. Under this assumption, they prove convergence of GF to a global minimum and they find an upper bound on the optimization length — measured as the integral of the $\ell_2-$norm of the gradient from time $t=0$ to the final time. This upper bound depends on the specific choice of the loss function and on the number of samples. With an additional assumption on the hypothesis class (encompassing, e.g., linear shallow networks, two-layer networks) the first result is used to derive an upper bound on the generalization gap. The bound depends on the choice of the loss function, its initial value, and the length of the optimisation path. This leads to the main result that shorter optimization paths induce smaller generalization gap. The authors apply this result to three models (underdetermined $\ell_p$ linear regression, kernel regression, and overparametrized two-layer networks with ReLU activation) with a given target function. They compute non-asymptotic expressions for the generalization bounds at fixed ratio between sample size and ambient dimension, and show that in these cases the bounds are non-vacuous when the dimension increases.

main_review: The paper inscribes in the relevant research direction aiming at understanding the interplay between efficient optimization and good generalization performances by identifying complexity measures that are implicitly minimised during training. 

The analysis is sound and presented in a clear way. Overall, I found the results interesting and worth of publication although some improvements are needed. 

In my opinion, the main weakness of the work regards the numerical experiments. I find that the authors could have provided better evidence than Figure 1. It is not clear to me whether each point in Figure 1 comes from an average (at fixed initialisation variance) or is the result of a single simulation starting from random Gaussian initialization with that variance. The first option does not make much sense to me, so I am assuming the second. However, in this case, since the initialization is random I do not understand why the authors need to change also the variance instead of comparing the optimization paths starting from different initializations from the same distribution. The way the figure is presented suggests that the length of the optimization path trivially depends on initialization, and similarly the generalization gap. 

Moreover, all the experiments are performed for a learning rate $\eta=0.05$. Since the theory is valid in the limit of gradient flow, I would be interested in seeing how Figure 1 changes for different learning rates.

Finally, it would be interesting to test the generality of the proposed framework by checking the relation between short optimization paths and good generalization in more realistic data model. Has this relation been previously observed in applications?   
summary_of_the_review: I find that this paper is worth of publication since it provides an interesting contribution to a relevant research direction in the theory of machine learning. However, I believe that the authors must improve their numerical results to provide a convincing final version of the work.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper provides a novel generalization bound for the gradient flow equation related to the length of the optimization path. The bound is valid for loss function that locally satisfies Łojasiewicz gradient inequality, which is applicable to different machine learning models such as underdetermined $\ell_p$ linear regression, kernel regression, and overparameterized two-layer ReLU neural networks. Explicit derivations are provided for these three models to show that the length-based generalization bound is non-vacuous. 
main_review: The paper is well organized and easy to follow. My main concern is regarding the claim "short optimization paths lead to good generalization" which I feel misleading. The reason is that

a. The upper bound $r_n(w)$ is not path-length related. In contrast, it only depends on the function value gap $L_n(w) - L_n^*$. In other words, we first upper bound the path length by the function value gap, which is expected under Łojasiewicz gradient inequality, then use the later function value gap to derive the generalization bound. Unless the path-length is used in the proof of Theorem 2, I wouldn't call it a length-based generalization bound. Please provide more details on this point. 

b. I am not sure whether the following case is possible: there are $w_0$ and $w_1$ that for any $L_n$, the gradient flow from $w_0$ always pass through $w_1$. In this case, they always share the same solution but the path length of $w_1$ is always shorter than the path length of $w_0$. Even though this might be impossible, what I want to say is I don't find the shorter length-path as the cause (in terms of causality) of better generalization, instead, I think the function value gap is the real cause of it, which I believe is well studied in the literature. (it might be wrong but I am happy to further discuss it)

Overall, I can't see how explicitly the length of optimization path influence the generalization bound in the current analysis, instead it is based on the function value gap. I am willing to raise my score if my concern is addressed in the rebuttal. 
summary_of_the_review: My major concern is how explicitly the length of optimization path influence the generalization bound in the current analysis, instead it is based on the function value gap.
review_title: null

Meta-review: The paper presents several interesting generalization results for Uniform-LGI loss functions (a generalization of PL functions). Some of these bounds seem useful, but the overall connection with the optimization length remains unclear. This concern and other points of criticism remain present after the rebuttal phase. Other minor concerns seem fixable, but in a larger timeline compared to the camera ready one. The paper should be revised for a future venue.
Decision: Reject