Steps Toward Deep Kernel Methods from Infinite Neural Networks

1 Introduction

• Deep networks can have far more parameters than training examples yet often avoid overfitting and exhibit smooth decision boundaries.The paper proposes studying deep, infinitely wide networks, with uncountably infinite parameters, to help explain this behavior.Source: §1 · p. 1
• Prior infinite networks encode information from only a single layer and interact linearly with inputs, limiting representation power; these works do not explain why likelihood learning avoids overfitting.Single-infinite-intermediate-layer networks were studied as universal approximators and in Gaussian-process and kernel-method contexts.Source: §1 · pp. 1–2
• The work extends infinite-network kernel methods to multiple layers using stochastic kernels derived from Gaussian processes that encode two infinitely wide layers.The two layers are associated with functions indexed by w and u, respectively.Source: §1 · p. 2, Figure 1 · p. 2
• A generalization bound based on stability of regularized loss minimization is provided, and the learned deep network's simplicity is attributed to fast convergence of learning algorithms.Source: §1 · p. 2
• The method relates first-layer learning units to Gaussian-distribution integrals over Euclidean-space functions, then relates second-layer units to expectations over a Gaussian process.Those expectations form stochastic kernel functions encoding the multilayer network.Source: §1 · p. 2
• The framework also introduces a method for incorporating localities and nonlinearities, including those arising in convolutional neural networks.Source: §1 · p. 2

• Single-hidden-layer networks combine weighted nonlinear activations, and they are universal approximators as the number of units grows.The activation function transforms each unit’s linear response; ReLU and step functions are examples.Source: §2 · p. 3
• Infinite networks replace sums over units with integrals over weight vectors under a probability measure.The measure may be any probability distribution for which the integral is finite, including a Gaussian distribution.Source: §2 · p. 3
• For learning an infinite single-hidden-layer network, kernel methods represent its classifier dually, restricting the learned function to the span of training features and evaluating kernel entries.The input-dependent feature is φ_x(w) = f(⟨x, w⟩).Source: §2 · p. 3
• Prior work derives analytic Gaussian-measure kernels for rectified-linear and sign transfer functions.Source: §2 · p. 3
• For non-Gaussian measures, kernels lack analytic solutions; with a log-concave density, kernel-function sample complexity decays exponentially with the number of samples.Source: §2 · p. 4

3 Stochastic kernels for deep and infinitely wide neural networks

• Deep infinite layers require function-valued parameters: second-layer neurons weight first-layer response functions, and the output layer weights the resulting activations over functions.The section develops its framework using two intermediate layers.Source: §3 · p. 4
• The framework treats the functions defining neurons as draws from a Gaussian process, which is specified by its mean and covariance; the paper assumes zero mean and general covariance.Finite collections of values from the process have multivariate Gaussian distributions.Source: §3 · pp. 4–5
• The stochastic kernel averages nonlinear first-layer responses while accounting for their covariances, and suffices for learning a deep infinite network that linearly separates training examples.The network’s second-layer activations are integrated against a measure, and the output layer similarly weights the resulting activations.Source: §3 · pp. 4–5
• Gaussian-process properties make it possible to compute the stochastic kernel analytically despite the process having infinitely many random variables.The kernel computation reduces expected values involving Gaussian variables to a bivariate Gaussian distribution.Source: §3 · p. 5
• For shift-invariant covariance functions, Bochner’s theorem represents the covariance using features sampled from a corresponding measure, enabling efficient kernel computation when that measure is known.The measure can be recovered from the covariance function by inverse Fourier transform.Source: §3 · p. 6
• For a squared-exponential covariance, Corollary 2 gives analytic forms for the deep stochastic-kernel covariance matrix and the step kernel.The covariance couples independent Gaussian vectors into a correlated joint Gaussian.Source: §3 · pp. 6–7
• With ReLU activations, kernel entries are computed by recursively applying h to the appropriate Gaussian parameters.The passage defines h as the expected product of two ReLU-transformed jointly Gaussian variables.Source: §3 · p. 7
• For multiclass prediction, the framework uses one decision boundary per class and selects the class with the largest output score.The paper notes that its preceding formulation focuses on binary classification for notational convenience.Source: §3 · pp. 7–8

