Do Neural Networks Need Gradient Descent to Generalize? A Theoretical Study

Thank you for highlighting that our results answer very relevant questions and should be shared with the wider theory community. Thank you also for noting the soundness of our theory and the clarity of the text. Below we respond to the points you raised. If you find our responses satisfactory, we would greatly appreciate it if you would consider raising your score.

I feel the experiments in Section 5 is unnecessary.

While we agree that experiments are not strictly necessary for a theoretical paper such as ours, we chose to include them in order to demonstrate that the conclusions from our theory extend beyond the technical assumptions made.

The assumptions for Theorem 2 is really, really strong. Imposing the ground truth matrix to be rank 1 really simplifies the problem by a lot. I recommend the authors to extend this result to more general settings.

Theorem 2 indeed assumes that the ground truth matrix has rank one. While the theorem’s proof currently requires this assumption, its intuition is far more general: as the depth of the network increases, the product of weight matrices (drawn from a Gaussian distribution) tends toward low rank, thus fitting training data will be achieved with lowest rank possible. We corroborate this intuition empirically in the supplementary material (Figures 5 and 6), demonstrating the conclusions of Theorem 2 with ground truth ranks beyond one. Extending the formal proof of Theorem 2 beyond ground truth rank one is a valuable direction for future research.

The proof of Theorem 1 seems to heavily rely on the well-known equivalence between infinite width neural networks and Gaussian processes. This does somewhat diminish the technical novelties of the paper

The proof of Theorem 1 indeed builds upon existing machinery, in particular connections between neural networks and Gaussian Processes. We stress however that the theorem is not an immediate outcome of existing machinery (see complete proof in Appendix A). Moreover, its extension to the case where $\epsilon_{\text{train}}$ is unspecified (Appendix C) requires highly non-trivial arguments, namely, a strong form of random variable convergence, as well as Gaussian Correlation inequalities.

some might argue that the guess-and-check algorithm does not warrant research in the first place

As an algorithm, the relevance of G&C is indeed limited. However, from a theoretical standpoint, studying G&C is essentially equivalent to studying the volume hypothesis, and thus has profound implications on our understanding of neural networks (see our introduction).

little from this paper that could lead to wider implications

The validity of our conclusions for real-world non-linear neural networks was empirically demonstrated by Peleg and Hein ([1]), which found that the generalization of G&C is inferior to that of GD with wide networks, but comparable to it with deep networks. From a theoretical perspective, as we note in the text, we hope that our theory will serve as a stepping stone towards analysis of more realistic settings. One promising avenue in this direction would be the analysis of tensor factorization (tensor sensing with neural network overparameterization), which is a model much closer to real-world neural networks than matrix factorization (see, e.g., [2, 3]). Tensor factorization has various similarities to matrix factorization, thus we believe elements of our theory may carry over to this richer model. We will mention this in the conclusion section of the camera-ready version. Thank you!

Despite the conciseness of the overall message, I found the paper to be a bit more difficult to read than it should be. In particular, Definition 3 should be split into 2. And in many instances, equations should be on their own lines and equation block alignments are often not good.

Definition 1 should be moved to Section 4.3. And the author should add a bit more discussing the RIP property because it may be unfamiliar to a lot of readers.

The proof sketches for both Theorem 1 and 2 are kind of rushed and do not seem to capture all of the main technical steps of the actual proofs.

Thank you for these suggestions; they will certainly help us improve the readability and clarity of the paper toward the camera-ready version. In particular, we will carefully revisit the presentation of definitions and equations, consider additional clarifications on the RIP, and enhance the exposition of the proof sketches.

---

References

[1] Peleg and Hein. “Bias of Stochastic Gradient Descent or the Architecture: Disentangling the Effects of Overparameterization of Neural Networks”

[2] Razin et al. “Implicit Regularization in Tensor Factorization.”

[3] Razin et al. “Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networks.“

Theorem 2:

