Deep linear networks for regression are implicitly regularized towards flat minima

Summary

The paper explores the behavior of deep linear neural networks in the context of overdetermined univariate regression, which is the setting of a univariate response $y$, more samples than input dimensions, and nonsingular data covariance matrix. The first result concerns the empirical risk minimizer (this is not equal to the gradient descent or gradient flow estimator) and shows a lower bound on the sharpness of the ERM. The next set of results show that gradient flow, a limit of gradient descent with a vanishing learning rate, implicitly regularizes the network towards flat minima, with sharpness close to a constant times the lower bound. This is proven for both small-scale and residual initializations.

Strengths

* The exposition is excellent. There are three main results, each given in its own section corresponding to Section 3, 4, and 5. * The setting described in Section 2 is mathematically clear * The first main result, Theorem 1, reaches a similar conclusion to previous work in Mulayoff and Michaeli (2020) but relaxes identity data covariance assumption and uses a supposedly simpler proof. * The next set of results characterize the gradient flow minimizers. This is indeed of independent interest, although the connection to sharpness is also interesting. * The sharpness papers I have come across seem to focus on sharpness induced by SGD. It's interesting that here the authors were able to demonstrate a preference for sharpness for deterministic gradient flow, albeit with specific initialization schemes.

Weaknesses

* I missed a rigorous theoretical connection between the three main results and the behavior of the gradient descent minimizer. If the connection is only empirical in nature, it might be good to highlight this * The work employs, to my eyes at least, a rather limited definition of sharpness. Are the results really very particular to sharpness being the largest eigenvalue of the Hessian? * I'm missing some motivation for the two initialization schemes studied. Are they studied simply because they've been studied before and so the results here can borrow from existing work? * I find the title misleading. An architecture cannot have a preference for flat minima(?). It must be the architecture in conjunction with how it is learned. In this case, the main results concern very specific configurations of gradient flow. * The implication for learning rate design from this theoretical analysis seems rather weak to me. I mean that I cannot envision a practitioner implementing a learning rate design based on the results presented here.

Questions

* Apologies for this very naive question, but what does $S(\mathcal W)$, the largest eigenvalue of $\mathcal W=(W_1,\ldots,W_L)$ mean exactly? This $\mathcal W$ is not itself a matrix. * Each of your results in Sections 3, 4, and 5 are based on existing proof techniques. Specifically, Section 3 proof is based on Mulayoff and Michaeli 2020, Section 4 on Ji and Telgarsky (2020), and Section 5 on Zou et al 2020, Sander et al 2022. I am not familiar with these papers. Do they attempt to prove similar things to this paper? Do you reach the same conclusions but with different proof techniques?

Rating

6

Confidence

2

Soundness

4

Presentation

4

Contribution

3

Limitations

* There are some obvious limitations that are par for the course in papers attempting to prove theoretical results in deep learning. Namely, the architecture here is extremely oversimplified. The data covariance being full rank is also unrealistic. Finally, the main results are about gradient flow and discrete-time stochastic gradient descent is surely very different in nature.

Summary

This paper studies the implicit bias of gradient flow on deep linear networks for overdetermined univariate regression problems. A lower bound on the sharpness of any minimizer is first derived for the general data covariance matrix, then it is shown that gradient flow with small initialization finds a minimizer with a sharpness no larger than a constant times the lower bound, where the constant depends on the condition number of the data covariance matrix. A similar result is also derived for GF on linear residual networks.

Strengths

1. Well-motivated problem. Good introduction. Clear writings. Theoretical results are carefully explained in the main paper. 2. New convergence results for deep linear networks and linear residual networks, together with the upper bound on the sharpness.

Weaknesses

1. **Tightness of Theorem 2**: In Mulayoff and Michaeli (2020), the lower bound on the sharpness is tight for whitened data: there exists a minimizer that achieves the lower bound. However, Theorem 2 in this paper only provides a lower bound. Is this lower bound improvable? For example, if the true lower bound has $\Lambda$ instead of $\lambda$, then the following results show that the sharpness minimizes found by GF is no larger than a constant times the lower bound, where the constant now does not depend on condition number. 2. **Relevance of the problem setting**: The sharpness is often considered to be affecting the generalization error of the trained network. However, this paper studies overdetermined linear regression, where every minimizer corresponds to the same input-output map $w^*$, thus having the same generalization error. Why does one care about studying the sharpness of the minimizer in this case, if sharpness does not affect generalization at all?

Questions

See Weaknesses

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

See Weaknesses

Summary

The paper considers a toy non-convex optimization problem, namely overdetermined univariate regression with a deep linear network. Their main contributions are: 1) A lower bound on the sharpness of the minimizers of the empirical risk. In particular, if the step size is chosen too big, then gradient descent will fail to converge. 2) They show that the sharpness of the minimizer found by gradient flow is at most a constant multiple of the above lower bound, for both small-scale and residual initialization. This constant does not depend on the width or depth, but only on the conditioning number of the data. This shows an implicit regularization towards flat minima (the empirical minimizers of the risk can have arbitrarily large sharpness). On the technical side, they prove convergence of the GF and characterize the solution at convergence in both initialization regimes. Numerical simulations are provided to illustrate and substantiate their claims.

Strengths

- The theoretical analysis is substantial. The results are novel and not straightforward. At the same time, they are easy to understand and offer clear insights. - The qualitative picture obtained in this paper, with the interplay between step size, scale at initialization, and sharpness of the gradient descent solution, is convincing and surprisingly clear, given the complex non-convex problem. In particular, I think it is interesting to have in a single model the behavior of sharpness, edge of stability and GD minimizer (even if only qualitatively). - The discussions are reasonably clear. The plots help a lot to understand the general message of the paper.

Weaknesses

The paper considers a simple setting: deep linear network and underdetermined regime. This allows the authors to characterize interesting and non-trivial behavior. However, it is unclear how much these results can extend beyond this simple setting.

Questions

Here, it is assumed that the data matrix is full rank. Is it not sufficient to assume that there exists a unique minimizer?

Rating

7

Confidence

2

Soundness

3

Presentation

4

Contribution

3

Limitations

Yes

Summary

The authors show three new results for deep linear networks (DLN). First, they show that any DLN that implements the optimal linear regressor must have a certain "sharpness". This amounts to a lower bound on the largest eigenvalue of the Hessian matrix at that set of weights. They then argue that the weights found by using gradient flow with two different types of initialization find minima that have a sharpness that is within a constant of this lower bound. They interpret these results as an implicit regularization of gradient flow towards flat minima.

Strengths

Results are novel. They are also of at least abstract interest to the community of researches working on the theory of deep learning. I also agree with their assertion that some of the intermediate results presented on the structure of weight matrices in DLNs post-training (e.g. approx rank 1 and aligned in small scale initialization case) might be of interest.

Weaknesses

The paper kind of has a mixed message, and doesn't really make the connection to generalization power in a way that is intepretable. Theorem 1 shows that the sharpness has to grow at a rate that is essentially linear in the number of layers. But then they mention that prior work indicates that flat minima generalize better, which suggests that making the DLN deeper is going to hurt you in this regard. The subjective interpretation of gradient flow going to flat minima is hard to digest when the authors just proved that there are no flat minima.

Questions

Do these results add to our understanding of the generalization power of deep linear networks trained with gradient flow?

Rating

6

Confidence

3

Soundness

4

Presentation

4

Contribution

2

Limitations

none

Thanks!

Thank you to the authors for their detailed response. I'd like to maintain my original rating that the paper is a "technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations."