  The increasing computational demands of modern neural networks present
deployment challenges on resource-constrained devices. Network pruning offers a
solution to reduce model size and computational cost while maintaining
performance. However, most current pruning methods focus primarily on improving
sparsity by reducing the number of nonzero parameters, often neglecting other
deployment costs such as inference time, which are closely related to the
number of floating-point operations (FLOPs). In this paper, we propose FALCON,
a novel combinatorial-optimization-based framework for network pruning that
jointly takes into account model accuracy (fidelity), FLOPs, and sparsity
constraints. A main building block of our approach is an integer linear program
(ILP) that simultaneously handles FLOP and sparsity constraints. We present a
novel algorithm to approximately solve the ILP. We propose a novel first-order
method for our optimization framework which makes use of our ILP solver. Using
problem structure (e.g., the low-rank structure of approx. Hessian), we can
address instances with millions of parameters. Our experiments demonstrate that
FALCON achieves superior accuracy compared to other pruning approaches within a
fixed FLOP budget. For instance, for ResNet50 with 20% of the total FLOPs
retained, our approach improves the accuracy by 48% relative to
state-of-the-art. Furthermore, in gradual pruning settings with re-training
between pruning steps, our framework outperforms existing pruning methods,
emphasizing the significance of incorporating both FLOP and sparsity
constraints for effective network pruning.
