PaperlayerView exact revision on arXiv

Source-linked AI summary

Tensor Programs III: Neural Matrix Laws

Greg Yang

arXiv:2009.10685v3cs.NEmath.PR

TL;DR

The paper addresses the lack of rigorous justification for treating neural-network weights and preactivations as free in wide randomly initialized networks. It proves an unrestricted Tensor Programs Master Theorem, establishes FIP, and applies it to Jacobian singular values while recovering classical random-matrix laws. These results hold across neural architectures within the stated random-initialization setting.

  • Problem

    Previous neural-network Jacobian singular-value calculations assumed weight–preactivation freeness without proving how broadly it holds.

    Source: §1.1 · p. 2

  • Method

    The paper proves a Master Theorem for any Tensor Program and uses it to analyze nonlinear random-matrix ensembles and neural networks.

    Source: §1.3 · p. 4, §1.4 · p. 5

  • Results

    FIP establishes asymptotic freeness between weights and preactivation-derived diagonal matrices, enabling rigorous Jacobian singular-value calculations for randomly initialized neural networks.

    Source: §1 · p. 1, §8 · p. 21

  • Takeaways & Limitations

    The Tensor Programs framework provides a mechanically applicable route to nonlinear random-matrix limits and neural-network analyses across architectures.

    Source: §8 · p. 21

    The paper makes no claim about trained weights, and its semicircle-law discussion is restricted to the GOE case rather than generic iid ensembles.

    Source: §1 · p. 1, §3 · p. 10

Abstract

from arXiv · show

In a neural network (NN), *weight matrices* linearly transform inputs into *preactivations* that are then transformed nonlinearly into *activations*. A typical NN interleaves multitudes of such linear and nonlinear transforms to express complex functions. Thus, the (pre-)activations depend on the weights in an intricate manner. We show that, surprisingly, (pre-)activations of a randomly initialized NN become *independent* from the weights as the NN's widths tend to infinity, in the sense of asymptotic freeness in random matrix theory. We call this the Free Independence Principle (FIP), which has these consequences: 1) It rigorously justifies the calculation of asymptotic Jacobian singular value distribution of an NN in Pennington et al. [36,37], essential for training ultra-deep NNs [48]. 2) It gives a new justification of gradient independence assumption used for calculating the Neural Tangent Kernel of a neural network. FIP and these results hold for any neural architecture. We show FIP by proving a Master Theorem for any Tensor Program, as introduced in Yang [50,51], generalizing the Master Theorems proved in those works. As warmup demonstrations of this new Master Theorem, we give new proofs of the semicircle and Marchenko-Pastur laws, which benchmarks our framework against these fundamental mathematical results.

1 Introduction

The paper introduces FIP, showing that randomly initialized wide neural networks exhibit asymptotic freeness between weights and activation-derived diagonal matrices, across architectures. It proves an unrestricted Tensor Programs Master Theorem to establish this result and derive random-matrix laws and Jacobian singular-value distributions.

1 Introduction

  • FIP shows that, as width tends to infinity, randomly initialized neural-network weights become asymptotically free from diagonal matrices formed from bounded coordinatewise functions of preactivations.The result applies to any neural architecture, but not to trained weights.Source: §1 · p. 1

1.1 Random Matrix Theory in Deep Learning

  • The paper addresses the missing rigorous foundation for neural-network Jacobian singular-value calculations, where weight–preactivation freeness had previously been assumed and empirically checked.FIP establishes that this free-independence phenomenon is architecturally universal within the stated setting.Source: §1.1 · p. 2

1.2 New Approach to Random Matrix Theory

  • Classical entrywise expansion fails for nonlinear neural-network ensembles because matrices and their diagonal nonlinear factors depend on one another in complicated ways.Taylor expansion is possible but becomes unwieldy, especially for nonsmooth nonlinearities.Source: §1.2 · pp. 2–3

1.3 The Tensor Programs Framework

  • The framework unifies analyses of wide neural networks across architectures, addressing the prior need for separate theoretical treatments of convolutions, normalization, attention, and other additions.Its key insight is that randomized program vectors have approximately iid coordinates while same-index coordinates across vectors retain calculable correlations.Source: §1.3 · p. 4
  • Tensor Programs replace manual combinatorial expansions with symbolic rules that track limiting coordinate distributions and correlations mechanically, including nonlinear transformations.The framework represents each computed vector by a scalar random variable and derives subsequent variables from program structure.Source: §1.3 · pp. 3–4

1.4 Tensor Programs Master Theorems

  • The unrestricted Master Theorem handles any Tensor Program, including programs that reuse both a weight matrix and its transpose, and supports the paper’s random-matrix results.The paper also gives new proofs of the semicircle and Marchenko–Pastur laws, proves FIP, and applies it to neural-network Jacobian singular values.Source: §1.4 · p. 5

2 NETSOR⊤: Language for Neural Computation

