PaperlayerView exact revision on arXiv

Source-linked AI summary

Tensor Programs I: Wide Feedforward or Recurrent Neural Networks of Any Architecture are Gaussian Processes

Greg Yang

arXiv:1910.12478v3cs.NEcond-mat.dis-nncs.LGmath-ph

TL;DR

The paper addresses whether infinitely wide, randomly initialized neural networks beyond previously studied architectures converge to Gaussian processes. It introduces NETSOR and a variable-dimensional GP formulation, and reports convergence across standard feedforward and recurrent architectures, with empirical verification for several examples.

  • Problem

    The paper asks whether all infinitely wide, randomly initialized neural networks correspond to Gaussian processes, beyond the architectures covered by earlier results.

  • Method

    The paper introduces variable-dimensional Gaussian processes, expresses standard neural-network computations in NETSOR, and analyzes expressible programs as dimensions tend to infinity.

  • Results

    Randomly initialized wide feedforward and recurrent networks of standard architectures converge in distribution to Gaussian processes, with empirical verification for simple RNN, GRU, transformer, and batchnorm networks.

  • Takeaways & Limitations

    The NN-GP correspondence extends to compositions involving MLPs, recurrent networks, convolutions, pooling, skip connections, attention, and normalization, as well as all NETSOR-expressible networks.

  • Takeaways & Limitations

    The paper excludes forward computations using both a weight matrix and its transpose and establishes convergence only for finite-dimensional marginals.

Abstract

from arXiv · show

Wide neural networks with random weights and biases are Gaussian processes, as originally observed by Neal (1995) and more recently by Lee et al. (2018) and Matthews et al. (2018) for deep fully-connected networks, as well as by Novak et al. (2019) and Garriga-Alonso et al. (2019) for deep convolutional networks. We show that this Neural Network-Gaussian Process correspondence surprisingly extends to all modern feedforward or recurrent neural networks composed of multilayer perceptron, RNNs (e.g. LSTMs, GRUs), (nD or graph) convolution, pooling, skip connection, attention, batch normalization, and/or layer normalization. More generally, we introduce a language for expressing neural network computations, and our result encompasses all such expressible neural networks. This work serves as a tutorial on the *tensor programs* technique formulated in Yang (2019) and elucidates the Gaussian Process results obtained there. We provide open-source implementations of the Gaussian Process kernels of simple RNN, GRU, transformer, and batchnorm+ReLU network at github.com/thegregyang/GP4A.

1 Introduction

The paper asks whether all infinitely wide, randomly initialized neural networks correspond to Gaussian processes and develops a general framework to answer this across standard architectures.

  • Motivation: Prior NN-GP results focused mainly on multilayer perceptrons and selected convolutional networks.The paper frames its contribution as extending this correspondence beyond those previously studied cases.
  • Contribution: The paper introduces Gaussian processes with variable-dimensional outputs to handle recurrent neural networks.This formulation accommodates outputs whose dimensions depend on input sequence lengths.
  • Contribution: The result covers compositions of MLPs, RNNs, convolutions, graph convolutions, pooling, skip connections, normalization, and attention.The listed recurrent architectures include LSTMs and GRUs.
  • Contribution: NETSOR provides a language for expressing neural network computations, and GP convergence for expressible networks yields the architecture results as a corollary.The paper also presents example kernel implementations for simple RNNs, GRUs, transformers, and batchnorm networks.
  • Scope: This paper excludes architectures whose forward pass uses both a weight matrix and its transpose.The authors state that this case is deferred to later work.

2 Gaussian Process with Variable-Dimensional Output

A Gaussian process with variable-dimensional output treats all outputs over finitely many inputs as one jointly Gaussian vector, allowing recurrent outputs of different lengths to fit the GP framework.

  • Definition: For an RNN, Gaussian-process behavior requires jointly Gaussian outputs whose total dimension varies with the input sequence lengths.The definition generalizes the fixed-output case by using the sum of output lengths across inputs.
  • Example: A simple RNN processing sentences of 7 and 9 words emits 7 and 9 scalars, respectively, producing 16 outputs together.The outputs include one scalar after each token and reflect all embeddings read so far.
  • Example: A width-1000 RNN empirically exhibits the predicted joint Gaussian distribution for the sentence outputs.The visualization compares the empirical distribution with the theoretically predicted Gaussian distribution.

