Enhancing Group Fairness in Online Settings Using Oblique Decision Forests
Authors: Somnath Basu Roy Chowdhury
Nicholas Monath
Ahmad Beirami
Rahul Kidambi
Kumar Avinava Dubey
Amr Ahmed
Snigdha Chaturvedi
Venue: ICLR 2024 spotlight (2024)
Keywords: Fairness
Online Learning
Oblique Decision Trees
Primary area: societal considerations including fairness, safety, privacy
TL;DR: We present an fairness algorithm, Aranyani, to achieve group fairness when data instances arrive one at a time in an online setting.

Abstract: Fairness, especially group fairness, is an important consideration in the context of machine learning systems. The most commonly adopted group fairness-enhancing techniques are in-processing methods that rely on a mixture of a fairness objective (e.g., demographic parity) and a task-specific objective (e.g., cross-entropy) during the training process. However, when data arrives in an online fashion – one instance at a time – optimizing such fairness objectives poses several challenges. In particular, group fairness objectives are defined using expectations of predictions across different demographic groups. In the online setting, where the algorithm has access to a single instance at a time, estimating the group fairness objective requires additional storage and significantly more computation (e.g., forward/backward passes) than the task-specific objective at every time step. In this paper, we propose Aranyani, an ensemble of oblique decision trees, to make fair decisions in online settings. The hierarchical tree structure of Aranyani enables parameter isolation and allows us to efficiently compute the fairness gradients using aggregate statistics of previous decisions, eliminating the need for additional storage and forward/backward passes. We also present an efficient framework to train Aranyani and theoretically analyze several of its properties. We conduct empirical evaluations on 5 publicly available benchmarks (including vision and language datasets) to show that Aranyani achieves a better accuracy-fairness trade-off compared to baseline approaches.

