Researchers Finally Prove Deep ReLU Networks Generalize as Well as Shallow Ones
A new paper proves deep ReLU networks trained with gradient descent can match the theoretical best possible generalization rates — a first for multi-layer architectures.
Takeaways
- First optimal bounds for deep networks: The paper proves deep ReLU networks trained with GD/SGD achieve minimax-optimal generalization rates — a first for multi-layer architectures.
- Polynomial width is enough: The result holds when network width scales polynomially (not exponentially) with depth and sample size, making it far more practical than prior theory.
- NTK bridge: The proof shows deep ReLU networks trained by gradient descent can fully inherit the optimal learning dynamics of their kernel method counterparts.
- Covers both GD and SGD: Optimal rates are proved for full-batch gradient descent and stochastic gradient descent, the algorithm actually used in practice.
- Regression focus: Results apply to regression tasks; classification and feature-learning regimes are out of scope.
- Theory only, no code: This is a pure theoretical contribution — no new architecture, training recipe, or released model. Paper on arXiv.
One of the most uncomfortable gaps in deep learning theory has quietly persisted for years: we could prove that shallow neural networks trained with gradient descent generalize well, but the same guarantees for deep networks were largely missing. A new paper from researchers at multiple institutions now closes that gap, establishing the first provably optimal generalization bounds for deep ReLU networks trained with both gradient descent (GD) and stochastic gradient descent (SGD).