3 Recap: GP Behavior of a Multilayer Perceptron (MLP)

For wide MLPs, conditioning on previous-layer activations makes each neuron’s paired outputs Gaussian, while a law-of-large-numbers argument drives covariances toward deterministic limits across layers.

  • MLP setup: An MLP recursively applies affine transformations and nonlinearities across layers.The computation begins with h1(x) = W 1x + b1 and continues as hl(x) = W lφ(hl−1(x)) + bl.
  • Layerwise argument: Conditioned on previous-layer activations, each neuron’s outputs for two inputs are jointly Gaussian when weights are independently randomized.The resulting covariance depends on the previous activations and the nonlinearity.
  • Layerwise argument: As the preceding width n_l−1 tends to infinity, the covariance converges to a deterministic limit by a law-of-large-numbers argument.This produces a Gaussian distribution with covariance Σ_l for the next layer.
  • Conclusion: Iterating the argument over layers establishes GP behavior for deep MLPs, with similar reasoning applying to feedforward CNNs.The result relies on the independent-weight structure used in the layerwise argument.
  • Limitation: The argument breaks down for RNNs because tied weights are no longer conditionally iid after conditioning on previous preactivations.The paper motivates a broader framework rather than relying only on an ad hoc Gaussian conditioning repair.

4 NETSOR : Language for Expressing Neural Network Computation

NETSOR expresses neural-network computations through typed variables and simple operations, enabling a general large-dimension analysis that covers standard architectures and parameter-dependent nonlinearities.

  • Language design: NETSOR represents computations with G, H, and A variables corresponding to Gaussian-like vectors, nonlinear images, and iid Gaussian matrices.Each variable type carries dimensionality information.
  • Core operations: Its core rules are matrix multiplication, linear combination, and coordinatewise nonlinear transformation.These rules encode the intended Gaussian, linearity, and nonlinear-image operations.
  • Outputs: NETSOR outputs tuples of normalized scalar readouts from H-vars using G-var readout vectors.The output form is (v1⊤y1/√n1, . . . , vk⊤yk/√nk).
  • Examples: NETSOR programs can encode MLP and simple RNN computations, including shared recurrent weights, embeddings, biases, nonlinearities, and readouts.The examples show how standard network computations map onto the language’s typed operations.
  • Scope: The paper’s framework excludes matrix transposes from the present tensor-program operations.The authors note that allowing transposes can make matrix-vector products far from Gaussian and defer that setting to future work.
  • Extensions: NETSOR+ allows nonlinearities to depend on parameters, including continuous functions of empirical moments.These empirical moments converge almost surely to deterministic limits, making the induced nonlinearity approximately fixed at large dimension.

5 Computing the GP Kernel from a NETSOR Encoding of a Neural Network

The NETSOR Master Theorem characterizes large-width tensor-program behavior through Gaussian expectations, yielding computable Gaussian-process kernels for broad neural-network architectures. The theory is empirically predictive for finite-width RNNs and other architectures.

  • NETSOR framework: NETSOR expresses standard neural-network architectures, and programs satisfying mild conditions exhibit Gaussian-process behavior as width grows.The framework covers architectures expressible in NETSOR, including recurrent and feedforward networks.
  • Gaussian characterization: Under Assumption 5.1, randomized weights, biases, and input variables define recursive mean and covariance quantities for the program’s Gaussian variables.The covariance construction uses Gaussian expectations of nonlinear transformations and avoids circularity because each transformation depends only on prior variables.
  • Assumptions: Controlled nonlinearities permit broad, potentially nonsmooth functions whose growth still ensures Gaussian integrability.The definition allows functions growing faster than exponential while remaining L1- and L2-integrable against Gaussian measures.
  • Master theorem: The NETSOR Master Theorem states that empirical averages of controlled functions converge almost surely to expectations under a Gaussian vector with the recursively defined mean and covariance.This theorem is the central analytical step for computing wide-network observables.
  • Kernel computation: For outputs of the form (v⊤x1/√n, …, v⊤xk/√n), the limiting distribution is N(0, K), with K determined by Gaussian expectations of the corresponding nonlinear features.The finite-width output is conditionally Gaussian, while its covariance converges to a deterministic kernel.
  • Empirical validation: Width-1000 simple RNN simulations closely match the predicted Gaussian distribution, while kernels for simple RNNs, GRUs, transformers, and batchnorm+ReLU converge in finite-width experiments.The RNN demonstration uses GloVe-embedded sentences and erf activation; the broader kernel comparisons include finite-width simulations across architectures.

