Open: generalisation bounds that track the generalisation gap
ProofResearch⏱ ResearchLearning TheoryDL Theoryopen problemgeneralisationpac-bayesbounds
Problem
Produce a generalisation bound for deep networks that is simultaneously: non-vacuous (below the trivial bound of 1 for a 0–1 loss), computable from the trained model and the training set, and correlated with the measured test gap across architectures, dataset sizes and label noise levels — so that when the true gap doubles, the bound moves in the same direction.
The third requirement is the open one.
This is an open problem. Nobody has a solution, and none is hidden below — what is recorded is the state of the argument. Progress on it would be publishable.
What is known
This problem is open. What follows is an account of what has been proved, what has only been measured, and where the argument stops — not a solution, because there is not one.
Related problems
All problems| Solved | Problem | Field | Type | Difficulty | Time |
|---|---|---|---|---|---|
| The bias–variance decomposition is an identity | Learning Theory | Proof | 15 min | ||
| Gradient descent finds the minimum-norm interpolator | Learning Theory | Proof | 30 min | ||
| Reproduce double descent run | Learning Theory | Coding | 3 hours | ||
| The interpolation peak is a conditioning phenomenon | Learning Theory | Proof | 30 min | ||
| The SVM margin bound abyss | Classical ML | Proof | 1 hour |