  Model pruning is a popular approach to enable the deployment of large deep
learning models on edge devices with restricted computational or storage
capacities. Although sparse models achieve performance comparable to that of
their dense counterparts at the level of the entire dataset, they exhibit high
accuracy drops for some data sub-groups. Existing methods to mitigate this
disparate impact induced by pruning (i) rely on surrogate metrics that address
the problem indirectly and have limited interpretability; or (ii) scale poorly
with the number of protected sub-groups in terms of computational cost. We
propose a constrained optimization approach that directly addresses the
disparate impact of pruning: our formulation bounds the accuracy change between
the dense and sparse models, for each sub-group. This choice of constraints
provides an interpretable success criterion to determine if a pruned model
achieves acceptable disparity levels. Experimental results demonstrate that our
technique scales reliably to problems involving large models and hundreds of
protected sub-groups.