6 Related Works

The paper extends prior neural-network–Gaussian-process work while connecting its framework to signal-propagation analyses and reservoir computing. Its main distinction is broader architectural and nonlinearity coverage.

  • NN-GP correspondence: Prior work established the neural-network–Gaussian-process correspondence for selected neural-network architectures and used it to construct Gaussian-process models.The paper positions its contribution against earlier results for restricted architecture classes.
  • NN-GP correspondence: This paper generalizes the correspondence to standard architectures and controlled nonlinearities, beyond several prior assumptions on boundedness, differentiability, or activation type.The comparison cites prior requirements including linear growth, twice differentiability, bounded derivatives, or ReLU-specific conditions.
  • Signal propagation: Signal-propagation studies compute related covariance recursions but generally use more restricted architectures and emphasize covariance dynamics with depth.Those studies often investigate initialization schemes intended to avoid gradient vanishing.
  • Reservoir computing: In reservoir computing, the infinite-width randomly initialized recurrent network corresponds exactly to Gaussian-process inference using the RNN kernel.Only the readout layer is trained in the described reservoir-computing setup.

7 Conclusion

The paper formulates variable-dimensional Gaussian processes and proves convergence for randomly initialized wide feedforward and recurrent networks with standard architectures. NETSOR supplies the expressive language and theorem underlying this generalization.

  • Conclusion: Randomly initialized, wide feedforward and recurrent networks of standard architectures converge in distribution to Gaussian processes with variable-dimensional outputs.The convergence is stated as widths or channel counts tend to infinity.
  • Conclusion: NETSOR expresses standard deep-learning computations, and the NETSOR Master Theorem characterizes their behavior when tensors are randomized and dimensions grow.This provides the proof framework for the paper’s generalized correspondence.

A Writing Standard Architectures in NETSOR

NETSOR expresses standard neural-network architectures as compositions of a small set of tensor operations, enabling the paper’s GP-convergence framework to cover convolutions, pooling, recurrent units, normalization, attention, and skip connections.

  • NETSOR building blocks: NETSOR represents neural computations as composable gadgets, and compositions of these gadgets express the showcased architectures.The examples include batchnorm, skip connections, convolution, pooling, GRU/LSTM, and scaled attention.
  • Normalization and attention: Batch normalization, layer normalization, and attention are expressed using nonlinear operations whose coefficients or attention scores converge to deterministic limits.For attention, q⊤k_i/n converges almost surely to a deterministic limit under the stated framework.
  • Convolution and pooling: Convolutional computations are expressed through matrix multiplications that reuse convolution weights across spatial positions.Higher strides and general graph convolutions can be expressed similarly.
  • Convolution and pooling: Pooling operations reduce feature maps through global averaging or local maxima while remaining expressible in the same notation.The examples cover global average pooling and 2 × 2 max pooling with stride 2.
  • Recurrent architectures: GRU and LSTM computations require unrolling gated recurrent states so coordinatewise nonlinearities can be applied to G-vars.The gates use sigmoid and the candidate update typically uses tanh.
  • GP-kernel consequences: The resulting computations support GP-kernel calculations for CNNs and batch-normalized networks through recursive covariance constructions.The paper states that CNN outputs converge to Gaussian distributions with recursively computed kernels.

