Long Term Fairness via Performative Distributionally Robust Optimization
Authors: Garnet Liam Peet-Pare
Nidhi Hegde
Alona Fyshe
Venue: Submitted to ICLR 2023 (2023)
Keywords: fairness
distributionally robust optimization
performative prediction
distribution shift

Abstract: Fairness researchers in machine learning (ML) have coalesced around several fairness criteria which provide formal definitions of what it means for an ML model to be fair. However, these criteria have some serious limitations. We identify four key shortcomings of these formal fairness criteria and address them by extending performative prediction to include a distributionally robust objective.  Performative prediction is a recent framework developed to understand the effects of when deploying model influences the distribution on which it is making predictions.  We prove a convergence result for our proposed repeated distributionally robust optimization (RDRO).  We further verify our results empirically and develop experiments to demonstrate the impact of using RDRO on learning fair ML models.

Under review as a conference paper at ICLR 2023
LONG TERM FAIRNESS VIA PERFORMATIVE DISTRI- BUTIONALLY ROBUST OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Fairness researchers in machine learning (ML) have coalesced around several fair- ness criteria which provide formal definitions of what means for an ML model be fair. However, these criteria have some serious limitations. We identify four key shortcomings of these formal fairness criteria and address them by extending performative prediction to include distributionally robust objective. Performa- tive prediction is a recent framework developed to understand the effects of when deploying model influences the distribution on which it is making predictions. We prove convergence result for our proposed repeated distributionally robust optimization (RDRO). We further verify our results empirically and develop ex- periments to demonstrate the impact of using RDRO on learning fair ML models.
INTRODUCTION
In the past two decades, machine learning (ML) has moved from the confines of research institutes and university laboratories to become deployed at enormous scales in complex environments, often making high stakes decision. Too often, however, this is done without adequate concern for the fairness and robustness of these ML models. Fairness in ML is burgeoning research area, but much of the work in fairness, particularly in defining formal fairness criteria, has been limited to the static classification setting.
element of the global economy. MI. models are now
Efforts to define fairness in ML have resulted in myriad criteria being proposed, many of which are equivalent to, or relaxations of, three core definitions of fairness: independence. separation, and sufficiency |Brocaas et al. (2019): Chouldechova (2017); Corbett-Davies et al. (2017): Dwork et al. (2012): Hardt et al. (2016b); Berk al. (2021); ): Zafar et al. (2017); Kleinberg et al. (2017): Wood- worth et al. (2017). These formal fairness criteria assume sensitive characteristic or protected demographic group for whom we want to ensure our model is non-discriminatory. The fairness
criteria then properties of the joint distribution of this characteristic, the output of the classifier, and the true labels of the data.
While these fairness definitions have been useful starting point in the consideration of discrimina- tion by ML models, they have several limitations. 1. They are not equivalent and, in most scenarios, they incompatible. 2. They apply only static supervised learning problems and ignore the dy- namic environments characteristic of many real world scenarios with fairness concerns. 3. They rely on having access demographic information. The definitions can only used if one has access to the sensitive characteristic, which is often not the case. 4. They ignore intersectionality. The criteria do take into account individuals who may sit at the intersection of several sensitive demographic groups. Fairness is fundamentally philosophical and political question, and the notion of having single, universal formal definition of fairness for ML is likely naive, For this reason, this work does not attempt to formally define fairess and largely ignores the first problem noted above. We do, however, attempt to address issues 2, 3, and 4 by drawing upon two recent areas of research with implications for fairness in ML: performative prediction and distributionally robust optimization (DRO).
DRO offers compelling and flexible method for training non-discriminatory algorithms without needing access to demographic information. Performative prediction, on the other hand, attempts to outline theoretical framework through which we reason about ML models in dynamic en- vironments, when the act of deploying a model influences the distribution on which making decisions.

---

