The \textit{lottery ticket hypothesis} (LTH) states that learning on a
properly pruned network (the \textit{winning ticket}) improves test accuracy
over the original unpruned network. Although LTH has been justified empirically
in a broad range of deep neural network (DNN) involved applications like
computer vision and natural language processing, the theoretical validation of
the improved generalization of a winning ticket remains elusive. To the best of
our knowledge, our work, for the first time, characterizes the performance of
training a pruned neural network by analyzing the geometric structure of the
objective function and the sample complexity to achieve zero generalization
error. We show that the convex region near a desirable model with guaranteed
generalization enlarges as the neural network model is pruned, indicating the
structural importance of a winning ticket. Moreover, when the algorithm for
training a pruned neural network is specified as an (accelerated) stochastic
gradient descent algorithm, we theoretically show that the number of samples
required for achieving zero generalization error is proportional to the number
of the non-pruned weights in the hidden layer. With a fixed number of samples,
training a pruned neural network enjoys a faster convergence rate to the
desired model than training the original unpruned one, providing a formal
justification of the improved generalization of the winning ticket. Our
theoretical results are acquired from learning a pruned neural network of one
hidden layer, while experimental results are further provided to justify the
implications in pruning multi-layer neural networks.

本文通过分析目标函数的几何结构和样本复杂度，理论上证明了剪枝神经网络在加速随机梯度下降算法的特定情况下，训练过程中获得零泛化误差所需的样本数与隐藏层中未被剪枝的权重数成正比，从而提供了对中奖票证明的形式化证明。