B.4.2 CNN with Multiple Inputs

For multiple inputs, the paper recursively constructs CNN covariance tensors and obtains an infinite-width Gaussian-process kernel, with vectorization enabling efficient computation.

  • Covariance initialization: The input covariance structure is initialized from convolutional receptive-field overlaps, with zero covariance assigned to other input G-variable pairs.The input mean is identically zero under the stated setup.
  • Recursive kernel construction: Layerwise means and covariances are propagated recursively through the convolutional network to produce the final kernel.The recursion uses the nonlinear covariance transform and spatial summations over kernel positions.
  • Vectorized computation: The covariance computation can be vectorized by treating the layer covariance tensor as a matrix and implementing the induced convolution operation computationally.The induced convolution can be implemented as a CUDA convolution vectorized over input pairs.
  • Final kernel: Spatial averaging completes the infinite-width CNN kernel after applying the nonlinear covariance transform at the final layer.The paper describes vectorizing the final spatial averaging operation as well.
  • Setup and result: A multiple-input L-layer CNN maps B images to outputs that converge in distribution to a Gaussian N(0, K).The kernel K is a B × B covariance matrix computed from the network’s recursive covariance quantities.
  • Related recurrent-kernel computation: For GRUs, kernel computation additionally requires high-dimensional Gaussian expectations representing products of gate values across timesteps.For erf-based nonlinearities, these expectations can be reduced to efficiently evaluated Gaussian orthant probabilities.

C NETSOR+ Master Theorem

The NETSOR+ Master Theorem extends convergence analysis to parametrized nonlinearities whose parameters converge almost surely to deterministic limits, under parameter-control and rank-stability assumptions. The paper explains why these assumptions matter and how recursive empirical-moment convergence supports the result.

  • Assumptions: Parameter-control requires approximation by a controlled function with an error bounded by a continuous factor that vanishes at the limiting parameter.The definition permits some discontinuous functions, including step(θx) when the limiting θ is nonzero.
  • Assumptions: Rank stability is an explicit assumption, although parameterless NETSOR programs obtain it automatically through the proof’s inductive rank and moment arguments.The paper notes that full-rank limiting covariance matrices are a common situation in which rank stability holds.
  • Master Theorem: Theorem C.4 covers parametrized nonlinearities when their parameters converge almost surely to a deterministic vector and the nonlinearities are parameter-controlled there.The theorem applies to all G-vars, including input G-vars, and yields Gaussian-limit behavior for controlled functions of them.
  • Proof structure: The proof must avoid circular reasoning because Theorem C.4 is used both for parameter convergence and for convergence of the empirical-moment equation.The authors introduce Theorem C.11 in Appendix C.1 as the primary practical tool for NETSOR+ programs.
  • Assumption failures: Without parameter-control, the Master Theorem can fail because an indicator nonlinearity changes discontinuously at the limiting parameter.For ψ(x; θ) = I(θx ≠ 0), the function is nonzero almost everywhere for θ ≠ 0 but identically zero at θ = 0.
  • Assumption failures: Rank stability can also fail when vectors converge to zero while remaining linearly independent at every finite width.The paper constructs this behavior using a scaling factor θ = exp(−n), showing why the assumption is needed.

C.1 Self-Parametrized NETSOR+ Programs and Their Master Theorem

