Deep neural networks match kernel methods in generalization: minimax rates proven
First minimax-optimal generalization rates for deep networks trained by gradient descent...
A team from multiple institutions (Zhou, Wang, Lei, Kloft, Ying) published a paper on arXiv establishing minimax-optimal generalization rates for deep neural networks (DNNs) trained with gradient descent (GD) and stochastic gradient descent (SGD). The work bridges a long-standing gap between shallow and deep architectures: while neural tangent kernel (NTK) theory explained shallow networks, deep networks remained poorly understood theoretically.
The authors prove that with smooth activation functions and sufficient width (scaling polynomially with sample size), gradient-based training endows DNNs with the same favorable learning dynamics as kernel methods. This leads to the first known minimax-optimal excess risk bounds for GD and SGD in deep regression. The results show that deep learning can achieve statistical optimality comparable to classical kernel approaches, providing a rigorous foundation for why over-parameterized deep networks generalize well.
- First minimax-optimal generalization bounds for deep neural networks trained by gradient descent and stochastic gradient descent
- Network width must scale polynomially with sample size (e.g., up to O(n^4)) to match kernel method performance
- Established a direct connection between gradient-based learning dynamics of DNNs (with smooth activations) and kernel methods
Why It Matters
Mathematically proves deep networks can achieve optimal statistical efficiency, validating over-parameterization as more than just memorization.