The proof begins by decomposing the factorized matrix $W$ into a product of three matrices: $W = W_d W_{d - 1 : 2} W_1$, where $W\_{d - 1 : 2} := W_{d - 1} \cdots W_2$. It then utilizes concentration bounds established by [3] for the Lyapunov exponents of $W_{d - 1 : 2}$ (product of $d - 2$ zero-centered Gaussian $k$-by-$k$ matrices), where the Lyapunov exponents, denoted $\lambda_1 , \ldots , \lambda_k$, are defined by $\lambda_i := \log ( \sigma_i ) / ( d - 2 )$, with $\sigma_1 \geq \cdots \geq \sigma_k$ standing for the singular values of $W_{d - 1 : 2}$. [3] gives non-asymptotic bounds on the deviation of $\lambda_1 , \ldots , \lambda_k$ from their infinite depth ($d \to \infty$) limits $\mu_1 , \ldots , \mu_k$, which satisfy $\mu_1 > \ldots > \mu_k$. Because $\sigma_i = \exp\left(( d - 2 ) \lambda_i\right)$, and because $\mu_i \neq \mu_j$ for all $i \neq j$, the non-asymptotic bounds imply that when $d$ grows, with high probability, $W_{d - 1 : 2}$ has one singular value much larger than the rest. More precisely, for any $\gamma \in \mathbb{R}\_{> 0}$, the probability that $W_{d - 1 : 2}$ is within $\gamma$ (in Frobenius norm) of a rank one matrix is $1 - \exp ( - \Omega ( d ) )$.

Next, the proof uses properties of standard multivariate Gaussian distributions (namely, their rotational invariance and concentration bounds on their norms), to argue that with high probability, multiplication of $W_{d - 1 : 2}$ by $W_d$ from the left and by $W_1$ from the right preserves the approximate rank one structure, and specifically, $W = W_d W_{d - 1 : 2} W_1$ is within $\gamma$ of a rank one matrix with probability $1 - O ( 1 / d )$. Employing compressed sensing arguments that rely on the RIP and the ground truth matrix being rank one (see, e.g., [4]), it is then proven that the probability of the events $\mathcal{L}\_{\text{train}} ( W ) < \epsilon\_{\text{train}}$ and $\mathcal{L}\_{\text{gen}}( W ) \geq \epsilon\_{\text{train}}c$ occurring simultaneously is $O ( 1 / d )$.

Finally, due to the fact that the distribution of $W$ is rotationally invariant, and that $W$ is with high probability close to a rank one matrix, the probability of $\mathcal{L}\_{\text{train}}(W) < \epsilon\_{\text{train}}$ is independent of the depth $d$, i.e., it is $\Omega(1)$. By the definition of conditional probability, this implies that the probability of $\mathcal{L}\_{\text{gen}}( W ) \geq \epsilon\_{\text{train}}c$ conditioned on $\mathcal{L}\_{\text{train}}( W ) < \epsilon\_{\text{train}}$ is $O ( 1 / d )$. This is the sought-after result.

---

References

[1] Hanin. “Random Fully Connected Neural Networks as Perturbatively Solvable Hierarchies.”

[2] Favaro et al. “Quantitative CLTs in Deep Neural Networks.”

[3] Hanin and Paouris. “Non-asymptotic Results for Singular Values of Gaussian Matrix Products.”

[4] Kutyniok. "Theory and applications of compressed sensing."

Dear Reviewer,

Kind reminder in light of the approaching deadline: we would greatly appreciate your response to our updated proof sketches. Thank you again for your engagement and willingness to consider raising your score.

Best wishes,

Authors

Thank you for highlighting the importance of studying the volume hypothesis in matrix factorization, the novelty of our results, the clarity of our writing, and the solidity of our theory and empirical support. We respond to your reservations and questions below. If you find our responses satisfactory, we would greatly appreciate it if you would consider raising your score.

In my opinion, the most restrictive assumption is that Theorem 2 requires the ground truth target to be rank 1. The proof of Theorem 2 relies on showing that in the large depth limit, the product $W_d…W_1$ is close to a rank 1 matrix. As such, if the ground truth were actually rank 2, it does not seem like the same proof technique would still work.

Theorem 2 indeed assumes that the ground truth matrix has rank one. While the theorem’s proof currently requires this assumption, its intuition is far more general: as the depth of the network increases, the product of weight matrices (drawn from a Gaussian distribution) tends toward low rank, thus fitting training data will be achieved with lowest rank possible. We corroborate this intuition empirically in the supplementary material (Figures 5 and 6), demonstrating the conclusions of Theorem 2 with ground truth ranks beyond one. Extending the formal proof of Theorem 2 beyond ground truth rank one is a valuable direction for future research.

