  Existing Rademacher complexity bounds for neural networks rely only on norm
control of the weight matrices and depend exponentially on depth via a product
of the matrix norms. Lower bounds show that this exponential dependence on
depth is unavoidable when no additional properties of the training data are
considered. We suspect that this conundrum comes from the fact that these
bounds depend on the training data only through the margin. In practice, many
data-dependent techniques such as Batchnorm improve the generalization
performance. For feedforward neural nets as well as RNNs, we obtain tighter
Rademacher complexity bounds by considering additional data-dependent
properties of the network: the norms of the hidden layers of the network, and
the norms of the Jacobians of each layer with respect to all previous layers.
Our bounds scale polynomially in depth when these empirical quantities are
small, as is usually the case in practice. To obtain these bounds, we develop
general tools for augmenting a sequence of functions to make their composition
Lipschitz and then covering the augmented functions. Inspired by our theory, we
directly regularize the network's Jacobians during training and empirically
demonstrate that this improves test performance.
