Blumer et al. (1987, 1989) showed that any concept class that is learnable by
Occam algorithms is PAC learnable. Board and Pitt (1990) showed a partial
converse of this theorem: for concept classes that are closed under exception
lists, any class that is PAC learnable is learnable by an Occam algorithm.
However, their Occam algorithm outputs a hypothesis whose complexity is
$\delta$-dependent, which is an important limitation. In this paper, we show
that their partial converse applies to Occam algorithms with
$\delta$-independent complexities as well. Thus, we provide a posteriori
justification of various theoretical results and algorithm design methods which
use the partial converse as a basis for their work.

通过在 Occam 算法中使用与 δ 无关的复杂性，本研究论文证明了 Board 和 Pitt 的部分对偶定理也适用于其，从而提供了各种理论结果和基于该对偶定理的算法设计方法的事后验证。

Occam 算法的等价性

On the equivalence of Occam algorithms

Residual connections significantly boost the performance of deep neural
networks. However, there are few theoretical results that address the influence
of residuals on the hypothesis complexity and the generalization ability of
deep neural networks. This paper studies the influence of residual connections
on the hypothesis complexity of the neural network in terms of the covering
number of its hypothesis space. We prove that the upper bound of the covering
number is the same as chain-like neural networks, if the total numbers of the
weight matrices and nonlinearities are fixed, no matter whether they are in the
residuals or not. This result demonstrates that residual connections may not
increase the hypothesis complexity of the neural network compared with the
chain-like counterpart. Based on the upper bound of the covering number, we
then obtain an $\mathcal O(1 / \sqrt{N})$ margin-based multi-class
generalization bound for ResNet, as an exemplary case of any deep neural
network with residual connections. Generalization guarantees for similar
state-of-the-art neural network architectures, such as DenseNet and ResNeXt,
are straight-forward. From our generalization bound, a practical implementation
is summarized: to approach a good generalization ability, we need to use
regularization terms to control the magnitude of the norms of weight matrices
not to increase too much, which justifies the standard technique of weight
decay.

本文研究残差连接对神经网络假设空间覆盖数以及泛化能力的影响，证明了哪怕是固定了权重矩阵和非线性函数的总数，残差连接不会增加神经网络的假设复杂性，并基于假设空间覆盖数得到了 ResNet 等采用残差连接的深度神经网络的多类泛化界。根据此泛化界，我们可以使用正则化项控制权重矩阵的模不要过度增大，以尽量达到良好的泛化性能。