NETSOR⊤ is a language for composing coordinatewise nonlinearities with matrix and transpose-matrix multiplications, enabling symbolic tracking of large-width neural computations. Its Master Theorem characterizes coordinate distributions and correlations, including corrections caused by reusing matrices and their transposes.

2 NETSOR⊤: Language for Neural Computation

  • The framework models wide neural networks as alternating matrix multiplications and coordinatewise nonlinearities, including standard multilayer perceptrons.A perceptron uses h_l+1 = W_l+1 x_l and x_l = φ(h_l).Source: §2 · pp. 5–6
  • NETSOR⊤ programs generate vectors through nonlinear transformations and multiplication by matrices or their transposes.The language begins with random vectors and matrices, then applies Nonlin and MatMul operations.Source: §2 · p. 6
  • When a matrix transpose has previously been used, matrix multiplication decomposes into a Gaussian component plus a correction capturing transpose-induced correlations.The correction lies in the span of earlier vectors and is determined by relevant inner products or derivative expectations.Source: §2 · pp. 7–9
  • The Master Theorem assigns each program vector an asymptotic coordinate random variable and proves convergence for polynomially bounded test functions.It applies when initial matrices and vectors follow the specified Gaussian setup and nonlinearities are polynomially bounded.Source: §2 · p. 9
  • The framework extends to variable dimensions, parameter-controlled nonlinearities, rank-stable NETSOR⊤+ programs, and rectangular matrices.Additional extensions allow coordinate averages and non-square matrices, subject to stated conditions.Source: §2 · p. 10

3 Semicircle Law

The paper gives a Tensor Programs proof of the semicircle law for a Gaussian symmetric matrix ensemble. It computes limiting trace moments through symbolic rules, recovering Catalan moments and contrasting this approach with classical entrywise combinatorics.

3 Semicircle Law

  • Theorem 3.2 establishes that the empirical eigenvalue distribution of W + W⊤ converges almost surely to the semicircle distribution.Here W has iid Gaussian entries with variance 1/(2n), and the result is tested against compactly supported continuous functions.Source: §3 · p. 10

3.1 The Main Proof Idea

  • The proof reduces spectral convergence to trace-moment limits, requiring even moments to converge to Catalan numbers and odd moments to vanish.The moment method supplies the bridge from these trace limits to the semicircle law.Source: §3 · p. 10, §3.1 · p. 11

3.2 Examples of First Few Moments

  • The first examples derive Gaussian coordinate variables for the program vectors and show n^-1 tr A^2 converges almost surely to 1.The construction uses z_t = Wz_t-1 + W⊤z_t-1 and the Master Theorem’s Gaussian and correction components.Source: §3.2 · p. 11, §3.1 · p. 11

3.3 Proof for General Moments

  • The general-moment proof represents each z_t as τ_t Z_z0 plus an independent zero-mean term, yielding the required trace limits through a recurrence matching Catalan numbers.The argument uses conditional expectations and the Master Theorem to pass from symbolic variables to normalized traces.Source: §3.3 · pp. 12–13

3.4 Comparison with the Classical Proof

  • Unlike the classical proof’s entrywise expansion and non-crossing-partition counting, the Tensor Programs proof is symbolic and more readily applies to nonlinear matrix dependencies.The paper notes that classical expansion becomes difficult for neural-network Jacobians because nonlinearities prevent direct matrix-entry expansions.Source: §3.4 · p. 13
  • The demonstrated proof currently relies on Gaussian matrices, while universality for general iid matrices is left for future work.The authors suggest a Lindeberg replacement argument as a possible route.Source: §3.4 · p. 13

4 The Free Independence Principle of NETSOR⊤Programs

The Free Independence Principle states that, at infinite width, Gaussian weight matrices and diagonal matrices formed from program vectors are asymptotically free. This formalizes weight–activation independence and enables asymptotic Jacobian singular-value calculations for randomly initialized neural networks.

4 The Free Independence Principle of NETSOR⊤Programs

  • Asymptotic freeness lets random-matrix spectral distributions combine predictably under sums and products, analogously to how scalar independence simplifies moments.The paper interprets this as a general-position relationship between eigenvectors and eigenvalues.Source: §4 · pp. 13–14
  • In randomly initialized neural networks, weight matrices are asymptotically free from diagonal matrices formed from preactivations and other program vectors.The theorem applies to any NETSOR⊤ program with polynomially bounded nonlinearities.Source: §4 · p. 14
  • The diagonal-matrix collection consists of bounded coordinatewise transformations of finitely many program vectors.D(π) collects these diagonal matrices for all vectors in the program.Source: §4 · p. 14
  • The theorem directly enables computation of the asymptotic singular-value distribution of a randomly initialized neural-network Jacobian.This addresses a previously unproved independence assumption used in such calculations [36, 37].Source: §4 · p. 14
  • The result extends to variable-dimension NETSOR⊤ programs and to NETSOR⊤+ programs when nonlinearities are parameter-controlled and rank stability holds.The variable-dimension extension is stated under Assumption E.7.Source: §4 · p. 14

5 Jacobian Singular Values of a Randomly Initialized Neural Network