Published as a conference paper at ICLR 2024
ENHANCING GROUP FAIRNESS IN ONLINE SETTINGS USING OBLIQUE DECISION FORESTS
Somnath Basu Roy Chowdhury",, *11, Nicholas Monath², Ahmad Beirami', Rahul Kidambi", Avinava Dubey?, Amr Ahmed Snigdha Chaturvedi'
UNC Chapel Hill, Google DeepMind, "Google Research.
(somnath, snigdha/ecs unc.edu
{nmonath, beirami, rahulkidambi, avinavadubey, amra amra)@google.com
ABSTRACT
Fairness, especially group fairnsss, is an important consideration in the context of machine learning systems. The most commonly adopted group faimess-enhancing techniques are in-processing methods that rely on a mixture of a fairness objec- tive (e.g., demographic parity) and a task-specific objective (e.g., cross-entropy) during the training process. However, when data arrives in an online fashion one instance at time- optimizing such faimess objectives poses several chal- lenges. In particular, group fairness objectives are defined using expectations of predictions across different demographic groups. In the online setting, where the algorithm has access to a single instance at a time, estimating the group faimess objective requires additional storage and significantly more computation (c.g., for- ward/backward passes) than the task task-specific objective at every time step. In this paper, we propose Aranyani, an ensemble of oblique decision trees, make fair decisions in online settings. The hierarchical tree structure of Aranyani enables parameter isolation and allows to efficiently compute the fairness gradients us- ing aggregate statistics of previous decisions, eliminating the need for additional storage and forward/backward passes. We also present an efficient framework train Aranyani and theoretically analyze several of its properties. We conduct em- pirical evaluations on publicly available benchmarks (including vision and lan- guage datasets) to show that Aranyani achieves a better secracy-fairness trade-off compared to baseline approaches.
INTRODUCTION
Critical applications of machine learning, such as hiring (Dastin, 2022) and criminal recidivism (Larson et al., 2016), require special attention to avoid perpetaating biases present in training data (Corhett-Davies et al., 2017; Buolamwini & Gebru, 2018; Raji & Buolamwini, 2019). Group fairness, which is a well-studied paradigm for mitigating such biases in machine learning (Mchrabi et al., 2021; Hort et al., 2023), tries to achieve statistical parity of system's predictions among dif- ferent demographic (or protected) groups (e.g., gender or race). In general, group fairness-enhancing techniques can be broadly categorized into three categories: pre-processing (Zemel et al., 2013; Cal- mon et al., 2017), post-processing (Hardt et al., 2016; Pleiss et al., 2017: Alghamdi et al., 2022), and in-processing (Quadrianto & Sharmanska, 2017: Agarwal et al., 2018; Lowy et al., 2022; Baharlouei et al., 2024) techniques. Most of these approaches rely on group fairness objectives that are opti- mized alongside spec-fp objectives in an offline setting (Dwork et al., 2012). Group fairness objectives (c.g., demographic parity) are defined using expectations of predictions across different demographic groups, requiring access to labeled data from different groups. However, in many mod- emn applications (e.g., output moderation using toxicity classifiers for chatbots, social media content, etc.), data arrives in an online fashion. In such cases, the definition of safety evolving, and new unsafe data points are identified on the fly, making them prime candidates for online learning.
In the online setting, optimizing for group fairness poses several unique challenges. Central to this paper, in processss techniques require additional storage or computation since the system only has
Work done during an internship Google Research.

---

Published as a conference paper at ICLR 2024
access single input instance at any given time. In online settings, naively training the model using group fairness loss involves storing all (or at least a subset of) the input instances seen so far, and performing forward/backward passes through the model using these instances at each step of online learning, which can be computationally expensive. We also note that other techniques such as pre- processing techniques are clearly impractical they require prior access to data. Post-processing techniques typically assume black-box access to trained model and a held-out validation set (Hardt et al., 2016), which can be impractical or expensive to acquire during online learning.
In this paper, we present a novel framework Aranyani, which consists of an ensemble of oblique de- cision trees. Aranyani uses the structural properties of the tree to enhance group faimesss in decisions made during online learning. The final prediction in oblique trees is a combination of local deci- sions at individual tree nodes. We show that imposing group fairness constraints on local node-level decisions results in parameter isolation, which empirically leads to better and fairer solutions. In the online setting, we show that maintaining the aggregate statistics of the local node-level decisions allows us to efficiently estimate group fairness gradients, eliminating the need for additional storage or borward/backwa ward passes. We present an efficient framework to train Aranyani using state-of- the-art autograd libraries and modern accelerators. We also theoretically study several properties of Aranyani including the convergence of gradient estimates. Empirically, we observe that Aranyani achieves the best accuracy-fairmen trade-off on 5 different online learning setups.
Our paper is organized as follows: (a) We hegin by introducing the fundamentals of oblique deci- sion trees and provide the details of oblique decision forests used in Aranyani (Section 2), (b) We describe the problem setup and discuss how to enforce group faimess in the simpler offline setting (Section 3.1 & 3.2), (c) We describe the functioning of Aranyani in the online setting (Section 3.3), (d) We describe an efficient training procedure for oblique decision forests that enables gradient computation using back- pooo-propagttion (Section 3.4), (e) We theoretically analyze several properties of Aranyani (Section 4), and (f) We describe the experimental setup and results of Aranyani and other baseline approaches on several datasets (Section 5). We observe that Aranyani achieves the best accuracy-fairnes tradeoff, and provides significant time and memory complexity gains com- pared to naively storing input instances to compute the group fairness loss.
OBLIQUE DECISION TREES
We introduce proposed framework, Aranyani, ensemble of oblique decision trees, for achiev- ing group fairness in an online setting. In this section, we introduce the fundamentals of oblique decision trees and discuss the details of the prediction function used in Aranyani. Similar to con- ventional decision tree, an oblique decision tree splits the input space to make predictions by routing samples through different paths along the tree. However, unlike a decision tree, which only makes axis-aligned splits, an oblique decision tree can make arbitrary oblique splits by using routing func- tions that consider all input features. The routing functions in oblique decision tree nodes can be parameterized using neural networks (Murthy et al., 1994; Jordan & Jacobs, 1994). This allows it to potentially fit arbitrary boundary structures more effectively. We formally describe the details of the oblique decision tree structure below:
Definition 1 (Oblique binary decision tree (Karthikeyan al., 2022)). An oblique tree of height h represents a function fxx W. B.B. O) Rd + RR parameterized by Waz E Rd, b.j E R at (i. node (j-th node at depth i). Each node computes (x)(x) = w bij > 0, which decides whether must traverse the left or right child. After traversing the tree, input x arrives at the 1-th leaf that outputs 0 E Re (c >> 1 for classification and c = for regression).
The oblique tree parameters (W, B, ②) can be learned using gradient descent (Karthikeyan et al., 2022). However, the hard routing in oblique decision trees (x is routed either to the left or right child) makes the learning process non-trivial. In our work, we consider modified soft version of oblique trees where an input x is routed to both left and right child at every tree node with certain probabilities based on the node output, (x).
Definition 2 (Soft-Routed Oblique binary decision tree). Using the same parameterization in Def- inition 1, soft-routed oblique trees route x to both children at each node with a certain probability. At (i, -th node, the probability that x is routed to the left node p(x)) neg(x) and the right node is pl 2) = 1 (xy( where niz(x) g( g(wTxx+ + bij) and g(x) E 10, 1] is an activation function. The outpul f fxx Exp((x where p((x) is the probability with which reaches the 1-th leaf.
2

---

Published as a conference paper at ICLR 2024
f(0
Ro0.01
- k(000)
R(i) = 8(W + by)
(1.0)
11,1)
fi) Σ f'0
f(.m
F(1,0) Ra.D)
R(D
x
(x)
fix) Ran/iinn +hmof [1,n]0++11 (e Maooy) "a..90
Figure 1: Schematic diagram of the functioning of Oblique Decision Forests. (Left): We illustrate the computation of soft-routed oblique tree output f'(x) using individual tree node outputs. We observe that the final tree decision is composed of individual node outputs. (Right): We showcase how decisions from multiple oblique trees are combined to form f(x).
In soft-routed oblique decision trees, we observe that the prediction fxx a linear combination of all the leaf parameters. The coefficients (x) = -II==1 (x) is the product of all probabilities along the path from the root to the 1-th leaf and A(i, I) is the 1-th leaf's ancestor at depth i. We observe that learning the parameters of the soft-routed tree structure much easier as we can easily compute the gradients of parameters w.r.t. f(x using backpropagation. We further improve the efficiency by computing fx) using matrix operations as described in Section 3.4. In our work, we use complete binary tree of height h to parameterize obliques trees. Note that the proposed soft-routed oblique trees are reminiscent of the sigmoid tree decomposition (Yang al., 2019) used in alleviating the softmax bottleneck.
We use an ensemble of trees and the expected output as the final prediction to reduce the variance and increase the predictive power of the outputs of soft-routed oblique decision trees. We call this
soft-routed oblique forest, which is computed as: fxx L/|T| 1/IT| | fx(x,, where (x) is the output of the t-th soft-routed oblique decision tree. The schematic diagram is shown in Figure 1.
3 ARANYANI: FAIR OBLIQUE DECISION FORESTS
In this section, we present Aranyani, a framework to enhance group fairness in decisions made during online learning. In this work, we focus on the group fairness notion of statistical or de- mographic parity. Our framework can be easily extended to other notions of group faimesss such as equalized odds (Hardt al., 2016), equal opportunity (Hardt al., 2016), and representation parity (Hashimoto et al., 2018) 8) as described in Appendix C.I.
3.1 PROBLEM FORMULATION
We describe the online learning setup where input instances arrive incrementally (x1, X2,x..... .), with X, arriving at time step t. The goal of the oblique decision forest ff is to make accurate decisions w.r.t. the lask, y (e.g., hiring decisions) while being fair w.r.t. the protected attribute, a (e.g., gender). At time step I, outputs prediction ÿe based on f(x:), where Dt = f(x,) for regression and ft = arg max of fx) for classification. With a slight abuse of notation, we denote decisions made for instance with protected attribute = k as f(xla k) (forest output) or nxx = k) (node output), where = {0, Following prior work (Zhang & Ntoutsi, 2019), we consider the setup where the model receives both the true label 3/+ and demographic label at of an instance x, after predicting ÿt. The model can then use this feedback to update its parameters. In this work, we consider the scenario where the model is not allowed store previous samples. Note that storing previous instances may pose additional challenges in applications that need to adhere to privacy guidelines (Voigt& Von dem Bussche, 2017) or involve distributed infrastructure, such as federated learning (Konečný et al., 2016). In this work, we focus on demographic parity notion of faimesss:
DP E[f 0)) E(f(x(a 1)]]-
3

---

Published as a conference paper at ICLR 2024
Note that in the above definition, consider slightly modified version of demographic parity to handle scenarios where the preferred outcome (or target label) is not explicitly defined. For simplicity, we describe our system using a binary protected attribute E {0, 1}. however, it can handle protected attributes with multiple classes (>2) as well (see more details in Appendix C.2).
3.2 OFFLINE SETTING
We begin by describing the simpler offline setting, in which all the training data is accessible prior to making predictions. this setting, I is optimized using stochastic gradient descent in a batch-wist manner. The constrained objective function is shown below:
min LJ v), subject to [x 0)] Elf(xxa 1)]1 <,
y
where C(:;) -) is the task loss function' / (e.g., cross entropy loss) and y is the true task label. The non- convex and non-smooth nature of the fairness objective (L.1-nomm in the DP term) makes it difficult to optimize the group fairness loss.
When f is an oblique decision forest, we leverage its hierarchical prediction structure to impose group fairness constraints on the local node-level outputs, (x)(x) (j-th node at depth i) of the tree. The rationale behind applying constraints at the node outputs stems from the observation that if instances from different groups receive similar decisions at every node, then the final decision (which an aggregation of the local decisions, Definition 2) is expected to be similar. We can formulate the node-level fairness constraints (Fij) as shown below:
min (x),,),) s.t. ((i,5) [Fyg < E, where Fij = ElIny((/e = 0)] - (x = 1)]. y
(3)
The node constraints FF are applied to all nodes (indexed by (i,j)) in the tree. We discuss the rela- tion between node-level constraints and group fairness in Section 4. We note that Fi, is a function of the parameters of the (i, j-th node only. In practice, we observe that this parameter isolation (Rusu et al., 2016) achieved by imposing fairness constraints on the local node-level outputs makes it easier to optimize f. We would like to emphasize that Aranyani can be extended to other notions of group fairness by modifying the formulation of Fij (see Appendix C.
However, the optimization procedure in Equation 3 is hard to solve. We relax it by using smooth surrogate for the L1-norm and turning the constraint into a regularizer. In particular, we use Huber loss function (Huber, 1992) (with hyperparameter 5 >> 0) and the relaxed optimization objective is:
[F2/2 ( 18|Fss 6/21, otherwise
F <
min ((f(x).)) + Σ Ho(Fig) ) where Ho(F.) (=
(4)
with À being a hyperparameter. In the offline setting, the expectations over input instances Fig (Equation 3) are computed using samples within a training batch. In the online setup, computing these expectations is challenging as we only have access to individual instances at a time and not to batch. Therefore, naively optimizing Equation 3 or 4 in the online setup requires storing all (or at least a subset) of the input instances. Moreover, we need to perform additional forward and backward passes for all stored instances to compute the group faimess gradients. In practice, this can be quite expensive in the online setting. In the following section, we discuss how to efficiently compute these group fairness gradients in the online setting.
3.3 ONLINE SETTING
In this section, we describe the training process for Aranyani in the online setting. As noted in the previous section, computing the expectations in group fairness terms is challenging due to storage and computational costs. However, we do not need to compute the loss exactly using previous input instances as we only need the gradients of the loss function to update the model. We show that it is possible to estimate the fairness gradients by maintaining aggregate statistics of the node-level outputs in the tree. Taking the derivative of Equation 4, with respect node parameters θ [W. B]
We assume that the task loss can be defined using single instance. This holds for most commonly used loss functions like cross entropy and mean squared error.
4

---

Published as a conference paper at ICLR 2024
of model f. we get the following gradients:
G(Ø) = ve((f(x), + Σ (Flls(Fi))
Vi.j
where Volls(Fe) = Fix VeF
if F <8
(5)
ösgn - V Ve ig
otherwise
and Ve E[Venx o (x 1)]-
In the above equation, have unbiased estimate of the task gradient: Vel(f(x), y) for an iid. sample x. The fairness gradient (FH can be estimated by maintaining a number of aggregate statistics each decision tree node. Specifically,
need to store the following aggregate statisties: (a) E[n,, (x]a = k)] and (b) E[Ven; (x/a = k)]. vk. where & E {0, 1} denotes different protected attribute labels. In practice, for every incoming sample x, we compute (x,(X,) and V Ven,y(x,), and update the aggregate statistics based on the protected label Oz. We denote the node constraints and gradients estimated using aggregate statistics as Fij and (()) respectively.
Note that in this setup,
not need to store the previous input instances or query I multiple times.
Furthermore, computing niy(x) and Venii (x) is relatively inexpensive. For sigmoid functions, both (x) and (x) can be obtained using a forward pass as: (x) n1y(x)(1
ny (x)) We discuss several properties of the estimated gradient G(O) in Section 4.
3.4 TRAINING PROCEDURE
In this section, we present efficient training strategy for Aranyani. In general, tree-based architec- tures are slow to train using gradient descent as gradients need to propagate from leaf nodes to other nodes in a sequential fashion. We introduce a parameterization that enables us compute oblique tree outputs only using matrix operations. This enables training on modern accelerators (like GPUs or TPUs) and helps us to efficiently compute task gradients (Equation 5) by using state-of-the-are autograd libraries. We begin by noting that all tree node outputs are independent of each other given the input x. Therefore, the node outputs can be computed in parallel as shown below:
N = g gW" x + B) E R", where W E Roxd B E R
and m = 24 - the number internal nodes (for complete binary tree). Subsequently, these node outputs are utilized to calculate the probabilities required to reach individual leaf nodes. The path probabilities are computed by creating 2 (number of leaf nodes) copies of the node outputs, .N) E Rmxx"", and applying a mask, A, that selects the ancestors for each
- N, leaf node. Each element of the mask Aij E {-1, 0, 1} selects whether the leaf path from selected node is left (1), right (-1), or doesn't 't exist (0). The exact probabilities are then stored in P. This sequence operations is shown below:
f(x) = exp (11xm log P)O, where P = ReLU C A) + (1mx2 - ReLU A))
and E xe, The selected probabilities can be utilized to compute the final output as f(x). More details about the construction of mask A is reported in Appendix D.3.
4 THEORETICAL ANALYSIS
In this section, we theoretically analyze several properties of Aranyani. In our proofs, we make assumptions that are standard in the optimization literature such as compact parameter set, Lips- chitz task loss, bounded input and bounded gradient noise (see Appendix A. for more details). First, we discuss the conditions of the node-level decisions and how they relate to group fairness constraints. Second, we analyze the properties of the gradient estimates (Equaatio 5) and show that the expected gradient norm converges for small step size and large enough time steps.
Lemma (Demographic Parity Bound). Lei [(x) be soft-routed oblique decision tree of height h with ||@:]| = and assume an equal number of input instances x xfor each group of a binary protected attribute E {0, 1). Then, if all the node-level decisions satisfy the following condition:
Allns(xxaa = 0) (x = 1)]] S e, v(i.j).
(6)
Then, the overall demographic parity of [xx is bounded DP & e, for >> 0.
5

---

Published as a conference paper at ICLR 2024
The above lemma (proof in Appendix A.2) provides the node-level constraint (Equation 6) that upper bounds the demographic parity. We note that the node constraint [Fig (Equation 4) is a weaker constraint than the one derived above. The rationale behind using Fez over the derived constraint is based on two key considerations: First, the expectation is computed using sample pairs from complementary groups (in Equation 6), which is challenging settings. Second, optimizing this constraint can severely limit the task performance as it encourages the trivial solution of having the same node outputs for all instances.
compute in both offline and online
Next, we derive the Rademacher complexity of soft-routed decision trees. Empirical Rademacher complexity, R. (H), measures the ability of function class H. to fit random noise indicating its ex- pressivity (formal definition and proof in Appendix A.3).
Lemma 2 (Rademacher Complexity). Empirical Rademacher complexity, Rn).), for soft-routed decision tree (of height h) function class, f(x) E H,, and [|&:]| = is bounded as: (H) S 2h /
We observe that the bound exponentially increases with the height of the tree, h. Interestingly, according to the DP bound in Equation 6, it appears that we can easily improve group fairness by using a shallower tree (smaller h). This illustrates the trade-off between fairness and accuracy, highlighting that it is not feasible to enhance group faimess without substantial impact on accuracy.
Next, we derive the estimation error bound for the gradients (in Equation 5). which stems from the fact that use aggregate statistics of node outputs from previous time steps where the model parameters were different. First, we derive the estimation error bounds for the aggregate statistics Fij and Fig (Lemma 4). Using these results, we bound the estimation error of faimnsss gradients Ve (Fig) in the following lemma (proof in Appendix A.4).
Lemma 3 (Fairness Gradient Estimation Error). For soft- oblique decision tree f(x) with T.g-smooth activation function g(-), bounded i..dd input instances ||xe|| S B, and compact param- eter set O E (0 R) (Frobenius norm ball of radius R), the estimation error can be bounded:
(V) - Ve 5B/2,
where 5 is the Huber loss parameter (Equation 4).
Next, we use the above bound to derive the convergence of biased gradients building on the results from Ajalloeian & Stich (2020) to obtain the following result (proof in Appendix A.5): Theorem 1 (Gradient Norm Convergence). Using the assumptions in Lemma 3, the expected gra- dient norm VT 1/T T-1 B[I]G(@))]]] can be bounded as: VT S (e (6+22%) 228 B²), for large enough time step T max 1FL(M+1) L -F small step size ? S min (MIi si.!
and >> 0 (see definitions in Appendix A.5).
The above bound demonstrates that the expected norm of the gradients estimated using the aggregate statisties of decisions from previous time steps converges over time (see Appendix A.5). In the following sections, we perform experiments to empirically verify the theoretical results.
5 EXPERIMENTS
In this section, we present the details of our experimental setup and results to evaluate Aranyani. Our implementation is available at: https//githubb.co//rccom/ www.bccoomnatt//Araaaaao Arantt///////////./
Baselines. We compare Aranyani V with the following online learning algorithms: Hoeffding Trees (HT) (Domingos & Hulten, 2000) performs decision tree learning for online data streams by leveraging the Hoeffdiig bound (Hoeffding, 1994). Adaptive Hoeffding Trees (AHT) (Bifet & Gavalda, 2009) improves upon HTTs by detecting changes in the input data stream and updating the learning process accordingly, >> FAHT (Zhang & Ntoutsi, 2019) modifies the HT splitting algorithm by introducing group fairness constraints while computing the Hoeffding bound, O MLP Aranyani, (MLP), uses an MLP as f(x and the same online learning updates described in Section 3.3 (more details about the architecture in Appendix D), Leaf Aranyani (Leaf) stores the aggregate gradient statistics w.r.t. leaf-level predictions or the final output instead of the node predictions, Majority is a post-processing baseline considers the output of fxx with probability p and outputs the majority
6

---

Published as a conference paper at ICLR 2024
Adu
Census
COMPAS
87
66.4
Accuracy
58-
94.2
54
94.0
72
0.02
0.01
0.34
DP
DP
DP
Majority
Hoeffding Tree (HT)
Adaptive HT FAHT
MLP
Leaf
Aranyani
We report the group fairness (demographic parity) vs. task performance (accuracy) trade- off plots for different systems in (left) Adult, (center) Census, and (right) COMPAS datasets. Ideally, a fair online system should achieve low demographic parity along with high accuracy scores. Con- sidering the inverted r-axis, the performance of a fair system should lie in the top right quadrant of each plot. We report Aranyani's performance for different X's and observe that it achieves better securacy-fairnese trade-off compared to baseline systems.
Figure 2:
label with (1 - p) probability. We report the results for different values of p. The majority baseline can provide a fairness improvement by simply decreasing the task performance, but it requires prior access to target label information. In practice, outperforming the majority baseline is not easy. As pointed out by (Lowy et al., 2022), many offline techniques fall short of the majority's performance when batch sizes are small, which is consistent with the online learning setup.
Online Setup& & Evaluation. We the online learning setup described in Section 3.1. For each algorithm, we retain predictions Je from every step and report the average task performance (aceu- racy) and demographic parity. In all experiments (unless otherwise stated), we use oblique forests with 3 trees and each tree has a height of (based on a hyperparameter grid search). We provide further details in Appendix D. Next, we present the evaluation results of fair online learning using Aranyani and other baselines on tabular datasets, vision, and language- based dataset.
5.1 TABULAR DATASETS
We conducted our experiments on the following tabular datasets: (a) UCI Adult (Becker & Kohavi, 1996), (b) Census (Dua et al., 2017), and (c) ProPublica COMPAS (Angwin et al., 2016). Adult dataset contains 14 features of 448K individuals. The task involves predicting whether the annual income of an individual is more than $50K or not and the protected attribute gender. Census dataset has the same task description but contains 41 attributes for each individual and 299K in- stances. Propublica COMPAS considers the binary classification task of whether a defendant will re-offend with the protected attribute being race. COMPAS has 7K instances.
Figure/ demonstrates the fairness-accuracy trade-off, where æ and y-axis show the average demo- graphic parity (DP) and accuracy scores respectively. Idcally, we want online system achieve low DP and high accuracy, making the top-right quadrant the desired outcome (æ-axis is inverted). We report A Aranyani's performance for different À values (Equation 5), which controls the trade-off. We observe that V Aranyani's is results lie in the top-right portion, showcasing that it can achieve the best trade-off. We also observe that the variance in the results of Aranyani is high in COMPAS. This could be because COMPAS has fewer instances than other datasets, potentially affecting con- vergence. We also compare with FERMI Lowy al. (2022), the only stochastic algorithm known to us that can be applied in online settings, and observe significant gains (Appendix E, Figure 11).
We also assess the significance of the tree structure in Aranyani by examining the Aranyani MLP O baseline that employs the same gradient accumulation method discussed in Section 3.3, but without the tree structure. In all datasets, we observe that the MLP baseline is unable to improve the fairness scores beyond certain point. Upon further investigation, we found that this phenomenon happens due to the vanishing fairness gradients in the layers further from the output. We also observe the same phenomenon for 4 Leaf baseline, where the faimess gradients for nodes away from the leaves become very small and they cannot be trained effectively. This showcases the importance of parame- ter isolation in Aranyani and the application of group fairness constraints on local decisions. We also note that the conventional Hoeffding tree-based baselines (HT AHT and FAHT D) achieve poor faimess scores, often falling behind majority post-processing. which shows that HT based ap-
7

---

Published as a conference paper at ICLR 2024
Civi Comments
CelebA
04
94.5
50-
95.5
85
Majority Hoeftding Tree (HT)
Adaptive HT
MLP < Leaf V
Aranyani
Figure 3: We report the group fairness accuracy trade-off plots for different systems in (left) CivilComments and (right) CelebA datasets. We observe that Aranyani achieves significantly better accuracy-fairnes trade-off than baseline systems.
proaches are unable to robustly improve the group fairness. Overall, we observe that Aranyani can achieve a better accuracy- securacy-firness trade-off than baseline approaches across all datasets.
5.2 VISION LANGUAGE DATASETS
We also conduct experiments on (a) CivilComments (Do, 2019) toxicity classification and (b) CelebA (Liu et al., 2015) image classification datasets. CivilComments a natural language dataset where the task involves classifying whether online comment is toxic not. We religion as the protected attribute and consider instances of religion labels: "Muslim" and "Christian", as they showcase the maximum discrepancy in toxicity. For CivilComments, we obtain text representations model, Instructor (Su et al., 2023) by using the prompt "Represent toxic-
from the instruction-turr ity comment for classifying its toxicity as toxic non-toxic: [comment]'. CelebA dataset contains 200K images of celebrity faces with 40 categorical attributes. Following previous works (Jung et al., 2022b; Qiao & Peng, 2022; Jung al., 2022a; Liu al., 2021), we select "blond hair" as the task label and "gender" as the protected attribute. For CelebA, we retrieve the image representations from the CLIP model (Radford al., 2021).
In Figure 3, we report the faimess trade-off plots, where we observe that Aranyani V achieves the best accuracy-fairnen trade-off on both datasets. Similar to tabular datasets, we observe that the MLP O and Leaf' < baselines unable to improve the fairness scores at all. Hoeffding tree (HT) baseline achieves decent faimess scores but is unable to converge on the task. This highlights the limitations of traditional decision trees when dealing with aon-axis-aligned data.
5.3 ANALYSIS
In this section, we perform empirical evaluations to analyze the functioning of Aranyani.
Reservoir Variant. We compare the performance of Aranyani with variant (using oblique forests) that stores all samples in the online stream to compute the faimess loss. We refer to this variant "Reservoir". In Figure 4 (left), observe that Aranyani achieves similar accuracy-fairnes tradeoff compared to the reservoir variant on the Adult dataset. As Aranyani does not need to store previous input samples, is quite efficient achieving ~33x improvement computation time and ~23% reduction in memory utilization.
Gradient Convergence. We investigate the convergence of the gradients used update the oblique tree. We conduct our experiment on CivilComments dataset using Aranyani with single tree and report the norm of the total gradients and faimess gradients used to update W (weight parameter of each node). In Figure 4 (center), we observe that the norm of both task and faimess gradients converge over time during the online learning process. This corroborates our theoretical guarantees in Lemma 1. We found this behavior to be consistent across different parameters (Appendix E).
Tree Height Ablations. We study the effect varying the tree height in oblique forests on the faimessyaccuracy tradeoff. In Figure 4 (right), we report Aranyani's performance on the Adult dataset with a fixed parameter À = 0.1. We observe that the accuracy increases with height and the demographic parity worsens (g-axis is inverted) with increasing height. This is consistent with our theoretical results (Lemma & 2). However, we have observed slight decrease in accuracy when using large tree heights (height=8). This observation suggests that oblique trees may overfit
8

---

Published as a conference paper at ICLR 2024
Task Gradient
13.
Rai Gradient
0.08
82
Gradient Norm
*
12.5
0.10
8c
10-2
12.0
0.12
78
Aranyani (1-1s, memmla) Reservoir (1=3x, mmmmi.33)
11.0
Accuracy
0.14
10.5
0.18
0:35 0.13
0.05 0:03 0.00
5000 10000 19000 20000 25000 30000
DP
Iterations
Tree Depth
Figure 4: (left) We compare Aranyani with the reservoir variant that stores all input instances, (cen- ter) we investigate the gradient convergence, and (right) the impact of tree height on performance.
the training data when reaching a certain height, and choosing shallower tree could be beneficial. We perform additional experiments to investigate the performance of Aranyani (see Appendix E).
6 RELATED WORKS
Fairness. Existing work on promoting group fairness can be classified into three categories: pre- processing (Zemel et al., 2013; Calmon et al., 2017), post-processigg (Hardt et al., 2016; Pleiss et al., 2017: Alghamdi et al., 2022), and in- in-processing (Quadrianto & Sharmanska, 2017; Agarwal al., 2018; Mary et al., 2019; Prost et al., 2019; Baharlouei et al., 2019; Lahoti et al., 2020; Lowy et al., 2022; Basu Roy Chowchury et al., 2021; Chowdhury & Chaturvedi, 2022; Chowdhury et al., 2023; Baharlouei et al., 2024) techniques. These are trained and tested on static dataset, and there is growing concern that they fail to remain fair under distribution shifts (Barrett et al., 2019; Mishler & Dalmasso, 2022; Rezaei et al., 2021; Wang et al., 2023). This calls for fairness-award systems that can adapt to distribution changes and update themselves in an online manner. However, an online learning setting, where input instances arrive at time, presents several challenges that make it difficult to apply existing techniques: (a) propprocssiing techniques are not feasible as they require prior access to input instances; (b) post-processing techniques often require access to a held-out set, which may be impractical; and (c) in- in-processing techniques need a batch of samples to estimate the group fairness loss, which may not always be feasible due to privacy reasons (Voigt & Von dem Bussche, 2017) or distributed infrastructure (Konečný et al., 2016). FERMI (Lowy et al., 2022) is the only in-processing approach that can work with a batch size of 1. Although several works (Gillen et al., 2018; Bechavod et al., 2020) have studied individual faimess in online settings, only a few recent works (Chowdhury & Chaturvedi, 2023; Zhao et al., 2023; Chen et al., 2023; Yin et al., 2024; Truong et al., 2024; Jiang et al., 2024) considered group fairness in settings where the underlying task or data distribution changes over time. However, these systems are incrementally trained on sub-tasks, requiring access to task labels, which is not available in online data streams.
Gradient-based learning of trees, Similar to Aranyani that leveraged a gradient- gradient-based objective, (Karthikeyan al., 2022) uses gradient-based methods discover the structure of oblique decision tree classifiers. Discovering tree structures with gradient-based methods has been also considered in works autoencoders (Nagano al., 2019; Shin al., 2016), on discovering structure (e.g., parses) in natural language (Yin et al., 2018; Drozdov et al., 2019). hierarchical clustering (Monath et al., 2017: 2019; Zhao et al., 2020; Chami al., 2020), phylogenetics (Macaulay & Fourment, 2023; Penn et al., 2023), and extreme classification ( (Yu et al., 2022; Jernite et al., 2017; Sun et al., 2019; Jasinska- Kobuas al., 2021). We discuss more prior works related decision trees in Appendix B.
7 CONCLUSION
In this paper, we propose Aranyani, a framework to achieve group fairness in online learning. Aranyani uses an ensemble of oblique decision trees and leverages its hierarchical prediction struc- ture to store aggregate statistics of local decisions. These aggregate statistics help in the efficient computation of group fairness gradients in the online setting, eliminating the need to store previ- ous input instances. Empirically, we observe that Aranyani achieves significantly better accuracy- fairness trade-off compared to baselines on a wide range of tabular, image, and text classification datasets. Through extensive analysis, we showcase the utility of our proposed tree-based prediction structure and fairness gradient approximation. While we investigated binary oblique tree structures, their ability to fit complex functions can be limited when compared to fully connected networks. Fu- ture research can explore other parameterizations (e.g., graph-based structures) that enable effective gradient computation to impose group fairness in online settings with superior prediction power.

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
We have submitted the implementation of Aranyani in the supplementary materials. We have exten- sively discussed the details of our experimental setup, datasets, baselines, and hyperparameters in Section 5 and Appendix E. We have also provided the details of our training procedure in Section 3.4 and Appendix D.3. We will make our implementation public once the paper is published.
ETHICS STATEMENT
In this paper, we introduce an online learning framework, Aranyani, to enhance group faimness while making decisions for an online data stream. Aranyani has been developed with the intention of mitigating biases of machine learning systems when they are deployed in the wild. However, it is crucial thoroughly assess the data's quality and the accuracy of the demographic labels used for training Aranyani, as otherwise, it may still encode negative biases. In our experiments, we use publicly available datasets and obtain data representations from open-sourced models. We do not obtain any demographic labels through data annotation or any private sources.
ACKNOWLEDGEMENTS
The authors are thankful to James Atwood, Anneliese Brei, Shounak Chattopadhyay, Haoyuan Li, and Anvesh Rao Vijini for helpful feedback and discussions. The work began when Somnath Basu Roy Chowdhury was student researcher at Google. Somnath Basu Roy Chowdhury and Snigdha Chaturvedi were partly supported by Amazon Research Awards and the National Science Founda- tion under award DRI-21 12635.
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jazefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wat- tenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learn- ing on heterogeneous systems, 2015. URL https: /tww///w.///// tensorfloo org/ Software available from tensorflow.org.
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reduc- tions approach to fair classification. In International conference on machine learning, pp. 60-69. PMLR. 2018
Sina Aghaei, Mohammad Javad Azizi, and Phebe Vayanos. Learning optimal and fair decision trees for non-discriminative Docision-making In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 1418-1422 2019.
Ahmad Ajallocian and Sebastian U Stich. On the convergence of sgd with biased gradients. arXiv preprint arXiv:2008. 00051, 2020.
Wael Alghamdi, Hsiang Hsu, Haewon Jeong, Hao Wang, Peter Michalak, Shahab Asoodeh, and Flavio Calmon. Beyond adult and compas: Fair multi-class prediction via information projection. Advances in Neural Information Processing Systems, 35:38747-38760 2022.
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. In Ethics of data and analytics, pp. 254 264. Auerbach Publications, 2016.
Sina Baharlouei, Maher Nouiehed, Ahmad Beirami, and Meisam Razaviyayn. Rényi fair inference. In International Conference on Learning Representations, 2019.
10

---

Published as a conference paper at ICLR 2024
Sina Baharlouei, Shivam Patel, and Meisam Razaviyayn. f-FERM: A scalable framework for robust fair empirical risk minimization, In The Tweifth International Conference on Learning Represen- tations, 2024. URL /tttttpss///ppeeeeeee///
/oppnreveeeeeeeeeeeeeeeeeeeeeeee net/ Eorum?id-s90viaaaa
Maria Barrett, Yova Kementchedjhieva, Yanai Elazar, Desmond Elliott, and Anders Søgaard. Ad- versarial removal of demographic attributes revisited. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 3330-6335, 2019.
Somnath Basu Roy Chowdhury, Sayan Ghosh, Yiyuan Li, Junier Oliva, Shashank Srivastava, and Snigdha Chaturvedi. Adversarial scrubbing of demographic information for text classifi- cation. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 550-562, Online and Punta Cana, Dominican Republic, November 2021, As- sociation for Computational Linguistics. doi: 10. 1211663///22222..mmmmaaaall //aclanthology. . org/2021. emnlp-enmeem cammppmmain......mmmmmmmmmmmmmmm main. 43.
URL https:
Yahav Bechavod, Christopher Jung, and Steven Wu. Metric-free individual fairness in online learning. Advances in neural information processing systems, 33:11214-11221 2020.
Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. DOI:
https://doi.org/10..22 http://dd.oorro1o.242/////////// 0.2444//55222
Lukas Biewald. Experiment tracking with weights and biases, 2020. URL https://www wandb. com/. Software available from wandb.com.
Albert Bifet and Ricard Gavalda. Adaptive learning from evolving data streams. In Advances in Intelligent Data Analysis VIII: 8th International Symposium on Intelligent Data Analysis, IDA 2009, Lyon, France, August 31-September 2, 2009, Proceedings 8. pp. 249-260. Springer, 2009.
Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commer- cial gender classification. In Conference on faimasssss, accountability and transparency, pp. 77-91. PMLR, 2018.
Flavio Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush Varshney. Optimized pre-processing for discrimination prevention. Advances in neural informa- fion processing systems, 30, 2017.
Ines Chami, Albert Gu, Vaggos Chatziafratis, and Christopher Ré. From trees to continuous embed- dings and back: Hyperbolic hierarchical clustering. Advances in Neural Information Processing Systems, 33:15065-15076, 2020.
Qinyi Chen, Jason Cheuk Nam Liang, Negin Golrezaei, and Djallel Bouneffouf. Interpolating item and user fairness in recommendation systems. Available SSRN 4476512, 2023.
Somnath Basu Roy Chowdhury and Snigdha Chaturvedi. Learning fair representations via rate- distortion maximization. Transactions of the Association for Computational Linguistics, 10: 1159-1174, 2022.
Somnath Basu Roy Chowdhury and Snigdha Chaturvedi. Sustaining faimnsss via incremental leam- ing. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 6797-6805, 2023.
Somnath Basu Roy Chowdhury, Nicholas Monath, Kumar Avinava Dubey, Amr Ahmed, and Snigdha Chaturvedi. Robust concept erasure via kernelized rate-distortion maximization. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Sam Corbett-Davies, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic decision making and the cost of faimess. In Proceedings of the 23rd acm sigkdd international conference on knowledge discovery and data mining, pp. 797-806, 2017.
Jeffrey Dastin. Amazon scraps secret Al recruiting tool that showed bias against women. In Ethics of data and analytics, pp. 296 299. Auerbach Publications, 2022.
Quan Do. Jigsaw unintended bias in toxicity classification. 2019.

---

Published as a conference paper at ICLR 2024
Pedro Domingos and Geoff Hulten. Mining high-speed data streams. In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 71-80, 2000.
Andrew Drozdov, Pat Verga, Mohit Yadav, Mohit lyyer, and Andrew McCallum. Unsuper- vised latent tree induction with deep inside-outside recursive autoencoders. arXiv preprint arXiv:/904.022 2019.
Dheeru Dua, Casey Graff, et al. Uci machine learning repository. 2017.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations theoretical computer science confer- ence, pp. 214-226, 2012.
Stephen Gillen, Christopher Jung, Michael Kearns, and Aaron Roth. Online learning with an un- known fairness metric. Advances in neural information processing systems, 31, 2018.
Swati Gupta and Vijay Kamble. Individual faimeess in hindsight. Journal of Machine Learning Research, 22(1444 22(144):1-35, 2021. URL httpt://mmmml r. org/
/tt///222//99/// 658 3html.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographics in repeated loss minimization. In International Conference on Machine Learning, pp. 1929-1938. PMLR, 2018.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffding, pp. 409-426, 1994.
Max Hort, Zhenpeng Chen, Jie M. Zhang, Mark Harman, and Federica Sarro. Bias mitigation for machine learning classifiers: A comprchensive survey. ACM Responsib. Comput., nov 2023, doi: 10.1145/3631326 URL https: http:///ooooooo//eee/e/ee 11.11111111111111 Just Accepted.
Peter Huber. Robust estimation of a location parameter. Breakthroughs in statistics: Methodol- ogy and distribution, pp. 492-518. Springer, 1992.
Kalina Lasinska-Kobur Marek Wydmuch, Devanathan Thiruvenkatachari, and Krzysztof Dem- bezynski. Online probabilistic label trees. In International Conference on Artificial Intelligence and Statistics, pp. 1801-1809. PMLR, 2021.
Yacine Jernite, Anna Choromanska, and David Sontag. Simultaneous learning of trees and represen- tations for extreme classification and density estimation. In International Conference on Machine Learning. pp. 1665-1674 PMLR, 2017.
Zhimeng Stephen Jiang, Xiaotian Han, Hongye Jin, Guanchu Wang, Rui Chen, Na Zou, and Xia Hu. Chasing fairness under distribution shift: A model weight perturbation approach. Advances in Neural Information Processing Systems, 36, 2024.
Michael Jordan and Robert A Jacobs. Hierarchical mixtures of experts and the em algorithm.
Neural computation, 6(2):181-214 1994.
Sangwon Jung, Sanghyuk Chun, and Taesup Moon. Learning fair classifiers with partially annotated group labels. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 18348-10357, 2022a.
Sangwon Jung, Taeeon Park, Sanghyuk Chun, and Taesup Moon. Re-weighting based group fairness regularization via classwise robust optimization. The Eleventh International Conference on Learning Representations, 2022b.
Faisal Kamiran, Toon Calders, and Mykola Pechenizkiy. Discrimination aware decision tree learn- ing. In 2010 IEEE international conference data mining, pp. 869-874. IEEF, 2010.
12

---

Published as a conference paper at ICLR 2024
Ajaykrishna Karthikeyan, Naman Jain, Nagarajan Natarajan, and Prateck Jain. Learning accurate decision trees with bandit feedback via quantized gradient descent. Transactions on Machine Learning Research, 2022.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), San Diega, CA, USA, 2015.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinske et al. Overcom- ing catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114(13)33521-33 -3526, 2017.
Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtarik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. In NIPS Workshop on Private Multi-Parry Machine Learning, 2016. URL https://arxte
org/abs/ 0011/1111.......... 05492.
Preethi Lahoti, Alex Beutel, Jilin Chen, Kang Lee, Flavien Prost, Nithum Thain, Xuezhi Wang, and Ed Chi. Fairness without demographies through udversarially reweighted learning. Advances in neural information processing systems, 13:728-740, 2020.
Jeff Larson, Surya Mattu, Lauren Kirchner, and Julia Angwin. How we analyzed the compas recidi- vism algorithm. ProPublica (5 2016), 31):3-33, 2016.
Evan 7. Liu, Behzad Haghgoo, Annie Chen, Aditi Raghunathan, Pang Wei Koh, Shiori Sagawa, Percy Liang, and Chelsea Finn. Just train twice: Improving group robustness without training group information. In International Conference on Machine Learning, pp. 6781-6792. PMLR, 2021.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
Andrew Lowy, Sina Baharlouei, Rakesh Pavan, Meisam Razaviyayn, and Ahmad Beirami. A stochastic optimization framework for fair risk minimization. Trunsactions on Machine Learning Research, 2022.
Matthew Macaulay and Mathieu Fourment. Differentiable phylogenetics via hyperbolic embeddings with dodonaphy. arXiv preprint arXiv:2309.1 17332, 2023.
Jérémie Mary, Clément Calauzenes, and Noureddine El Karoui. Faimess-awarr learning for contin- uous attributes and treatments. International Conference on Machine Learning, pp. 4382-4391.
PMLR, 2019.
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey bias and fairness in machine learning. ACM computing surveys (CSUR), 5466: 2021.
Alan Mishler and Niccolò Dalmasso. Fair when trained, unfair when deployed: Observable fair- ness measures are unstable in performative prediction settings. arXiv preprint arXiv:2202.05049, 2022.
Nicholas Monath, Ari Kobren, Akshay Krishnamurthy, and Andrew McCallum. Gradient-based hi- erarchical clustering. In 31st Conference neural information processing systems (NIPS 20/7), Long Beach, CA, USA, volume 1, pp. 6, 2017.
Nicholas Monath, Manzil Zaheer, Daniel Silva, Andrew McCallum, and Amr Ahmed. Gradient- based hierarchical clustering using continuous representations of trees in hyperbolic space. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 714-722, 2019.
Sreerama K Murthy, Simon Kasif, and Steven Salzberg. system for induction of oblique decision trees. Journal of artificial intelligence research, 2:1-32, 1994.
13

---

Published as a conference paper at ICLR 2024
Yoshihiro Nagano, Shoichiro Yamaguchi, Yasuhiro Fujita, and Masanori Koyama. A wrapped nor- mal distribution on hyperbolic space for gradient-basse learning. In International Conference on PMLR, 2019.
Machine Learning. pp.
Matthew J Penn, Neil Scheidwasser, Joseph Penn, Christl A Donnelly, David A Duchêne, and Samir Bhatt. Leaping through tree space: continuous phylogenetic inference for rooted and unrooted trees. arXiv preprint arXiv:2306.057.99 2023.
Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. On fairness and calibration. Advances in neural information processing systems, 30, 2017.
Flavien Prost, Hai Qian, Ed H. Chi, Jilin Chen, and Alex Beutel. Toward better trade-off be- tween performance and fairness with kernel-based distribution matching. 2019. URL https:
//arxivv /tt/ / 910. 111.11771...11111111111111111111 pd.
Fengchun Qiao and Xi Peng. Graph-relational distributionally robust optimization. In NeurlPS 2022
Workshop on Distribution Shifts: Connecting Methods and Applications, 2022.
Novi Quadrianto and Viktoriia Sharmanska. Recycling privileged learning and distribution matching for fairness. Advances in neural information processing systems, 30, 2017.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference machine learning, pp- 8748-8763. PMLR, 2021.
Edward Raff, Jared Sylvester, and Steven Mills. Fair forests: Regularized tree induction to minimize model bias. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pp. 243-250, 2018.
Inioluwa Deborah Raji and Joy Buolamwini. Actionable auditing: Investigating the impact of pub- licly naming biased performance results of commercial products. Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pp. 429 435, 2019.
Ashkan Rezaei, Angi Liu, Omid Memarrast, and Brian D) Ziebart. Robust faimess under covariate shift. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9419- 9427, 2021.
Andrei A Rusu, Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. 2016.
Richard Shin, Alexander A Alemi, Geoffrey Irving, and Oriol Vinyals. Tree-structured variational autoencoder. 2016.
Hongjin Su, Weijia Shi, Jungo Kasai, Yizhong Wang. Yushi Hu, Mari Ostendorf, Wen-tau Yih, Noah A. Smith, Luke Zettlemoyer, and Tao Yu. One embedder, any task: Instruction-fimetueed text embeddings. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Findings of the Association for Computational Linguistics: ACL 2023, pp. 1102-1121, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10. 11118663//12223.fnmmmn findinns--cl..7... URL https: aacaaannnoooooyyyyyooo org/ 2023. findings acl. 71.
Wen Sun, Alina Beygelzimer, Hal Daumé lii, John Langford, and Paul Mineiro. Contextual memory trees. In International Conference on Machine Learning, pp. 6026-6033 PMLR, 2019.
Thanh-Dar Truong, Hoang- Quan Nguyen, Bhiksha Raj, and Khoa Luu. Fairess continual learn- ing approach to semantic scene understanding in open-world environments. Advances in Neural Information Processing Systems, 36, 2024.
Paul Voigt and Axel Von dem Bussche. The eu general data protection regulation (gdpr). A Practical Guide, 1st Ed., Cham: Springer International Publishing, 1033152676) 2017.
Haotao Wang, Junyuan Hong, Jiayu Zhou, and Zhangyang Wang. How robust is your faimess? evaluating and sustaining fairness under unseen distribution shifts. Transactions on machine learning research, 2023, 2023.
14

