Balancing Act: Constraining Disparate Impact in Sparse Models
Authors: Meraj Hashemizadeh
Juan Ramirez
Rohan Sukumaran
Golnoosh Farnadi
Simon Lacoste-Julien
Jose Gallego-Posada
Venue: ICLR 2024 poster (2024)
Keywords: deep learning
sparsity
disparate impact
constrained optimization
pruning
fairness
Primary area: general machine learning (i.e., none of the above)
TL;DR: We propose a constrained optimization method that directly reduces the disparate impact of pruning on accuracy across data sub-groups.

Abstract: 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.

Published as a conference paper at ICLR 2024
BALANCING ACT: CONSTRAINING DISPARATE IMPACT IN SPARSE MODELS
Meraj Hashemizadeh" Golnoosh Farnadi
Juan Ramirez Simon Lacoste-Julien
Rohan Sukumaran 12 Jose Gallego-Posadai
1 Mila
DIRO Université de Montréal
McGill University
*Caaaaa CIFAR Al Chair
ABSTRACT
Model pruning is 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 that of their dense counterparts at the level of the entire dataset, they exhibit high accuracy drops for some data
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 determine if pruned model achieves acceptable disparity levels. Experimental results demonstrate that our technique scales reliably to problems involving large models and hundreds of protected groups...
INTRODUCTION
Current deep learning practice displays trend towards larger architectures (Bommasani et al., 2021), as exemplified by popular models such as GPT-4 (OpenAl, 2023), Llama 2 (Touvron et al., 2023) and DALL-E 2 (Ramesh et al., 2022). Model compression techniques such as pruning (Gale et al., 2019), knowledge distillation (Hinton et al., 2015), or quantization (Gholami et al., 2021) are crucial towards enabling the deployment of large models across wide range of platforms, including resource-constrainee edge devices like smartphones.
Despite achieving comparable performance an aggregate level over the entire dataset, pruned models often exhibit significant accuracy reduction for some data sub-group (Hooker et al., 2019; 2020; Paganini, 2020). In particular, under-represented groups can suffer high performance degradation while the overall performance remains unaffected, thus exacerbating systemic biases in machine learning models. Tran et al. (2022) refer to this phenomenon the disparate impact of pruning.
Existing mitigation methods face challenges in terms of interpretability and scalability to a large number of uub-groups. Tran et al. (2022) introduce constraints aiming to equalize the loss of the sparse model across sub- gropp.. However, their approach does not account for the unequal group- level performance of the dense model. Moreover, while the loss can be useful surrogate for training, this method addresses the disparate impact issue indirectly as it focuses on controlling the loss, rather than group-level changes accuracy. Alternatively, Lin et al. (2022) compute per-group importance scores for every model parameter to determine the weights to be pruned. This approach becomes prohibitively expensive when the model or the number of sub-groups is large.
In this work. we characterize the disparate impact of pruning in terms of the group- accuracy gaps between the dense and sparse models. Additionally, we propose a problem formulation forbulmtoorullaiionn that directly addresses the disparate impact of pruning by imposing constraints gaps (CEAG). A key advantage of our proposed formulation is that it enjoys interpretable semantics: feasible solutions of our optimization problem correspond to models with low pruning- inddued disparity. Finally, our approach introduces a negligible computational overhead (Appendix E. compared to disspaitt-aanostic naive fine-tuning of the sparse model, making it applicable to problems with large numbers of groups, such as intersectional faimess tasks.
the per-group excess accuracy
"qqual contribution. Contact: me thashemi @yahoo. co.uk, uk, juan, rami rezêmi ququbec.

---

Published as a conference paper at ICLR 2024
Naive Fine Tuning Equalized Lows
Accuracy Gap sl. (99)
CEAG (Ours)
Noive Fine Tuning
Magnitude Pruning (GMP)
Equalied
White
Block
Asion
Indian
Others
CEAG (Ours)
Naive Fine Tuning
Equalized Loss
CEAG (Ours
6
Disparate Impact Vew (%)
Figure 1: Left: A dense model is sparsified with GMP, and then subjected to either (i) naive fine-tuning (NFT, using ERM), (ii) equalized loss constraints (Tran et al., 2022, EL), or (iii) approach (CEAG). Right: Positive (resp. negative) excess accuracy gaps (EAGs, $3.1) indicate groups whose performance degraded more (resp. less) than the model's overall accuracy change. Models with low disparate impact have EAGs that concentrate around zero. CEAG consistenly yields models with lower disparity (V pw, $3.1) than NFT and EL. For example, NFT yields 10% hyper-degradation (EAG, 1/)) on group Others. Results correspond to race prediction UTKFaae, with race as group attribute 90% sparsity. Metrics are measured on the training set and averaged over seeds.
Fig. illustrates the reliability of our approach at mitigating the disparate impact of pruning. We measure disparity in terms of excess accuracy gaps (EAGs, $3.1). Naive fine-tuning yields models that disproportionately affect group Others, and while the equalized loss formulation mitigates the issue, our formulation consistently reduces the pruning praning-induced induced disparity. See $5 for further discussion.
The main contributions our work' are as follows:
We formulate constrained optimization problem (CEAG, $3) that directly controls disparate impact by bounding group-level accuracy gaps between the dense and sparse models.
We propose algorithm for solving constrained optimization problems with non- differentiable, stochastic constraints ($4). We use proxy constraints (Cotter et al., 2019) to address ddddffferentiablity; and introduce replay buffers ($4.2) for handling noise in the estimation of constraints.
Our replay buffers improve the training dynamics of the equalized loss formulation proposed by Tran et al. (2022). The improved dynamics lead to better models in terms of disparity.
Our experiments demonstrate that we can reliably mitigate the disparate impact of pruning across multiple architectures, datasets, and sparsity levels ($5). These results carry over to tasks with intersectional groups, and up to hundreds of constraints.
Our experimental results indicate that all methods considered in this paper (including ours) fail to mitigate pruning-indee induced disparities on unseen data. To the best of our knowledge, we are the first document this generalization challenge. Despite this, proposed method constitutes step in the right direction since our approach is the only one that reliably mitigates the disparate impact of pruning on the training set. We hope our empirical observations will motivate further research on improving the generalization properties of methods for mitigating the disparate impact of pruning.
RELATED WORKS
Disparate Impact of Pruning. Hooker et al. (2019; 2020) and Paganini (2020) document the dis- parate impact of pruming where some classes experience more sigmificant performance degradation compared to others. Existing methods mitigate disparity involve fairnsss-aware pruning (Lin et al., 2022) or formulating constraints on a surrogate metric such as the loss (Tran et al., 2022).
Our code is available here: https:
jhashemi /bal anci agtact
2

---

Published as a conference paper at ICLR 2024
Lin et al. (2022) propose a pruning technique that removes weights based on a heuristic metric that relates parameters with their importance for predicting samples from each group. This approach scales poorly it requires computing importance scores for each weight and group.
Tran et al. (2022) apply constraints to match the sparse model's loss on each sub-group to the aggregate loss. These constraints are (i) agnostic to the performance of the dense model on each group and (ii) are based on the loss, which is a surrogate metric for assessing the accuracy- disparate impact. Since the disparate impact of pruning measured with respect reference model, the equalized loss formulation addresses the problem indirectly. Moreover, loss-based constraints lack the interpretability of the per-group accuracy changes between the sparse and dense models.
Fairness and Constraints. Independent of model pruning, fairess in machine learning models is a well studied problem (Dwork et al., 2012: Dieterich et al., 2016; Verma & Rubin, 2018; Mchrabi et al., 2021; Zemel et al., 2013; Zhao & Gordon, 2022). Enforcing faimess with constraints has mainly focused on imposing requirements such as demographic parity, equalized odds, equal oppor- tunity (Hardt et al., 2016), accuracy parity (Agarwal et al., 2018; Berk et al., 2021), ), or combinations of these properties (Zafar et al., 2017; Lowy et al., 2021; Bakker et al., 2020; Shui al., 2022). The disparate impact of pruming is fairness notion in the context of sparsity that aims to match the performance of a sparse model to that of a reference dense model.
Constrained Optimization. Constrained formulations have gained popularity in different sub-fields of machine learning such as safe reinforcement learning (Stooke et al., 2020), active learning (Elenter et al., 2022) and sparsity (Gallego- Posaaaa et al., 2022). These constrained formulations lead to stochastic min-max optimization problems, which can be challenging to optimize due to their non- convexity (Lin et al., 2020). We make use of proxy constraints (Cotter et al., 2019) to solve problems with interpretable but non-differentiable constraints.
Variance Reduction. The stochasticity in gradient estimates introduces additional optimization challenges (Beznosikov et al., 2023). Variance reduction techniques (Gower et al., 2020) have been employed to improve convergence on stochastic optimization (Defazio al., 2014), and in min-max games (Chavdarova et al., 2019). In this work, we leverage the idea of replay buffers (Mnih et al., 2013) to reduce the noise in the estimation of stochastic constraints.
3 ADDRESSING THE DISPARATE IMPACT OF PRUNING VIA ACCURACY GAPS
In this section, we propose using accuracy gaps (AGs) to quantify the disparate impact induced by model pruning. AGs are group-level measurements that quantify changes in accuracy between the dense and sparse models. As we will see, large discrepancies in AGs across groups correspond to scenarios where pruning-induced disparity is high. In $3.2, we propose problem formulation that yields models with low disparity by explicitly constraining deviations in the group accuracy gaps.
3.1 ACCURACY GAPS
We consider supervised learning problem on dataset D (<x,, Vi, 9i) 2 of N i.i.d tuples, each comprising features æ E X, target class E [K] and group membership E G. The dataset can be partitioned into sub-groups D, {(x; V.. 9i) E D
|g, = g}} for every g E G.
Let he X + R be a predictor with parameters 0 E O. The accuracy of he on sample set D is A(O)D) A DJ E(r.,.)eD 1 [argmax([hol( = y) In particular, A())D) denotes the model (g)))))))))))))) g) is the model accuracy on specific sub-group g. accuracy on the entire dataset, while A(o
Given access to a dense pre-trained model, we are interested in the effect of pruning on the accuracy across sub-groups Dg. In realistic pruning applications the dense model may exhibit different accuracies across sub-groups, thus we do not aim to equalize the accuracy of the sparse model across groups. Therefore, we argue that the accuracies after pruning should change (approximately) equally across sub-groups.
Let O. and O, denote the parameters of the dense and sparse models, respectively. We define the global accuracy gap A (O., Oz) and group accuracy gaps A, (0., 0a) as:
A (0,, O2) & A(Ox - A(0,12),
(I)
A, (,,, 02) A A 22y (g) Eg E g.
(2)
3

---

Published as a conference paper at ICLR 2024
A positive gap (resp. negative) corresponds to degradation (resp. improvement) in the performance of the sparse model with respect to that of the dense model. This correspondence holds both at the global A (0.. 0a) and group levels Ag (0., 0.)
Disparate Impact of Pruning. Following our discussion above, we say a sparse model ho, experi- ences low disparate impact (with respect to dense model he,) if the changes in performance similar across sub-groups, i.e. A, (0,, 0a) R Ay (0., 0a): Vg.g' E g.
Due to the loss of model capacity caused by pruning, typically A (0... 0a) > 0. Thus, consider A (O., Oa) as the reference point for defining the group excess accuracy gaps (EAGs):
v (0., 0a) - A, (0.,
(0., 0a), Vg E G.
If 9 (0., > O, then g is more negatively impacted by pruning than the overall dataset. Conversely, g (0,, 0a) < 0 indicates that group g' was less affected relative to the overall model degradation.
Note that if v0g = 0, Vg E G, then it follows that Ag (0., 0a) - Ag (0., Oa), Vg.g g E GG and there no disparate impact. Thus, we quantify the disparate impact of pruning via:
V Wise (0., 0a) A max 1/ (0.. Oa) d (0., 0a) = max A, (0., 0a) 9.9'E9
min A, (0., 0a). (4) 5 ''Eg
Note that Pw 0 always. Moreover, Pww 0 if and only if we are in ideal setting where the accuracy gaps are equal across all groups. However, aiming to constraint Vw directly can be difficult in practice (see Appendix B.3). Instead, consider constraints on each individual group EAG.
3.2 CONSTRAINED EXCESS ACCURACY GAPS FORMULATION
We propose to impose upper-bounds (with tolerance level 2 0) on the values of 1/ (0., 0z) S Since 2 0, the constraints are effectively only enforced on 1/ (0,, 0u) > O, corresponding to groups experieneing byper-degradation in performance (with respect the average degradation) Imposing a lower bound on group EAGs vh would allow for better control over the resulting disparate impact Ppw However, solving the problem with both of these bounds is challenging due to the small size of the feasible region relative to the estimation noise in the constraints. Appendix B.3 provides further discussion and motivation regarding the choice to constrain only positive 1i values.
This choice motivates an operational definition of disparate impact which focuses on the group with the highest EAG, given by maxg vgg. Bounding this quantity can be achieved by imposing constraints on every FAG. This gives rise to the following optimization problem with per-group constraints:
(CEAG) argmin L(O, s.t. 49 02) Ag (0., 0a) A (O,, 02) S E, Vg E 9 (5)
e,
where D() is the loss of he dataset D. and the tolerance 2 0 is the maximum allowed EAG.
When A (f., 0₂) > O, the constraints require that the performance degradation for each group be at most the overall model degradation plus the tolerance. Conversely, if A (0,,, 6x) < O, the constraints prescribe that all group accuracies must increase by at least the overall improvement, except for an c.
3.3 DISCUSSION
By formulating constraints on EAGs, CEAG directly addresses the disparate impact of pruning and has benefits in terms of interpretabilityy flexibility, and accountability. See Appendix B for alternative constrained formulations for addressing the disparate impact of pruning.
Tackling disparate impact. Existing methods aim to mitigate disparate impact by enforcing proper- ties on the sparse model while being agnostic to the performance of the dense model. Since EAGs relate the per-group performance of the dense and sparse models, we argue that our approach actually addresses pruning-induce disparity, rather than other fairness notions such as loss equalization as proposed by Tran et al. (2022).
Interpretability. The choice of tolerance level e directly translates to bounds on AGs. For example, setting 1% implies the worst affected class may not lose beyond 1% accuracy compared to the
Note that the set of heper-degraded groups (g E 9 v/ (0., 0z) > 0) depends directly on the parameters of the sparse model 0 and thus changes at every training step.
4

---

Published as a conference paper at ICLR 2024
overall model change. In contrast, it is challenging to set interpretable tolerance levels for constraints based on losses.
Flexibility. CEAG allows for some slack in the disparity of the pruned model, as prescribed by the tolerance e, This flexibility allows incorporating application-speccie
requirements into the learning procedure. For example, small tolerance values allow enforcing strict fairness regulations. Moreover, this flexibility may be necessary in practice since the reduced capacity of the sparse model can make impossible to attain 4, (0,, 0a) A (O., Oa) Vg G.
Accountability. Being a constrained approach, establishing feasibility with respect to CEAG constitutes clear success criterion determine if pruned model achieves acceptable disparity levels: model is only admissible if it satisfies the constraints at prescribed tolerance level.
4 SOLVING THE CONSTRAINED EXCESS ACCURACY GAPS PROBLEM
popular approach to solve constrained optimization problems such as CEAGin Eq. (5) to formulate its Lagrangian and optimize the resulting min-max problem:
min max 2(0,, A) - L(0,l2) + Σ Xa (1) (6,, 02) c),
(6)
0.E0 A20
gEG
where X, 2 is the Lagrange multiplier associated with the constraint for group and X Dglgeg We refer to 0₂ as the primal parameters, and À as the dual parameters.
Optimizing deep neural networks can be challenging, and generally requires carefully crafted proce- dures and extensive hyper-parament tuning (Choi al., 2019). We interested in re-using standard techniques for optimizing 0, Therefore, we consider a generic optimization protocol on 0, and gradient ascent on A, instead of specialized optimization approaches for min-max games such as extragradient (Gidel et al., 2019; Korpelevich, 1976).
4.1 OPTIMIZATION WITH NON- SE--DDIFFEENIABBLE CONSTRAINTS
natural next step to optimize Eq. (6) with gradient-based updates. Unfortunately, this is not possible as the b terms are not continuous (since they are accuracy gaps), and are non-differentiable with respect 0.. Therefore,
must resort surrogate b. for computing gradients with respect to 0, In contrast, Eq. (6) is differentiable with respect to X, with gradients corresponding to constraint violations. Thus, the dual variables be updated using the non-differentiable constraints 1/g. This update scheme is inspired by the proxy-come proxy-constraint technique introduced by Cotter et al. (2019).
argmin Ee A) - L(0.12) + EGES Ag (0., Oa) 0.E0
0: X
argmax (0 X) EnEc do (v% (0.. 0,) - -),
X20
Specifically, we choose surrogates v, given by the excess (negative) loss gaps: 3 (0,, & - -[1(0)/9)- + (L(O,)D) I(O,|D)). Note that Wy has the same structure as vig but replaces accuracy measurements with negative loss terms. This is reasonable choice of surrogate function since drops in accuracy for the sparse model correspond to increases in loss.
Eq. (7) represents two-player, non-zero-sum game. Rather than replacing the non-differentiabbl constraints with their surrogates everywhere, this approach only performs the replacement when necessary, i.e., for computing gradients for the primal parameters. Preserving the actual constraints on the dual objective Lx(0,. A) is useful as it results in a problem closer to Eq. (6).
Equation (7) can be optimized via gradient descent on 0, (based Ee) and gradient ascent on À (based on Σx). Alternating gradient descent-ascent (Alt-GDA) updates yield:
Ag (1+1) = ( + 77
((())
04 - -c)
(8)
0(++)) g(
Vol.
0 ( + Σ
((+
V Vorg (00)) Oz
gEg
5

---

PRIMALOPTIMPDDATEE(M grads) return Published as a conference paper at ICLR 2024
where 7/8 and !/ step-sizes and [+]+ max(:; 0). We initialize the Lagrange multipliers to A (0) 0. Appendix A contains more details non-convex constrained optimization.
Algorithm Constrained Excess Accuracy Gap (CEAG)
Input: O: Initial model parameters, T7: Primal step-size, JΙx Dual step-size, k: Memory size for replay buffer, e: Tolerance
B: Batch size, T: Total number of iterations, A dense' Accuracy of the dense model on each group 9, Adense: Aggregate accuracy of the dense model.
1: 0g + O, Vg EG
Initialize dual parameters D Initialize replay buffer
2: bufg f- queueek).
Eg
3: for iter = I...., do
4:
x.y.g t Sample {I Ys. 91 )= ~
> Sample batch from training set Calculate sub- grougroupp indices for batch
5:
idxg (g == 9), Vg
6:
ÿ < (x)
b. Compute forward-past
7:
Vg Eg 4. - QUEFESBUFERS 10 gl k (Alonse ) Adense)
buf, UUPAAEBBUFERCCUU y.y, idx)),
b Update replay buffer
8:
b Query replay buffers
9:
". + COMPUTESURROGATEÉN
idxx),
Vgg E
b Compute surrogates
10:
Xg + max(0, ' + ( })}, EgEg
b Update dual params
grady Vo (0( Eggg \g
D Compute primal gradient
Update model params
13: end for
4.2 STOCHASTIC CONSTRAINTS AND REPLAY BUFFERS
In practice, the problem in Eq. (5) solved by using mini-batch samples from the dataset to estimate the objective function, the constraints, and their gradients. This procedure can yield constraint estimates with high variance across mini-batches, especially for under-represented groups; or for all groups when the number of constraints is large. In extreme cases, a mini-batch may contain very few samples from given sub-group, leading to multiplier updates based on very noisy estimates.
We overcome these issues by estimating constraints based on information across multiple mini- batches. For calculating AGs, (i) we compute the performance of the dense model on the whole datasel (once at the beginning of training), and (ii) we estimate the accuracy of the sparse model from per-sample accuracy measurements on the most recent datapoints of each group. We refer to the data structure that stores historic accuracies used in reinforcement learning (Mnih et al., 2013). The choice of buffer size introduces a trade-off between reducing the variance of the constraints, and biasing estimates towards old measurements.
replay buffer (RB), given the analogy to the technique
These adjustments reduce variance the estimation of the constraints, thus yielding stable updates for the multipliers. This allows us solve Eq. (5) in settings with large numbers of constraints relative to the choice of batch size. We do not apply variance reduction on the model updates. For details on our implementation of replay buffers, see Appendix C. For experimental evidence on their benefits, see $5.3 and Appendix C.I.
4.3 ALGORITHMIC DETAILS
Algorithm presents our approach for solving CEAG. Note that Algorithm is applicable to broader class of constrained optimization problems with stochastic constraints, including the equalized loss formulation of Tran et al. (2022) (see Appendix B.I for details).
Computational Overhead. The constrained approach in Algorithm represents a negligible com- putational overhead compared to fine-tuning the sparse model with empirical risk minimization. An iteration of Alt-GDA (Eq. (8)) requires one forward pass and one backward pass through the model since the same iterate of 0, is used for both the primal and dual updates. This matches the cost of gradient descent for ERM, except for the minimal overhead associated with the evaluation of constraints after the forward pass. Note that, given our choice of surrogate, the gradient of the Lagrangian with respect to O, is weighted average of the per-sample loss gradients, which autograd

---

Published as a conference paper at ICLR 2024
frameworks compute efficiently as V&L (0, For empirical evidence supporting the claim that CEAG has negligible computational overhead compared to ERM, see Appendix E.1.
Memory Cost. The memory overhead of our approach is negligible in the context of training deep networks: storing the dual variables requires one float per constraint, and the replay buffers store only [g] booleans for each one of the i slots in the buffer memory.
5 EXPERIMENTS
In this section, we present an empirical comparison between naive fine-tuning, equalized loss (Tran et al., 2022), and our proposed CEAG approach. The main goal of our experiments is to train sparse models with low pruning-induced disparity. While low disparity may introduce a trade-off with aggregate performance, we aim achieve comparable overall accuracy to mitigation-agnostic methods. We explore the reliability and accountability of our approach, along with the effect of replay buffers on the constrained optimization problem. Our experiments demonstrate that our method successfully scales to problems with hundreds of groups.
5.1 EXPERIMENTAL SETUP
Tasks and architectures. We carry out experiments on the FairFace (Kärkkäinen & Joo, 2021) and UTKFace (Zhang et al., 2017) datasets, following the works of Lin et al. (2022) and Tran et al. (2022). Additionally, we perform experiments large number sub-groups, The choice of target and group attributes for each dataset is specified in Appendix D. The architectures for each task, and the source of our pre-trained models are presented in Appendices D.3 and D.4, respectively.
CIFAR- 100 (Krizhevsky, 2009), a task with
Baseline methods. We compare with three baseline mitigation methods (i) NFT: the last iterate when fine-tuning the sparse model via ERM, (ii) NFT+ES: the best iterate of NFT in terms of test accuracy (early stopping), and (iii) EL+RB: our re-implementation of the equalized loss formulation proposed by Tran et al. (2022), enhanced with replay buffers (see Appendix B. The optimization hyper- parameters employed for each mitigation method (including CEAG) are described in Appendix D.6.
Model pruning, Previous work has shown that gradual magnitude pruning (GMP) (Zhu & Gupta, 2017) achieves SOTA aggregate performance on unstructured sparsity tasks (Blalock et al., 2020). Because of this (and its simplicity). we employ unstructured GMP on all our tasks. GMP gradually prunes the model by removing parameters with the smallest magnitude once every epoch. The remaining weights are fine-tuned in between pruning episodes. We carry out GMP during the first 15 epochs. Appendix D.5 provides further details on our pruning protocol.
Choice of sparsity levels. For very high levels of unstructured sparsity (over 95%), Gale et al. (2019) observe that pruning has devastating impact on the overall performance of ResNet-50 models (He et al., 2016). In contrast, performance remains essentially unaffected for models with up to 85% sparsity. These observations may not carry over to other architectures such as MobileNets (Sandler et al., 2018), or other ResNets. Nonetheless, experiments stick to the [85%, 95%] range, except for FairFace experiments, where we consider 99% sparsity, akin to FairGrape (Lin et al., 2022).
Software. Our implementations use PyTorch 1.13.0 (Paszke et al., 2019) and the Cooper library for constrained optimization (Gallego-Posade & Ramirez, 2022).
Experimental uncertainty. All metrics reported in our tables and plots follow the pattern avg + std. Unless mentioned otherwise, all our experimental metrics are aggregated across 5 seeds.
For comprehensive experimental results across multiple tasks and sparsity levels, Appendix F.
5.2 FAIRFACE AND UTKFACE
ResNet-34 Models on FairFace. Table includes results for FairFace classification at 99% sparsity. We compare the behavior of NFT, NFT+ES, EL+RB, and CEAG. We quote the results reported for the FairGRAPE technique aggregated over seeds.
We observe that CEAG attains feasible model in training (max, Vi S c), as well as the smallest max, by both in the training and test sets. This does not come the cost of aggregate performance,
We do re-run FairGRAPE owing its high computational cost, see discussion in Appendix F.2
7

---

Published as a conference paper at ICLR 2024
all methods achieve comparable test accuracy of around 65%. We observe that FairGRAPE's maxg 2 and Pww are significantly higher than that of all other methods.
Table 1:
Race prediction task on FairFace with race as group attribute. CEAG achieves a maxy V/ within the prescribed threshold. Tol (e) the tolerance hyper-parameter of CEAG, We do not specify e for other formulations as they do not admit tolerance.
Train
Test Pw
Sparsity
Method
Accuracy
Pw
max, 1g
Tol (e)
Accuracy
max, 2i
NFT NFT ES
76.1 0.2
3.9 0.9
2.3 0.3
65.2 1 0.4
4.2 1 0.5
2.1
0.5
74.0 2.5
7.2 3.3
4.0 1.4
65.4 4 0.4
6.3 2.6
2.9 +
99
EL + RBB
76.1 0.1
8.8 1.3
2.6 0.2
65.1 + 0.4
6.0
2.4 0.4
PRiP
15.9
10.7
CEAG
76.2 1.1
0.6
1.4
2%
0.4
4.3 0.8
2.0 0.3
Table 2: Race prediction task on the UTKFace dataset with the intersection of race and gender as group attribute. For instance, if a sample has race Black and gender Female, group is CEAG consistently achieves maxg bh within the threshold, across sparsities.
Train
Test Prw
Sparsity
Method
Accuracy
Pw
maxg 1/g
Tol (c)
Accuracy
max, Vig
NFT
98.1 0.1
11.5 + 0.7
10.0 = 0.7
79.6 0.5
8.9 2.3
3.1
+ 0.5
NFT + ES
90.5 + 4.7
49.8 + 23.0
44.8 = 20.8
81.0 +1.0+-02
12.0 +.3
6.9
+ 4,8
90
EL + RB
3,2 0.6
2.4
79.4 0.5
1.94
3.0
CEAG
96.2
2.4 0.6
1.0 0.3
3%
80.2 -0.2
6.0
2.3 1.0
NET
95.1 0:2
34.2
30.7
79.2 +.2
8.8
NFT ES
91.2 = 2.7
53.3 9.6
48.0 = 8.3
80.4 0.4
7.5 +
5.4 3.1
92.5
EL. + RB
95.4
+ 0.3
11.1
+ 1.5
8.6 + 1.4
78.7 0.3
16.3 3.9
3.3 + 0.6
CEAG
93.4 0.3
3.8
+ 0.4
3%
79.5 0.1
10.8
2.2
1.0
Train
Test
100
81
Methods NFT RB
98
Accuracy (%)
Accuracy (%)
80
CEAG
96
Sparsity
79
90 %
91
10
Max Excess Accuracy Gap fmax, vol (%)
Max Excess Accuracy Gap [max, viyl (%)
Figure 2: Trade-off between disparity and accuracy for UTKFace race prediction with race group attribute. NFT and EL+RB yield models with high disparity. produces models that mitigate the disparate impact of pruning. CEAG's gains do not entail degradation in overall test accuracy. Vertical dashed lines indicate the tolerance (e) of our method, with colors corresponding different sparsity levels.
contrast, CEAG consistently
MobileNet- V2 Models on UTKFace. Fig. 2 illustrates results for UTKFace with race as group attribute. CEAG consistently attains feasible models in training, and the smallest values of max, Vi in the test set. CEAG attains comparable performance to NFT and EL+RB in the test set.
Table 2 presents results for UTKFace with intersectional groups (race n gender). NFT and NFT+ES have very high disparity metrics. contrast, CEAG attains a feasible max, Vi and the smallest Vpw in the training set, for all sparsities. Our approach has worse aggregate performance than NFT and EL in the train set; however, the test accuracy of these three methods is comparable.
For NFT, both Fig. 2 and Table 2 show significantly higher disparity metrics in training when compared to in test. This is an indicator that the sparse model achieves good performance training by overfitting the majority groups and losing lot of performance on the under-represent represeee groups.
8

---

Published as a conference paper at ICLR 2024
5.3 SCALING TO LARGE NUMBERS OF GROUPS
CifarResNet-56 models on CIFAR-100. Table 3 contains results for CIFAR-100 classification at 92.5% sparsity. By having the groups correspond to class labels, constrained formulations for this experiment have 100 constraints. We include two additional experiments to illustrate the importance of replay buffers: equalized loss (EL), and CEAG (no RB), both without replay buffers.
Disparity metries for EL and CEAG are better when employing replay buffers, both on the train and test sets. This difference is more notable for EL. We also observe the RBs improve the training dynamics of the dual variables (Appendix C.1). CEAG obtains the best disparity on the train set. Nonetheless, all approaches have a significant generalization gap in terms of disparity measurements. We observe that the best accuracy and the smallest máxg 1/ on the test set are obtained by EL+RB.
Table 3: CIFAR-100 100 classification with the group attributes being the class lahels, 92.5% sparsity. EL is the equalized loss formulation without replay buffers; CEAG (no RB) is similarly defined.
Train
Test Vpw
Sparsity
Method
Accuracy
pw
max Vg
Tol (6)
Accuracy
max 1/g
NFT NFT
99.8 + 0.0
3.7 1 0.9
3,0 0.9
64.9 + 0.4
26.2 5.2
14.3 + 34
99.3 + 0.2
1.9
5.8
65.2 - 0.4
27.4
14.6
2.0
92.5
EL.
98.5 0.1
11.3
0.9
9.8 + 1.0
65.3 + 0.5
25.8
2.0
14.1
+ 1.3
EL+ RB
99.5 0.0
6.7
1.4
+.7
65.3 + 0.4
24.2
24
13.3
+ 24
CEAG (no RB)
99.6 + 0.0
2.6 0.3
1.7 0.2
S 2%
65.0 + 0.4
27.2 + 2.6
14.9
+ 2.5
CEAG
99.6 -: 0.0
2.4 + 0.2
1.1
2%
64.8
0.3
25.0 1.9
13.8
DISCUSSION
It is important to develop techniques that reliably mitigate the disparate impact of pruning since deploying pruned models can have downstream consequences. We observe that NFT unsucessful doing this, and NFT+ES amplifies the disparity induced by pruning. In contrast, CEAG reduces disparity while achieving comparable aggregate performance to NFT. However, we observe that all mitigation approaches may fail to mitigate disparate impact on unseen data.
Mitigating the disparate impact of pruning. Unlike other mitigation methods, our approach consistently mitigates the disparate impact of pruning on the training set. We observe this across a wide range of tasks and architectures. In contrast, other mitigation approaches generally yield worse maximum degradation maxg Vg- In particular, NFT+ES yields models with very high disparity.
Accuracy trade-off. CEAG may introduce trade-off in terms of accuracy in order to satisfy the disparity requirements. On the train set, we observe small degradation in performance in comparison to NFT, typically of at most 2%; on the test set, CEAG's 's accuracy is comparable to that of NFT.
Reliability. Our approach reliably yields models within the requested disparity levels. Moreover, CEAG results in the smallest variance of the max, Vig and Vpw metrics across seeds.
Generalization. Although CEAG reliably satisfies the constraints on the train set, this may not transfer to the test set. We highlight that (i) these generalization issues are present for other mitigation methods, and (ii) our approach generally achieves better test disparity than the baselines. Improving the generalization of disparity mitigation methods is an important direction for future research.
7 CONCLUSION
In this paper, we explore mitigating the disparate impact of pruning. We formalize disparate impact in terms of accuracy gaps between the dense and sparse models, and propose a constrained optimization approach for mitigating it. Our formulation offers interpretable constraints and allows for algorithmic accountability. Although other methods can indirectly reduce disparity, our approach reliably addresses the disparate impact of pruning across wide range of tasks, while attaining comparable aggregate performance. In particular, our method successfully scales to tasks with hundreds of sub- groups. Despite the fact that current mitigation methods exhibit generalization issues, our approach represents a solid step towards mitigating the disparate impact of pruning.

---

Published as a conference paper at ICLR 2024
ETHICS STATEMENT
Facial recognition. Our paper makes use of datasets that contain face images. We focus on these datasets as they illustrate the disparate impact of pruning, and for comparisons with previous work. We would like to highlight that although our method focuses on reducing the disparate impact across groups, do not endorse the use of our algorithm in facial recognition systems.
Data annotation. We use the UTKFaae (Zhang et al., 2017) and FairFace (Kärkkäinen Joo, 2021) datasets in this work. These datasets include annotations for sensitive demo- graphic attributes such as race, gender, and age. However, essential to recognize that these annotations represent normative ways of perceiving gender, race, and age, and do not endorse or promote these normative categorizations.
Ethical sourcing of data. We don't It endorse using datasets where the data may not have been ethically sourced the workers/subjects involved in the data collection process not fairly compensated.
Fairness notions. We explore specific notion of fairness in this paper: the disparate impact of pruning- Our framework can be extended to other fairness notions by incorporating additional constraints. However, certain notions of fairness are incompatible with each other, and a "fair" model in one definition could be "unfair" with respect to another (Friedler et al., 2021). Therefore, our method should not be considered a solution all notions of fairness.
Disparate impact of pruning. In this paper, we propose constrained optimization technique that mitigates the disparate impact of pruning and successfully solve the problem on the training data. Unfortunately, like all other surveyed techniques, we observe significant challenges at mitigating disparate impact unseen data. We advise practitioners to consider the implications of these generalization challenges when deploying sparse models in real- world systems.
Deploying pruned models. We hope paper brings about important discussion the implications deploying pruned deep learning models edge devices. As shown in this work, despite the application of mitigation techniques, pruning can exacerbate systemic biases. In particular, given the generalization issues across mitigation methods, it could cause unintended consequences when used in commercial applications.
REPRODUCIBILITY STATEMENT
We provide our code", including scripts to replicate the experiments in this paper. The pseudo-code of our algorithm described in Algorithm 1. Experimental details, as well as the hyper-parameters used in our experiments, are included in Appendix D. Our implementation uses the open-source libraries PyTorch (Paszke et al., 2019) and Cooper (Gallego- Ramirez, 2022).
ACKNOWLEDGEMENTS
This research was partially supported by an IVADO PhD Excellence Scholarship, the Canada CIFAR AI Chair program (Mila), Google Excellence Award, and the Natural Sciences and Engineering Research Council of Canada (NSERC). Simon Lacoste-Julien a CIFAR Associate Fellow in the Learning in Machines & Brains program.
This research was enabled in part by compute resources, software, and technical help by Mila.
We would like to thank Nazanin Sepahvand for support in the initial stages of the project. We would like thank Christos Louizos for encouraging the pursuit of this research idea. Additionally, we would like to thank Marwa El- El-Halabi, Stefan Horoi and Albert Orozco Camacho for their feedback on the paper.
*Our code is available here: hww.ah/wwww...tgg.g////./..oooee /bal anci inccing-act aatt
10

---

Published as a conference paper at ICLR 2024
REFERENCES
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A Reductions Approach to Fair Classification. ICML, 2018. (Cit. on p. 3)
Michiel Bakker, Humberto Riverón Valdés, Patrick D Tu, Krishna P Gummadi, Kush R Varshney, Adrian Weller, and Alex Sandy Pentland. Fair Enough: Improving Faimesss in Boddet-Constrainee Decision Making Using Confidence Thresholds. In CEUR- WS 2020. (Cit. on p.p.3) p)
Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. Faimess in Criminal Justice Risk Assessments: The State of the Art. Sociological Methods & Research, 2021. (Cit. on p. 3)
Dimitri P Bertsekas. Nonlinear Programming. Journal of the Operational Research Society, 1997.
(Cit. on 16)
Aleksandr Beznosikov, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou. Stochastic Gradient Descent-Ascent Unified Theory and New Efficient Methods. In AISTATS, 2023. (Cit. on p)
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the State of Neural Network Pruning? In MLSys, 2020. (Cit. on p. 7)
Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ B. Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg. Antoine Bosselut, Emma Brunskill, Erik Brynjolfssonn, Shyamal Buch, Dallas Card, Rodrigo Castellon, Niladri S. Chatterji. Annie S. Chen, Kathleen Creel, Jared Quincy Davis, Dorottya Demszky, Chris Donahue, Moussa Doumbouya, Esin Durmus, Stefano Ermon, John Etchemendy, Kawin Ethayarajh, Li Fei-Fei, Chelsea Finn, Trevor Gale, Lauren Gillespie, Karan Goel, Noah D. Goodman, Shelby Grossman, Neel Guha, Tatsunori Hashimoto, Peter Henderson, John Hewitt, Daniel E. Ho. Jenny Hong, Kyle Hsu, Jing Huang, Thomas Icard, Saahil Jain, Dan Jurafsky, Pratyusha Kalturi, Siddharth Karamcheti, Geoff Keeling, Fereshte Khani, Omar Khattab, Pang Wei Koh, Mark S. Krass, Ranjay Krishna, Rohith Kuditipudi, and et al. On the Opportunities and Risks of Foundation Models. arXiv:2108.07255, 2021. (Cit. on p.
Luiz Chamon and Alejandro Ribeiro. Probably Approximately Correct Constrained Learning. In NeurlPS, 2020. (Cit. on 16)
Luiz FO Chamon, Santiago Paternain, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained Learning with Non-Convex Losses. IEEE Transactions on Information Theory, 2022. (Cit. on 16)
Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien. Reducing Noise in GAN Training with Variance Reduced Extragradient. In NeurIPS, 2019. (Cit. on p. 3)
Yaofo Chen. PyTorch CIFAR Models. http:///hhhbbccooooooooooocoocce 2021.
(Cit. p. 20, 21, 22)
D Choi, CJ Shallue, Z Nado. Lee, CJ Maddison, and GE Dahl. On Empirical Comparisons of Optimizers for Deep Learning. arXiv:1910.05444 2019. (Cit. on p. 5)
Andrew Cotter, Heinrich Jiang, Maya R Gupta. Serena Wang, Taman Narayan, Seungil You, and Karthik Sridharan. Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals. JMLR, 2019. (Cit. on p. 2, 3, 5, 16)
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives. In NewrIPS, 2014. (Cit. on
p. 3)
William Dieterich, Christina Mendoza, and Tim Brennan. COMPAS Risk Scales: Demonstrating Accuracy Equity and Predictive Parity. Northpointe Inc. 2016. (Cit. on p. 3)
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness Through Awareness. In Innovations in Theoretical Computer Science, 2012. (Cit. on 3)

---

Published as a conference paper at ICLR 2024
Juan Elenter, Navid NaderiAlizadeh, and Alejandro Ribeiro. A Lagrangian Duality Approach to Active Learning. In NeurIPS, 2022. (Cit. on p. 3, 16)
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the Lottery: Making All Tickets Winners. ICML, 2020. (Cit. on p. 21)
Sorelle A. Friedler, Carlos Scheidegger, and Suresh Venkatasubramanian. The (Im)Possibility of Fairness: Different Value Systems Require Different Mechanisms for Fair Decision Making. Commun. ACM, 2021. (Cit. on p. 10)
Trevor Gale, Erich Elsen, and Sara Hooker. The State of Sparsity in Deep Neural Networks. arXiv:1902.09974, 2019, (Cit. on p. 7, 20, 21)
Jose Gallego-Posada and Juan Ramirez. Cooper: a toolkit for Lagrangian- based constrained opti- mization. http://ghhhbbooooooppprrrrrr//// 2022. (Cit. on p. 7. 10, 20)
Jose Gallego-Posada, Juan Ramirez, Akram Erraqabi, Yoshua Bengio, and Simon Lacoste-Julien.
Controlled Sparsity via Constrained Optimization or: How Learned to Stop Tuning Penalties and Love Constraints. In NeurlPS, 2022. (Cit. on p. 3, 16)
Amir Gholami, Sehoon Kim, Zhen Dong, Zhewei Yao, Michael Mahoney, and Kurt Keutzer. Survey of Quantization Methods for Efficient Neural Network Inference. arX1v:2103.13660, 2021.
(Cit. on p.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julics A
Variational Inequality Perspective on Generative Adversarial Networks. In ICLR, 2019. (Cit. on p. 5, 16)
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley. Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative Adversarial Networks. In NeurIPS, 2014. (Cit.
on p. 16)
Robert M Gower, Mark Schmidt, Francis Bach, and Peter Richtárik, Seriance-Reduced Methods for Machine Learning. Proceedings of the IEEE, 2020. (Cit. on p.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of Opportunity in Supervised Learning. In NeurIPS, 2016. (Cit. on p.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. CVPR, 2016. (Cit. on p. 7, 20, 21, 29)
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the Knowledge in a Neural Network. In Deep Learning and Representation Learning Workshop at NeurIPS, 2015. (Cit. p. 1)
Sara Hooker, Aaron Courville, Gregory Clark, Yann Dauphin, and Andrea Frome. What Do Compressed Deep Neural Networks Forget? arXiv:1911.05248, 2019. (Cit. on p. 1,2)
Sara Hooker, Nyalleng Moorosi, Gregory Clark, Samy Bengio, and Emily Denton. Characterising Bias in Compressed Models. arXiv:2010.03058, 2020. (Cit. on p. 1,2)
Ignacio Hounie, Luiz FO Chamon, and Alejandro Ribeiro. Automatic Data Augmentation via Invariance-Consrriieee Learning. In /CML, 2023. (Cit. on p. 16)
Diederik Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. ICLR, 2014. (Cit. on p. 22)
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 1976. (Cit. on 5, 16)
Alex Krizhevsky. Learning Multiple Layers of Features from Tiny Images. Technical report, University of Toronto, Toronto, Ontario, 2009. (Cit. on p. 7, 702
Kimmo Kärkkäänen and Jungseock Joo. FairFace: Face Attribute Dataset for Balanced Race, Gender, and Age. In WACV, 2021. (Cit. p. 10, 20, 22)
12

---

Published as a conference paper at ICLR 2024
Tianyi Lin, Chi Jin, and Michael Jordan. On Gradient Descent Ascent for Nonconvex-Conent Minimax Problems. In ICML, 2020. (Cit. on p. 3, 16)
Xiaofeng Lin, Seungbae Kim, and Jungseock Joo. FairGRAPE: Fairness-Aware GRAdient Pruning mEthod for Face Attribute Classification. In ECCV, 2022. (Cit. on p. 2, 7, 15, 25, 26, 29)
Andrew Lowy, Sina Baharlouci, Rakesh Pavan, Meisam Razaviyayn, and Ahmad Beirami. A Stochastic Optimization Framework for Fair Risk Minimization. TMLR, 2021. (Cit. on 3)
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks. In ICLR, 2018. (Cit. on 16)
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A Survey on Bias and Fairness in Machine Learning. ACM computing surveys (CSUR), 2021. (Cit. on p. 3)
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Toannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing Atari with Deep Reinforcement Learning. In NeurIPS Deep Learning Workshop. 2013. (Cit. on p. 6)
Aryan Mokhtari, Asuman E Ozdaglar, and Sarath Pattathil. Convergence Rate of O(1/k) for Optimistic Gradient and Extragradient Methods in Smooth Convex- Convex-Concave Saddle Point Problems. SIAM Journal on Optimization, 2020. (Cit. on p. 16)
OpenAl. GPT-4 Technical Report. arXiv:2303.08772 2023. (Cit. on p. 1)
Michela Pagannii. Prune Responsibly. arXi::2009.099 09936, 2020. (Cit. on p. 1,
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, High-PPeformance Deep Learning Library. In NeurIPS, 2019. (Cit. on p. 7, 10, 20)
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical Text- Conditional Image Generation with CLIP Latents. In CVPR, 2022. (Cit. on p. 1)
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen. Mo- bileNetV2: Inverted Residuals and Linear Bottlenecks. In CVPR, 2018. (Cit. on p. 7, 20, 21, 26)
Changjian Shui, Gezheng Xu, Qi Chen,Jaaqe Li, Charles X Ling, Tal Arbel, Boyu Wang, and Christian Gagné. On Learning Fairness and Accuracy on Multiple Subgroups. In NeurIPS, 2022. (Cit. on p. 3)
Adam Stooke, Joshua Achiam, and Pieter Abbeel. Responsive Safety in Reinforcement Learning by PID Lagrangian Methods. In ICML, 2020. (Cit. on p. 3, 16)
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cris- tian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, lliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. I.lama 2: Open foundation and fine-tuned chat models. 092002 2023. (Cit. on onp.11
Cuong Tran, Ferdinando Fioretto, Jung-Eun -un Kim, and Rakshit Naidu. Pruning has a disparate impact model accuracy. In NeurIPS, 2022. (Cit. on p. 1, 3, 4, 6, 16, 20, 21)
13

---

Published as a conference paper at ICLR 2024
Sahil Verma and Julia Rubin. Faimnsss Definitions Explained. In International Workshop on Software Fairness, 2018. (Cit. on p. 3)
J von Neumann. Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100(1):295-320, 1928. (Cit. on p. 16)
Muhammad Bilal Zafar, Isabel Valera, Manuel Rodriguez, Krishna Gummadi, and Adrian Weller. From Parity to Preference-basee based Notions of Faimess in Classification. In NeurlPS, 2017. (Cit. on 3)
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning Fair Representations. In ICML, 2013. (Cit. on 3)
Guodong Zhang. Yuanhao Wang, Laurent Lessard, and Roger B Grosse. Near-optimal Local Convergence of Altemaaiin Gradient Descent-Ascent for Minimax Optimization. In AISTATS, 2022. (Cit. on p. 16)
Zhifei Zhang, Yang Song, and Hairong Qi. Age Progression/Regresion by Conditional Adversarial Autoencoder. In CVPR, 2017. (Cit. on 7, 10, 20)
Han Zhao and Geoffrey J Gordon. Inherent Tradeoff's in Learning Fair Representations. JMLR, 2022. (Cit. on p. 3)
Michael Zhu and Suyog Gupta. To Prune, or Not to Prune: Exploring the Efficacy of Pruning for Model Compression, arXiv:1710.01877 2017. (Cit. p. 7, 20, 22)
14

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
A Constrained and Min-Max Optimization
16
B Alternative Constrained Formulations
16
B.1 Equalized Loss
16
B.2 Constrained Excess Loss Gaps
17
Constrained W Pw
C Replay Buffers
18
C.I Training Dynamics with Replay Buffers
19
C.2 Replay Buffer Size Ablation
19
D Experimental Details
20
D.1 Tasks and Protected Attributes
................................
20
D.2 Mitigation Schemes
................................
20
D.3 Model Architectures
21
D.4 Pre-Trained Models
21
D.5 Gradual Magnitude Pruning
22
D.6 Primal Optimization parameers
22
D.7
Dual Optimization Elyper-parameted
23
E
Additional Experiments
24
E.1
Computational Overhead
24
E.2
Comparison FairGRAPE (Lin 2022)
:...............................
25
E.3
Sensitivity Analysis
25
F
Comprehensive Experimental Results
25
E1 UTKFace
26
FairFace
29
F3 CIFAR-100
32
15

---

Published as a conference paper at ICLR 2024
A CONSTRAINED AND MIN-MAX OPTIMIZATION
Lagrangian- based constrained optimization has gained popularity in machine/deep learning owing to the fine-gre arni-graieed control it provides over specific properties of models (Cotter et al., 2019; Stooke et al., 2020; Elenter et al., 2022: Gallego-Posade et al., 2022; Hounie et al., 2023). In the context of our work, attaining a desired disparity level can done directly by imposing the excess accuracy gap constraints presented in Eq. (5). In contrast, achieving bounded disparity by augmenting the training objective with additive penalties is challenging as requires iteratively tuning a penalty coefficient per group (Gallego-Posaaee Posada et al., 2022).
The Lagrangian-barn based approach involves solving non-convex-concave min-max optimization problem. In general, as long the constraints differentiable, the min-max problem can be optimized with gradient-basee updates. Fortunately, Cotter et al. (2019) show how even when the constraints are non-differentiable (but differentiable surrogates available) proxy constraints can be used to find a semi-coarse correlated equilibrium of the min-max problem.
The solution to the min-max optimization problem (i.e. saddle point) associated with the Lagrangian corresponds to global constrained minimizer of the original constrained problem (Bertsekas, 1997). However, saddle point of the Lagrangian may not exist for non-convex problems (Cotter al., 2019; von Neumann, 1928).
In the context of machine learning, the success of adversarial formulations such GANs (Goodfellow et al., 2014) and adversarial training (Madry et al., 2018) has sparked interest in min-max optimization. Lin et al. (2020) prove local linear convergence for simultaneous gradient descent-ascees ascent in the non- convex-concave setting. Moreover, Zhang et al. (2022) prove local linear convergence of Alt-GDA in the ceoonnly-conve--cmeee
setting. They observe that the iteration complexity of Alt-GDA is optimal (Mokhtari et al., 2020), thus matching that of extragradient (Korpelevich, 1976; Gidel et al., 2019). These observations motivate our choice of Alt-GDA for optimizing Eq. (5).
Recent work has studied the statistical properties of constrained optimization problems (Chamon & Ribeiro, 2020; Chamon et al., 2022). This line of work has formulated PAC generalization bounds on feasibility and optimality, arguing that learning with constraints is not more difficult problem than learning without constraints (Chamon & Ribeiro, 2020).
B ALTERNATIVE CONSTRAINED FORMULATIONS
This section elaborates alternative constrained formulations for mitigating the disparate impact of pruning. Appendix B.1 presents the equalized loss formulation of Tran et al. (2022), Appendix B.2 describes problem that constrains excess loss gaps of the sparse model, and Appendix B.3 formulates problems that (approximately) equalize the per ger-group excess accuracy gaps.
B. EQUALIZED LOSS
Equation (10) presents the equalized loss formulation for mitigating disparate impact (Tran et al., 2022). This formulation matches the loss of each group with the overall loss.
argmin L(O S.t. 6ce
- 0, VgEg
(10)
Tran et al. (2022) provide theoretical arguments to link disparate impact (in terms of group-level excess loss gaps) to the loss each group. This justifies their choice of constraints.
Our implementation of this approach follows pipeline akin to Algorithm we optimize it with alternating gradient descent-ascens and use group replay buffers to reduce variance in the estimation of the constraints for updating the dual variables. The storage cost associated with the buffer this setting is higher than that for CEAG, since per-sample losses (floating point numbers) stored instead of accuracies (booleans).
As shown in Appendix C. notice smoother training dynamics for the multipliers when using the replay buffers. Table shows how the equalized loss formulation benefits from them in terms of mitigating the disparate impact of pruning.
16

---

Published as a conference paper at ICLR 2024
B.2 CONSTRAINED ExCESS Loss GAPS
An alternative to both CEAG and Eq. (10) is to constrain loss gaps between the dense and sparse models. This yields the following constrained excess loss gaps problem:
argmin I(0,|2)
(11)
0,E0
s.t. 3 - (L(0,)))) L(0,12,))
s.
Vg e
This formulation addresses the disparate impact of pruning, although in terms of loss gaps instead of accuracy gaps. Selecting a tolerance for this formulation can be challenging as requires specifying acceptable levels of excess loss gaps, which can vary significantly across tasks.
B.3 CONSTRAINED PW
Constrained disparate impact. A natural formulation to consider involves constraining the disparate impact, as defined in Eq. (4). The constrained optimization can be formulated as:
argmin L(O,[D), S.L. P/ww = max A (0., 0a) min A, (0., 0a) Se. geg
(12)
0.E0
gEg
The constraint on Vew considers the difference between the most and least degraded groups. There- fore, when calculating the gradient of the Lagrangian, only the contribution from said extreme groups appears. This "lack of signal" may make optimization dynamics challenging, illustrated Fig. The formulation successfully mitigates the disparate impact problem in the context of race prediction for UTKFaae dataset, which features sub-groups. However, when confronted with the CIFAR-100 dataset, encompassing 100 sub-groups, gradient-based approaches to solve Eq. (12) unable to identify a feasible solution. For both of these scenarios, we observed that the value the (single) Lagrange multiplier grew continuously, without settling, confirming the previous intuition regarding poor optimization dynamics.
UTKFace
CIFAR-100
2ew (%)
50
50-
25
0
0
10
20
30
40
50
60
Epoch
Epoch
Figure 3: Evolution of disparate impact of pruning (Vew) during training under Eq. (12). Left: UTKFace dataset 92.5% sparsity. Right: CIFAR-100 dataset 95% sparsity. The horizontal dashed lines indicate the tolerance (E) of 5% and 10%, respectively.
potential approach to alleviate this problem could be to introduce constraints on the pair-wise accuracy gaps:
argmin L(O,)D), 8.E0
s.t. - < A, (0., 0z) - A, (0., 0a) S, Vg.g' E
(13)
However, this alternative formulation requires quadratically many constraints in the number of protected groups and does not scale situations where the number of protected groups is large.
Equalized excess accuracy gaps. Equalizing the per-group excess accuracy gaps to zero gives rise to the following formulation:
(0.. argmin L(O,)D), s.t. b = (0. 0.) - A (0.. 0.) = -0, Vg E G.
(14)
e
Compared to CEAG, this formulation (i) does not have an additional tolerance and (ii) prevents groups from having negative EAGss.
e,
17

---

Published as a conference paper at ICLR 2024
However, Eq. (14) can be challenging to solve because it may not have any feasible solutions; equalizing accuracy values may not be possible due to their discrete nature. Moreover, the lack of a tolerance hyper-pane apeer-paraeete hurts flexibility disparity requirements cannot be incorporated into the problem formulation.
Approximately equal excess accuracy gaps. A possible way to circumvent the limitations of Eq. (14) is to formulate the constrained problem:
argmin L(0,)2),
S.L. 1//gl A (0., - (,, se, VgEg.
(15)
0,E0
Feasible solutions of Eq. (15) achieve Vew 2c by imposing both an upper and lower bound on per-group EAGs. Compared to CEAG, this formulation prevents groups from experiencing large improvement performance compared the global accuracy gap. Compared to Eq. (14), allows for some tolerance at satisfying the equality. Naturally, for reasonable values of e, Eq. (15) has non-empty set of feasible solutions.
However, since the feasible set of Eq. (15) is small (as prescribed by e), solving it is challenging, especially in the context of stochastic optimization. Mini-batch estimates of the constraints have a high chance of being infcasible due to the small feasible region and noise in the estimation. This leads to updates on the dual variables that are positive most of the time. In turn, this yields dual variables that perpetually increase and never stabilize.
Two-sided inequality. Alternatively, two-sided inequality constrained optimization problem is:
argmin L(O, (2) 0,E0
(16)
s.t. Vig A (0,, 0.) - A O.) s,, Eg -/ (A, (0., 0.) - A (0,, 0.)) e, Vg
(17)
(18)
This problem allows for individual dual variables to behave akin to those of CEAG. However, note how the two constraints for each EAG introduce conflicting terms to the gradient of 0g: the model would aim to increase or decrease 1ig depending on the current values of the dual variables.
Discussion. We focus Eq. (5), and argue that constraining negative EAGs is crucial for mitigating disparity. A side effect of this choice allowing for sparse models whose group AGs are arbitrarily below the overall AG. In practice, this may lead to some groups improving their perfor- mance while the overall model accuracy decreases. We argue that this behavior is not problematic since it only likely to manifest for under-represented groups: groups with few samples can deviate in performance from other groups, without significantly influencing overall accuracy.
Eqs. (14) to (16) consider bounds on negative EAGs, but carrying out experiments on them outside the scope of our work.
C REPLAY BUFFERS
Algorithm 2 Update Buffer
Input: bu fg: Buffer for group y: A batch of model predictions, y: The batch of true targets, idx,: The sub-group indices of the batch.
1: function SUPDATEBUIFER(WN)
V, y, idx;)
2: SampleAcc + (y == y)x,
3: buf, +- PUsH(buf., SampleAco
b Drops old elements to respect capacity le
4: return bufg
5: end function
Algorithms 2 and 3 contain functions for updating and querying the replay buffers. respectively. These are called by Algorithm 1. Note that we wait until a buffer has been filled before considering its contents for computing the thg terms. Before buffer is filled, its corresponding bh is O.
For all groups, we consider the same buffer memory size k. Thus, the effective dataset used when computing EAGs of the sparse model is balanced across groups: it has & samples per group. However, when the original dataset is not balanced, this design implies that over-represented classes refresh their buffers faster as oppossed under-representte classes.
18

---

Published as a conference paper at ICLR 2024
Algorithm 3 Query Buffers
Input: bufg, Vg E G: All replay buffers, k: Memory size for the replay buffers, Aense Accuracy of the dense model each group 9; Adesse Aggregate accuracy of the dense model.
1: function QUERYBUFFFRSS(bUS g= k. { g=1> A dcase)
2: I {
Indices of full buffers
3:
for g E G do
4:
if LEN(buE, == k then
==
5:
t IU {g}
6:
SampleAce & QUERY(buf k) Alparse + AVERAGF(SampleAAG,,
Query all elements of each buffer
7:
8:
end end for
9:
10:
Asparse f- -AAEERAG(( Alparse (OEI)
Compute aggregate accuracy from full buffers
for
9 E 9 do
12:
if g E I then
Vg f (Apparse Alense) (Asparse - Adense)
14:
else
10g r
D Ignore non-full buffers 1/
16:
end if
17:
end for
18:
return (
19:
end function
C.I TRAINING DYNAMICS WITH REPLAY BUFFERS
In Fig. 4, we present the behavior of select multiplier in a CIFAR-100 experiment with 90% sparsity, We depict two training stages: the left, the multiplier consistently maintains non-zero value, while on the right, it is frequently around zero. Multipliers are initialized at zero, and are expected to increase during the first stages training when constraints may not be satisfied. Moreover, they expected to eventually stabilize at a value (possibly zero) if their corresponding constraint is inactive the solution.
On the left plot, we observe a smooth curve for the dual variable corresponding to the run with replay buffers. In contrast, the dual variable for the run without buffers is more noisy. On the right plot, the multiplier associated with the run without buffers becomes active more frequently than the multiplier of the run with buffers. Given the small magnitude of these multipliers (up to 0.003), the constraint may actually be feasible in this region and so the desirable behavior is to keep multipliers O.
0.02
0.0030
No Buffer
With Buffer
Multiplier
0.01
0.0015
0.0000
7600
7800
8000
8200
8400
8600
18500
18700
18900
19100
19300
19500
Step
Step
Figure 4: Effects of replay buffers on the multiplier dynamics on CIFAR-100 under 90% sparsity. As expected, the multiplier exhibits notably smoother dynamics when using replay buffers.
C.2 REPLAY BUFFER SIZE ABLATION
Table 4 showcases the effect of the choice of buffer size in terms of accuracy and disparate impact. We observe that having a buffer is beneficial in terms of the train and test max, ei while yielding models with similar accuracy those obtained without replay buffers.
19

---

Published as a conference paper at ICLR 2024
Table 4: Effects of the memory size of replay buffers CIFAR-100 task 95% sparsity. Not using a buffer yields poor results in terms of max, 4/-- For experiments with buffers, different choices of memory sizes yield comparable results. We consider tolerance of 5%.
Train
Test
Buffer Size (k)
Accuracy
max, 4
Accuracy
max, V9
No Buffer
95.8 + 0.15
5.8 + 0.53
62.5 + 0.41
17.1 + 3.59
20
95.7 = 0.10
5.4 : 0.69
62.6 = 0.30
16.0
2.82
40
95.6 + 0.12
5.7 0.49
62.7 = 0.28
14.8 + 1.52
60
95.6 + 0.16
5.5
62.7 0.26
14.5 1.92
80
95.6 0.17
5.5 0.42
62.8 1 0.44
16.4 1 4.59
We observe that changing the buffer size has a small impact in terms accuracy. In terms of max, d/g. the smallest (20) and largest (80) choices of buffer size result in more significant overfitting compared to 40 and 60. Moreover, the maximum EAG in test shows high variance in these cases. Table 4 motivates our choice of 40 for most experiments.
D EXPERIMENTAL DETAILS
Our implementations are PyTorch 1.13.0 (Paszke et al., 2019), with the Cooper library for Lagrangian-based constrained optimization (Gallego-Posada & Ramirez, 2022).
Pipeline. As illustrated in Fig. 1, our pipeline consists of stages: (i) obtaining a dense pre-trained model, (ii) pruning said model using gradual magnitude pruning, and (iii) fine-tuning the sparse model using either empirical risk minimization, the equalized loss formulation Tran et al. (2022), or our approach.
Dense models. Except for tasks involving the UTKFace dataset, we use publicly accessible pre- trained dense models. Appendix D.4 provides references to the pre-trained models we use throughout this work.
Pruning. We perform unstructured, layer-wise, gradual magnitude pruning (Zhu & Gupta, 2017) with cubic sparsity schedule (see Appendix D.5). We sparsify the weights of the model, but not the biases. We also do not sparsify the input and output layers of the model, as recommended by Gale et al. (2019). See more details in Appendix D.3.
Tolerance level We choose the tolerance level for each experiment by running NFT, measuring its corresponding max, v and choosing value of below this level. This protocol is ran independently for every task and every sparsity level. Finally, note that since EL imposes an equality constraint, there is no tolerance hyper--arameter to be chosen.
D. TASKS AND PROTECTED ATTRIBUTES
We carry out experiments on the UTKFace (Zhang et al., 2017), FairFace (Kärkkäinen & Joo, 2021), 1), and CIFAR- 100 (Krizhevsky, 2009) datasets; these respectively employ MobileNet-V V2 (Sandler et al., 2018), ResNet-34 (He et al., 2016), and CifarResNet-50 models (Chen, 2021), using different sparsity levels. These details are summarized in Table 5.
We highlight the data transformations and the batch size we employ for each dataset in Table 6.
D.2 MITIGATION SCHEMES
This section describes the approaches considered throughout this work for fine-tuning the sparse model, with without scheme to mitigate the disparate impact of pruning. We fine-tune sparse models on UTKFaae and CIFAR for 45 epochs, and for 32 epochs on FairFace.
Naive Fine Tuning (NFT). The sparse model is fine-tuned the training using ERM.
20

---

Published as a conference paper at ICLR 2024
Table 5: Tasks considered throughout this work.
Predicted Attribute
Group
Dataset
Model
Sparsity
Attribute
Race
Race
85, 90, 92.5
UTKFace
MobileNet- V2
Gender
Race
85, 90, 92.5
Race
Race n Gender
85, 90, 92.5
Race
Race
99
FairFace
ResNet-34
Gender
Race
99
Race
Race n Gender
99
CIFAR-100
CifarResNet-56
Class
Class
90,92.5, 95
Table 6: Transformations and batch sizes considered for each dataset.
Transformations
Dataset
Batch Size
Train
Test
UTKFace
Pp (0.5)
128
Resize (224, 224)
FairFace
Resize (224,229)
256
RandomHorizontallF/ (0.5)
CIFAR
128
Naive Fine Tuning with Early Stopping (NFT+ES), Obtained by selecting the best iterate of NFT in terms of test accuracy. We analyze this approach since early stopping is popular technique deep learning practice and, as evidenced by our experiments, often results in higher disparity (compared to the last iterate in NFT).
EL. Our implementation of the equalized loss method proposed by Tran al. (2022). More details of this formulation can be found in Appendix B.I.
EL+RB. Enhanced version of EL employing replay buffers ($4.2) for updating the dual variables.
The replay buffers store the per-sample losses observed at the mini-batch level across groups.
CEAG. Our constrained excess accuracy gap approach (see $4.3), which uses replay buffers by default.
D.3
MODEL ARCHITECTURES
We employ MobileNet-V V2 (Sandler et al., 2018), ResNet-34, and CifarRessNet-56 models (He et al., 2016). ResNet-34 models composed of bottleneck residual blocks He al. (2016), while CifarResNett56 models use basic residual blocks (Chen, 2021).
Following Evei et al. (2020), across all models, do not sparsify the biases due their low footprint towards the total number of parameters. We also do not sparsify the first and last layers of the model recommended by Gale et al. (2019).
Table specifies the number of parameters of all considered architectures. We also provide the number of parameters remaining post-pru cest-pruning across the considered sparsities for the reader's convenience.
D.4 PRE-TRAINED MODELS
Reusing and fine-tuning of pre-trained deep learning models is common practice. For example, typical application pipeline might involve (i) obtaining a pre-trained model, (ii) fine-tuning on an application-spedte task, and (iii) pruning it before deployment.
Therefore, we concentrate on studying the behavior of mitigation techniques when applied to openly available pre-trained models.
21

---

Published as a conference paper at ICLR 2024
Table 7: Statistics the total number of parameters and active parameters at different sparsity levels for our employed architectures. 'Sparsifiable parameters indicate the number of parameters that may be removed during pruning (thus, excluding non-pree oon-rraaall parameters such as biases). 'Parameter counts reported for MobileNet-V2 and ResNet-34 models are for race prediction tasks on UTKFace and FairFace, respectively.
Total
Sparsifiable
Active parameters at sparsity:
Architecture
Params
Params 85%
90%
92.5%
95%
99%
MobileNet-V22
2,230,277
2,222,944 21,275,136
366,946
255,250)
198,709
ResNet-34t
21,288,263
241,751
CifarResNet-56
861,620
854,656
96,179
74,889
53,621
ResNect-34 models for FairFace use the weights provided by Kärkkäänen & Joo (2021).
CifarResNet-56 models for CIFAR-100 use the weights provided by Chen (2021).
We were unable to find publicly available pre-traines MobileNet-V V2 models for the UTKFace dataset. Thus, we train these from scratch (see details below). As part of our reproducibility efforts, we are making our pre-trained UTKFace MobileNet- V2 models openly available.
For training UTKFace models, we use SGD with an initial learning rate of 0.01, decayed by factor of 0.1 at training milestones of 60%, 80%, and 90% of total training epochs. We use a momentum coefficient of 0.9, and train for total of 50 epochs. These hyper-parameters are used both for race and gender prediction tasks.
The group-wise performance for all the dense models is reported in Tables 17, 18, 20, 21, 23, 24, 26, 27, 29, 30, 32 and 33.
D.5 GRADUAL MAGNITUDE PRUNING
As mentioned in $5.1, our experiments perform Gradual Magnitude Pruning (GMP), where fraction of the smallest weights (in magnitude) is pruned on every epoch. Zhu & Gupta (2017) consider the following cubic schedule prescribing the proportion of parameters prune at every epoch:
3
to 8: = ( - (1- (Tend - (o) At
E {to, to + At...,, to + (Tend - tt) (19)
where to is the initial training step, At is the pruning frequency (in epochs), Tend is final epoch of pruning, and 8; and 8y denote the initial and final sparsities, respectively.
Our experiments carry out GMP since epoch to 0, throughout Tend 15 14 epochs, and perform pruning once every epoch (At = 1).
D.6 PRIMAL. OPTIMIZATION HYPER- PARA
We make use of SGD with momentum as the primal optimizer for all of our experiments. In our initial ablation experiments the choice of primal optimizer, we found that employing SGD with momentum outperformed or matched the performance of Adam (Kingma & Ba, 2014).
For UTKFace and C10AR-100 datasets, we employ primal step size of 1 10-2 along with momentum of 0.9 (Polyak), and apply weight decay at the rate of 1 10-4.
For FairFace, we employ Nesterov momentum with step-size of 1- 10-3 and apply a weight decay of 1 10-2, Specifically, for race prediction tasks, we utilize momentum of 0.95, while for gender prediction tasks, momentum of 0.99 is employed.
Additionally, we use PyTorch's 's Mult Multiste istt StepLR as the learning rate scheduler, with decay 7 0.1 across all experiments. For UTKFaae and CIFAR-100,
set scheduler milestones at 60%. 80% and 90% of the total training epochs (including the execution of GMP). For instance, for a task that has 60 epochs where it employs GMP 15 epochs, the above milestones would activate at epoch 36, epoch 48 and epoch 54. For race prediction on FairFace we use a single milestone at 90%, while gender prediction FairFace constant learning rate of 1 10-2
22

---

Published as a conference paper at ICLR 2024
D.7 DUAL OPTIMIZATION
We employ stochastic gradient ascent the dual parameters (corresponding to the Lagrange multi- pliers) in all experiments. The choices of dual learning rate are presented Tables to 13.
We fix k 40 the memory size for the replay buffer. Preliminary ablations the choice of E [20, 80) showed low sensitivity to the specific value of this hyper-parameter (See Appendix C.2).
Note that the order of magnitude for the dual step-size choices is relatively consistent across datasets, tasks, sparsity levels and disparity tolerances. This highlights the ease of tuning exhibited by this hyper-parameter.
D.7.1 UTKFACE
Table 8: Tolerance and dual step-size for CEAG on UTKFace tasks.
Target Attribute
Group Attribute
Sparsity
Dual Step-Size (1)x)
Tolerance (%
85
2 10
0.5
Gender
Race
90
1-10
0.5
92.5
3 3-10-3
0.5
85
1 10
0.25
Race
Race
2.
1
92.5
2 2.10-3
1
1.
0.5
Race
Race n Gender
90
1.10-3
3
92.5
1 10
3
Table 9: Dual step-size for EL+RB on UTKFaace tasks.
Target Attribute
Group Attribute
Sparsity
Dual Step-Size (17)
85
1 1.10-1
Gender
Race
90
1. 1.10-
92.5
1-10-5
85
1.10-5
Race
Race
1-10-5
92.5
1.10-5
85
1.10-5
Race
Race n Gender
90
1.10-5
92.5
10
D.7.2 FAIRFACE
Table Tolerance and dual step-size for CEAG on FairFace tasks at 99% sparsity.
Target Attribute
Group Attribute
Dual Step-Size (77)
Tolerance e (%)
Gender
Race
1 10-6
1
Race
Race
1- 1-10-
2
Race
Race
Gender
1-10-5
0.25
23

---

Published as a conference paper at ICLR 2024
Table 11: Dual step-size for EL+RB on FairFace tasks.
Target Attribute
Group Attribute
Dual Step-Size (17x)
Gender
Race
1 10-3
Race
Race
1- 1-1003
Race
Race
Gender
1-10-a
D.7.3 CIFAR
Table 12: Tolerance and dual step-size for CEAG CIFAR tasks.
Target Attribute
Group Attribute
Sparsity
Dual Step-Size (77x)
Tolerance (%)
90
2 10
Class
Class
92.5
2 10 3
2
95
1 10-0
5
Table 13: Dual step-size for EL+RB on CIFAR tasks.
Target Attribute
Group Attribute
Sparsity
Dual Step-Size (7))
90
1 10-5
Class
Class
92.5
1. 10-5
95
1. 10-5
E ADDITIONAL EXPERIMENTS
COMPUTATIONAL OVERHEAD
Table 14 presents the wall-clock time of an experiment for different mitigation approaches CIFAR- 100 at 95% sparsity. Note that the reported time includes the 15 epochs of gradual magnitude pruning of the dense model, well the 45 epochs of fine-tuning.
Table 14: Runtime of different mitigation approaches on CIFAR- 100 at 95% sparsity. All runs are on NVIDIA A100-SXM4-8CCE GPUs. Runtimes average across runs for each mitigation method.
Min
Median
Max
Method
Wall-clock Time
Overhead wrt NFT
Wall-clock Time
Overhead wrt NFT
Wall-clock Time
Overhead wrt NFT
NFT EL
Ih Om 04s
1x
1h 3m 13s
1x
1h 12m 19s
1x
Ih 2m 37s
1.031x x
Ih 4m 34s
1.021
Ih 15m 50s
1.049
EL+RB
Ih 4m 15s
1.058x
1h 7m 10s
1.062x
17m 35s
1.073x
CEAG (No RB)
Ih 2m 08s
1.023x
1h 3m 08s
0.998
Ih 8m 35s
0,948x
CEAG
Ih 1m 58s
1.020x
1h 4m 28s
1.020x
1h 6m 27s
0.919x
We observe a negligible increase training time for constrained approaches that use replay buffers relative to NFT. For approaches that do not replay buffers, the runtime essentially the same as NFT. This overhead is especially insignificant considering that the CIFAR-100 problem involves 100 constraints.
24

---

Published as a conference paper at ICLR 2024
E.2 COMPARISON TO FAIRGRAPE (LIN ET AL., 2022)
Computational cost: As a benchmarking exercise, we re-ran the code provided by Lin et al. (2022) for UTKFace Race prediction and Race as protected group'. The method took more than 90 hours of compute time on an NVIDIA A1 - -0GB GPU. Given how prohibitively expensive this is, we refrained from running experiments with FairGRAPE, Furthermore, we expect the runtime to increase for tasks with larger numbers of protected groups.
Lin et al. (2022) apply their method on UTKFace, but remove race group Others from dataset. The authors state that this done as Others is an ambiguous class. Since consider the complete dataset our experiments, we can not compare directly to the numbers reported by Lin al. (2022).
UTKFace:
Although we could apply CEAG to the UTKFace dataset without race group Others, we choose not since observe that this group is generally the most disproportionately affected by pruning. Table 15 shows that NFT can achieve models with low disparity on UTKFace without Others, but presents significantly worse accuracy and higher disparity on experiments with Others.
Table 15: NFT results on UTKFace race prediction with race as group attribute, with and without race group Others.
Train
Test
Setup
Accuracy
Ppw
max, Vy
Accuracy
Pw
max, V'g
UTKFaae (without Others) UTKFace
99.5 = 0.0
2.0 + 0.16
0.5 + 0.00
86.7 + 0.55
10.9 + 1.68
7.4 # 0.14
98.2 = 0.0
9.9 1 0.82
8.7 1: 0.82
79.5 1: 0.46
6.1 + 1.60
2.2 ::: 0.68
E.3 SENSITIVITY ANALYSIS
Table 16 presents the sensitivity of our approach to the tolerance hyperparameter UTKFace race prediction task with race as group attribute.
Table 16: Race prediction task for UTKFace with race as group attribute, at 92.5% sparsity. All experiments use dual step size of 2 10-3 Results aggregated across 5 seeds.
Tolerance
Accuracy
max, 1
1.5
93.6 + 0.1
0.9
t 0.61
1.0
93.4
= 0,3
1.1
0,36
0.5
93.2
- 0.2
1.2
+ 0.44
93.2 1 0.2
0.9 1. 0.24
We observe small improvements performance for experiments with large tolerance values. For low tolerance values, we observe that feasibility is not attained. Moreover, the resulting max, the values are similar across the considered tolerances. These observations are indicative of robustness the choice of tolerance.
F COMPREHENSIVE EXPERIMENTAL RESULTS
This section contains the results corresponding to all experiments mentioned in Table 5 across all datasets, sparsities, and tasks considered in our work. As mentioned earlier, all metrics reported in our tables and plots follow the pattern avg + st.d. Unless mentioned otherwise, all our experimental metrics are aggregated across 5 seeds.
Some of the tables displayed below are extensions of tables presented in the main paper. Such tables have been clearly identified in the captions. For the tables reporting group accuracies, we report the numbers for both the dense model well all the sparse models.
Thhe FairGRAPE implementation he found here: https::////// https:://itthub.cc
/98/Fa PGRAPE
25

---

Published as a conference paper at ICLR 2024
F.1 UTKFACE
We use MobileNet-V2 Sandler et al. (2018), similar to Lin et al. (2022).
F.1.1 GENDER
Table 17: Groupwise train accuracy for gender prediction in UTKeaae with as protected attribute,
across sparsities.
Sparsity
Method
White
Black
Asian
Indian
Others
Dense
100.0
99,9
99.9
99.8
99.3
NFT
99.9 0.02
99.8 + 0.04
99.9
0.06
99.8 + 0.02
99.3 0.1
85
EL + RB
99.9 + 0.01
99.8 + 0.03
99.9
0.03
99.8 + 0.04
99.4 : 0.13
CEAG
99.9 + 0.03
99.8 + 0.06
99.9 +: 0.05
99.8 + 0.03
99.3 0.12
Dense
100.0
99.9
99.9
99.8
99.3
NFT
99.8 1 0.03
99.8 1 0.04
99.7 1: 0.09
99.6 1 0.1
98.9 - 0.17
90
EL + RB
99.8 0.05
99.8 + 0.05
99.7 0.09
99.6 + 0.08
99.0 = 0.17
CEAG
99.8 + 0.02
99.8 + 0.02
99.7 + 0.12
99.7 + 0.04
99.1 = 0.1
Dense
100.0
99.9
99.9
99.8
99.3
NFT
99.4 + 0.07
99.5 + 0.08
98.8 + 0.22
99.1 + 0.11
98.0 + 0.23
92.5
EL + RB
99.5 0.05
99.6 - 0.09
98.6 0.23
99.1 + 0.1
98.1 = 0.45
CEAG
99.1 = 0.22
99.3 = 0.28
99.6 + 0.12
98.7 0.11
98.5 = 0.29
Table 18: Groupwise test accuracy for gender prediction in UTKFace with race as protected attribute, across sparsities.
Sparsity
Method
White
Black
Asian
Indian
Others
Dense
94.2
95,0
89.5
93.2
89.5
NFT
92.0 + 0.42
94.0 = 0.82
87.0 + 0.62
92.5 + 0.37
88.6 = 0.83
85
EL + RB
92.1 0.45
94.2 i 0.52
87.2 0.72
92.1 0.41
88.4 = 0.4
CEAG
91.9 - 0.3
93.8 = 0.41
86.7 + 0.75
92.1 + 0.55
88.1 = 1.03
Dense
94.2
95.0
89.5
93.2
89.5
NFT
91.1 + 0.67
92.6 - 0.57
85.9 0.95
91.6 + 0.67
87.1 = 0.85
90
EL RB
91.0 + 0.1
93.0 - 0.38
86.4 4: 0.64
91.4 + 0.45
87.6 0.83
CEAG
91.0 + 0.56
93.2 + 0.64
85.5 0.73
91.8 + 0.64
86.3 + 1.03
Dense
94.2
95.0
89.5
93.2
89.5
NFT
90.5 0.67
92.6 1
85.1
91.0 0.89
87.3 1
92.5
EL + RB
90.2 1 0.54
93.2 1 0.66
85.0 1 1.57
90.6 1 0.4
86.6 1 1.35
CEAG
90.6 - 1.0
92.7 - 0.2
85.8 0.93
90.5 + 0.76
87.1 = 0.91
Table 19: Gender prediction UTKFace with race as group attribute, across sparsities. CEAG consistently achieves a max, 39 within the threshold, across sparsities.
Train
Test Ppw
Sparsity
Method
Accuracy
Vpw
max, Vig
Tol (c)
Accuracy
max, 1
0.01
0.3 0.15
0.0 0.02
91.5 = 0.25
+ 0.87
85
+
98.0 1.72
1.7 1.19
1.3 0.91
91.8 = 0.28
EL
0.02
0.18
0.0
91.5 -
1.9
CEAG
0.16
0.1 0.05
0.5%
91.3 - 0.3
+ 0.78
NFT
99.7 0.04
0.26
0.3 0.2
90.5 = 0.2
2,7 + 1.03
1,3 + 0.65
NFT ES
97.41.555
2.5
1.8 1.15
91.0 - 0.15
1.8 0.9
1.0 + 0.65
90
EL + RB
99.7 0.05
0,1
0.2 0.15
90.6 - 0.17
2.0 + 0.52
0.8 - 0.27
CEAG
99.7 0.03
0.1
0.2 0.05
S 0.5%
90.4 0.37
3.0 + 0.82
1.4 + 0.51
NFT
99.2 0.088
0.7 1.1
90.0 - 0.44
3.1 + 0.71
1.4 + 0.57
NFT ES
96.2 +: 1.82
3,0
2.2
90.4 = 0.37
2.8
+ 0.55
1.2 0.52
92.5
EL RB
99.2 + 0.07
1.3 0.34
0.9
89.8 = 0.29
3.1
+ 1.64
1.5 + 0.98
CEAG
99.1 4 0.14
0.8 0.24222
0.09
0.5%
90.1 = 0.52
2,2 4 0.75
1.0 0.2
26

---

Published as a conference paper at ICLR 2024
Train
Test
Methods
99.8
91.5
NFT
Accuracy (%)
99.6
Accuracy (%)
EL + CEAG
RB
91.0
99.4
90.5
Sparsity
99.2
85 %
90.0
90 %
99.0
92.5 %
89.5
0.5
Max Excess Accuracy Gap [max, 1//] (%)
Max Excess Accuracy Gap [max, vall (%)
Figure 5: UTKFace gender prediction with race as protected attribute.
F.1.2
RACE
Table 20: Groupwise train accuracy for race prediction in UTKFace with race protected attribute, across sparsities.
Sparsity
Method
White
Black
Asian
Indian
Others
Dense
99.8
99.7
99.9
99.8
99.5
NFT
99.7 + 0.08
99.6 + 0.11
99.8 + 0.06
99.7 + 0.06
99.0 + 0.13
85
EL RB
99.6 0.11
99.6 = 0.18
99.8 0.1
99.8 0.14
99.5
CEAG
99.6 = 0.13
99.5 = 0.17
99.7 + 0.09
99.7 + 0.19
99.8 = 0.09
Dense
99.8
99.7
99.9
99.8
99.5
NFT
98.6 = 0.26
99.2 = 0.24
99.3 0.04
98.9 + 0.2
89.0 = 0.79
90
EL + RB
98.4 = 0.19
98.8 = 0.18
99.2 + 0.22
98.7 + 0.3
94.3 0.61
CEAG
95.7 + 0.35
95.5 + 0.35
96.0 0.4
97.1 + 0.52
98.4 + 0.42
Dense
99.8
99.7
99.9
99.8
99.5
NFT
96.8 0.15
98.0 - 0.23
98.2 0.44
96.3 0.47
69.4 = 3.72
92.5
EL + RB
95.9 = 0.37
97.2 0.23
97.6 0.55
95.9 95.9 0.56
82.5 = 1.36
CEAG
93.2 0.28
92.9 0.74
92.8 0.99
93.9 0.79
95.4 0.35
Table 21: Groupwise test accuracy for race prediction in UTKFace with race as protected attribute, across sparsities.
Sparsity Method
White
Black
Asian
Indian
Others
Dense
90.6
87.9
88.5
80.7
29.2
NFT
87.3 + 0.24
84.4 + 1.32
86.7 + 0.82
74.9 + 1.01
31.0 = 1.55
85
EL RB
87.2 0.48
84.1 + 0.74
86.1 + 1.33
75.2 + 1.53
32.8
1.47
CEAG
86.5 + 0.31
84.3 + 1.31
85.7 + 1.25
75.3 + 1.26
32.1 + 2.36
Dense
90.6
87.9
88.5
80.7
29.2
NFT
86.5 + 0.52
83.3 + 1.28
84.2 2.46
74.6 + 0.44
28.8
1.95
90
EL + RB
86.2 - 0.94
83.7 = 0.91
83.6 + 1.15
75.3 + 1.08
31.4 = 1.33
CEAG
86.6 = 0.83
84.2 - 1.1
85.6 1.12
77.7 + 1.07
29.1 = 2.73
Dense
90.6
87.9
88.5
80.7
29.2
NFT
86.3 0.78
83.8 + 0.58
84.6 0.8
73.8 1.04
28.5 2.52
92.5
EL + RB
85.1 + 1.0
82.8 - 1.37
83.5 + 1.49
73.4 + 1.09
30.9 = 2.49
CEAG
85.5 0.6
83.0 0.65
84.6 1.66
76.3 0.47
31.8 2.38
27

---

Published as a conference paper at ICLR 2024
Table 22: Race prediction on UTKFace with race as protected attribute, across sparsities. CEAG almost always achieves a max, V9 within the threshold. It also has the minimum maNy 19 across sparsities.
Train
Test Vpw
Sparsity
Method
Accuracy
Vpw
max, %
Tol
Accuracy
max, 4
NFT
99.7
1:3:1:00 0.16
0.2
80.6
7.6 1:
2.7
NFT ES
92.1 4.2.2
35.1 1. 20.55
30.3 17.82
81.1 0.51
10.7 2.01
5.2 2.81
EL.+ RB
99.7 0.00
0.4 0.09
0.2 + 0.08
80.6 # 0.44
9.2 + 2.67
2.4 + 1.16
CEAG
99.6 +: 0.05
0.8 + 0.14
0,2 + 0.05
& 0.25%% /
80.3 = 0.5
8.4 + 2.95
2.0 +00+:00 0.91
NFT
98.2 +: 0.08
9.9 = 0.82
8.7 = 0.82
79.5 = 0.46
6,1 # 1.6
2.2 : 0.68
+ ES
90.6 4.72
45.5 1: 22.51
40.6 20.13
81.0 = 0.24
8,0 :: 4.73
5.3
90
EL
3.6
79.7
8.0
0.91
CEAG
96.1 0.1.1
3.5 0.51
0.8 0.26
S 1%
80.5 0.25
5.2 I: 1.86
1.5 D.2
NFT
95.1 0.36
28.2 3.49
25.3 + 3.35
79.4 0.17
6.1 6.0
2.5 +
NFT + ES
91.2 4.29
43.5 # 10.64
38.7 8.87
80.2 0.21
5.7 2.79
3,5 1 1.76
92.5
EL + RB
95.4
1: 0.22
14.6 1.31
12.5 1.12
78.6 0.33
9.0 3.2
2.2 :
CEAG
0.31 93.4
0.86
1.1 0.36
S x
79.6
8.0 2.59
0.43
Train
Test
100
81
Methods
NFT
Accuracy (%)
Accuracy (%)
EL RB CEAG
80
Sparsity
85 %
79
90
94
92.5 %
10
20
30
0
3
Max Excess Accuracy Gap fmax, voll (%)
Max Excess Accuracy Gap [max, vigl (%)
Figure 6: UTKFace race prediction with race protected attribute.
F.1.3 INTERSECTIONAL
For the sake of brevity, we use acronyms to refer the intersectional sub-groups. The acronyms are separated by dash, the initial part refers to the race and the later part refers to the gender. For instance, W-M refers White and Male. Other races B-Black, A-Asian, I-Indian, and O-Others.
Table 23: Groupwise train accuracy for race prediction in UTKFace with intersection of race and gender as protected attribute, across sparsities.
Spunsity
Method
B-M
09.5 0.14
09.7
90.7
09.9
99.9 0.1
90.7
CEAG
99.6 0.11
98.7 1: 0.1
99.6 0.2
99.7 1
99.7
100.0
0.04
99.7 0.17
99.9 007
99.4
0.14
99.6 0.17
Donse
90.7
99.9
99
09.8
99.8
99.9
99.7
99.9
99.3
90.6
90
EL RB
NFT
98.3
98.6 0.2
0.31
9800 0.20
98.4 à: 0,21
98.7 5 0.44
99.1 1 11.7
99.1 1: 0.23
98.6 3 0.28
99.2 a 0.24
98. 6 0.27
99.5 0.15
99.2
0.15
99.0 0.33
98.3
0.6
98.1
98.5 0.21
0.45
97.3 0.64
$1.7 1.07
89.9 1.85
95.6 0.59
CEAG
96.4 11:99
96.0
95.1
96.2
95.3 0.25
97.0 0.7%
95.7 0.00
96.2 0.57
96.0
96.6
Dense
99.7
99.9
99
99,8
99.8
99.9
99.7
99.9
99.3
99.6
98.2
99.8
0.54
05.1
96.0
97.1
28

---

Published as a conference paper at ICLR 2024
Table 24: Groupwise test accuracy for race prediction in UTKeaace with intersection of race and gender as protected attribute, across sparsities.
Sparsity
Method
A-M
I-M
1-F
87.3-001
EL
$7.3
$6.1 1.18
82:2 1.73
85.6 0:51
2:53
56.7
1.85
74.6 1.57
78.1 L:35
312 2.36
52.1 2.81
CEAG
57.2
0.63
85.8
0.76
82.6 1.27
86.0
0.96
$4.6 0:53
87.7
1.76
74.0 8: 1.18
77.2 2
31.5
1.55
52.3 -: 3.18
Danse
90.9
90.2
86.9
68.9
87.5
$9.3
$1.0
80.4
26.4
31.6
NET
36.8
0.57
86.4 0.97
81.9 1.5
85.2 1.1
82.2 2:46
$4.4 1.99
74,2 6: 0.53
75.4 1.09
26.8
3.26
51.6
1.74
FJ. + RR
85.9
1:17
85.6 1:31
82,5 0.58
83.8 0:48
83.4 1.95
85.0
2.00
73.8 1.72
76.1 1.45
30.3 1.31
52.3
2.81
CEAG
56.2
87.2
83.5
85.6
1.22
25,8
29.8
0.92
CEAG
56.8 0.64
85.3 1.22
82.5 1.47
84.8 4: 0.58
$1.8 4: 1.98
$6.2 = 1.15
73.7 1: 1.73
76.0 2: 1.41
29.5 d: 1.4
30.3 2: 2.73
Table 25: Race prediction task the UTKFace dataset with the intersection of race and gender as group attribute, across sparsities. For instance, a sample has race as Black and gender as Female, its group label is Slack-Female CEAG consistently achieves a max, 1/9 within the threshold, across sparsities. This table is an extension of Table 2.
Train
Test Vpw
Sparsity
Method
Accuracy
Vew
max, 1g
(e)
Accuracy
max, V
NFT
99.6 0.03
0.8 :: 0.26
0.5 4: 0.33
80.6 0.44
10.3
2.09
3.4 + 1.29
85
NFT ES
91.8 = 4.03
37.0 :: 21.45
31.8 : 18.93
81.2 0.4
13.0
= 3,29
5.2 2.03
EL RB
99.7
0.8 :
0.2 0.08
80.4
11.7
3.4
CEAG
99.7 0.03
0.5 4: 0.1
0.2 0.04
0.5% v
80.4 0.27
12.2
2.62
3.6 1.14
NET
98.1 0.06
11.5 0.72
10.0 = 0.67
79.6 0.49
8.9 2.35
3.1 0.46
NFT ES
90.5 4.73
49.8 = 23.02
44.8 = 20.76
81.0 31.0
12.0 5.34
6.9 4.779
FI. RB
98.3 + 0.19
3.2 +: 0.63
2.4 4: 0.61
79.4 0.5
11.4 = 0.91
3.0 1.06
CEAG
96.2 0.1
2.4 + 0.59
1.0 + 0.27
& 3%
80.2 +: 0.13
6.0 2,48
2.3 + 1.03
NFT
95.1 = 0.17
34.2 = 1.64
30.7 = 1.48
79.2 0.16
8.8 = 3.18
3.6
NFT ES
91.2 = 2.66
53.3 9.55
48.0 8.28
80.4 0.35
3.41
5.4
92.5
95.4 0.27
1.45
8.6
0.27
3.92
3.62
CEAG
93.4 0.31
3.8 = 0.4
2.3 0.41
53 v
79.5 0.14
10.8
3.3 1.02
Train
Test
100
81.0
Methods NFT EL + RB CEAG
80.5
Accuracy (%)
Accuracy (%)
80.0
79.5
Sparsity
*
85 %
79.0
90
92.5 %
78.5
10
20
30
0
2
Max Excess Accuracy Gap [max, vol (%)
Max Excess Accuracy Gap [max, vill (%)
Figure 7: UTKFace race prediction with race and gender (intersectional) as protected attributes.
F.2 FAIRFACE
We make of ResNet-34 models (He al., 2016) FairFace, similar to Lin al. (2022).
29

---

Published as a conference paper at ICLR 2024
F.2.1 GENDER
Table 26: Groupwise train accuracy for gender prediction in FairFace with race as protected attribute.
Sparsity
Method
East Asian
Indian
Black
White
Middle Eastern
Latino Hispanic
S.E.
Dense
97.2
97.1
94.9
97.4
98.0
97.2
96.8
NFT
99.4
99.4 = 0:23
98.9
0.12
99.3
= 0.14
99.5 = 0.15
99.3 = 0.2
99.2 = 0.31
99
99.0
99.6
99.2
CEAG
99.3
99.2 = 021
98.9
0.25
=
99,5 0.13
99.3 0.15
99.1 + 0.11
Table 27: Groupwise test accuracy for gender prediction in FairFace with race protected attribute.
Sparsity
Method
East Asian
Indian
Black
White
Middle Eastern
Latino Hispanic
S.E. Asian
Dense
95.2
95.6
90.0
94.2
96.6
95.2
94.4
99
NFT
86.5
0.48
93,4
0.59
EL. + RB
92.4 0.41
92.9 = 1.14
86.8
0.68
91.8 = 0.2
94,9 = 0.39
93.6
0.36
91.4 + 0.33
CEAG
92.8 4: 0.49
92.7 a 0.32
86.2 0.45
91.3 0.66
94.6 0.25
93.8
0.25
91.2 4: 0.55
Table 28: Gender prediction on FairFace with race as protected attribute. CEAG achieves a max₃ V9 within the threshold.
Train
Test Pw
Sparsity Method
Accuracy
Ppw
max bi
(c)
Accuracy
max 1ig
NFT NFT ES
99.3 = 0.17
2.6 + 0.23
0.9 0.13
91.8 0.17
2.4 0.81
1.1 + 0.42
97.6 = 1.29
1.5 : 0.67
0,5 0.19
92.2 0.13
0.45
1,5 : 0.35
99
EL + RB
99.3 = 0.09
2.7
+: 0.22
0.8 0.07
91.9 + 0.21
2.1 0.39
1.0
+ 0.34
FairGrapp
90.5
2.3
1.0
CEAG
99.2 0.14
2.7 0.22
0.9 0.07
15 /
91.7 + 0.1
2.4
+: 0.48
1.2 +: 0.44
Train
Test
92.1
Methods
99.4
92.0
NFT
Accuracy (%)
Accuracy (%)
X EL + RB
91.9
CEAG
99.3
91.8
S Sparsity
99.2
99
91.7
99.1
91.6
0.5
1.0
0.0
0.5
1.0
Max Excess Accuracy Gap [max, voll (%)
Max Excess Accuracy Gap [max, viel (%)
Figure FairFace gender prediction with race as protected attribute.
F.2.2 RACE
Table 29: Groupwise train accuracy for race prediction FairFace with race as protected attribute.
Sparsity
Method
Indian
Black
White
Middle
Latino Hispanic
Dense
84,8
81.9
90.9
84.7
76.8
68.0
74.1
99
NET
81.1 : 0.88
78,2 = 0.59
87.3
0.43
80.9
1.06
70.2 = 0.73
63.2
1.47
68.6 :: 1.18
RB
4 0.58
77.0 0.95
84,7
1.03
71.9
69.7
1.13
+ 1.13
CEAG
80.7 2 0.95
77.9 0.61
87.2 = 0.61
80.4 1.14
73.7
= 0.79
63.1 1.46
68.5 4 1.22
30

---

Published as a conference paper at ICLR 2024
Table 30: Groupwise test accuracy for prediction in FairFace with race as metrics attribute.
Sparsity
Method
East Asian
Indian
Black
White
Middle Eastern
Latino Hispanic
S.E. Asian
Dense
78.3
72.2
86,2
77.2
63.9
58.1
64.3
99
NFT
72.5 4: 0.98
65.8 = 0.97
81.4
0.41
70.1 = 1.34
55.7 = 0.94
50,9
1.19
56.1 :: 1.06
EL RB
70.6
65.0 1.24
79.3
0.8
56.5
0.54
54.8
1.07
57.7 1.86
CEAG
72.5 = 1.25
65.8 1.04
81.5 = 0.6
69.5 1.32
57.5
= 0.84
50.3
1.22
56.4 :: 0.89
Table 31: Race prediction task on FairFace with race as group attribute. Tol (c) is the tolerance hyper-parameter of CEAG. We do not specify c for other formulations as they do not admit a tolerance. CEAG achieves max, Vig within the threshold. This table is already presented the main paper as Table 1, we include this for completeness.
Train
Test Pw
Sparsity
Method
Accuracy
Vpw
max by
Tol (e)
Accuracy
max, 1/2
NFT
76.1 = 0.19
3.9 + 0.91
2.3 + 0.26
65.2 0.44
4.2 0.51
2.1 0.51
NFT ES
74.0 2.55
7,2 3.35
4.0 1.38
65.4 0.35
6.3 2.59
2.9 1.3
99
EI. RB
76.1 0.13
8.8 1.26
2.6.6.0.21
65.1 0.44
6.0
0.36
FairGrape
65.1
15.9
10.7
CEAG
76.2 = 0.13
3.5 0.61
1.8 0.442
2%
65.2 0.37
4:
2.0
Train
Test
76.3
65.6
Methods
NFT
76.2
65.4
X EL + RB CEAG
Accuracy (%)
Accuracy (%)
65.2
76.1
S Sparsity
65.0
76.0
99 %
64.8
75.9
64.6
Max Excess Accuracy Gap [max, (%)l (%)
Max Excess Accuracy Gap [max, vol (%)
Figure FairFace race prediction with race as protected attribute.
F.2.3 INTERSECTIONAL
For the sake of brevity, we acronyms to refer the intersectional sub-groups. The acronyms are separated by a dash, the initial part refers to the race and the later part refers to the gender. For instance, EA-M refers to East Asian and Male. Other races are I-Iniian, B-Black, W-White, ME-Middle Eastern, LH-Latino Hispanic, and SA-South East Asian.
Table 32: Groupwise train accuracy for race prediction in FairFace with intersection of race and gender protected attribute.
Bane
913
137
T10
22.4
040
120
6.1
103
913 1.2
698
1.15
125 6171
790 131
2233 833
198.13 1.35
015
26. 135
418-31
111-111
6731-121
Table 33: Groupwise test accuracy for prediction in FairFace with intersection of race and gender as protected attribute.
Sparsty
Methel
K4-M
BAF
I.
1-1
B-M
B-F
W-M
W1-2
ME-M
ME-F
LH-M
18--
54-M4
S4-7
Dame
75.0
964
75.
41.5
53.5
62.5
63.3
NF1
6144
147
105
11
76.
683
01.0
00.8
43.0
951
55.7
54.
CEAC
7677
763
013 141
The
835
811 633
684 125
305
60.
43. 124
576--443
5K. 1.0
31

---

Published as a conference paper at ICLR 2024
Table 34: Race prediction FairFace with intersection of gender and race protected attribute. CEAG achieves maxy 49 within the threshold.
Train
Test Ppw
Sparsity
Method
Accuracy
Pp
max, Vi
Tol (c)
Accuracy
maxg 4
0.17
5.2 0.94
2,9 0.42
65.3 = 0.45
+ 0.66
4:
NFT
73.7 2.33
8,9 3.83
4.6 2.14
65.4 = 0.37
+ 2.45
4.3 1,56
99
+L
4.0
0.15
65.1 =
+
0.36
CEAG
75.8 0.14
0.42
0.26
65.3 0.51
7.6 =
3.5 +
Train
Test
76.0
65.8
Methods
65.6
NFT
Accuracy (%)
75.9
Accuracy (%)
X EL + RB
65.4
CEAG
75.8
65.2
S Sparsity
99
65.0
75.7
64.8
Max Excess Accuracy Gap [max, 1/ll (%)
Max Excess Accuracy Gap [maxx, voll (%)
Figure 10: FairFace race prediction with race and gender (intersection) as protected attribute.
F.3 CIFAR-100
We consider CifarResNet-56 (Chen, 2021) models for this task. We consider scenario where both the target and group attributes correspond to the class labels. In the context of mitigating the disparate impact of pruming, want to ensure that none of the classes degrade more than the average degradation with a tolerance of e. The dense model performance is 72.61% %.
Table 35: CIFAR-100 classification with the group attributed being the class labels. CEAG yields the best model terms of disparate impact on the training set, and competitive in terms of Pw and max, 2/g on the test set.
Train
Test Ppw
Sparsity
Method
Accuracy
Yyw
8/2
Tol (e)
Accuracy
max, t
NFT
99.9 : 0.0
0.9 1 0.18
0.4 4: 0.18
66.7 :: 0.35
25.0
3.08
12.9
= 2.92
NFT +
99.9 1. 0.01
1.1
0.6
66.9 0.27
24.6
1.52
12.7
1.72
3.1
2,4
3.13
12.4
90
EL + RB
99.9 = 0.01
1.3 0.223
0.8 0.22
67.0 1: 0.38
23.6
1.52
12.2
2.06
CEAG (no RB)
100.0 0.01
1.0 1 0.09
0.4 0.09
S 1% /
66.4 1 0.31
26.4
1.3.21
13.8
1.77
CEAG
99.9 0.01
1.0 : 0.09
0.4 0.08
1%
66.7
23.4
1.52
12.5
NET
99.8 0.02
3.7 0.86
3.0 0.87
64.9 0.39
26.2
1.2.2
14.3
3.39
NET ES
99.3
6.8 1: 1.9
65.2
27.4
14.6
1.97
EL
98.5 1 0.09
11.3 0.09
9,8 0.95
65.3 0.51
25.8 2.2.0
14.1
1.29
92.5
EL + RB
99.5 = 0.01
6.7 + 1,42
5,7
65.3
24.2 2.86
13.3
2.35
CEAG (no RB)
99.6 = 0.04
2.6
0.19
2%
0.37
27.2 2.59
14.9
2,48
CEAG
99.6 0.04
2.4
0.15
S 2%
64.8 0.3
25.0 1.87
13.8
1.16
NFT
96.2
14.8
11.1
62.6 -:
28.4 3.21
15.6
NET + ES
93.9 = 0.83
20,0
1.52
14,6 1.43
63,3 0.21
+:555
16.1 3.22
EL
87.9 = 0.45
21.4 + 1.36
14.5 1.31
60.7 - 0.48
32.8 3.7
16.1 4.57
95
18.4 1.05
0.16
27.4
14.8
CEAG (no RB)
95.8 0.15
9.2
0.53
< 5%
62.5
29.6 4.34
17.1 3,59
CEAG
95.6 0.12
9.1 + 0.64
$.7 4 0.49
S 5% X
62.7 4: 0.28
27.6 + 1.14
14.8 1.52
32

---

Published as a conference paper at ICLR 2024
Train
Test
100
Methods
99
NFT
Accuracy (%)
98
Accuracy (%)
66
X EL + RB
CEAG
65
Sparsity
96
64
90 %
92.5 %
95
63
95 %
10
10
Max Excess Accuracy Gap [max, vol (%)
Max Excess Accuracy Gap mmax, Vol (%)
Figure 11: CIFAR-100 100 classification with both target and protected attribute being the class labels.
33


Reviews:
[{"review_id": "SBnrfujZCB", "reviewer": "Reviewer_cVd6", "summary": "This paper deals with the problem of pruning models with desire of not decreasing performance on subsets via constraints.", "questions": "Can we give some formal results with Equation(6) like the analytical solution or convergenece guarantee?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The technique is solid and the experiments are sound.", "weaknesses": "Can the paper deals with other pruning techniques to demonstrate the effectiveness of constraint to subsets?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uEJt2M5oZm", "reviewer": "Reviewer_Haeo", "summary": "This paper provides a new training protocol to manage pruning induced bias. The main aim is to create algorithms in which the difference in accuracy between any two groups is minimised. The authors highlight that their main focus is lessen the effects of compression and thus they treat dense models as baseline.", "questions": "Please see weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a useful research area. With concerns of AI inclusion and climate change, sparse models are very appealing. The authors provide a method to ameliorate some of the effects of compression by limiting the disparity between group performance.\nThis is a well written paper and the methodology is clear. Implementation and results are well described and the examples in the appendix provide further grounding on their work.", "weaknesses": "It is not clear from the analysis provided that solutions always exist given the constraints. Perhaps the authors could more light on this. Is there a relationship between the starting point and how tight the constraints can be?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BB6Dm9qkz2", "reviewer": "Reviewer_KSs2", "summary": "This work proposes a new approach for fine-tuning sparse models after pruning. The proposed approach involves formulating a constrained problem, where loss function is optimized subject to a group-wise accuracy constraint (that is, the accuracy drop for each group should be bounded by a tolerance $\\varepsilon$). This Lagrangian of this constrained problem is then optimized with standard gradient-based methods. This approach is empirically shown to reliably generate models where the differences in the group-wise impact of sparsity on accuracy is minimized.", "questions": "* Have the authors tried applying this technique to other pruning methods? For instance, how well would this fine-tuning method work if structured pruning was used instead of unstructured pruning? How well would the method work if other unstructured pruning methods were used instead of IMP (i.e. SynFlow [1] or SNIP [2])?\n* Is there a sparsity level at which the method fails to achieve models with the desired worst-case groupwise accuracy loss? Put another way, is there a sparsity level at which the constrained optimization problem described in eq. (5) become infeasible? Can the authors comment on how this might play out in the case of structured pruning?\n* Are there any formal results that can be provided for solving the CEAG (eq (5))? For instance, is Algorithm 1 guaranteed to find a solution provided the feasible set is nonempty?\n* Have the authors considered ways by which the test-case performance can be improved, say by dataset splits?\n* Is the CEAG method affected by dataset imbalance? Suppose certain groups have comparatively fewer samples in the dataset. How, if at all, would this affect the efficacy of the method?\n\n[1] \"Pruning neural networks without any data by iteratively conserving synaptic flow\", Tanaka et al, 2020.\n\n[2] \"SNIP: Single-shot Network Pruning based on Connection Sensitivity\" Lee et al, 2019.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper has several strengths:\n\n* The proposed approach is interesting, novel, and flexible, and reliably reduces group wise disparities in accuracy after pruning.\n* The empirical evaluation is very thorough.\n* Limitations of the proposed methods and ethical considerations are discussed thoroughly as well.\n* In the appendix, variations of the main results are discussed as well.;/\n* The writing and presentation is clear.", "weaknesses": "The paper has a few weaknesses. \n\n* This method is independent of the choice of pruning strategy. However, it would have been nice to see the experiments replicated for other pruning strategies, including structured pruning methods. \n* A more detailed discussion on the feasibility of the constrained problem given in equation (4) would have been useful for readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tH6SfUDtf4", "reviewer": "Reviewer_qBid", "summary": "This paper proposes a method for mitigating disparate effect on model accuracy by formulating the task as a constrained optimization problem and solving it via alternative gradient descent. The introduced approach manages to decrease the gap between average model performance and worst performance on a subgroup of data while preserving the mean accuracy on the target task.", "questions": "How sensitive is the algorithm to the initialization of dual parameters $\\lambda_g$ and the corresponding update rule?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem being addressed is quite novel in sparsification community and is of significant interest to practitioners, especially in safety-critical applications. The approach looks very reasonable and directly optimizes the imposed constraints via solving a min-max problem. The method is quite non-trivial and comprises several interesting ideas - alternating between non-differentiable accuracy constrain term and excess loss term, as well as use of replay buffers for stabilization of optimization. \n\nCEAG outperforms existing alternatives on a couple of benchmarks - UTKFace and CIFAR100. The method doesn’t add significant computation overhead compared to the standard training procedure.", "weaknesses": "While the proposed method manages to keep train accuracy on subgroups within desired tolerance bounds, seems it has hard to achieve on the test data, especially in the setting with many classes and subgroups (for example in the provided CIFAR-100 experiment). \n\nThe difference between $\\mathrm{max}_g \\psi_g $ on the hold-out-data between NFT and CEAG doesn’t seem to be very significant in many cases - 2.0 vs 2.1 on 99% sparsity UTKFace *(Table1)*, 3.3 vs 3.6 for 92.5% *(Table2)*, 13.8 vs 14.3 on CIFAR-100 *(Table3)*. Given the standard deviation of the runs, improvement of CEAG appears to be statistically insignificant. \n\nExperimental validation is not exhaustive enough. To demonstrate the efficiency in a more large scale and practically relevant scenario one could consider more diverse and large-scale dataset, such as ImageNet (or ImageNet-LT version), or one of the iNaturalist versions, considering only large hierarchy groups to make the task computationally tangible. \n\n*Minor*. The pruning strategy called in the paper is customary named **Gradual Magnitude Pruning** (GMP) [2], where after each pruning step one continues training the model from the current state. **Iterative Magnitude Pruning** (IMP) [3] adopted in discovery of Lottery Tickets rewinds the weights to initialization after pruning step. I would suggest calling the method GMP to avoid confusion. \n\n---\n[1] Liu, Ziwei, et al. \"Large-scale long-tailed recognition in an open world.\" Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2019.\n\n[2] Zhu, Michael, and Suyog Gupta. \"To prune, or not to prune: exploring the efficacy of pruning for model compression.\" arXiv preprint arXiv:1710.01878 (2017).\n\n[3] Frankle, Jonathan, and Michael Carbin. \"The lottery ticket hypothesis: Finding sparse, trainable neural networks.\" arXiv preprint arXiv:1803.03635 (2018).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)