The section rigorously derives asymptotic Jacobian singular-value distributions by combining Jacobian factorizations with the Free Independence Principle. The framework extends beyond MLPs to essentially any neural architecture expressible as a NETSOR⊤ program and also supports a Neural Tangent Kernel gradient-independence argument.

Jacobian singular-value calculation

  • The Jacobian factors into weight matrices and diagonal activation-derivative matrices, so its singular values are determined by the spectrum of J⊤J.The diagonal matrices contain φ′ evaluated at hidden-layer preactivations.Source: §5 · p. 15

Free Independence Principle

  • The Free Independence Principle makes the required asymptotic freeness assumption rigorous for weight matrices and bounded preactivation images in randomly initialized networks.It also establishes freeness among diagonal collections formed from mutually independent partitions of preactivations.Source: §5 · p. 15

MLP result

  • For an MLP with bounded weak derivative, the Jacobian spectrum converges almost surely to a free multiplicative-convolution expression involving Marchenko-Pastur laws and activation-derivative distributions.When φ is the identity, the result recovers the Marchenko-Pastur law.Source: §5 · p. 15
  • The input ξ affects the limiting Jacobian spectrum only through the distributions of activation derivatives across hidden layers.The theorem covers common nonlinearities such as tanh and ReLU, whose weak derivatives are bounded.Source: §5 · p. 15

Generalizations

  • The theorem generalizes to non-unit width ratios by replacing repeated Marchenko-Pastur factors with free multiplicative convolutions of different shape ratios.Extensions to polynomially bounded derivatives are expected but left for future work.Source: §5 · p. 16

General architectures

  • The method yields a general algorithm for asymptotic Jacobian singular-value distributions of residual, recurrent, convolutional, and other NETSOR⊤ architectures.The Jacobian is expressed as a polynomial in asymptotically free matrices and evaluated using operator-valued free probability or Tensor Program moment computations.Source: §5 · p. 16

Neural Tangent Kernel

  • Under the Simple GIA Check, the Neural Tangent Kernel depends on backpropagation through second Jacobian-singular-value moments, allowing transposed weights to be replaced by forward-pass-independent copies.This supplies a new justification for the gradient-independence assumption used in Neural Tangent Kernel calculations.Source: §5 · p. 16

6 Proof Sketch of the Master Theorem

The proof sketch establishes the Master Theorem by induction over generated vectors, conditioning Gaussian matrices and replacing quantities with deterministic limits. It removes smoothness requirements through averaging, proves rank stability for degenerate cases, and derives the correction term using an adjunction identity.

6.1 Master Theorem Proof Sketch with Sufficient Regularity Assumptions

  • The Master Theorem proof inducts over G-vars, reducing each new matrix-vector computation to earlier moment quantities and deterministic limits.The base case follows from the strong law of large numbers for iid initial vectors.Source: §6.1 · p. 16
  • Conditioning a reused Gaussian matrix on previously generated vectors yields a conditional mean plus projected Gaussian randomness, enabling the inductive reduction.The remaining randomness concentrates by a law-of-large-numbers argument, while scalar coefficients converge almost surely to deterministic limits.Source: §6.1 · p. 17

6.2 Getting Rid of Smoothness Assumption

  • The first smooth proof sketch relies on sufficiently smooth nonlinearities, whereas ReLU motivates the separate nonsmooth treatment because its weak derivative is discontinuous.The averaging and rank-stability arguments address this limitation.Source: §6.1 · p. 17
  • The smoothness assumption is removed because Gaussian averaging smooths conditional expectations even when the original nonlinear function is nonsmooth.This strategy requires controlling correlations without replacing the projection by the identity.Source: §6.2 · p. 18

6.2.1 Law of Large Numbers for Images of Weakly Correlated Gaussians

  • Theorem 6.2 proves a strong law of large numbers for polynomially bounded images of weakly correlated Gaussian triangular arrays.The result applies to low-corank projection covariances and completes the nonsmooth argument.Source: §6.2.1 · p. 18

6.2.2 Rank Stability

  • Rank Stability prevents limiting rank loss from causing divergent pseudoinverses and rules out the problematic case where conditional variance vanishes only asymptotically.If the limiting conditional variance is zero, the new vector becomes the same linear combination of earlier vectors for sufficiently large width.Source: §6.2.2 · p. 19

6.3 The Calculation of ˙Z

  • The calculation of the correction term uses the adjunction relation between W and W⊤ to transfer expectations and verify the recursive form of ˙Z.This identifies the coefficients in the inductive representation of each newly generated vector.Source: §6.3 · pp. 19–20

7 Related Works

Related work established neural Jacobian spectral calculations and earlier Tensor Program Master Theorems, but this paper broadens both the architecture and program settings. It also connects its correction term to asymmetric message passing while tracking it through arbitrary computations.

