  We introduce a novel capacity measure 2sED for statistical models based on
the effective dimension. The new quantity provably bounds the generalization
error under mild assumptions on the model. Furthermore, simulations on standard
data sets and popular model architectures show that 2sED correlates well with
the training error. For Markovian models, we show how to efficiently
approximate 2sED from below through a layerwise iterative approach, which
allows us to tackle deep learning models with a large number of parameters.
Simulation results suggest that the approximation is good for different
prominent models and data sets.
