Deep Neural Network Foundations

1. The Universal Approximation Theorem

1.1 Classical Statement (Width-Based)

The Universal Approximation Theorem (UAT), first proved by Cybenko (1989) and later generalised by Hornik (1991), establishes that a feedforward network with a single hidden layer containing a finite number of neurons can approximate any continuous function on compact subsets of , provided the activation function is non-constant, bounded, and monotonically increasing.

Theorem 1.1 (Cybenko, 1989). Let be a sigmoidal activation function. For every continuous function and every , there exist an integer , real constants , and vectors such that

satisfies

The constructive proof uses the fact that the linear span of functions is dense in under the supremum norm.

1.2 Quantitative Bounds

While the classical UAT is an existence result, modern analyses provide quantitative approximation bounds. For Lipschitz-continuous functions, the width required grows polynomially in :

where is the compact domain and is the Lipschitz constant of .

For ReLU networks specifically, Telgarsky (2016) showed that depth- networks can compute functions that require exponential width to represent with depth :

1.3 Depth Efficiency

The depth efficiency result is profound. Consider the class of functions computable by ReLU networks:

Theorem 1.2 (Depth vs Width Tradeoff, Eldan & Shamir, 2016). There exists a function that can be represented by a ReLU network of depth 3 and width , but any ReLU network approximating to within using fewer than layers requires width .

This implies that depth is exponentially more parameter-efficient than width for certain function classes.

2. The Neural Tangent Kernel (NTK)

2.1 Definition and Motivation

The Neural Tangent Kernel provides a linearised description of neural network training in the infinite-width limit. Consider a network with parameters . The NTK is defined as:

In matrix notation, for a dataset , the NTK matrix is:

2.2 Infinite-Width Limit

For a fully-connected network with layers and width , as , the NTK converges to a deterministic kernel:

For a two-layer network with ReLU activation and Gaussian initialization :

where can be computed analytically:

where .

2.3 Training Dynamics

Under gradient descent with learning rate , the network function evolves as:

In the infinite-width limit, the training dynamics become linear:

This yields the solution:

2.4 NTK Regime vs Feature Learning

The NTK regime describes a scenario where the kernel remains approximately constant during training (the "lazy training" regime). This contrasts with the rich regime where features are actively learned:

3. Loss Landscape Geometry

3.1 Loss Surface Visualization

The loss surface is a function of where can be in the millions or billions.

Critical Points. A point is a critical point if:

The nature of the critical point is determined by the Hessian:

• Local minimum: (all eigenvalues positive)
• Saddle point: has both positive and negative eigenvalues
• Local maximum:

3.2 saddle Points and the Loss Landscape

For overparameterised networks (), the loss surface has a complex topology:

Theorem 3.1 (Li et al., 2018). For overparameterised neural networks with random initialisation:

1. All local minima have loss values close to the global minimum
2. Saddle points dominate the landscape (exponentially more than local minima)
3. Most critical points have (index > 0)

The fraction of saddle points among critical points grows exponentially with dimension:

3.3 Visualising Loss Contours

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import LogNorm

def loss_landscape_2d(model_fn, param_grid, data, labels):
    """
    Compute loss landscape along two random directions.
    
    Parameters
    ----------
    model_fn : callable
        Function mapping parameters to predictions
    param_grid : tuple of (v1, v2, center, resolution)
        Random directions and grid parameters
    data, labels : np.ndarray
        Training data and labels
    
    Returns
    -------
    Z : np.ndarray
        Loss values on the 2D grid
    """
    v1, v2, theta0, n = param_grid
    alphas = np.linspace(-1, 1, n)
    betas = np.linspace(-1, 1, n)
    
    Z = np.zeros((n, n))
    for i, a in enumerate(alphas):
        for j, b in enumerate(betas):
            theta = theta0 + a * v1 + b * v2
            preds = model_fn(theta, data)
            Z[i, j] = np.mean((preds - labels) ** 2)
    
    return Z

# Generate random directions
np.random.seed(42)
v1 = np.random.randn(1000) / np.sqrt(1000)
v2 = np.random.randn(1000) / np.sqrt(1000)

# Visualise
fig, axes = plt.subplots(1, 2, figsize=(14, 5))

# Contour plot
ax = axes[0]
Z = loss_landscape_2d(model_fn, (v1, v2, theta0, 200), X_train, y_train)
ax.contour(Z, levels=50, cmap='viridis', alpha=0.8)
ax.set_xlabel('Direction 1')
ax.set_ylabel('Direction 2')
ax.set_title('Loss Landscape Contours')