Jacobian Singular Value Distribution

  • Earlier Jacobian analyses covered MLPs, residual MLPs, and convolutional networks but assumed asymptotic freeness that was initially empirical or limited in scope.This paper handles practically all architectures expressible in NETSOR⊤ and requires only bounded φ′ in the stated comparison.Source: §7 · p. 20
  • The paper studies input-output Jacobians, distinct from parameter Jacobians whose dimensions are determined by parameter and data counts.The distinction concerns the object whose singular-value distribution is analyzed.Source: §7 · p. 20

Onsager Correction Term

  • The correction term ˙ZW x generalizes the Onsager correction from asymmetric message passing by tracking it throughout arbitrary Tensor Program computations.This broader tracking enables the paper’s semicircle-law and Free Independence Principle results.Source: §7 · p. 20

The Tensor Programs Series

  • Compared with Yang [50], the unrestricted Master Theorem permits NETSOR⊤ programs that use a matrix and its transpose together, a setting needed for the paper’s random-matrix results.The earlier theorems covered important but narrower program classes.Source: §7 · p. 20

8 Conclusion

The paper concludes that an unrestricted Master Theorem enables new semicircle and Marchenko-Pastur proofs, establishes FIP, and yields Jacobian singular-value calculations for randomly initialized neural networks. Appendix results extend convergence in mean to bounded and selected linearly or quadratically bounded settings, while polynomially bounded generality remains conjectural.

8 Conclusion

  • The paper proves an unrestricted Master Theorem, new semicircle and Marchenko-Pastur proofs, the Free Independence Principle, and rigorous neural-network Jacobian singular-value calculations.Together these results support a Tensor Programs approach to nonlinear random matrix theory.Source: §8 · pp. 20–21

A.1 Convergence in Mean

This in particular means the convergence of expectations

  • The convergence result also holds when ψ is quadratically bounded and all nonlinearities are linearly bounded.High-probability norm bounds for Gaussian matrix products and coordinatewise nonlinearities provide the needed tail control.Source: This in particular means the… · p. 25
  • The paper conjectures that the convergence theorem extends to polynomially bounded ψ, but proving the required tail bound is left for future work.The stated difficulty is establishing a sufficiently strong tail estimate despite Gaussian sampling and polynomially bounded nonlinearities.Source: This in particular means the… · p. 26

A.2 Convergence in Distribution of Coordinates

The appendix establishes convergence and asymptotic independence of coordinate slices, then extends these results to broader Tensor Programs and Gaussian-process limits for wide networks.

A.2 Convergence in Distribution of Coordinates

  • Distinct coordinate slices converge jointly to iid copies of the limiting coordinate distribution.The result is proved by induction from single-coordinate convergence.Source: §A.2 · p. 26

A.3 Extensions to NETSOR⊤+ and Programs with Variable Dimensions

  • The coordinate-convergence theorems extend to variable-dimension programs and NETSOR⊤+ programs under rank stability and stated nonlinearity conditions.Vector nonlinearities require linear boundedness, while scalar nonlinearities require quadratic boundedness and an additional convergence condition.Source: §A.3 · p. 27

B Generalized Architectural Universality of Neural Network-Gaussian Process

  • Wide networks whose forward propagation is expressible as a NETSOR⊤ program converge in distribution to Gaussian Processes when output layers are independently sampled and unused internally.The GP conclusion follows from deterministic convergence of input-embedding kernels and independent readout layers.Source: B Generalized Architectural… · p. 27
  • When output weights are reused inside the network, the limiting output can instead be non-Gaussian, while remaining computable through the Master Theorem.The example identifies nonzero dependence between the output and the reused weight matrix.Source: B Generalized Architectural… · p. 27

C Generalized Architectural Universality of Neural Tangent Kernel

The paper generalizes infinite-width Neural Tangent Kernel analysis beyond the usual Gradient Independence Assumption, using the NETSOR⊤ Master Theorem to compute dependencies involving transposed weights.

C Generalized Architectural Universality of Neural Tangent Kernel

  • Under Simple GIA Check, the generalized theorem recovers the standard independent-copy computation used in prior NTK analyses.The paper states that the infinite-width NTK can be computed straightforwardly using Theorem 2.10.Source: C Generalized Architectural… · p. 28
  • The NETSOR⊤ Master Theorem permits correct NTK computation when transposed forward weights invalidate the usual independence heuristic.A concrete square-activation network produces an erroneous result if W 2⊤ is incorrectly treated as independent from W 2.Source: C Generalized Architectural… · p. 28
  • Theorem C.1 shows that any NETSOR⊤-expressible network in NTK parametrization has a deterministic infinite-width NTK under polynomially bounded weak derivatives, without Simple GIA Check.The convergence holds over any finite set of inputs.Source: C Generalized Architectural… · p. 28

D Simple GIA Check Implies Gradient Independence Assumption

The paper proves that FIP justifies the Gradient Independence Assumption for networks satisfying Simple GIA Check, while extending Tensor Programs with scalar quantities and convergence rules.