Self-parametrized NETSOR+ programs extend tensor programs with scalar C-vars that serve as nonlinear parameters and converge almost surely to deterministic limits. Under parameter-control assumptions, their moments and outputs are computed recursively through a Master Theorem and yield Gaussian-process kernels.

  • Program definition: Recursive scalar parameters are represented explicitly through a scalar type, allowing dependencies on previously defined scalar variables.This notation untangles recursive parameters that could otherwise introduce circular logic.
  • Program definition: Self-parametrized NETSOR+ programs add scalar C-vars, which can parameterize nonlinearities and are intended to converge almost surely to deterministic constants.The syntax adds C-vars to the G- and A-vars of NETSOR programs, with Nonlin+ rules accepting parametrized functions.
  • Master Theorem: Theorem C.11 establishes the limiting moments and covariance structure of self-parametrized NETSOR+ programs through recursively defined µ, Σ, and C-var limits.The recursive expectations use a Gaussian vector Z ∼ N(µ, Σ) and only previously defined variables, removing circularity.
  • Master Theorem: The self-parametrized Master Theorem requires input C-vars to converge almost surely to deterministic limits and each parametrized nonlinearity to be parameter-controlled at its limiting parameters.The theorem uses simultaneous induction to establish both moment convergence and C-var limits without circular reasoning.
  • GP kernel: The output of a program with readouts (v^⊤x_1/√n, ..., v^⊤x_k/√n) converges in distribution to N(0, K), with K computed from limiting Gaussian expectations.For self-parametrized programs, the kernel replaces each parametrized nonlinearity with its deterministic limiting parameters.

D.3.5 Vectorized Implementation: Double Sequence

The double-sequence implementation computes a joint transformer Gaussian-process kernel by retaining covariances across tokens and across input sequences. The resulting token outputs converge jointly to a Gaussian distribution with covariance matrix K.

  • Kernel computation: The joint kernel includes covariances between embeddings of tokens within one sequence and between tokens from different sequences.The implementation summarizes these cross-sequence covariances through a vectorized tensor representation.
  • Kernel computation: For p input sequences of t tokens, transformer outputs—one scalar per input token—converge in distribution to N(0, K), where K has dimension pt × pt.The kernel is computed over all token positions across all sequences.
  • Vectorized implementation: The vectorized procedure processes transformer layers and sequences using masked, row-wise SoftMax attention and block-diagonal sequence structures.Each sequence contributes a diagonal block, while the full tensor represents all pairwise sequence covariances.
  • Vectorized implementation: An open-source implementation of the transformer-kernel algorithm is available in the GP4A repository.The passage explicitly directs readers to github.com/thegregyang/GP4A.

E Different Versions of Tensor Programs

The paper presents several semantically equivalent tensor-program languages and proves Master Theorems for them. NETSOR◦ permits nonlinearities to consume H-vars directly, while NETSOR− removes LinComb by absorbing it into downstream nonlinearities.

  • NETSOR− programs: NETSOR− removes the LinComb rule, while remaining semantically equivalent to NETSOR because linear combinations can be absorbed into downstream nonlinearities.This reformulation preserves the computation while changing the program representation.
  • Master Theorems: The NETSOR− and NETSOR◦ Master Theorems give Gaussian scaling-limit formulas for controlled functions of all G-vars under the stated program assumptions.The NETSOR◦ theorem additionally requires all unwinded nonlinearities to be controlled.
  • Parametrized limits: NETSOR+ empirical moments converge almost surely to deterministic limits, so parametrized nonlinearities behave intuitively like fixed nonlinearities at large width.This supports treating the nonlinearity as determined automatically by the tensor program.
  • NETSOR◦ programs: NETSOR◦ extends NETSOR by allowing nonlinearities to take H-vars, and NETSOR◦+ makes the same extension for parametrized nonlinearities.H-vars can therefore be reused without recursively expanding their definitions in the program syntax.
  • NETSOR◦ programs: For NETSOR◦ programs, H-vars are recursively unwound into functions of G-vars before computing the limiting mean and covariance.The extended µ and Σ calculations otherwise retain the same form.

F Programs with Variable Dimensions

