Complexity, Statistical Risk, and Metric Entropy of Deep Nets Using Total Path Variation
This provides theoretical guarantees for deep learning generalization, but is incremental as it builds on existing complexity analysis.
The paper tackles the problem of bounding statistical risk and complexity measures for ReLU networks by showing they are proportional to total path variation V, independent of network width, and provides mean square generalization error bounds of order V√(L+log d)/√n for sub-Gaussian noise.
For any ReLU network there is a representation in which the sum of the absolute values of the weights into each node is exactly $1$, and the input layer variables are multiplied by a value $V$ coinciding with the total variation of the path weights. Implications are given for Gaussian complexity, Rademacher complexity, statistical risk, and metric entropy, all of which are shown to be proportional to $V$. There is no dependence on the number of nodes per layer, except for the number of inputs $d$. For estimation with sub-Gaussian noise, the mean square generalization error bounds that can be obtained are of order $V \sqrt{L + \log d}/\sqrt{n}$, where $L$ is the number of layers and $n$ is the sample size.