SGD Learns the Conjugate Kernel Class of the Network

Amit Daniely

Source-linked AI summary

SGD Learns the Conjugate Kernel Class of the Network

Amit Daniely

arXiv:1702.08503v2Feb 27, 2017cs.LGcs.DSstat.ML

TL;DR

The paper addresses the scarcity of success guarantees for standard SGD, especially beyond restricted depth-2 settings. It analyzes SGD through the conjugate kernel space associated with network architectures and shows that sufficiently large networks trained with suitable parameters learn any function in that space. The results imply polynomial-time learning for several function classes and learning of any continuous function without a polynomial-time guarantee.

Problem
Few results guarantee that standard SGD from random initialization succeeds, with prior guarantees restricted to settings such as depth-2 networks, Gaussian inputs, full gradient descent, and polynomial regression.
Method
The paper builds on the network-to-kernel framework and analyzes SGD for a broad family of architectures, with sufficiently large networks, small learning rates, and sufficiently many steps.
Results
SGD is guaranteed to learn any function in the corresponding conjugate kernel space, including polynomial-time learning of constant-degree polynomials with polynomially bounded coefficients and non-polynomial-time learning of any continuous function.
Takeaways & Limitations
The guarantees extend standard SGD theory to log-depth, fully connected and convolutional architectures and connect neural-network learning guarantees with the richness of conjugate kernel classes.
Takeaways & Limitations
The bounds have a rather large polynomial degree, and the theorem’s main-result assumptions include activation boundedness or Lipschitz and zero-value conditions.

Abstract

from arXiv · show

We show that the standard stochastic gradient decent (SGD) algorithm is guaranteed to learn, in polynomial time, a function that is competitive with the best function in the conjugate kernel space of the network, as defined in Daniely, Frostig and Singer. The result holds for log-depth networks from a rich family of architectures. To the best of our knowledge, it is the first polynomial-time guarantee for the standard neural network learning algorithm for networks of depth more that two. As corollaries, it follows that for neural networks of any depth between $2$ and $\log(n)$, SGD is guaranteed to learn, in polynomial time, constant degree polynomials with polynomially bounded coefficients. Likewise, it follows that SGD on large enough networks can learn any continuous function (not in polynomial time), complementing classical expressivity results.

1 Introduction

The paper addresses the lack of broad success guarantees for standard SGD by proving polynomial-time learning guarantees tied to a network’s conjugate kernel space. It derives implications for several function classes and positions the result against prior, more restricted analyses.

Motivation: Existing SGD guarantees are scarce and previously covered only depth-2 networks, Gaussian inputs, full gradient descent, and polynomial regression.The cited prior result is described as the only known guarantee in that restricted setting.
Main contribution: The conjugate kernel class is motivated by random initialization, after which changing only the final layer can approximate every kernel-space function.Approximation quality depends on network size and the function’s kernel norm, while final-layer optimization is convex.
Main contribution: SGD learns any function in the corresponding conjugate kernel space when the network, learning rate, and training duration satisfy polynomial resource conditions.The guarantee applies to a broad architecture family containing fully connected and convolutional networks, arbitrary input distributions, and general supervised learning tasks.
Implications: For depths from 2 through log(n), the conjugate class contains predictors with performance close to the learned function for standard convolutional networks on CIFAR-10.This empirical connection motivates evaluating the richness and predictive quality of the guaranteed function class.
Implications: Polynomial-time guarantees cover constant-degree polynomials with polynomially bounded coefficients, plus conjunctions, DNF formulas, and CNF formulas with constant-size structure.The cited exceptions include unrestricted-coefficient constant-degree polynomial thresholds, decision lists, and parities.
Implications: SGD can learn any continuous function with sufficiently large networks, though not necessarily in polynomial time.This complements universal approximation by adding a learning guarantee within the stated scope.

2 Preliminaries

The preliminaries define the learning setting, neural-network and kernel terminology, computation skeletons, and the generic SGD procedure analyzed later. Computation skeletons compactly specify network families and their associated normalized compositional kernels.