Variable-dimensional NETSOR programs organize variables into Common Dimension Classes (CDCs), allowing dimensions to vary across classes. Under controlled nonlinearities and Gaussian input assumptions, their G-vars converge to Gaussian behavior as all program dimensions grow.

  • Variable-dimensional programs: Variable-dimensional NETSOR programs must satisfy dimensionality constraints for linear combinations, nonlinearities, and matrix multiplications.For matrix multiplication, input and output dimensions must match the corresponding matrix shapes.
  • Variable-dimensional programs: Common Dimension Classes group H-vars whose dimensions are tied together while allowing different classes to have different dimensions.The CDC partition is induced by input equivalence and dimensionality constraints.
  • Assumptions: Under Assumption F.3, input G-vars within each CDC are sampled independently across coordinates from a shared Gaussian distribution.The distribution is specified by a CDC-specific mean and covariance.
  • Master theorem: As all dimensions tend to infinity, controlled functions of the G-vars in any CDC converge to expectations under a Gaussian with limiting mean and covariance.The theorem requires all program dimensions to grow, not only the dimension of the selected CDC.
  • Proof tools: The proof extends the equal-dimension argument using Gaussian conditioning, pseudoinverse identities, and convergence results for conditioned Gaussian outputs.The conditioning lemmas characterize Gaussian matrices under linear constraints and their projections.

H Proof of NETSOR Master Theorem

The NETSOR Master Theorem is proved by simultaneous induction on moment convergence and a CoreSet property. The argument uses rank stability and Gaussian conditioning to establish the Gaussian limit for successive program variables.

  • Proof strategy: The proof inducts simultaneously on Moments and CoreSet rather than only on the number of program variables.CoreSet supplies basis and null-avoidance properties needed in the inductive argument.
  • CoreSet: Basis reduces moment analysis to core-set G-vars because every other G-var is asymptotically a linear combination of them.NullAvoid ensures the relevant distributions do not become singular on measure-zero sets.
  • Base cases: For input variables, moment convergence follows from the law of large numbers.The base CoreSet is any subset preserving the rank of the input covariance matrix.
  • Inductive step: Conditioning on previous G-vars expresses a newly formed matrix-multiplication variable through a conditional Gaussian mean and variance.The variance converges to a Schur-complement-like expression involving the limiting covariance.
  • Rank stability: Rank stability yields eventual equality of kernels, images, and ranks between random covariance matrices and their limits.This permits continuity of the Moore-Penrose pseudoinverse on fixed-rank matrices.

I Proof of NETSOR+ Master Theorem

The NETSOR+ proof extends the NETSOR argument to parameterized nonlinearities. It handles LinComb rules, assumes rank stability, and accounts for fluctuations in the nonlinear parameters through an additional vanishing term.

  • Proof modifications: The NETSOR+ proof differs from the NETSOR proof through LinComb rules, the rank-stability assumption, and parameter-fluctuation terms.These are the three structural changes highlighted in the proof setup.
  • LinComb: LinComb applications can be absorbed into downstream nonlinearities or expressed as Nonlin+ rules without loss of generality.The proof therefore focuses on NETSOR+ programs without explicit LinComb applications.
  • Rank stability: Rank stability is necessary for the NETSOR+ Master Theorem because it allows pseudoinverse operations to commute with almost-sure limits.Assumption C.3 replaces the more involved CoreSet induction used for NETSOR.
  • Parameter fluctuations: The parameterized limit equation contains an additional term D caused by fluctuations in the parameter Θ.Under parameter-control assumptions, the relevant terms converge almost surely to zero.

J Formal Specification of Tensor Programs

The formal specification presents tensor-program languages through grammars, inference rules, and semantics. Successive variants add linear combinations, self-parametrized scalar variables, and Moment expressions.

  • Formal specifications: NETSOR−, NETSOR, and self-parametrized NETSOR+ are formally specified by separate grammar, inference-rule, and semantics figures.The formal appendix uses explicit MatMul and Moment operations and double-colon type annotations.
  • Semantics: The NETSOR semantics interpret nonlinear expressions coordinatewise and linear combinations as vector sums.A function applied to G-vars produces an H-var whose coordinates apply the function to corresponding inputs.
  • NETSOR: NETSOR extends NETSOR− by adding LinComb as the only new expression item.The NETSOR grammar retains the underlying variable and operation structure while adding linear combinations.
  • Self-parametrized NETSOR+: Self-parametrized NETSOR+ adds type C and the Moment expression to NETSOR.C-vars represent random variables converging almost surely to deterministic limits and can parameterize nonlinearities.
Loading 1910.12478v3…