  Pruning the weights of randomly initialized neural networks plays an
important role in the context of lottery ticket hypothesis. Ramanujan et al.
(2020) empirically showed that only pruning the weights can achieve remarkable
performance instead of optimizing the weight values. However, to achieve the
same level of performance as the weight optimization, the pruning approach
requires more parameters in the networks before pruning and thus more memory
space. To overcome this parameter inefficiency, we introduce a novel framework
to prune randomly initialized neural networks with iteratively randomizing
weight values (IteRand). Theoretically, we prove an approximation theorem in
our framework, which indicates that the randomizing operations are provably
effective to reduce the required number of the parameters. We also empirically
demonstrate the parameter efficiency in multiple experiments on CIFAR-10 and
ImageNet. The code is available at: https://github.com/dchiji-ntt/iterand