---

Published as a conference paper at ICLR 2024
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jemnte, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. Transformers: State-of-the-ar natural language processing. In Qun Liu and David Schlangen (eds.), Proceedings of the 2020 Confer- ence on Empirical Methods in Natural Language Processing: System Demonstrations, pp. 38- 45, Online, October 2020. Association for Computational Linguistics. doi: 10.18653/v1/2020, emplp-demos.6. URL https: ac aalaannthloyyyy org/ 222000000 emnlp-demos 6.
Zhilin Yang, Thang Luong, Russ R Salakhutdinov, and Quoe V Le. Mixtape: Breaking the softmax bottleneck efficiently. Advances in Neural Information Processing Systems, 32, 2019.
Pengcheng Yin, Chunting Zhou, Junxian He, and Graham Neubig. StructVAE: Tree-structured latent variable models for semi-supervised semantic parsing. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 754-765, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 18.18653/v1/ P18-1070 URL https: : /aaaaaaaaannoooooooooooooo wwg/ P18 10000.
Tongxin Yin, Reilly Raab, Mingyan Liu, and Yang Liu. Long-term fairness with unknown dynamics. Advances in Neural Information Processing Systems, 36, 2024.
Hsiang-Fu Fu Yu, Kai Zhong, Jiong Zhang, Wei-Cheng Chang, and Inderjit S Dhillon. PECOS: Pre- diction for enormous and correlated output spaces. the Journal of machine Learning research, 23 (1):4233-4264, 2022.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International conference on machine learning, pp. 325-333. PMLR, 2013.
Wenbin Zhang and Eirini Ntoutsi. FAHT: An adaptive faimess--awaee decision tree classifier. 2019.
Chen Zhao, Feng Mi, Xintao Wu, Kai Jiang, Latifur Khan, Christan Grant, and Feng Chen. Towards fair disentangled online learning for changing environments. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1480-3491,222 2023
Jinyu Zhao, Hao, and Cyrus Rashtchian. Unsupervised embedding of hierarchical structure in euclidean space. arXiv preprint arXiv:2010.16055, 2020.
15