# Surface plot
ax = axes[1]
ax.plot_surface(np.arange(200), np.arange(200), Z, cmap='coolwarm')
ax.set_zlabel('Loss')
ax.set_title('3D Loss Surface')
plt.tight_layout()
plt.savefig('loss_landscape.png', dpi=150, bbox_inches='tight')

3.4 Overparameterisation and Interpolation

In the overparameterised regime (), the network can perfectly interpolate the training data:

Implicit Regularisation. SGD with small learning rate and appropriate initialisation tends to find solutions with minimum norm or minimum curvature:

This is the Neural Tangent Kernel perspective: the implicit bias of gradient descent in the infinite-width limit.

4. Gradient Flow Analysis

4.1 Backpropagation Equations

For a network with layers, the forward pass is:

The gradient with respect to parameters at layer is:

where the error signal is computed recursively:

4.2 Jacobian Chain Rule

The gradient through the network is:

The singular values of this Jacobian determine gradient magnitude:

4.3 Spectral Analysis of Training

The NTK eigenvalues at initialization determine learning speed for different function components. Let be the eigenfunction of corresponding to . Then:

High-eigenvalue modes (easy-to-learn features) converge quickly, while low-eigenvalue modes (hard-to-learn features) converge slowly:

5. Code Examples

5.1 Computing the NTK

import torch
import torch.nn as nn

def compute_ntk(model, x1, x2):
    """
    Compute the Neural Tangent Kernel matrix between two sets of inputs.
    
    For a network f(x; θ), K(x, x') = <∇_θ f(x), ∇_θ f(x')>.
    
    Parameters
    ----------
    model : nn.Module
        Neural network model
    x1, x2 : torch.Tensor
        Input tensors of shape (N1, D) and (N2, D)
    
    Returns
    -------
    K : torch.Tensor
        NTK matrix of shape (N1, N2)
    """
    def get_jacobian(output, inputs):
        """Compute Jacobian ∂f/∂θ."""
        batch_size = output.shape[0]
        jacobian = []
        
        for i in range(batch_size):
            model.zero_grad()
            output[i].backward(retain_graph=True)
            grads = []
            for param in model.parameters():
                if param.grad is not None:
                    grads.append(param.grad.view(-1).clone())
            jacobian.append(torch.cat(grads))
        
        return torch.stack(jacobian)  # (batch, num_params)
    
    # Forward pass
    f1 = model(x1)
    f2 = model(x2)
    
    # Compute Jacobians
    J1 = get_jacobian(f1, x1)  # (N1, p)
    J2 = get_jacobian(f2, x2)  # (N2, p)
    
    # NTK matrix
    K = J1 @ J2.T  # (N1, N2)
    
    return K

# Example: Compute NTK for a 2-layer ReLU network
class SimpleNet(nn.Module):
    def __init__(self, width=100):
        super().__init__()
        self.fc1 = nn.Linear(1, width, bias=False)
        self.fc2 = nn.Linear(width, 1, bias=False)
        nn.init.normal_(self.fc1.weight, std=1/width**0.5)
        nn.init.normal_(self.fc2.weight, std=1/width**0.5)
    
    def forward(self, x):
        return self.fc2(torch.relu(self.fc1(x)))

model = SimpleNet(width=500)
x = torch.linspace(-2, 2, 100).unsqueeze(1)
K = compute_ntk(model, x, x)

print(f"NTK matrix shape: {K.shape}")
print(f"NTK condition number: {K eigvals().max() / K eigvals().min():.2f}")

5.2 Visualising Loss Landscape

import torch
import numpy as np
import matplotlib.pyplot as plt