D Simple GIA Check Implies Gradient Independence Assumption

  • FIP proves that NTK computation may replace backward-pass W ⊤ matrices with copies independent of forward-pass W matrices under Simple GIA Check.This follows because the relevant gradient inner products become moments preserved by FIP.Source: D Simple GIA Check Implies Gradient… · pp. 28–29
  • Simple GIA Check requires no weight matrix to be another matrix’s transpose and an independently sampled, unused, zero-mean output layer.These conditions make the output weights independent of the embedding used in backpropagation.Source: D Simple GIA Check Implies Gradient… · p. 29

E NETSOR⊤+: Adding Scalars to NETSOR⊤

  • NETSOR⊤+ augments Tensor Programs with scalars that converge to deterministic limits alongside vectors with asymptotically iid coordinates.Scalars are generated from averages or coordinatewise nonlinear operations and are tracked recursively.Source: E NETSOR⊤+: Adding Scalars to NETSOR⊤ · p. 29

E.1 NETSOR⊤+ Master Theorem for Pseudo-Lipschitz Nonlinearities

  • The pseudo-Lipschitz NETSOR⊤+ Master Theorem gives polynomially bounded empirical-moment convergence and almost-sure convergence of program scalars under rank stability.The theorem applies to programs initialized as specified and whose nonlinearities satisfy the stated regularity conditions.Source: §E.1 · pp. 30–31

E.2 NETSOR⊤+ Master Theorem for Parameter-Controlled Nonlinearities

The paper introduces a parameter-controlled Master Theorem that handles broader nonlinearities, explains why its assumptions matter, and removes rank stability when stronger test-function smoothness is imposed.

E.2 NETSOR⊤+ Master Theorem for Parameter-Controlled Nonlinearities

  • The parameter-controlled Master Theorem extends convergence results to nonlinearities controlled at deterministic limiting parameters, assuming rank stability.It covers vectors and scalars represented through G-vars and yields almost-sure scalar convergence.Source: §E.2 · pp. 31–32
  • The parameter-control and rank-stability assumptions are substantive: discontinuous parameter dependence or collapsing vectors can make the Master Theorem fail.The examples show that limiting behavior can disagree with finite-width ranks or with the theorem’s predicted expectation.Source: §E.2 · p. 32
  • Parameter control is more flexible than pseudo-Lipschitzness but harder to verify compositionally, and it supports applications such as layer-normalized GP and NTK calculations.For example, division by a parameter is not pseudo-Lipschitz but is parameter-controlled when its limiting value is positive.Source: §E.2 · p. 32

E.3 Getting Rid of Rank Stability Assumption through More Test Function Smoothness

  • With pseudo-Lipschitz nonlinearities and test functions, Theorem E.15 removes rank stability while retaining empirical-moment and scalar convergence.The proof must address instability of covariance-matrix pseudoinverses in the Gaussian conditioning argument.Source: §E.3 · p. 33

F Programs with Variable Dimension

The paper extends Tensor Programs to variable-width networks by organizing vectors into common dimension classes and taking coupled large-dimension limits. It uses this framework to formulate master-theorem results and benchmark them by proving the Marchenko–Pastur law.

F Programs with Variable Dimension

  • Variable-dimension Tensor Programs permit MatMul operations between matrices and vectors whose two sides have different dimensions.Nonlinearities still act on vectors in a shared dimension, while MatMul enforces matching input and output dimensions across paired operations.Source: F Programs with Variable Dimension · pp. 33–34
  • Common Dimension Classes partition vectors whose dimensions must agree, allowing different classes to grow at different rates.The limit sends every class dimension to infinity while keeping each pairwise dimension ratio finite and nonzero.Source: F Programs with Variable Dimension · pp. 33–35
  • The variable-dimension Master Theorems extend asymptotic coordinate and scalar-limit guarantees to polynomially bounded and pseudo-Lipschitz programs.The results include almost-sure convergence of program scalars and coordinate statistics under rank-stability and nonlinearity assumptions.Source: F Programs with Variable Dimension · pp. 35–36
  • The parameter-controlled Master Theorem further handles nonlinearities whose parameters converge almost surely to deterministic limits.It applies to parameter-controlled functions evaluated at convergent random parameter vectors.Source: F Programs with Variable Dimension · p. 36

G Random Matrix Theory Background

  • The paper reviews the Moment Method, which establishes spectral convergence by matching matrix-trace moments to target-distribution moments under moment-determinacy conditions.For Hermitian matrices, empirical eigenvalue moments are normalized traces of matrix powers.Source: G Random Matrix Theory Background · pp. 36–37

H Proving the Marchenko-Pastur Law by Tensor Programs

  • Using variable-dimension Tensor Programs and the Moment Method, the paper proves the Marchenko–Pastur law for rectangular Gaussian Wishart matrices.The construction represents repeated AA⊤ applications through alternating A⊤ and A multiplications and matches all limiting moments.Source: H Proving the Marchenko-Pastur Law by… · p. 37

H.1 Explicit Calculations of the First Few Moments

  • The first moment calculation obtains 1/n tr(AA⊤) → 1 almost surely, matching the first moment of the Marchenko–Pastur distribution.The calculation illustrates how the Tensor Program’s limiting coordinate variables reproduce the target spectral moment.Source: §H.1 · p. 38

