Foundations of Optimisation & Generalisation in Neural Networks

Jeremy Bernstein

https://jeremybernste.in

What makes deep learning theory hard?

A common pattern of study:

1. Take well-known classical theory;
2. Try to bend it to match deep learning.�

✅ Results look qualitatively complete.

❌ Results often quantitatively vacuous.

2

What makes deep learning theory hard?

A common pattern of study:

• Take well-known classical theory;
• Try to bend it to match deep learning.�

✅ Results look qualitatively complete.

❌ Results often quantitatively vacuous.

❌ Results do not address important practical questions.

3

Something better is out there.

…Why must I tune ten different hyperparameters?

…How can I control my network’s inductive bias?

Neural architecture as the starting point

Our pattern of study:

1. Perform targeted explorations of the NN function space;
2. Introduce theoretical tools selectively.�

✅ Results are quantitatively non-vacuous.

✅ Theory makes useful predictions.

❌ Complete theory is still a work-in-progress.

4

Two ideas in this talk

1. Neural network–Bayes point machine correspondence

• Neural architecture aware optimisation

5

Bayesian risk bounds for single classifiers.

Inductive bias control.

Deep network descent lemma.

Hyperparameter transfer.

Part I

Max-Margin Neural Networks�as Bayes Point Machines

The modern machine learning paradigm

The punchline of this section

• Interpolating classifiers form an ensemble.�
• To predict, we can use the majority vote.�
• NN can fit its own majority vote in one shot.

7

Why do neural nets generalise… even when non-generalising functions exist in the function space?

Information theory

Voting theory

Convex geometry

8

Bayes point machine (noun)

A single classifier that approximates the aggregate prediction of an ensemble of classifiers.

Herbrich, Graepel & Campbell (JMLR 2001)

Connections to other disciplines

• Mean voter theorem in social choice theory �When can a single voter speak for an electorate?�📚 Caplin & Nalebuff, 1991�
• Tukey median in high dimensional statistics�How can we generalise the median to high dimension?�📚 Tukey, 1977�
• Mass partitions in geometry�How can we divide a set into more-or-less equal halves?�📚 Grünbaum, 1960

9

We propose the NN–BPM correspondence

≈

10

✅ Good theory.

❌ Expensive to construct.

❌ Poor theory.

✅ Used in practice.

Part I: NN–BPM correspondence

Introduction ←

Experiments

Theory

Outlook

Part I: NN–BPM correspondence

Introduction

Experiments ←

Theory

Outlook

Let’s take control of normalised margin

• Train ensembles of neural networks to 100% train accuracy.
• Control the normalised margin of each ensemble member.
• Measure the test accuracy.

13

Normalised margin control

14

Normalised margin control carefully scales:

1. the outputs, by choice of loss function:� L_a(w) ← ∑_(x,y)(f(x;w) - a⋅y)².
2. the weights, by projected gradient descent:� W_k ← W_k / ‖W_k‖_F for each layer k.
3. the inputs, by projection:� x ← x / ‖x‖₂ for each input x.

W₁

W₂

W₃

W₄

input x

output f(x;w)

Effect of normalised margin control

For networks with 100% train accuracy:

15

• Ensemble size ↑ implies test accuracy ↑.

• Normalised margin ↑ implies test accuracy ↑.

Part I: NN–BPM correspondence

Introduction

Experiments

Theory ←

Outlook

Our theoretical results

Result 2. (Generalisation)

Bayes point machines have nice generalisation properties.

Result 1. (Concentration)

Conditioned on fitting a training set, as normalised margin → ∞, the function space of a width-∞ NN concentrates on a BPM.

17

Bayes point machine (noun)

A single classifier that approximates the aggregate prediction of an ensemble of classifiers.

Herbrich, Graepel & Campbell (JMLR 2001)

→

Result 1. (Concentration)

Conditioned on fitting a training set, as normalised margin → ∞, the function space of a width-∞ NN concentrates on a BPM.

18

Proof sketch.

1. The function space of a width-∞ NN, conditioned on fitting a training set, is a GP posterior distribution.
2. Taking normalised margin → ∞ causes this GP posterior distribution to concentrate on its mean.

Result 1. (Concentration)

Conditioned on fitting a training set, as normalised margin → ∞, the function space of a width-∞ NN concentrates on a BPM.

19

Proof sketch.

• The function space of a width-∞ NN, conditioned on fitting a training set, is a GP posterior distribution.
• Taking normalised margin → ∞ causes this GP posterior distribution to concentrate on its mean.
• The mean prediction approximates the majority vote.