def create_loss_landscape(model, data, labels, directions=None, resolution=100):
    """
    Visualise loss landscape projected onto random directions.
    
    Parameters
    ----------
    model : nn.Module
        Trained model
    data, labels : torch.Tensor
        Training data and labels
    directions : tuple of (v1, v2), optional
        Random directions; if None, generate random ones
    resolution : int
        Grid resolution
    
    Returns
    -------
    fig : matplotlib Figure
    """
    if directions is None:
        # Generate random orthogonal directions
        flat_params = torch.cat([p.view(-1) for p in model.parameters()])
        v1 = torch.randn_like(flat_params)
        v2 = torch.randn_like(flat_params)
        v2 = v2 - (v2 @ v1) / (v1 @ v1) * v1  # orthogonalise
        v1 = v1 / v1.norm()
        v2 = v2 / v2.norm()
    else:
        v1, v2 = directions
    
    # Create grid
    alphas = np.linspace(-1, 1, resolution)
    betas = np.linspace(-1, 1, resolution)
    A, B = np.meshgrid(alphas, betas)
    
    # Compute loss at each point
    Z = np.zeros_like(A)
    for i in range(resolution):
        for j in range(resolution):
            # Perturb parameters
            delta = alphas[i] * v1 + betas[j] * v2
            param_iter = iter(model.parameters())
            for p in model.parameters():
                p.data += delta[:p.numel()].reshape(p.shape)
                delta = delta[p.numel():]
            
            # Compute loss
            with torch.no_grad():
                preds = model(data)
                Z[i, j] = nn.MSELoss()(preds, labels).item()
            
            # Reset parameters
            param_iter = iter(model.parameters())
            for p in model.parameters():
                p.data -= delta[:p.numel()].reshape(p.shape)
                delta = delta[p.numel():]
    
    # Create figure
    fig, ax = plt.subplots(figsize=(10, 8))
    contour = ax.contour(A, B, Z, levels=50, cmap='viridis', alpha=0.8)
    ax.clabel(contour, inline=True, fontsize=8)
    ax.set_xlabel('Direction v₁', fontsize=12)
    ax.set_ylabel('Direction v₂', fontsize=12)
    ax.set_title('Loss Landscape Contour Plot', fontsize=14)
    
    return fig

# Example usage
model = SimpleNet(width=100)
x_train = torch.randn(50, 1)
y_train = torch.sin(x_train)

# Train model
optimizer = torch.optim.SGD(model.parameters(), lr=0.01)
for _ in range(1000):
    pred = model(x_train)
    loss = nn.MSELoss()(pred, y_train)
    optimizer.zero_grad()
    loss.backward()
    optimizer.step()

fig = create_loss_landscape(model, x_train, y_train)
fig.savefig('loss_contour.png', dpi=150, bbox_inches='tight')

6. Spectral Bias and Frequency Analysis

6.1 Spectral Bias Theorem

Neural networks exhibit a spectral bias: they learn low-frequency components of the target function faster than high-frequency components. For a target function with Fourier decomposition:

The training dynamics under gradient descent yield:

where is the NTK eigenvalue corresponding to frequency mode .

6.2 Frequency Dependence

For a network with ReLU activation, the NTK eigenvalues scale as:

where is the frequency vector and depends on the network architecture. This implies:

• Low frequencies (small ): Large , fast learning
• High frequencies (large ): Small , slow learning

6.3 Practical Implications

The spectral bias has several consequences:

1. Generalisation: Networks preferentially learn smooth functions
2. Shortcut learning: Networks may learn low-frequency shortcuts rather than high-frequency details
3. Data efficiency: More data is needed to learn high-frequency components
4. Architecture design: Skip connections and attention help mitigate spectral bias

Mitigation strategies:

• Positional encodings in transformers
• Fourier features in implicit neural representations
• Multi-scale architectures
• Regularisation that encourages high-frequency learning

7. Summary and Key Takeaways

1. Universal Approximation: Neural networks are universal approximators, but the classical UAT provides no guidance on width/depth requirements. Depth efficiency results show that deep networks can be exponentially more parameter-efficient.

2. Neural Tangent Kernel: The NTK provides a rigorous framework for understanding training in the infinite-width limit. It reveals that gradient descent performs kernel regression in the NTK regime.

3. Loss Landscape: Overparameterised loss surfaces have many saddle points but few bad local minima. The geometry facilitates optimisation despite non-convexity.

4. Implicit Regularisation: SGD with small learning rate implicitly biases towards minimum-norm solutions, providing a form of regularisation without explicit penalty terms.

5. Spectral Perspective: The NTK eigenvalues determine learning speed for different function components, explaining the spectral bias of neural networks.

References

• Cybenko, G. (1989). Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4), 303-314.
• Hornik, K. (1991). Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2), 251-257.
• Jacot, A., Gabriel, F., & Hongler, C. (2018). Neural tangent kernel: Convergence and generalization in neural networks. NeurIPS.
• Li, H., Xu, Z., Taylor, G., Studer, C., & Goldstein, T. (2018). Visualizing the loss landscape of neural nets. NeurIPS.
• Telgarsky, M. (2016). Benefits of depth in neural networks. ICML.
• Eldan, R., & Shamir, O. (2016). The power of depth for feedforward neural networks. COLT.
• Novak, R., Bahri, Y., Abolafia, D. A., Pennington, J., & Sohl-Dickstein, J. (2020). Sensitivity and generalization in neural networks: an empirical study. ICLR.