H.2 Proof for General Moments

The general-moment proof derives recurrences for the limiting coordinates of repeated matrix products and identifies their solutions with Marchenko–Pastur moments. The section also develops subprogram independence, showing how asymptotic uncorrelation supports treating later matrix computations as independent of earlier ones.

H.2 Proof for General Moments

  • The general proof represents each repeated product through limiting coordinate variables whose Gaussian covariances and deterministic components satisfy recursive relations.The resulting recurrence is solved by expressing Marchenko–Pastur moments through semicircle-law moments and Catalan identities.Source: §H.2 · pp. 38–39
  • The recurrence solution matches the Marchenko–Pastur moments for every k, completing the moment-based proof of the law.The proof explicitly identifies E λ∼µ_mp λ^k with the limiting coordinate calculation.Source: §H.2 · p. 39

I Subprogram and Subprogram Independence

  • A program can be divided into consecutive subprograms, and subprogram independence is defined by replacing later-used matrices with independent copies without changing the limiting joint distribution.The definition is structural and concerns the asymptotic random variables associated with program vectors.Source: I Subprogram and Subprogram Independence · p. 40
  • The independence-from-uncorrelation lemma makes a later MatMul subprogram independent when it depends on an earlier subprogram through a vector uncorrelated with the relevant matrix products.The lemma applies when the later computation is a polynomial in W and W⊤ and the stated covariance conditions hold.Source: I Subprogram and Subprogram Independence · pp. 40–41
  • The lemma yields a decomposition of later products into a component proportional to the input vector plus an independent zero-mean component.For variable dimensions, the proportional coefficient vanishes when the input and output vectors lie in different common dimension classes.Source: I Subprogram and Subprogram Independence · p. 41
  • Applying these lemmas to forward and backward MLP computations provides another proof that the gradient-independence assumption is valid under the stated structural condition.The backward pass can repeatedly treat transposed weight matrices as independent from the forward-pass quantities for the relevant asymptotic calculations.Source: I Subprogram and Subprogram Independence · pp. 40–42

J Proving Free Independence Principle

This section develops the proof of the Free Independence Principle through auxiliary NETSOR⊤+ programs and induction, establishing asymptotic independence or uncorrelatedness under rank-stability conditions. It also presents a Hermite-polynomial argument for a key lemma, supported by combinatorial vertex-covering and analytic tools.

J Proving Free Independence Principle

  • The argument represents alternating matrix and diagonal-polynomial factors through a NETSOR⊤+ subprogram, then applies Theorem A.7 to prove the target trace convergence.Examples unpack matrix powers and diagonal factors using MatMul, Moment, and Nonlin+ operations satisfying Theorem A.7’s nonlinearity conditions.Source: J Proving Free Independence Principle · pp. 43–44
  • The cited calculation shows that E v,u1,...,ut v⊤(At −ut⊤Atut) · · · (A1 −u1⊤A1u1)v equals v⊤vt almost surely and converges to E ZvZvt = 0.Source: J Proving Free Independence Principle · p. 44

K.1 Probability Facts

  • The mathematical-tools appendix supplies probability facts including almost-sure convergence from uniformly bounded moments, Gaussian conditioning, Stein’s Lemma, and Hessian-gradient identities.These results provide the probabilistic foundations for the proof’s independence and convergence arguments.Source: §K.1 · pp. 45–46

K.2 Gaussian Conditioning Trick

  • The Gaussian-conditioning toolkit characterizes conditioned Gaussian vectors and matrices using Moore-Penrose pseudoinverses and orthogonal projections, including simultaneous linear constraints on A.The appendix also records the pseudoinverse’s defining identities, uniqueness, and projection properties.Source: §K.2 · pp. 47–48

K.3 Hermite Polynomials

  • Hermite polynomials {Hn}n≥0 form an orthonormal basis for L2(R; N(0,1)), and for (z1,z2)∼N(0,C) with C11=C22=1 and C12=ρ∈[−1,1], E φ(z1)ψ(z2)=a0b0+a1b1ρ+a2b2ρ2+⋯ absolutely converges.Source: §K.3 · p. 48
  • Lemma K.17 assumes selected functions are centered and imposes bounded pairwise correlation parameters, including |λ_12| ≤ 1/2 and |λ_ij| ≤ λ/(k − 1).The centering condition is b_i0 = a_i0 = 0 for i in an index set I ⊆ [3, k], with λ < 1/8.Source: §K.3 · p. 50
  • The proof partitions index pairs into sets P and Q according to whether pairs include indices 1 or 2, and introduces R = Q^k.These sets organize the combinatorial terms used in the proof.Source: §K.3 · p. 51
  • The proof bounds the relevant combinatorial contribution using B_|I|, the number of coverings of |I| vertices by ⌈|I|/2⌉ edges, plus an o(1) term controlled as λ → 0.The remainder is bounded by a function of k for all λ < 1/8.Source: §K.3 · p. 51
  • Choosing an appropriate constant C′_{k,|I|} completes the proof of the lemma.The supplied passage states completion through this constant choice but does not include the lemma’s resulting bound.Source: §K.3 · p. 51

