Analyzing Lottery Ticket Hypothesis from PAC-Bayesian Theory Perspective
The lottery ticket hypothesis (LTH) has attracted attention because it can
explain why over-parameterized models often show high generalization ability.
It is known that when we use iterative magnitude pruning (IMP), which is an
algorithm to find sparse networks with high generalization ability that can be
trained from the initial weights independently, called winning tickets, the
initial large learning rate does not work well in deep neural networks such as
ResNet. However, since the initial large learning rate generally helps the
optimizer to converge to flatter minima, we hypothesize that the winning
tickets have relatively sharp minima, which is considered a disadvantage in
terms of generalization ability. In this paper, we confirm this hypothesis and
show that the PAC-Bayesian theory can provide an explicit understanding of the
relationship between LTH and generalization behavior. On the basis of our
experimental findings that flatness is useful for improving accuracy and
robustness to label noise and that the distance from the initial weights is
deeply involved in winning tickets, we offer the PAC-Bayes bound using a
spike-and-slab distribution to analyze winning tickets. Finally, we revisit
existing algorithms for finding winning tickets from a PAC-Bayesian perspective
and provide new insights into these methods.