Do Neural Networks Need Gradient Descent to Generalize? A Theoretical Study
Authors: Yotam Alexander
Yonatan Slutzky
Yuval Ran-Milo
Nadav Cohen
Venue: NeurIPS 2025 poster ()
Keywords: Neural Networks
Generalization
Implicit Bias
Theory
Matrix Factorization
Primary area: theory

Abstract: Conventional wisdom attributes the mysterious generalization abilities of overparameterized neural networks to gradient descent (and its variants). The recent volume hypothesis challenges this view: it posits that these generalization abilities persist even when gradient descent is replaced by Guess & Check (G&C), i.e., by randomly drawing weight settings until one that fits the training data is found. The validity of the volume hypothesis for wide and deep neural networks remains an open question. In this paper, we theoretically investigate this question for matrix factorization (with linear and non-linear activation): a canonical testbed in neural network theory. We first prove that generalization under G&C deteriorates with increasing width, establishing what is, to our knowledge, the first canonical case where G&C is provably inferior to gradient descent. Conversely, we prove that generalization under G&C improves with increasing depth, revealing a stark contrast between wide and deep networks, which we further validate empirically. These findings suggest that even in simple settings, there may not be a simple answer to the question of whether neural networks need gradient descent to generalize well.

Do Neural Networks Need Gradient Descent to Generalize? A Theoretical Study
Yotam Alexander
Yonatan Slutzky
Tel Aviv University yotam. al www.aanderggaallccomm
Tel Aviv University slutzky1 @mail. tau ac.
Yuval Ran-Milo
Nadav Cohen
Tel Aviv University yuv wim mwl.mmmmmamal..mmmmmmmmmmm.. com
Tel Aviv University cohennadav@tauex tau. ac.
Abstract
Conventional wisdom attributes the mysterious generalization abilities of over- parameterized neural networks to gradient descent (and its variants). The recent volume hypothesis challenges this view: it posits that these generalization abilities persist even when gradient descent is replaced by Guess & Check (G&C), i.e, by randomly drawing weight settings until one that fits the training data is found. The validity of the volume hypothesis for wide and deep neural networks remains an open question. In this paper, we theoretically investigate this question for matrix factorization (with linear and non-linear activation): a canonical testbed neural network theory. We first prove that generalization under G&C deteriorates with increasing width, establishing what is, to our knowledge, the first canonical case where G&C is provably inferior to gradient descent. Conversely, we prove that gen- eralization under G&C improves with increasing depth, revealing a stark contrast between wide and deep networks, which further validate empirically. These findings suggest that even in simple settings, there may not be simple answer to the question of whether neural networks need gradient descent generalize well.
1 Introduction
Overpuramelerized neural networks trained by (variants of) gradient descent are a cornerstone of modern artificial intelligence (AI) [I17] 5T 17 64 3] Typically, an overparameterized neural network can fit its training data with any of multiple weight settings. some of which generalize well (i.e., perform well on unseen test data), while others do not. The fact that weight settings found by gradient descent often generalize well is mystery attracting vast attention Conventional wisdom states that this phenomenon stems from special implicit bias induced by
134
57
90
87
85
gradient descent when applied to overparameterized neural networks 107
63 70
Recently, it has been argued that gradient descent is not necessary for overparameterizze neural networks to generalize well, and in fact, any reasonable (non-adversarial) optimizer that fits the training data suffice 22 I8 116 13. Notable empirical support for this argument was provided by Chiang et al. [22). who demonstrated that generalization comparable to that of gradient descent can be attained by Guess and Check (G&C), i.e., by repeatedly drawing weight settings from specified prior distribution, until weight setting that happens to fit the training data is drawn. For particular prior distribution over weight settings, hypothesizing that G&C attains good generalization is equivalent to the so-called volume hypothesis [22] 89], which states the following. Define the volume of collection of weight settings be the probability assigned to it by a posterior distribution obtained from conditioning the prior distribution on the training data being fit. Then, the volume of weight settings that generalize well much greater than volume of weight settings that not.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Aside from Chiang et al. [22], several works have supported the volume hypothesis in certain cases involving wide and deep overparameterized neural networks [8 47
However, the literature also includes contrasting evidence. In particular, Peleg and Hein g systematically experimented with overparameterized neural networks of varying width and depth, and found that the generalization attainable by G&C is inferior to that of gradient descent, most prominently with larger network widths. Overall, the current literature on overparameterized neural networks presents a conflicting view of how the generalization attainable by G&C compares to that of gradient descent, and how this relationship depends on network width and depth.
In this paper, we present a theoretical study that takes step toward clarifying the foregoing view, i.e., toward delineating the extent to which wide or deep overparameterized neural networks need gradient descent in order to generalize well. Our theoretical study centers on matrix factorization a canonical
testhed in the theory of neural networks, used for studying generalization 43
6
73
25
127 77 as
well as other phenomena [40] [4 108 (3)] Past analyses of matrix factorization have contributed to real-world neural networks- -ieldine theoretical insights 4 [. concrete mathematical tools [96] 97],
and practical methods that improve empirical performance [6] [09]. In its basic form, matrix factorization is akin to using overparameterized neural networks with linear (no) activation for tackling the low rank matrix sensing problem. We consider more general form that allows for
alternative (non-linear) activations as well [93].
Our first contribution is theorem proving that, with an anti-symmeeric activation (e.g., linear, tanh or sine), if the width of network increases, then the generalization attained by G&C deteriorates, the point of being no better than chance-oy more precisely, no better than the generalization attained by drawing single weight setting from the prior distribution while disregarding the training data. The theorem applies to any prior distribution satisfying mild conditions, and in particular to the canonical Gaussian and uniform prior distributions considered in previous works [8 47.. In light of known
results proving that gradient descent attains good generalization 23 75 76 63 107 we conclude that there are canonical cases where the generalization attainable by G&C (with a conventional prior distribution) is provably inferior to that of gradient descent- that is, canonical cases where overparameterized neural networks provably need gradient descent in order to generalize well. To our knowledge, this is the first establishment of the existence of such cases
As a second contribution, we provide theorem proving- for linear activation and a normalized Gaus- sian prior distribution that if the depth of a network increases, then the generalization attained by G&C improves, to the point of being perfect. This theorem, which essentially implies that increasing network depth renders gradient descent not necessary for good generalization, stands in stark contrast to our analysis of increasing network width. We empirically showcase this contrast, demonstrating that in matrix factorization, the generalization attained by G&C improves with network depth but deteriorates with network width, whereas gradient descent attains good generalization throughout.
The findings in this paper suggest that even in simple settings, there may not be a simple answer to the question of whether neural networks need gradient descent to generalize well: the answer may hinge on subtle dependencies between network width and depth. We hope that our study of matrix factorization will serve as stepping stone toward deriving complete answer for real-world settings, thereby illuminating the role of gradient descent in modern AI.
1.1 Paper Organization
The remainder of the paper is organized as follows. Section reviews related work. Section 3 introduces notation and the setting we study. Section delivers our theoretical analysis, followed by Section 5 which presents an empirical demonstration. Section discusses the limitations of our theory. Finally, S concludes.
'It is relatively straightforward to contrive some cases where the generalization attainable by G&C (with conventional prior distribution) is provably inferior to that of gradient descent: indeed, one can retroactively detine the ground truth distribution to be such that gradient descent attains perfect generalization. The novelty of our conclusion is that the foregoing provable inferiority arises in cases that are canonical, ie., that are fundamental and extensively studied.
2

---

2 Related Work
Numerous works have been devoted to understanding why overparameterized neural networks trained by gradient descent (or variants thereof) often generalize well [34
57
12
59
335
86
21
[05] 101 42 While this generalization is most commonly attributed to an implicit bias induced
by gradient descent [104
66 88
75 58 126 23
133
7 82 76 30 128
80 2
121 70, 95] 138, 94], an emerging view is that much of it stems from the architectures of neural
networks. Results supporting this emerging view include: (i) results that establish a certain notion of
54 83 [2]; (i)) results simplicity when a weight setting is drawn from a prior distribution [13 116
that establish good generalization in Bayesian framework, i.e., when predictions are defined through an expectation over weight settings, where the probability of weight settings is higher the better they fit the training data [123] [56; and (iii) results that establish good generalization with G&C, L... when weight setting is drawn from posterior distribution obtained from conditioning prior distribution on the training data being fit 47 18 48 112.. Among these, the third category-i.e, results concerning G&C-is arguably the most aligned with the standard learning paradigm, as it involves selecting a single weight setting that fits the training data.
Chiang et al. 22 and Peleg and Hein 89 compared the generalization attainable by G&C (with a conventional prior distribution) to that of gradient descent, by experimenting with overparameterized neural networks of varying width and depth. Chiang et al. [22 provided evidence suggesting that: (i) the generalization attainable by G&C is on par with that of gradient descent; and (ii) increasing the width of overparameterized neural network improves the generalization of G&C. Peleg and
Hein [89] pointed to confounding factors in the experimental protocol Chiang et al. [22], and made different observations, namely: (i) the generalization attainable by G&C is inferior to that of gradient descent; (ii) increasing the width of an overparameterized neural network improves the generalization of gradient descent but not that of G&C; and (iii) increasing the depth of an overparameterried neural network deteriorates the generalization of both gradient descent and G&C. The latter observation does not align with the conventional wisdom, i.e., with the extensive empirical and theoretical evidence that deep neural networks generalize better than shallow ones [6] 110 79 50 Peleg and Hein [89 accordingly hedge this observation, effectively implying that it may result from confounding factors.
Our work is similar to those of Chiang al. [2 and Peleg and Hein 89 in that it compares the generalization attainable by G&C (with a conventional prior distribution) to that of gradient descent for overparameterizee neural networks of varying width and depth. It markedly differs from these past works in that it provides rigorous theoretical analysis (the works of Chiang et al. 22 and Peleg and Hein [89] are purely empirical), and focuses on a canonical testbed model (matrix factorization). This allows for controlled study free from confounding factors. Moreover, it allows to conclude-foe the first time, to our knowledge- that there exist canonical cases where the generalization attainable by G&C (with conventional prior distribution) is provably inferior to that of gradient descent!!
3 Preliminaries
3.1 Notation
We use non-boldface lowercase letters for denoting scalars (e.g., E R, d E N), boldface lowercase letters for demoting vectors (e.g., v E Rd), and non-boldface uppercase letters for denoting matrices (e.g., A Rddd). For d E N, we define [d] := {1.... , d}. We let || |la and || stand for the Euclidean norm of a vector and the Frobenius norm of a matrix, respectively.
3.2 Low Rank Matrix Sensing
Low rank matrix sensing is fundamental and extensively studied problem in science and engineering
[8 [13 192 19, [06 127 9.. In its basic form, the goal in low rank matrix sensing is to reconstruct a low rank matrix based on linear measurements. Namely, for m, m², r,n E N, where < min(m, m') and n < m m', the goal is to reconstruct a ground truth matrix W* E TRm.m of rank r based on
(A, E mmmm MA RR) > where:
y: (*) TrA, E [n].
(1)
We refer to (A,) as measurement matrices, and to (,+)² as the corresponding measurements.
3

---

The above can be cast as a supervised learning problem. Indeed, we may identify a matrix W E Rmm with the linear functional that maps Rmm.m to (A, W) E R. Our goal is then to learn the linear functional W* based on the training data (A;, M i.e. based on the training instances (A:) and their corresponding labels (yt);= The training data induces a training loss defined over linear functionals (or equivalently, over matrices):
Luain Rmmm + R20 Lirain (W) = ((A,, W) - wi)²
71
Any W E Rm that minimizes the training loss, i.e., that fits the training data, necessarily coincides with W on instances in span (A, (meaning (A, W) coincides with (A, W*) for all E
span [A, ). Accordingly, we quantify generalization (performance unseen test data) through instances orthogonal to span { or more precisely, via the following generalization loss:
fi=
Lgen R 7 R20 Lgen (W) = B Σ AEB ((A,W) - (A,W")
(3)
where B C m. is some orthonormal basis for the orthogonal complement of span (A:) (it is straightforward to show that (.) is independent of the particular choice of B).
Much of the literature on low rank matrix sensing concerns canonical special case where the measurement matrices (A.)ī= satisfy a restricted isometry property (RIP) as defined below [38]. Such property holds with high probability when (A:) are drawn from common distributions, for example Gaussian or Bernoulli [10]
Definition 1. We say that the measurement matrices (A,), satisfy a restricted isometry property (RIP) of order p E N with constant 5 E (0, 1), if for every matrix W E Rm.m whose rank is at most p. holds that:
(1 - 8) [ < |(A(W) s (1 ( where A(W) == ((A,, .....,, (Ap, TY)T E R
3.3 Matrix Factorization
Matrix factorization is canonical testhed in the theory of neural networks, used for studying gen- cralization [43 6 73
25 127 [77] as well as other phenomena [40] [4 [08 39]. Past analyses
of matrix factorization have contributed real-world neural networks-yielding theoretical in-
sights 4 5), concrete mathematical tools [96] 97). and practical methods that improve empirical
performance [6] 109].
In its basic form, matrix factorization is akin to using overparameterized neural networks with linear (no) activation for tackling the low rank matrix sensing problem described in Section 3.2] We consider a more general form that allows for alternative (non-linear) activations as well [93] Concretely, in our context, matrix factorization with activation R - RR width k E N and depth d N refers to learning matrix W E mmm aimed at approximating the ground truth rank r- matrix W", through the following parameterization:
W =
where W, E IRmm' W, E TR for all j (2...., d to matrix signifies an application of (-) to each of the matrix's 's entries. We refer to Wi...., Wa as the weight matrices of the factorization, and to value assumed by (W,..., Wa) as a weight setting. Our interest lies in the overparameterized regime, where the width & does not restrict the rank the learned matrix W. Accordingly, assume throughout that & 2 min(m, m').
1), Wa E Rm.,, and the application of (+))
The low rank matrix sensing losses Luain()) and Lgen()) in Equations (2) and (3) respectively, induce training and generalization losses for the matrix factorization. With slight overloading of notation, these are:
Laran Carin(WWr.r (W,,.... Wa) 1
n 1=1 (AA, (W..
1 Σn_
vn)
(5)
and:
Egen (WI...., Wa) = B Σ AEB
(A.. -
(A, (A, w
(6)

---

3.4 Gradient Descent
Similar to real-world neural networks, matrix factorization admits a non-convex training loss, for which baseline optimizer is grudient descent emanating from small random initialization [26 114. Various cuudics-theoreee matrix factorization with this baseline optimizer. In context, this amounts to implementing the following iterations:
[26] [4| 43 39 [37] and empirical [6 I6 were devoted to training
a w + with - " "aw, Crain (w ..........")) je [d] te te
w
(7)
where L-nin()) (-) is the training loss defined in Equation (5) 17 E Ry0 is a predetermined step size (learn- ing rate), and (W1), ,...,, W holds a randomly chosen initial weight setting of small magnitude.
3.5 Guess & Check
conceptual alternative to gradient descent is Guess and Check (G&C) 122 In the context of the matrix factorization described in Section 3.3 let P--) be probability distribution over weight settings, Le., over values that may be assumed by the tuple of weight matrices (W..... Wa). Regard P(.) prior distribution, and let Cuain 0 be some threshold on the training loss Lumin()) (Equation (5). Applying G&C to the matrix factorization then consists of repeatedly drawing (Wi, ...,.,, Wa from P(-), until the condition Lirin ...., Wa) < émain is met. From statistical perspective, this is equivalen to single draw of (W1,... Wa) from P(- (P-iin (W,, Wi,.... Wa) < <main), where the latter is the posterior distribution obtained from conditioning P(-)) on the event fusin (W1,
Wa) <
rrain
4 Theoretical Analysis
Consider a matrix factorization (Section 3.3) optimized by gradient descent (Section 3.4) or G&C
has been devoted to establishing that gradient descent attains good generalization under various choices of width and depth for the factorization. In this section we tackle the question of whether gradient descent is needed for good generalization. Specifically, we theoretically analyze the generalization attainable by G&C as the width and depth of the factorization vary.
(Section 3.5). A large body of theoretical work 44 72, 6 (77 B4 [27 [36, [73 106 60 I31
4.1 Distributions Over Weight Settings
Both G&C and gradient descent are defined with respect to a probability distribution over weight settings: for G&C it is the prior distribution (see Section [35), and for gradient descent it is the distribution from which initialization is drawn (see Section 3.4). We consider broad class of distributions over weight settings specified by Definitions 2 and below.
Definition 2 defines a regular distribution over R as one that has zero mean, is symmetric, and assigns positive probability to every neighborhood of the origin. This definition regularity covers canonical distributions over IR, for example pero-centered Gaussian distributions and uniform distributions over symmetric intervals. Definition 3 builds on Definition 2 to specify the class of distributions over weight settings we consider. Namely, given regular distribution (over R) ((-). Definition Iefinittonnder defines a distribution over weight settings generated by Q(-) to one in which entries are independently drawn from ((-), and then subject to Kaiming scaling [52], i.., to scaling that preserves magnitudes when the width of the factorization increases. This definition of a generated distribution covers Kaiming Gaussian and Kaiming Uniform distributions: common choices for the initialization of gradient descent (53) |30 [ and the prior of G&C [18 47 48). Definition also defines a distribution over weight settings generated by Q(-) with normalization, as one that generated by Q(-). with an additional normalization (scaling) that ensures the product of weight matrices has unit norm. The role of this normalization is to preserve magnitudes when the depth of the factorization increases, analogously to the role of normalization techniques applied when training real- world neural networks with large depth
115
129 103 8 (55).
See 37 100 for folklore arguments justifying the equivalence.
5

---

Definition 2. Let ()-) be a probability distribution over R. We say that 2(-) is regular if the following
conditions hold: (i) (+-) has zero mean and all of its moments exist, i.e. 16- |la] 0 and
Ea--Q() [t)="()]|aa]]] < oe for all p E N: (ii) ((-) is symmetric, meaning a 2(-) implies aa ~ 2()): and
(iii) 2(-) assigns positive probability every neighborhood of the origin (i.e., for any neighborhood I 0 E IR, if a ~ 2(-) then the probability of the event a E I is positive).
Definition 3. Let Q(.) be a regular probability distribution over I (Definition 2 and let P(.) be
probability distribution over weight settings, f.e., over values that may be assumed by the tuple
of weight matrices (W1,..., Wa). For every j E [d]. denote by my the number of columns in the
weight matrix Wj. and by (,).) the probability distribution over Ik obtained from scaling 2(-) by
1/ymy (meaning a ~ 23(+) implies Vm,a ~ 2())). We say that P(-) is generated by 2() if
(W Wa) ~ P(-) implies that W w,...., a are statistically independent, and for every j E [d]
the entries of W2 are independently distributed per ()(-). We say that P(-) is generated by 2-)
with normalization if (W,,. (W...., ,,a) ~ P()) can be implemented by drawing (Wi..., Wa) from
distribution generated by 2(-), and then, for all j [d], dividing each entry of W by IWa.... Wi
4.2 Increasing Width: Need for Gradient Descent
In this subsection, we consider a regime where the width of the matrix factorization increases, and prove that gradient descent is needed for good generalization. In particular, we present an analysis leading to the conclusion that there exist canonical cases where the generalization attainable by G&C (with a prior distribution generated by a regular distribution) is provably inferior to that of gradient descent. To our knowledge, this is the first establishment of the existence of such cases
Definition 4 below defines an admissible activation as one that is non-constant, piece-wise continu- ously differentiable, has polynomially bounded derivative, and does not vanish on both sides of the origin. This definition of admissibility covers most activations used in practice (e.g., tanh, sigmoid, ReLU and Leaky ReLU [102 68 84 (78).
Definition 4. We say that the activation R-- - IK is admissible if the following conditions hold: (i) (() is non-constant; (ii) (-) is (continuous and) piece-wise continuously differentiable; (iii) the derivative of (.) is polynomially bounded, i.e., there exist p E N and e E R> such that (a'(a)) s c(1 + |a (²) for every a E R at which o-()) is defined; and (iv) (-) does not vanish on both sides of the origin, i.e., any neighborhood of 0 E R includes some R for which o (a) # 0.
Theorem I below proves for cases where the activation is admissible and anti unti-symmetric (e.g., it is linear, tanh or sine)-that as the width of the factorization increases, the generalization attained by G&C deteriorates, to the point of being no better than chance, i.e., no better than the generalization attained by drawing a single weight setting from the prior distribution while disregarding the training data. In the limit of width tending to infinity, the theorem applies to any prior distribution generated by some regular distribution over R (Definitions 2 and (3) the canonical case where the regular distribution over RR is zero-centered Gaussian, the theorem also accounts for finite widths.
Theorem 1. Suppose the activation ((-) is admissible (Definition D. and that it is anti- symmetric, meaning of a)) = (a(x) for all a E R. Let Q(.) be a regular probubility distribution over IR (Definition 2). and let P(-) be the probability distribution over weight settings that is generated by 2(-)
(Definition) Lel Eirain: Egen E IR R Regard (.)) as a prior distribution, and consider the posterior distribution P(. / ( (W..... Wa) < (uain), i.e., the distribution obtained from conditioning P(.) on the event that the training loss Lurin()) (-) is smaller than Euain- Then, as the width k of the matrix factorization tends to infinity the posterior probability of the event that the generalization loss Egen(t) is smaller than Egen converges to its prior probability, i.e.:
P (Lagen (W1, Wa) < 'gen Larain (W1, W...... Wa) (1ran) -P (W1 ....... Wa) < (gen)
0.
k
Moreover, in the case where Q(-) is a zero-centered Gaussian distribution, i.e., 2(-) = NN(=;,,v) for some ve E Ro, holds that for any k.
P (Cgge (W1, W...... Wa) < <Ggen Curin (W,.... Wa) < Craam) (C (W1, Wa) < <geen) = +z)
"The O O-notation below hides constants that depend on a--), Grain. eyen and v. as well as the ground truth matrix W*, the measurement matrices (A.))=1. the depth d and the dimensions mn and m² of the matrix factorization. See Appendix A.3 A.3
for details.

---

Proof sketch (full proof in Appendix A).. The proof begins by establishing an equivalence between a matrix factorization and a feedforward fully connected neural network: each column of a factorized matrix W (Equation 4 can be seen as the output of a feedforward fully connected neural network when its input is a standard basis vector. This equivalence facilitates utilization of the following results from Hanin [5] and Favaro et al. [6]
(i) as the width & of a feedforward fully connected neural network tends to infinity, drawing its weight settings from any distribution P()) generated by some regular probability distribution 2(-) (Definitions 2 and 3). leads the output of each of the network's s layers to converge in distribution to Gaussian process, whose covariance structure can be computed recursively using the covariance structures of previous layers; and
(ii) the case where ((+) is zero-centered Gaussian distribution, the convex distance (a standard distance metric for multivariate distributions) between the output of a network's 's layer and the Gaussian process to which it converges, O(1/Vk).
For treating the case where 2(-) an arbitrary regular probability distribution and the width is tends to infinity, the proof utilizes result (i) above. Namely, it utilizes the recursive computation of covariance structures to show that the columns of the factorized matrix W' (i.e., the vectors obtained by applying the feedforward fully connected neural network to standard basis vectors) converge in distribution to Gaussian vectors with statistically independent entries, and furthermore, since the activation (-) is anti-sy aatiisymmetric, these Gaussian vectors are statistically independent of one another. Overall, it holds that W converges in distribution to a random matrix Wia whose entries are independently drawn from a zero-centered Gaussian distribution. Since the measurement matrices (A.) are orthogonal to the basis B that defines the generalization loss (see Equations 2 and 3 ). the events Caain (Wia) Erain and Ggan (Win) < Egen are statistically independent. Therefore, as the width & of the matrix factorization tends to infinity, conditioning on the event that the training loss is lower than Emain does not change the probability of the event that the generalization loss is lower than Egen-
The proof concludes by treating the case where 2(-) is zero-centered Gaussian distribution and the width l is finite. There, result (ii) above is utilized to show that the probabilities of the events Lurana (W) < Curain and Cgen
Egen converge to those of the events Luain (Waa) Cuain and
Laenn (Wia) < égen, respectively, at sufficiently fast rate.
Theorem 3.3 from Soltanolkotabi et al. 106 restated as Proposition I below-is a representative result from the large body of work establishing that, in matrix factorization, gradient descent attains good generalization 43 72 6 77 B4 127 136 73 60 [31]. The result proves for cases where the activation is linear, the depth is two, and the measurement matrices satisfy an RIP (Definition) [ that gradient descent (with small step size and small Kaiming Gaussian initialization) attains good generalization, with probability (over the initialization) tending to one as the width of the factorization increases. In light of this result, Theorem [ leads to the conclusion that there exist canonical cases where the generalization attainable by G&C (with a prior distribution generated by a regular distribution) is provably inferior to that of gradient descent. To our knowledge, this is the first establishment of the existence of such cases
Propesition 1 (restatement of Theorem 3.3 from 106)). There exists universal constant C1 E Ry0 with which the following holds. Suppose the activation (.)) is linear (i.e., o(a) = a for all a E R), and the depth d equals two. Let Q.(-) be a cero-centered Gaussian probability distribution, i.e., = N.:; v), with variance v E (0, (1k-2//2) Let PP-)) be the probability distribution over weight settings that is generated by 2(-) (Definition 3y Assume the measurement matrices (Aa) satisfy an RIP (Definition)) 7) of order 2r + 1 (recall that r is the rank of the ground truth matrix W*) with a constant 5 E (0, ((1).. Consider minimization of the training loss Larin (.) via gradient descent (Equation 7 with initialization drawn from P(-) and step size 1 E (0, ((1). Then, there exists some T E N,
O(n-"),, such that for any width k of the matrix factorization, after
T iterations of gradient descent, with probability at least 1 O(e -aak over its initialization, the generalization loss Lgen (-) is O 3/10 1-
'Throughout the statement of Proposition 1 the O- and Ó-notations hide constants that depend on the dimensions m and m' of the matrix factorization, and on the ground truth matrix W*, The Ó-notation also hides factors logarithmic in & and v. See Appendix for details.
7

---

4.3 Increasing Depth: No Need for Gradient Descent
In this subsection, we consider a regime where the depth of the matrix factorization increases, and prove that gradient descent is not necessary for good generalization. In particular, Theorem (2 below establishes cases where, as the depth of the factorization increases, the generalization attained by G&C improves, to the point of being perfect (in the sense that, with probability tending to one, the generalization loss is no greater than a constant times the threshold set for the training loss). This stands in stark contrast to our analysis of increasing width (Section 4.2), which established canonical cases where the generalization attainable by G&C (with a prior distribution generated by a regular distribution) is provably inferior to that of gradient descent. A large body of theoretical work has argued that neural networks benefit from depth more than from width in terms of expressiveness [8] and the implicit bias induced by gradient descent [4] 49 197. Our analyses suggest another potential advantage: depth may render neural network architectures more amenable to generalization than width, in the sense that the volume hypothesis holds to greater extent.
29 [8
The cases to which Theorem appliee are those where the activation linear, the measurement matri- satisfy an RIP (Definition[] D.. the prior distribution is generated with normalization (Definition 3) from a zero-centered Gaussian distribution (over IR), and the ground truth matrix has norm and rank equal to one (an extension to ground truth matrices of higher rank is discussed in Appendix D). The theorem is non-asymptotic, meaning it applies to finite depths, not only to the limit of depth tending to infinity.
Theorem 2. Suppose the ground truth matrix W* satisfies ||W* = and its rank r equals one 5
Suppose the activation (-) is linear (i.e., (a) = a for all a E IR). Assume the measurement
matrices (A,) satisfy an RIP (Definition 77 of order two with some constant ô E (0, 1). Let Q(-)
be a zero-centered Gaussian probability distribution, i.e. Q(.) = -(.)=N((::0) N-; for some v E R.x0- Let
P(.) be the probability distribution over weight settings that is generated by Q(-) with normalization
(Definition 3. Then, there exists с E R (dependent only on 8) such that, for any Grain E R,0 and any depth d of the matrix factorization
1 1- P(Ceaa ((CCge(W1..... (W1...., Wa) < CuainC| Cuain (W1..... ....... Wa) Euain) = 03).
Proof sketch (full proof in Appendix Bj. The proof begins by decomposing the factorized matrix W (Equation (4) into a product of three matrices: W = WaW Wi, where Wa-1:2 := W 1 ... W2. Then, temporarily disregarding the normalization in P(.), ), i.e., temporarily treating P(-) as if were generated by Q(-) without normalization (Definition 3. the proof applies concentration bounds established by Hanin and Paouris [46] the Lyapunov exponents of W (when normalization is disregarded, Wd-1:2 is product of d - 2 zero-centered Gaussian k-by-k matrices). These Lyapunov exponents, denoted λ1 ..... Ag. are defined by A, == log(o;))
2) for E [k), where a 2 ... 2 a stand for the singular values of Wd-122. Hanin and Paouris [46] give non-asympiotic bounds on the deviation of AI,...,,A from their respective infinite depth (d - oc) limits /l,..... Mik. which satisfy 0 > Mi > > M4. Since o; exp( - 2)..). and since μ4 & μyy for all + j. the non-asymptotic bounds imply that when the depth dl large, with high probability, Wa- 1:2 has one singular value much larger than the rest, i.e., Wa-1:2 has approximate rank one structure.
Next, while still (temporarily) disregarding the normalization in P(.), the proof uses properties of standard multivariate Gaussian distributions (namely, their rotational invariance and concentration bounds on their norms) to show that, with high probability, multiplication of Wd-1:2 by Wa from the left and by W1 from the right preserves its approximate rank one structure. In other words, with high probability, the factorized matrix W WWWa-1:22 W1 has an approximate rank one structure. Now (and hereinafter) accounting for the normalization in P(-), the latter finding is formalized as follows: for any 7 E Ry,, the probability that W is within y (in Frobenius norm) of a rank one matrix is - ((1d))
Choosing 7 appropriately, while employing compressed sensing arguments that rely on the RIP and the ground truth matrix having rank one (see, e.g., (65)), it is then proven that the probability of the events Cuaaio (W) < Grain and Egen (W)+ 2 Ctrain occurring simultaneously is ((1dd). Finally, using the facts
'An extension of Theorem to ground truth matrices of higher rank is discussed in Appendix D
'The O-notation below hides constants that depend on the measurement matrices (A.) the ground truth matrix W*, the dimensions m and m' of the matrix factorization, and the width & of the matrix factorization. See Appendix for details.
8

---

Generalizationn Loss
Unear
0.20
Tanh
0.15
Leaky ReLU
0.2
+
GD
0.10
G&C
0.1
0.05
0.0
0.00
100
200
100
400
500
600
0
100
200
500
400
500
6.00
100
200
300
4000
5.00
500
Width
Width
Width
Figure 1: In line with our theory (Section (.2]. as the width of a matrix factorization increases, the generalization attained by G&C deteriorates, to the point of being no better than chance, i.e, no better than the generalization attained by drawing a single weight setting from the prior distribution while disregarding the training data. In contrast, gradient descent attains good generalization across all widths. Each of the above plots corresponds to matrix factorization described in Section 3.3 with a different activation (-)): linear activation (a(a) = a))
for the left plot; tanh activation (ar(a) = tanh (a)) for the middle plot; and Leaky ReLU activation (or(a)
max a, a:). with c 0.2) for the right plot In each plot, the generalization loss (Equation (6)) is shown against the width of the matrix factorization, for three optimizers: gradient descent with small step size and small initialization (Section 3.4) G&C with Kaiming Gaussian prior distribution (Section 3 and simply drawing a single weight setting from the prior distribution while disregarding the training data. For each combination of width and optimizer, we report the median (marker) and interquartile range (error bar) of generalization losses attained over eight trials (differing only in random seed). Across all experiments reported in this figure: the matrix factorization had depth two and dimensions = m' 5; the ground truth matrix had (Frobenius) norm and rank equal one; and the training data size x 15. We note that with Leaky ReLU activation. which lies beyond the scope of our theory, the gencralization attained by gradient descent is not as good as it with linear and tanh activations. For further experiments and implementation details see Appendices G and respectively.
that the distribution of W is rotationally invariant, that (due to the normalization in P(.)) the norm of W equals one with probability one, and that W is with high probability close to rank one matrix, the proof establishes that the probability of Luain < éuain is independent of the depth d, ie., is (1)). By the definition of conditional probability, the latter two findings imply that the probability of (gen(W) 2
Crainn conditioned on Liaain (W) < Cirin is O(1/d). This is the desired result.
5 Empirical Demonstration
In this section, we corroborate our theory (Section 4 by empirically demonstrating that in matrix factorization (Section 3.3). the generalization attained by G&C (Section (3.5p improves as depth increases but deteriorates as width increases, whereas gradient descent (Section 3.4) attains good generalization throughout. Figures @ present such demonstrations, plotting generalization as a function of width and depth, respectively, for both G&C and gradient descent. The demonstrations in Figures T and 2 cover the theoretically analyzed linear and tanh activations, as well as the Leaky ReLU activation (78) which lies beyond the scope of our theory Additional demonstrations covering further cases (including gradient descent with momentum (91) are provided in Appendix Code for reproducing all demonstrations can be found in https://githu:: com/Yono/ wwwll'onnnulaa S0utzky999 nn aa-gg-geo ged-gen-m mf
6 Limitations
It is important to acknowledge several limitations of our theory. First, while large body of theoretical work [43] 72
60 131 has been devoted to establishing that gradient descent attains good generalization in matrix factorization, Theorem 3.3 from [106] (restated as Proposition I (herein)-wwe which applies only when the activation is linear, the depth is two, and the measurement matrices satisfy an RIP (Definition is the only result guarantees low generalization loss with high probability for gradient descent with a positive (non- infinitesimal) step size and conventional (data-independent) initialization. Second, the guarantees we prove for G&C-namely Theorems [ are vacuuusuous only when the width or depth of the matrix factorization is sufficiently large. Third, Theorem assumes that the activation is anti-symmetric. Fourth, Theorem 2 imposes even stronger assumptions: the activation linear, the measurement matrices satisfy an RIP, and the ground truth matrix has norm and rank equal to one (an extension to ground truth matrices of higher rank is discussed in Appendix D but is not formally established). Fifth, Theorem requires the G&C
6
77
34
127
136
73
106
disposal that formally
[and
unspecified constant factors, and in particular,
"ee attempted to include a demonstration with the more popular ReLU activation 84]. but its tendency to zero out matrix entries made G&C computationally infeasible, requiring an excessive number of draws to obtain weight setting that fits the training data.

---

Generalization Loss
Linear
Tanh
Leaky ReLU
0.08
0.08
0.075
0.06
GD
0.06
0.44
GSC
0.04
0.050
0.02
0.02
0.025
0.00
0.00
0.000
10
10
Depth 10
Depth
Depth
Figure 2: In line with theory (Section 4.3 as the depth of a matrix factorization increases, the generalization attained by G&C improves, drawing closer that of gradient descent. This figure adheres to the caption of Figure except for the following differences: (i) the matrix factorization had variable (rather than fixed) depth and fixed (rather than variable) width, with the latter set to five; (ü) generalization losses are shown against the depth (rather than the width) of the factorization; and (iit) the prior distrihution of G&C included normalization (Definition B) We did not include depths greater than ten in our experiments, they led excessively long times for gradient descent (due to vanishing gradients). Note that such greater depths would not necessarily lead the generalization attained by G&C to match that of gradient descent. Indeed, our theory for increasing depth (Theorem 2 guarantees that the generalization loss attained by G&C tends to zero only if the threshold set for its training loss (see Section 3.5) tends to zero, which makes G&C computationally infeasible (as it requires an infcasible number of draws). For further experiments and implementation details see Appendices G Gland respectively.
training loss threshold étrain to be specified (the theorem does not rule out the possibility that for any width, sufficiently small étain will lead G&C to attain good generalization), and although Appendix C proves a result that allows unspecified Erainn it does so under strong assumptions not imposed by Theorem | Finally, Theorems I and 2 consider different types of prior distributions: Theorem excludes normalization (Definition whereas Theorem iicluues it.
While we empirically demonstrate that the conclusions of our theory hold beyond its formal scope, the above limitations remain. We hope that this paper will serve as a stepping stone towards addressing these limitations, and more broadly, towards extending our theory from matrix factorization to real-world neural networks.
7 Conclusion
Conventional wisdom attributes the miraculous generalization abilitics of neural networks to gradient descent. A recent bold argument claims that gradient descent is not necessary for neural networks to generalize well, and in fact, any reasonable optimizer can suffice. This is justified by the so-called volume hypothesis, which posits that among the weight settings that fit the training data, the volume of the weight settings that generalize well is much greater than the volume of the weight settings that do not. While several works have supported the volume hypothesis in certain cases involving wide and deep neural networks, the literature also includes contrasting evidence.
In this paper, we presented theoretical study for matrix factorization (with linear and non-linear activation) canonical and important testbed the theory neural networks-to rigorously exam- ine the validity of the volume hypothesis. Our first contribution is proof that the volume hypothesis fails when the width network is large (compared to its depth), thereby establishing for the first time, to our knowledge-as canonical case where gradient descent is provably necessary for neural network to generalize well. As a second contribution, we proved that the volume hypothesis holds when the depth of network is large (compared to its width). These contributions reveal stark con- trast between wide and deep networks, which we further validated through empirical demonstrations.
Overall, our findings suggest that even in simple settings, whether the volume hypothesis holds may hinge on subtle dependencies between network width and depth. Delineating when holds of interest not only from theoretical perspective, but also in practice. Indeed, when the volume hypothesis is known to hold, one may confidently employ fast-converging optimizers (e.g., Adam (62)
or Adam W 74) without worrying about their potential to deteriorate generalization [124 139
Our study of matrix factorization may serve as a stepping stone toward analogous studies of more realistic models. A natural next step is the study of tensor factorization: a model obtained by lifting matrices -wwoddimensional arrays) tensors coulti-dimensiona. arrays). Tensor factorization has been studied extensively in the theory of neural networks (2 28)
96 98
2 partly due to its ability
to capture convolutional (27], recurrent 132 and self-attention [12
69 architectures. Delineating
when the volume hypothesis holds in tensor factorization-ic. when tensor factorization needs gradient descent to generalize woll-would comprise an important milestone toward elucidating the role of gradient descent in modern AI.
10

---

Acknowledgments and Disclosure of Funding
This work was supported by the European Research Council (ERC) grant NN4C 101164614, a Google Research Scholar Award, Google Research Gift, Meta, the Yandex Initiative in Machine Learning, the Israel Science Foundation (ISF) grant 1780/21, the Tel Aviv University Center for Al and Data Science, the Adelis Research Fund for Artificial Intelligence. Len Blavatnik and the Blavatnik Family Foundation, and Amnon and Anat Shashua.
References
[1] Madhu S Advani, Andrew M Saxe, and Haim Sompolinsky. High-dimensional dynamies of generalization error in neural networks. Neural Nenworks, 132:428-42 4466, 2020.
[2] Yotam Alexander, Nimrod De La Vega, Noam Razin, and Nadav Cohen. What makes data suitable for locally connected neural network? necessary and sufficient condition based on quantum entanglement. arXiv preprint arXiv:2303. 1249, 2023.
[3] Md Zahangir Alom, Tarek M. Taha, Christopher Yakopeic, Stefan Westberg, Paheding Sidike, Mst Shamima Nasrin, Brian Van Esesn, Abdul Awwal, and Vijayan K. Asari. The history began from alexnet: A comprehensive survey on deep learning approaches, 2018. URL https
//axxiv.org.r.. www.://gg/abbbbe....ooo... 1803. 01164
[4] Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization deep networks: Implicit acceleration by overparameterization. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th Interna- tional Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 244 253. PMLR, 10 15 Jul 2018. URL BRRLhttps:// pttttps:/pprcceediie proc/edincee..... mlr press/ grress/80//a v80/ 2000///rr188a..... html
[5] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep ma- trix factorization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates. Inc., 2019, URL
neur Paper..d pdf]
Paper
[6] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factoriza- tion, 2019. URL URL /ttppss:s///axi www.aawwwwi.oooaaaaaaaaaaaeaaeae wwt./ba///aaaeee.eo abtp///...11111...1 13655
[7] Shahar Azulay, Edward Moroshko, Mor Shpigel Nacson, Blake E Woodworth, Nathan Srebro, Amir Globerson, and Daniel Soudry. On the implicit bias of initialization shape: Beyond infinitesimal mirror descent. In International Conference on Machine Learning, pages 468 668-477. PMLR, 2021.
[8] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey F. Hinton. Layer normalization, 2016. URL https: 7/arxiv. www...rggggooo... hargg/bb//iae /tba//160....0 06455
[9] Zhiwei Bai, Jiajie Zhao, and Yaoyu Zhang. Connectivity shapes implicit regularization in matrix factorization models for matrix completion, 2025. httpss//:///a http:///aaaxiv...//bbbaaaees
13721
[10] Richard Baraniuk, Mark Davenport, Ronald Verore and Michael Wakin. A simple proof of the restricted isometry property for random matrices. Constructive Approximation, 28:253-263, 12 2008. doi: 10. 00.1000/00365-000-0000
[11] Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 1 117448))3003330077, 2020.
[12] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-leaminn practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116 (32): 15844, 2019.
[13] Yakir Berchenko. Simplicity bias in overparameterized machine learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 11052 1060, 2024.
[14] Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srebro. Global optimality of local search for low rank matrix recovery, 2016. URL httttts////xxxi/ org/ abo/aa/.......//..// 07221
[15] Dennis D Boos. A converse scheffe's 's thcorem. The Annals of Statistics, pages 423-427, 1985.
[16] Amit Boyarski, Sanketh Vedula, and Alex Bronstein. Spectral geometric matrix completion, 2021. URL https:/ haaps://arxxx /ttpxv/vivv/////////////////aa www.ooogg///........o....o... 0tt///911...7770
11

---

[17] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan. Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Vosss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh. Daniel M. Ziegler, Jeffrey Wu. Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Matcusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, llya Sutskever, and Dario Amodei. Language models are few-shot learners, 2020. URL htt.hhhtss//// bttppp://arxivv org/ absa 14165
[18] Gon Buzaglo, Itamar Harel, Mor Shpigel Nacson, Alon Brutzkus, Nathan Srebro, and Daniel Soudry. How uniform random weights induce non-uniform bias: Typical interpolating neural networks generalize with narrow teachers. Forty-first International Conference on Machine Learning, 2024.
[19] Em Candes and Benjamin Recht. Exact matrix completion via convex optimization, 2008. URL https://arxix www./o/////////eo////ooo/eaeee// abs/0805. 4471
[20] Richard Caron and Tim Traynor. The zero set a polynomial. WSMR Report, pages 05-02, 2005.
[21] Satrajit Chatterjee and Piotr Zielinski. On the generalization mystery in deep learning. arXiv preprint arXiv:2203 2022.
[22] Ping-ych Chiang, Renkun Ni, David Miller, Arpit Bansal, Jonas Geiping, Micah Goldblum, and Tom Goldstein. Loss landscapes are all you need: Neural network generalization can be explained without the implicit bias of gradient descent. In The Eleventh International Conference Learning Representations, 2023.
[23] Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on learning theory, pages 1338. PMLR, 2020.
[24] Eungchun Cho. Inner product of random vectors. International Journal of Pure and Applied Mathematics, 56(2):217-221) 2009.
[25] Hung-Hsu Chou, Carsten Gieshoff, Johannes Maly, and Holger Rauhut. Gradient descent for deep matrix factorization: Dynamics and implicit hias towards low rank, 2023. httpa//tp////axii www..oogggbbaa.. 2011. 2011.13772
[26] Nadav Cohen and Noam Razin, Lecture notes on linear neural networks: A talc of optimization and generalization in deep learning, 2024. URL jttpp:////// http://wwwww.rr////////a//// 13767
[27] Nadav Cohen and Amnon Shashua. Convolutional rectifier networks generalized tensor decompositions. International conference on machine learning, pages 955-963. PMI.R, 2016.
[28] Nadav Cohen and Amnon Shashua. Inductive bias of deep convolutional networks through pooling geometry. arXiv preprint 1ii.:1605.067433 2016.
[29] Naday Cohen, Or Sharir, and Amnon Shashua. On the expressive power of deep learning: A tensor analysis. In Conference on learning theory, pages 698-728. PMLR, 2016.
[30] Alex Damian, Eshaan Nichani, and Jason Lee. Sell-stabilization:: The implicit bias of gradient descent at the edge of stability. arXiv preprint arXiv:2209. 15594, 2022.
[31] Philip J. Davis. Gamma function and related functions. In Milton Abramowitz and Irene A. Stegun, editors, Handbook of Mathematical Functions with Formdls, Gruphs, and Mathematical Tables, chapter 6, page 258. Dover Publications, New York, 1972.
[32] Giacomo De Palma, Bobak Kiani, and Seth Lloyd. Random deep neural networks are biased towards simple functions. Advances in Neural Information Processing Systems, 32, 2019.
[33] John Duchi. Lecture notes for theory of statistics (stats:300b), 2017. URL Intps:::: stanford Accessed: 2025-01-21.
http://cssttt330o//cc//oo/eeeeee pdf
[34] Armin Eftekhari and Konstantinos C. Zygalakis. Implicit regularization matrix sensing: A geometric view leads to stronger results. arXiv preprint arXiv:2008. /2091, 2020.
[35] Ge Fan, Chaoyun Zhang, Junyang Chen, Paul Li, Yingjie Li, and Victor M. Leung, Improving rating prediction in multi-criteria recommender systems via a collective factor model. IEEE Trunsactions on Network Science and Engineering, (066))3633-364) 2023. doi: 10. 10.1100/
[36] Stefano Favaro, Boris Hanin, Domenico Marinucci, Ivan Nourdin, and Giovanni Peccati. Quantitative cits in deep neural networks. Probability Theory and Related Fields, pages 1-45, 2025.
12

---

[37] Bernard D. Flury. rcceplance-rejection sampling made easy. SIAM Review, 32(3):474-476 1990.
[38] Rahul Garg. Gradient descent with sparsification: An iterative algorithm for sparse recovery with restricted isometry property. page 43, 06 2009. doi: 10. 10.1145/153334.116 1553417..
[39] Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis, 2017.
[40] Rong Ge, Jason D. Lee, and Tengyu Ma. Matrix completion has no spurious local minimum, 2018. URL https://arxiv: www.aawwww.....aoooooooooo wwtgg//b//66..0//.//
[41] Daniel Gissin, Shai Shalev- Shwartz, and Amit Daniely. The implicit bias of depth: How incremental learning drives generalization. arXiv preprint 1rXiv:199../205/ 2019.
[42] Daniel Gissin, Shai Chalev-Shwarte and Amit Daniely. The implicit bias of depth: How incremental learning drives generalization, 2019. URL Btl.hhtta://axiiii org/ abs/ 1909..999.... 12051
[43] Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srebro. Implicit regularization in matrix factorization, 2017. URL /ttt/hhtt///rrae //rpiiv////xvv..o// http:////aaaa..orra//////..... 09280
[44] Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srehro. Implicit bias of gradient descent on
linear convolutional networks, Advances neural information processing systems (NeurlPS), 31, 2018.
[45] Boris Hanin. Random neural networks in the infinite width limit as gaussian processes. The Annals of Applied Probability, 33(6A):4798 4819, 2023.
[46] Boris Hanin and Grigoris Paouris. Mon-asympiotic results for singular values of gaussian matrix products. Geometric and Functional Analysis, 31(2):268-324, 2021.
[47] Boris Hanin and Alexander Zlokapa. Bayesian interpolation with deep linear networks. Proceedings of the National Academy of Sciences, 120(23):c23013455122 2023.
[48] Itamar Harel, William M Hoza, Gal Vardi, Itay Evron, Nathan Srebro, and Daniel Soudry. Provable tempered overfitting of minimal nets and typical nets. arXiv preprint arXiv:2410. 19092, 2024.
[49] Kais Hariz, Hachem Kadri, Stéphane Ayache, Maher Moakher, and Thierry Artieres. Implicit regular- ization with polynomial growth in deep tensor factorization. In International Conference on Machine Learning, pages 4484-8501. PMLR, 2022.
[50] Haiyun He, Hanshu Yan, and Vincent Tan. Information-thhorrtiic characterization of the generalization error for iterative semi-supervised learning. Journal of Machine Learning Research, 23(287):1-55 -52, 2022.
[51] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, 2015. /tttlttta///axiiv.oom wwwpg//bb///ii 1512. 03385
[52] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectitiers: Surpassing human- level performance on imagenet classification, 2015. URL http::t/////xi...r.. http:/arwwwa.rrrraaa/aaaa//e///e 01852
[53] Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks, 2018 URL
06993
[54] Minyoung Huh, Hossein Mohahi, Richard Zhang, Brian Cheung, Pulkit Agrawal, and Phillip Isola. The low-rank simplicity hias in deep networks. arXiv preprint arXiv:2003. 10427, 2021.
[55] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift, 2015. httpsttss://// httptpss//aaxxi.ooo
[56] Pavel Izmailov. Sharad Vikram. Matthew D Hoffmman, and Andrew Gordon Gordon Wilson. What are bayesian neural network posteriors really like? In International conference on machine learning, pages 4629-4640. PMLR, 2021.
[57] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generaliza- tion in neural networks. Advances in neural information processing systems, 31, 2018.
[58] Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep leaming. Advances in Neural Information Processing Systems, 33: 13:17776-17186 2020.
[59] Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. arXiv preprint 191 2019.
13

---

[60] Jikai Jin, Zhiyuan Li, Kaifeng Lyu, Simon Shaolei Du, and Jason D Lee. Understanding incremental learning of gradient descent: fine-grained analysis of matrix sensing. In International Conference on Machine Learning, pages 15200-15238. PMLR, 2023.
[61] Li Jing, Jure Zbontar, and Yann LeCun. Implicit minimizing autoencoder, 2020. //axxiv.org/aat www.o/////////oo///o///eeogoooee 00010000679
URL https:
[62] Diederik P Kingma. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[63] Yiwen Kou, Zixiang Chen, and Quanquan Gu. Implicit bias of gradient descent for two-layer relu and leaky relu networks on nearly-orthogonal data. Advances in Neural Information Processing Systems, 36: 30167-30221, 2023.
[64] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Wein- berger, editors, Advances Neural Information Processing Systems, volume 25. Curran Asso- ciates, Inc., 2012. URL
www.reeuurrripeereeeee httppppppp..cppppp...eaaaa/ppppp 38962336667666444246666666 Paper pdf
[65] Gitta Kutyniok. Theory and applications of compressed sensing, 2012. URL wtttps://axxii.... /rrg//r///v.. abs/1203.38V
[66] Andrew K Lampinen and Surya Ganguli. An analytic theory of generalization dynamics and transfer learning in deep linear networks. arXiv preprint arXiv:1809) 18... 10374, 2018.
[67] Rafal Latala and Dariusz Matlak. Royen's ss proof of the gaussian correlation inequality. In Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 2014-2016, pages 265-275. Springer, 2017.
[68] Yann LeCun, Léon Bottou, Geneviève B. Orr, and Klaus- Robert Mülllr. Efficient backprop. In Neural Networks: Tricks of the Trade, pages 9-50. Springer, 1998.
[69] Yoav Levine, Noam Wies, Daniel Jannai, Dan Navon, Yedid Hoshen, and Amnon Shashua. The inductive bias of in-context learning: Rethinking pretraining example design. arXiv preprint 10..52110.00541. 2021.
[70] Binghui Li. Zhixuan Pan, Kaifeng Lyu, and Jian Li. Feature averaging: An implicit bias of gradient descent leading to non-robustness in neural networks. arXiv preprint arXiv:2410. 10322, 2024.
[71] Yi Li and David P Woodruff. The product of gaussian matrices is close to gaussian. arXiv preprint arXiv:2108. 09887, 2021.
[72] Yuanzhi Li. Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over parameterized matrix sensing and neural networks with quadratic activations. In Conference On Learning Theory, pages 2-47. PMIR, 2018.
[73] Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning, 2021. URL /ttpps/::///ar wwwreiiii.rrgaaae arg/abs/ aat///12.202.....///// 2012.012222222 09839
[74] Ilya Loshchilov and Frank Hutter. Decoupled
weight decay regularization.
arXiv preprint
arXiv::111..51001, 2017.
[75] Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint arXiv: 19009990999999 2019.
[76] Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora. Gradient descent on two-layer nets: Margin maximization and simplicity bias. Advances in Neural Information Processing Systems, 19:11--8-1999 2021.
[77] Cong Ma, Kaizheng Wang, Yuejic Chi, and Yuxin Chen. Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion. and blind decon- volution. Foundations of Computational Mathematics, 20(3):41 August 2019. ISSN 1615-3383. doi: 10. 10.10007/100000-099 019-999999999999 htlp:htt:///at doi www.:ooi..ooooo..ooooooooo www./ogg///0//.. 100000000//000
[78] Andrew L. Maas, Awni Y. Hannun, and Andrew Y. Ng. Rectifier nonlinearities improve neural network acoustic models. In Proceedings of the 30th International Conference on Muchine Learning, 2013.
[79] Eran Malach and Shai Shalev- Shwartz. Is deeper better only when shallow is good? Advances in Neural Information Processing Systems, 32, 2019.
14

---

[80] Pierre Marion, Yu-Han Wu, Michael E Sander, and Gérard Biau. Implicit regularization of deep residual networks towards neural odes. arXiv preprint arXiv:2309.01213. 2023.
[81] Hrushikesh Mhaskar, Qianli Liao, and Tomaso Poggio. Learning functions: when is deep better than shallow. arXiv preprint (:03:v:6633000000 2016.
[82] Hancheng Min, Salma Tarmoun, René Vidal, and Enrique Mallada. On the explicit role of initialization on the convergence and implicit bias of overparametrized linear networks. In International Conference on Machine Learning, pages 7760-7768. PMLR, 2021.
[83] Chris Mingard, Joar Skalse, Guillermo Valle-Pérez David Martinez- Vladimir Mikulik, and Ard A Louis. Neural networks are a priori biased towards boolean functions with low entropy. arXiv preprint arXiv: 1522, 2019.
[84] Vinod Nair and Geoffrey E. Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 807-814, 2010.
[85] Prectum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang. Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt, 2019. URL/httss:/aaxxv.com wttp:///...raa///1112/ abs/1912 02292
[86] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021(12)1124003, 2021.
[87] Behnam Neyshabur. Implicit regularization in deep learning, 2017. URL httpaa/::///rrii.vcoo 1709. 01953
[88] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv: 14126664, 2014.
[89] Amit Peleg and Matthias Hein. Bias of stochastic gradient descent or the architecture: disentangling the effects of overparameterization of neural networks. In Forty-first International Conference on Machine Learning, 2024.
[90] Alethea Power, Yuri Burda, Harri Edwards, Igor Bahuschkin, and Vedant Misra. Grokking: Generalization beyond overfitting on small algorithmic datasets, 2022.
ortp:///w....//////20..... 02177
[91] Ning Qian, On the momentum term in gradient descent learning algorithms. Neural Nenworks, 12(1): 145-151, 1999.
[92] Lianke Qin, Zhao Song, and Ruizhe Zhang, A general algorithm for solving rank-one matrix sensing, 2023. BRLLatttpp///arad.orrr/aaba wttp:///////a/aaa/oooba 1
[93]
Adityanarayanan Radhakrishnan, George Stefanakis. Mikhail Belkin, and Caroline Uhler. Simple, fast, and flexible framework for matrix completion with infinite width neural networks. Proceedings of the National Academy of Sciences,
(1116))221506411 19, 2022.
[94] Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred A. Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks, 2019. URL hattp:://arx/ org/abs/1806.08 08734
[95] Hrithik Ravi, Clay Scott, Danicl Soudry, and Yutong Wang. The implicit bias of gradient descent on separable multiclass data. Advances in Neural Information Processing Systems, 37:81324-81355 2024.
[96] Noam Razin, Asaf Maman, and Naday Cohen. Implicit regularization in tensor factorization, 2021. URL aattps://arzin org/ abs/ 2202. 099722
[97] Noam Razin, Asaf Maman. and Nadav Cohen. Implicit regularization in hierarchical tensor factorization and deep convolutional neural networks. In Kamalika Chaudhuri, Stefanic Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 18422- 18422-18462. PMLR, 17-23 Jul 2022. URL BtLLittttps///prceeddinn wtw.gggssnl.rrrr.eeeeeee
mlr ppress/ / www2/razin22a...mmmm html
[98] Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in hierarchical tensor factorization and deep convolutional neural networks, 2022. URL https////r/ org/abs.. abtp///....a1 11729
15

---

[99] Jason D. M. Rennie. Jacobian of the singular value decomposition with application to the trace norm distribution. http://people..co wwtp:ppp..sall....eeeeuueee miit.ed//renni//wiiiggg February 2006.
[100] Christian P. Robert and George Casella. Monte Carlo Statistical Methods. Springer Texts in Statistics. Springer, New York, 2 edition, 2004,
[101] Chris Rohlfs. Generalization in neural networks: A broad survey. Neurocomputing, 61 1: 1217001 2025.
[102] David E. Rumelhart, Geoffrey Hinton, and Ronald J. Williams. Learning representations by back- propagating errors. Nature, 323:533-536 1986.
[103] Tim Salimans and Diederik Kingma. Weight normalization: A simple reparamettriizatoon to accelerate training of deep neural networks, 2016. URL lattp:://axxx wttp://.rrrraaa////////2
[104] Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. arXiv preprint arXiv:1312.00 13/2.6120, 2013.
[105] Rylan Schaeffer, Mikail Khona, Zachary Robertson, Akhilan Boopathy, Kateryna Pistunova, Jason W Rocks, Ila Rani Ficte, and Oluwasanmi Koyejo. Double descent demystified: Identifying, interpreting & ablating the sources of a deep learning puzzle, arXiv preprint arXiv:2303. (.1:2333..1451,, 2023.
[106] Mahdi Soltanolkotabi, Dominik Stöger, and Changzhi Xie. Implicit balancing and regularization: Generalization and convergence guarantees for overparameterrize asymmetric matrix sensing. In The Thirty Sixth Annual Conference on Learning Theory, pages 5140-5142. PMLR, 2023.
[107] Daniel Soudry, Flad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srehro. The implicit bias of gradient descent on separahle data. Journal of Machine Learning Research, 19(70):1-57, 2018.
[108] Ruoyu Sun and Zhi- Qui-Quan Luo. Guaranteed matrix completion via non-convex factorization. IEEE Transactions on Information Theory, 62(11):6535 6579, November 2016. ISSN 1557-9654. doi: 10.1109/ti.2201.225998
http://:://dx http:t:://x.dooo.rrge.. www..//................
2598577
[109] Shih- Yu Sun, Vimal Thilak, Etai Littwin, Omid Saremi, and Joshua M. Susskind. Implicit greedy rank learning in autoencoders via overparameterized linear networks, 2021. https:// www..oogggbbb.. 2107. 01301
[110] Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural networks. Intermational conference on machine learning, pages 6105-6114, 14. PMLR, 2019.
[111] Mingxing Tan and Quoe V. Le. Efficientnet: Rethinking model scaling for convolutional neural networks, 2020. URL https://arxix www.a/wwwwi...oooooooa wrgg/bs/1900 wtw.b////.990 11946
[112] Ryan Theisen, Jason Klusowski, and Michael Mahoney. Good classifiers are abundant in the interpolating regime. In International Conference on Artificial Intelligence and Statistics, pages 3376-3384. PMLR, 2021.
[113] Joel A. Tropp and Anna C. Gilbert, Signal recovery from random mcasurements via orthogonal matching pursuit. IEEE Transactions on Information Theory, 53(12):4655-466 2007. doi: 10.1 109/ 909108.
[114] Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Benjamin Recht. Low-rank solutions of linear matrix equations via procrustes flow, 2016. https:t:::///nt hwwp:/.org//bba. abs/ 1507 03566
[115] Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Instance normalization: The missing ingredient for fast stylization, 2017. URL htlllhhtta///aiii/// wwt.://///aab/eeeeeeeeeeeeeeeeee 1607708022
[116] Guillermo Válee-Pérez, Ard A Louis, and Chico Q Camargo. Deep learning generalizes because the parameter-function map biased towards simple functions. In 7th International Conference on Learning Representations, ICLR 2019, 2019.
[117] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need, 2023. URL http:tttatssii...ot wwtpssiwwrggaab////e/eeo haagg//bs/177 1706 03762
[118] Roman Vershynin. High-DDmensional Probability An Introduction with Applications in Data Science, chapter Example 1.1. Cambridge University Press, Cambridge, I edition. 2018.
[119] Roman Vershynin. Righ-Dimensional Probability: An Introduction with Applications in Data Science, chapter Exercise 4.50. Cambridge University Press, Cambridge, 2 edition, May 2025.
16

---

[120] Roman Vershynin. High-Dimension Probubility: An Introduction with Applications in Data Science, chapter Lemma 3.4. Cambridge University Press, Cambridge, edition, May 2025.
[121] Zheng Wang, Geyong Min, and Wenjie Ruan. The implicit bias of gradient descent toward collaboration between layers: A dynamic analysis of multilayer perceptions. Advances in Neural Information Processing Systems, 37:74868- 77774888887778888.888 2024.
[122] Noam Wies, Yoav Levine, Danicl Jannai, and Amnon Shashua. Which transformer architecture fits my data? a vocabulary bottleneck self-attention. In International Conference on Machine Learning, pages 11170- 11181. PMLR, 2021.
[123] Andrew G Wilson and Pavel Izmailov. Bayesian deep learning and a probabilistic perspective of generalization. Advances neural information processing systems, 33:4697-4708, 2020.
[124] Ashia Wilson, Rebecca Roelofs, Mitchell Stem, Nati Srebro, and Benjamin Recht. The marginal value adaptive gradient methods in machine learning. Advances in neural information processing systems, 30, 2017.
[125] Johan S Wind, Vegard Antun, and Anders Hansen. Implicit regularization in ai meets generalized hardness of approximation in optimization-ssarp results for diagonal linear networks. arXiv preprint wwXiv:2307.074/00 2023.
[126] Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrizee models. In Conference on Learning Theory, pages 3635-3673, PMLR, 2020.
[127] Fan Wu and Patrick Rebeschini. Implicit regularization in matrix sensing via mirror descent, 2021. URL https:/ potps://arxiin . wwt//ts///////e//e//oo aataa/aa////// 2205 13831
[128] Jingfeng Wu, Vladimir Braverman, and Jason D Lee. Implicit bias of gradient descent for logistic regression at the edge of stability, Advances in Neural Information Processing Systems, 36:74229-742222 2023.
[129] Yuxin Wu and Kaiming He. Group normalization, 2018. URL
08494
[130] Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transforma- tions for deep neural networks, 2017. URL hattts:///arx:t
htrgg/bs/11611 05431
[131] Yang Xu, Yihong Gu, and Cong Fang. The implicit bias of heterogencity towards invariance: A study of multi-environment matrix sensing, arXiv preprint arXiv:2403.0144 014400 2024.
[132] Yao Lei Xu, Ciuseppe G Calvi, and Danilo P Mandic. Tensor-train recurrent neural networks for interpretable multi-way financial forecasting. In 202/ international joint conference neural networks (JCCN), pages 1-5. IEEE, 2021.
[133] Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. A unifying view implicit bias in training linear neural networks. arXiv preprint arXiv:2010.02501, 2020.
[134] Chiyuan Zhang. Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.0355: 2016.
[135] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriel Vinyals. Understanding deep lcarning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
[136] Jialun Zhang, Salar Fattahi, and Richard Y Zhang. Preconditioned gradient descent for oxer-parameterrieed nonconvex matrix factorization. Advances Neural Information Processing Systems, 34:5985-5996, 2021.
[137] Qinqing Zheng and John Lafferty. Convergence analysis for rectangular matrix completion using burer- monteiro factorization and gradient descent, 2016. /ttp:/ttts///a wwwpziivv.rrr/eo orgo abb//605..11./..//// 16010 07051
[138] 7hi-Qin John Xu Zhi-Qin John Xu, Yaoyu Zhang Yaoyu Zhang, Tao Luo Tao Luo, Yanyang Xiao Yanyang Xiao, and Zheng Ma Zheng Ma. Frequency principle: Fourier analysis sheds light on deep neural networks. Communications in Computational Physics, 28(5): 1767. January 2020. ISSN 1815-2406. doi: 10.4208/cicp..a--22..
http://x doi org/ 10. 420.//2i2...../ 00- 2020-0006-66
[139] Pan Zhou, Jiashi Feng. Chao Ma. Caiming Xiong, Steven Chu Hong Hoi, et al. Towards theoretically understanding why sgd generalizes better than adam in deep learning. Advances in Neural Information Processing Systems, 33:21285 21296, 2020.
17

---

[140] Gordan Zitkovic. Lecture 8: Characteristic functions. Lecture notes for the course Theory of Probability I, Department of Mathematics, University of Texas at Austin, 2013. Corollary 8.5.
[141] Emmanuel Candes and Benjamin Recht. Exact matrix completion via convex optimization. Communica- tions of the ACM, 55(6): 1116),111-11,.10 2012.
[142]
Emmanuel J Candes and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE transactions information theory, 56(5):2053-2080) 2010.
[143] Jafar Jafarov. Survey of matrix completion algorithms. arXiv preprint arXiv:224.001522 2022.
[144] Charles R Johnson. Matrix completion problems. In Proceedings of Symposia in Applied Mathematics, volume 40, pages 87-169, 1990.
[145] A Paszke. Pytorch: An imperative style, high-performance deep learning library. arXiv preprint arXiv:19/2.01703, 2019.
[146] Benjamin Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12 (12), 2011.
[147] Olivier Roy and Martin Vetterli. The effective rank: A measure of effective dimensionality. In 2007 15th European signal processing conference, pages 606-6 610. IEEE, 2007.
[148] Ruoyu Sun and Zhi- Zhi-Quan Luo. Guaranteed matrix completion via non-convex factorization. IEEE Transactions on Information Theory, 62(11 (2(11))655) 1:6555-6579, 2016.
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All of our theoretical claims and empirical results clearly presented in Sections 3 and and Section respectivvly
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of our work are properly discussed Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
19

---

Answer: [Yes]
Justification: All of our assumptions are clearly presented before each claim. All claims are rigorously proven in the appendix, with short proof sketches in the main paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide all implementation details in Appendix H Code for reproduc- ing the experiments will be made available at
nn- aan-ddgee gd-gge-mmm"
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
20

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We provide all implementation details in Appendix H Code for reproduc- ing the experiments will be made available at /ttpp::/github.b.. com/ YoniSlutzky98/ nn- aan-gd-ge gd-gen-m-
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
wwt.:/uwmmsssioossoooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-sourge benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
guwdes/ CodeeSumiiiseeeeee onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide all implementation details in Appendix H Code for reproduc- ing the experiments will be made available at hhttts://githhii com Yoni Yooii/nnnt1y988///// nn aoa-gd-gen-mt
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The results reported in Section 5 and Appendix show the medians and their corresponding inter-quartile ranges, each computed from eight distinct random seeds.
Guidelines:
The answer NA means that the paper does not include experiments.
21

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide all implementation details in Appendix H Code for reproduc- ing the experiments will be made available at /tttttt:///// https:///gthub.... com Yoni /oton/oynnSuutty9/// nn-ged umn-gdgge-mit
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp::/neurrpps.. https///cppppcccccccecceiiiaaeee
Answer: [Yes]
Justification: This paper fully conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
22

---

The paper deals with theoretical properties of generalization in deep learning, and the work performed has no societal impact.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not deal with data or models that have high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
23

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the datasets.paperssii paperswi thcode. com/datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide all implementation details in Appendix H Code for reproduc- ing the experiments will be made available at /ttttt:://// http///gtttu..../. com/ YoniSlutzky988 nn- gd-gen-mi
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
24

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM for what should or should not be described.
25

---

A Proof of Theorem 1
This appendix proves Theorem | Appendix establishes an equivalence between a matrix factor- ization and feedforward fully connected neural network. This equivalence allows us to utilize the theoretical results of Hanin [45] and Favaro al. [36]. developed for feedforward fully connected neural networks of large widths. Relying these results: Appendix A.2 treats the case where 2(-) an arbitrary regular probability distribution and the width tends to infinity; and Appendix A.33
treats the case where (--) is zero-centered Gaussian distribution and the width k is finite.
A.1 An Equivalence Between Matrix Factorizations and Fully Connected Neural Networks
We begin by defining the concept of fully connected neural network. Definition A fully connected neural network of depth
with input dimension m' N. output dimension m E 19, hidden dimension k E N and activation function o--) is function (d)
Xa E TM + Za E RR of the following recursive form:
Wix (5-0)(1111)
j=1 i 2,
W WW5o(zz
where W1 E RR. Wa E Rm and W Wa E RR. are the networks weights, and a applied vector is shorthand for applied to each entry.
Next, we prove a useful equivalence which shows that when matrix factorization and fully connected neural network share their weights and activation function, each of the columns of the former are equal to the outputs of the latter when input the appropriate standard basis vectors.
Lemma 1. Let a E [m']. For any weight matrices Wi...., Wa and activation function o.), the a column of the matrix factorization W (Equation (4h) produced by the weight settings (W1...., Wa) and the activation function (.), is equal to the the output of the fully connected neural network (Definition 5 produced by the weights (W1.... Wa) and the activation function o-),, when the input ex E R the standard basis vector holding its coordinate and zeros in the rest, Formally, we denote this as
W
2/
where [W].a is the a column of W and Zis is the output of the fully connected neural network when the input is C. E Imm...
Proof. We prove the claim via induction on First, for the base case, it trivially holds that
[W1a],a W1.10 2
Next, fix j E [d] and assume that [Wis].a = (1) We thus have that
[Wij+1),a Wisttea, Wit1o(Winjee
WWHHo(WW1,eea)
WWHHoo(Wissla (Wis)la)
W5+10
where the third equality is due to Lemma 21, and the fourth equality is due to the inductive assumption.
With this we complete the proof.
A.2 Proof for Arbitrary Regular Distribution and Infinite Width
The outline of the proof for the arbitrary prior case is as follows; Appendix A.2. presents Theorem 3 of which the arbitrary prior case of Theorem I is special case. Appendix|A.2.1 provides a useful Lemma used the proof of Theorem 3 Appendix A.2.3 adapts result from Hanin (45) showing that an infinitely wide matrix factorization converges in distribution to centered Gaussian matrix (Definition D Finally, Appendix applies tools from probability theory to show that the latter convergence implies the conditions required for Lemma 2 in Appendix A.2.2
26

---

A.2.1 Restatement of the Arbitrary Prior Case of Theorem
The arbitrary prior case of Theorem follows from Theorem which allows for the distribution Q(-) and the activation (-) to be slightly more general. Theorem is presented below; afterwards, we demonstrate how it implies the arbitrary prior case of Theorem
Theorem 3. Let N be a fixed depth. Let Q(-) be some probability distribution on which satisfies
E [c) =0 2~2()
E =1
x~2())
has finite higher moments and is symmetric, i.e. if 2(-) then -x 2()) Let o(.) be an activation function that is not constant and anli-symmetric, i.e,
4x E R. o(x) -
furthermore suppose that is absolutely continuous, and that its almast--eergwwere defined derivative is polynomially bounded, i.e:
o d'(x)
Pp OSL
30.
1+ 2 (X)
Suppose also that
(-)) (x)) > >0
Let Egens Euain: CW > 0. Suppose that for any j E [d]. the entries of W E Pm are drawn
independently by first sampling x ~ Q(-) and then setting [Wrlrs = factorization W satisfies
lew x. Then the matrix my
lim P (Egen(W) Egen Cirain (W) < Erainn 10000
lim PC (W) < Egen) 1-+00
Let 2(-) be regular distribution over IR (Definition 2) and let (-.) be an admissible activation function (Definition 4 that is anti-symmetric. First, observe that since Theorem Janrewssslllwss
alllow for arbitrary
> 0, the condition for Ez-2(-) [a-] = is satisfied with = Ez~o(-) [a+²]. Next, note that since Q(-) assigns a positive probability to every neighborhood of the origin and has finite higher moments, and since (-)) does not vanish on both sides the origin, must hold that
E [a (x)] 0.
The rest of the conditions in Theorem 3 are directly fulfilled by the properties of regular distributions (Definition [ and the properties of admissible activation functions (Definition 4 that are anti- symmetric. Overall we showed that Theorem applies for Q(-) and (-), and so the arbitrary prior case of Theorem will follow from Theorem
A.2.2 Sufficient Condition for Theorem
useful Lemma used in the proof of Theorem is provided below. The Lemma shows that for an infinitely wide matrix factorization (Equation with probabilities for low training loss and low generalization loss equal to that of a centered Gaussian matrix (Definition 8). the probability for having low generalization loss (Equation ( conditioned having low training loss (Equation is equal to the probability of having low generalization loss.
Lemma 2. Let Egen; Grrain > O. Let Wia E mmm be a centered Gaussian matrix (Definition g
Suppose that as kt the quantities
P (Curaio (W)) < Eurin Egeu (W) Egea) P (Cuain (Wia) Cuain (Wia)) < Egen))
IP (Lmin (W) Errain) P (Lurain (Wia) Erriin))
and
IP (Cgen < Egen) P (Cyon (Wina) Egen)]
all tend to 0. Then
lim P (gan (W) Egen Craiin (W) < Emiin k-000
lim P. (Lgen(W) Egen) k0000
27

---

Proof. By the definition of the conditional probability
P (Crrain (W) < Euain [W) Egen)
P ( Egon Craiin (W) Etrain
P (Cirain (W) < Emain)
Observe that P (Crrain (Wia) < Crrain) > 0 does not depend on k. Therefore, we have that
lim P (fgen (fgen()) (W) 'gen Lirain (W)) < R-+00
lime-roo P (Lirain Errain Lyen Eyyn(W) (W)
Egen)
Grain
limg-+so P (Craii(() < (train)
P (Curai (Wia) Grain Lagen(Winl (Wia) < 'genn
P (Cuain (Wid) < Euain)
(Egen (Wns) < Eyen Furain (Wia) Cirain
P (Cegn (Wid) Egen
lim P (Lgen (W) <
Egen
k++00
In penultimate transition we have used the fact that the measurement matrices B are orthogonal to .l....,A, and thus
Egenl (Wia)= < Egon Cirain Wiia))
Eraiin
n ((A,, Win) - 31)² 2 cvain
P
Σ
((A, Wiia (A,W*)) < Egen
AEB
P
1
((A, Wii) (A, (A,W)))² <
Egen
AEB
= (Cgeen (Wiaa) < Egen)
where the second equality stems from the fact that for any fixed vectors ......, v, which orthogonal (each of the flattened matrices A An and the flattened A), and a vector of indepen- dent identically distributed zero-centered Gaussian variables X (the flattened Wia), the variables {(X, vx) hiser are independent.
A.2.3 Convergence in Distribution to Centered Gaussian Matrix
In this section prove that in the limit of infinite width, the matrix factorization converges in distribution to a centered Gaussian matrix (Definition (). Key to the proof is the main result of Hanin 45 which characterizes the convergence of infinitely wide fully connected neural networks
Gaussian processes. We present here slightly adapted version which is sufficient for our needs.
Theorem 4 (Theorem 1.2 of [45] (adapted)). Let T C Rmmm probability distribution on which satisfies
be some compact set. Let Q(-) be some
[x] = 0,
E z-)(()
=1
T~ 2()
and has finite higher moments. Suppose that for any j E [d], the entries of W, E Rm are drawn independently by first sampling Q(-) and then setting [Wjlrs = / cw x. Additionally, suppose that absolutely continuous and that its almost-everywhere defined derivative is polynomially bounded:
m,
d'(x) 1 1+|2| (x)
3p > O.L.
X0.
Then as h: -> D0, the sequence of stochastic processes E TR'
2i ( E R given by a fully connected neural network (Definition)) set with weights WI,..., Wa converges weakly in C (T, R I a zero-centered Gaussian process taking values in m with independent identically distributed coordinates. For any r [m] and inputs Na, Xg E T, the coordinate mordinate-wise wise covariance function
k-(d) 0g := Cov ([r!.)
[ [T(d]] [ = lim Cov ([2.0)
(d)
23
28

---

for this limiting process satisfies the following recursive relation:
K k-1-11
k(i-1)) k(--1)
Ku cw Blo((z)
Fa
N
0,
az k
Z/8
ag
for ......,. d, with the initial condition
K K 0/
(1) 2/3
cw
E
La
where the distribution of [Z(T]] the weights W1.
2 ()"],)
(1) (Wixa, W2x;) is determined by the distribution of
Proof. The above is an adaption of Theorem 1.2 in
45 where the fully connected neural network
has no biases. For full proof see Hanin 45
We now move to the following Proposition arising from Theorem 4 showing that for a symmetric distribution 2(-) and anti-symmetric activation function the random variables corresponding the network's is outputs when the inputs Xa, Xa are two distinct standard basis vectors, converge in distribution to independent identically distributed zero-centered Gaussian vectors.
Proposition 2. Let ' S I8T be the unit sphere. Suppose the assumptions of Theorem hold. Suppose also that:
The distribution Q(-) is symmetric, i.e., if Q() then -I ~Q-)(.).
The activation function is not constant and anti-symmmttrcc, i.e., Wz E R. (zz) -o(-x).
It holds thut
[x) 0. go (()
E
Let 3 [m'' be two distinct indices. Denote e, E Rmm the standard basis vector holding 1 in its coordinate and zeros in the rest. Denote C₁ similarly. Then as k - co the random output vectors zee and (d) corresponding to ea and eg respectively converge in distribution vectors each with independent entries drawn from the same zero-centered Gaussian distribution.
independent random
(d) Proof. Per Theorem 4 as - oo the variables (0)) and 1 converge in distribution to zero-centered Gaussian vectors where for any distinct indices r, r E [m]:
The entries
Zi
(d)
Zic
are independent.
(d)
The entries
2
are independent.
r
The entries
(d)
2 are independent.
Next, using the notation of Theorem we prove via induction d that K/ 0, K!d!
K 33 and
(d)
that k(d)) is finite and positive. First, for the base case, note that have
k-(1) aB
(1)
= ew EE
2
Cw EE
(Wiea)))
(Wie=)))
cw E
(Will,.)
(Wilr.)]
(Wi))
E I (Wii),)))
cw T.
29

---

where the ultimate transition is due to the independence of [Wi1,, and [Wil1,0- Next, since 2(-) is symmetric and o is anti-symmetric, we obtain by Lemma 20 that
(Will..) = E (Wil O. B
Overall, we obtain that
K. = cw 00 0.
ag
Additionally, since [Wi]1,a and [Wi]2,3 both drawn from 2(-), obtain that
k(I)
cw E
2
(1 []]
(Wall,a)
(Will,a)
CW
(Wil
(Wil1.s)
cw
(1)
B3
Finally, by our assumption have that K()
(IWil,a)) a ( cw
E [x² > 0.
2~ e(-)
required. Next, fix j [d] and assume that KGi O, K positive. Hence, plugging the inductive assumption into Theorem obtain that
K (j)
and that K is finite and
k(/-1) cw E (((=))((2))
where
k-
K
k()
= - (0.
K!
Zex
N
0,
K-
K()
au
#8
Therefore, 2n and 2g are independent identically distributed zero-centered Gaussian variables. Hence, we obtain that
kbi+1) ew E cw 0- =
where the penultimate transition is due Lemma 20 Additionally,
k(++) cw E (= - cw E [[ = K (j+1)
88
Finally, we have by our inductive assumption that k!I is finite and positive, thus the non-constant random variable 2o (0, K()) has finite moments. Therefore, since a has a polynomially bounded derivative almost-everywhere and is not constant, it holds that
K(++1) cw E (z. 0
as required. Thus by Theorem 4 for any j [m]. the entries
Zi
(d)
and (d)
2 converge in
distribution to two independent identically distributed zero-centered Gaussian variables as k +
Overall we have shown that A co, the random vectors z!d) and 2 converge to two independent random vectors each with independent entries drawn from the same zero-centered Gaussian distribution, completing the proof.
(d)
The last two arguments imply the following important Corollary, which states that - oc, the matrix factorization W converges in distribution to centered Gaussian matrix (Definition 8).
Corollary As & - oo, the matrix factorization W converges distribution to the random matrix Wia E mmm.m whose entries are drawn independently from the same zero-centered Gaussian distribution.
30

---

(4) ..... mm corresponding to the Proof. Per Proposition k + the random output vectors 2 inputs e1..... em' converge in distribution to independent random vectors each with independent entries drawn from the same zero-centered Gaussian distribution. Therefore, & oo, the random matrix
(d) 7'm
E R mm.
converges in distribution to the random matrix Wiid mm... whose entries are drawn independently from the same zero-centered Gaussian distribution. The claim follows by Lemma which states that the above matrix is equal to W.
A.2.4 Convergence Distribution Implies Sufficient Condition
In the previous section, Corollary [ showed that W converges in distribution to a random matrix with independent entries drawn from the same zero-centered Gaussian distribution. In this section, we use basic tools from probability theory in order to show that this convergence in fact implies the quantities in Lonvereo converge, completing the proof of Theorem T We begin by introducing the concept of continuity sets:
Definition 6. Let be some random variable on the space Q. set A S2 continuity set X when
P(X E 0A) = -0
where 0A is the boundary of A.
The main tool we employ this part of the proof is Portmanteau's Theorem, which states that convergence in distribution implies convergence in the probability of any continuty set:
Theorem 5. Let {= be series of random variables on the same space Q. Let X be a random variable the space Qt If
dist.
X
X
then for any continuity set A of X (Definition
6 it holds that
lim
P(Xx E
P(X A)
10000
Proof. See Duchi
333
we continue to showing that the sets in question are all continuity sets of Wii We begin by showing that the set with low training error and the set with low generalization error are both continuity sets of Wia-
In order to invoke Theorem 5
Proposition The sets
Syen = (W& E IRmmm'. Lyen (W) < (gen),
Strain = (W E Ipmmmm -Lrain
< &train)
continuity sets of Wiia (Definition 6).
Proof. Consider the first set (the proof is identical for the second). The boundary of the set is of form
[W mmm.' -Cgen Egen = 0}
Since (W) is polynomial in the entries of W and Lgen (W*) Egen f 0, the polynomial Egaa (W) Egen is not the zero polynomial. Therefore by Lemma 23 the boundary has Lebesgue measure zero. Per Corollary Wia has a continuous distribution over IR mmmm and thus it must hold that
Wia E (W E mm,m' (W) - Egen = =0} = =0,
i.e., the set is continuity set.
31

---

The next Lemma shows that the intersection of two continuity sets is also continuity set, hence Proposition B iimlies that Sen Strain also a continuity set.
Lemma 3. Let X be a random variable over the space QL Let A, B Ω be continuity sets of X (Definition 6). Then the set A n B is a continuity set of X.
Proof. Per Definition 6 holds that
P(X 0A)= =0, P(X 0B)
and so
P(X E aAU0B) 0.
Hence, the proof follows if
0(An B) S CaAUeB.
First, recall that for any X C
0x X n Ca(X),
where is the closure of X and Cn(-) is the complement operator. Next, we have that
(AnB) CA, (AnB)
Finally, it holds that
Cn(AnB)=Ca(4))) = Ca(A) Un(A) Cn(B),
therefore,
0(An B) = (ANB) CA(AnB)
(AnB)n n
Co(A) U Cn(
(ANB)nCC(A) U (AnB)
S [An (AnCo(A) U B BBCa(B)
0AUAB
as required.
Overall, we have shown that Corollary Cemoolaayyiimpe iimpiees together with Theorem 5 and Proposition 3 that
lim IP (Cgon (W) < ] n [rrain (W) < Grriin)) P (Ceon( (Wia) < Egon n Errain (Wia) < Crain) }) = 0,
R=000
lim [P (fCirain (W) < (irain)) (f (Wia) < Grain })l 0, 80000
and
lim |P (W)) Egen (Cgen( Egen)))
100
Hence, the proof follows by invoking Lemma which implics Theorem
A.3 Proof for Gaussian Distribution and Finite Width
The outline of the proof is follows; Appendix A.3.1 presents Theorem 6, of which the canonical case Theorem [ is a special case. Appendix A.3.2 provides a useful Lemma used in the proof. Finally, Appendix A.3.3 adapts a result from Favaro et al. (36) showing that a matrix factorization with Gaussian weights has bounded convex distance from a centered Gaussian matrix (Definition 8 and arguing that the latter bound implics the conditions required for the Lemma in Appendix A.3.2
32

---

A.3.1
Restatement of the Canonical Case of Theorem
The canonical case of Theorem follows from Theorem which allows for the activation a ((.) to be slightly more general. Theorem 6 is presented below; afterwards, we demonstrate how implies the canonical case of Theorem[]
Theorem Let d E N be a fixed depth. Let N() be the standard Gaussian distribution, i.e. 1). Let o(-) be an activation function that is not constant and anfi-symmetric, i.e.,
Vx E R. o(x) =-((=x).
furthermore suppose that is absolutely continuous, and that its almost--verryweeee defined derivative polynomially bounded, i.e:
a' a'(x)
3p S.t. Ve E
00.
1+ | (x)
Suppose also that
I8 am)(())
[o² > O.
Let Egens Etrain; CW Suppose that for any j E [d], the entries of W E Bm are drawn independently by first sampling N-) and then setting [Wilrs - CW
Then there exists my
x.
constant C dependent on m, m', d, o, CW; n, emain and Egen and a constant ko E N dependent on and P (Lamin(Wial < éurin), such that for any k 2 kn the matrix factorization W satisfies
P (Coen ( (W) Egen Curin (W) Erriin)
P (W) Egen) S
VA
P(Lirain (Wia) < Errain)
vk
Note that the above bound is of order 1
V Remark 1. For any k 2 ko it holds that
2a
Vk P P(Larin (Win) < (rain)
2c
-((1,,
P( (Wia) < (rriin)
VE
VR
hence
2c VE
O
P(Cuain (Wii)
Ctrain)
VK
Vk
Let (:;00,) be zero-centered Gaussian distribution, and let (r.) be an admissible activation function (Definition 4 that anti-symmetric. First, observe that since Theorem for arbitrary ew > 0, one may view (-; O, v)) as the standard Gaussian distribution (V--) scaled by vv. Next, note that since N.).) assigns a positive probability to every neighborhood of the origin and has finite higher moments, and since or does not vanish on both sides of the origin, it must hold that
E
[ (x) >
(-))(()
The rest of the conditions in Theorem are directly fulfilled by the properties of admissible activation functions (Definition 4 that anti-symmetric.. Overall showed that Theorem 6 applies for ((;+0,,) v) and (.), and so suffices to prove Theorem
A.3.2 Sufficient Condition for Theorem 6
A useful Lemma used in the proof of Theorem 6 provided below. Before presenting the Lemma, we define the convex distance between random variables, and prove that the sets matrices with either low training error low generalization error convex.
Definition 7. Let m e N and let X and be two m-dimensional random variables. The comver distance between X and Y is defined
d.(X, sup |P(X -) P(Y B))
B
where the supremum over all convex B R
33

---

The convex distance between two random matrices is naturally defined as the convex distance between their corresponding flattened vector representations.
Remark 2.
Lemma 4. Let gea Euain 0. The sets
Strasn = =(W E mm. Luain (W) < Euain Sgen = W E Rm.m Cgea(W)
< Egen
convex.
Proof. We prove that Sgen is convex (one can prove the same claim about Strain using identical arguments). To do this, suffices show that Liiin (W) is convex function. Because sums of convex functions are convex, suffices to show that the function corresponding to a single test matrix, namely
((A, W) (A, )))
for some A B is convex, and this is the case because it is the composition of an affine function with the convex function x x?
Remark 3. The intersection two sets is convex, thus the following set is also convex
W E Imm.m -irain (W) < Crain Legn(WW) <
'gen
We are now ready to present the Lemma. The Lemma show that if the convex distance between the matrix factorization (Equation (4 and a centered Gaussian matrix (Definition 8 is
then for any large enough & the probability for having low generalization loss (Equation 33) conditioned on having low training loss (Equation of having low generalization loss.
2 is no more than order O
larger than the prior probability
V
Lemma 5. Let Egen; Errain > 0. Let Wii E IRm., be a centered Gaussian matrix (Definition 8
Suppose that there exists some c such that the convex distance between W and Wia (Definition satisfies
de(W, Wnd) S
Vk
Then there exists some kn E N dependent on c. and Pi Piniin (Wia) < (1rin) such that for any k 2 ko it holds that
2c
P (Egen
(W) (W) < Egen Curai Crrain) S P(Cgen < Egen) P P(Crrain (Wia)
Vk
Euain
Vi
Proof.
Per Definition
7 Lemma and Remark 3 the fact that (W, Wiia)
S vk
c
implies that
(Crrain (W) < Etrain) P(Curin (Wis) &vain)
VI
(P(Cgco()) < Egen) - P(CgonWWid < Egenn) <
VT:
and
(P (W) < Euain Cgen (W) < Egen) - P (Cuain CraainWWid (Wia) < Euain Egen (Wid) < Egea) $ c
Vi P (W) < (train)
By the definition of the conditional probability have that
P(Lgen W) < Egen Limin (W) < Etrain) P(Crrain (W) < Grain Egen (gen(W) Cgen)
Since Wind centered Gaussian matrix (Definition g holds that P(Crain (Wia) < Emain) 0 and so for any
k 2 P(Lurin (Wna) Curin
=: kn
34

---

it holds that P P(Cuaail (Wid) < Euain) e V/
> O. Therefore, for any such &s the above is bound by
(W) < Egon| Cerain ( (W) < Enriin)
P Purain (Wia) < Etrain Lgea WWis) < Egon) + vk
P(Curain( (Wird) < Etrain) - C
V/
P(Crain (Wiia) Etrain) PC(Coon (Wiid) <geen) w/
P(Crrain (Wiia) < Grrain)
V/
P(Crain (Wia) Craina) (P(C (oggenW(W))))) (W) (gen)
c vk)
) VV
a P(Lrrain Wiia) < Ctrain)
v/b
P(Cemin (Wii) < Etrain)
P PLCrriin (Wia) < (rain)
-eegg ([Cgge(W)) égen)
vb
vk.
P(Cirain via) < Grain)
P( (Wid) Crrain) vT:
vT
P(C (W) Cgea)
VE
P(Curin (W (ia)
Curain)
vT:
In the third transition we have used the fact that the measurement matrices A in B are orthogonal to A1 ...,... An and thus
P (fege (Wiaa) 'gen Larain (Win) < (train)
1
P
B
((A, Win) - (A, w=y)²
Egen
n [=1
((A;, Win) 11)² <<< éxrain
AEB
P
((A, Win) (A,W%))
Cgen
P
Σ
((A Win) yz)
Cuain
ACB Egen) (Crrain (iidd < Erriin)
= (Cgen
where the second equality stems from the fact that for any fixed vectors Uj...., U,- which are orthog- onal (each of the flattened matrices AI,..., An and the flattened A), and a vector of independent identically distributed zero-centered Gaussians X (the flattened Wia), the variables ((X, u4) Jisier are independent.
A.3.3 Bound on Convex Distance from a Centered Gaussian Matrix
In this section we prove that for any width k, the matrix factorization has a bounded convex distance from a centered Gaussian matrix (Definition [8. Key to the proof is a result of Favaro et al. (36 which provides a bound on the convex distance fully connected neural network has from Gaussian process. We present a softer adaption of it sufficient for our needs.
Theorem 7 (Theorem 3.6 of [36] (adapted)). Let N(.)) be the standard Gaussian distribution. Suppose that for any j E [d]. the entries of W, E Rmm+1.m; are drawn independently by first sampling x N-) and then setting [Wilrs = V /. Additionally, suppose that a is absolutely continuous and that its almost-everywlee defined derivative is polynomially bounded:
my
o' d'(z)
3p > O... VE
30.
1+ |x|2
For any j = 2.....
.. denote the matrix KG) Rmd mn by
N (0.
() k(lj-1))
Va, B [m']. K/ = ew Blo(za)o(z))),
Fa ZB
k(5-1)
k-l
with the initial condition
Va, 3 E [m']. [0 = ew E a (Wieal)) a ([Weal))
35

---

where for E [m'), the vector E R"' is the standard basis vector holding 1 in its coordinate and zeros the rest. Additionally, for a E [m²'] denote by Zi the output given by a fully connected neural network (Definition 5 set with weights W W for the input Ca. Lastly, for E [m'] denote by I a m-ddimensional zero-centered Gaussian vector with
(d)
vo,8 E [m'], r, E [m]] Cov
[T(
K-d aB
If for any j E [d] the matrix K() is invertible, then there exists c > dependent on m, m', d, o, ew, n, Erain and Egen such that for any k. E 14 it holds that
(I!e) axe(m))
de (za aElm))
Vk"
where we have implicitly regarded (zaa aa(m)) vectors.
(all)) and (I(e1
as m' m-ddimensional random
aa(mm)
Proof. The above is an adaption of case (1) of Theorem 3.6 in [6), where the fully connected neural network has no biases, the partial derivatives in question are all of order zero and the finite collection of distinct non-zero network inputs (ea Ja=1 For a full proof see Favaro et 36
We move forward to the following Lemma, showing that for an anti- semmmtrmmeiii activation function o the covariance matrices K(i are not only invertible but also positive multiple of the identity. Lemma 6. Suppose the assumptions of Theorem hoold. Suppose also that
The activation function a is not constant and anti-symmetric, i.e.
Vx E R. a(x) -o x-x).
It holds that
[o² 0. a=-((()
E
Then for any j E [d] there exists positive constant b(i) > O such that KG) = 868) Im
Proof. The proof is extremely similar that of Proposition We prove via induction on d that and that k(d) is finite and positive, First, for the base case, note that we k(d) = 0, k(d) ag
have
k0)) = cw E
a (Wieal (Wieehh)
(Wi) a ( (W)l,
cw E
cw E a (Will,.)
)
( (Will,))
where the ultimate transition is due to the independence of [Wi] 1, and [Wi],,s Next, since N(.) is symmetric and a is anti-symmetric, we obtain by Lemma 20 that
(Will.)) 13 (WWWl..)) O.
Overall, obtain that
(((1) 0/8 = cw 0-0 0 0.
Additionally, since [W1],,o and [Wi],,s are both drawn from N()., we obtain that
[(1) cw E
(Wal1,a)
(Will,.) (Iill1,))
[Wi1l..)
cw E
99
36

---

Finally, by our assumption we have that
bOa K ow 13 (or (Will.a) (Will,a))
[or
cw
[o² > 0. x~)(()
E
as required. Next, fix j E [d] and assume that K 0. x(i) positive. Hence, plugging the inductive assumption into Theorem
k 8B
and that K is finite and
we obtain that
K kレ cw E ([(2))((22)]
where
Fox 2B
N
0,
K(
K0 ad
= -N 0,
0
K-U
K
83
Therefore, 2a and 2 independent identically distributed zero-centered Gaussian variables. Hence, we obtain that
K k(++1) cw E (o ] [[(x)]] cw 0- =0 0.
0,
where the penultimate transition is due Lemma 20 Additionally,
K(++) cw E (zz = cw E (zz3) K (j+1)
Finally, we have by our inductive assumption that k-U) is finite and positive, thus the non-constant random variable 2n (o k(ll has finite moments. Therefore, since has a polynomially bounded derivative cimost-everywhee and it is not constant, it holds that
B(+1)
R(++1) ow E (o(2))((Z)) 0 oa
completing the proof.
Theorem and Lemma together imply the following Corollary, which states that Za
as [mmml
bounded away from zero-centered Gaussian vector with independent entries.
Corollary 2. There exists O dependent m, m d, a, cw, n. Euain and Egen such that for any k N, the m' m-dimensional random vector (d) outputs of the fully connected neural network (Definition) for the inputs (Ca)ae(m)) satisfies
corresponding to the concatenated
do ((25)) ce(mm)) (T!.)
(d)
(r((m)))
Vi"
([r60])
where the random variables
independently drawn from N (l))..
aE(m(].JEmm)
Lemma and Corollary together imply that the matrix factorization W has the required bound on its convex distance from centered Gaussian matrix Wia (Definition 8. Hence, the proof follows by invoking Lemma 5 which implies Theorem
B Proof of Theorem 2
This appendix proves Theorem Appendix B.1
begins by establishing that for any 7 E Ryo- the
factorized matrix W (Equation (4) is within y (in Frobenius norm) of a rank one matrix with probability - O(/d). This finding utilized by Appendix B.2 which establishes that
probability of the events Lirin < émain and Lggn(W)) (W) 2 étrain occurring simultaneously is ((1 /d) Appendix B.3 shows that the probability of Larii (W) < Eirain 2(1). Finally, Appendix B.4
combines the findings of Appendices B.2 and B. 3 to prove the sought-after result.
37

---

B.1 W is Close to a Rank One with High Probability
According to Definition the matrices W, are obtained by normalizing matrices Wj where each entry of W drawn independently from the distribution 2j- Specifically, each entry of W equals the corresponding entry of Wi divided by [[W ... Willa/d. In this section, we will analyze the spectrum of the matrix W 1:2 == W -.... W using results from Hanin and Paouris [46 to show that this implies that with high probability, W is close rank one matrix.
Note that because we normalize the final product, we can assume without loss of generality that 2(-) is the standard normal distribution (-; 0, rather than (-:: v).. Any scaling factor from y would be eliminated by the normalization. Thus, each entry of W is independently drawn from A/ (0, 1 1/m)), where my is the number columns W, as defined in Definition
For any d >> and t [Kt], will denote the random variable that is the tth singular value of W d=112 by 2,,, and the related quantity the Lyapunov exponents by 2 defined as follows:
1 2 d 2 log (sa-2.1)
The following Theorem provides concentration bounds on the deviation of the Lyapunov exponents of W 1:2:
Theorem There exist universal constants {14,, ) C1, 0g and es such that for all S S and any for which
C3T
ck
2
log
(d - 2)
r
it holds that
E mka)) 23 c1 exp (-o2k(d 2)s min {1, (s)))
P
t=p
where (s) is the function
1 min
(1, k=
rs
(s)
k min
(Thir: log(1/ne.r) f
2 krrk
for
--r
k
The
k
k
Proof. See Theorem 1.1 in Hanin and Paouris [46].
We now show that the above deviation estimate implies that with probability converging exponentially to 1, there a constant gap between the largest and second largest Lyapunov exponents.
Lemma 7. There exist constants Cs, > 0 independent of such that for all d 2
P P I Ad-2,1 - cs) 2 1 - exp (-cold 2))
Proof. Obviously Pk,1 Theorem we get that
Mk.2 0. We define Cg 1 14.1-M22 P4. Plugging in p
into
P (()--211 | 2 3) S ei exp (-ozk(d 2)s min (1, s/k, (s)))
for all s 2J log (ek). We take large enough such that cs 2 kı² log (ek) and take C5- Plugging in the definition tha,1, one may obtain that c2k(d - 2)s min {1, (x, = 2(d).
hence
P (1Aa-2.1 Mr, 2 cs) S Ci exp (-Q(d)) The argument be applied for p = 2 to conclude that
P (1Aa-2,2 Mk.2l 2 cs) C1 exp exp (-)(d))
Combining these two results by union bound and the triangle inequality yields the theorem.
38

---

The following Lemma implies that the spectrum of W is rapidly decaying, and in particular that it can be well approximated by rank one matrix. Lemma 8. Let E be the best rank approximation to W d-1:2- It holds with probability at least 1 exp (-cs (d 2)) that
[ d-122 1.2 ElLe
|
where Cs and Og are the same constants as in Lemmal 7
Proof. By the definition of Lyapunov exponents and Lemma have that with probability 2 1 - exp ca (d 2)), the following inequality holds for all t 2:
84-2,1 2
8d-2.1
exp ((d - 2)(22-211 - 2a-2.2) 2 (cs( 2))
8d-2.t
Sd-2.2
hence obtain that
d- FllF
V Di=
(x)-2.)
V(k - 1)(6a-22))
I V(k 11-xppepp (cs(d- 2))
El
8d-2,1
$d-211
as required.
We now show that not only W W2 but also the end-to-end matrix W W2 is approxi- mately rank one.
Lemma 9. There exist constants C11 C12, C13 >
independent of d such that with probability least
1 1- 212
C11 ((T) exp (-c1a(d-2)
the product of unnormalized matrices W
W44
Wii can be written as
W' = R
where O is rank matrix and
|R|| ||0|
(-cold -2)) 1) S de (k) exp
for the constant described in Lemma
Proof. We start from the decomposition obtained in Lemma namely the decomposition
W4-12= E (W)-1.2 E),
where has rank one and
[W 1:2 Elle
S /(K (1-k1) 1) exp (-cs -
| F
which holds with probability 1 - exp (-c6 - 2)). Plugging into W we obtain that
W' = WWWW W/ = W2 + W/2 (W - F.) WI
Note that BankWW"EW'S whenever W + 0. which holds with probability Now we can O WWWWW and f WC(W - E)W, It therefore suffices to upper bound the ratio
[W E)Wille
WWEWWll
We will separately give an upper bound
[| E)Will
and lower bound on
WWWWWl
39

---

that hold simultaneously with high probability. First, note that by Lemmas 24 and 25 large d, with probability exxp (-iod)) holds that
for a sufficiently
WWo(W2112 E)Will [ 1 EI
d- 1.2
S
Elp.
For the lower bound on ||]/EW]llp consider the SVD decompositions of W/ and Wi given by
W D.
d. (n:)
1=1
and
W ui (u
1=1
Likewise, as a rank one matrix, E can written as
E u
Invoking Lemma 26 with j= = we obtain that
W' [ (vî, un) (VE, ut)
It suffices to lower bound the absolute values of each of the terms in the product above. Note that by Lemma 27 all terms are independent. To lower bound of and of we apply Lemma 28 which yields that
p
2
1
d
d(P2)
and
C11
p
2 1
d(22)
where Cyi the constant from Lemma Lemma 29 which yields that
28
To lower bound (vi, uE>l and (VVE, ut)l
we invoke
p
(o),
uE)
2 d
2
C12
d
and
P (1gg
2 2 C12
where 61 is the constant from Lemma 29 Hence by the union bound, with probability least1
29 2 ou it holds that
a
WWFWWll 2 |F
Applying the union bound once more, we obtain that with probability at least
1 1- 2 C12
2 Cn1 exp(-co(d - 2)) 2 exp (-cind) d(ka)
d
the following holds:
S d V (k= 1 exp (-cs(d 2)) WW E)WillF
[W/FWllle
The proof follows by choosing Cr3 such that
exp (-c1a(d 2)) 2 exp(-co((d 2)) + 2exp (-cind)
Now that we' we've shown that W can be approximated by a rank one matrix with high probability tends to infinity, we ready show this for the normalized matrix W WW/|[W'|FF as well.
40

---

Lemma 10. Let
C(t) (W:: W = X + Y, rank(X) 1, |Y < <>)
Let Cai be the event that
W [
E C(7). Then any 7 > 0, if
7 d (k: ( 1.5 exp (cs (d 2)) 1
then
(C 2 2
911 exp (-c13(d -2)) d(
where C11, C12; and C13 are the same constants as in Lemma g
Proof. By Lemma with probability 2 11- 2 -
---4 exp (-c1s(d 22) it holds that the d(#a)
unnormalized matrix W can be written as
= =
where O has rank one and
| F 1
S d V(I:
exp eexp(eea (-es(d 2))
from which it follows that
| [
| |
|
d 1) 0.5 exp (cs (d (d- -
Consider the normalized matrix W" it holds that
W /||W"|| and its best rank one approximation denoted as X. Then,
W
|W'-OlF
||B|E < [d-6(k 1)-0.5 exp (cs 2)) 1 n.
- x
W
|
||
required.
B.2 W is Close to Rank One Then Low Training Loss Ensures Low Generalization Loss
In this appendix. show that if the RIP holds and learned matrix W is close enough to a rank one matrix, achieving low training loss ensures low generalization loss. This is formally stated the Lemma below.
Lemma 11. Suppose that the measurement matrices (Ad) satisfy the RIP of order (see Defini- tion I with a constant 5 (0, 1) and is defined as in Definition 7 Suppose that there exists some constant b > 0 such that for any matrix M E mmmm it holds that
[[((M)) S M1
Let M E R.m.m be a matrix such that
I((M) E.
and suppose that
M = E +
where rank(F) E) 1. If
|R]| < -I - 1)ve
1 1+b1I-
then
2c
|1M1 < 8"
41

---

Proof. By the definition of A it holds that
A(E)= - A(M) A(B),
therefore, using the triangle inequality obtain that
(l S [|A(())) [IA(R))E S SC Bl
By the RIP, the above results in
|| F - (1-6) 6)- [V
Finally, we obtain by the triangle inequality that
|| S (1 - The proof follows by plugging the assumption on || |R][ and rearranging.
b|| b|| rr + ||]
B.3 Lower Bounds on the Probability of Low Training Loss
In this Appendix, we show that the probability of attaining low training loss is bounded from below as d tends infinity. The argument is formally stated in the next Lemma.
Lemma 12. Suppose that W* has rank one and that [W*||r = 1. Then for any > O it holds that
(Cunia (W) E) 2 22(1)
as d + oc.
Proof. By the law of total probability we have that
P (Curin (W) < 2 P (Cuain (W) (W) < Can) P (Can))
where Ca. is as defined in Lemma 10
Additionally, By Lemma 10 it holds that
lim P P(Can) = d+oc
therefore suffices show that
P (Cuzin (W) < <c(Car) 2 ((1).
as d + oo. Observe that
P (Cramm (W)
< <e| 2 PPPPIN (IW w
b Can)
where b is the Lipschitz constant of A as defined in Lemma II Thus it suffices lower bound the
latter probability. By the symmetry of the Gaussian distribution (see Lemma (7) and the symmetry of the event Ca,y we have that for any the following holds for any rank one matrix with || F 1:
P [[W-wwIF
Ca - P (IW El? 5 g|Ca))
Now we set 7 e/2h and consider the M = M (26 d) matrices Fe,..., Fas from Lemma 30 the triangle inequality and the union bound have that
By
(Cant(aan Car)
1 1 P
P
U
W: IW Eiil < +) Can
1SiSM
Σ P ((we W ; !|W - E.ll2 5 Cam
ISiSM
Now again by symmetry we have
Σ P ((W:
w:
|W [W-- Falle < 5J
5) Can) = M -M.P ((w || - w0 < = CCr)
ISISM
Therefore, conclude that
P (fw: IW -W*13 < Car) M
required.
42

---

B.4 Proof of Sought-After Result
We are now ready to prove Theorem Let us define Cd.y as Lemma 10 For convenience we will denote by Ga.e the event that Lgaa (W) < ce, and by La the event that Luain (W) < c. By the law of
total probability it holds that
P PGa 0 LL Car))
P (GGa
P(La)
By Lemma if we set
VI - 81-2 - L)VE
1 1 1+bb1 1 8
where b is the Lipschitz constant of A, and
c 1-8"
then we obtain that
Ga La Can Lt n Ca.y
Hence,
P (Lanca
P P(C2,)
P P(aanCar) P(La)
La) 2
P(Ld)
P(La)
By Lemma
10 for large enough it holds that
P P(C,,)
< 2 - +
C11 d(ke) + exp (-cold - -2) O(1/d).
d
By Lemma 12
P (La) = ((1) and so
lim P (Ga = -1-0/111))
completing the proof.
C Increasing Width with Unspecified étrain
Theorem D requires the G&C training loss threshold Emain to be specified. Thus, the theorem does not rule out the possibility that for any width, sufficiently small Guain will lead G&C to attain good generalization. In this appendix, we state and prove a Dasult-Theorent Sacooremmber beloow- -that allows for an unspecified Grain- Theorem 9 imposes assumptions beyond those of Theorem (i) the depth of the matrix factorization is two; (ii) the prior distribution is generated by zero-centered Gaussian; (iii) the activation is linear; and (iv) the factorization is square, i.e., m m (though this latter assumption can easily be lifted). Moreover, Theorem considers a case in which the prior-induced probability distribution of the factorized matrix W (Equation (4) is shifted such that its mean is the ground truth matrix W The theorem establishes that even with this shift-which makes good generalization easier to attain-the posterior probability of low generalization loss conditioned on low training loss converges to the prior probability of low generalization loss.
Theorem 9. Let m. k E N and let Egen 0. Let W1 and W₂ be random matrices dimensions m, and k m, respectively. Assume that the entries of both W1 and W₂ are drawn independently from (O, 1). Consider the normalized product which is then centered around the ground truth matrix W*, i.e.:
1
:
W. + W*
Vmnk
Then, it holds that:
lim sup P (Cgen (W) Egen Larin (W) < Errain) P (Leen (W) < Egen) 0.
k-000 Smin 50
Proof. The proof is delivered by Appendices C.I to C.4 below. Appendix C.I establishes that locally
uniform convergence of densities implies convergence of probabilities. Appendix C.2 calculatess the characteristic function of the factorized matrix W. Appendix C.3 establissss that the conditional probabilities in Theorem can approximated by conditional probabilities of bounded sets. Finally, Appendix C.4 combines the above to prove the sought-after result.
43

---

C.1 Locally Uniform Convergence of Densities Implies Convergence of Probabilities
Convergence of probability measures in convex distance, as Appendix A is not sufficient for proving results which deal directly with the case of unspecified Eyain- This is so because the denominator and the numerator of the conditional probability can be arbitrarily small, and the convex distance gives additive approximation guarantee. To prove such result we will first have to prove that a stronger notion of convergence which we introduce this Appendix holds in our case.
Theorem 10. Suppose that Gn and G have continuous densities In and (with respect to Lebesgue dist.
measure) on Rmm Suppose that G, exists M Rm + I. such that
GG, the densities On are uniformly bounded, i.e., there
Vx E RR
sup
9n (x) S M(x) < 00.
eEN
and In also equicontinuous, i.e. for each then
there exists ò(e) such that if ||x - 8(e)
Vn e N,
(x)(x) - -n(y)) <c
Then
lim sup (gn(x) g(x)l + 0. xEX
Proof. This a slight adaptation of Lemma in Boos 15
Lemma 13. Let (fn be family of probability densities on Tm with respective characteristic functions (t)(t) (Definition) 17). Suppose that the L. -'-nnrmss of the characteristic functions weighted by ||t]], are uniformly bounded, i.e.,
Vn N,
1:p (t)ldt S M,
where M > O is a constant independent of Then the family is uniformly bounded and equicontinuous.
Proof. Note that the above bound implies that there also exists some M > 0 independent of n such that
Vn N, [ [ = M.
We employ the decomposition
ft (Pn(t)
/ ||t||ss1
/
(tn(t)
1P (t)(tt /1t1,21
The first summand uniformly bounded for all v. because the integrand is most (any characteristic function satisfies [o(t)] < TE( exp (i (t., X)) 1) and the domain has finite volume, whereas the second summand is upper bounded by
||tll2
Ipn(t) <
||tll2 (sn(t)) & M.
10
JRm
now follows by Lemma
32 that for any x E I
sup [x( < sup
[fr(y)) S (2
M.
nEN
nEN
remains to verify that {fn JnEN are equicontinuous. To see this, note that by Lemma 33
x vll2
/
|| vll2
(x) - fn(y)
Jmm ||t||| len(t)ldt _
M.
(2
(2T)
This bound uniform n and depends only on the distance ||x - -1122- For any given > 0, choose 5(c) (2x) Then for all |x y1l2 < 8(c), we have:
Vn N, [fa(x) fn(y)) <c.
Thus, the family (fahne is equicontinuous.
44

---

Lemma 14. Let (fnTNEN be sequence of probability density functions on R that converges uniformly to limit density f. Suppose that f is positive and smooth R For any bounded set K C T. such that K C B(0, R), the ratio of probabilities assigned by Sa and I to K converges to i.e.
lim SK (x(
n SK f(x)dx +1.
furthermore, this convergence is uniform over all subsets contained in B(0, R).
Proof. The positivity and smoothness of f imply that f is bounded below on bounded sets sets-indeed. K is contained in (0, R) which f is bounded from below. That is, there exists constant such that for all x E ((0, R) holds that
f(x) 2 c.
Since fn + f uniformly on R",, for any c > 0 there exists E N such that for all n 2 N and all K it holds that
[fa(x) f(x)) < < <
Thus, bound [n(x)
(1 (1-x)f(x)) S fm(xx) S (1 (1+x)
Integrating this inequality over K, we obtain
(1 c) / f(x))xx / fa(x)dx S
fa(x)dxx (1+ / f(x)dx.
Dividing through by SR (x))xx (which is strictly positive since f > 0 and is compact), we obtain that
JK fn(x)dx
1 1-
JK fxx)dx S1+c.
Taking the limit as n co, we conclude:
SK. f (x)dx
1.
JK f(x)dx
Furthermore, the above convergence does depend on itself but only on B(0, R)) hence the convergence is uniform over all subsets contained in B0, R).
C.2 Calculation of Characteristic Function
To apply the results the previous subsection, we need to calculate the characteristic function so that we can bound its integral in Lemma [6 We begin with the following formula.
Lemma 15. Given the random variable W Vin W,W2, where W1. W E R are matrices
with independent standard Gaussian entries, the characteristic function fa (T) EleAT.WW) for @ Rmmm is given by:
(a(T)
/dct (Im
TTT km
Proof. Since for any random variable X and constant c E IR we have
fax(T) = fx()
45

---

it suffices to compute the characteristic function without the have that
1
factor, which we denote by f. We
Vmk
7
(T.
W
T
W
W W
1
sp
PJ
W
w- (2)
(2)
T W
pm
Note that the variables
m
m Σ
(2)
To w
Pj
ip
independent for distinct values of p, hence
m
n12
(A
II
E
W
exp
W
(2)
Tiy
W sp
PJ
j=1
To evaluate the above expression we first fix (2 pj
i.e., we consider the expectation
m
m
(1) sp
E
exp
W PJ
Tí
( Note that a Gaussian random variable (being a linear combination of Gaussian random variables) with mean and covariance
Let Z E R. such that (Z) = En= Tiy ip
(Ez)px Ti).
where Tp Ti R" are the pth and (th rows of the matrix T. respectively. Therefore by the formula for the characteristic function of Gaussian variable (see Lemma 34 we obtain
Tú ((())
exp (-0.5 ( EzW,²))
E waa
exp
PJ
2m
where ((2) R is the vector whose jtth entry is Wr(2) It remains evaluate this expectation with respect to w:(2) well. Thus task reduces evaluating the expectation, with respect standard Gaussian, of a function of the form
exp 0..5 (W(), E2W(?))
where is is PSD. We now apply Lemma 35 to obtain the formula:
E E exp (-0.5 (w(2), Ez >
dett(Tn + Σ)
/ ddet Im TTT)
where the second equality uses the definition of Σ. follows that
k
ia(T)) = (Kk)
Video
(Im + TTT Tem
required.
46

---

We are now ready to show that the integrals of the characteristic functions fu are bounded, even if multiplied by ||T'r which will allow us to derive the equicontinuity of the corresponding densities.
Lemma 16. For fk defined in Lemma 15 it holds that
|e (fa(T) < oc.
sup KEN
Proof. Recall that by Lemma 15 above holds that
f |T ITll
||T||
dT.
Bm..
Rmm..
Vdet(Lm
rTI km
+
Using the change of variables to singular values and the Vandermonde determinant (Corollary 3), we may write the above
f I
dT
det Allet(Tn
In
+
TTT km
1/2
Cm
Σ o
(0 - of)da
Rm
I
V
of km
Isicssm
where Cm constant depending on the dimension m. Using the elementary bound
II
(o
-
of) -
2mm
Isicssm
1
we obtain the following upper incquality
1/2
(0 - of)do
RT
I1
+
Isicj$m
1/2
m
m
Cm
2 m
do
D
km
Now we apply the inequality v - b S Va + vb to the Frobenius norm term:
1/2
m
m
Σ
p
p=1
p=1
This separates the sum into individual terms:
k
m7 Σ
op
2 1)
do
RT
o?
km
Using Fubini's Theorem, the integral separates into a sum over m products of individual integrals:
b
(/+
EI
0,
2(m-i) 1)
do.
o 2(m
p)+
do
o2 kmm
o²
km
This decomposition allows the integral to be expressed as sum of m factorized integrals, each involving single variable.
47

---

We now perform for each 1 S i S m the change of variable and overall
which gives dz;
do Vkm
vkm
Mm
m7
7
77
2(m
1)
do
1
I 2(m p)+ dxp
+
x
1
x
p=1
k
k
m
m
Mm
(VI+
(v++
+
2(m-
drg
x
(1mmpp)+ p)+
dxp
11
p=1
where we have again absorbed the multiplicative dependence on m (which remains constant through- our analysis) into constant M,.-
We now perform another change variables x² = Yi. which gives 2r,dæ; = dy:- Overall for i + get factor of
m- dy:
Jo (1 (1+
and for i = a factor of
y4 m-P Pdy-
2 J
Up
remains examine the asymptotics of these expressions for large To do this we that by the definition of the Beta function (Definition 12), we have that
k
m it 2)
dy: B - i
(1+
y.)
2'
and by Lemma 37
we have
1 k B i
m i+ 1)
r (m - i r (m i 2))
2
where [()) is the Gamma function (Definition 10 By Lemma the above is order h (m--i++ (.. Summing these terms we get that
The same calculation gives for = p a term of order A 6-mm- p+ the product is of order
mim-11 +
k
Overall, the terms dependent on & cancel and each of the m integrals remain bounded as l oo, as required.
We summarize the above discussion by the following Lemma.
Lemma 17. Let W1, (W2)² E gm.. matrices with entries drawn independently from N 1), and let W
1 Wi W2. For any bounded set K B(0, R) C Rmm. we have
Vmk
P(W E K) +0000 P(Wia K)
lim
+1,
where Wia E BRm. is a matrix with entries drawn audependentlyfrei N N(0, L.), and furthermore this convergence is uniform all subsets K B(0, R).
Proof. By Theorem W converges as - oc Wia in total variation distance, and hence also in
distribution. Combining this with Lemmas 13 and 16 implies that the conditions of Theorem 10 are satisfied. Clearly the limiting density, being product of Gaussian densities, smooth and positive. Hence the conclusion is consequence of Lemmal
48

---

C.3 Approximation by Conditional Probabilities of Bounded Sets
We would ultimately like to bound conditional probabilities involving the events gen (W)) < Egen)
and (Ca)(WW)) < Guain Unfortunately, Lemma [4 applies only to bounded subsets of mm and the events above are unbounded. We will eircumvent this difficulty by intersecting genn (W) < Egen with [0, R), for sufficiently large R. and arguing that the approximations thus obtained are suffi- ciently precise. Specifically, we have the following Lemma.
Lemma 18. Let BR(V) be the event that random matrix V is contained in open ball of radius R around the origin
Bn(V) = (V E B(0, R)}
It holds that
lim sup R kEN.e>0
(BB((W) Curain < Errain) 1 0.
Proof. To see this, we first note that by the law of total probability
P ((B(WW)
Luain
<
Carain)
- =/o ggm.
P (BB(WW) Luain (W) <
Curain W2) f (W2 Luain (W) < Cuain) dW2.
where f(W2 Cuain (W) < Erain) is the conditional density of W2 given Carin Evain Now note that given W2 we have that W Vmk W, W2 is zero-centered Gaussian random variable (with covariance matrix which depends W2). Furthermore the set {W1 Luiin (W) < Erain] is convex and since V = it is also symmetric. Furthermore, the set ((0, R) is convex and symmetric for any R. We can therefore apply the Gaussian Correlation inequality (Lemmna 39) to conclude that
P(Bn(W) firai (W) < Crains W2) 2 P(Bn(W)) W2)
and therefore
P (BR(W) Luriio (W) < Emain)
((BR(W) W2) f (W2 Carin (W) Etrain) dW2. (8)
JRk.
Let W2, be the jth column of W2. Consider the following set:
i((e)
W2 Wi [m], ||2 S evk).
This set is convex and symmetric, so we can again apply the law of total probability by conditioning on Wi to get
P W/ E i((e) Lrmin (W) <
étrain
= =fo JRm.
P P(Wa E R((c) Lirain (W) Curain Wi) f (W1 Carin (W) < Crrain) dW1
Given Wi, the set {Lirain (W) Emann is again convex and symmetric, and W Wi W2 is zero-centered Gaussian, so again by the Gaussian Correlation inequality (Lemma
mi
39p
we have
P W2 R(()) (w) < Etrain
2 [ Jmm P p(Ws E P((c) W:) (W, Luain (W) < <vain) dW,
(W2 R(()) [(me (W, (W) < Eirain) dWi
P (w> n(c)).
where we have used the fact that the event W2 E it(c) is independent of Wi. Overall we therefore obtain that
P (W2 R((c) Liran (W) < Etrain) 2 P >Pwws R(e))
49

---

Now note that by Lemma 40 we can choose independent of such that P (w2 E B(()) is
arbitrarily close to 1. We have by Equation (8) that
P (BR(WW) (W) <
Erain)
IV
((BR(W) W2) f (W2 Luain < Erain) dW2.
R(e)
Now we claim that for R(n) sufficiently large, independent of both Grain and k, the integrand can be made to satisfy
P ((BRr) (W) W2) 2 1 -1
for any W2 E R(c). To do this, note that each entry of W is of the form
Vmk (1i,s W2,5)
for some i,j E [m]) where Wi.:: is the ith row of W1. Each row of W1 consists of k independent standard Gaussians, and by assumption W2,5 is vector of norm S evk. Thus have that the product is a Gaussian variable with zero mean and variance || 1| c²k. Thus after dividing by vikk we get a zero-centered Gaussian variable whose variance is independent of k. now follows by a union bound that we can select R := R(c, m) independent of k and Grain such that the matrix W will lie in (0,, R) with probability larger than 1 77 whenever W2 R((c). Overall we get that
W2 E R(c)) Cuain(W) Eurain P (BR(W) Curina (W) Crain) 2 7)
2 PP W2 E A(())
which can be made arbitrarily close 1 (by Lemma 40). as required.
We would also like to show that the approximation is precise with respect to the measure of the random matrix Wia which W converges as k - oo: Lemma 19.
Let Win be centered Gaussian matrix (Definition Sj. It holds that
P (Larii (Wia) < étrain O Egen (WgaaWiia)) ni) < Egen n BR(Wia)) P (Legen (Wia) < Cgen)
lim R-00
P (Luraia (Wna) < Craan Bx (wa)) Furthermore, this convergence is uniform with respect to Crains Cgen-
Proof. Since BR, (Cuain (W) Crain } and { (geen (W) < Egen) are convex and symmetric, we can
apply the Gaussian Correlation inequality (Lemma 33) to the numerator to obtain that for all R
P (Lmin Wina) < Crrain O Egen (Wia) < Egen n BIaWaaa))
P (Lurain < Craan (Waa)
P (rraiu (Wia) < Crain 0 Bre(Waa)) P
< (gen)
P (Curin (WWa) Eurin O BR(Waa))
=P (Cgen (Wia) < Egen).
hence the same inequality holds in the limit. On the other hand, by applying the Gaussian Correlation inequality to the denominator get
P (Lrnin (Wna) < Eunin n Cgen < Egen n BR(Wia))
(Lurain(Wial < Cirain n BB (Wiaa)
P Lrran (Wiia) < étrain n Lyenn Win)) < Egen O (naa)
P (Crrain (Win) < Caraia) P (Bu()))))
P. Cirai (Wia) < Crrin n Lyen (Wia) (gen)
P (Lrein (Wua) < Erriin) P (BR
P (urai BeauniWiit (Wia) < Cuain) P (Lgen
( (Waa) < Egen) (Crain (Wii)) ewain) P (BR (Wia)
P (L Win) < Egenn)
(BR(Wia))
50

---

where the second inequality follows by basic probability properties, and the penultimate equality follows by the independence of Lrain AraiinWiit (Wiia) Etrain and (gen(Win egen- The ratio (Wa))
(())(Wm))
tends to P geen (Wia) < (gen) as R + oo, hence the proof is complete.
C.4 Proof of Sought-After Result
We are now ready to prove Theorem a mean shift. First note that we have
We assume WLOG that W 0 as all claims are invariant to 9
lim pe Cgen) = P(Cgen (iia) <
Cgen)
k-+00
where Win is a centered Gaussian matrix (Definition 8 hence it suffices to show that
lim
sup P (fgge (W) < Egen Lurain (W) < Crain) - P (Egen (Wia) < Cgen) = 0.
R-
ruais 50
First, yh, 72 O. We can choose a radius == R(n, 9/2) > such that both
sup kER
[P(Bn(W) Lirain (W) < <miin) - 1| < m
and
P (Lurain CCrrin(Wii)) (Wia) Girain O Lgen! (Wii)= < Egen Bn(Waaa) P CCCee(Wing < (gen) < 12
P (Cuain (Waa) < Grain n BR (Waa)
Note that such an exists by Lemma 18 and Lemma
Then, we rewrite the conditional probability using the law of total probability by conditioning the events that W is within B(0, R) and its complement:
19
P (W) < Egen Cuain < Curaia)
P (Cgen (W)- < Egen Lrain (W) < Eurin Bx((W) (BB()) (W) < Evain)
+ P ( (W) Egen Lirain (W) < Emrin BR( ()) P (BR(W)C Lrmin (W) Ctrnin)
By the choice of R and the triangle inequality we have
P (Ceen (W) < Egen Lerain (W) < Errain)
P (W) < Egon Crrain(W] < Etrain BR BR(W))
< <m
Next, note that
Pl (Cgen(W) (W) < Egen Curin < Eraann BR(W))
P (Euaan (Wis)= Eprain n Egen (Wis) < Egen n (W
P (Curain (Wiia) < Euain O BR(Wia))
By Lemma 14, we can divide and multiply by the corresponding probabilities obtained with respect to the matrix Wid which converge to k > oc, and rewrite this ratio as
P (Caaii(W) Etrain 77 Egen (W) Egon n (R(W))
P (Crrinn < érrain 0 BR(())
P (Lrrrin (Wis) < Crain O Le (Wis) < Cgen n (B((Wa))) ar R) P (Lirain (W (iia) < Earain n (niWaa))
where (k: R)) - 1 as h: oo (uniformly in frmiin Egen). Again by the choice of R we have that
P (imin (W) < Crrin n Eyen(()) < Eyen n Bn)))) -P (C (Wia) < (gen) <
P (Cuain(W) (W) Crain BR(W))
Overall we obtain that for any érrain > 0
sup P (Cgen (W) < Egen
Liinn (W)= < Etrain)
k0000
< 2m + lim P (Lgen (W) < Egen
Lirain (W) < étriin BR(W) (W))
k0000
< 2m + 122 + P (Cgen (Wii) < Egen)
51

---

Since the above holds for all 1/, 722 > O we obtain that
lim sup P (Cgen < Egen Lraan (W) < Etrain) S (Ceen (Wid)) Egen)
k-+00 A symmetric argument applied to lim in P (Cgon (W) Egen Limin (W) < étrain) implies that
lim inl P (Lege(()) < Egen Lirain (W) Etrain) 2 P geen (Wia) < Egen)
80000
and hence
lim P (Leen(W) <
Lirain (W) < Gtrain)
= P (Cgen (Wina < (gen)
'gen
k-+00
Since the above holds uniformly in e > we conclude that
lim sup P (Ceen(W) Cgen Ltrain (W) < Crrin) P (Coon (W) < (gen) = 0
Eran 50
as required.
D Increasing Depth with Ground Truth Matrices of Higher Rank
Theorem 2 applies to cases where the ground truth matrix W has rank equal to one. In this appendix discuss an extension of Theorem to ground truth matrices of higher rank. A complete formalization of this extension left for future work.
Suppose the ground truth matrix W has arbitrary rank r and is non-degenerate, in the sense that its r non-zero singular values have similar orders of magnitude. Suppose the matrix factorization is square, i.e., its dimensions m and m' and its width & are all equal. Finally, suppose temporarily that the probability distribution over weight settings P()) does not include normalization, iee,, that PP()) generated by 2(.) without normalization (Definition) 3).
Hanin and Paouris 46) proved that, as the depth d of the matrix factorization tends to infinity, drawing its weight setting from P(-) leads the Lyapunov exponents of the factorized matrix W (Equation (4)
converge in distribution independent Gaussians with means 0 > μ1 > μ2 variances Od,- where the Lyapunov exponents of W are respectively defined as A; := (og( / for i E [m]. with 01 2 ... 2 Om 2 standing for the singular values of W. Assume that is large enough for the distribution of A1...., Am to be well approximated by its limit. In particular, assume that À (- p.dd where == (A1...., Am.. p = (P1,..., pm) and mm is an identity matrix.
> j'm and
Let j E [m]. We now estimate the probability that the leading singular values of W, i.e., 01.-..,0 .-. have similar orders magnitude. Per the definition of the Lyapumov exponents of W (namely, X; := log(a:)/d for i E [m]), this takes place when max;,F'(s]] [^; Aal S A for some small E R>o- By our assumption on the distribution of At,..., Ams the probability of the latter event is:
P( (maxx,yvbl Ahi -del - 2) [
3/2
-d dA.j
Je, 2rd-1
where A.j = (A Ag). Mij = (M1,..., (4) and:
(9) For large d, the integral above is dominated by the maximum of the integrand. More precisely, we may apply Laplace's principle and obtain:
C₁, = {Xag) maxx |^, 1
5/2
[
e -- dA. ss -idnffff 1A
C
2nd
We conclude that:
P(a....., have similar orders of magnitude) Rs ein [| [AA--1s(1++o())
(10)
Scaling W by positive factor does not change whether di.... TT have similar orders of magnitude. Therefore, Equation (10) carries over to the case where P(.) includes normalization. We hereinafter consider this case.
52

---

We would like to show that the probability of high generalization loss (Equation 3 conditioned on low training loss (Equation (2)) namely
(Ce (W) 2 étrain Limin (W) < Erriin) P(Cyen 2 Crrin Liaain (W) Crain
(11)
P (( (W) < (train)
diminishes as the depth increases. The probability low training loss-denominator in the right-hand side of Equation (IT) is lower bounded by the probability that W is close (in Frobenius norm) to the ground truth matrix W By isotropy and normalization, the latter probability should be proportional (identical up to multiplicatiie factors that do not depend d) to the probability that W has singular values akin to those of W*, i.e., to the probability that the r leading singular values of W have similar orders of magnitude while the following singular value is much smaller. We thus have:
P (faain (W) Grain)
Ω (P(o1...... have similar orders of magnitude while 0,-1 is much smaller))
Invoking Equation 110 with j r and with j = r + 1, we obtain:
P P(Curin (W) (rrain) = Ω (e ee - M1. +o( -d -d - |rr Mir +irezll(+o(d))
(12)
Moving to the numerator in the right-hand side of Equation due to the measurement matrices satisfying an RIP (Definition] T. high generalization loss (Gnge training loss (Cuain(W) < (rain) necessarily implies that the effective rank of W is higher than
(rain()) in conjunction with low
meaning its r + leading singular values have similar orders of magnitude. We thus have:
P(Cgen (W) euain Larin (anin(()) (W) Etrain)
o (P (P 0r+1 have similar orders of magnitude))
(13)
( d 160,11.4 [|Art1 - +o(d)
where we invoked Equation
10 with = +
Plugging Equations
and
13 into Equation yields:
P P(Cgen (W) 2 erain Crain (W) < Etrain)
d
||r M 11l +o(d)
(14)
0 dinfx: || -M,, +o(d)
|1r+1 po |l +l]+)
Recalling the definition of C, and C,+1, (Equation ()), ). as well as the fact that /41 > ... Pr+1- we have that for sufficiently small A:
inf infx EC |rr+1 M 1| > inf EC..a
||. ec.,A 11,
Together with Equation (14) this implies the desired result: the probability of high generalization loss conditioned on low training loss diminishes as the depth d increases.
E Auxiliary Theorems, Lemmas and Definitions
In this appendix we provide additional theorems, lemmas and definitions used throughout our proofs. Definition 8. Let W E Rm.m' be a random matrix. We say that W is a centered Gaussian matrix when the entries of W are drawn independently from N v) where v Ryo is some fixed variance.
Lemma 20. Let PP.)) be some distribution IR that is symmetric, i.e., if P()) then x P(-). Let f R > be some anti-symmetric function, i.e.,
Vx R. f(x) -f(-xx).
Then
[f(z)) 0. a>)())
53

---

Proof. Since P(-) is symmetric and is anti-symmetti it holds that
E = E 2xP(()
[f(=)]
E -x~P()
[ʃ(-x)]
=
E
[f(x)]
[/(-x)
P()
-w-P())
The claim follows by rearranging.
Lemma 21. Let f R + R be some function, A E Rm be some matrix and a E [mm'] be some index. Denote by E R. the standard basis vector with 1 in its entry and weros elsewhere. Then f(A)ea f(Aca)
where / applied matrix vector is shorthand for I applied each entry.
Proof. Observe that
f(An1)
f(Aim')
f(A)ea= =
Ca
[(Ami)
[(Amm))
f(A1a)
((Ama)
f(Ae,)
as required.
Definition 9. The total variational distance (TV distance) between two random variables X, Y on the same space Ω is defined as
TV(X,Y) sup |P(X E A) - P(Y E A)I
AÇQ
Lemma 22. For any two random variables X, on the same space St and any e >> holds that
TV(cX,cY)= = -TCCX,
Proof. By Definition it holds that
TV(X,Y) sup PP(X A) P(Y A)] Ago
For any A C Ω denote
= = fc- x/2 A}. Hence the above is equal to
sup
[P(cX A) P(cY e A)] TV(cX,
AgR
as required.
Theorem 11. Let [Wi]seta set of random matrices where for each j E [d], W, Rm
where ma+1 m, my = m' and m, k for all = 2..... ...... Suppose that for each j [d],
the matrix W, is centered Gaussian (Definition 8) with variance Let W = II W, and let W* E mm. be centered Gaussian matrix with variance m² Assume that ls 2 m. Then
L
m m
TV(W,W*) C(d C(d-CC() (1)
k
for some universal constant C > 0.
Proof. Theorem in Li and Woodruff [1] states that for random matrices Uy E "",,,,";;, .j e [d] where m4+1 m, = m' and my k,j = 2,... d with entries drawn independently from (0, 1), and random matrix U Rm.m' with entries drawn independently from (0, 1), it holds that
TV( II ,,)
U,) s C(d 1)
m
j=d Vk
54

---

1 for some universal constant C' such. Per Lemma 22 scaling A U and IT/=a vic Uy by factor
v
of Lk preserves the TV distance between the random variables. Hence. Vmn
TV Vm'
U, II U, j=d
1 U1)
= -i
TV(
U. II
U,) s c(d-1)) m ml
Vk
Vml
Vk
Vk.
j=d
The proof concludes by noting that W
II
U1 and W
U. Vm
Vml
Lemma 23. Let p Rd + R be some polynomial. The zero set of p.
(x E Rd pp(x)= 0}
either Rdd has Lebesgue measure zero.
Proof. See Caron and Traynor 20
Lemma 24. For any two matrices A E Rm and B E R.P it holds that
||B||E I ||
Proof. This is a clssical result that follows from the Cauchy-Schward inequality.
Lemma 25, For any centered gaussian matrix X E IR-9 (Definition & there exists a sufficiently large constant N E Rzo and constant ci0 Rz0 depdendent p, such that with probability at least 1 - e N it holds that
Proof. This follows from standard concentration inequalities for x2 random variables.
Lemma 26. Let A mm and C 128-9 be matrices with singular value decompositions
A
o
C= Lof (v9)
1=1
We denote the the rank summands of A and C as
X, x,=oAuÇ ( Y, y==0 of (v9)T
Let B E PR be rank one matrix of the form
= uBVB
Then for any i E [rali] E [rc] it holds that
||ABCI 2 1X,,Y,11
Proof. Substituting the singular value decompositions A and into the product, we obtain
rC Y
ABC
X₂
j=1
Expanding the product yields
TA TC ABC Σ X,BY,
i=1
To show that the terms X,BY, are mutually orthogonal, we compute the Frobenius inner product between distinct terms:
X, Tr ((X,BY))(XX,
(Xy (XxBY;)).
55

---

Using the definitions
Xi X1 o, (v/)", Y, of
the term B,B expands as
X,BY, of ((vA) (vzug) ui (v T uB) (vzu,) vi (u,t) (X,BY,) of ((vA)
Therefore,
Likewise,
By of (( us) (vzuf) u (vg)*
Substituting into the inner product and factoring out scalars obtain that
(X,BY, X;By)) of ((v!) T un) (vbug) ogoo ((v7) Tun) (vbuf) Tr (v9 (uft) (w:)) up (v9))
Using the cyclic property of trace,
Tr (u,") un (v)))) ((v)) ((u)) u
Since the singular vectors u vAl .uf vs are orthonormal,
(u u ba, (v T "vv'' v
Thus, the trace vanishes whenever * or j J'. Applying the Pythagorean theorem for the Frobenius norm,
P4 |ABC
|X,
Since every term in the sum is non-negative, for any i [ra]:j [rc] holds that
|BCC 2 IX,BY,
required.
Lemma 27. Let W E mR be a centered Gaussian matrix (Definition g with variance one. Consider the singular value decomposition (SVD) of W:
W = UTV
where U E mm and V E Ra. are orthogonal matrices, and E is diagonal matrix of singular values. Then, the first left singular vector in (the first column of ) and the first right singular vector Vi (the first column of V) are uniformly distributed the unit spheres Sm-1 and 5n-1, respectively.
Proof. Since W is an m, n matrix with independent standard normal entries, its distribution is invariant under orthogonal transformations. That is, for any orthogonal matrices Q ((m) and P E (n), the distribution of W satisfies
QWP W.
This follows from the fact that Gaussian matrix remains Gaussian after orthogonal transformations, and the standard normal distribution is rotationally invariant.
Consider the singular value decomposition
W = T.V.
The left singular vectors of W are the eigenvectors of WWT, and the right singular vectors the eigenvectors of W W. Since W is rotationally invariant, so the Gram matrix WWT which determines the left singular vectors. Specifically, for any fixed orthogonal matrix Q.
QWwTQ Q ww
56

---

This implies that the cigenvectors of WWT,, which form the columns of U, must be uniformly dis- tributed on the unit sphere STm-1 since no particular direction is preferred. Thus, u, Unif( ( [).
Similarly, considering W W, the right singular vectors (columns of V) are eigenvectors of W W. and by the same rotational invariance argument,
PWTwP' WTW
for any orthogonal matrix P E O(n). This implies that V1 Unif(S"-1).
The singular values 01.-.., mm,n(m,n) of W are independent of the singular vectors. This follows from standard results in random matrix theory, where the eigenvectors of Wishart matrix (which are the singular vectors of W) are independent of its eigenvalues (which correspond to the squared singular values of W). Thus, u₁ and Vi are independent from the singular values and remain uniformly distributed on their respective spheres.
Definition 10. The Gamma function, denoted by T(=) for = > O, is defined as:
((=) J e
Lemma 28. Let A E Rm. be centered Gaussian matrix (Definition) g with variance one. Then there exists constant C11 E Rg depdendent on m, n such that for any E (0,1) it holds that
(oi (A) S x) S 011x
where 01 (A) is the largest singular value of
Proof. Note that || a Chi Chi-squared random variable with mn degrees of freedom, i.e., holds that ||||] ~ X The density of for this distribution is given by
T E>0
[1;; mn)
mm
x
where [(.) is the Gamma function (Definition
10
Hence, we obtain that
P P( (I Sz)
f(s; mn)ds = O(r ))
Now note that for any matrix M E mm.. m it holds that
|M min n)
aM(2) >
thus
P < x²) S (IAII ()m 0n)
as required.
Lemma 29, Let Rn be some fixed unit vector, and let u be random vector uniformly distributed on the unit sphere 5m-1 in IR", Define = (u, v) as their inner product. Then there exists a constant C12 Ryo depdendent such that for any x [-1,]]
P( 7 < x) & C12 l
Proof. First note that by symmetry, we can assume WLOG that also uniformly distributed on the unit sphere. By Theorem in Cho 224, the probability density function of Z for any [-1, given by:
fz(2)
2
n
where r(.)) is the Gamma function (Definition 10.. particular, has bounded density supported on [-1, It follows that for any [-1,
[ [z(=)ds O(
P (| < x
required.
57

---

Lemma 30. For any m, & N and e E Ry0, there exists a collection of rank 1 matrices {E, "e he(M where M is depdendent on m, and e, such that for any rank matrix E E Rm with | there exists some index i [M] for which
Rm.")
E Eille <c..
Proof. Standard, see Vershynin [19
Definition 11. Let X be a random vector taking values in RM, The characteristic function of X is the function yxx I -> C defined for any IR.m by:
x x (e(tt.))
where (t, X) denotes the standard inner product IR...
Lemma 31. Let be a random vector taking values in R and let xx its characteristic function (Definition 77). If X has a probability density function fx(x), then it can be recovered using the following inversion formula
(2x)m / -xtxx)
1
fx(x)
Proof. Standard, see Zitkovic 140
Lemma 32. Let f R - 0, xo) be probability density function with characteristic function <t(t). The supremum of J. denoted by |I == suPxER? [x()), is bounded by the L -n-ormm of its characteristic function. Specifically,
|l S (2m)) / lo((t)dt.
Proof. By the Fourier inversion formula for probability density function on IR" (Lemma 31> [
(2 f(x)
1
((txxx) (t)dtt
Taking the absolute value, get:
[f(x)] S (2x)
e i(t.x) lt(t)ldt. mmm
Since |e -i(t,x)) for all R", the latter simplifies to:
[((x) S (2 / le(t))dt.
1
Taking the supremum over all R". we obtain:
/ le(())at
Ilf S (2 Rm
as required.
Lemma 33. Let X be random vector in R with density function Jxx (x() and characteristic function dx (t). For any two points x, E Te. the difference between their densities is bounded by:
6-yll2
[xx(x) - fx(x)]
(t)lllx(())ttt.
(2x))
J
Proof. From the inversion formula for the density function (Lemma 31) write:
fx(x) fx(x) (2 [ (e (e-i(t.x) e- - Øx (t)dt.
1
58

---

By factoring out the exponentials:
(t,x) k(ty)) = (((.)) (1
Taking absolute values and using the bound:
el(txxxx s -tt,y 1x)--111 x)
resulting in
lfx(x) - fx(y)) $ (2m) / ( - x) (t)xxt)
Finally, applying the Cauchy-Schwerd inequality we obtain that
(t,y - x) |||l|||| yl12.
which implies that
1x y-yll12 / [tt|2|/x(())
(xx fx(v) 1
(2 Jmm
as required.
Lemma 34. Let X ~ (O, E) be a zero-centered Gaussian random vector in Ih" with covariance matrix Σ E R.m.m, The characteristic function of X is given for any Tpm by:
(x((t) exp (-2 (t. 21)
Proof. Standard, see Vershynin 120
Lemma 35. Let X NO, Im) be a standard Gaussian random vector in R", and let be a positive semi-definite (PSD) matrix. It holds that
R 1m,
X AX
v det (Im + 2A)
Proof. The expectation is given by:
X AX
= /f -xx 1
(2 C fx dxc
e
Jmm
Combine the exponential terms:
Ax xxxxx fx (2A+tl)))
Thus,
XT AX
e (2A+tmmm)
e
(2
Rm
This is the Gaussian integral over mm for a quadratic form. Using the standard result for multivariate Gaussian integrals
(2m))//2
--1x" 1xx Bx fxxxx
mmm
/det(B)
where B is a PSD matrix. Observing that the matrix B = Im + 2A is PSD, we conclude that
E e
x
AX
[d + 2A)
required.
59

---

be function that depends only on the singular values of matrix X Rm.. Then, the integral of f over the space Imm matrices can expressed as an integral over the singular values as follows:
Lemma 36. Let f Rm. +
f f(X)dX =
=Cm Cm
f(a) do
20m222-22mm20
where:
Cm constant depending on the dimension m.
A(a)) = Iissicsm(of -o3) is the Vandermonde determinant of the squared singular values.
do represents the differential volume element over the singular values.
Proof. Consider the singular value decomposition (SVD) of X:
X = -UVV
where U, V E ((m) are orthogonal matrices, and Σ diag(o 01, , is a diagonal matrix containing the singular values a; of X.
The differential volume element dXX in the space of m, m matrices can be decomposed into the product of volume elements corresponding to U, E, and V, along with the Jacobian determinant of the transformation:
dX dU))ddddd
where J(E) the Jacobian determinant associated with the change of variables from X (U,
For function f that depends only on the singular values, the integral over the orthogonal matrices U and V contribute to the constant Cm. allowing to focus the integral over the singular values. The Jacobian determinant (2) for the transformation involving singular values the space of m, m matrices is given by:
(( A(o)²
where A(a) IIsiessmlo? 0f) (see Rennie [99]).
Therefore, the integral over the space of m, m matrices can be rewritten as:
Jmm. [(X)XX -Cm 20m20
f(a) A(or)
where da is the measure on the singular values.
Corollary Consider the function f(X) = ||
where X E Rmmm Using
det X
the change of variables to singular values (Lemma 36
1
gmm. |
dX
del
X (I+
km
1/2
Cm I
m
Aoo
2012022 200222200mm
Tem
where:
*X|| (Em o,) 1/2 is the Frobenius norm X.
60

---

det (I+
XIX)
V [
(1+
km
km
A(o) Ilgieess (of 03) is the Vandermonde determinant of the squared singular
values.
This reduces the integral to one over the singular values 02. mm Definition 12. The Beta function, denoted by (Ix, v) for æ, >> O, is defined as:
1
B(r, v)
(1+ 1)++o dt.
Lemma 37. For any x, y > it holds that
T(x)T(v)
B(r,y)
T(x +
Proof. Standard, see Davis 31
Lemma 38. For large 2, the ratio of the Gamma function evaluated z and z cfo any constant satisfies:
F' + c)
2 as + 00. 00.
r(2)
Proof.
Using Stirling's approximation for the Gamma function:
[(2) 1//2 as 2 00.
we compute the ratio:
T(= [(2)
V2T(z + c)=tt-1122 (x+c)
22T=== 1/2c-
Simplify the terms:
+c)
(= (=+c)
T(2)
22-1/2 1/2
Taking the dominant term for large we approximate
80:
[( c
T(=)
as required.
Lemma 39. Let & denote Gaussian measure on Rnd with mean zero and covariance matrix Σ. For
any two closed, symmetric, convex subsets A, B C RR, the Gaussian Correlation Inequality (GCI) states:
Φ(An B) 2 (AA)(BB.
Proof. See Latala and Matlak [67]
Lemma 40. For all 8 > O, there exists a constant c(ō) such that with probability at least 8, the norm of an L-dimensional standard Gaussian vector NO, Ir.) satisfies:
|X|| S (
Proof. See Vershynin 118
61

---

F Theorem 3.3 From Soltanolkotabi et al. [106]
Proposition D restates Theorem 3.3 from Soltanolkotabi et al. 106 using O- and O-notations. For completeness, Proposition | below restates the theorem without these notations.
Proposition 4 (restatement of Theorem 3.3 from [106), without O- and O-notations). There exist universal constants C1,..., , C10 250 with which the following holds. Suppose the activation o(-)
is linear (i.e., (()) a for all a IR), and the depth d equals two. Let E Ryo be the condition number of W*. Let Q(-) be zero-centered Gaussian probability distribution, i.e. 2(-) 00, with variance
Vr 0 O<NS k9.5 (max/m (m + m', k))* C2k² V max m + m' k}
Vk
(recall that r is the rank of the ground truth matrix W whose dimensions are m and m'), Let P(-) be the probability distribution over weight settings that is generated by Q(-) (Definition 3 Assume the meusurement matrices (A,);= satisfy an RIP (Definition ! of order + with constant 5 E (0, min 1, cn/(n3 (r)))) Consider minimization of the training loss Luain (-) via gradient descent
(Equation 7 with initialization drawn from P(-) and step size
C5
0 O<TS
W In
Av IVI(km)) volvk- (F-1)
Then, there exists some T E N which satisfies
Av Av2(km 1//41W" 1F volVk- 11-
C6 In
T T
mi (W*)
such that for any width ic of the matrix factorization, after T iterations of gradient descent, with probability at least 1 C7 exp(-cak) + 6g k-r+1 over its initialization, the generalization loss Egen (-)
no more than c1ol 7/10 /3/10 /kkm))
G Further Experiments
Section 5 corroborates our theory by empirically demonstrating that in matrix factorization (Sec- tion (.3). the generalization attained by G&C (Section 3.5) deteriorates width increases and improves as depth increases, whereas gradient descent (Section 3.4) attains good generalization throughout. This appendix reports further experiments.
Figures and
respectively extend Figures and to account for gradient descent with momentum.
Figures and
6
respectively extend Figures and account for a ground truth matrix of rank two
Figures and 8 respectively extend Figures and to account for G&C with a Kaiming Uniform
prior distribution. Figures and T0 respectively extend Figures [nd 2 to special case where the measurement matrices are indicator matrices (meaning each holds one in a single entry and zeros elsewhere), leading to what is known as low rank matrix completion problem that has been studied extensively [144] [42 [46] [41
148 [43]. Figure exxtends Figure[]te account for G&C with a prior distribution that does not include normalization (Definition 33). Figure 12 establishes that our large width results are robust to the exact choice of érain- Finally, Figure shows that the trends displayed in Figure namely improved performance of continue for larger values of depth.
H Experimental Details
In this appendix, we provide experimental details omitted from Section 5 and Appendix G Code for reproducing all demonstrations nn nn-gd- an-gd-gen-- mf All experiments were implemented using PyTorch [45] and carried out on a single Nvidia RTX A6000 GPU.
be found in httts:///iithbb Comm/ooniSi Slutzky98/
Ground truth matrix. In all experiments the ground truth matrices were generated via the following procedure. First, two matrices U E Rmm. and V E Rr.m were generated by independently drawing
double descent like phenomenon namely (small) spike in generalization loss which is then reversed model size is further increased, is observed for gradient descent (but not for G&C) with the Leaky ReLU activation. We leave investigating this phenomenon for future work.
*We note that in Figures 1 and
62

---

Generallzation Lass
Liner
0.20
Tanh
0.15
Leaky ReLU
0.15
GD
0.10
0.05
100
200
300
100 200
300
400
500
600
100
200
400
5.0
600
Wilth
Width
Width
Figure line with our theory (Section 4.2) . as width a matrix factorization increases, the generalization attaiind by G&C deteriorates, to the point of being no better chance, i.e., no hetter than generalization attained by randomly drawing single weight setting from the prior distribution while disregarding the training data. This figure adheres to the caption of Figure except that employ gradient descent with momentum coefficient 0.9 [91]. For further details Appendix H
Generalizaton Lass
Linear
Tanh
Leaky ReLU
0.08
0.08
0.075
0.06
GD
0.06
0.050
Prior
0.02
0.02
0.025
0.00
0.00
0.000
10
Dopth
Figure 4: In line with theory (Section 4.3 as the depth of matrix factorization increases, the generalization attained by G&C improves, drawing closer that of gradient descent. This figure adheres to the caption of Figure 2 except that we employ gradient descent with a momentum coefficient of 0.9 [9] For further details see Appendix
each of their entries from the standard Gaussian distribution ([; 1). Here stands for the desired ground truth matrix rank. Then, the ground truth matrix was set as
W b
UV.
I
where b stands for the desired ground truth matrix norm. This procedure ensured that W had rank and norm In the experiments reported in F the ground truth matrices were of rank two and norm one. In the rest of the experiments, the ground truth matrices were of rank one and norm one.
Mcasurement matrices. In all experiments, the training measurement matrices were generated by independently drawing each of their entries from the standard Gaussian distribution A (-; 0, 1), and then normalizing each matrix to have norm one. For each set of training measurements, the corre- process and taking the
sponding orthonormal basis B generated by performing the components which were not spanned by the original set of measurements. In the experiments reported in Figures 5 and 6 the amount of training measurements was 22. In the rest of the experiments the amount of training measurements was 15.
G&C optimization. A G&C sample consisted of a drawing of the weight matrices W ...... Wa and computation of the factorization W (Equation (4). the training loss (Equation (5) of the given factorization is lower than érain then the sample considered successful. Table TableeTrep reports the value of Erain used in each experiment.
For each trial-that is, for each random draw of the ground truth and measurement matrices-th G&C algorithm was executed by drawing num_ num_samples samples and averaging the generalization losses of all successful samples. Table reports the value of num_samples used in each experiment.
To efficiently execute the G&C algorithm, the following batched implementation was used, Given sample batch size bs. for each layer j E [d], the layer's weight matrices W, R..51..73 were: (i) drawn parallel as a tensor of dimensions (bs, m my): (ii) multiplied in parallel with the factorizations produced in the previous layer via the bmm() function of PyTorch, and; (ūū)) applied the activation function elementwise. The weights of the jth layer were drawn with independent entries
from either (1; 0, or u(; 11 and then scaled by /mj. This procedure was performed until
63

---

Generalization Loss
Linerr
Tanhh
Leakyy ReLU
0.15
GD
0.10
0.10
0.1
0.05
0.05
0.00
100
200
300
400
100
200
300 400
500
600
100
200
300
400
500
600
Wilth
Width
Width
Figure line with our theory (Section[42) as width a matrix factorization increases, the generalization attained by G&C deteriorates, to the point of being no better chance, i.e., no hetter than generalization attained by randomly drawing single weight setting from the prior distribution while disregarding the training data. In contrast, gradient descent attains good generalization across all widths. This figure adheres to the caption of Figure[] except that the ground truth matrix had rank two and the training data size details see Appendix
22. For further
Generalization Lass
Linear
Tanh
Leaky ReLU
GD
0.06
0.06
0.05
0.04
0.04
0.04
0.02
0.02
0.02
0.00
Depth
Depth
Depth
Figure 6: In line with our theory (Section 4.3 as the depth of a matrix factorization increases, the generalization attained by G&C improves. drawing closer to that of gradient descent. This figure adheres to the caption of Figure except that the ground truth matrix had rank and the training data size with larger depths, the generalization attained by gradient descent as good is with smaller depths For further details see Appendix H
22. We note that
total of iimmmmmmaaaaaaaa samples samples accumulated. In experiments where the final factorizations were normalized, a softening constant size 10-6 was added to the denominator.
GD optimization. In all of the experiments we trained gradient descent using the empirical sum of squared errors as loss function and optimized over full batches.
All weights matrices were initialized as follows. First, for each layer j E [d]. the layer's weight matrix W, E R 11. was drawn with independent entries from (:: 111.1///././//mmmm//m///. /my) (this is the default Py Torch initialization). Next, in order to facilitate near-zero initialization, all weight matrices were further scaled by a scalar init init_scale.
scale. init init_nccilll scale was set to 10-3 3 in all the experiments of Figures 1 3 and 12 Table reports the values of init_ used in the and 13
experiments of Figures
In order to facilitate more efficient experimentation, optimized using gradient descent with an adaptive learning rate scheme, where at each iteration a base learning rate divided by the square root of exponential moving average of squared gradient norms (see appendix D.2 in Razin et al. [97] for more details). We used a weighted average coefficient a = 0.99 and softening constant of 10 10-6 Note that only the learning rate (step size) is affected by this scheme, not the direction of movement. Comparisons between the adaptive scheme and optimization with fixed learning rate showed significant difference in terms of the dynamics, while run times of the former considerably shorter. The base learning rate was set to 10-4 in all the experiments of Figures Tabccffse the base learning rates used in the experiments of Figures specifies the number of epochs used in each experiment.
5
and 12 Table 4 specifies
4 6
and
13 Table 5
"We examined weight settings found by gradient descent, and observed that with larger depths. the factorized matrix W (Equation 4) had effective rank [147] lower than that of the ground truth matrix W This aligns with the conventional wisdom by which adding layers a matrix factorization leads gradient descent to have stronger implicit bias towards low rank (6, 25). The fact that it was possible to fit the training data with an effective rank lower than that of the ground truth matrix, is an artifact of the training data size being limited in order ensure reasonable runtime by G&C.
64

---

General Innaralizttion Lass
Lnaky ReLU
0.00
GD
0.04
0.02
0.02
0.02
0.00
0.00
100
200
300
400
500
600
100
200
300
400
500
800
100
200
310
400
500
860
W. dtth
Width
Width
Figure 7: In line with theory (Section[4.) . as the width of matrix factorization increases, the generalization generalization
attained by G&C deteriorates, to the point of being better chance, iee, better attained by randomly drawing single weight setting from the prior distribution while disregarding the training data. This figure adheres to the caption of Figure except that the prior distribution of G&C was Kaiming Uniform. For further details Appendix H
Generalization Loss
Linear
Tanh
Leaky ReLU
0.05
G&C
0.075
0.06
Prior
0.06
0.050
0.04
0.02
0.02
0.025
0.00
0.00
0.000
10
Depth
Depth
Depth
Figure 8: In line with theory (Section 4.3 attained by G&C improves. drawing closer that of gradient descent. This figure adheres to the caption Figure except that the prior distribution of G&C was Kaiming Uniform. For further details see Appendix
the depth of matrix factorization increases, the generalization
Goneralization Loss
near
Tanh
0.15
Leaky ReLU
0.15
0.10
G&C
0.10
0.1
Prior
0.05
0.55
0.0
0.00
0.00
100
200
300
400
500
600
100
200
300
400
500
6.0
100
200
300
400
500
600
Width
Width
Width
Figure 9: In line with our theory (Section[4.2 as the width of a matrix factorization increases, the generalization attained by G&C deteriorates, to the point of being better than chance, i.c., better than the generalization attained by randomly drawing single weight setting from the prior distribution while disregarding the training data. figure adheres to the caption Figure except that measurement matrices were indicator matrices (meaning each held one in a single entry and zeros elsewhere), leading to a low rank matrix completion problem. For further details see Appendix
Generalization Loss
Linear
Tanh
Leaky ReLu
0.075
0.06
GD
0.06
0.04
0.04
0.050
0.02
0.025
0.00
0.00
0.000
Depth 10
10
10
Dopth
Dopth
Figure 10: In line with our theory (Section 4.3 as the depth of matrix factorization increases, the generalization attained by G&C improves, drawing closer that of gradient descent. This figure adheres the caption of Figure except that measurement matrices were indicator matrices (meaning each held one single entry and zeros elsewhere), leading to a low rank matrix completion problem. For further details see Appendix
Table 1: Training error Eiran used in the experiments of Figures
Setting
étrain
Figures and
0.02
Figures and 13
0.0035
Figures and
0.01
Figure
0.025, 0.03
65

---

Generalization Loss
0.2
0.15
GD
G&C
0.10
0.1-
0.05
0.0
0.00
10
Depth 10
Depth
Figure 11: In line with theory (Section 4.3 the depth of matrix factorization increases, the generalization attained by G&C improves, drawing closer that of gradient descent. This figure adheres to the caption of Figure except for the following differences: (i) the prior distribution of G&C did not include normalization; and (ii) experiments with Leaky ReLU activation were omitted (because without normalization the number of draws it required from G&C was computationally prohibitive). We note that with tanh activation, the generalization attained by drawing single weight setting from the prior distribution (while disregarding the training data) improves as depth increases. This results from factorized matrix (Equation (4) approaching the zero matrix, whose generalization loss is greater than that attainable by G&C. For further details see Appendix
Strain = 0.025
Genoralization Loss
Linear
0.20
0.15
Leaky
0.15
0.10
0.10
Pnor
0.55
0.00
0.03
Generalization Loss
Linear
0.20
Tanh
0.15
Loakyy ReLU
0.2
GD
0.1
0.0
0.00
100
200
300
400
500
600
100
200
300
400
500
600
100
200
300
400
5.00
800
Width
Width
Width
Figure 12: In line with our thenry (Section attained by G&C deteriorates, to the point of being better chance, i.e. better attained by randomly drawing single weight setting from the prior distribution while disregarding the training data. The above figures demonstrate that the results in Figure Jare robust to the choice of emain. Here we show Eurin 0.025 and fuain 0.03 to complement Emain 0.02 shown in the main text. We see that the qualitative bchavior is the same.
the width of matrix factorization increases, the generalization
generalization
Generalizatton Loss
Linear
Tanh
Loaky ReLl
0.08
0.08
0.06
GD
0.04
G&C
0.04
0.02
0.02
0.00
0.00
0.000
10
15
20
5
10
20
10
20
Depth
Depth
Depth
Figure 13: In line with our theory (Section[43) as the depth of a matrix factorization increases, the generalization attained by G&C improves, drawing closer that of gradient descent. This figure adheres to the caption of Figure except that plot results for G&C up depth 20 as opposed to 10. Results for gradient descent omitted larger depths because running it became computationally prohibitive. Note that our theory does not imply that as the depth tends to infinity the generalization loss of G&C will tend to zero, but rather that the probability that it is smaller than some constant times eman will tend to 1. For further details see Appendix H
66

---

Table 2: Number of G&C samples used in the experiments of Figures
to
Setting
num Stum_samples
Figures and
108
Figures
and
109
Figure
5 X 10
Table 3: Gradient descent initialization scale used in the experiments of Figures (increasing depth). The first three columns (left) specify the experiment (setting, activation Tunction and associated depths d), and the last column specifies value of init_scale used.
4 6 g
10
and 13
Setting
Activation
init_scale
Figures
10
and
13
Linear, Tanh, Leaky ReLU
2, 2,3,4 4
0.001
Figures
and
13
Linear, Tanh
5, 7,8
0.1
Figures
and
13
Linear, Tanh
9. 10
0.2
Figures
and
13
Leaky ReLU
5
0.03
Figures
and
13
Leaky ReLU
6,7
0.1
Figures
and
13
Leaky ReLU
8,9
0.2
Figures
and
13
Leaky ReLU
10
0.8
Table 4: Gradient descent base learning rate used in the experiments of Figures 4 (increasing depth). The first three columns (left) specify the experiment (setting, activation function and associated depths d), the column specifies the base learning rate n used.
6
8
10
and 13
Setting
Activation
d
Figures
10
11
and
13
Linear, Tanh
2, ..... 10 0.01
Figures
and
13
Leaky ReLU
2,3,4
0.01
Figures
0
TO
and
B
Leaky ReLU
5,..., 10
0.1
Table 5: Number of gradient descent epochs used in the experiments of Figures 1o to 13
The first two columns
(left) specify the experiment (setting and activation functions), and the last column specifies the number of epochs used.
Setting
Activation
Number of Epochs
Figures
12
Linear, Tanh, Leaky ReLU
100000
Figures
and
13
Linear, Tanh
20000
Figure
Linear, Tanh
50000
Figures 10
and 13
Leaky ReLU
50000
67


Reviews:
[{"review_id": "itb4PKVgEX", "reviewer": "Reviewer_tfAT", "summary": "This paper studies whether gradient descent is necessary for neural networks to generalise well, using matrix factorisation as a simplified and analytically tractable setting. The authors compare the generalisation performance of gradient descent and a non-optimised alternative known as Guess & Check (G&C). They analyse how generalisation under G&C behaves as network width and depth vary. Their theoretical results suggest that generalisation under G&C deteriorates with increasing width but improves with increasing depth, in contrast to gradient descent, which performs consistently well. These theoretical findings are complemented by empirical experiments within the matrix factorisation framework. The study aims to shed light on the conditions under which gradient descent may — or may not — be necessary for generalisation.", "questions": "**1)** In Figure 1c, a double descent behaviour [Belkin et al., 2018] appears to emerge around width $\\approx 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?\n\n**2)** 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].\n\n**3)** 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 \\to \\infty$.\n\n**4)** 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?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Quality**\n\nThe paper is solid and presents rigorous theoretical analyses under well-defined assumptions. The authors provide formal results characterising the generalisation performance of G&C as a function of network width and depth. The empirical results are consistent with the theoretical predictions (see question regarding the dimensionality). Naturally, as acknowledged by the authors, the results are derived in a very specific setting (matrix factorisation with specific activations and priors), and their relevance to more realistic networks remains to be established in this context. Since matrix factorisation is a traditional playground in theoretical analysis, its use is well motivated. 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.\n\n\n**Clarity**\n\nThe paper is generally well written and well structured. The motivation is clear, and the presentation of results is good.\n\n\n**Significance**\n\nThe work addresses a timely and important question raised by recent publications: whether gradient-based optimisation is necessary for generalisation. While the matrix factorisation setting is simplified, it serves as a common theoretical proxy. The observed contrast between width and depth is interesting, though its underlying cause still needs to be better understood.\n\n\n**Originality**\n\nThe paper offers new theoretical contributions regarding the limitations and capabilities of G&C, particularly the contrasting behaviour under increasing width and depth. This perspective contributes to the ongoing discussion around the volume hypothesis and the role of implicit bias in generalisation.", "was_revised": true, "final_justification": "I thank the authors for their careful and detailed rebuttal addressing all questions and remarks. I maintain my recommendation for acceptance.", "rebuttal": "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.\n\n>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?\n\nThank 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.\n\n>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]\n\nOur 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!\n\n>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$.\n\nDue 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).\n\nNote that Theorem 1 applies to finite width settings, not only the infinite width case.\n\n>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?\n\nOur 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.\n\n>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\n\nThe 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.\n\n---\n**References**\n\n[1] Chiang et al. “Loss Landscapes are All You Need: Neural Network Generalization Can Be Explained Without the Implicit Bias of Gradient Descent.”\n\n[2] Peleg and Hein. “Bias of Stochastic Gradient Descent or the Architecture: Disentangling the Effects of Overparameterization of Neural Networks.”"}, {"review_id": "h3FmNoIi53", "reviewer": "Reviewer_a89s", "summary": "The authors investigate the generalization behavior of the Guess & Check (G&C) algorithm in the context of matrix factorization problems, both with and without activation functions. The G&C algorithm operates by sampling parameters from a prior distribution without any gradient-based training, and selecting those that yield sufficiently low training loss. The paper presents two main theoretical findings. First, under certain assumptions, as the network width tends to infinity, the generalization performance of the G&C algorithm degrades to the level of random parameter selection. Second, under specific rank-1 assumption, increasing the network depth can lead to improved generalization performance of the G&C algorithm. The author uses this to illustrate whether gradient-based algorithms are necessary for the generalization of neural networks. The conclusion is that there is no simple answer and specific analysis is required for specific situations.", "questions": "1. 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? Could the authors clarify whether this limitation is inherent to their theoretical framework, or if it is possible to extend the results to more general supervised learning settings?\n\n2. According to the restatement of Proposition 1, is it implied that the generalization loss tends to zero as the width $k \\to \\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.\n\n3. 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.\n\n4. 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.\n\n4. The experimental section lacks sufficient persuasive power. According to the authors’ theoretical claims:\n   - 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.\n   - As depth increases, the generalization error of the G&C algorithm should follow a straight line with slope $-1$ in a log-log plot.\n\n   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.\n\n\nOther Minor Comments:\n\n1. Line 26: Reference [102] appears to be cited twice; please check for redundancy.\n\n2. The notation for sets is somewhat confusing. In Line 142, parentheses 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.", "limitations": "In addition to the theoretical assumptions and settings discussed by the authors, the limited empirical validation also constitutes a potential limitation of the paper.", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 1, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n1. The volume hypothesis that the author is trying to solve seems to be a very interesting problem. Generalization, as the most fundamental ability of neural networks, is guaranteed by the optimization algorithm or by the architecture itself, which is a question worth studying.\n\n2. The authors provide a reasonably comprehensive review of relevant literature and appropriately cite several classical and foundational results in the field.\n\n3. The conclusions that the author wants to convey are relatively clear, and the overall writing logic of the paper is relatively clear.\n\n4. I checked some theoretical details, and the author's theoretical results are relatively solid. The derivations build upon well-established statistical principles, and the arguments are generally rigorous.\n\n**Weakness**\n\n1. 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. For instance, it is a well-known result that infinitely wide neural networks converge to Gaussian processes. The theoretical derivations in the current paper seem to build directly upon such existing limit results to obtain implications for matrix sensing problems. In this context, the derivation of the limiting distribution itself is arguably more fundamental, and the additional insights provided in this work seem rather limited in terms of novelty. I think it would be a greater theoretical contribution if the authors could provide a generalization analysis of the G&C algorithm under finite width/depth (this setting in Chiang et al.).\n\n2. 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'$. Theorem 1 essentially states that in the infinite-width limit, under undersampling, the training and test data become statistically independent—i.e., no generalization is possible. However, this conclusion heavily relies on the special structure of matrix sensing, particularly the inner-product structure of the measurement operator. I am skeptical whether this result would hold in more general settings, such as learning a target function using a fully connected neural network (which allows unlimited number of samples). In such cases, the training and test are unlikely to be completely independent.\n\n3. 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 \\to \\infty$. The authors seem to use it to illustrate the generalization guarantee of GD when the width tends to infinity. I think the conditions of these two theorems are completely different, so the two cannot be compared to show the generalization of GD is guaranteed, and the generalization of G \\& C is weaker.\n\n4. Although the authors cite a fairly comprehensive literature, there are some important and related works that are not mentioned. For example, [1, 2] discovered the frequency principle (or spectral bias) of the general neural network structure itself. Because of the smoothness of the activation function, the network itself will learn from low frequency to high frequency, and thus has good generalization for the actual data distribution (often low frequency). In addition, more specifically, for matrix factorization models, [3] systematically studied the implicit regularization effect of data connectivity on the low rank and low nuclear norm of the matrix decomposition problem, especially highlighting the impact of the intrinsic invariant manifold induced by the model structure on global dynamics. In addition, [4] studied how the implicit preference for depth promotes generalization.\n\n[1] Frequency principle: Fourier analysis sheds light on deep neural networks. Communications in Computational Physics, 28(5):1746–1767, 2020.\n\n[2] On the spectral bias of deep neural networks. International Conference on Machine Learning, 2019.\n\n[3] Connectivity shapes implicit regularization in matrix factorization models for matrix completion. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, volume 37, pages 45914–45955, 2024.\n\n[4] The implicit bias of depth: How incremental learning drives generalization, in: International Conference on Learning Representations, 2019.", "was_revised": true, "final_justification": "Resolved Issues:\n\nTechnical issues have been addressed, including clarification of experimental details.\n\nUnresolved Issues: \n\nThe authors' response to my primary concerns remains inadequate. First, regarding the theoretical scope limitation to matrix sensing settings: while the authors claim other works also operate under matrix sensing assumptions, most of these studies address the more significant problem of implicit regularization with visible generalization potential. In contrast, this work's results heavily depend on the matrix sensing sampling constraint $n < m \\times m'$, making generalization to standard deep learning scenarios with infinite sampling capacity questionable.\n\nSecond, concerning the authors' assertion that their theory merely provides an upper bound that may not align with experiments: there is insufficient discussion on bound tightness. We have observed numerous theoretical works offering elegant upper bound theorems (e.g., generalization bounds for deep learning models) that fail to enhance our genuine understanding of the underlying problems. Therefore, we should exercise caution when evaluating such seemingly elegant theorems derived under unrealistic assumptions.\n\nOverall, I maintain that this work's contribution remains quite limited. I preserve my score of 3.", "rebuttal": "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.\n\n>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… \n\nIn 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.\n\nNotwithstanding 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.\n\n>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’$...\n\nAs 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).\n\nWith 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.\n\n>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$...\n\nWe 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.\n\n>Although the authors cite a fairly comprehensive literature, there are some important and related works that are not mentioned. For example…\n\nThank 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.\n\n>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?...\n\nOur 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.\n\n>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.\n\nAgain, 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.\n\n>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.\n\nAs 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.\n\n>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.\n\nWe 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).\n\n>The experimental section lacks sufficient persuasive power. According to the authors’ theoretical claims:\n>- 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.\n>- As depth increases, the generalization error of the G&C algorithm should follow a straight line with slope -1  in a log-log plot.\n\n>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.\n\nWe 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).\n\n>Line 26: Reference [102] appears to be cited twice; please check for redundancy.\n\nWe will fix this.  Thank you.\n\n>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.\n\nWe use parentheses to denote tuples, and this is appropriate for both lines 142 and 148.\n\n---\n**References**\n\n[1] Candes et al. “Exact Matrix Completion via Convex Optimization.”\n\n[2] Sun et al. “Guaranteed Matrix Completion via Non-convex Factorization.”\n\n[3] Tu et al. “Low-rank Solutions of Linear Matrix Equations via Procrustes Flow.”\n\n[4] Bhojanapalli et al. “Global Optimality of Local Search for Low Rank Matrix Recovery.”\n\n[5] Gunasker et al. “Implicit Regularization in Matrix Factorization.”\n\n[6] Peleg and Hein. “Bias of Stochastic Gradient Descent or the Architecture: Disentangling the Effects of Overparameterization of \nNeural Networks.”\n\n[7] Razin et al. “Implicit Regularization in Tensor Factorization.”\n\n[8] Razin et al. “Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networks.“\n\n[9] Soltanolkotabi et al. “Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing.”"}, {"review_id": "PbHdEz3Yyi", "reviewer": "Reviewer_yf5s", "summary": "This paper studies the question if the use of gradient descent as an optimizer generalizes systematically better than a random sampling strategy, Guess and Check (G&C), at the exemplary problem of (low rank) matrix recovery. More specifically, it uses linear measurements of a (ground truth) low-rank matrix as training data, and measures generalization via the L2 norm of the projection of predicted and ground truth matrix on the subspace orthogonal to the measurements. The work proves that, in the limit of infinite width, G&C does not generalize well, despite the existence of a result proving that – in a specific case – gradient descent does generalize: The probability of G&C generalizing well becomes as bad as randomly drawing from the prior distribution independent of the training data. In contrast, in the limit of infinite depth d, the probability of G&C generalizing converges to 1 at a rate of 1/d. The authors claim that the former result makes this paper the first case where G&C has proven to be inferior to gradient descent. Overall, the paper concludes that the is no simple answer to the question if networks need gradient descent to generalize well.", "questions": "Please clarify my main question raised under \"strength and weaknesses\" above. I might very well just be mistaken on this, as I am not an expert on this topic. If not, please explain how you plan to change the interpretation of the result.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper tackles a very interesting question and is very well-written. All technical results are described (in terms of their meaning, interpretation and intuition) before stating them formally, allowing readers to see the reasons for certain formal definitions. Similarly, the main ideas of the proofs have been stated in the papers, while all details are deferred to the appendix. \n\nWhile the contribution and overall study are nice, I have some doubts about the conclusions. The following part is based on my (possibly wrong) understanding of the results and I’d highly appreciate a comment/correction in the rebuttal: The results seem to heavily depend on the desire to find low-rank matrices. The setup is not a supervised learning scenario. The training data could be identical for many different distributions of ground truth matrices, i.e., the same y_i could originate from a sparse ground truth matrix or a ground truth matrix with a small $\\ell_p$ norm. As for identical training data the resulting matrices produced by gradient descent and G&C will not change, the generalization seems to depend on the (hidden) desired ground truth. If G&C and gradient descent (GD) yield probability distributions p( . | L_{train}<epsilon) that are sufficiently different, doesn’t that immediately mean there are settings where G&C generalizes better than GD and settings where GD generalizes better than GD (because the unknown ground truth distribution could coincide with either of the two without really changing the training data)? In this sense generalization does not seem to be a property to associate with an algorithm (alone). \n\nIf we, for instance, consider the least-squares problem $||Ax-y||^2$. Running gradient descent converges to a solution such that $x-x_0 \\in \\text{kern}(A)^\\perp$, i.e., it commonly ends at a solution close to the minimal norm solution (for typical initializations). If $y = Ax_{true}$ and $x_{true}$ is sparse, then the solution of gradient descent will be quite different from $x_{true}$. But would we really blame this on gradient descent not generalizing well? Don’t we need to talk about the property of generalization for the combination of architecture, optimization algorithm and data distribution? If so, this would be something to emphasize in the paper.", "was_revised": true, "final_justification": "I'd like to thank the authors for the discussion. I like the overall result and contribution of this paper. To my mind, the results are, however, pitched in a little more generality than they contain. As the authors acknowledge in the discussion, creating a difference (on any artificially manufactured problem) between the distributions obtained by applying gradient descent and G&C is sufficient to claim that there exists a case where GD is systematically better than G&C (and vice versa). Manufacturing such a problem is likely not difficult. Thus, the authors' results should rather be interpreted in the specific (but widely studied) context of low-rank matrix factorization than as a trend in deep learning problems in general. Trusting the authors to make this clear in a possible camera-ready version of the paper, I tend towards accepting this work and have updated my score accordingly.", "rebuttal": "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.\n\nYou 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]).\n\nWe 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!\n\n---\n**References**\n\n[1] Candes et al. “Exact Matrix Completion via Convex Optimization.”\n\n[2] Sun et al. “Guaranteed Matrix Completion via Non-convex Factorization.”\n\n[3] Tu et al. “Low-rank Solutions of Linear Matrix Equations via Procrustes Flow.”\n\n[4] Bhojanapalli et al. “Global Optimality of Local Search for Low Rank Matrix Recovery.”\n\n[5] Gunasker et al. “Implicit Regularization in Matrix Factorization.”\n\n[6] Razin et al. “Implicit Regularization in Tensor Factorization.”\n\n[7] Bell and Koren. “Lessons from the Netflix Prize Challenge.”\n\n[8] Ma. “Three-Dimensional Irregular Seismic Data Reconstruction via Low-Rank Matrix Completion.”\n\n[9] Kapur et al. “Gene Expression Prediction Using Low-Rank Matrix Completion.”\n\n[10] Razin et al. “Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networks.“"}, {"review_id": "ShfHuglnc0", "reviewer": "Reviewer_yR2t", "summary": "This submission studies the volume hypothesis -- the claim that \"most\" near-interpolating solutions have small generalization error -- in the context of low-rank matrix factorization. The authors specifically consider a model parameterized by a (deep) feed-forward neural network with i.i.d random initialization. The first main result, Theorem 1, is that as the width of the neural network increases, the probability that a randomly sampled near-interpolating solution has small generalization error tends to zero. On the other hand, the second main result, Theorem 2, is that as the depth increases, the probability that a near-interpolator has small generalization error tends to 1.", "questions": "- 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)?\n- 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?\n- I would also appreciate if the authors could comment on my above concerns re the rank 1 assumption in Theorem 2.", "limitations": "Limitations are adequately addressed.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths:\n- The problem studied here is well motivated, and matrix factorization is a tractable and interesting testbed to understand how randomly sampled near-interpolators generalize. I thus think the results are of interest to the community.\n- To the best of my knowledge, the results presented here are novel.\n- The submission is well-written and easy to understand. I skimmed the appendices, and the proofs appear to be correct.\n- Theorems 1 and 2 are supported empirically.\n\n## Weaknesses\n- As the authors indeed admit, the theoretical results rely on a number of assumptions, such as the choice of activation function. 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 \\cdots 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.\n- Implications beyond matrix factorization towards more standard neural network settings (such as training a fully connected network on a simple dataset) are not clear.\n- (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?", "was_revised": true, "final_justification": "The authors have explained how their proof techniques should generalize to rank > 1, which was my main initial concern, and thus I recommend acceptance for this paper.", "rebuttal": "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.\n\n>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.\n\nTheorem 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.\n\n>Implications beyond matrix factorization towards more standard neural network settings (such as training a fully connected network on a simple dataset) are not clear.\n\nThe 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!\n\n>(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?\n\nThank 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.\n\nNotwithstanding 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. \n\n>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)?\n\nYour 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.\n\nIf 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).\n\n> 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?\n\nOur 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.\n\n> I would also appreciate if the authors could comment on my above concerns re the rank 1 assumption in Theorem 2.\n\nSee above.\n\n---\n**References**\n\n[1] Peleg and Hein. “Bias of Stochastic Gradient Descent or the Architecture: Disentangling the Effects of Overparameterization of Neural Networks”\n\n[2] Razin et al. “Implicit Regularization in Tensor Factorization.”\n\n[3] Razin et al. “Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networks.“"}, {"review_id": "mRiwme77XA", "reviewer": "Reviewer_2Hfc", "summary": "This paper studies the generalization properties of over-parameterized neural networks by considering scenario of low-rank matrix sensing. The central contribution of this paper derives generalization bounds for a guess-and-check optimization algorithm. In particular, when the weights of a fully connected FFN is drawn from an iid Gaussian distribution:\n\n- In the limit as the width of a fully-connected FFN $\\to \\infty$, the out-of-sample loss of guess and check is as bad as random guessing.\n\n- Under additional assumptions such as *restricted isometry property*, in the limit as the depth of the network $\\to \\infty$, the out-of-sample loss approaches 1.\n\nThese two results demonstrate that whether guess-and-check can match gradient descent in generalization performance is instance dependent.", "questions": "see above", "limitations": "see above", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I do not have too many comments on this work because the main takeaway of this paper is clear and the overall technical setup is not particularly complicated. It is actually refreshing to read this paper given the recent trend of content creeps in ML theory papers.\n\nIn terms of the main message of the paper, I think the testbed should be called low-rank matrix sensing rather than matrix factorization, since the later does not make much sense when the activation in eq (4) is non-linear.\n\nThe paper as whole is not difficult to understand and the author did a good job at identifying a concise theoretical framework that captures the intended messages. Personally, I feel that the first result on infinite width (Theorem 1) is not too surprising, and the second result on infinite depth (Theorem 2) does require some fairly strong assumptions. But both of these results answered very relevant questions and therefore they should be shared with the wider theory community.\n\nFor the technical contents, I briefly read over the proofs in Appendix A and B, though I did not check the details line-by-line. The math seems to be sound overall. The theorem statements in the main body are clear and easy to understand, but their counterparts in the Appendix (e.g. Theorem 6) are somewhat bloated.\n\nThings that could be improved:\n1. 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.\n\n2. 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.\n\n3. I feel the experiments in Section 5 is unnecessary.\n\n4. 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.\n\n5. 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.\n\n6. 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.\n\nOverall, I think the results of this paper is sufficiently interesting for publication. But it is not particularly sophisticated in the technical contribution and some might argue that the guess-and-check algorithm does not warrant research in the first place. Also, there is very little from this paper that could lead to wider implications for both future theoretical and empirical studies. So I think it is fair to recommend a **borderline accept**.", "was_revised": true, "final_justification": "This paper is technically sound and offers some interesting perspectives. While the authors' rebuttal is quite detailed, I still have some lingering doubts about the deeper implications of this work. Therefore, I will maintain my original score, but will raise my confidence to show my support for this paper.", "rebuttal": "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.\n\n>I feel the experiments in Section 5 is unnecessary.\n\nWhile 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.\n\n>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.\n\nTheorem 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.\n\n>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\n\nThe 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.\n\n>some might argue that the guess-and-check algorithm does not warrant research in the first place\n\nAs 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). \n\n>little from this paper that could lead to wider implications\n\nThe 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!\n\n>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.\n\n>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.\n\n>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.\n\nThank 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.\n\n---\n**References**\n\n[1] Peleg and Hein. “Bias of Stochastic Gradient Descent or the Architecture: Disentangling the Effects of Overparameterization of Neural Networks”\n\n[2] Razin et al. “Implicit Regularization in Tensor Factorization.”\n\n[3] Razin et al. “Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networks.“"}]

Author rebuttal:

Meta-review: This paper examines whether gradient descent is necessary for neural networks to generalize effectively, using matrix factorization as a testbed. The authors compare the generalization performance of gradient descent with a non-optimized alternative, Guess & Check (G&C), and analyze how generalization varies with network width and depth. Their theoretical results show that generalization under G&C deteriorates with increasing width but improves with increasing depth, in contrast to gradient descent, which remains consistently strong across settings.

The reviewers agreed that the paper introduces interesting ideas that are well-motivated and carefully validated, supported by both theoretical analysis and empirical evidence. Based on this, I recommend acceptance.
Decision: Accept (poster)