  Model pruning is an essential procedure for building compact and
computationally-efficient machine learning models. A key feature of a good
pruning algorithm is that it accurately quantifies the relative importance of
the model weights. While model pruning has a rich history, we still don't have
a full grasp of the pruning mechanics even for relatively simple problems
involving linear models or shallow neural nets. In this work, we provide a
principled exploration of pruning by building on a natural notion of
importance. For linear models, we show that this notion of importance is
captured by covariance scaling which connects to the well-known Hessian-based
pruning. We then derive asymptotic formulas that allow us to precisely compare
the performance of different pruning methods. For neural networks, we
demonstrate that the importance can be at odds with larger magnitudes and
proper initialization is critical for magnitude-based pruning. Specifically, we
identify settings in which weights become more important despite becoming
smaller, which in turn leads to a catastrophic failure of magnitude-based
pruning. Our results also elucidate that implicit regularization in the form of
Hessian structure has a catalytic role in identifying the important weights,
which dictate the pruning performance.
