Optimisation & Generalisation in Networks of Neurons

Jeremy BernsteinarXiv 2022 · DOI · arXiv

Introduction

Despite the transformative success of deep learning, the field often operates on empirical heuristics—a practice frequently described as "alchemy." Practitioners rely on trial-and-error to determine hyperparameters like learning rates, and a rigorous mathematical explanation for why over-parameterized networks generalize rather than simply memorizing training data remains a central challenge. This work provides a unified theoretical foundation by treating optimization and generalization as two sides of the same coin, introducing "architecture-aware" algorithms and proving that wide, large-margin networks function as Bayes Point Machines.

The Dual Challenge: Optimisation and Generalisation

The research addresses two fundamental questions that govern the behavior of neural networks:

  1. Optimisation: To what extent can network weights be adjusted before the underlying function being learned is fundamentally "damaged"?
  2. Generalisation: Among the infinite weight configurations that can fit a training set, which one will perform best on unseen data, and what is the mathematical basis for this selection?

Methodology: Architecture-Aware Framework

To bridge the gap between theory and practice, a three-step framework for deriving architecture-aware optimization is developed. This framework moves beyond looking at weight changes in isolation, instead focusing on how perturbations in the network's outputs (function space) affect the loss.

Key architectural notation used to derive perturbation bounds.

1. Functional Majorisation

The approach begins by analyzing the impact of output perturbations on the loss function. By establishing a "tangent upper bound" of the loss, the author creates a Majorise-Minimise (MM) meta-algorithm that derives update rules inherently tuned to the specific network structure.

2. Architectural Perturbation Bounds

A novel mathematical bridge is constructed to relate functional changes back to weight changes. These bounds specifically account for the network's depth ($L$) and width ($d$), ensuring that the optimization process respects the geometry of the model.

Mathematical norms used to define the architectural bounds and generalization properties.

3. Generalisation via PAC-Bayes Theory

For generalization, the work leverages the Neural Network–Gaussian Process (NNGP) correspondence. Using PAC-Bayes theory, it is shown that as networks become infinitely wide and are trained to maximize their "normalized margin," they concentrate on a Bayes Point Machine (BPM). This single classifier effectively approximates the aggregate prediction of an entire ensemble.

Key Insights

  • Hyperparameters as Structural Properties: The "correct" learning rate is not an arbitrary constant but a function of the network's geometry. Specifically, the optimal learning rate should scale inversely with depth ($1/L$).
  • Logarithmic Gradient Scaling: The derived optimal updates depend on the gradient scale only logarithmically. This provides a formal theoretical justification for the empirical success of optimizers like Adam, which normalize gradients.
  • The Single-Model Ensemble: The research suggests that the benefits of ensembling can be captured within a single model. By training a wide network to a large normalized margin, the model's predictions concentrate, acting as the mean of an infinite ensemble.
  • Bridging Kernels and Neurons: There is a deep correspondence between minimum-norm kernel interpolators and neural networks, suggesting that deep learning succeeds by finding the "simplest" functional explanation for the data.

Experimental Validation

The theoretical insights were validated using standard computer vision benchmarks:

  • CIFAR-10: Experiments demonstrated stable learning rate transfer. The architecture-aware update allowed the same learning rate to work effectively across networks ranging from 2 to 10 layers in depth and 64 to 8192 units in width without manual retuning.
  • MNIST: A single neural network trained to a large Frobenius-normalized margin achieved test accuracy nearly identical to the majority vote of a 501-member ensemble, confirming the BPM hypothesis.
  • Non-Vacuous Bounds: The PAC-Bayes bounds derived for these wide networks were shown to be "non-vacuous," providing meaningful, tight guarantees on generalization error.

Conclusion and Future Directions

While the current framework provides a robust foundation, particularly for deep linear networks, several avenues for future work remain. Extending these insights to complex non-linearities beyond ReLU and incorporating the stochasticity of mini-batch gradient descent are critical next steps. Additionally, while the use of operator norms is theoretically elegant, developing more computationally efficient approximations will be necessary for applying these architecture-aware updates to extremely large-scale models.

Summary updated

Abstract

The goal of this thesis is to develop the optimisation and generalisation theoretic foundations of learning in artificial neural networks. On optimisation, a new theoretical framework is proposed for deriving architecture-dependent first-order optimisation algorithms. The approach works by combining a "functional majorisation" of the loss function with "architectural perturbation bounds" that encode an explicit dependence on neural architecture. The framework yields optimisation methods that transfer hyperparameters across learning problems. On generalisation, a new correspondence is proposed between ensembles of networks and individual networks. It is argued that, as network width and normalised margin are taken large, the space of networks that interpolate a particular training set concentrates on an aggregated Bayesian method known as a "Bayes point machine". This correspondence provides a route for transferring PAC-Bayesian generalisation theorems over to individual networks. More broadly, the correspondence presents a fresh perspective on the role of regularisation in networks with vastly more parameters than data.
BibTeX
@misc{bernstein2022optimisation,
  author = {Jeremy Bernstein},
  title = {{Optimisation \& Generalisation in Networks of Neurons}},
  year = {2022},
  eprint = {2210.10101},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.10101},
}
Figure