Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a
suitable space to model functions by neural networks as the curse of
dimensionality (CoD) cannot be evaded when trying to approximate even a single
ReLU neuron (Bach, 2017). In this paper, we study a suitable function space for
over-parameterized two-layer neural networks with bounded norms (e.g., the path
norm, the Barron norm) in the perspective of sample complexity and
generalization properties. First, we show that the path norm (as well as the
Barron norm) is able to obtain width-independence sample complexity bounds,
which allows for uniform convergence guarantees. Based on this result, we
derive the improved result of metric entropy for $\epsilon$-covering up to
$\mathcal{O}(\epsilon^{-\frac{2d}{d+2}})$ ($d$ is the input dimension and the
depending constant is at most polynomial order of $d$) via the convex hull
technique, which demonstrates the separation with kernel methods with
$\Omega(\epsilon^{-d})$ to learn the target function in a Barron space. Second,
this metric entropy result allows for building a sharper generalization bound
under a general moment hypothesis setting, achieving the rate at
$\mathcal{O}(n^{-\frac{d+2}{2d+2}})$. Our analysis is novel in that it offers a
sharper and refined estimation for metric entropy (with a clear dependence
relationship on the dimension $d$) and unbounded sampling in the estimation of
the sample error and the output error.

利用路径范数和巴伦范数建立了适合于过参数化的两层神经网络的函数空间，并证明了度量熵和一般化界限方面的改进结果。

受限的、过参数化的、两层神经网络的学习

Learning with Norm Constrained, Over-parameterized, Two-layer Neural  Networks

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.

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