Implications beyond matrix factorization towards more standard neural network settings (such as training a fully connected network on a simple dataset) are not clear.

The validity of our conclusions for real-world non-linear neural networks was empirically demonstrated by Peleg and Hein ([1]), which found that the generalization of G&C is inferior to that of GD with wide networks, but comparable to it with deep networks. From a theoretical perspective, as we note in the text, we hope that our theory will serve as a stepping stone towards analysis of more realistic settings. One promising avenue in this direction would be the analysis of tensor factorization (tensor sensing with neural network overparameterization), which is a model much closer to real-world neural networks than matrix factorization (see, e.g., [2, 3]). Tensor factorization has various similarities to matrix factorization, thus we believe elements of our theory may carry over to this richer model. We will mention this in the conclusion section of the camera-ready version. Thank you!

(minor) In Figure 2, it is not obvious that as depth increases, the generalization error converges to zero. The authors state that running gradient descent at larger depths is computationally prohibitive. But it seems like it should be straightforward to run guess and check at larger depths?

Thank you for highlighting a potential source of confusion. To clarify, our theory does not imply that the generalization loss of G&C tends to zero as depth increases. Rather, it implies that under G&C, if the training loss is smaller than $\epsilon_{\text{train}}$, then the probability of the generalization loss being less than some universal constant times $\epsilon_{\text{train}}$ tends to one as depth increases. Accordingly, achieving near-zero generalization loss could require a very small $\epsilon_{\text{train}}$, significantly lengthening the run-time of G&C. This point will be emphasized in the camera-ready version of the paper.

Notwithstanding the above, following your question we ran G&C with larger depths, and observed that the generalization loss continues to decline. These results will be added to the camera ready version of the paper.

The initialization in Theorem 1 seems to be an "NTK" initialization (hidden layer variances are 1/width), and the proof relies on showing that the pre-activations are close to Gaussian. It is not particularly surprising that in the linear/kernel regime, interpolating solutions do not generalize -- the intuition from linear regression being that the parameters in the subspace of the datapoints and the orthogonal subspace are independent. Is this understanding correct? And can you comment on what would happen if a different initialization were used that permitted feature learning (say muP/mean-field where the hidden layer variances are 1/width^2)?

Your intuition is generally correct, but its formalization requires a non-trivial step of showing that under the “NTK” initialization, the entries of the represented matrix $W$ (Equation (4)) are close to being independent. This is the essence behind the proof of Theorem 1.

If the initialization was smaller, in particular “mean field,” then as width increases, the distribution of $W$ would concentrate around zero. It is possible to show that in this regime, when the activation is linear, the entries of $W$ would still be close to independent, thus with high probability, the generalization of G&C would be close to that of the zero matrix (i.e., G&C would still fail).

Theorems 1 and 2 focus on what happens if either width or depth is taken to infinity, while the other is fixed. What if both are taken to infinity at the same time (say at a fixed ratio)? What would the generalization error look like?

Our theory does not indicate how G&C would compare to GD in a regime where network width and depth grow jointly. This is a very interesting direction for future work.

I would also appreciate if the authors could comment on my above concerns re the rank 1 assumption in Theorem 2.

See above.

---

References

[1] Peleg and Hein. “Bias of Stochastic Gradient Descent or the Architecture: Disentangling the Effects of Overparameterization of Neural Networks”

[2] Razin et al. “Implicit Regularization in Tensor Factorization.”

[3] Razin et al. “Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networks.“

—-

Quantitative details

Consider a square ground truth matrix $W^{*} \in \mathbb{R}^{k \times k}$ of rank two whose two leading singular values are equal (ground truth matrices of higher rank can be treated analogously). Hanin et al. ([1]) show that the Lyapunov exponents of $W := W\_d \cdots W\_1$, defined as $\lambda\_i = \frac{\log \sigma\_i}{d}$, $i = 1 , \ldots , k$, where $\sigma\_1 \ge \sigma\_2 \ge \cdots \ge \sigma\_k$ are the singular values of $W$, converge as the depth grows ($d \to \infty$) to independent Gaussians with means $\mu\_1 > \mu\_2 > \dots > \mu\_k$ and variances $O( 1 / d )$.