K.4 Bounding the Off-Diagonal Correlations of a Projection Matrix

This section develops the projection-matrix bounds, notation, and proof infrastructure underlying the inductive Master Theorem. It advances the induction through rank and zero stability, covariance and projection identities, and Gaussian-conditioning estimates showing the relevant error terms converge almost surely to zero.

K.4 Bounding the Off-Diagonal Correlations of a Projection Matrix

  • For an orthogonal projection matrix Π, every diagonal entry satisfies 0 ≤ Π_ii ≤ 1.Source: §K.4 · p. 51
  • After normalizing Π by its positive diagonal, the resulting correlation matrix C has off-diagonal correlations controlled by the projection’s rank deficiency.Source: §K.4 · p. 51
  • The proof constructs a dual solution to a linear program over squared off-diagonal correlations, using the ordered diagonal profile, its concave integral, and a reflected piecewise function.Source: §K.4 · pp. 52–53
  • A simpler argument partitions indices by whether Π_ii ≥ 1/2, uses |J̄| ≤ 2r, and separately bounds the resulting off-diagonal sums.Source: §K.4 · p. 55

K.5 Law of Large Numbers for Images of Weakly Correlated Gaussians

  • For weakly correlated Gaussian images, the stated convergence results require nonzero variances, bounded normalized correlations, and suitable finite moments; projection matrices satisfy the correlation condition through their rank-deficiency bound.Source: §K.5 · pp. 55–57
  • The weak-law result permits the correlation bound R(n) to grow like n^(1−ε) when the relevant moments are uniformly bounded, while the presented theorem can be strengthened with more involved case analysis.Source: §K.5 · pp. 56, 59

A Bit of Notation and Terminology

  • CoreSet combines Basis and NullAvoid to reduce moment analysis and prevent limiting covariance ranks from dropping, enabling pseudoinverse convergence and Gaussian conditioning.The proof introduces rank stability and zero stability as consequences needed for the complicated inductive step.Source: A Bit of Notation and Terminology · p. 61

L.1 Preliminaries: Square-Integrable Random Variables and Matrix Notation

  • The preliminaries define mixed-type inner-product matrix multiplication and represent orthogonal projections through covariance matrices and pseudoinverses.Matrices involving square-integrable random variables multiply through inner products, while projection coefficients use Λ+ and covariance vectors.Source: §L.1 · pp. 61–62

L.2 Preliminaries: Adjunction Relation Between ˆZ and ˙Z

  • Lemma L.3 proves the adjunction identity E ˆZ_u Z_h = E Z_v ˙Z_g for g = Wh and u = Wᵀv, with a variable-dimension factor ρ when applicable.The proof uses Gaussian conditioning, covariance projections, and the fact that ˙Z_g lies in the span of the relevant Z-vectors.Source: §L.2 · pp. 62, 64

L.3 Base Cases: Moments and CoreSet for Initial Vectors

  • For initial vectors V, Moments follows from the strong law of large numbers, while CoreSet follows by selecting a linearly independent subset whose Z-vectors form a basis.The selected core set satisfies Basis, Density, and NullAvoid.Source: §L.3 · p. 65

L.4 Inductive Case: Setup

  • The inductive setup conditions the new matrix A on prior variables, expressing g = Ah through constrained Gaussian structure and fixed-dimensional covariance matrices Υ, Λ, and Γ.Under the induction hypothesis, these matrices and associated quantities converge almost surely to deterministic limits; the conditional randomness is isolated in z.Source: §L.4 · p. 65, §L.4.1 · p. 65

L.4.1 Definitions

  • Proposition L.5 gives Υ+ → ˚Υ+ and Λ+ → ˚Λ+ almost surely, while Lemma L.6 shows σ converges almost surely to a deterministic limit ˚σ.These conclusions rely on eventual equality of the ranks of the finite-dimensional covariance matrices and their limits.Source: §L.4.1 · p. 66

L.4.2 Helper Lemmas

  • Helper lemmas derive projection-matrix identities by expanding definitions and using linear-combination relations among the relevant variables.These identities connect Π, Π⊥, and the auxiliary quantities used later in the induction.Source: §L.4.2 · pp. 67–68

L.4.3 Index of Symbols

  • The symbol index records the definitions and equation locations for the variables, projections, auxiliary quantities, and σ-algebra used in the proof.It lists g, h, φ; x_i, y_i, u_j, v_j; X, Y, U, V; Π_V, Π_Y; E; ω, σ; and the derived symbols.Source: §L.4.3 · p. 68

L.5 Rank Stability and Zero Stability

  • Lemma L.11 proves that K and its limit ˚K eventually have identical kernels, images, and ranks almost surely.The result applies to random matrices built from polynomially bounded functions and also preserves rank under suitable principal restrictions.Source: §L.5 · pp. 68–69