Learning setup: Inputs are sequences of n unit vectors, and supervised learning seeks a predictor minimizing expected loss over an i.i.d. sample.The setup supports arbitrary output spaces, output length k, and loss functions defined on predictions and labels.
Neural networks: Neural networks are weighted directed acyclic graphs whose non-input neurons apply normalized, square-integrable, left- and right-differentiable activations.Outputs aggregate incoming neuron values through learned weights, producing a k-dimensional network prediction.
SGD training: The analyzed training algorithm uses Xavier-style β-biased random initialization, back-propagated stochastic gradients, and updates of the form w_t+1 = w_t − ηv_t.Its inputs include learning rate, batch size, number of steps, bias parameter, and an optional zero prediction layer.
Kernel classes: A kernel induces a Hilbert space with a corresponding norm, and normalized kernels satisfy κ(x, x) = 1.Kernel SGD benchmarks compare expected loss against bounded-norm functions in the induced space; multiclass separability is defined relative to a kernel.
Computation skeletons: A computation skeleton is a single-output DAG with n inputs and labeled non-input nodes that compactly represents a family of feed-forward networks.Its realization uses replication parameter r for internal neurons and k output neurons; r corresponds to channels or hidden neurons in common architectures.
Computation skeletons: Each skeleton defines a normalized compositional kernel through conjugate activations, which take Gaussian correlations to expected products of activation outputs.The kernel is constructed inductively over skeleton nodes using the conjugate activation of each network activation.

3 Main results

The main results give SGD guarantees against the conjugate-kernel model class for broad network architectures, with implications for polynomial-time learning and continuous-function learning.

Main theorem: The guarantees cover zero-initialized prediction layers for C-bounded activations and ReLU activations under sufficiently large networks, small learning rates, and enough SGD steps.The ReLU case is stated separately, while the general theorem assumes C-bounded activations.
Main theorem: For constant-depth and several log-depth skeletons, the complexity quantities C(S) and C′(S) remain polynomial in n.This includes fully connected skeletons and layered skeletons with constantly many non-fully-connected layers.
Main theorem: SGD competes with the best bounded-norm function in the conjugate-kernel space under the stated theorem conditions.The guarantee holds for some iterate with high probability over initialization and expected loss over training examples.
Main theorem: With randomly initialized prediction layers, the result is restricted to multiclass classification with margin-separable data and logistic loss.The corresponding theorem assumes C-bounded activations and gives a probability bound over initialization and training examples.
3.1 Implications: SGD efficiently learns constant-degree polynomials with polynomially bounded coefficients, and consequently certain conjunction, DNF, and CNF classes.The polynomial guarantee compares against degree-t0 polynomials with coefficient norm at most n^t1; logistic or hinge loss yields the stated Boolean-class implications.
3.1 Implications: For sufficiently large networks, sufficiently small learning rates, and sufficiently many steps, SGD learns any continuous function, though not necessarily in polynomial time.The corollary assumes a continuous target on the sphere and a distribution realized by that target.
3.2 Extensions: The results extend to varying replication parameters and convolutional networks with weight sharing, while the stated analysis assumes fresh example batches at every step.With a fixed training set, the guarantee applies to training loss and transfers to population loss under sufficiently large samples.

4 Proofs

The proof formalizes the network through its skeleton, aggregated weights, node outputs, representation layer, prediction layer, loss, and induced kernel.

Objectives and kernel: Matrix norms and coordinatewise activation notation support the subsequent bounds on network weights and representations.The operator norm is bounded by the Frobenius norm, and scalar activations are applied coordinatewise to vectors.
Network notation: The network weights are aggregated over internal nodes, biases, and a final prediction matrix.Each internal-node map combines outputs from incoming nodes, while the prediction matrix maps the representation to the final output.
Network notation: For an input x, R_v^x(W) denotes the output at node v, and R_x(W) denotes the representation-layer output.The network output is obtained from the representation through the prediction layer.
Objectives and kernel: The paper defines pointwise loss ℓ_(x,y)(W), population loss L_D(W), and kernel k_W(x,x′) from representation inner products.The kernel is k_W(x,x′) = ⟨R_x(W), R_x′(W)⟩.

4.1 Overview

The proof starts from a good random initialization supplied by the kernel approximation framework, then shows SGD preserves this advantage while optimizing the final layer.

Proof strategy: With high probability over initialization, a prediction matrix W* has small loss at the initial representation and bounded Frobenius norm.The construction extends prior results to general output dimension k and removes a logarithmic dependence on the support size of the distribution.
Proof strategy: If SGD updates only the last layer, online-learning results yield a step with expected loss at most 2ϵ.This guarantee uses the specified learning rate and the existence of W*.
Proof strategy: For full-network SGD, the proof shows that non-last-layer weights change slowly enough to preserve the small loss obtained with W* throughout optimization.The online-learning argument can then be invoked again.
Proof strategy: Gradient bounds depend on spectral norms of the network matrices, which are controlled with high probability for random matrices.These bounds apply to both example losses and their averages, including the population and training objectives.
Proof strategy: The proof for the classification result uses a different route because the initial prediction layer is random rather than zero.It controls the gradient direction while the lower-layer weights move slowly, then applies smooth-convex-optimization arguments.