The probability of achieving low training loss is lower bounded by the probability that $W$ lies sufficiently close (in Frobenius norm) to the ground truth (if $W$ and $W^{*}$ are sufficiently close in Frobenius norm, then $W$ will also obtain low training loss).

By isotropy, the latter probability should be proportional (identical up to multiplicative factors depending on the training loss and the ambient dimension) to the probability of sampling an arbitrary rank two matrix with two equal nonzero singular values. Thus, the probability of approximating the ground truth matrix (in Frobenius norm) is governed by the event $\lambda\_1 \approx \lambda\_2$. If one assumes that for large but finite $d$ the limit established by ([1]) provides a sufficiently good approximation (this is the primary claim that requires more work to formalize), this probability should scale like $e^{-d(\mu\_1-\mu\_2)^2}$.

Failure to generalize can occur only if $W$ has rank $\ge 3$ (otherwise, generalization is guaranteed by the RIP). If we again assume that the limit provides a good approximation for large but finite $d$, then by independence this event should have a probability of roughly $e^{-d\bigl[(\mu\_1-\mu\_2)^2 + (\mu\_1-\mu\_3)^2\bigr]}$. Conditioning on low training loss, the probability of generalization is therefore lower bounded by

$$1 - \frac{e^{-d\bigl[(\mu\_1-\mu\_2)^2 + (\mu\_1-\mu\_3)^2\bigr]}} {e^{-d(\mu\_1-\mu\_2)^2}} = 1 - e^{-d(\mu\_1-\mu\_3)^2} \xrightarrow[d \to \infty]{}\ 1.$$

Thus, as the depth $d$ increases, the conditional probability of generalization given low training loss tends to 1.

—-

References

[1] Hanin and Paouris. “Non-asymptotic Results for Singular Values of Gaussian Matrix Products.”

Thank you for your thoughtful review, and for highlighting that our paper tackles a very interesting question and is very well-written. We respond to your comments and questions below. If you find our response satisfactory, we would be grateful if you would consider raising your score.

You are absolutely correct in that generalization is defined with respect to a ground truth distribution. Indeed, without any assumption about the ground truth, no guarantee can be derived for any learning algorithm. In the context of matrix factorization (and, more generally, matrix recovery problems), the canonical assumption is that the ground truth matrix has low rank (see, e.g., [1, 2, 3, 4, 5, 6]). This assumption is so common that it is often not mentioned explicitly (e.g., “matrix sensing” is used instead of “low rank matrix sensing”). The main motivation behind it is that matrices corresponding to real-world data distributions are often close to being low rank ([7, 8, 9]). Moreover, when extended from matrices to tensors, the low rank assumption captures real-world data distributions of high dimensions as well ([10]).

We will clarify the above in the camera-ready version of the paper. In particular, we will clarify that our claim of being the first to establish “cases” where the generalization of G&C is inferior to that of GD, refers to cases with a common assumption on the ground truth distribution. Thank you very much for raising this matter!

---

References

[1] Candes et al. “Exact Matrix Completion via Convex Optimization.”

[2] Sun et al. “Guaranteed Matrix Completion via Non-convex Factorization.”

[3] Tu et al. “Low-rank Solutions of Linear Matrix Equations via Procrustes Flow.”

[4] Bhojanapalli et al. “Global Optimality of Local Search for Low Rank Matrix Recovery.”

[5] Gunasker et al. “Implicit Regularization in Matrix Factorization.”

[6] Razin et al. “Implicit Regularization in Tensor Factorization.”

[7] Bell and Koren. “Lessons from the Netflix Prize Challenge.”

[8] Ma. “Three-Dimensional Irregular Seismic Data Reconstruction via Low-Rank Matrix Completion.”

[9] Kapur et al. “Gene Expression Prediction Using Low-Rank Matrix Completion.”

[10] Razin et al. “Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networks.“

Thank you for highlighting the importance of the problem we study, the rigor of our theoretical arguments, and the clarity of our writing. We respond to your reservations and questions below. In light of our responses, we would greatly appreciate it if you would consider increasing your score.

My primary concern lies in the theoretical contributions. The core results, particularly Theorems 1 and 2, appear to be largely derived from well-established prior work on the limiting behavior of neural networks as width or depth tends to infinity…