Under review as a conference paper at ICLR 2023
We combine these two areas of research extend the performative prediction framework developed in Perdomo et al. (2220). The work in performative prediction has thus far only concerned risk minimizatiin and empirical risk minimization (ERM), extend definitions to include a distribu- tionally robust objective and prove an analogous convergence result to that shown in PPerdooo et al. (020). Due space constraints, we provide extended discussion of related work in section A. of the appendix.
BACKGROUND
2.1 DISTRIBUTIONALLY ROBUST OPTIMIZATION
The de facto objective used in most supervised learning settings is ERM. In ERM we attempt to approximate minimization of the expected loss over the data generating distribution by minimizing the average loss over our data set:
1 - Σ ((h(z)),
= arg min GEH To ==1
where It represents a hypothesis or model, H a hypothesis class, and l non-negative loss function. ERM is intuitively appealing and has important theoretical guarantees associated with it |apnik (1991). It can, however, be problematic when it comes to fairness concerns. Since we are averaging the loss over our data points, general, ERM causes an algorithm to focus on majority cases while ignoring minority cases or rare events.
DRO, on the other hand, considers the distributionally robust problem in which we construct an uncertainty sel around the data generating distribution and attempt to minimize the expected loss on the worst-case distribution within this uncertainty set. Following Duchi & Namkoong (202T) we
define our uncertainty set as
(P = (Q: (Q) p),
where P) is an f-divergence between probability distributions Q and P.
f
Formally the distributionally robust problem as follows:
sup [Eq[e(0; Q U, loeP
minimize BEB
where e C Rd is the parameter (model) space, Po is the data generating distribution the measure space (X, , X is a random element of X' and l θ x X' lk is a loss function.
In this formulation of DRO, the uncertainty set is determined by an f-divergence between Q and Po and (Eo](((0; X)]= Q E (P.)) is the set of all expected losses over the f-divergence ball of radius A. centred Po- Alternative DRO formulations utilizing different measures of distance between probability distributions such as Wasserstein balls have also been explored Wald (1945);
Wozabal 2012
Pilug& & Wozabal (007): Lee & Raginsky (2018)
Unlike ERM, DRO does not equally weight each data point, but instead up-weights data points on which the model is achieving high loss. This means that the model should achieve somewhat uniform performance on individuals across demographic groups Duchi & Namkoong (2021): Duchi al. (2020); Namkoong & Duchi (2016): Hashimoto et al.) (2018). Note that the distributionally robust objective does not require any access to demographic information and, at least potentially, naturally accounts for intersectionality.
One can optimize the distributionally robust objective directly via the primal form, specified above, or alternatively through a dual formulation. For convex losses, the dual form jointly convex the parameters of the model and the dual variables Duchi & Namkoong (2021). A detailed discussion of the dual formulation can be found in A.2 The dual formulation also helps provide intuition for why DRO is more likely to result in fair ML models.
2.2 PERFORMATIVE PREDICTION
Performative prediction attempts to formalize the notion a model affecting the distribution on which it is making predictions type of feedback loop. There many examples of scenarios with
2

---

Under review as a conference paper at ICLR 2023
fairmess concerns in which this is likely oceur, such as predictive policing college admission decisions.
This notion of performativity of an algorithm is captured by distribution map, D(0), which maps the data generating distribution to a new distribution as a function of the parameters of the model which has been deployed. In performative prediction, the problem of risk minimization becomes performative risk minimization and involves minimizing the expected loss on the induced distribu- tion rather than the data generating distribution. The performative risk of model is defined
PR(O) = ( 0)).
Solution concepts differ for performative prediction and traditional supervised learning, as the dis- tribution shift complicates the learning problem. To capture this distinctive problem, Perdomo et al. (2020) define performative optimality and performative stability.
Definition 2.1. (performative optimality) A model, fero is performatively optimal if the following relationship holds:
0 PO arg min ( (((o))))
0E
Equivalently, 8PO = arg m PR(O) where PR(0) is the performative risk defined above.
A performatively optimal point is minimizer of the performative risk. An alternative solution concept is referred to as performative stability.
Definition 2.2. (performative stability) model, Sêps is performatively stable if the following relationship holds:
0ps arg mig Di
Define DPR(0, 0') = 1(2; as the decoupled performative risk; then 0ps arg migge DPR(Ops.O).
A performatively stable model is not necessarily minimizer of the performative risk, but it is optimal on the distribution it induces.
Performative prediction presents special case of learning under distribution drift, where the distri- bution drift a function of the model that was deployed. A common approach in supervised learning under distribution drift is retrain model newly collected data. While this does not directly minimize performative risk, it is a realistic representation the strategy taken by many machine learning practitioners and can be a reasonable solution in some scenarios.
Definition 2.3. (repeated risk minimization) Repeated risk minimization (RRM) refers to the pro- cedure where, starting from an initial model fag, we perform the following sequence of updates for every / 2 0:
0.+1 = G(f,) == arg min [x=:
A5e
In Perdomo et (020)) the authors show that under certain smoothness and convexity conditions on the loss function and distribution map, RRM is contraction mapping that converges fixed point which is a performatively stable model. The smoothness condition on the distribution map called e-sensitivity and ensures that the distribution shift is relatively small for small changes in the model parameters. Section A.3 contains an extended discussion of performative prediction and formally defines all the relevant concepts.
3 CONVERGENCE OF REPEATED DISTRIBUTIONALLY ROBUST OPTIMIZATION
In order to extend the performative prediction framework to encompass DRO, we need to redefine many of the concepts from Perdomo al. (2020) to account for the distributionally robust objec- tive. The supremum over the uncertainty set introduces additional complications necessitating novel definitions and altered proof for convergence to performatively stable model. We define bust performative risk, robust performative optimality, robust performative stability, and repeated distributionally robust optimization (RDRO).
3

---

Under review as a conference paper at ICLR 2023
We begin by redefining performative risk and performatively optimal and stable models in terms of a robust objective. In the following D(0) is a distribution map and D(()) is an f-divergence ball of radius p.
Definition 3.1. (robust performative risk) The robust performative risk of model, 0, is
RPR(O) sup (Bx-ol((2:0] D s p). Q<D(())
Robust performative risk differs from performative risk in that the induced distribution, D(0), is now the centre of an f-divergence ball over which supremum of the expected loss is taken.
Definition 3.2. (robust performative optimality) A model foro is robustly performatively optimal the following relationship holds:
r arg min sup (Bz=o|[(2:0)) D)(Q)))(0) : s s
dee
QED((1)
Equivalently, OPO arg mingge RPR(() where RPR(0) is the robust performative risk as defined above.
Definition 3.3. (robust performative stability) A model fays robustly performatively stable if the following relationship holds:
0p arg min
sup QcD(Ops)
{E
s)
Define RDPR(O, 0') == supq (Ez-a D)(() s p} as the robust decoupled performative risk; then fp = arg gen RDPR(Ops,d) 6).
We discussed earlier that previous work has shown that repeated risk minimization converges to a performatively stable model under certain assumptions the loss and distribution map Perdomo et al. 2020). We can analogously define repeated distributionally robust optimization as follows.
Definition 3.4. (repeated distributionally robust optimization) Repeated distributionally robust op- timization (RDRO) refers the procedure where, starting from an initial model feo. we perform the following sequence of updates for every 2 0:
8++1 G(O,) = arg min sup (Ez~ol((z:0) D)(Q) s st.
8E
QED(O,)
As with RRM, this is an iterative procedure where we optimize the distributionally robust objective each time step l. While it only a small departure from RRM conceptually, the DRO objective has fundamentally different mathematical properties than risk minimization making it unclear whether RDRO and RRM should exhibit similar behaviour.
The assumptions the loss function and distribution map required for convergence of RRM do not suffice for RDRO, as the supremum over the uncertainty set alters the mathematical properties the robust objective. We adapt these conditions to extend them the distributionally robust objective. The original conditions from Perdomo et al. (2020) can be found in A.3
Definition 3.5. (robust B-joint smoothness) We say the distributionally robust objective is robustly --jointly smooth if for all 0' E O and z, E the gradient,
V sup (Ez~ol((z:0) Q (D())))) Q+1(
exists and is 9-Lipschitz in z and 0.
Definition 3.6. (robust 7-strong convexity) We say the distributionally robust objective is robustly --strongly convex if for all 0, 0' E O and E 2
sup (Ez~ql Q (D(()))) 2 ())(
is 7-strongly convex.
4

---

Under review as a conference paper at ICLR 2023
Definition 3.7. (robust e-sensitivity)
Let (0) = arg max.: (D(0) Ez (2==)((2;(0) Assume that a distribution map, D(-), is e- sensitive We say that this distribution map is robustly e-sensitive if there exists >> 0 such that for any 0,
Wi (D)))) ww (D(0), D(6)) S wc| 8'11.
where Wi denotes the Wasserstein-1 distance.
We now state our convergence theorem for DRO in the performative prediction setting. This the- orem says that under the conditions outlined above, repeatedly optimizing distributionally robust objective will converge to performatively stable model at a linear rate. The proof can be found in A.4
Theorem 3.8. Suppose that the distributionally robust objective satisfies definitions
3.5 and 3.6
and that the distribution map satisfies definition 3.7 Then the following statements are true:
1. ||G(B) G(0 S we wc 110 12. for all 0, 0,0'E6 E
2. If we < 3. the iterates O, of RDRO converge to unique robustly performatively stable
point 0ps at linear rate: |10, Psll2 s ffr (1-we log [00 Ops
Note that G(0) arg mingee sup (Ez~ol [ Q (D()))))
The proof of this theorem shows that RDRO is contraction mapping and is essentially applica- tion the Banach fixed point theorem. Definitions 3.6 3.5 and provide smoothness conditions for the mapping sufficient to ensure contraction.
The importance of this theorem is that it suggests that RDRO should exhibit similar convergence behaviour RRM. As discussed earlier, however, training models with ERM is liable to result in models which are discriminatory towards minority subgroups, while models trained with DRO should exhibit uniform performance across different subgroups. What this implies that RRM may converge to unfair fixed points, while RDRO should converge to fair fixed points.
4 EXPERIMENTS
We run experiments to empirically verify the convergence of RDRO as compared to RRM, as well as to demonstrate the utility of DRO in learning fair models in the presence of data characterized by majority and minority subgroups. Implementation details can be found in A.5
4.1 RRM AND RDRO ON CREDIT EXTENSION DECISIONS
For our first experiment we reproduce an experiment from Perdomo et al. 2020) using a credit ex- tension dataset from the Kaggle competition Give Me Some Credit. The dataset contains information about potential borrowers and the task is to predict whether or not an individual will default on their debt. We construct a distribution map by strategically manipulating individuals features in response to the deployed classifier Hardt et al. (2016)).
In order to add a performative element the prediction problem, we identify of the 10 features as strategic features which will be altered as function of the parameters of our model. Strategic classification particular instance of performative prediction in which individuals adversarially adjust their features to maximize the likelihood of classification to the positive class. Strategic classification has been explored relation fairness concems in previous work Hardt et. (2016a);
Bruckner et al. 2012); Miller et al. (2020); Milli et al. (2019): A'mourr et al. (2020); Hu et al. 2019).
As described in Perdomo et al. 2020) and Hardt et al. (2016a). we assume individuals have linear utilities u(0, x) = - - x)) and quadratic costs c(x', ,I) x'' - x x|E The constant controls
the cost individuals incur by altering their features. Individuals thus pay cost to manipulate their
The formal definition of e-sensitivity is given in A.3
5

---

Under review as a conference paper at ICLR 2023
ERM Theta Gaps
DRO Theta Gaps
10
10a
10a
0.1
0.1
10a
e:
10"
10
10.0
10"
100
10
100.0
10"
10
10
20
20
30
Iteration
é
Iteration
Figure Plot of the normalized distance be- tween successive values of 0 for ERM.
Figure 2:
Plot of the normalized distance be- tween successive values of 0 for DRO.
features in order to minimize the likelihood of the model predicting that they will default on their loan, but are unable to change the true outcome, y E {0, 1), of whether or not they default. Given linear utilities and quadratic costs as described here, the individuals' best response to manipulate their features
z's = 2g eBs.
where æs.''s r's R and |S] is the number of strategic features. The explanation of why this distribu- tion map e-sensitive can be found [Perdomo et al. (2020).
The procedure for updating the data according to the distribution map for strategic classification is explained in the box below.
Input: Base distribution P. a classifier So, a cost function c, utility function u. Sampling procedure for D()):
1. Sample (z, y) P
2. Compute best response ZBR + arg max, u(x',0) -c''', x)
3. Output sample (MAR, y)
We train two logistic regression models using RRM and RDRO. The magnitude of the distribution shift is controlled by a parameter, c. The larger the value of c, the larger the distribution shift. The c-sensitivity condition of the distribution map thus only satisfied for small values of c. Further details are given in A.6
Figures and contain the distance between the learned parameters the model on successive iter- ates. A distance of zero means that the model has converged to performatively stable point. These figures show us RRM and RDRO exhibit similar convergence behaviour. Both RRM and RDRO converge for 0.01, and RDRO also converges for 1.0. Both RRM and RDRO converge to small neighbourhoods for c = 10, while neither converge for e = 100. This result empirically sup- ports theoretical work, suggesting that RRM and RDRO exhibit similar convergence behaviour.
4.2 STATIC CLASSIFICATION WITH ERM AND DRO
The credit dataset does not contain any demographic information, so to investigate the fairness prop- erties of the fixed points resulting from RRM and RDRO we generate synthetic data, sampled from two multivariate normal distributions with different means. We refer to the majority sub-pnt sub-probability distribution as group A and the minority distribution as group B. Data from each individual distribu- tion is linearly separable, but the combined distribution is not, meaning that linear classifier must trade-off performance between the two subgroups.
To build intuition for the differing behaviour of ERM and DRO on classification task involving subgroups and fairness concerns, we first investigate a static classification scenario, before exploring long-term faimeess via performative prediction.

---

Under review as a conference paper at ICLR 2023
Our data is generated from bivariate Gaussian distributions and the label, y, of a given data point is if the sum of its features are greater than the sum of the means of the two Gaussian distributions from which we draw samples and 0 otherwise. We have two subgroups within our data, A and B. We vary the proportion of samples from each subgroup in the experiments. The exact data generating process is given in A.6
Although this dataset is extremely simple, it is characterized by a feature that represents a cen- tral concern for fairness in machine learning, namely that the conditional probability distributions, P(y]z), are significantly different for distinct subsets of the data. This example is intended to rep- resent a simplified abstract instance of a population with majority and minority subgroups in order to see how the behaviour of ERM and DRO differ in this cireumstance.
We generate three distinct datasets on which to train our algorithms, each made up of differing pro- portions of the two subgroups A and B. Each dataset contains a sample of 10,000 data points, with samples distributed according the values of C and cB. parameters which control the proportion of the data coming from each subgroup. The accuracy of the models on the three datasets is summa- rized in Tables 5) and 6 below. For both ERM and DRO we use 122regularized logistic regression trained with stochastic gradient descent. The step-size for all algorithms is fixed at 0.05 and we train for 15,000 epochs.
Models trained with the distributionally robust objective have the additional complication that must specify a value for the radius of the divdieergence ball, i.e. p. The larger the value of p. the more we can expect DRO model to differ from ERM model because as the divdeeegee ball grows, the worst case distribution can be further and further from the data generating distribution. Conversely, in the limit as p + O, we recover ERM as the diveieegee ball shrinks contain only the data generating distribution.
Choosing the value of p is challenging decision, as the performance of a model varies significantly as p changes. If one has access to demographic information, it is possible to conduct grid search over possible o values in order to find a value that results in a model with the desirable fairness properties. Doing this, however, largely defeats the purpose of DRO. As explained earlier, a central advantage to using DRO, rather than some fairness constrained optimization technique, is that DRO does not require access to demographic information.
In this experiment we work directly with the dual formulation of DRO and set 1j = 0.56. The dual formulation of DRO is explained in A.2 This value was chosen empirically to achieve relatively uniform accuracy across group A and group B for an 80/20 split between the two subgroups. As the values of сд and cg change, we can see that the performance of DRO changes for given value of y and hence p. as 17" depends on p.
Objective
Group
CA
0.6, CB = 0.4
CA
0.8, Cg = 0.2
CA 0.95, CB 0.05
ERM
A
0.797
0.907
0.966
B
0.701
0.652
0.592
All Data
0.759
0,856
0.948
DRO
A
0.665
0.751
0.780
B
0.869
0.744
0.766
All Data
0.747
0.750
0.780
Table 1: Accuracy by Group for ERM and DRO.
We first examine the performance of ERM (Table D. As the data is not linearly separable, ERM must learn decision boundary that trades off performance between the two subgroups. Because the ERM objective treats the loss each data point equally, the model learns decision boundary that is more accurate for the majority group than for the minority group. This discrepancy in accuracy of predictions worsens the smaller the majority group is. For instance, when 95% of the data comes from group A, the logistic regression model trained with an ERM objective achieves 96% accuracy on group A members, but only 59.2% accuracy group B members.
Models trained with a DRO objective behave much differently (Table For the 80/20 split and 95/5 split, the DRO models learn relatively fair decision boundaries, effectively balancing perfor-
7

---

Under review as a conference paper at ICLR 2023
Group DRO Decision Boundary
Group with DRO Decision Boundary
25
25
2.0
1.0
10
05
0.5
0.
0.-
-0.5
-0.5
00
0.5
1.0
15
2.0
25
-05
X1
Figure 3: Group A, DRO.
Figure Group B, DRO.
Group with Decision Boundary
Group with ERM Decision Boundary
2.5
25
20
20-
0.0
-0.5
-0.5
Figure 5: Group A, ERM.
Figure 6: Group B, ERM.
Figure 7: Decision boundaries for ERM and DRO classifiers with samples from groups A and with Ca 0.95 and en 0.05. Shading indicates predicted label and data point colour indicates true label.
mance on both subgroups and B. For the 60/40 split, however, DRO actually learns a model that performs significantly better on the minority group than the majority group. This model is in a sense discriminatory against the majority group. This is the result of the radius of the "ivvvergee ball being too large and the model thus overly focusing on worst case distribution.
In Figures 3 4 and o we plot data from groups and B for data generated with сд 0.95, cB 0.05 with the learned decision boundary from DRO and ERM model, respectively, overlaid. The background shading indicates predicted label with blue representing ý red representing 1, while the colour of the data points indicate their true label.
4.3 RRM AND RDRO WITH SUBGROUPS
We have seen empirical confirmation of convergence of RDRO and RRM in our first experiment, and the static classification with subgroups has demonstrated the potential for DRO as a tool achieve fairness in ML models, but neither of these address the question of long term fairness under dynam- ically changing distributions. To investigate this question, we generate data in a similar fashion to the static classification experiment (details in A.6 and add performative element to the model.
The data this experiment is composed of a mixture of multivariate normal distributions with different means. 80% of the data is drawn from the majority subgroup, while the remaining 20% is drawn from the minority subgroup. We again implement a strategic manipulation distribution map and train models using RRM and RDRO for 30 iterations. As dataset, for small values of we observe convergence, whereas for larger values of c we do not observe convergence. Plots illustrating this behaviour can be found in A.6
with the Give Me Some Credit
The accuracy of the models for the values for which we observe convergence are given in Tables We that RRM converges performatively stable model that achieves high
and 4.3
8

---

Under review as a conference paper at ICLR 2023
ERM Performative Accuracy
DRO Performative Accuracy
Group
0.01
6= 0.25
= 0.5
c= 0.01
<= 0.25
0.5
A
0.893
0.896
0.898
0.687
0.710
0.738
B
0.540
0.540
0.540
0.670
0.660
0.660
All Data
0.834
0.837
0.838
0.684
0.701
0.725
Table 2: Accuracy by Group for ERM and DRO after 30 iterations.
accuracy the majority group, but performs poorly the minority group. RDRO on the other hand, results in models that perform similarly across both subgroups in the data.
This result, while perhaps not that surprising in light of the two previous experiments, is important, as it demonstrates that not only does DRO exhibit similar convergence behaviour to ERM, but DRO converges to fair fixed points, whereas ERM converges discriminatory fixed points in the presence of heterogeneous data composed of minority and majority subgroups. Recall also that DRO is not given access group information, but still learns to achieve more uniform performance across subgroups, as it is attempting to minimize the worst case loss across all probability distributions within the -diivergee ball surrounding the data generating distribution. Further details of this experiment, as well as additonal experiments are provided in A.6
5 CONCLUSION AND FUTURE WORK
Performative prediction offers rigorous framework in which to reason about decision making in dynamic environments. Existing theory for performative prediction had only been developed for models trained with ERM objectives, however, which is liable to result in models that discriminate against minority groups
We extend the performative prediction framework to DRO and prove convergence result for RDRO. We also investigate RRM and RDRO empirically and find that while they exhibit similar conver- gence behaviour, RRM converges fixed points that perform well majority subgroup. but poorly on a minority subgroup, whereas RDRO converges to models which successfully balance performance across majority and minority subgroups.
We hope that this work helps to further our still very limited understanding of fairness properties of ML algorithms in changing and dynamic environments, which charactierize many real-world settings with fairness concerns. By combining performative prediction with a distributionally robust objective, we have tried to overcome some of the shortcomings of the dominant fairness criteria and to offer flexible and general tool to ML practitioners and researchers concerned with ensuring that algorithms do not discriminate against vulnerable minority groups.
This work represents a preliminary investigation into the combination of DRO and performative prediction as a method to understand and learn fair algorithms, and, as such, leaves many impor- tant avenues for future work open. Further theoretical investigation of the convergence properties of RDRO would yield better understanding the distributionally robust objective, as this work es- chewed answering important questions of stability of worst case distributions as well as questions of smoothness and strong convexity of distributionally robust objectives.
It would also be very interesting investigaate both the convergence properties and practical efficacy of a parametric DRO objective, rather than an f-divergence based robust objective. Recent work suggests that parametric DRO can outperform f-divergence based DRO and offers practitioners and theoreticians greater flexibility than with analytic DRO Michel et al. (2022 2021).
Additionally, performative prediction and distributionally robust optimization have connections and similarities to many other well established areas of research in machine learning, and it is likely that existing results in areas such bandits, reinforcement learning, online learning, stochastic optimization, and out of distribution generalization could greatly contribute to our understanding of DRO and performative prediction.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
AJ Abdallat. A push for digital transformation: The global ai investment boom. 2021.
Tara Balakrishnan, Michael Chui, Bryce Hall, and Nicolaus Henke. The state of ai in 2020. Mckinsey Analyties, 2020.
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning. fairml- book.org, 2019, hett::/wwwy Eai rm wwm.lbo..ooo
A. Ben-Tal, L.. El Ghaoui, and A.S. Nemirovski. Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press, 2009.
Aharon Ben-Tai Dick den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Ro- bust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2):3413377, 2013. ISSN 0025-1909.
Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. Fairness criminal justice risk assessments: The state of the art. Sociological Methods & Research, 50(1):3-44 44, 2021.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. ISBN 0521833787.
Gavin Brown, Shlomi Hod, and Iden Kalemaj. Performative prediction in stateful world. 2020.
Michael Bruckner, Christian Kanzow, and Tobias Scheffer. Static prediction games for adversarial learning problems. Journal of Machine Learning Research, 13(85):2617-2554 2012.
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism
prediction instruments. Big data, 5 2:153-163, 2017.
Sam Corbett-Davies, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic decision making and the cost of faimesss KDD '17, pp. 797-806. Association for Computing Machinery, 2017. ISBN 9781450348874.
Csiszar. Information-type type measures of difference of probability distributions and indirect obser- vation. Studia Scientifica Mathematica, 2:299-318, 1967.
I. Csiszár and P.C. Shields. Information theory and statistics: A tutorial. Foundations and Trends in Communications and Information Theory. 1(4):417-528, 2004. ISSN 1567-2190.
Alexander D' d'Amuur, Hansa Srinivasan, James Atwood, Pallavi Baljekar, D. Sculley, and Yoni Halpern. Fairness is not statie: Deeper understanding of long term faireess via simulation stud- ies. FAT '20, pp. 525-534, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450369367.
Roy Dong and Lillian Ratiff. Approximate regions of attraction in learning with decision- dependent distributions, 2021.
John C. Duchi and Hongseok Namkoong. Learning models with uniform performance via distribu- tionally robust optimization. The Annals of Statistics, 49(3):1378- 1406, 2021.
John C. Duchi, Tatsunori Hashimoto, and Hongseok Namkoong. Distributionally robust losses for
latent covariate mixtures. CoRR, Abs/2007..33982 2020.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations Theoretical Computer Science Conference, ITCS '12, pp. 214-226. Association for Computing Machinery, 2012. ISBN 9781450311151.
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classi- fication. In Proceedings of the 2016 ACM Conference Innvaations in Theoretical Com- puter Science, ITCS '16, pp. 111-122. Association for Computing Machinery, 2016a. ISBN
9781450340571.
10

---

Under review as a conference paper at ICLR 2023
Moritz Hardt, Eric Price, and Nathan Srebro. Equality of opportunity in supervised learning. In NIPS, 2016b.
Tatsunori B. Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness with- out demographics repeated loss minimization. ICML, 2018
Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan. The disparate effects of strategic manip- ulation. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT 11, pp. 259-268, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450361255
Sookyo Jeong and Hongseok Namkoong. Robust causal inference under covariate shift via worst- case subpopulation treatment effects. Jacob Abernethy and Shivani Agarwal (eds.), Proceed- ings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 2079-2084. PMLR, 2020.
Jon Kleinberg. Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determi- nation of risk scores. Christos Papadimitriou (ed.), 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informat- ics (LIPIcs), pp. 43:1-43:23, Schloss Dagstuhl-Leibniz-Zeettee fuer Informatik, 2017. ISBN 978-3-95977-029-33
Christian Kroer. Lecture Notes for Economics, AI, and Optimization. 2022.
Jacho Lee and Maxim Raginsky. Minimax statistical learning with wasserstein distances. In S. Ben- gio, H. Wallach, H. Larochelle, K. Grauman, N. Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
and R. Garnett (eds.), Advances in
Celestine Mendler-Dünner Juan Perdomo, Tijana Zmic,, and Moritz Hardt. Stochastic optimization for performative prediction. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances Neural Information Processing Systems, volume 33, pp. 4929-4929999 Curran Associates, Inc., 2020.
Paul Michel, Tatsunori Hashimoto, and Graham Neubig. Modeling the second player in distribu- tionally robust optimization. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
Paul Michel, Tatsunori Hashimoto, and Graham Neubig. Distributionally robust models with para- metric likelihood ratios. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in disguise. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 6917-6926. PMLR, 2020.
John Miller, Juan Carlos Perdomo, and Tijana Zmic. Outside the echo chamber: Optimizing the performative risk. International Conference on Machine Learning (ICML) 2021, 2021.
Smitha Milli, John Miller, Anca D. Dragan, and Moritz Hardt. The social cost of strategic classifi- cation. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT '1,, pp. 230-239. Association for Computing Machinery, 2019. ISBN 4703612362
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
Hongseok Namkoong and John C Duchi. Variance-based regularization with convex objectives. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
11

---

Under review as a conference paper at ICLR 2023
Juan Perdomo, Tijana Zmice, Celestine Mendler-Dümen Dünner, and Moritz Hardt. Performative prediction. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 7599-7609. PMLR, 2020.
Georg Pflug and David Wozabal. Ambiguity in portfolio selection. Quantitative Finance, 7(4): 435-442 2007.
Alfred Renyi. On measures of entropy and information. In The 4th Berkeley Symposium on Mathe- matics, Statistics and Probubility, pp. 547-561. University of California Press, 1961.
Alexander Shapiro. Distributionally robust stochastic programming. SIAM Journal Optimization, 27(4): 2,
V. Vapnik. Principles of risk minimization for learning theory. In Proceedings of the 4th Inter- national Conference on Neural Information Processing Systems, NIPS'91, pp. 831-838. Morgan Kaufmann Publishers Inc., 1991. ISBN 1558602224.
Abraham Wald. Statistical decision functions which minimize the maximum risk. Annals of Math- ematics, 46:265-280, 1945.
Blake Woodworth, Suriya Gunasekar, Mesrob Ohannessian, and Nathan Srebro. Learning non- discriminatory predictors. In Satyen Kale and Ohad Shamir (eds.), Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pp- 1920-1953. PMLR, 2017.
David Wozabal. A framework for optimization under ambiguity. Annals of Operations Research, 193(1):21-44 47, 2012.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P. Gummadi. Fair- ness beyond disparate treatment and disparate impact: Learning classification without disparate mistreatment. In Proceedings of the 26th International Conference World Wide Web, WWW '17 pp. 1171-1180. International World Wide Web Conferences Steering Committee, 2017.
ISBN 9781450349130.
12

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 RELATED WORK
The two most inftuential areas of research for this work are performative prediction and distribution- ally robust optimization, and the papers most important for this work are Predooo et al. (2020) and Duchi & Namkoong (022). Perdomo er al. develop the performative prediction framework, while Duchi and Namkoong give thorough summary of distributionally robust optimization and explain its potential upplication fairness concerns in machine learning.
Following the publication of Performative Prediction Perdomo et al. (2020), there have been a num- ber of papers which have further explored performative prediction and extended some of the results from the original paper. For instance, Srender--ünnne et al. (2020) prove results for stochastic op- timization performative prediction, Miller et (2021) prove new results relating performatively stable points to performatively optimal points, [Brown et al. (2020) attempt to move toward sequen- tial games for performative prediction by adding a notion of state to the performative prediction problem, and Dong & Ratliff (2021) approach performative prediction from a dynamical systems perspective allowing a move away from strict contraction mappings when examining convergence to performatively stable models.
Distributionally robust optimization is an older area of research as compared to performative pre- diction, but it has only recently received more attention within the machine learning community, largely due to work by Hongseook Namkoong and John Duchi Nankoong & Duchi (2017): Duchi al. 2020);]eeon & Namkoong (2020). Areas such as finance, where robust optimization is impor- tant as rare events have the potential to be catastrophic for a portfolio, have seen research on robust optimization for decades. See Ben-Tal et al. (2009) for survey. [Ben-Tal Tal et al. (0013) Shapiro (2017) provide rigorous mathematical treatments of DRO with f-divergence balls.
A number of recent papers have also attempted to better understand fairness in machine learning over time, albeit not within the performative prediction framework. Closely related to performative prediction, strategic classification Hardt et al. (2016a) models the prediction problem as an adversar- ial game where individuals manipulate their features in response to deployed models. Recent work Milli et ) Hu et al. (2019) has examined how strategic classification interacts with fairness concerns. Strategic classification an interesting problem setting, but is not as general as perfor- mative prediction and only captures scenarios that can rightly be modelled as adversarial games. D'Amour et al. (2020) on the other hand, approach long-term faimess questions from purely em- pirical perspective and use simulation studies to understand the long-term dynamics of algorithmic choices populations in variety of scenarios designed to reflect real-world applications. This ap- proach is interesting, but the lack of theoretical framework limits their ability to generalize beyond specific simulations.
Finally, the work most closely related to this paper. Hashimoto et al. (0118), examines the impact of repeatedly minimizing loss and deploying a model using empirical risk minimization and distri- butionally robust optimization on a population that changes as function of the loss incurred. This work, however, does not fit into the performative prediction framework and applies only a specific scenario in which individuals arrive according to Poisson process and depart function of the loss. This research aims to extend this work by combining DRO and performative prediction in order to leverage the known results in both areas to provide more general understanding of how DRO can impact long-term fairness.
A.2 DISTRIBUTIONALLY ROBUST OPTIMIZATION
The notation Q < Po means that Q is absolutely continuous with respect to P An f-divergence, ()(Q|| [P). is a function that measures the difference between two probability distributions Q and P, although it is not metric. There are variety of different f-divergences, but their general definition is as follows Renyi 1961]; : Csiszár Shields (2004); Csiszar (1967).
PIf two measures, f and are on the same measure space (X,A), / is said to be absolutely continuous with respect v if yl () for every A for which v(A) = O.
13

---

Under review as a conference paper at ICLR 2023
Dy(Q]IP) f(ar f( )PP where f is convex function such that f(1) = 0. If Q and P are absolutely continuous with respect to a reference distribution μ. then their probability densities and p satisfy dP p and dQ q and the f-divergence can be written as
DA((11P) /
((xx) p(a) )dulx).
Some examples of f-divergences are KL-divergence (f(1) log (), Pearson x²-divergence f
(f(t) (t 1)² 1,2,² t² 1, t), and total variation distance (f(t) = z 1). An f-divergence ball centred at P of radius p set that contains all probability distributions whose f-divergence is within p of P. For example, {Q (2(Q))P)) S p} is an f-divergence ball that contains all probability distributions Q that are within p f-divergence distance from Po. This is analogous the notion of an c-ball surrounding a vector in vector space.
The distributionally robust problem therefore, is find set of parameters, 0 E O, that minimize the worst case expected loss of all probability distributions Q that are within the f-divergence ball of radius p of our data generating distribution. This differs from ERM in that we do not seek to min- imize the expected loss over data generating distribution, but instead seek to minimize the worst case expected loss over a set of probability distributions nearby our data generating distribution.
As the name suggests, learning parameters that minimize the distributionally robust risk gives model that is robust to changes in the data generating distribution. Traditional risk minimization will return model that minimizes risk for the data generating distribution, but offers performance guarantees when that distribution changes, and can result in models that are brittle and do not per- form well out of distribution (OOD) examples. DRO, the other hand, is more conservative procedure that minimizes worst-case risk and should thus be robust to changes to the probability generating distribution that lie within the f-divergence ball of radius p.
As with traditional risk minimization, we do not have access to the theoretical data generating dis- tribution. Instead, we solve the distributionally robust problem via the plug-in estimator
(,, Pa) (R)(0.P))
0n arg min AEE
sup : s QEPP
where Pr is the empirical measure X; Rid Po. Duchi and Namkoong prove convergence guarantees and rates for the plug-in estimator along with some asymptotic results such as showing consistency of the estimator Duchi & Namkoong (2021).
is not necessarily clear from the discussion so far what DRO has to do with fairness concerns in machine learning, but DRO in fact has characteristics that are very desirable for addressing issues of fairness and discrimination in learning algorithms. We will explain this shortly, but first we introduce dual reformulations of the distributionally robust problem as it provides some intuition as to the connection with fairness concerns.
The following theorem comes from Shapiro 2017). Let (*) sup, S(L) be the Fenchel conjugate.
Theorem A.1. ([Shapiro 2017), Section 3.21). Let P be a probability measure on (X, and p 0. Then
Ep A5" (400-)))) -
();0:P) = inf X20.EER
for all 0. Moreover, if the supremum the left hand side is finite, there are finite x(0) 2 0 and 7)()) E R attaining the infimum on the right hand side.
Additionally, Duchi & Namkoong (2021) provide a simplified version of this dual formulation for the Cressie-Rees Read family of f-divergences, obtained by minimizing out À > 0 from Theorem A.
Theorem A.2. (Duchi & Namkoong) (2027), Section 21). For any probability P on (X, A), k E
(1, oo). k. = k/(h- 1), any > O, and cs (p) = (1 + k:k 1)pp)/K we have for all @ E θ
1/k.
Ry P)= inf HER
(p(p) [<((0 X) x)- - n)
+ 17
14

---

Under review as a conference paper at ICLR 2023
The above formulations are jointly convex in (0, X. and (9, respectively, for convex losses, e(;; X). making them amenable to techniques from convex optimization such as interior point meth- ods Boyd & Vandenberghe (2004).
The Cressie-Read family of f-divergences are parameterized by E (-o0, 0o) (0,1), k. = R-1 with
16 kt + k:k 1)
1 and ==())== To [(k
[x(1)
1)s 11 -
Issues of fairness arise in machine learning when an algorithm treats different demographic groups in a disparate fashion. As outlined above, this often means that algorithmic performance varies across different demographic groups If this occurs, distinct probability distributions over the demographic groups because if all demographic groups were characterized the the same probability distribution, classification algorithms should exhibit uniform performance across demographic groups.
almost certainly the case that there exist
This realization makes it easy to see why ERM is likely to discriminate, particularly against minority groups. ERM treats the loss each data point equally, thus, if there is majority and minority probability distribution and a learning algorithm must balance performance on these groups, an ERM objective is likely result in model that performs better on the majority group and worse on the minority group. It is exactly this type of problem that DRO is designed to resolve.
Unlike ERM, DRO does not equally weight each data point, but instead up-weights data points on which the model is achieving high loss. This means that the model should achieve somewhat uniform performance on individuals across demographic groups. This can be seen by looking the dual formulation in Theorem A.2 The DRO objective only considers losses above the optimal dual variable 17" r7"()) and these losses are up- weighted by the (P-((D)n Losses that are less than the optimal dual variable are set to zero in the objective. Another way of saying this is that the DRO objective is equivalent to optimizing the tail-performance of a model Duchi Namkoong (021))
If DRO performs poorly on a subset of the data that is correlated with a distinct demographic group, these losses will be up-weighted by the dual formulation of the distributionally robust objective, pushing the model to improve performance on this subset. DRO does not offer any guarantees of uniform performance across demographic groups, but as we increase the value of p we will increase the loss incurred on "hard" regions of the data where the model performs poorly.
A.3 PERFORMATIVE PREDICTION
In supervised learning we assume that our data is sampled i.i.d. from an unknown data generating distribution and that our model is then deployed to make predictions on data that follows this same distribution. In many scenarios, however, the very act of making predictions influences the data on which we wish to make these predictions. That is to say, our models are performative and instead of passively describing the world and making predictions about it, they actually induce change in the world.
A simple example of this predictive policing. In predictive policing we train model to predict where crimes are likely to occur based on historical data and then deploy more resources to areas where the model predicts crimes are more likely to occur. The increased police patrols and surveil- lance results in more crimes being detected which might further increase the perceived crime rate in those areas. this data is then used for future predictions will result in shifted distribution of the data as a result of the predictions of the previous model. Another example of performativity is an algorithm that weights different elements make college admissions decisions. If the algorithm heavily weights SAT scores, over time it will become apparent to applicants that SAT scores are very important and they will dedicate more re- sources to improving SAT scores, thus changing the distribution of the data on which the algorithm is making predictions as a result of those very predictions.
student's CV such as SAT scores and GPA in order to
Performative prediction is closely related to many other fields in machine learning including bandits, reinforcement learning, strategic classification, causal inference, convex optimization, and game theory, but the precise notion and formalism for performative prediction was only developed very
15

---

Under review as a conference paper at ICLR 2023
recently in Perdomo et al. (2020). We formally specify the performative prediction problem now and contrast it with the supervised learning problem.
Assume have measure space (2,A) with Z a random element of Z and D the data generating distribution on this space. Let C H be the parameter (model) space and & θ x Z + R be a loss function. The supervised learning problem is minimize the the objective over this distribution. In the case of risk minimization the objective is the expected loss, ((Z;)) with respect to D.
R(0) = Ez-z Ezzp ((( 0)].
In contrast to this, performative prediction involves making predictions on distribution that has been shifted as result of deploying the model, D(0). We refer to (()) as the distribution map. The concept that captures this notion of risk is known as performative risk and is formalized as follows:
PR(O) = 1 [e(Z;)).
The difference between this and the supervised learning problem is that expected loss is now taken with respect to the induced distribution rather than the data generating distribution.
The notion of what constitutes good model is different in supervised learning and performative prediction. In supervised learning the task is simpler minimize the risk the data generating distribution. performative prediction however, we now need to consider how minimize risk on a distribution that is different from that which generated our training data, and is in fact a function of whatever model we deploy. To capture these notions, Perdomo et al. (2020) define performative optimality and performative stability.
Definition A.3. (performative optimality) A model fero is performatively optimal the following relationship holds:
fro = arg min E [[[Z;)]]
Bg
Equivalently, 0PO = arg mingee PR( where PR(0) is the performative risk defined above.
A performatively optimal point is a minimizer of the performative risk. An alternative solution concept is referred as performative stability.
Definition A.4. (performative stability) A model Sope is performatively stable if the following re- lationship holds:
0ps = arg min La [x200(ss))(
DE Define DPR(0, 8¹) = E2-D as the decoupled performative risk; then 0ps = arg migmi DPR(Ops,O).
A performatively stable model is not necessarily minimizer of the performative risk, but it is optimal on the distribution it induces. Hence, you have performative stability there is no need to retrain model to cope with the induced distribution drift. Performative optimality and performative stability are distinct concepts and a performatively optimal point is not necessarily performatively stable, and vice versa. As explained in Perdomo et al. (2020), performatively stable models are fixed points of risk minimization. In game theoretic terms, we can consider performative prediction as a game in which one player deploys model, 9, and the environment responds with some distribution map, D()). If D(0) is a best response, then a performatively optimal point corresponds to a Stack- elberg equilibrium, whereas a performatively stable point corresponds to Nash equilibrium. From game theory we know that except in special cases (e.g. finite zero-sum games), Nash equilibria and Stackelberg equilibria do not necessarily coincide Kroer (2022).
Performative prediction presents a special case of learning under distribution drift, where the distri- bution drift is function of the model deployed. A common approach in supervised learning under distribution drift is to retrain a model on newly collected data. While this does not directly minimize performative risk, it is a potentially reasonable solution in a variety of scenarios. Perdomo et al. (020)) prove theorems under which repeated risk minimization and repeated gradient descent con- verge to performatively stable models. We present these findings in detail here as they are relevant for our work.
Definition A.5. (c-sensitivity) We say that a distribution map D(-) is e-sensitive if for all 0, 0' E θ:
W1 (D(0), D(O') S ell@ 6 0'112.
where W, denotes the Wasserstein-1 distance.
16

---

Under review as a conference paper at ICLR 2023
We also make assumptions the loss function {(2; 8). Let 2 (bees)pp(D(())) Definition A.6. (joint smoothness) We say that loss function {(z;0) is B-jointly smooth if the
gradient Ve is 3-Lipschitz in and z, that
[Vok(2; 0) Vol(=; 12) S 3 122,, [[Vol(>;0) - - A||= 1122 for all 0,0' O and 2;
Definition A.7. (strong convexity) We say that loss function {(2; 8) is y-strongly convex if (=;0) ((;;0)) Vol(=;0))' 0²)
0
for all 0,0' and = E z. y = 0 this condition is equivalent to convexity.
Definition A.8. (repeated risk minimization) Repeated risk minimization (RRM) refers to the pro- cedure where, starting from an initial model fag, we perform the following sequence of updates for every t 2 0:
02+1 G(O.) arg min Eg~-Do,)(((;;0)}
IE
Definitions A.5 A.6, and A.7 are assumptions on the loss and distribution map that are required for Theorem 3.5 in Perdomo et al. 2020). We state that theorem now.
(Perdooo et al. (2020), Theorem 3.5]) Suppose that the loss ((2; 0) is 3-jointly smooth and y-strongly convex. If the distribution map D()) e-sensitive, then the following state- ments are true:
Theorem A.9.
1. ||G(B) - -G(0)l2 & c2 110 12. for all 0, 8' E
2. If'e < 7. the iterates 02 of RRM converge to a uniquely performatively stable point Ops at
a linear rate: ||0, 0psll2 - for 2 (1- (1- log 110--0ps1
This theorem says that with the appropriate smoothness and convexity conditions satisfied on the loss and distribution map, repeatedly retraining model by minimizing risk will converge unique performatively stable model at linear rate. The proof proceeds by demonstrating that under the assumptions stated in Theorem A.9 the RRM operator is a contraction mapping. Perdomo et al. (2020) also show that without any of e-sensitivty, 3-joint smoothness, or 7-strong convexity one can produce examples that do converge to fixed point. Hence these assumptions are necessary conditions to guarantee convergence of RRM to performatively stable model in the general case.
A.4 DEFINITIONS AND PROOF FOR DISTRIBUTIONALLY ROBUST PERFORMATIVE PREDICTION
We begin by redefining performative risk and performatively optimal and stable models terms of a robust objective. In the following D(0) is distribution map and (Q( is an f-divergence ball of radius p. Definition A.10. (robust performative risk) The robust performative risk model,
RPR(()) sup (Ez-ol((Z:()) : ()(()))(O) s p). QE:(())
Robust performative risk differs from performative risk in that the induced distribution, D(0), is now the centre of an f-divergence ball over which supremum of the expected loss taken.
Definition A.11. (robust performative optimality) model fero is robustly performatively optimal if the following relationship holds:
0PO = arg min
sup (E2~ol((2:0) ()(Q)))(0) S p). QED(()
8ee
Equivalently, 9r = arg min RPR(0) where RPR(0) is the robust performative risk as defined above.
17

---

Under review as a conference paper at ICLR 2023
Definition A.12. (robust performative stability) A model føns is robustly performatively stable if the following relationship holds:
Ors arg min sup ge (<D(Ors)
[1 =
Define RDPR(O, 0²) = (()) [2-o)((2200) - performative risk; then Ps = arg gingee RDPR(Ops.
p} as the robust decoupled
We discussed earlier that previous work has shown that repeated risk minimization converges to performatively stable model under certain assumptions the loss and distribution map Perdomo ct al. (020). We can analogously define repeated distributionally robust optimization as follows.
Definition A.13. (repeated distributionally robust optimization) Repeated distributionally robust optimization (RDRO) refers to the procedure where, starting from an initial model fa,- we perform the following sequence updates for every 2 0:
o++1 G(O,) == arg min sup (Ez-ole(Z:0) (((Q))((0)) S p).
dc Qe.(().)
As with RRM, this is an iterative procedure where we optimize the distributionally robust objective at each time step f. While is only small departure from RRM conceptually, the DRO objective has fundamentally different mathematical properties than risk minimization making it unclear whether RDRO and RRM should exhibit similar behaviour.
We now re-state and prove our convergence theorem for RDRO. The proof of this theorem straightforward adaptation of the proof in Perdomo et al. (202)). We first introduce two lemmas used in Perdomo et al. (2020) which we will make use in our proof.
Lemma A.14. (First-order optimality condition) Let f be convex and let be a closed convex set on which f is differentiable, then
Ix arg argmmin f(x)
and only if
V (t EQ. Lemma A.15. (Kamtorovic--Rubinsteen A distribution map D(-) is robustly e-sensitive if and only for all 0,0' E O
sup (|E -02- g: IR. - R.g I-Lipschitz) I well0 - 6'112
where (+) arg max Ez~al((Z:0). Q:D)(Q1IP(0)sp
We now state theorem.
Theorem A.16. Suppose that the distributionally robust objective satisfies definitions 3.5 and 3.6 and that the distribution map satisfies definition) 3.7 Then the following statements are true:
1. |[G(0) - G(0 S we we 12 for all 0, e
2. If we 3. the iterates 9, of RDRO converge to unique robustly performatively stable
point 0ps at a linear rate: |10: 0ps/22 S for Z (1-wef) log [ [100-pps
Note that G(Ø) ;= arg mingge (B2
()(Q)ID(0)) s sp}.
Proof. Fix 0,0 0' e O. Let
(*
arg max Ez~q (((:0)). (:I)(
That is, (*) is the distribution within the fddivergence ball centred at D(0) with radius that maximizes the expected loss. Further, let
f(E) EZ (0) [(() and J'(S) (0
18

---

Under review as a conference paper at ICLR 2023
That is, f(E) and f(( the worst case losses for f-divergence balls centred 9 and 6' respec- tively with radius p.
We Definition 3.6 and Definition 3.5 to ensure that is y-strongly convex and that the gradient of f exists and is 3 D-joinll smooth. With our assumption of y-strong convexity of f. G(0) the unique minimizer of f(x and we have the following inequalities
[(G(0) (000)-((G(()) S(G(O)) 2 (G(0) - + (2)()))))))))))))))))))
(1)
f(G(O)) f(G(0)) 2 22 ()) G
(2)
Inequality T comes from the definition of 7-strong convexity and incquality (2) comes from y- strong convexity and the first-order optimality condition since Lemma A.14 tells us (G(0") 2 0 because G(f) is the minimizer of fx)).
Using these two inequalities
derive the following
->||G(0) - G( 2 f(G(0)) f(G(()) - (]G ((G()) G(#))
(G(0) - ((O))=(()))/(((())
where we get the first inequality from and the second from
Now, using ß-joint smoothness in and Cauchy-Schwarz we get
[|(G(0) - G V(o) (G(O) G(O)) (
|G(()) - G(0)) 2/122
That is, (G(O) G(O)) is |G(()
z. We will now use this
and Kantorovich-Rubinsteed (Lemmal A.15). Let
g(z) = (G(0) - V((''
|G G(0))l223
The function g(z) is I-Lipschitz in because we have just divided (G(0) - G(O')) V G(D'))
by its Lipschitz constant. From Lemma A. 15 and Definition 3.7 we have the following, with g (2) as defined above
E EzwD- (9) [g( [)] Ex well0 uell 0'
Using linearity of expectation and multiplying by ||G(8) 1(0 we get the following
(G(O) -
- (G( (())))))))))))(((111
2 - 0
Now again using Lemma
A.14
we have (G(O) G()))) > 0, hence (G(0)
(((e))) weB G()) - G( (2()))221 8'112. From our work above we showed that
-y|[G(0)- G(0) (G(()) G( ((())) V((()) Putting this all together we get
- G(D') we G(D) G(00'|l2|10 - 0'112
We rearrange the above to get
[[G - G(0')l S we -10 81
which proves claim (1) of the theorem.
Claim (2) follows easily. We note that 6, = G(0,-1) from the definition of RDRO and G(Ops) Ops by the definition of robust performative stability. Using the result of claim (1) we get
100 0rsll2 we 100- 0rslla (e xee 110. 0rsl2
19

---

Under review as a conference paper at ICLR 2023
Now set
1160 - -pslll S we 0) 7
and solve for t.
we 18)
110u -pssl2 S
B
t flog
we
+ log(116 - -0ps|12) s <log(d)
tlog
we
I <og(()) - log(1 - 0rs(l2)
?
WE 3)
3
tlog
S t
we
-1
< (og - log(1 - 0psl12)
?
?
WE 8
-1)-
z (log(d) - log([100 - 0ps|12))
100
0psll2
t we
log
Note that this theorem essentially just an application of the Banach fixed point theorem as we <
we 2
While this proof provides us with conditions under which RDRO converges, it is somewhat unsat- isfying as it leaves as an open question what is required for Definitions 3.5 3.6 and 3.7 to be true. Unlike for performative prediction with risk minimization, making assumptions our loss function does not guarantee that the distributionally robust objective will share those properties. In order to have smoothness of our objective and also robust e-sensitivity of the distribution map require some sort of stability or regularity of the worst case distributions as the centre of the t f-divergence ball moves function of 0.
The robust c-sensitivity condition could possibly be equivalently expressed as a smoothness con- dition for the f-divergence ball surrounding the data generating distribution. Further exploration of these questions would likely yield further understanding of the distributionally objective, even outside of the context of performative prediction.
It could also be possible that robust 3-joint smoothness is not necessary condition for convergence of RDRO and that a convergence proof may be possible working with subgradients or directional derivatives, but if this is the case it would necessitate different, and likely more involved, proof technique than the one used here. An alternative approach would also be to work with the dual reformulation of the DRO problem given in Theorem to use alternative probability distance measure rather than f-divergence balls that may be more amenable to this type of analysis.
These approaches come with their own complications, however, and likely require answering similar questions. We believe these are interesting questions worthy of further research, but their investiga- tion is beyond the scope of this work. Instead, we present empirical work which demonstrates the convergence of RDRO in a variety of scenarios.
A.5 IMPLEMENTATION
We provide brief explanation of the implementation details for ERM and DRO. Both risk mini- mization and distributionally robust optimization require access to the data generating distribution, i.e. infinite data, which is obviously impossible, we perform empirical risk minimization and utilize the plug-in estimator for distributionally robust optimization instead. Further, for DRO we make use of the dual formulation (Theorem A.2) and perform optimization this objective rather than working with the primal form. Following Duchi Namkoong (202I) and Haasimmtoo et al. 2018). divvergene balls in our implementation.
20

---

Under review as a conference paper at ICLR 2023
In all of our experiments size and a fixed number of epochs for training. The logistic regression utilizes an L2-regularized cross-entropy loss function.
linear models trained with gradient descent. We fixed step-
The dual formulation of the distributionally robust objective allows for a simple training procedure where treat the dual variable !/ as hyperparameter. Recall that for convex losses, {(0; Z), the dual formulation is jointly convex in (6, .7). The training procedure is thus as follows, for given 1), compute the approximate minimizer On
minimize E({(f; 2) 7
AEB
Because the dual convex in 7) we can use binary search to find the optimal dual variable rf".. The loss (e(0; Z) 7) is merely the ReLu function applied to the usual loss with subtracted and then squared which allows us train models using gradient descent methods. Hence, using binary search we train models with different values of until we find the optimal vz" The optimal value, 1f", depends on the data and also the radius of our f-divergence ball, p. The value of p is a hyperparameter that we must specify before training our model.
A.6 EXPERIMENTS
A. RRM AND RDRO FOR CREDIT DATASET
Our first experiment reproduces the experimental work from Perdomo et al. (2020), We use a dataset from Kaggle competition titled Give Me Some Credit. The dataset contains relevant information for predicting credit scores. The target variable is binary variable indicating whether or not an individual has experienced financial distress in the past two years. The original dataset contains historical information for 250,000 borrowers.
Following Perdomo et al. (2020) we balance the dataset to contain an equal number of positive and negative cases for the target variable and normalize predictor variables to have mean of zero and variance of one. The reduced dataset contains 18,358 entries.
We train L2-regularized logistic regression models on the data for both ERM and DRO. Both models are trained with stochastic gradient descent with a fixed step-size of a = 0.03 for 5000 epochs. The step-size and number of epochs were chosen empirically to approximately replicate performance from Perdomo et al. (2020) on the base distribution. Additionally, a fixed value of was chosen as radius of the divvieeeee ball for DRO. The value of o was chosen that the accuracy of the DRO model on the full dataset was significantly, but not drastically, different than that of the ERM model.
In order to add a performative element to the prediction problem, we identify 3 of the 10 features as strategic features which will be altered as function of the parameters of model. Strategic classification is a particular instance of performative prediction in which individuals adversarially adjust their features to maximize the likelihood of classification
the positive class. Strategic
classification has been explored in relation to fairness concerns in previous work Hardt et (20
Bruckner et al. (2012): ) Miller et al. (2020 Milli et al. (2019): D' D'Amour et al. (2020): Hu et al. (2119).
As described Perdomo et al. 2020) and Hardt et al. 201 6a utilities u(0,x)) = -(0,x) and quadratic costs c(x', xx)
we assume individuals have linear x xi1.. The constant controls
the cost individuals incur by altering their features. Individuals thus pay a cost to manipulate their features in order to minimize the likelihood of the model predicting that they will default on their loan, but are unable to change the true outcome, y E {0, 1}. of whether or not they default. Given linear utilities and quadratic costs as described here, the individuals' best response is to manipulate their features as
d'z = c0s,
where æs, .t's R and |S| is the number of strategic features. The explanation of why this distribu- tion map is c-sensitive can be found in Perdomo et al. (2020).
The procedure for updating the data according to the distribution map for strategic classification is explained in the box below.
21

---

Under review as a conference paper at ICLR 2023
Input: Base distribution P, classifier Jo, cost function c, utility function u. Sampling proce- dure for D(0);
1. Sample (a, v) ~
2. Compute best response øBR t- arg m 0( c(x',
3. Output sample (# y)
Using logistic regression classifier and the strategic classification distribution map sam- pling procedure outlined above, we rum ERM and DRO for 30 iterations on our dataset with values of {0.1, 10, 100). We observe similar convergence behaviour for both ERM and DRO. As the value of grows, the inequality
3 no longer holds, meaning that the conditions of Theorems A.9 and 3.8 are not satisfied and we do not necessarily have a contraction mapping. We plot the normalized distance between values of 0 for successive iterations of ERM and DRO in Figures 2 The distance between iterates is calculated as
1
110--1 Bel12.
|0s||2
where fg is the value of 0g on the strategic features.
A.6.2 BUILDING INTUITION THROUGH SIMPLE EXAMPLES
We now investigate the convergence ERM and DRO on simple synthetic datasets to build intuition for the behaviour of the two algorithms. We move away from the assumptions required for our general theoretical guarantees for convergence a fixed point and experiment with distribution maps that are not necessarily e-sensitive. We begin with regression problem and then investigate classification problem.
Regression
We start with a simple mean prediction task with data sampled from a mixture two univariate Gaussians, XA (HHA, and XB ~ (N,,,
80% of the data is sampled from X and
20% from NB, Le. X = 0.2XA+ 0.8X We train a linear regression model using gradient descent with backtracking line search predict the mean of the data. We initialize
data with values MA = 4, |4 = 4, and x² 0.01. We choose a small value of o² so that the variance and finite samples have only small impact on the convergence behaviour of ERM and DRO. We select an f-divergence ball radius of 4 for DRO.
We use 0 denote the learned parameter of the model, s denote the true mean of the data generating distribution, and and to denote the true means of the XA and XB. In other words, f is the estimated mean from the model. Where necessary, we indicate with subscripts ERM and DRO to indicate which model we are referring to.
We investigate three different distribution maps which we call Du. D1, and D2. For each map the means of the normal distributions from which we sample are adjusted as a function of é. Hence, the induced distribution is
(0) 0.2N + (O)
These distribution maps were chosen because they are simple to understand, but reveal important differences the way ERM and DRO behave when their predictions alter the distribution on which they are learning. The distribution maps are specified in Table
Dol.)
Di(.)
Dz(.)
D NO 0²)
D1 = ((AA
D2 N200 o²)
D = N1. DF = N
D = (F(00))((,03)
Table 3: Distribution maps for prediitredittion experiment.
The distribution map determines the evolution of the distribution over the data at each iteration of deploying and learning our model, which in turn changes the learned 0: 14:- Despite starting from
22

---

Under review as a conference paper at ICLR 2023
ERM Learned Theta
DRO Learned Theta
10
10
Dv
Dg
10"
D
10'
D
D2
D
10
10
0
10
30
40
50
Iteration
Iteration
Figure 8: Learned values of 0 for ERM.
Figure Learned values of for DRO.
the same initial distribution in each case, the induced distributions vary widely. This demonstrates the importance of performativity and illustrates why static supervised learning framework fails to adequately capture the complex dynamics prediction problems which involve performativity.
We run the experiment for 50 iterations, where one iteration involves training model on data sampled from the current distribution and then updating the distribution via the distribution map. We summarize the evolution of the learned parameter 0g over time for both ERM and DRO in Figures g a Given the simplicity of the learning problem, the learned values 8 closely approximate true mean of the distribution, μ4, over time. The approximate values to which ERM and DRO converge are given in Table
It is interesting note that with this simple mean prediction task observe significant dif- ferences in the behaviour ERM and DRO over time. For all three distribution maps we observe ERM's tendency focus the majority group over the minority group. Recall that 20% of the data is sampled from XA and 80% from Xn so we refer to group A as the minority group and group B the majority group. For Do, ERM quickly converges toward zero as group B's mean evolves as μB 2- approximately 0.004 even though 0 0 is the performatively optimal value.
e Interestingly, however, it does not converge to zero, but instead remains fixed at
DRO displays similar behaviour for this distribution map, but does not converge as close to zero. As noted, performative stability and performative optimality are distinct solution concepts, and perfor- matively optimal points only coincide with performatively stable points in specific settings.
Method
Dol-)
D1(-)
D2(-)
ERM
8ERM 0.004
θERM 1.33
8ERM 0.008
DRO
PDRO = 0.128
PDRo
2.66
@DRO 00
Table Values which 0 converges for ERM and DRO.
The second distribution map, D reveals differences in ERM and DRO that are relevant for fairness. For D,, the mean of the majority group again evolves as μu 2. but this time the minority group's mean remains unchanged with μ = 4. As ERM averages the loss over all data points, it converges to predicted mean much closer to ju than to μ4. DRO, that balances performance on prediction of the means of both minority and majority groups. In fact the distance from the true means of group A and group B is almost identical.
the other hand, converges to value
D MAl 12.66 4 = 1.34
p uBl 2.66
1.33 1.33
ERM, however, is a much better predictor of the global mean of the data. This simple example illustrates trade-off expect between ERM and DRO in terms of faimesss versus global
23

---

Under review as a conference paper at ICLR 2023
ERM Learned Theta
DRO Learned Theta
10"
10
10
10*
10
Majority A Majority
Majority A Majority
10"
10¹
10"
10a
10'
10
30
40
50
50
Iteratoon
Iteration
Figure 10: Learned values of 0 for ERM with
Figure 11: Learned values for DRO with D2.
D2.
performance.
PERM 0.2pu + 0.8μB (0.2) + (0.6)().665) 1.332
JDRO 0.2pA + 0.8μ0 = (0.2) + (0..)30.1.33) = 1.864
The final distribution map. D2, demonstrates that ERM and DRO behave entirely differently under some circumstances. For this distribution map ERM converges to similar value to that under Do. that is FERM 0.008. This makes some sense intuitively as μ 20 whereas for Do we had 0. DRO, on the other hand, diverges with DRO going to infinity. The reason for this is that for the first iteration DRO learns value of &RR that is larger than 4. Similarly, for each successive iteration the learned value of DRO gets larger which in turn causes the true means of the data to grow as a function of the learned PpRo Interestingly, you swap the majority and minority groups the behaviour of DRO remains nearly identical, while ERM diverges at a faster rate than DRO. This again demonstrates how DRO treats minority and majority groups similarly, while ERM learns a function that prioritizes performance on majority groups. We illustrate this in Figures 10 and
Classification
We now move to a classification task and analyze the behaviour of logistic regression classifiers trained using ERM and DRO. The classification task is more complex than the simple mean predic- tion task, so for this experiment reduce complexity and elucidate the relevant differences between ERM and DRO.
analyze only the static supervised learning setting in order to
Our data is generated from bivariate Gaussian distributions and the label, y. of a given data point is 1 if the sum of its features are greater than the sum of the means of the two Gaussian distributions from which draw samples and 0 otherwise. As with the regression experiments, subgroups within our data, A and B. We vary the proportion of samples from each subgroup in the experiments. Precisely, the data generating process is as follows:
have two
XA ~ N(HA,
X N En)
X = CAXA + CB CA.CB E (0, and Ca + CB =
where
11 M
PB
Hg JB
Σ
[6]
0
ΣB
o 0
o
And for data point,
[x],
with E (),
0
if
if
x +
Hence, A * pn. the data is not linearly separable and the logistic regression model must trade off performance across the two subgroups. We provide scatter plots of samples from the data generating
24

---

Under review as a conference paper at ICLR 2023
Sample of Full Data by Label and Group
20
15
Label
0
X2
10
Group
A
0.5
0.0
0.00
0.25
0.50
0.75
100
125
150
1.75
X1
Figure 12:
Sample of 360 data points from the data generating distribution with Ca
0.8 and
CB 0.2.
Group
Group B
15
Label
10
0.0
0.5
1.0
1.5
20
0.
0.5
1.0
15
20
Figure 13: Sample of 600 data points from the data generating distribution with CA = 0.8 and
CB 0.2.
distribution below with P/ 1 and 1 0.7. 0' - 0.1 for i E 10, and ca 0.8, en = 0.2. Figure 12 contains a sample of 360 data points coloured by the value of their target variable, with crosses representing data points belonging to group B and circles representing data points belonging to group A. Figure 13 contains sample of 500 and 100 data points respectively from group A and group B coloured by the value their target variable.
In Figure 12 can see that the data is not linearly separable, some members of group B who belong to the positive class have features that place them lower than the threshold for positive clas- sification for group A. Although this dataset is extremely simple, it is characterized by feature that represents a central concern for faimess in machine learning, namely that the conditional probabil- ity distributions, ((y) are significantly different for distinct subsets of the data. This example
25

---

Under review as a conference paper at ICLR 2023
is intended to represent simplified abstract instance of population with majority and minority subgroups in order to see how the behaviour of ERM and DRO differ in this circumstance.
We generate three distinct datasets which to train algorithms, each made up of differing proportions of the two subgroups A and B. Each dataset contains a sample of 10,000 data points, with samples distributed according the values of сд and cp. The accuracy of the models on the three datasets is summarized in Tables 5] and 6 below. For both ERM and DRO we use L2-regularized logistic regression trained with stochastic gradient descent. The step-size for all algorithms is fixed at 0.05 and we train for 15,000 epochs.
Models trained with the distributionally robust objective have the additional complication that must specify value for the radius of the X²-divergence ball, i.e. The larger the value of p. the more we can expect a DRO model to differ from an ERM model because as the -i-divereence ball grows, the worst case distribution can be further and further from the data generating distribution. Conversely, in the limit as p -> O, we recover ERM as the -ivvergeee ball shrinks contain only the data generating distribution.
Choosing the value of p is a challenging decision, as the performance of a model varies significantly as p changes. If one has access to demographic information, it is possible to conduct grid search over possible / values in order to find a value that results a model with the desirable fairness properties. Doing this, however, largely defeats the purpose of DRO. As explained earlier, a central advantage to using DRO rather than some fairness constrained optimization technique is that DRO does not require access to demographic information. In this experiment dual formulation of DRO and set = 0.56. This value was chosen empirically to achieve relatively uniform accuracy across group A and group B for 80/20 split between the two subgroups. As the values of сл and en change, we can see that the performance of DRO changes for given value of 77 and hence p, as 17" depends on p.
work directly with the
Group
CC = 0.6, 0.4
CA = 0.8, CB = 0.2]
CA = 0.95, 0.05
A
0.797
0.907
0.966
B
0.701
0.652
0.592
All Data
0.759
0.856
0.948
Table 5: Accuracy by Group for ERM.
Group
CC = 0.6, = 0.4
CCA = 0.8, CB = 0.2]
CA
0.95,
0.05)
A
0.665
0.751
0.780
B
0.869
0.744
0.766
All Data
0.747
0.750
0.780
Table 6: Accuracy by Group for DRO.
We first examine the performance of ERM (Table 5 As the data is not linearly separable, ERM must learn decision boundary that trades off performance between the two subgroups. Because the ERM objective treats the loss on each data point equally, the model learns decision boundary that more accurate for the majority group than for the minority group. This discrepancy in accuracy of predictions worsens the smaller the majority group is. For instance, when 95% of the data comes from group A, the logistic regression model trained with an ERM objective achieves 96% accuracy on group A members, but only 59.2% accuracy group B members.
Models trained with DRO objective behave much differently. For the 80/20 split and 95/5 split, the DRO models learn relatively fair decision boundaries, effectively balancing performance on both subgroups A and B. For the 60/40 split, however, DRO actually learns a model that performs signifi- cantly better the minority group than the majority group. This model is in sense discriminatory against the majority group. This is the result of the radius of the 2 -diveeggee ball being too large and the model thus overly focusing on worst case distribution.
As mentioned above, the correct choice of p is not necessarily obvious, but it greatly impacts the performance of the model. Duchi al. provide some recommendations and heuristics for choosing
26

---

Under review as a conference paper at ICLR 2023
Group DRO Decision Boundary
Group with DRO Decision Boundary
25
25
2.0
1.0
10
05
0.5
0.
0.0
-0.5
-0.5
00
0.5
1.0
15
2.0
25
-05
X1
Figure 14: Group A, DRO.
Figure 15: Group B, DRO.
Group with Decision Boundary
Group with ERM Decision
2.
25
20
20-
0.0
-0.5
-0.5
1.0
Figure 16: Group ERM.
Figure 17: Group B, ERM.
Figure 18: Decision boundaries for ERM and DRO classifiers with samples from groups and with Ca 0.95 and en 0.05. Shading indicates predicted label and data point colour indicates true label.
values of p in Duchi & Namkoong (2021). Along with altering the value of p. one can change the f-divergence ball by varying the the value of k for f-divergences in the Cressie-Reat family. This has a similar effect to changing the value of p.
In Figures 14
15 16 and 17 plot data from groups A and B for data generated with Ca
0.95, CB 0.05 with the learned decision boundary from a DRO and ERM model, respectively, overlaid. The background shading indicates the predicted label with blue representing ý 0 and red representing ý = 1, while the colour of the data points indicate their true label.
Neither the regression the classification experiments in this section designed to be realistic representations of real-world applications, but rather are intended to provide simple setting in which investigate important differences in the behaviour of models trained with ERM versus DRO objectives. In the next section we investigate slightly more complex classification task in the performative prediction setting and examine how DRO and ERM may impact fairness considerations when deploying model influences the distribution on which it is making predictions.
A.6.3 FAIRNESS AND RDRO
The data generating process is follows:
XA NWHA, EA)
XB ~ N(uB, EB)
X CAXA + CB
CA.CH (0, and cB
27

---

Under review as a conference paper at ICLR 2023
where
PB
B
0
MA
BB
AA =
Σg
[B
10
10
And for a data point, x. = [xc
1/1 with E (A, B),
0
if x
10
S 1
+ p
10
y
if xt
For our experiment we set the parameters of the data generating process as
pA = "B- = 0.8,
d = 0.1
CA = 0.8
d = 0.1,
cB = 0.2.
These parameters were selected as an attempt to capture the notion that an underprivileged minority group may have features that make them appear to be less qualified, despite having the same propor- tion of qualified individuals as a dominant majority group. The data generating process obviously represents this at a high level of abstraction and is much less complex than most real-world applica- tions. With that said, we believe the data generating process effectively encapsulates this abstracted characteristic that is central to concerns for learning fair models. Examples of the type of situation that this experiment is intended represent are college admissions hiring, where underprivi- leged minority group may not, on average, have CVs that appear as impressive as their peers from the majority group due to lack of opportunity, but are nevertheless equally qualified for the school or job.
We once again examine a strategic classification scenario, as in experiment 1, but our data now contains subgroups, allowing us to analyze the impact of ERM and DRO on fairness and model performance in the performative setting. We examine four different distribution maps by varying the parameter E {0.01, 0.25, 0.5, 10} and set 5 of the 10 features to be strategic (i.e. manipulable).
For both ERM and DRO we train L2- 1.2-raularizeed logistic regression models with 0.0001. We use stochastic gradient descent with a fixed step-size of a = 0.2 and train for 8000 epochs on samples of 1,200 data points. We use a fixed radius p of the x² xi-diverge ball for DRO. All parameters were chosen empirically to give good performance on the base distribution.
First, we examine the convergence behaviour of both algorithms by plotting the normalized distance between successive iterates of the learned parameters, 6,, in Figures 19 and 20 We observe that ERM does not converge for any value of e, while DRO converges for only e 0.01. It is unclear why the algorithms do not converge for other values of e. The failure to converge could be related to using a fixed, rather than decaying step-size, or because the conditions for the contraction mapping not met (recall that the conditions sufficient, but not necessary for convergence of particular instance). For the three smaller values of e, both ERM and DRO converge to a small neighbourhood, whereas for e 10, neither ERM DRO exhibit any convergence.
To demonstrate the effect of the convergence, or lack thereof, of f on the model's performance, we plot the average supervised and performative L2-regularized binary cross-entropy loss for ERM and DRO for = 0.5 and e = 10 in Figure 21 The blue lines indicate the optimization phase and the green lines indicate the effect of the distribution shift after the classifier deployment. That is, the dots at the end of a green dotted line represent performative loss, while the dots at the end of a blue line represent supervised loss. In the plots we can see that even though ERM and DRO do not converge for = 0.5, the models quickly achieve relatively stable loss on the classification task. Note that the average 1.2-regularized binary cross-entropy loss the objective for which ERM optimizing, but not the objective for which DRO is optimizing.
Given that this experiment a balanced binary classification task, the metric in which we are prin- cipally interested is accuracy. Furthermore, as we are interested in comparing the faimess properties of DRO and ERM, it is important to analyze the performance of the models on the subgroups within the population, as well as the population as whole. In Figures 22 and 23 we plot the the accuracy of the two models for e = 0.5. We see that the performative accuracy of ERM initially degrades significantly, before quickly converging approximately 84% on the full population.
28

---

Under review as a conference paper at ICLR 2023
ERM Theta Gaps
10a
c-10++1 10++1-0rb 0
10
0.01
E 0.25
10
3 = 0.5
E 10.0
10-5
10
20
30
Iteration t
Figure 19: Plot of the normalized distance between successive values of for ERM.
DRO Theta Gaps
10-1
c. 1 0r12
E 0.01
0.25
10-3
E 0.5
E = 10.0
10-5
0
10
20
30
Iteration t
Figure 20: Plot of the normalized distance between successive values of for DRO.
Conversely, the performative accuracy for DRO is actually initially higher than the accuracy the distribution on which the model was trained, but it also converges relatively quickly to an accuracy of approximately 72.5% the full population. This optimization objective than ERM. The average cross-entropy loss acts as a surrogate loss for the 0-1 loss and hence aims maximize accuracy on the full dataset. The objective used for DRO focuses on the tails of the distribution and therefore does not maximize accuracy across the full dataset. The improvement of the DRO model's accuracy after the distribution shift not an inherent property of DRO, but rather is specific to this particular dataset and distribution map. We see in Figure 22 at iteration / that ERM also occasionally achieves better performance after distribution shift. In general, the improvement or degradation of accuracy depends the leamed parameters of the model. the distribution map. the data, and the loss function.
again due DRO having different
In Figure 25 we plot the accuracy of ERM and DRO for the subgroups A and B for 0.5. We can see from these plots that the fairness properties of ERM and DRO are preserved in the performative prediction setting.
ERM converges to an accuracy of approximately 90% on group A and only approximately 54% on group B. DRO, on the other hand, converges to much more equal accuracy across the two subgroups, achieving an accuracy of approximately 74% for group A and approximately 66% for group B. We summarize the accuracies to which ERM and DRO converge in Tables and g We do not include
29

---

Under review as a conference paper at ICLR 2023
LOSS
10
15
20
25
Iberstion
DRO Performetive Risk during eps=0.5
10
25
itoratiion
ERM Perfarmative Risk during eps-10
Loss
109
tteratio
DRO Performetive Risk during epp=10
Los5
109
6
10
1.
20
25
Berration
Figure 21: Plots of the average L22regularized binary cross-entropy supervised and performative loss.
30

---

Under review as a conference paper at ICLR 2023
0.85
Accuracy
0.70
5
10
15 Iteration
20
30
Figure 22: ERM
Accuracy during
0.76
0.75
Accurecy
0.74
0.73
0.72
10
15
20
30
lteration
Figure 23: DRO
Figure 24: ERM and DRO accuracy on the full population across successive iterations.
the accuracy for c = 10 because neither ERM nor DRO converged to a small enough neighbourhood, and therefore did not converge in accuracy. We that the algorithms converge to similar accuracy values for all the values of
This result, while perhaps not that surprising, important, demonstrates that not only does DRO exhibit similar convergence behaviour to ERM, but DRO converges to fair fixed points, whereas ERM converges discriminatory fixed points in the presence of heterogeneous data composed of minority and majority subgroups. Recall also that DRO is not given access to group information, but still learns to achieve more uniform performance across subgroups. as it is attempting to minimize 2 diviergee ball surrounding the the worst case loss across all probability distributions within the
data generating distribution.
ERM Performative Accuracy
Group
0.01
c 0.25
<= 0.5
A
0.893
0.896
0.898
B
0.540
0.540
0,540
All Data
0.834
0.837
0.838
Table 7: Accuracy by Group for ERM after 30 iterations.
A.7 FINAL THOUGHTS
We began this work with discussion of why research into fairness in machine learning is such an urgent issue and would like to reemphasize this point. Machine learning is no longer niche research area. It has become a fundamental driving force of the global economy and now attracts billions of dollars in investment around the Abdallat (202): Balakrishnan al. (002)) This
31

---

Under review as a conference paper at ICLR 2023
ERM Accuracy for group during aps-0.5
0.65
Aocuracy
0.70
DRO group during
0.79
Accuracy
0.77
76
0.74
5
10
15
20
30
Iteration
ERM Accuracy for group during aps=0.5
Accuracy
0.51
0.50
Accuracy group during ep5+0.5
0.67
0.06
0.65
0.64
0.62
10
13
20
25
30
leertion
Figure 25: ERM and DRO accuracy on subgroups A and B across successive iterations.
32

---

Under review as a conference paper at ICLR 2023
DRO Performative Accuracy
Group
0.01
6= 0.25
6= 0.5
0.687
0.710
0.738
B
0.670
0.660
0.660
All Data
0.684
0.701
0.725
Table 8: Accuracy by Group for DRO after 30 iterations.
change has resulted enormous opportunity for individuals with expertise machine learning and it appears that this trend will only increase in the coming years.
The reality, however, that this emergence of AI as an economic powerhouse has not occurred in particularly responsible manner. Machine learning researchers and engineers have benefited greatly from the investment Al and the community has a responsibility to ensure that the future development of the field aligns with and supports universal rights, freedoms, and values. Chief among these responsibilities is ensuring that the development and deployment of machine learning models do not harm the most vulnerable among us. We hope that this work contributes to this endeavor.
33


Reviews:
[{"review_id": "ysvXqnaAU0", "reviewer": "Reviewer_oy4Y", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper presents repeated distributionally robust optimization (RDRO), a theoretical framework that extends the performative prediction with distributionally robust optimization. The authors provide a convergence analysis of RDRO and empirically demonstrate its implications for fair ML.", "summary_of_the_review": "The paper is technically sound and well-written. However, the paper's novelty is unclear, and the presentation still needs improvement.", "strength_and_weaknesses": "Strengths:\n1. The paper is well-written and well-motivated. In particular, the paper clearly justifies the proposed method by listing the limitations of the prior methods.\n2. The high-level background knowledge of DRO and performative prediction is clear and easy to follow.\n3. The empirical results demonstrate the proposed method is effective in learning fair ML models.\n\nWeaknesses:\n1. The paper does not clearly state the technical novelty of the proposed method and misses some essential information when presenting the main results. For example, the authors state, \"The supremum over the uncertainty set introduces additional complications necessitating novel definitions and an *altered* proof for convergence to a performatively stable model.\" However, there are no details about the technical challenges until we dive into the proofs. I suggest the author provide some information in the main text as well. Besides, Definitions 3.5 and 3.6 seem incomplete, making it difficult to follow the proofs.\n2. Experiments are hard to read, especially for the introduction of strategic classification. I know little about strategic classification. Could you please provide more background information (e.g., feature-changing dynamics)? Besides, I am also interested to see some visualization of how the features change over time, given DRO and ERM.  \n3. Missing references to reinforcement learning and online learning for fairness. The authors mention bandits, reinforcement learning, and online learning in \"Conclusions .\"There is a line of work focused on long-term fairness in this area, to name a few [1-5].\n\n[1] Fairness in Reinforcement Learning\n\n[2] Algorithms for Fairness in Sequential Decision Making\n\n[3] Towards Return Parity in Markov Decision Processes\n\n[4] On preserving non-discrimination when combining expert advice\n\n[5]  Equal opportunity in online classification with partial feedback", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "nvkHMuT-U86", "reviewer": "Reviewer_EH8v", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies distributional robustness in the setting of performative prediction. Specifically, it proposes to use DRO with performative prediction as a way to ensure long-term fairness where the demographic information is not available beforehand. The paper further explicates the definitions, assumptions, and constructs require to perform repeated RM in this setting. It theoretically shows that the repeated DRO in this setting should converge under given conditions. It also experimentally shows the benefits of using this approach.", "summary_of_the_review": "I think the paper studies an interesting question and an interesting problem setup. It is cleanly written. But much remains to be discussed and shown than the present draft under considerations. It will be imperative to answer the questions in weakness to judge the value of the propositions.", "strength_and_weaknesses": "Strength:\n1. The problem of ensuring long-term fairness where the demographic information is not available, is an interesting and relevant problem.\n2. The idea of doing DRO in performative prediction is an intuitive and interesting problem to study.\n3. The paper presents the required definitions, assumptions, and background materials clearly and rigorously.\n4. The experiments show interesting benefits of performing RDRO.\n\nWeakness:\n1. The motivation and the proposition seem disconnected to me. Though the paper begins with the problem of ensuring long-term fairness without demographic info, I do not see explicitly any proof or discussion to connect them. For example, it would be interesting to know how does it relate or contradict existing fairness metrics. Or even if we learn a \\theta^t with RDRO, how much fairness violation it can induce in terms of any group fairness metric? How far or close the classifier learned with DRDO is with the fair classifiers learned using demographic information? As none of these pieces are available, it reads more like a DRO paper for performative predictions with some side-effects on fairness than a paper pointed to fairness. Please clarify if I miss any detail.\n2. The definitions and assumptions are mathematically clear. But some intuition or an example to comprehend them would be very helpful.\n3. The cost of RDRO wrt the performative prediction is not discussed. It would be nice to understand how hard/easy it is do RDRO than PP and what is the cost in terms of sample complexity.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "i0mfXq6Ehl4", "reviewer": "Reviewer_5ptm", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors address the problem of long-term fairness in the setting where the result of predicting impact the data distribution in a feedback loop. The authors extend the concept of performative prediction Perdomo et al. (2020) from purely empirical risk minimization settings to distributionally robust settings. The results show that in the long term, distributionally robust performative prediction achieves fairness even without knowing protective attributes. ", "summary_of_the_review": "Novel and sound paper with clear presentation.\nTherefore, I recommend acceptance.", "strength_and_weaknesses": "Strengths:\n- Novel idea on long-term fairness\n- Very interesting analysis of the behavior of performative prediction under distributionally robust optimization.\n- The benefits of the method are demonstrated for long-term fairness.\n\nWeakness:\n- I would suggest the author also compare the method with the standard group fairness model (any of them, preferably an in-processing model), to show that directly using this 'classical' fairness model will not perform well in the long term due to distribution shift, etc.\n- Can the author discuss the possibility that the fair distribution is not in the uncertainty set? How should \\rho be set such that the desired fair distribution is in the DRo's uncertainty set?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "-LKHX62uisv", "reviewer": "Reviewer_MxRz", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper lists four limitations of current fairness studies and proposes to address (some of) them by considering performative prediction with distributionally robust objectives.", "summary_of_the_review": "The paper lists four limitations of current fairness studies (which I hesitate to agree with in the current form), and proposes to address some of them via RDRO (which I am not sure how to parse its connection to previously listed limitations). The paper can benefit from content organizations, so that readers can understand how their presented results support their central claim.\n\n====Post Rebuttal====\n\nI acknowledge that I have read reviewers' comment, authors' responses, and have incorporated them in evaluation.", "strength_and_weaknesses": "## Strength\n\nThe paper makes an effort to reflect on previous fairness notions by listing four limitations of some previously proposed fairness notions. The paper also attempts to solve some of the aforementioned issues by considering performative prediction with distributionally robust objectives.\n\n## Weakness\n\n### 1. w.r.t. the listed four limitations\n\nI agree with authors that we need to reflect on previously proposed fairness notions. However, I do not agree with the way limitations are presented. For Limitation 1 (as they also acknowledged), there is no one-size-fits-all solution, therefore, we should not expect the equivalence between fairness notions in the first place, i.e., Limitation 1 is not problematic. For Limitation 2, fairness has actually been studied in dynamic settings, and fairness notions can be applied in the dynamic setting (e.g., the references in the survey paper by Zhang and Liu, 2020 \"Fairness in Learning-Based Sequential Decision Algorithms: A Survey\"). For Limitation 3, while an accurate estimation of fairness violation prefers the availability of demographic information, we can in certain cases make use of a subset (instead of the whole set) with ground truth to get accurate unfairness estimation. For Limitation 4, intersectionality is not ignored in more recent fairness notions, e.g., Fairness Gerrymandering characterized by Kearns et al., (2018), subgroup fairness definitions.\n\n### 2. the connection of presented RDRO results and the listed limitations\n\nWhile I understand the fact that the paper considers repeated distributionally robust optimization (RDRO) and presents convergence analysis, I am not sure how these results connect to the listed limitations of some previous fairness notions. In particular, how to parse those results in the context of long-term fairness, as claimed in the paper?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject