{'fraction_non_alphanumeric': 0.035823456856330774, 'fraction_numerical': 0.009089934037646807, 'mean_word_length': 4.955764931331843, 'pattern_counts': {'":': 1, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
FairGBM: Gradient Boosting with Fairness Constraints

Machine Learning (ML) algorithms based on gradient boosted decision trees (GBDT) are still favored on many tabular data tasks across various mission critical applications, from healthcare to finance. However, GBDT algorithms are not free of the risk of bias and discriminatory decision-making. Despite GBDT's popularity and the rapid pace of research in fair ML, existing in-processing fair ML methods are either inapplicable to GBDT, incur in significant train time overhead, or are inadequate for problems with high class imbalance. We present FairGBM, a learning framework for training GBDT under fairness constraints with little to no impact on predictive performance when compared to unconstrained LightGBM. Since common fairness metrics are non-differentiable, we employ a"proxy-Lagrangian"formulation using smooth convex error rate proxies to enable gradient-based optimization. Additionally, our open-source implementation shows an order of magnitude speedup in training time when compared with related work, a pivotal aspect to foster the widespread adoption of FairGBM by real-world practitioners.


Introduction
The use of Machine Learning (ML) algorithms to inform consequential decision-making has become ubiquitous in a multitude of high-stakes mission critical applications, from financial services to criminal justice or healthcare [1,2,3]. At the same time, this widespread adoption of ML was followed by reports surfacing the risk of bias and discriminatory decision-making affecting people based on ethnicity, gender, age, and other sensitive attributes [4,5,6]. This awareness led to the rise of fair ML, a research area focused on discussing, measuring and mitigating the risk of bias and unfairness in ML systems. Despite the rapid pace of research in fair ML [7,8,9,10,11] and the release of several open-source software packages [12,13,9,14], there is still no clear winner method that "just works" regardless of data format and bias conditions. Fair ML methods are usually divided into three families: pre-processing, in-processing and postprocessing. Pre-processing methods aim to learn an unbiased representation of the training data but may not guarantee fairness in the end classifier [15,16]; while post-processing methods inevitably require test-time access to sensitive attributes and may not always generalize [7,17]. Most inprocessing fair ML methods rely on fairness constraints to impede the model from disproportionately hurting protected groups [8,9,14]. Using constrained optimization, they optimize for the predictive performance of fair models. In principle, in-processing methods have the potential to introduce fairness with no training-time overhead and a minimal predictive performance cost -an ideal outcome for most mission critical applications, such as financial fraud detection or medical diagnosis. Sacrificing a few percentage points of predictive performance in a mission critical application may result in catastrophic outcomes, from safety hazards to substantial monetary losses. Therefore, the use of fair ML in mission critical systems is particularly challenging, as fairness must be achieved with minimal sacrifice of predictive performance.
Tabular data is a common data format in many mission critical applications of ML (e.g., financial services). While deep learning is the dominant paradigm for unstructured data, gradient boosted decision trees (GBDT) algorithms are pervasive in tabular data due to state-of-the art performance and the availability of fast, scalable, and ready-to-use implementations (e.g., LightGBM [18], XG-Boost [19]). Unfortunately, fair ML research still lacks suitable fairness-constrained frameworks for GBDT, making it challenging to satisfy stringent fairness requirements.
As a case in point, Google's TensorFlow Constrained Optimization (TFCO) [14], a well-known in-processing bias mitigation technique, is only compatible with neural network models. Conversely, Microsoft's ready-to-use Fairlearn EG framework [9] supports GBDT models, but its substantial training overhead and the employed score binarization make this framework impractical. Particularly, the production of binary scores is incompatible with deployment settings with a fixed budget for positive predictions (e.g., resource constraint problems [20,21]) or settings targeting a specific point in the ROC curve (e.g., fixed false positive rate), such as in fraud detection.
To address this gap in fair ML, we present FairGBM, a framework for fairness constrained optimization tailored for GBDT. Our method incorporates the classical method of Lagrange multipliers within gradient-boosting, requiring only the gradient of the constraint w.r.t. the model's outputŶ . Lagrange duality enables us to perform this optimization process efficiently as a two-player game: one player minimizes the loss w.r.t.Ŷ , while the other player maximizes the loss w.r.t. the Lagrange multipliers. As fairness metrics are non-differentiable, we employ differentiable proxy constraints. Our method is inspired by the theoretical ground-work of Cotter et al. [14], which introduce a new "proxy-Lagrangian" formulation, and prove that a stochastic equilibrium solution does exist even when employing proxy constraints. Contrary to related work, our approach does not require training extra models, nor keeping the training iterates in memory.
We apply our method to a large-scale account opening fraud case study, as well as to the benchmark ACSIncome-Adult dataset [22]. Moreover, we enable fairness constraint fulfillment at a specific ROC point, finding fair models that fulfill business restrictions on the number of allowed false positives. Figure 1 shows FairGBM's ability to achieve high fairness at a negligible cost to predictive performance when compared with unconstrained LightGBM. When compared with state-of-the-art inprocessing fairness interventions, our method consistently achieves improved predictive performance for the same value of fairness.
In summary, this work's main contributions are: • A novel constrained optimization framework for gradient-boosting, dubbed FairGBM.
• A high-performance implementation of LightGBM [18] with fairness constraints, based on differentiable proxies of well-known fairness metrics.
• Validation of our method on a real-world case-study, as well as on a public benchmark dataset, showing a dramatic fairness increase at little to no predictive performance cost.

Related Work
Prior work on algorithmic fairness can be broadly divided into three categories: pre-processing, in-processing, and post-processing; depending on whether it acts on the training data, the training process, or the model's predictions, respectively.
Pre-processing methods aim to modify the input data such that any model trained on it would no longer exhibit biases. This is typically achieved either by (1) creating a new representation U of the features X that does not exhibit correlations with the protected attribute S [15,16], or (2) by altering the label distribution Y according to some heuristic [23,24] (e.g., equalizing prevalence across sub-groups of the population). Although compatible with any downstream task, by acting on the beginning of the ML pipeline these methods may not be able to guarantee fairness on the end model. Moreover, recent empirical comparisons have shown that pre-processing methods often lag behind in-processing and post-processing methods [22].
In-processing methods alter the learning process itself in order to train models that make fairer predictions. There are a wide variety of approaches under this class of methods: training under fairness constraints [8,9,14], using a loss function that penalizes unfairness [23,25,26], or training with an adversary that tries to predict protected-group membership [27]. The main shortcoming of in-processing methods lies in their selective compatibility with particular algorithms or families of algorithms. As a case in point, there is currently no constrained optimization method tailored for the GBDT algorithm, besides the one present in this work. However, the state-of-the-art results for numerous tabular data tasks are currently held by boosting-based models [28].
Post-processing methods alter the model's predictions to fulfill some statistical measure of fairness. In practice, this is done by (1) shifting the decision boundary for specific sub-groups [7,23], or by (2) randomly classifying a portion of individuals of the underprivileged group [29,30]. Methods based on shifting the decision-boundary have the clear advantage of achieving 100% fairness in the data where they are calibrated (training or validation data), while also being compatible with any score-based classifier. However, post-processing methods can be highly sub-optimal [17], as they act on the model after it was learned. Moreover, they can lead to higher performance degradation when compared to in-processing methods [22].

Constrained Optimization
Constrained optimization (CO) approaches aim to find the set of parameters θ ∈ Θ that minimize the standard predictive loss L of a model f θ given a set of m fairness constraints c i , i ∈ {1, ..., m}: This problem is often re-formulated using the Lagrangian function, where λ ∈ R m + is the vector of Lagrange multipliers. The problem stated in Equation 1 is then, under reasonable conditions, equivalent to: which can be viewed as a zero-sum two-player game, where one player (the model player) minimizes the Lagrangian w.r.t. the model parameters θ, while the other player (the constraint player) maximizes it w.r.t. the Lagrange multipliers λ [32]. A pure equilibrium to this game will not exist in general for a given CO problem. Sufficient conditions for there to be one are, for example, that the original problem is a convex optimization problem satisfying an appropriate constraint qualification condition [33]. Consequently, two main issues arise when using classic CO methods with fairness metrics: the loss functions of state-of-the-art ML algorithms are non-convex (as is the case of neural networks), and standard fairness metrics are non-convex and non-differentiable.
Agarwal et al. [9] put forth a solution dubbed exponentiated gradient reduction for fair classification (EG) based on finding instead a mixed Nash equilibrium. The θ-player plays a mixed strategy found by minimizing the expected Lagrangian over a distribution over the model parameters. This is achieved by solving a sequence of cost-sensitive learning tasks, each yielding a single model θ i corresponding to a particular best response for a fixed choice of the Lagrange multipliers. The final result of this process is a randomized classifier corresponding to the mixture distribution that is the average of all the iterates, Q(θ) = 1 N N i δ(θ − θ i ). They also consider a deterministic solution obtained by performing a simple grid-search over the Lagrange multipliers. While this does not enjoy the same theoretical guarantees, and is impractical when there are many constraints, they have found it to be comparable to the stochastic solution in their experiments.
These methods are implemented in the well-known fairlearn open-source package 2 . Although easyto-use and widely applicable (including compatibility with GBDT), the fact that a new classifier is trained from scratch at each iteration until convergence leads to severely slower training when compared to solving the analogous unconstrained problem. Moreover, all classifiers (default n = 50) must be kept in memory in order to make predictions. Furthermore, in practice, when relying on a typical ML algorithm to solve the required cost-sensitive classification problem we would not be minimizing our desired Lagrangian (that would be hard in the non-convex setting) but instead a differentiable surrogate obtained by replacing 0-1 step functions with appropriate convex surrogates (e.g., replacing a cost-weighted error rate with cost-weighted binary cross-entropy).
Cotter et al. [14] thus propose finding a weaker type of equilibrium for a two-player non-zero sum game, obtained by using two different Lagrangians that they call "proxy-Lagrangians": • the original Lagrangian (using the original constraints), that is maximized by the λ-player; this is already linear in λ and thus its gradient is ∂L(θ,λ) • a proxy LagrangianL, that is minimized by the θ-player, and is obtained by replacing the constraints with continuous sub-differentiable upper bounds; this allows for the use of (sub-)gradient based optimization methods.

Name
Proxy metric,l Proxy derivative, ∂l ∂f (x)
Cotter et al. [14] show that their proposed type of equilibrium still corresponds to an approximately optimal and feasible solution to the desired constrained optimization problem and with tighter bounds than using the same surrogate Lagrangian for both players. Furthermore, they propose a practical algorithm to find this equilibrium in the setting that the objective function is convex (but importantly no such requirement is needed for the constraints, c i ). Their algorithm has the constraint player minimizing swap regret and the model player minimizing external regret via gradient descent updates. As with fairlearn [9], the θ-player will play a mixed strategy but with the marked advantage that the randomized classifier is built out of the iterates of a gradient descent algorithm instead of a mixture of models where each needs to be trained from scratch. This method is implemented in TensorFlow (TF) 3 , dubbed TFCO.
All in all, there is still a limited selection of CO methods compatible with gradient-boosting, and none tailored for this specific algorithm. One of the main advantages of LightGBM [18] is the substantially reduced training time, which may be entirely undone by the use of randomized classifiers. Indeed, these stochastic solutions may require training a large number of strong models and keeping them in memory at all times, reducing their prospects for real-world applicability.

Gradient Boosted Decision Trees
A gradient boosting algorithm estimates a mapping f : X → y that minimizes a loss function, where f is constrained to be a sum of base (weak) learners h t ∈ H. In the case of GBDT, these can be shallow decision trees with fixed depth or fixed number of nodes: where η t is a step size parameter. Typically, h 0 would be a constant function that minimizes L and η 0 = 1. Gradient boosting can then be understood as performing gradient descent on the space of functions f . Each subsequent step, h t , being essentially a projection onto H of the negative gradient of the loss L w.r.t. f . In other words, the base learner whose predictions are as close as possible, in the l 2 sense, to the negative gradient 4 : where g t,i are the gradients evaluated at the current iterate f t−1 = t−1 m=0 η m h m : Note that Equation 6 is equivalent to: XGBoost [19] and LightGBM [18] replace the approximation above with a local quadratic one thus implementing the following second order step: where H i,t is the hessian of l w.r.t. f computed at the current iterate and Ω is a regularization term penalizing complex base learners.

Fairness Constraints
As a fundamentally subjective concept, there is no "one-size-fits-all" definition of fairness. Nonetheless, popular fairness notions can be defined as equalizing rate metrics across sensitive attributes [12]. For example, equality of opportunity [7] is defined as equalizing recall 5 , when measured over members of specific protected groups (e.g., different genders or ethnicities).
In the general case, a model f is deemed fair w.r.t. the sensitive attribute S and some rate metric L if the expected value of L is independent of the value of s ∈ S: Equation 10 can be naturally viewed as an equality constraint in the model's training process after replacing expectations under the data distribution by their sample averages. However, as discussed in Section 3.1, common fairness notions (i.e., common choices of L) are non-convex and nondifferentiable. Therefore, in order to find a solution to this CO problem, we must use some proxy metricL that is indeed differentiable (or at least sub-differentiable) [14]. Figure 2 shows examples of convex and sub-differentiable surrogates for the False Positive Rate (FPR). Equalizing FPR among sensitive attributes is also known as predictive equality [34]. As any function of the confusion matrix, the FPR takes in predictions binarized using a step-wise function. As no useful gradient signal can be extracted from the step-wise function, we instead use a crossentropy-based proxy metric that upper-bounds the step-wise function. Ideally, for some fairness constraint c, we can guarantee its fulfillment by solving the CO problem using a proxy upper-bound c, such that c(θ) ≤c(θ) ≤ 0. Note that, while Cotter et al. [14] use a hinge-based proxy, which has a discontinuous derivative, we opt for a cross-entropy-based proxy, which has a continuous derivative. Moreover, there is a nice parallel between our proposed cross-entropy-based proxy and the widely popular cross-entropy loss 6 . Table 1 shows instance-wise rate metrics commonly used to compose fairness metrics and the proposed proxy counterparts.
In practice, the fairness constraint in Equation 10 is implemented using the set of m = |S| inequalities in Equation 11: where ∈ R is the allowed constraint violation, and is the proxy loss measured over the samples that belong to group s. 5 Or equivalently equalizing false negative rate. 6 Note that, in order for the proxy metric to upper-bound the step-wise function, the model's scores must be shifted by adding a constant c = log(e − 1), as the standard cross-entropy crosses the y-axis at log(2) ≤ 1.

Fairness-Aware GBDT
If our objective function and constraints were convex, we could find the pure Nash equilibrium of the zero sum, two-player game corresponding to the saddle point of the proxy-Lagrangian: where L is a predictive loss function, andc i are the proxy inequality constraints given by Equation 11. This equilibrium could be found by gradient descent over our model function, f , and ascent over the Lagrange multipliers, λ. Importantly, this setting is relevant for GBDT models but not for Neural Networks, as the first have a convex (proxy) objective and the latter do not. However, when using fairness constraints, we would still only be enforcing our proxy-constraints and not necessarily the original ones.
Thus, following Cotter et al. [14] we adopt a non-zero sum two-player game formulation where the descent step for the model player uses the proxy-Lagrangian and the ascent step for the λ-player the Lagrangian with the original constraints. According to the authors this should converge to a coarse-correlated equilibrium that despite not having the same guarantees as their solution where the λ-player maximizes swap-regret (see section 3.1), is simpler and was found to perform well in practice. This solution corresponds to a mixed strategy for the model player, defined as a distribution over all f t iterates, t ∈ [1, T ]. That is, for each input x, we first randomly sample t ∈ [1, T ], and then use f t to make the prediction for x, where f t = t m=0 η m h m . In practice, using solely the last iterate f T will result in a deterministic classifier that often achieves similar metrics as the randomized classifier [10], although it does not benefit from the same theoretical guarantees. There are also several methods in the literature for reducing a randomized classifier to an approximate deterministic one [36].
In the general case, using this randomized classifier implies training T separate models (as performed by the EG method [9]), severely increasing training time. When using an iterative training process (such as gradient descent), it only implies training a single model, but maintaining all T iterates (as performed by the TFCO method [14]), severely increasing memory consumption. Crucially, when using gradient boosting, each iterate contains all previous iterates. Therefore, a GBDT randomized classifier can be fully defined by maintaining solely the last iterate, carrying no extra memory consumption nor significant extra training time when compared with the vanilla GBDT classifier.
To summarize, FairGBM is the result of employing the proxy Lagrangian CO method with crossentropy-based proxies of fairness constraints, resulting in a randomized classifier with known optimality and feasibility bounds 7 . The gradients of the proxy-Lagrangian are derived in Appendix B.

Experiments
We implemented FairGBM 1 as a fork from the open-source Microsoft LightGBM implementation 8 . The LightGBM algorithm [18] is a widely popular high performance GBDT implementation in C++, with a high-level Python interface for ease-of-use. This algorithm in particular builds on top of the standard GBDT framework by introducing gradient-based one-side sampling (GOSS) and exclusive feature bundling, both aimed at decreasing training and inference time. Although the FairGBM framework (Algorithm 1) could be applied to any gradient boosting algorithm, we choose to implement it on top of LightGBM due to its excellent scalability.
We initially validate our method on a public benchmark dataset from the fairness literature, the ACSIncome-Adult dataset [22], and afterwards move on to applying our method in a real-world account opening fraud application (our target use case). The first scenario aims to be an easily reproducible comparison under common literature objectives and constraints: maximizing accuracy under an equal opportunity constraint over different genders. On the other hand, the second scenario poses a distinct set of challenges that are seldom discussed in the fairness literature, from highly imbalanced data to tight budget constraints on the number of positive predictions. The following sub-sections describe experiments on each setting in detail.

ACSIncome-Adult Dataset
The ACSIncome-Adult dataset [22] is a recently introduced 1.6M rows dataset based on the American Community Survey (ACS) public use microdata sample from 2018. It consists of high-quality data made available to the public by the US Census Bureau. It is essentially a modern-day version of the popular 1994 UCI-Adult dataset [37] (50K rows), which has been widely used in ML research papers over the years.
The objective is to predict whether US working adults' yearly income is above $50K. Each row contains a set of demographic features, such as age, marital status, education, occupation, working hours, place of birth, race, and gender. The objective is to maximize global accuracy, while equalizing group false negative rate (FNR), also known as equality of opportunity [7], over different binary gender groups.
We compare FairGBM with a set of constrained optimization baselines from the fair ML literature. Fairlearn EG [9] is a state-of-the-art method based on the reduction of CO to a cost-sensitive learning problem (discussed in Section 3.1). It produces a randomized binary classifier, composed of several base classifiers. Fairlearn GS [9] is a similar method that instead uses a grid search over the constraint multipliers λ, and outputs a single (deterministic) classifier that achieves the best fairness-performance trade-off. RS Reweighing is a variation of GS that instead casts the choice of multipliers λ as another model hyperparameter, which will be selected via Random Search (RS   Table 3. increase exploration and variability of the attainable trade-offs. Both EG and GS are implemented in the popular open-source Fairlearn package 2 . All models are trained with an equal opportunity constraint (Equation 10), using LightGBM as the base algorithm. Finally, we also show results for the standard unconstrained LightGBM algorithm.
It is well-known that the choice of hyperparameters affects both performance and fairness of trained models [38]. To control for the variability of results when selecting different hyperparameters, we randomly sample 100 hyperparameter configurations of each algorithm. Furthermore, we follow the reproducibility check-list put forth by Dodge et al. [39] (further details in Appendix A). In the case of EG and GS, both algorithms already fit n base estimators as part of a single training procedure. Hence, we run 10 trials of EG and GS, each with a budget of 10 iterations, for a total budget of 100 models trained. As such, all algorithms have an equal training budget of 100 hyperparameter configurations in total.
Finally, the dataset is split 60%/20%/20% in train/validation/test data, with random sampling stratified by US state. This follows the directions given by the dataset's datasheet [40]. All models are trained on the training data, and evaluated on both validation and test data. Model selection (after random search) is based on validation results, while test results are withheld and strictly ignored for any decision-making. Figure 3a shows a scatter plot of the fairness-accuracy results in the validation set for trained models on the ACSIncome-Adult dataset, as well as the performance and fairness distribution for each algorithm. Note that the xx axis spans a small accuracy range, as all models consistently achieve high performance on this task. Moreover, the standard fairness-blind LightGBM algorithm already achieves above 0.7 equal opportunity on this task, while naturally achieving the highest performance among all algorithms. These results further motivate our focus on a real-world setting, as it poses a much more challenging environment (compare Figures 3a and 3b). Tables 2 and 3 show results for different fairness-performance trade-offs. Among all CO algorithms, which were trained with a constraint to achieve 1.0 fairness (Equation 10), FairGBM has the lowest average constraint violation. The EG algorithm follows, also achieving high performance and high fairness, although clearly behind FairGBM in the latter. At the same time, the GS and RS Reweighing algorithms achieve a surprisingly low fairness, signalling that their randomized counterpart (the EG  Due to only providing binary (0/1) model outputs instead of real-valued scores, EG cannot be used in the AOF case-study (score threshold at 5% FPR). Note the different xx axis ranges (AOF has a wider performance spread).

Results
algorithm) seems better fitted for this setting. Importantly, the total time taken to train all FairGBM models is under a tenth of the time taken to train all EG models.
Regarding standard unconstrained LightGBM, it consistently achieves very high performance for all trained models, while FairGBM has a wider spread on the performance metric. However, as expected, fairness for the LightGBM algorithm is considerably lower. Notably, the best-performing FairGBM algorithm achieves only 0.002 lower accuracy than LightGBM, while increasing fairness by 0.287 (test results).

Real-world Account Opening Fraud Dataset
Finally, we want to employ FairGBM to a real-world fraud detection case-study. Each real-world environment has a set of requirements, constraints, and goals, which vary wildly depending on the context. Nonetheless, the requirements we discuss in this section (e.g., alert rate, scalability) are arguably commonplace in production ML systems, and could be generalized to a wide variety of settings.
Our case is of a fintech company that leverages ML solutions to prevent financial fraud. Specifically, our goal is to deploy a model to detect fraudulent bank account opening requests for a large European bank. These requests are made via an online application form. Fraudsters will attempt to open a new bank account using a synthetic identity, or to impersonate a real person using stolen credentials (or a mixture of both). The end objective of the fraudster is to quickly max out the account's line of credit, leading to losses incurred by the bank 9 .
The account opening fraud (AOF) dataset spans a 6-month data stream with over 500K instances. Data is split using 4 months for training, 1 month for validation, and 1 month for test, such that we train on the oldest data and test on the most recent. This temporal aspect plays an important role in model deployment, as oftentimes we witness considerable concept drift throughout the year (a model trained on 1-year-old data will perform poorly on recent data). Moreover, as fraudsters are in the minority relative to legitimate individuals, our data is highly imbalanced, with only 1% fraud prevalence. 9 Losses in account opening fraud are incurred by the bank, not the person whose identity was stolen.

Evaluation Setup
Fraud detection is a punitive ML setting: a positive prediction leads to a negative outcome for the individual (application denied). For an ML system to be deemed fair, the likelihood of a legitimate individual to be wrongly denied access to her/his bank account (a false positive) should be independent of them belonging to a specific protected group. This is defined as equal group-wise FPR, also known as predictive equality [34]. In our setting, we target FPR parity among individuals of different age-groups (preventing ageism).
Moreover, we have a strict business requirement of operating the model at a specific false-positive rate (FPR): 5% FPR. This entails a budget on the number of false positives we can commit. Requirements on the ROC operating point are commonplace in real-world settings, and the 5% FPR requirement is typical within the fraud prevention industry, striking a balance between customer attrition and loss prevention. As a case in point, we could trivially achieve 99% accuracy by predicting all inputs as negative, or 100% recall by predicting all inputs as positive. Hence, the performance metric to maximize is fraud recall at 5% FPR.
Note that the EG algorithm is not compatible with this real-world setting, as it outputs a binary randomized classifier, providing no confidence score for its predictions. Effectively, an arbitrary decision threshold of 0.50 is implicitly used. The only way to use this method at a specific ROC point would be to randomly classify a portion of the samples to meet the maximum number of positive/negative predictions. As this would not make for a fair comparison, we omit this method for the AOF dataset. Finally, the EG method also requires keeping tens of models in memory (the package default is n = 50), straining the scalability of the production environment.
Similarly to the ACSIncome-Adult task, we give each algorithm an equal budget of 100 trials.

Operating FairGBM at a specific ROC point
Without fairness constraints, meeting a specific ROC operating point can be achieved by appropriately thresholding the output of a classifier that learns to approximate the class probabilities: p(y = 1|x) [41]. That is the case of a classifier that is trained to minimize a proper scoring rule such as binary cross-entropy.
However, when optimizing for the Lagrangian (Equation 13), we are no longer optimizing for a classifier that approximates the true class probabilities. This is a key point that is often overlooked in the constrained optimization literature. Namely, both L andL have an implicit threshold when evaluating constraint fulfillment: the 0.5 decision threshold, or 0.0 when considering the log-odds (see Figure 2). In practice, FairGBM will be optimized to fulfill the constraints at this pre-defined threshold, but constraint fulfillment may not (and likely will not) generalize to all thresholds. Indeed, we could use any decision threshold during training, but it is impossible to know which threshold would meet our ROC requirements beforehand.
We propose to solve this by introducing our ROC requirement as another in-training constraint. In the AOF setting, this is achieved by introducing an additional constraint of global F P R ≤ 0.05. In practice, instead of shifting the threshold to meet our target ROC operating point, we are shifting the score distribution such that the 0.5 decision threshold corresponds to our target ROC point, enabling constraint fulfillment at any attainable ROC point. Figure 3b shows a scatter plot of all trained models on the AOF dataset, together with metric distributions for each algorithm on the margin. Note that, while most models achieve high performance on the ACSIncome-Adult dataset, on AOF we see a significantly wider range of performance values (compare xx axis scale between the two plots). Moreover, the unconstrained LightGBM algorithm in this setting shows significative average unfairness.

Results
Although FairGBM achieves a wider spread over both metrics, it significantly extends the Pareto frontier of attainable trade-offs. As mentioned for the ACSIncome-Adult dataset, Tables 2 and 3 show results for different model selection fairness-performance trade-offs. Arguably, FairGBM consistently achieves excellent trade-offs. Indeed, FairGBM dominates LightGBM on both fairness and performance for the α = 0.5 and α = 0.75 trade-offs, while achieving +0.519 fairness and only −0.011 performance on the α = 0.95 trade-off (AOF test results). Moreover, FairGBM strictly dominates RS on all studied trade-offs, while only slightly lagging behind GS on the fairness metric. Although the GS method consistently achieves very high fairness (note the green yy axis distribution), it does so at a dramatic performance cost.  Figure 4 shows a comparison between using the randomized classifier predictions or solely the last iterate predictions on the ACSIncome-Adult dataset. As mentioned in Section 3, the first approach benefits from theoretical convergence guarantees, while the latter benefits from being a deterministic classifier (which may be a requirement in some real-world settings). In practice, using the last iterate version of FairGBM (which always uses all trees of the GBM ensemble) achieves similar results to the randomized classifier version (which randomly picks the number of trees it will use for each prediction). The same trend is clear on the AOF dataset, and concurs with related work on randomized classifiers by Cotter et al. [14].

Conclusion
The last decade of breakthroughs in ML has led to a ubiquitous use of automated decision-making in high-stakes domains. Nowadays, GBDT algorithms are commonplace for tabular data tasks such as financial fraud detection.
In this work, we present a constrained optimization (CO) framework for the GBDT algorithm, dubbed FairGBM. Our method uses a non-zero sum two player game formulation with differentiable proxies of popular fairness rate metrics. The result is a randomized classifier that provably converges to an approximately optimal solution. Moreover, FairGBM does not require significant extra computational resources, while related CO algorithms considerably increase training time (EG, GS) or memory consumption (TFCO).
We evaluate our method on a literature benchmark dataset, as well as on a real-world account opening fraud case-study. Results on both datasets show FairGBM dominates LightGBM for a wide range of fairness-performance trade-offs, or otherwise significantly increases fairness at a tiny performance drop (e.g., +0.519 fairness, −0.011 performance, for α = 0.95 on the AOF test results). Moreover, FairGBM consistently achieves very high fairness fulfillment (above 0.9) for any trade-off choice. When compared with general-purpose constrained optimization methods, our tailored approach is more consistent across datasets, and achieves higher fairness for the same level of performance. Crucially, FairGBM models effectively extend the Pareto frontier on both datasets, occupying a previously empty region of the fairness-performance trade-off.
Finally, we enable fairness constraint fulfillment at a specified ROC point (e.g., with a fixed budget for false positives), which is a common requirement in deployed ML models. We hope the public release of FairGBM will foster adoption of fairness-aware methods in high-stakes tabular data tasks.

C Notation
L the Lagrangian function, which uses the original constraints c; see Equation 2. L the proxy-Lagrangian function, which uses the proxy constraintsc; see Equation 13. c an inequality constraint function; it is deemed fulfilled if c(θ) ≤ 0; this function may be non-differentiable; examples include a constraint on TPR parity or parity of any other metric of the confusion matrix. c a proxy inequality constraint that serves as sub-differentiable proxy for the corresponding constraint c; see Equation 11. l an instance-wise loss function, i.e., l : Y ×Ŷ → R + , where Y is the set of possible labels andŶ is the set of possible predictions; see green line in Figure 2. l a sub-differentiable proxy for an instance-wise loss function; see blue and purple lines in  Table 3: Results on the fair ML benchmark dataset (top rows) and on the real-world case-study (bottom rows). For each algorithm, we select the top model based on the weighted sum [α · performance + (1 − α) · fairness] measured in validation and report results on both validation and test data. Total run-times are shown in absolute terms (in hours) and in relative terms (compared to LightGBM).