---

Published as a conference paper at ICLR 2024
A
THEORETICAL PROOFS
CONTENTS
A.1 Assumptions
16
A.2 Proof of Lemma
16
A.3 Proof of Lemma
17
A.4 Proof of Lemma
18
A.5 Proof of Theorem
19
A.6 Additional Theoretical Analysis
20
A.1 ASSUMPTIONS
In this section, we will present standard regularity assumptions utilized in deriving the theoretical results. We derive the results for soft-routed oblique decision forest, f(x), with single tree,
[T| = However, these can be easily extended to setup with multiple trees. Specifically, we derive the estimation errors in gradients leveraging the framework of Ajalloeian & Stich (2020), i.e.
we assume our stochastic gradient estimation for the objective has the following form: G( G(@) + b(θ) + neE), where b(θ) and n({) denotes the bias and noise involved in the estimation. We present an exact description all the assumptions used in our setup and optimization process:
(A1) The input instances x, arrive in an i.id. fashion and are bounded: ||><;] < B.
(A2) The parameter set is compact and lies within a Frobenius ball θ E (0 Rt) of radius R.
(A3) (x) denotes a soft-routed binary oblique forest with a single tree (7) 1), activation function, g()), and leaf parameters ||0:]| 1.
(A4) The activation function g(-) used oblique trees is Lg smooth.
(A5) The noise in gradient estimation n({) has zero mean Bg[n and is (M, bounded:
Egg [[)[ s ( + vO.
(A6) The task loss function ((:)) is Kj-Lipschitz.
A.2 PROOF OF LEMMA 1
First, we present proposition that would be helpful in proving Lemma
Proposition 1. Let pa and qs be samples from random variable P that is bounded between [0, 1]. Then, the following inequality holds:
II
II
4h
Σ
44
Pil-
(9)
Proof. The proof is presented below:
gi max [ps, 9:P
II min gi
Σ 19: Psl
max 9f
0#1
lq: Psl-
Next, proceed to the main proof of Lemma 1.
16

---

Published as a conference paper at ICLR 2024
Proof of Lemma 1.
The proof is completed using the following steps:
DP = [x = 0)] TEf(x 1)]1
Σ (i 0)0,
Σ (x|a - 1)81
E
E
E (x(pi(x(aa = 0)] (x:(x 1)]) 01
E [e Ep - 1)]1 10
AGa 00 - II (x
Σ
E
1
Il [mLA
Σ
II mssstan((x))
m
x1mp(x(a=1)
Σ
II mL..ai,,((x))
II ImLacn(()))
Xpruplx (=0) xp(x(==))
ni, (i.A(i,)((xo) (LAc),((3s))
(10)
m
Xg.Xi
Σ Σ [1L,A (x)))
(11)
ΣΣ<
h2ae.. E.
In the above proof, the first few steps use the linearity expectation. We derive Equation by using the result in Proposition 1. Finally, plugging the bound from Equation in Equation 11 we obtain the final result.
A.3 PROOF OF LEMMA 2
First, we present the definition of empirical Rademacher complexity, R. (HL), for function class, H.
n ft (x1)
R (H) = -E. sup
(12)
hch t=1
Intuitively, the above definition measures the expressivity of function class 7. by measuring the ability to fit random noise. In the above equation, for a given set S = {xi...., x and Rademacher vector e, the supremum quantifies the maximum correlation between f fxx, and randomly generated samples E 1f.1 H.
Proof. In Equation 12, we plug in the soft-routed binary oblique decision tree formulation, f(x) Th g( ol ((G.)) ba.Att.)) 10, in the above equation obtain:
17

---

Published as a conference paper at ICLR 2024
(H) = Ee
sup
g( LAG. + -
hEH
t=1
1=1 1=1
2
Ex
sup max NEH
W T. M. + b(.ACo)))))
t=1
i=1
2b
1
E2,
sup
C max
g ( T. ALL.)) + bLAC.
n
NEN
Next, we continue the proof by using F(x:) = max
IT Ww (.A br. and ||0|]| = 1.
2h
(H)
E.
sup
(xF(x))
hEH
2
sup E.c NEH
c ((xe)
71
2
sup E hEH
T1
& (xx))
+ E,
[d(F(())P(3))
n
2
n
E
2
n
2h /V.
A.4 PROOF OF LEMMA 3
The proof of Lemma 3 builds on the intermediate results that we present in the sequel. First, we derive the bound the estimation error in V Fr.. Using this result, we can bound the estimation in the fairness gradients derived in Equation 5.
For simplicity of notation, in the subsequent proof, we denote input instances from different demo- graphic groups as X; ~ p(xla 0) and Xj p(x(a = 1). With a slight abuse of notation, we also the indices i indicate the time step which the instance x; arrives.
Lemma 4 (Estimation error V.Fi)- Under assumptions (A7), (A2), (A3), (A4), the estimation error of Fij is bounded as: Fij v.G.gl S min (B/4, 2gg R).
Proof. Next, we focus on approximating the estimation error in V Fig.
Vi E. (n((,, x E,( V..,, F. Vn E.(
Similarly, we can estimate the approximation enror as:
VFg f = E. h/tp::/))|_aaaaa.ooa/33/////////
- -x.
E, (n,
- =n((),
< E, x)) - Vn(O,, + EE[Vn(O, x,) vn(e,,,))]
L,E,[] 0.1l + L,E,, 6,11
L,E, - 0
R.yR,
18

---

Published as a conference paper at ICLR 2024
where Lg is the smoothness constant of the activation function. Note that this error bound doesn't t increase in an unrestricted manner as the node gradients are bounded as:
[n E ||x|/4 & B/4.
Therefore, we can derive a tighter bound as:
VFF - VFil S min
{ B
4 21 R
For sigmoid activation, can plug Lg 2v3-3 in the above equation get the exact bound.
Using the bounds derived in the above lemmas, we proceed towards the proof of Lemma 3.
Proof of Lemma 3. We begin by noting that the task loss gradients are unbiased as the input instance X2 is sampled in an i.d. fashion making the gradient estimate unbiased on expectation.
(oHo((F)) VoHo(FF))1 || VeF.s - Fi 8llsgn 6/2) VaFy sgn (f 6/2) Vo FoFulll
if v/
<
otherwise
Therefore, the approximation error arises from the fairness gradient terms. First, consider the approximation error in the gradients when Figl S 5. It can be written as:
- -
S - v S 8B/4
Note that in the above equation, we consider the weaker upper bound for the estimation error of VFi of B/4. As the bound on the input ||||| < B is easier to work with. Next, we consider the case where Fryl > 8:
sgn (Fi - 8/2) sgn(F., 6/2) $ S 6B/2.
Therefore, we observe that the overall error can be bounded as:
(VeH((FF)) - (aHa(FF))) - 6B/2.
(13)
A.5 PROOF OF THEOREM
Theorem (Precise Statement of Theorem 1). Using the assumptions (A1), (A2), (A3), (A4), (A5),
for > the expected gradient norm VT 1/T BIIC()))1 can be bounded VT S
(e + 2 B2) for
4FL(M +
4FLO² e2
T> max
and 7 < min
(14)
(MLL 2L
where == [0.) Cs with C. denoting the overall loss function (Equation 4).
Proof. Due to estimation errors in the online setting, the gradients we use are biased and can be written as:
Ō(O,E) = G(e) M()) n())
(15)
19

---

Published as a conference paper at ICLR 2024
where G(@) is the exact gradient (computed using all the input instances seen far), b( is the bias or estimation error, and n({) is the noise coming from the i..d. estimate of the loss function. From Lemma 3, we can bound the overall estimation bias as:
| S A (F))) VoH, S2 5-
2
(16)
Vi.j
and ri(E) has zero mean. We assume that the noise n({) is (M, bounded as defined by Ajalloeian & Stich (2020). Note that M depends the task loss function [(.;)) and is not function of t. We
use the result from Lemma 2 (Ajalloeian & Stich, 2020) to obtain:
2F T7
T S
22
(17)
where we denote the average gradient norm as: VT + + [[IG())))) [0)]
f with L. denoting the overall loss function, and y is the step size. We assume that Lo has smoothness constant of L.
Then, for e > 0 we can show that the expected gradient norm converges as follows:
T S
B² = 2 B².
(18)
for large enough time step (or input samples) and small enough step size:
4FL(M +
4FLo²
T 2 max
and 7 S min
(19)
2²
(M 1)L' 2L
which completes the proof.
Discussion. Theorem 2 shows that the convergence of the gradient norms depends exponentially on the tree depth, O(22%). However, we used shallow trees (h S 10) and observed that shallow trees provide good securacy-fairmes tradeoff. In Appendix E. empirically study the gradient norm at the end of online training and how it varies with the tree height. Surprisingly, we observe a linear correlation between the gradient norm and the tree height for small h 10. The experiment yielded consistently small gradient norms that had no discernible impact on the final accuracy or DP results, which shows that the gradient estimation process works in practice. Theoretically explaining this phenomenon for small h is non-trivial and we leave it for future works to explore this result.
A.6 ADDITIONAL. THFORETICAL ANALYSIS
In this section, we provide additional theoretical results analyzing the properties of Aranyani. Specifically, we derive the gradient bound for G(@) (Equation 5) and show the oblique decision trees are K -ipsshhht continuous and -mmooh..
Lemma 5 (Bounded gradients). Under assumptions (AI), (A3), (A6), and activation function g(-) is sigmoid function the gradients are bounded as:
[[G(O]| < K, 2 268B,
(20)
where 8 is the Huber parameter and X is hyperparameter (Equaatin 5).
Proof. Using Equation 5, the gradient bound can be written as:
20

---

Published as a conference paper at ICLR 2024
[G( S max [IV2LF()))))1
I H (H
Vi.j
$ Kg + A
max
(1
(21)
Vi.j
$ K2 A6
max VFyll
Vi.j
$ K, + A62 max
E Vig (x/aa 0)] - E E|Vn,y 1)]l
I K, + A62 max
E Vnn (x|a 0)]l
= K2 + A62h max [[| (x|a = 0) - miy (xla 0))x
(22)
S K2 + A52 max || (x|a (1 -nij(x(aa 0))
K2 2 A8B.
In Equation 21, the first term is upper bounded by 5 VFF because the gradient is selected only when |Figl & 8. The maxima in Equation 22 achieved when nxy(x) = 0.5. For cross-entropy loss with softmax, the upper bound can be derived by plugging in K, = /2:
|[G()]| S /2 + 2
(23)
Note that even though the gradient bound has exponential term (2,- in practice due param- eter isolation the gradients for individual node parameters have much lower bound as each tree node is only associated with single Fij constraint.
Lemma (Lipschitz Continuity Smoothness). Under assumptions (AI), (A3), f(x) Ks- Lipschitz and smooth, where K, 2hB and L, = 2hh4h(h 1)B2.
Proof. Using the mean value theorem, the Lipschitz constant of a function f(x) bounded by max V (x)]] Therefore, finding the upper bound the derivative is sufficient.
2h
f(x, = Σ
II
(x)0,
i= 5=1
2h
Vef(x, 0) = Σ
nxx (x) mx())) II
mx)(x)0,x 1,
i=1
km
2
0,x
4
2/
|011
i=
||||||
where ||@]] and ||x|| denote the maximum norm of parameters 8, and input x respectively. Next, plugging in the assumptions about the norm get the following:
Vef(x, () < 2h2 Ky.
Similarly, we can derive the expression for the smoothness constant Ly. Using the mean value theorem, know that /x, θ)1 < T,g. Therefore, we derive an upper bound for the former:
21

---

Published as a conference paper at ICLR 2024
2h ()
n (x) (xx(x)) 2n
II (x)(x)0,²
2
h
n.((x) - mx)(
Σ
nim (x) nim (x))
II
nx)(x)),x²
<=1 k=1
m=1.ma
j= (R.m)
2"h
<
||]|||111 + 11hh - 1)2 |||0||01|| ||
6/3
S 2 4h(h + 1)|[0 ||
= hhh 1) = L.-
This completes the proof.
22

---

Published as a conference paper at ICLR 2024
B ADDITIONAL RELATED WORK
Aranyani uses gradient-based approach to learn the parameters of an oblique decision tree. this section, we discuss prior works that utilized decision trees in the online learning setting.
Decision Trees. Decision trees have been studied for the online setting where data arrives in stream over time, particularly to mitigate catastrophic forgetting (Kirkpatrick al., 2017). Initial works (Kamiran et al., 2010; Raff et al., 2018; Aghaei et al., 2019) explored various formulations of the splitting criterion to improve fairness in decision trees within the offline setting. More recent work (Zhang& & Ntoutsi, 2019) in fair online learning leveraged Hoeffding trees (Domingos Hul- ten, 2000) to process online data streams, and introduced group fairnsss constraints in its splitting criteria. However, this approach has several drawbacks: (a) conventional decision trees can only function with axis-aligned data making unsuitable for more complex data domains like text im- ages, (b) it cannot be trained using gradient descent making it difficult to plug in additional modules like text image encoder. In contrast to these approaches, Aranyani leverages oblique decision trees parameterized by neural networks improving its expressiveness while making it amenable to gradient-based updates using modern accelerators. Aranyani exploits its tree structure to store ag- gregate statistics of the local node outputs to compute the fairness gradients without requiring it to store additional samples.
"The name of our approach was inspired by the Hindu goddess of forests and wild animals. Aranyani. She fearlessly navigated the wilderness, treating humans and animals equally. These characteristics hear resem- blance to the desired traits of system, which must be fair and functional in the wild (online settings).
23

---

Published as a conference paper at ICLR 2024
C EXTENSIONS OF Aranyani
In this section, we discuss several ways to extend Aranyani to handle non- non-binary protected attribute labels or different notions of group fairness objectives.
C.I HANDLING DIFFERENT NOTIONS OF GROUP FAIRNESS
In this section, show that Aranyani be used to impose different notions of group fairness. Specifically, we derive the fairness constraints in Aranyani for the group fairness notion of equalized odds (Hardt et al., 2016). However, note that Aranyani be extended handle any conditional moment-based group faimess loss. For equalized odds, the node-level constraints can be shown as:
Fij = Elne(xxl = e, = 0)] [[[ny c, a = 1)];
where e denotes different task labels. The objective the offline setup is formulated as:
min (((())))) +
ΣV 1
Hs(
The gradient estimation in the online setting requires the storage of the following aggregate esti- mates: (a) E[m;y(x/) (xly - 1, 0)]. (b) E[Ven, 1 C, = 0)]. (c) Ex = C, a = 1)]. and 1}. This would result in an overall storage cost of O(2 Cd), where d is the dimension of the input x and C' is the number of task labels. Similarly, Aranyani can be extended to handle other group fairness notions like equality of opportunity (Hardt et al., 2016), and representation parity (Hashimoto et al., 2018) as well. We report initial results with the equality of opportunity fairness notion in Appendix E.
(d) E Veny (xly c, = 1)1. 14 {O.....
C.2 HANDLING BON-BINARY PROTECTED ATTRIBUTES
In this section, we show how Aranyani can be extended to process protected attributes with more than two labels. Let us assume the protected label {O..... - 1}. In this case, the fairness loss is defined as the difference between the expected overall output and the expected output for specific protected group as shown below:
F = Bi:Enn (x) - (x/a = k:)].
The modified objective in the offline setup needs to consider the difference for every protected label k. It is shown below:
min C(f(x), + + (F( AJ &
(24)
To extend this online setting. where aggregate statistics maintained, we need main- tain the following expectations: (a) E|ng (x)]. (b) [[Ven; (c) E|me((x(a k)], and (d) ViVeny((Xee = k)], Vk. This would result in an overall storage cost of O(2h Kd), where the dimension of the input and K is the number of protected classes.
24

---

Published as a conference paper at ICLR 2024
D IMPLEMENTATION DETAILS
In this section, we describe the implementation details of the experimental setup, baselines, and training procedure.
Dataset
Size
Split (3)
Split (a)
Adult
32.5K
75.9/24.1
66.9/33.1
Census
199.5K
93.8/6.2
52.1/47.9
COMPAS
7.2K
52.0/48.0
66.0/34.0
CelebA
202.6K
85.2/14.8
58.3/41.7
CivilComments
33.9K
93.4/6.6
76.6/23.4
Table I: Dataset Statistics. We report the number samples (size) used during online training and the percentage splits of the binary task (y) and protected attribute (a) respectively.
D.1 SETUP
We perform our experiments using the TensorFlow (Abadi et al., 2015) framework. We select the hyperparameters of the different models by performing a grid search using Weights & Biases li- brary (Biewald, 2020). To compute the accuracy-faine of X's and report the performance of all runs in the trade-off plots. We retrieve the text and image representations from Instructor and CLIP models respectively using the HuggingFace library (Wolf et al., 2020). All experiments involving Aranyani 2015) optimizer with a learning rate of 2 x 10 and Huber parameter 5 = 0.01. As the primary task classification in all datasets, we use cross-entropy loss as the task loss, L(:-)- For line learning, the model is evaluated with every incoming input instance. Therefore, we perform evaluation the training set of each dataset, except for COMPAS and CelebA, where both the training and test set were used for online learning. We report the dataset statistics in Table 1. We report the percentage of the majority label versus the minority label (Split) in the table for all of our datasets as they have binary task and protected label.
tradeoff, we run Aranyani on a wide range
optimized using an Adam (Kingma & Ba,
D.2 BASELINES
We describe the details of the baseline approaches used in our experiments.
O Aranyani MLP. This is variant of Aranyani, where the model f(x) is replaced by an MLP network. We use a two-layer neural network with ReLU non-linearity to parameterize the MLP. The parameters of the MLP are: W1 Rdxm B1 R" W₂ E Rx B2 R where is the input dimension, m is the hidden dimension, and e is the number of output class labels (c = for regression). To compute the gradient estimates in the online setting, the following aggregate statistics are maintained: (a) E V w. f(xla k)]. (b) E V f(xla k)). (c) E fx k)), (d) B (x|a k)), and (e) [
k)] for all E {0, 1). Note that the derivates are computed w.r.t. the final decisions of the MLP network fx),, as there are local decisions. These aggregate statistics are used to compute the gradients of the form shown below:
G())= vo[(((x)) + (V)H;(()), +
where F (xf(x(a 0)] Exf(x 1)].
In the above equation, we note that there is a single faimeess term as the group fairness constraint can only be defined on the final prediction, fxx).
4 Aranyani Leaf. This is similar variant of Aranyani as described above, where we use the pro- posed oblique forests and apply faimesss constraints to the final prediction. Therefore, the group fairness constraint can be applied at the leaf probabilities, px(x) = I ni.A(i,) (x), as the predic- tion takes the following form:
25

---

Published as a conference paper at ICLR 2024
If(x|a 0) f(x(a= = 1)
[(i((xa==)) -) 1))01)
h
Σ (i,A( 0) (4.,A(i.)((/aa -) 0:
Σ
II An,
II ALL 110111-
The above expression provides an upper bound that allows to define leaf-level faimess constraints:
F II (..A(C.)) 0) II n. AL..) 11
This can be used to define the fairness gradient formulation in the online setting:
G(@) = Ve((((x), + > VoHs(Fi)
Similar to MLP gradients, the above gradients be computed in the online setting by maintaining aggregate statistics of derivates of parameters w.r.t. the leaf-level probabilities.
AHT-based baselines do obtain good accuracy- fairness tradeoffs as they do not consider fairness at all. Note that we directly report the FAHT > results for Adult and Census presented in the original paper, the public implementation' and replicate the results. Since the original paper reports results only on tabular data, we could not report the results on CivilComments or CelebA. However, as HT's are not able to fit the data properly (or all) on CivilComments or CelebA datasets, incorporating additional fairness constraints would not have improved the results.
Hoeffding Tree-based Methods. In general, simple HT
could not run
D.3 TRAINING PROCEDURE
In this section, we provide more details about the training process presented in Section 3.4. First, discuss the formulation of the mask used to select the node probabilities for a leaf. We have access to N E Rm=x22 which stores copy of the node decisions (as column) for each leaf. There are 2 leaves and m = 2 1 node decisions. Using the mask A, we wish to select the node decisions needed to compute each leaf probability. For example, consider the mask for tree with height 2, which has 4 leaves (number columns) and internal nodes (number of rows):
1 -1 0
A =
1
Now let us consider the probability of reaching the second leaf of the tree involves node decisions of the root (index 0) and leftmost node of the first level (index 1). The highlighted column in the above equation selects the desired nodes. Note the mask entry takes the value when the leaf can
be reached by choosing the left path from the node, -1 when the leaf is reachable from the right, and when the leaf unreachable from the node. For trees with different height h, the entries of A can be derived using the following general form:
1, if (h-
+ 2(100 2(h-1-1)
A; = 1, if 12 2(hh-) < 2h +j < 2th 1) + ((h-1))
0, otherwise.
26

---

Published as a conference paper at ICLR 2024
Algorithm Aranyani Online Learning Algorithm
Input: Oblique tree with parameters W, B.
2: for E {0, ] do
3:
Ca =0 set the sample count for label
4:
!/ aggregate node outputs and their gradients for label a
5:
Na 0 VwN, = 0mxd, VBN, Om where m 2
6: end for
7: // Begin online learning
8: for X2 X' do
9:
Get the prediction as described in Section 3.4.
10:
N g( (WTx, +B)
11:
D = cxp (1ixm log P)e
Access true labels (y, a) after prediction
13:
Ca = Ca + // Update the counts
Update the aggregate statistics
15:
+ N/cc N. = N (1 1/c,) + WWNNca Vw.N, V
17:
VBN, NB 1/ea) + BBN/ca
Update the aggregate statistics No N N, E Rm
19:
20:
Vw.ww V. VWN1 Rm
21:
VB = VBN, - VBN E R
22:
Update the parameters using gradients from Equation 5
23:
W = W Vw + AVwHs(F)
24:
B B= B VBC(U,)) AV
25:
θ - - -
end for
where 1 logg (1 + 1)]. Using the above mask A, we can compute f(x) efficiently and train using autograd libraries via backpropagation.
We also provide an outline Aranyani's online training algorithm in Algorithm 1. This algorithm showcases how Aranyani can be trained efficiently. The faireess gradients for all nodes are computed simultaneously using matrices of aggregate statistics (Na, VN.). The task gradients VL(.,) are efficiently using standard autograd libraries.
27

---

Published as a conference paper at ICLR 2024
E ADDITIONAL EXPERIMENTS
In this section, we provide the details of additional experiments we perform to analyze the perfor- mance of Aranyani.
Ablations with A. In this experiment, we perform ablations by varying the À parameter (Equation 5), which allows us control the accuracy-fairnes, trade-off. In Figure 5, report the accuracy and DP scores on the Adult dataset during online learning. We observe that increasing À results in lower accuracy and improved DP consistently throughout the training process. This shows that Aranyani presents general framework that allows the user to control accuracy-fairees fairness trade-offs using X.
Am0.5
Accuracy
0.80
1=10
5-500
0.75
A= 10.0
0.60
0
5900
10000
15i0e 20000 25000 30036
0.0g 5000 10000
15000 2000e 25000 39000 Iterations
Iterations
Figure 5: Ablations with different We observe that increasing À results lower accuracy and improved DP scores consistently throughout the online learning process.
Tree Ablations. In this experiment, we perform ablation experiments to investigate the impact of the number of trees in the oblique forest on the accuracy- trade-off. In Figure 6, we report the change in average accuracy and demographic parity achieved during the online learning process in Adult dataset, when the number trees in Aranyani is increased. this experiment, we set the hyperparameter À 0.1. We observe gradual decrease in accuracy (Figure 6 (left)) when the number of trees is increased, which can potentially result from overfitting. In a similar trend, we observe improvement in the demographic parity (Figure 6 (right)), which is caused by the drop in accuracy due to overfitting. We report the results over 5 different runs for each setting. The error bars in the plots illustrate the standard deviation within each of the settings. We observe that the standard deviation (in Accuracy and DP) gradually decreases with an increased tree count.
83.2
0.125
82.8
0.120
82.6
0.115
0.110
82.2
0.105
82.0
0.100
0.095
10 Number of Trees
6
12
6
10 14
Number of Trees
Figure 6: Ablation experiment with a varying number of trees, [7, in the oblique forest of Aranyani. We observe slight drop in accuracy and consistent drop in demographic parity when the number of trees used in Aranyani is increased.
Gradient Convergence. this experiment, we investigate the convergence of fairness gradients (derived in Equation 5). We perform experiments on CivilComments dataset and report the gradient norms for node parameters (W, B) in Figure (left center). The y-axis in the figure is in log- scale for better visibility. We observe that the fairness gradients for both parameters converge over time and it is well correlated with the demographic parity the decisions during online learning.
In Figure 7 (right), we study the gradient convergence bounds predicted by Theorem 2. Specifically, we try to understand how the fairness gradient norm varies as a function of the tree height. We observe a linear correlation between the magnitude of the fairness gradient norm and the height of the tree. However, in general, for small tree heights (h S 10), we observe that the gradient bound quite slow and doesn't impact the final demographie parity scores (which lie between ~ 0.05-0.07).
28

---

Published as a conference paper at ICLR 2024
2.005
$2"5
20-4
Gradient
10-2
Gradient
Gradient
0.003
13-4
16-
DP
DP
2.001
Faimess
Gradient IB)
0.000
15032
15020
Figure 7: Convergence of gradients on CivilComments dataset: (left & center) We show the evolu- tion of the gradient norms of the oblique parameters (W, B) and the demographic parity during the online training process. We observe that the fairness gradients converge along with demographic parity. (right) We report the norm the fairness gradients (for W) at the end of online training with different tree heights. We observe that the gradient magnitude is very small and there appears to be a linear correlation with tree height.
0.5
60
Acturacy
0.4
40
0.3
0.2
0.0
10
10a
10"
Iterations
Iterations
Figure 8: Variation in the Accuracy and DP scores during online learning using Aranyani on the Adult dataset. The r-axis shown lcglscale. We observe that most of the variance is concentrated in the initial parts of the training process.
Performance Variance. In this experiment, we investigate the variance in performance during the training process. We perform online learning using Aranyani on Adult dataset using different seeds. In Figure 8, we report the average Accuracy and DP scores during online learning. The standard deviation for each metric is highlighted in light red. Note that æ-axis shown in log scale to observe the variance in performance clearly. We observe that most of the variation in metric concentrated the initial parts of the training process. We observe a minimal variance in the scores after a small number of around 1000 iterations. This showcases the robustness of Aranyani during the online learning process.
50
100
100
95
50
Accuracy (%6
90
(%)
90
85
85
Accuracy
80
0
12
A- 0.3
0.3
18
A 10
2-10 10
10K
15K
20K
25K
30K
5K 10K
15K
20K
25K
30K
DP
Iterations
Iterations
Figure 9: Performance of Aranyani with an adversarial stream of data on the Adult dataset. Left: We report the Accuracy vs. DP tradeoff for Adult dataset with adversarial stream. Right: We report the accuracy Aranyani during the online learning process for different X. observe significant dip in accuracy when the minority class is introduced.
Adversaiial Stream. In this experiment, we investigate the robustness of Aranyani in the advent of an adversarial stream of samples. We experiment on the Adult dataset and construct an adversarial online stream in two different ways: (a) In the first stream, present Aranyani with 90% of the majority class samples, followed by all samples of the minority class, and then the remaining 10% of the majority class samples. In Figure 9 (left), report accuracy DP tradeoff and observe that
29

---

Published as a conference paper at ICLR 2024
82
Accuracy (%%)
02
Accuracy
Accuracy
80
56
75-
Majority
Aranyani
78
MLP
52
HT
Aranyani (Update y1
Majority
0.18 0.15 0.13 0:10 0.09 0,85 0.0
0.00
0.40
0.35
0.30
0.25
0.20
9.15
0.30
0.20
9.15
0.10
0.05
0.00
EO
DP
Figure 10: (Left) Performance of Aranyani under limited feedback where the model is updated only when the prediction ò = 1. (Center) Performance of Aranyani under the equality of opportunity fairness constraint. (Right) Performance of Aranyani in the batch setting where 10 instances encountered at each time step.
Aranyani performs significantly better than the strong majority baseline. In Figure 9 (Center), report the accuracy achieved by Aranyani during the online learning process. We observe a sharp dip in accuracy when the minority class is introduced, which is expected. The accuracy improves towards the end and results using different À values show that the accuracy can be controlled using it. (b) In the second stream, we follow the same procedure as in the first one but replace the majority class samples with the minority ones. In Figure 9 (Right), we observe similar dip in accuracy when the majority class is introduced but the performance gradually improves over time.
Overall, this experiment shows that Aranyani is susceptible to adversarial data streams like any other ML system. However, our results show that even in such cases the user can control the fairness- accuracy tradeoff.
Limited Feedback. In this experiment, we explore scenarios where Aranyani conditionally receives feedback. Specifically, during online training Aranyani receives feedback from the environment only when its prediction, ÿ = 1. Figure 10 (left), we report the performance of Aranyani on the COMPAS dataset. We observe that Arunyani achieves similar tradeoff curves but it is unable to achieve high accuracies for a similar set of A's compared to when full feedback provided. This is expected as the system is unable to get feedback for many of the input samples.
Equality Opportunity. In this experiment, we evaluate the efficacy of Aranyani for the fairness notion of equality of opportunity (EO). For equality of opportunity, the node-level constraint is:
E [2. x 1, 0)] E[n., (xly 1, 1)].
We report the accuracy vs HO results Figure 10 (center). We observe that Aranyani achieves a much better trade-off than the strong majority baseline. This showcases the efficacy of Aranyani while using different fairness measures.
Batch Learning. In this experiment, analyze the performance of Aranyani in the batch setting where we present the system with 10 input instances at each time step. We report the results in Figure 10 (right). We observe trends similar to the online learning setting with Aranyani achieving the best fairness-utility tradcoffs. This shows the efficacy of Aranyani even when input instances are introduced in a batch-wise manner.
Method Runtime Analysis. We empirically analyze the runtime of Aranyani and other baseline approaches on the Adult dataset. We report the total time to process stream 32K samples in Table We observe that Ho- effding tree-based approaches are the fastest they do not require any gradient propagation. Among the variants of Aranyani, Aranyani (MLP) achieves the fastest runtime as it requires faimess gradient computation only w.r.t. the final network output.
Runtime (min)
HT AHT Aranyani
5.07
input
5.67
32,97
Aranyani (MLP)
14.65
Aranyani (Leaf) 37.12
Table 2: Runtime of different online fairness mitigation approaches.
Regularizer Ablation. We investigate the performance of Aranyani with regularizers different from the Huber function. Specifically, we foeus the I.2 norm regularizer. For using 1.2-norm in
30

---

Published as a conference paper at ICLR 2024
Ma Aranyani
813
52
L2 Loss
A. A
Accuracy (86)
82-
Accuracy (%%
77.5
54
Accuracy
01
72.5
80% Data
80% Data
67.5
Aranyani
0.20 0.30 0.36
D.14 0.32 0.30 9.58 0.06
0.04
0.15 0.15 0.15 0.19
0.58 0.05 0.00
0.50
6.29 0.15
0.15
0.32 0.10
0.08
0.00
0.05
DP
DP
Figure 11: (Left) Performance of Aranyani using L2 regularization for the node constraints Fig in Adult. (Center) Ablation experiment to investigate the performance of Aranyani under a limited data regime on the COMPAS dataset. (Right) Comparison of Aranyani with stochastic batch fair learning technique, FERMI.
100
30
A=0.1
A
82
90
Accuracy (%)
80
70
0.1
60
Aranyari
50
5K
10K 15K
lterations
20K
25K
30K
0.0
5K
10K 15K Iterations
20K
25K
30K
0.30
0.25
Majofit
0.20
6.15
0.10
0.05
0.00
Figure 12: (Left & Center) Evaluation of Aranyani on an unseen held-out validation set during online learning. We observe that the accuracy score improves consistently while there variance in the DP scores. (Right) Convergence of the tradeoff curve over training iterations (shown in colors) during online learning.
the online setup, the fairness gradient can be written as = (left), we report the results of this setup on the Adult dataset. We observe that Aranyani using L.2 regularization achieves similar fairness-accuracy tradeoffs. However, it is unable to reduce the DP scores beyond certain extent. We hypothesize that this phenomenon happens the approximation error for L2 gradients is large, which eventually hinders the convergence of fairness gradients.
In Figure 11
Dataset Size Ablation. In this experiment, we aim to investigate the impact the performance of Aranyani when exposed to varying fractions of data during online learning. In Figure 11 (center), we report the results of this experiment tradeoff gradually deteriorates with a decreasing amount of data. In particular, we note that Aranyani fails to attain higher accuracies, anticipated due the reduced size of the training data.
the COMPAS dataset. We observe that the faimess accuracy
Comparison with Batch Techniques. In this experiment, we compare Aranyani's performance with the stochastic batch-based fair learning method, FERMI (Lowy al., 2022). which is the only fairness algorithm we are aware of that can be applied with a batch size of 1. In Figure 11, we report the fairness-accuracy tradeoff for Aranyani and FERMI. We observe that Aranyani achieves much accuracy tradeoff than FERMI in the online setting with a batch size of 1. Aranyani can consistently beat FERMI across different values of X. Contemporary work (Baharlouei al., 2024) proposed algorithms to make stochastic versions of offline algorithms amenable to small batch sizes. Future works can investigate the performance of such algorithms in online settings.
better aairuess-accuracy
Temporal Analysis. Inspired by the notion of faimess in hindsight (Gupta & Kamble, 2021), we try to evaluate how the fairness Aranyani varies over time. In the online setting (described in Section 3.1), the system is evaluated on each incoming Aranyani a more absolute setting, we select 10% of Adult's data as a held-out validation set. We measure the faimess (DP) and utility (Accuracy) over time. In Figure 12 (left & center), observe a gradual improvement in accuracy scores over time and there a slightly higher variance in the DP scores. However, find that there it is still possible control the fairness-ule utility tradeoff using X.
sample. To evaluate the faimess of
31

---

Published as a conference paper at ICLR 2024
Tradeoff Convergence. In this experiment, investigate the convergence of the fairness-utillts tradeoff achieved by Aranyani during the online learning process. Specifically, we plot the DP and accuracy scores a held-out validation set attained by Aranyani at each iteration. In Figure 12 (right) we observe that gradually improves over time and the performance leans slightly more to- wards the accuracy at the end. The color of each point indicates the iteration when that tradeoff was achieved. We also plot the convergence curve for the Majority baseline and observe that Aranyani consistently outperforms it during the training process.
32


Reviews:
[{"review_id": "b64Hlm8Zx1", "reviewer": "Reviewer_9Pu9", "summary": "This paper explores the application of an existing machine learning model to improve group-level fairness performance in an online data streaming setting. Specifically, the authors work in a setting where individual data points arrive at the predictive system one after another over time. Given this setting, the authors deploy a predictive algorithm based on an oblique decision forest. The paper shows how to incorporate group fairness notions such as demographic parity while ensuring efficient training of the forest-based model online. The authors use real-world datasets ranging from tabular to vision and language to highlight the efficacy of their method.", "questions": "1. The authors showed how to implement a binary oblique decision tree. However, is it possible to formulate a non-binary version of oblique trees for fairness? Are there any scenarios that may necessitate non-binary splits in the tree?\n2. The scenario considered exposes the ground-truth label of an individual data point after the prediction is made, irrespective of the predicted label. However, in many real-world online decision-making settings, the ground-truth label is observed **only** when the prediction/decision is positive [1, 2, 3], e.g., in the COMPAS recidivism setting. This is the selective labeling scenario that reflects the real world more. Can the method be applied when true labels are not observed when the prediction is negative?\n3. Instead of considering a tree-based structuring across the nodes, can we train a GNN where each node's representation is learned from the features? Would it be possible to apply similar tricks to optimize for the problem?\n4. Temporal aspects of fairness can have many different meanings. While the expected fairness across different time steps is one measure, there can be other measures, e.g., fairness in hindsight. Can Aranyani be modified to work for such temporal notions?\n5. What does the variance of the fairness look like during the online training across the time steps? Does the fairness measure change a lot from one time step to another? Is it stable, or does it reach a stable state relatively soon? Similarly, what does the accuracy nature look like over time?\n6. Why does tree depth impact the fairness variance so much? Similarly, moving from a tree to a forest should reduce variance. But, from Fig. 6, an apparent relationship is not clear. In some cases, it seems that having a forest increases the variance. Do the authors have a thought about this behavior?\n5. How would the method compare to bandit-based solutions? Bandits seem well suited to the single-datum online setup discussed here, where the bandit can observe the true label no matter the decision.\n6. If we start moving away from the one datum at a time setup and consider multiple data points arriving at each time step, would the efficacy of the oblique tree reduce compared to other methods, e.g., MLPs?\n\n[1] Kilbertus, Niki, et al. \"Fair decisions despite imperfect predictions.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2020.\n\n[2] Rateike, Miriam, et al. \"Don’t throw it away! the utility of unlabeled data in fair decision making.\" Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency. 2022.\n\n[3] Wick, Michael, and Jean-Baptiste Tristan. \"Unlocking fairness: a trade-off revisited.\" Advances in neural information processing systems 32 (2019).", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors propose a novel application of oblique decision trees in the online group fairness setting. I believe the paper has several strengths.\n\nThe work is original as it explores the novel application of oblique decision trees in the context of group-fair online predictions. In order to ensure predictions are accurate and fair in the online setting, the authors provide key insights and explore the novel adaptation of oblique decision trees for efficient training. They also introduce theoretical lemmas to help show the relationship of the complexity, fairness performance and the modeling choices, e.g., the depth of the tree.\n\nThe authors have presented a work of good quality. The paper provides extensive theoretical complexity analyses. In addition, the authors provide evaluations for demographic parity fairness on multiple modalities of data, e.g., tabular data, image data, and language data. The work also includes extensive ablation studies to empirically show the properties and behavior of the proposed method.\n\nThe authors do a good job in making the paper clear to read. The scenario is clearly defined, the intuitions clearly stated, and the modeling is explained in clear language and terms. The article was relatively easy to follow even without understanding of oblique decision trees.\n\nIn my opinion, the work can be significant in showing how to adapt a powerful tree-based model for online predictions with fairness as an important consideration. This is especially for tabular data where tree-based models have been shown to perform better. The authors' proposed model may prove to be an useful tool in the practitioner's toolbox for online predictive systems, especially where fairness is also important to consider.", "weaknesses": "In terms of weaknesses, I find the following points.\n* The evaluations only show demographic parity results. While the authors mention how to formulate Aranyani for other group-fairness notions, they provide no results to highlight how it would perform for notions also based on the true label, e.g., equalized odds or equal opportunity.\n* The results do not have error bars. So, it is difficult to compare different methods without taking into consideration the variance across different initialization. As far as I understand, Aranyani and the other baselines may not be guaranteed to find the global optimum. Hence, reporting the mean and the variance across different initialization is very important for fair comparison. \n* While the work measures and reports the expectation of the fairness measure at each time step, it is unclear what the fairness dynamic looks like for different methods across time as the training proceeds. In online settings, the variation of the fairness measure over time may tell a story and be essential to see. Specifically, it is not clear how the fairness measure **varies across different time steps**. It is not clear if the training process is relatively stable or not, and how Aranyani compares to the baselines in this respect.\n* As per the appendix results, the fairness result variance seems to increase significantly as we move from a single tree to a forest. The authors motivate the need for a forest instead of a tree with a promised reduction of variance. However, in some sense, it seems that variance can increase as well. This aspect does not seem to be discussed well.\n\n\nThere are a few minor points as well.\n* Figure 4 (right) includes error bars, but it is not clear how the variance is measured in this case. Is it the variance of a measure across time steps? It is not clear why the tree depth impacting the variance of fairness so greatly.\n* The fairness performance seems to degrade considerably when the tree depth is higher. This follows from the theoretical finding, where the fairness bound becomes looser as we increase the tree depth. However, this may limit the expressivity of the model in some situations.\n* There are no ablation studies that show the impact of the particular loss that is used to measure fairness, i.e., using Huber loss over $\\ell_2$ loss or hinge loss.\n* While the authors provide a complexity analysis for their method, an empirical runtime analysis comparing the different methods might have also been insightful.\n* Figure 4 (right) does not have any legend. It is difficult to understand which line/symbol corresponds to which metric.\n\nVery minor point.\n* The Aranyani triangle symbol in the text does not match with the plots.", "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": "bB4nACVVK6", "reviewer": "Reviewer_vgYA", "summary": "The authors propose a framework, Aranyani,  based on an ensemble of (soft) oblique decision trees to address group fairness in the online learning setting where one instance arrives at a time. This work proposes a method to update the oblique decision forests model that only relies on updating two aggregated statistics for each node    in the tree and each sensitive group (Section 3.3).  The authors provide a theoretical analysis (Section 4) of the proposed approach such as a bound on demographic parity (DP) based on the depth of the tree under the assumption that the fairness constraint is satisfied on each tree node. Moreover, they also show that the proposed approach to aggregate statistics in an online fashion guarantees gradient norm convergence with enough time steps. Finally, they provide experimental results showing that their approach achieves in general better or competing tradeoffs between accuracy and demographics parity.", "questions": "In addition to the questions in the weakness section I have some concerns about the practical scalability of this approach.  My understanding is that each time step a new oblique tree is generated, then, the final model can be considerably large. Have the authors thought how this can scale in practice?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well written, the problem is well motivated, and results are promising. I think one of the interesting aspects of the proposed approach, in addition to its online characteristics (no need to store previous data, no need to query the model multiple times), is that the group fairness objective (DP in this case) is being imposed at a local level (in each node). This may reduce the disparities in terms of DP across different regions of the input space. The theoretical analysis provided is reasonable, it motivates and provides some grounded guarantees on the proposed solution.", "weaknesses": "The weaknesses I see are summarized in the following questions:\n\nHow do you guarantee that in each leaf you have samples from both sensitive groups? From Eq.3 and Eq 5 I understand that $F_{i,j}$ requires examples from both sensitive groups. If this is not guaranteed in the solution, how do you deal with nodes containing samples from a single sensitive group?. How does this method scale with multiple groups?\n\nA discussion on $\\delta$ and $\\lambda$ parameters from Eq.4 should be provided. In particular, I think $\\lambda$ should be set based on $\\epsilon$ (DP constraint) from Eq 2, which is the fairness violation that the user is willing to accept. In general, I would have expected to maximize the $\\lambda$ parameter until that constrain is satisfied ($\\epsilon$). However, it seems that the Huber loss function is not zero when the epsilon constraint is satisfied. Why did you choose this approach to enforce the fairness constraint?\n\n\nI think the algorithm or a simplified pseudocode of the proposed framework should be provided. This would help with the understanding and reproducibility of the work since it summarizes the logic of the proposed approach.", "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": "Id5E09WKIA", "reviewer": "Reviewer_mq1x", "summary": "This paper introduces \"Aranyani,\" a novel framework designed to compute and enhance group fairness in online learning scenarios. The work is systematically presented, starting with foundational knowledge on oblique decision trees in Chapter 2. Chapter 3 delves into the problem formulation, detailing demographic parity equations for both offline and online settings. Within this chapter, the authors explain their choice of the Huber loss function, addressing the challenges inherent to online scenarios. Chapter 4 provides a comprehensive theoretical analysis of Aranyani, covering its expectations and assumptions. The experimental findings, presented in Chapter 5, benchmark Aranyani against prominent online learning algorithms.\n\nCentral to the paper is Aranyani's innovative approach to achieving fairness in online settings. Aranyani leverages an ensemble of oblique decision trees, which are capable of making nuanced oblique splits by utilizing routing functions that account for all input features. The authors begin by detailing an offline setting, constraining the objective function with a fairness objective (L1 norm), and then adapt this framework to oblique decision forests. Given the non-smooth and convex nature of the L1 norm, optimization challenges arise. The authors cleverly employ Huber Regularization to smoothen the L1 norm, paving the way for more effective optimization.\n\nWhat sets Aranyani apart is its approach to data storage. Traditional methods tend to store instances to train a model, whereas Aranyani calculates fairness gradients based on aggregated statistics from previous decisions, effectively handling the online situation.\n\nFrom a theoretical standpoint, the authors rigorously examine four fundamental properties of Aranyani: Demographic Parity (DP), Rademacher Complexity, Fairness Gradient Estimation, and Gradient Norm Convergence. Each of these properties is supported by robust theoretical proofs.\n\nTo validate their approach, the authors conduct experiments on five diverse datasets: UCI Adult, Census, COMPAS, CelebA, and CivilComments. Their results indicate that, in terms of the Fair-Accuracy trade-off, Aranyani outperforms existing online learning algorithms across most datasets. Notably, its performance on the COMPAS dataset was less dominant, warranting further investigation.", "questions": "\"In scenarios where the provided dataset is inherently imbalanced, does the definition of fairness shift? Could the fairness criteria evolve based on varying tasks and datasets? And how does the framework handle datasets that may already carry inherent biases? (This query extends broadly to research in the domain of fairness.)\"\n\nRegarding addressing some of the weaknesses:\n- Handling imbalanced or biased datasets is a nuanced challenge in fairness-related research. Proper preprocessing, data augmentation, or applying techniques like re-sampling can help. If Aranyani uses any such methodologies or has in-built mechanisms to counter these biases, it would be crucial to highlight.\n- Furthermore, explaining the adaptability of Aranyani in different scenarios, especially with datasets that are inherently biased, would provide clarity on its real-world applicability.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Significance: The proposed Aranyani framework has the potential to be a groundbreaking adjustment in online learning algorithms, paving the way for enhanced fairness in this domain.\n\nOriginality: This research stands out due to its unique experimental environment settings and the innovative adjustments made in the problem formulation. The paper presents a fresh perspective by introducing a new idea in the realm of online learning.\n\nQuality: While there are certain ambiguities, primarily concerning the linkage between foundational knowledge and experimental configurations, the paper's narrative is cohesively structured and of commendable quality. The meticulous mathematical proofs provided for each of the Aranyani properties add depth and credibility to the work.\n\nOther Notable Strengths: Aranyani's design, which negates the need to store individual data instances, is especially significant concerning data privacy. This approach not only addresses data storage challenges but also underscores the paper's emphasis on operating based on aggregate statistics rather than individual data points.", "weaknesses": "Methodological Clarity: \n- The manuscript would be enhanced with a more detailed breakdown of the concluding stages of the training process. It remains uncertain whether the oblique decision tree is designed as an end-to-end neural network or if Aranyani follows the training pattern of standard tree models while adopting a neural configuration.\n\nPerformance Insights & Recommendations: \n- It would be beneficial to have deeper insights regarding Aranyani's subdued performance on the COMPAS dataset. Could there be challenges in using Aranyani for datasets with less than 7k entries?\n- While the paper indicates that Aranyani is more suited to trees of limited height, it would be useful to explore alternative approaches for instances where greater tree height is needed.\n\nExperimental Enhancements: \n- Real-World Application: Observing Aranyani's functionality in intricate real-world situations, outside the realm of benchmark datasets, would add depth to the findings. \n- To further solidify the paper's comparative analysis, including more recent fairness representation learning models from the related works — modified for online environments — as baselines would be valuable.\n\nVisualization Feedback: In Figure 4 (right), legends are necessary to distinguish which line represents accuracy.", "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": "FfeaUJyWgM", "reviewer": "Reviewer_VSWz", "summary": "This paper proposes a method for achieving group fairness in online setting, equipped with fairness, accuracy, convergence analysis. Moreover, numerical experiments have been conducted for showing the great performance of the proposed method in terms of reducing the unfairness while maintaining the accuracy.", "questions": "1. Where is the FAHT’s result in the rightmost plot in Figure 2? \n2. Why is FAHT worse than the adaptive HT in terms of DP?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. This paper proposed an effective approach called Aranyani, and provide solid theoretical analysis for it. \n2. The experiment results look promising", "weaknesses": "1. [Major] The main use cases for achieving fairness in this online setting are missing. This issue makes the motivation of this work lack justification. \n2. [Major] Problem setting should be stated more clearly. For instance, in this paper, considers an online setting where only one single instance can be processed. Typical online learning indeed process one data point at a time but also privy to the feedback from previous data points, but this paper seems to assume that the previous data points are not available. A more clearly setup should be stated before getting into the gradients used in the algorithm (5). \n3. [Major] Authors do not clearly state the goal in the online setting. Can you add an equation like (3) to the online setting? I am not even sure what is the right fairness metric for online settings — at each step, are you measuring the fairness for the entire dataset?", "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": "sCZKkXxuMV", "reviewer": "Reviewer_uVjM", "summary": "This study introduces an online algorithm called Aranyani, aimed at addressing group fairness issues. This algorithm integrates a collection of oblique decision trees and leverages the tree's structural attributes to improve group fairness in online learning scenarios.\n\nFirstly, the study demonstrates that when group fairness constraints are applied to decisions at the local node level, it results in parameter isolation, paving the way for superior and more equitable outcomes.\n\nSecondly, by keeping track of the overall statistics of decisions made at the local node level, the algorithm can effectively calculate group fairness gradients, removing the requirement for extra storage for forward/backward passes.\n\nThirdly, the study offers a framework work for training Aranyani.\n\nLastly, both empirical and theoretical evidence provided in the study underscores the efficacy of the suggested algorithm.", "questions": "Questions are provided in the weakness section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* This study focuses on a unique and critical problem wherein machine learning fairness is examined in an online context, with individual sample instances observed sequentially.\n* In such a scenario, determining group fairness attributes and executing backward propagation to modify model parameters necessitates retaining all prior samples, leading to computational complexities. To address this, the paper introduces an effective framework for forward and backward propagations, taking advantage of statistical summaries from previous samples.\n* The presented algorithm consistently surpasses baseline techniques across all tasks. It is both empirically and theoretically robust and comprehensive.", "weaknesses": "* Utilizing the aggregate of past statistics to adjust the model parameters poses a challenge. As the model parameters shift with each time step, past statistics, derived from earlier model parameters, might diverge significantly from what would be obtained if the model gradients were calculated using all the previously stored data. I'm curious if the authors could elaborate on the conditions under which using aggregated past gradients to update the current model would be successful or not.\n* The problem is framed in an online setting where the actual predictive labels are seen after the model makes its predictions. More realistically, if the model consistently underperforms, it could result in a shift in data distribution. Specifically, the minority group might cease supplying data for model updates. Could the author discuss how the proposed algorithm would operate under these circumstances?", "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 (spotlight)