We study a generalization of boosting to the multiclass setting. We introduce
a weak learning condition for multiclass classification that captures the
original notion of weak learnability as being "slightly better than random
guessing". We give a simple and efficient boosting algorithm, that does not
require realizability assumptions and its sample and oracle complexity bounds
are independent of the number of classes.
In addition, we utilize our new boosting technique in several theoretical
applications within the context of List PAC Learning. First, we establish an
equivalence to weak PAC learning. Furthermore, we present a new result on
boosting for list learners, as well as provide a novel proof for the
characterization of multiclass PAC learning and List PAC learning. Notably, our
technique gives rise to a simplified analysis, and also implies an improved
error bound for large list sizes, compared to previous results.

将增强学习推广到多类别情景中，引入了适用于多类别分类的弱学习条件，提出了一种简单高效的增强学习算法，并在列表式 PAC 学习的背景下应用其新的增强技术，证明了其可行性和可靠性。

多类别提升：简单直观的弱学习准则

Multiclass Boosting: Simple and Intuitive Weak Learning Criteria

Deep neural networks are known to be difficult to train due to the
instability of back-propagation. A deep \emph{residual network} (ResNet) with
identity loops remedies this by stabilizing gradient computations. We prove a
boosting theory for the ResNet architecture. We construct $T$ weak module
classifiers, each contains two of the $T$ layers, such that the combined strong
learner is a ResNet. Therefore, we introduce an alternative Deep ResNet
training algorithm, \emph{BoostResNet}, which is particularly suitable in
non-differentiable architectures. Our proposed algorithm merely requires a
sequential training of $T$ "shallow ResNets" which are inexpensive. We prove
that the training error decays exponentially with the depth $T$ if the
\emph{weak module classifiers} that we train perform slightly better than some
weak baseline. In other words, we propose a weak learning condition and prove a
boosting theory for ResNet under the weak learning condition. Our results apply
to general multi-class ResNets. A generalization error bound based on margin
theory is proved and suggests ResNet's resistant to overfitting under network
with $l_1$ norm bounded weights.

本文针对深度神经网络训练的不稳定性，提出具有强学习能力的 ResNet 架构，并在该条件下证明了 ResNet 的 Boosting 理论，同时提出 BoostResNet 训练算法来刻画 “浅层 ResNet” 的序列训练，推导出了 ResNet 的弱学习条件，并证明在深度为 $T$ 时，训练的误差随着 $T$ 指数下降。基于边缘理论证明了广义分类 ResNet 的泛化误差上限，并建议 ResNet 对边缘带 $l_1$ 约束的权重具有抵抗过拟合的能力。