L.6 Inductive Step: CoreSet(m)

  • The CoreSet induction establishes that Moments(m −1) and CoreSet(m −1) imply CoreSet(m), explicitly considering whether to add m to core set M to maintain Basis, Density, and NullAvoid properties.Source: §L.6 · p. 70

L.6.1 If ˚σ = 0.

  • When ˚σ = 0, the existing core set is retained because the new variable is asymptotically a fixed linear combination of earlier variables.Basis remains valid, while Density and NullAvoid follow from the induction hypothesis.Source: §L.6.1 · p. 71

L.6.2 If ˚σ > 0.

  • When ˚σ > 0, the new variable is added to the core set, and conditional absolute continuity establishes Density and NullAvoid for the enlarged set.The proof also shows the relevant projection matrix has no zero diagonal entries, using nonsingularity derived from convergence and Sherman-Morrison arguments.Source: §L.6.2 · pp. 71–73

L.7 Inductive Step: Moments(m)

  • The Moments(m) induction begins by reducing the ˚σ = 0 case to a fixed linear combination and restricting the remaining proof to ˚σ > 0.For any polynomially bounded ψ : R^m → R, Moments is immediate in the zero-variance case.Source: §L.7 · p. 74
  • The inductive-step proof decomposes the argument into A, B, and C, with each shown to converge almost surely to 0.The passage states that this would complete the proof of Theorem 2.10.Source: §L.7 · pp. 74–75

L.7.1 C Converges Almost Surely to 0

  • An inductive argument makes the Z variables polynomially bounded functions of Zg1, . . . , Zgm−1, enabling definition of the function Ψ.The proof then invokes Lemma L.19 and Gaussian conditioning for jointly Gaussian variables.Source: §L.7.1 · pp. 75–76

L.7.2 A Converges Almost Surely to 0

The proof establishes almost-sure convergence of A and B to zero by combining moment bounds, induction hypotheses, and uniform-boundedness arguments. For B, a smoothness bound for Ψα and the bounded-rank complement of J control the remaining terms.

L.7.2 A Converges Almost Surely to 0

  • The proof conditions on amenable sequences, applies a moment bound, and then removes the conditioning because almost all sequences are amenable.Source: §L.7.2 · p. 77
  • A converges almost surely to a deterministic value, and therefore is almost surely uniformly bounded in n.Source: §L.7.2 · pp. 78–79

L.7.3 B Converges Almost Surely to 0

  • B converges almost surely to zero by decomposing its error terms, controlling four summands uniformly, and using the smoothness of Ψα.Source: §L.7.3 · pp. 79–81

L.7.2 A Converges Almost Surely to 0

  • Polynomial boundedness of the nonlinearities is required because faster-growing compositions may not be integrable against the Gaussian measure.Source: §L.7.3 · p. 79

L.7.3 B Converges Almost Surely to 0

  • The partition J ⊔ ¯J uses J={α:dα≥1/2}, while |¯J|≤2 rank V≤2s remains uniformly bounded as n grows.Source: §L.7.3 · p. 80
  • Gaussian averaging supplies the smoothness bound for Ψα, allowing the perturbation terms to be shown almost surely o(1).Source: §L.7.3 · pp. 80, 81, 84

M Proof of NETSOR⊤+ Master Theorem Assuming Rank Stability

The appendices extend the NETSOR⊤+ Master Theorem first under rank stability and then without that assumption. The proofs use induction on moments, parameter-fluctuation control, and a decomposition into bounded- and vanishing-moment components.

M Proof of NETSOR⊤+ Master Theorem Assuming Rank Stability

M.2 Fluctuation of the Parameters

  • The parameter theorem assumes Θ converges almost surely to a deterministic vector, and deterministic scalar parameters are handled as a consequence.Source: §M.2 · p. 84
  • Parameter-controlled nonlinearities add a term D to Eq. (69), while the original terms A, B, and C converge almost surely to zero as before.Source: §M.2 · pp. 84–85, §M.3 · p. 85

N Proof of NETSOR⊤+ Master Theorem without Assuming Rank Stability

N.1 Induction Hypotheses

  • The induction preserves rewrite, moment-convergence, orthogonality, and vanishing-moment invariants, with the base case initialized by Gram-Schmidt and the Strong Law of Large Numbers.Source: §N.1 · pp. 85–86, §N.2 · p. 86, §N.3 · p. 86

N.3 Induction

  • Each new vector is split into a component depending only on bounded-moment variables and a residual with vanishing moments, then projected onto the maintained orthogonal system.Source: §N.3 · pp. 86–87
  • The residual A∆h has vanishing moments because it decomposes into a Gaussian component with vanishing second moment and linear combinations of vectors with vanishing moments.Source: §N.3 · p. 87
  • Lemma N.3 transfers vanishing moments through pseudo-Lipschitz functions when bounded-moment variables, vanishing-moment variables, and convergent scalar parameters are combined.Source: §N.3 · pp. 86–87

Related papers

Loading 2009.10685v3…