In general, we believe that theoretical results should be evaluated primarily by their rigor, importance and novelty, rather than by the technical complexity of their derivation. We are glad that you appreciated the rigor and importance of our study. With regards to novelty, we emphasize that, as stated in the paper, our theory is not only the first to analyze the volume hypothesis in the context of matrix factorization (an important testbed in the theory of neural networks), but also the first to formally prove existence of cases where the generalization attainable by G&C is provably inferior to that of GD.

Notwithstanding the above, from a technical perspective, our theory indeed builds upon existing machinery, e.g., connections between neural networks and Gaussian Processes, and characterizations of singular values in Gaussian matrix products. We stress however that our results are not an immediate outcome of existing machinery, and some of our proofs involve highly non-trivial arguments. For example, Theorem 2 requires applications of concentration bounds on the Lyapunov exponents of a product of Gaussian square matrices, and the extension of Theorem 1 to the case where $\epsilon_{\text{train}}$ is unspecified (Appendix C) requires a stronger form of random variable convergence, as well as the use of Gaussian Correlation inequalities.

Another major concern is the limited scope of the theoretical results. All analysis in the paper is conducted under the matrix sensing setting, where the number of observed samples $n<m \times m’$...

As noted by reviewers tfAT and yR2T, matrix factorization (matrix sensing with neural network overparameterization) is a well established testbed in the theory of neural networks. Seminal papers in the field focused solely on matrix factorization, e.g., [1, 2, 3, 4, 5]. We believe our work should be held to a similar standard, meaning it should not be disqualified for being limited to matrix factorization (especially given how transparent the text is about this).

With regards to the validity of our conclusions with real-world non-linear neural networks, note that Peleg and Hein ([6]) empirically evaluated such models and produced findings consistent with our theory, namely, findings by which the generalization of G&C is inferior to that of GD with wide networks, but comparable to it with deep networks.

The authors cite Proposition 1 to argue that gradient descent (GD) generalizes well in the infinite-width limit. However, I believe this claim requires more careful justification and proof. Specifically, the cited result from [92] shows that for any fixed width $k$, gradient descent can recover the target matrix with high probability as the initialization scale tends to zero. This setting corresponds to the nonlinear training dynamics regime, and crucially, it does not require $k\rightarrow\infty$...

We fear there may be a misunderstanding. We do not cite Proposition 1 to argue that GD generalizes well in the infinite width limit. Rather, we combine Proposition 1 with the result in Theorem 1 applicable to finite widths, for proving (for the first time, to our knowledge) that there exist (finite width) cases where the generalization attainable by G&C is provably inferior to that of GD.

Although the authors cite a fairly comprehensive literature, there are some important and related works that are not mentioned. For example…

Thank you for noting that we “cite a fairly comprehensive literature,” and for pointing out the additional references. We will cite them all in the camera-ready version of the paper.

On the one hand, the authors aim to generalize matrix factorization results to multi-layer neural networks with nonlinear activation functions, which goes beyond the classical matrix factorization setting. However, why the analysis must be restricted specifically to matrix sensing settings?...

Our analysis indeed accounts for non-linear activations, going beyond the classical form of matrix factorization. It is however limited to the matrix sensing problem. As we note in the text, we hope that our theory will serve as a stepping stone towards analysis of more realistic settings. One promising avenue in this direction would be the analysis of tensor factorization (tensor sensing with neural network overparameterization), which is a model much closer to real-world neural networks (see, e.g., [7, 8]). Tensor factorization has various similarities to matrix factorization, thus we believe elements of our theory may carry over to this richer model. We will mention this in the conclusion section of the camera-ready version.

According to the restatement of Proposition 1, is it implied that the generalization loss tends to zero as the width $k\rightarrow\infty$? If so, I believe this conclusion requires a more careful justification or even a formal proof. It is not immediately clear how this follows from Theorem 3.3.

Again, we fear there may be a misunderstanding. Proposition 1 includes no new content beyond Theorem 3.3 from [9]. Note that in this latter theorem, the upper bound on the generalization loss is given in terms of $\alpha$, which itself satisfies an upper bound that tends to zero as $k$ grows. For comparing Proposition 1 with Theorem 3.3, you are welcome to consult Appendix E in our paper, which includes a version of Proposition 1 without O-notations.