4.2 Boundness of the objective function

This section establishes boundedness of network representations and losses by propagating value, gradient, and Hessian bounds through affine maps, concatenation, activations, and losses.

Bound propagation: A function is (α, β, γ)-bounded when its value, gradient, and Hessian are controlled along every one-dimensional direction.For scalar functions, this corresponds to bounds on |f|, ∥∇f∥, and ∥∇²f∥.
Objective bounds: The logistic-loss example supplies a concrete classification loss whose derivatives fit the boundedness framework.The loss is defined through the softmax probabilities p_i(ŷ).
Bound propagation: Affine transformations, concatenation, and composition with bounded activations preserve boundedness with explicitly transformed parameters.The stated facts provide the algebraic rules used to propagate these bounds through network layers.
Network induction: Under C-bounded activations, the loss and representation satisfy bounds whose scale grows with network depth, parameter radius, computation size, and replication dimension.Lemma 10 gives β = 4C′R(4CR)^depth(S)p comp(S)r for the loss and β = (4CR)^depth(S)p comp(S)r for the representation.
Network induction: The induction tracks boundedness from input nodes through internal nodes and the representation layer.Input functions start with (1, 0, 0)-boundedness, and the network construction propagates the bounds by depth.
Objective bounds: Under Lipschitz activations and loss, the objective has separate bounds for internal and prediction-layer variables.The bounds differ by factors involving R and the loss Lipschitz constant L; bounded activations additionally control the representation output.

4.3 Optimization given good initialization

Given a suitable initialization and a bounded prediction matrix, the optimization analysis shows that SGD reaches a step with expected loss close to the initialized representation’s comparator loss.

Assumptions and stability: Throughout optimization, stochastic gradients remain bounded and internal weights move by controlled amounts per step.The resulting trajectory-length bound controls how much the representation changes from initialization.
Assumptions and stability: The analysis sets a learning rate and assumes initialization, comparator-norm, and approximation conditions sufficient for the SGD guarantee.The comparator W* has Frobenius norm at most M√r, while the initial prediction layer is zero.
Comparator stability: There exists an iteration t ∈ [T] with expected loss at most LD(W_0|W*) + 3ϵ.The result follows by applying online convex optimization to the prediction layer while controlling representation drift.
Comparator stability: The representation-loss comparator satisfies LD(W_t|W*) ≤ LD(W_0|W*) + Mtηα^2.This connects lower-layer movement to the initial comparator loss and the optimization horizon.
Classification optimization: The proof also bounds the number of iterations before some iterate achieves a sufficiently small excess-error quantity.The argument combines nonnegativity of expected loss with a per-step progress estimate.

4.4 Initial conditions

This section develops finite-support representations for kernel-space functions and connects them to perceptron and SGD guarantees, then establishes initialization conditions for neural-network kernels.

4.4.1 Finite support representation of kernel space functions: Kernel-space functions can be represented as finite sums of kernel evaluations, with coefficient vectors controlling classification accuracy.The representation uses terms of the form a_iκ_xi and is used to approximate functions in H_κ.
Perceptron and kernel-space learning: The perceptron makes at most (2 + 2a)M^2 mistakes and returns a matrix whose Frobenius norm is at most (2 + 2a)M.The guarantee assumes a separating matrix W* with Frobenius norm at most M and zero loss on every example.
Perceptron and kernel-space learning: SGD reaches expected loss within ϵ of the comparator after M^2L^2/ϵ^2 iterations under convex, L-Lipschitz loss and projection onto the radius-M ball.Each update contributes a rank-one matrix, yielding a finite-support representation with controlled norm.
4.4.2 Initial conditions: With probability at least 1 − δ, random initialization admits a prediction matrix W* with ∥W*∥F ≤ 2M√r and loss at most the kernel comparator loss plus ϵ.The result is stated for both bounded-activation and ReLU skeletons, with depth- and width-dependent conditions.
4.4.2 Initial conditions: For C-bounded activations, the required width scales with depth, activation bound, M, and logarithmic confidence factors, while r ≥ k ensures an initialization condition.The main theorem derivation combines the initialization corollaries with bounds on the loss at random initialization.