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.

我们引入了一种基于有效维度的统计模型的新容量度量 2sED。这个新数量在模型的温和假设下能证明地限制了泛化误差。此外，对标准数据集和流行的模型架构的模拟结果表明，2sED 与训练误差具有良好的相关性。对于马尔可夫模型，我们展示了如何通过分层迭代方法从下方高效地逼近 2sED，这使我们能够处理具有大量参数的深度学习模型。模拟结果表明，这种逼近适用于不同的突出模型和数据集。

深度学习模型的双尺度复杂度度量

A Two-Scale Complexity Measure for Deep Learning Models

Recently, path norm was proposed as a new capacity measure for neural
networks with Rectified Linear Unit (ReLU) activation function, which takes the
rescaling-invariant property of ReLU into account. It has been shown that the
generalization error bound in terms of the path norm explains the empirical
generalization behaviors of the ReLU neural networks better than that of other
capacity measures. Moreover, optimization algorithms which take path norm as
the regularization term to the loss function, like Path-SGD, have been shown to
achieve better generalization performance. However, the path norm counts the
values of all paths, and hence the capacity measure based on path norm could be
improperly influenced by the dependency among different paths. It is also known
that each path of a ReLU network can be represented by a small group of
linearly independent basis paths with multiplication and division operation,
which indicates that the generalization behavior of the network only depends on
only a few basis paths. Motivated by this, we propose a new norm
\emph{Basis-path Norm} based on a group of linearly independent paths to
measure the capacity of neural networks more accurately. We establish a
generalization error bound based on this basis path norm, and show it explains
the generalization behaviors of ReLU networks more accurately than previous
capacity measures via extensive experiments. In addition, we develop
optimization algorithms which minimize the empirical risk regularized by the
basis-path norm. Our experiments on benchmark datasets demonstrate that the
proposed regularization method achieves clearly better performance on the test
set than the previous regularization approaches.

提出一种基于一组线性独立路径的新范数，用于更准确地衡量神经网络的容量，在基于此范数的正则化方法下获得更好的测试性能。