Proof sketch.

• The function space of a width-∞ NN, conditioned on fitting a training set, is a GP posterior distribution.
• Taking normalised margin → ∞ causes this GP posterior distribution to concentrate on its mean.

weighted Grünbaum’s inequality (Caplin & Nalebuff, 1991)

Prob[halfspace( )] > 1/e

Result 2. (Generalisation)

Bayes point machines have nice generalisation properties.

20

risk(BPM) ≈ risk(majority vote)

≪ 𝔼 risk(randomised predictor)

≲ # bits in Q / # train examples

Given an ensemble Q of classifiers, we can classify x:

• randomly x ↦ sign f(w;x) for w~Q (aka Gibbs classifier).
• by majority vote x ↦ sign 𝔼_w sign f(w;x) (aka Bayes classifier).

Part I: NN–BPM correspondence

Introduction

Experiments

Theory

Outlook ←

NN–BPM correspondence

• A new way to understand generalisation in deep learning.
• Based on old ideas about kernel methods.
• What’s better than reading old papers? Reading old textbooks.

22

Controlled optimisation as a scientific tool

• We are charting the behaviour of a function space that we do not fully understand.
• Optimisation is our friend.

23

Normalised margin control carefully scales:

• the outputs, by choice of loss function:� L_a(w) ← ∑_(x,y)(f(x;w) - a⋅y)².
• the weights, by projected gradient descent:� W_k ← W_k / ‖W_k‖_F for each layer k.
• the inputs, by projection:� x ← x / ‖x‖₂ for each input x.

Application: Uncertainty quantification

→

←

• Let’s train an ensemble of NNs to estimate model uncertainty.
• We need to avoid the ensemble collapsing on a single function.
• Normalised margin control can “anti-regularise” the ensemble.

24

24

anti-regularise

regularise

Good generalisation

Good uncertainty

References

≈

📚 Kernel interpolation as a Bayes point machine

📚 Investigating generalization by controlling normalized margin

25

input

majority vote

input

sign

Ensemble of NNs

One large margin NN

One large margin NN

Part II

Neural Architecture Aware Optimisation

Optimisation theory versus practice

Practice

Perturb every operator in a composition!

Theory

Flatten weights; neglect compositional structure!

27

min_ΔW g^TΔW + λ ‖ΔW‖²

At each iteration:

1. minimise first order Taylor approximation of the loss;
2. subject to quadratic penalty.

Optimisation theory versus practice

New theory

Practice

Perturb every operator in a composition!

Δf(x) := f(W+ΔW; x) - f(W; x)

-1

min_ΔW g^TΔW

Deep network descent lemma

→

Result 1. (Deep network descent lemma)

An update will decrease the objective function provided that �for all layers k = 1, …, L:

-1

1. direction: ΔW_k ∝ -g_k;
2. magnitude: ‖ΔW_k‖ < ‖W_k‖ · O(1/L).

add layers

deep relative trust

Training deeper MLPs with Fromage

• We explored “Frobenius matched gradient descent” 🧀
• Enforces ‖ΔW_k‖ < ‖W_k‖ · η where η sets the learning rate
• Similar to LARS (You et al, 2017)

30

• Fromage trains deeper MLPs than Adam or SGD

• Deeper nets required smaller learning rate

Hyperparameter transfer

• Fromage-variant optimiser
• Tested on 6 deep learning tasks
• Same hyperparameters worked on 5 out of 6 tasks

31

“may unlock a simpler workflow for training deeper and more complex neural networks”

Connection to neuroscience

Per-synapse relative update

32

grow by factor (1 + η)

shrink by factor (1 - η)

References

→

📚 On the distance between two neural networks and the stability of learning

📚 Learning by turning: Neural architecture aware optimisation

📚 Learning compositional functions via multiplicative weight updates

33

add layers

What’s next?

Making deep learning a mature technology

• Learning theory & optimisation theory need to account for the structure of the NN parameter–function map.�
• Should enable new functionality:
• Uncertainty quantification;
• Hyperparameter transfer.�
• Old theory (used selectively) plays an important role:
• Bayes point machines;
• Trust region methods.�
• More work is needed!

35

Neural hardware

36

“synaptic plasticity”

“weight update”

✅ access to all microscopic details

✅ can do numerical analysis

❌ energy intensive

❌ hard to experiment on

✅ energy efficient

✅ that’s us!

≈

→

Thank you!

• Deep network descent lemma

• NN–BPM correspondence

🛝 Slides on my website: https://jeremybernste.in.