In Figure 1, what is the precise relationship between the plotted curves and the training error threshold $\epsilon_{\text{train}}$? How would the results change if a different value of $\epsilon_{\text{train}}$ were used? A sensitivity analysis would help clarify this.

As stated in Appendix G, the plots in Figure 1 were generated with $\epsilon_{\text{train}}=0.02$. Following your question we conducted additional experiments with $\epsilon_{\text{train}}=0.03$ and lower values. All of the results we obtained were qualitatively similar to those reported in Figure 1. We will add this information to the camera-ready version of the paper. Thank you for the question.

Why is the prior baseline curve omitted in Figure 2? It was included in Figure 1, so it would be helpful to explain the rationale for excluding it here.

We believe it makes less sense to plot generalization of priors in Figure 2, as the purpose of the figure is to demonstrate that the generalization of G&C improves with depth, in contrast to Figure 1 whose purpose was to demonstrate that the generalization of G&C approaches chance (generalization of the prior) with width. Nonetheless, we will specify generalization of priors in Figure 2 (as expected, these are well above the generalization of G&C and GD).

The experimental section lacks sufficient persuasive power. According to the authors’ theoretical claims:

• As width increases, the difference between the generalization error of the G&C algorithm and that of random guessing should follow a straight line with slope -1/2 in a log-log plot.
• As depth increases, the generalization error of the G&C algorithm should follow a straight line with slope -1 in a log-log plot.

A more quantitative and explicit visualization of these trends in Figures 1 and 2—e.g., by plotting the log-log slope or fitting lines—would significantly enhance the clarity and credibility of the empirical findings.

We believe there is a misunderstanding: our theory provides upper bounds (which we do not claim are tight), and these upper bounds pertain to probabilities (rather than generalization errors).

Line 26: Reference [102] appears to be cited twice; please check for redundancy.

We will fix this. Thank you.

The notation for sets is somewhat confusing. In Line 142, partentheses are used to denote a set, while in Line 148, the same notation appears to indicate concatenation. It would be clearer and more conventional to use curly braces for sets to avoid ambiguity.

We use parentheses to denote tuples, and this is appropriate for both lines 142 and 148.

---

References

[1] Candes et al. “Exact Matrix Completion via Convex Optimization.”

[2] Sun et al. “Guaranteed Matrix Completion via Non-convex Factorization.”

[3] Tu et al. “Low-rank Solutions of Linear Matrix Equations via Procrustes Flow.”

[4] Bhojanapalli et al. “Global Optimality of Local Search for Low Rank Matrix Recovery.”

[5] Gunasker et al. “Implicit Regularization in Matrix Factorization.”

[6] Peleg and Hein. “Bias of Stochastic Gradient Descent or the Architecture: Disentangling the Effects of Overparameterization of Neural Networks.”

[7] Razin et al. “Implicit Regularization in Tensor Factorization.”

[8] Razin et al. “Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networks.“

[9] Soltanolkotabi et al. “Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing.”

Thank you! We are glad to have clarified some of the previous misunderstandings. It seems that there remain additional ones. We address these below. If there is anything else that we can clarify please let us know. Otherwise, we would greatly appreciate it if you would consider raising your score.

most of these studies investigate the more significant problem of implicit regularization..

We stress that our work investigates this exact problem. Namely, we study the question of whether the implicit regularization (i.e., the generalization in overparameterized settings) necessitates gradient descent, or, alternatively, takes place with any reasonable (non-adversarial) optimizer that fits the training data.

the results in this paper are heavily dependent on the matrix sensing sampling constraint $n < m \times m’$...

All of the seminal papers which we have mentioned (and which you have acknowledged) [1, 2, 3, 4, 5] make the exact same assumption (i.e., they assume $n < m \times m’$, meaning that the number of measurements is smaller than the number of matrix entries). When this assumption is violated the question of generalization becomes vacuous (generalization is guaranteed just by fitting the training data).

numerous theoretical works provide elegant upper bound theorems …, but these contribute little to our genuine understanding of the underlying problems.

We reiterate that our bounds apply to probabilities, not generalization losses.

Moreover, papers as you mention include seminal works that significantly advanced the field (e.g., [6, 7, 8, 9, 10, 11, 12]). We believe our work should be held to a similar standard, meaning it should not be disqualified for providing bounds that are not necessarily tight.

