Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity
  on Pruned Neural Networks   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.

22
The categories of this paper are: chao-dyn
29
The categories of this paper are: funct-an
18
The categories of this paper are: econ
27
The categories of this paper are: comp-gas
16
The categories of this paper are: stat
9
The categories of this paper are: nlin
17
The categories of this paper are: q-fin
0
The categories of this paper are: hep-ph
3
The categories of this paper are: physics
15
The categories of this paper are: nucl-ex
28
The categories of this paper are: alg-geom
4
The categories of this paper are: cond-mat
34
The categories of this paper are: chem-ph
10
The categories of this paper are: q-bio
13
The categories of this paper are: quant-ph
11
The categories of this paper are: hep-lat