• With margin-separated data and m ≫ t, passive-aggressive analysis restricts the deep learner’s capacity, provided ∥ψx∥2 ≤ R.The section motivates this by noting that linear decision functions are finite sums of training-example functions, so their capacity is limited when those functions are simple.Source: §4 · p. 8
• The dual optimization is strongly convex and smooth, and early stopping can yield a simple separator with O(log(1/ϵ)) functions ψx(u).The cited passage says dual exponentiated coordinate descent reaches an ϵ-optimal dual solution in O(log(1/ϵ)) updates, while noting that this alone does not guarantee an ϵ-optimal primal solution.Source: §4 · p. 9
• With ∥φx∥≤1 and independently sampled training examples, Theorem 2 bounds the log-risk gap for vS by 1/mλm.The passage identifies the log-risk gap as |LD(vS) − LS(vS)| and states that λm is chosen so mλm goes to zero as m tends to infinity.Source: §4 · p. 9
• The stochastic kernel completely separated MNIST training data in 50 iterations, whereas the single-layer kernel nearly—but not completely—separated it.The paper presents this as evidence that the stochastic kernel is more expressive than the single-layer kernel.Source: §4 · pp. 9–10
• On MNIST, the stochastic kernel’s average error was 1.7%, versus 1.9% for the single-layer kernel, a 0.2% improvement.The paper describes this as about a 10% gain relative to the single-layer kernel’s error.Source: §4 · p. 10

5 Non-linearities

• Global linear interactions in the described infinite layers ignore spatial information, limiting their expressive power for applications such as computer vision and language processing.The paper notes that convolutions exploit spatial information through overlapping data subsets and introduce locality and non-linearity.Source: §5 · p. 10
• In the first intermediate layer, each input subset x(p) receives infinitely many responses φx,p(w) = f(⟨w, x(p)⟩), forming a P-dimensional feature function.This extends the earlier feature function from mapping Rd to R to mapping Rd1 to RP.Source: §5 · p. 10
• In the second intermediate layer, convolution operations restrict φx to coordinate subsets, weight each subset with u, and produce responses ψx,q(u) = f(⟨u, φx(q)⟩).The paper states that the appropriate kernels follow from a straightforward derivation of these higher-dimensional constructions.Source: §5 · p. 10

Related work

• Unlike dropout-based explanations [23], the approach represents large networks as infinite multilayer networks and uses early stopping and stability to explain their generalization.Its layers encode neuron responses as functions, with Gaussian processes in the second layer; the algorithm reaches an almost optimal solution in a few steps, yielding a simple, regularized classifier.Source: §6 · p. 11
• Unlike Bayesian infinite-network analyses, which study predictive probabilities and Gaussian-process limits, this work maximizes the likelihood of infinite layers and uses Gaussian processes to define a measure over deeper layers.It establishes prediction power through stability and considers multiple intermediate layers rather than a single infinitely wide intermediate layer.Source: §6 · p. 11
• Other infinite-network learning methods formulate an infinite convex program with an incremental dual algorithm [2] or use randomization to optimize a single-layer network.This work instead focuses on Gaussian-process construction of multiple layers and on how infinite networks avoid overfitting.Source: §6 · p. 11
• Where prior work introduced infinite-network kernels and kernel composition for deep architectures, this work builds layers from their predecessors using Gaussian processes and addresses overfitting.It also connects Gaussian processes and kernel methods and incorporates nonlinearities and invariances, including convolutional neural networks—open problems identified in.Source: §6 · p. 11
• The second-layer kernels have an unbiased estimate based on Bochner’s theorem for shift-invariant covariance functions, as in random-feature estimation.Improved variance-reduction methods and estimators used to match deep-learning results in language processing [13] are also discussed.Source: §6 · pp. 11–12

7 Discussion

• Deep infinite neural networks explain why highly overparameterized deep networks can generalize: stochastic Gaussian-process kernels encode them, while locality, non-linearity, generalization bounds, and regularity explain their architecture and resistance to overfitting.The paper addresses networks whose parameter counts exceed their training examples by orders of magnitude.Source: §7 · p. 12
• The framework is presented with two intermediate layers for simplicity; it extends to any depth, but higher layers may not use non-linearities.The analytic forms of stochastic kernels for arbitrarily deep layers with non-linearities remain largely open.Source: §7 · p. 12
• Open questions include which non-linearities matter in deep infinite networks, whether they can be learned from data, which probabilities best fit the framework, and whether process properties beyond covariance control learning.Source: §7 · p. 12