---

References

[1] Candes et al. “Exact Matrix Completion via Convex Optimization.”

[2] Sun et al. “Guaranteed Matrix Completion via Non-convex Factorization.”

[3] Tu et al. “Low-rank Solutions of Linear Matrix Equations via Procrustes Flow.”

[4] Bhojanapalli et al. “Global Optimality of Local Search for Low Rank Matrix Recovery.”

[5] Gunasker et al. “Implicit Regularization in Matrix Factorization.”

[6] Bartlett et al. “Spectrally-Normalized Margin Bounds for Neural Networks.”

[7] Neyshabur et al. “A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks.”

[8] Arora et al. “Stronger Generalization Bounds for Deep Nets via a Compression Approach.”

[9] Golowich et al. “Size-Independent Sample Complexity of Neural Networks.”

[10] Li and Liang. “Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data.

[11] Cao and Gu. “Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks.”

[12] Bartlett. “The Sample Complexity of Pattern Classification with Neural Networks: The Size of the Weights is More Important than the Size of the Network.”

Thank you for your thoughtful review, and for highlighting the quality, clarity, significance and originality of the paper. We address your comments and questions below.

In Figure 1c, a double descent behaviour [Belkin et al., 2018] appears to emerge around width ~12. Would the authors say that, in this setting, this behaviour stems from the algorithmic component of the learning process (i.e., the choice of optimiser), rather than from data or model architecture alone?

Thank you for pointing this out! We indeed observe a double descent phenomenon, and only with GD. This suggests that the phenomenon may indeed relate to the optimizer more than the architecture or data. Investigation of this prospect is a very interesting direction for future work, which will be discussed in the camera-ready version of the paper.

Do the authors have any intuition about the contrasting behaviour under increasing width and increasing depth? I wonder whether this contrast could be related—perhaps even indirectly—to the classical universal approximation theorem for networks of arbitrary width [Cybenko, 1989]

Our results can be interpreted as suggesting that in terms of generalization, neural network architectures benefit from depth more than they do from width. In analogy, various works have shown that in terms of approximation (expressiveness), neural network architectures benefit from depth more than they do from width. We will discuss this analogy in the camera-ready version of the paper. Thank you for bringing it up!

The numerical experiments are performed in very low dimensions. For instance, in Figure 1, we have $m=m’=5$ and $n=15$. Could there be finite-size effects influencing the observed trends? This is particularly relevant since Theorem 1 considers the limit $k\rightarrow\infty$.

Due to the run-time of G&C being exponential in the number of training examples, we (like all prior works, see for example [1, 2]) are limited to small scale experiments. While this might influence observed trends, our empirical findings generally align with our theoretical predictions (which are not limited to small scale).

Note that Theorem 1 applies to finite width settings, not only the infinite width case.

The paper seems to support the perspective that architecture, data, and algorithmic choices cannot be studied in isolation when analysing generalisation in overparameterised systems [Zdeborová, 2020, Nature Physics]. Do the authors agree with this interpretation, and if so, could they comment on how their findings might inform this broader view?

Our paper actually points to a more nuanced claim: in some settings (those where the generalization of G&C is inferior to that of GD) generalization crucially depends on the architecture, data and optimizer; whereas in other settings (those where the generalization of G&C is on par with that of GD) generalization stems primarily from the architecture and data, with the optimizer playing a secondary role (it only needs to fit training data in a non-adversarial way). We hope that our study will serve as a stepping stone towards delineating between the two regimes, i.e., towards identifying when the choice of optimizer has significant implications on generalization.

That said, I would highlight more carefully the additional restrictions imposed by Theorem 2 compared to Theorem 1, and their connection to the most standard settings in matrix factorisation

The additional restrictions imposed by Theorem 2 compared to Theorem 1 are explicitly discussed in our limitations section (lines 347 to 349). Following your comment, we will also highlight them in Section 4.

---

References

[1] Chiang et al. “Loss Landscapes are All You Need: Neural Network Generalization Can Be Explained Without the Implicit Bias of Gradient Descent.”

[2] Peleg and Hein. “Bias of Stochastic Gradient Descent or the Architecture: Disentangling the Effects of Overparameterization of Neural Networks.”