  The lottery ticket hypothesis (LTH) has shown that dense models contain
highly sparse subnetworks (i.e., winning tickets) that can be trained in
isolation to match full accuracy. Despite many exciting efforts being made,
there is one "commonsense" rarely challenged: a winning ticket is found by
iterative magnitude pruning (IMP) and hence the resultant pruned subnetworks
have only unstructured sparsity. That gap limits the appeal of winning tickets
in practice, since the highly irregular sparse patterns are challenging to
accelerate on hardware. Meanwhile, directly substituting structured pruning for
unstructured pruning in IMP damages performance more severely and is usually
unable to locate winning tickets. In this paper, we demonstrate the first
positive result that a structurally sparse winning ticket can be effectively
found in general. The core idea is to append "post-processing techniques" after
each round of (unstructured) IMP, to enforce the formation of structural
sparsity. Specifically, we first "re-fill" pruned elements back in some
channels deemed to be important, and then "re-group" non-zero elements to
create flexible group-wise structural patterns. Both our identified channel-
and group-wise structural subnetworks win the lottery, with substantial
inference speedups readily supported by existing hardware. Extensive
experiments, conducted on diverse datasets across multiple network backbones,
consistently validate our proposal, showing that the hardware acceleration
roadblock of LTH is now removed. Specifically, the structural winning tickets
obtain up to {64.93%, 64.84%, 60.23%} running time savings at {36%~80%, 74%,
58%} sparsity on {CIFAR, Tiny-ImageNet, ImageNet}, while maintaining comparable
accuracy. Code is at https://github.com/VITA-Group/Structure-LTH.
