  The lottery ticket hypothesis (LTH) has increased attention to pruning neural
networks at initialization. We study this problem in the linear setting. We
show that finding a sparse mask at initialization is equivalent to the
sketching problem introduced for efficient matrix multiplication. This gives us
tools to analyze the LTH problem and gain insights into it. Specifically, using
the mask found at initialization, we bound the approximation error of the
pruned linear model at the end of training. We theoretically justify previous
empirical evidence that the search for sparse networks may be data independent.
By using the sketching perspective, we suggest a generic improvement to
existing algorithms for pruning at initialization, which we show to be
beneficial in the data-independent case.
