Model Transferability with Responsive Decision Subjects 
Authors: Yang Liu
Yatong Chen
Zeyu Tang
Kun Zhang
Venue: Submitted to ICLR 2023 (2023)
Keywords: transferability
responsive decision subjects
induced distribution shift
human-ML interaction
performance bound

Abstract: This paper studies model transferability when human decision subjects respond to a deployed machine learning model. In our setting, an agent or a user corresponds to a sample $(X,Y)$ drawn from a distribution $\mathcal{D}$ and will face a model $h$ and its classification result $h(X)$. Agents can modify $X$ to adapt to $h$, which will incur a distribution shift on $(X,Y)$. Therefore, when training $h$, the learner will need to consider the subsequently ``induced" distribution when the output model is deployed. Our formulation is motivated by applications where the deployed machine learning models interact with human agents, and will ultimately face \emph{responsive} and interactive data distributions. We formalize the discussions of the transferability of a model by studying how the model trained on the available source distribution (data) would translate to the performance on the induced domain. We provide both upper bounds for the performance gap due to the induced domain shift, as well as lower bound for the trade-offs that a classifier has to suffer on either the source training distribution or the induced target distribution. We provide further instantiated analysis for two popular domain adaptation settings with covariate shift and target shift.

Under review as a conference paper at ICLR 2023
MODEL TRANSFERABILITY WITH RESPONSIVE DECI- SION SUBJECTS
Anonymous authors Paper under double-bling review
ABSTRACT
This paper studies model transferability when human decision subjects respond a deployed machine learning model. In our setting, an agent or a user corresponds sample (X,, Y) drawn from a distribution D and will face a model h and its classification result (X)). Agents can modify X to adapt to h, which will incur a distribution shift on (X, Y). Therefore, when training h, the learner will need to consider the subsequently "induced" distribution when the output model is deployed. Our formulation is motivated by applications where the deployed machine learning models interact with human agents, and will ultimately face responsive and interactive data distributions. We formalize the discussions of the transferability of model by studying how the model trained on the available source distribution (data) would translate to the performance on the induced domain. We provide both upper bounds for the performance gap due the induced domain shift, as well as lower bounds for the trade-off's that a classifier has to suffer on either the source training distribution or the induced target distribution. We provide further instantiated analysis for two popular domain adaptation settings with covariate shift and target shift.
INTRODUCTION
Decision makers increasingly required be transparent their decision making to offer the "right to explanation" (Goodman & Flaxman 2017 Selbst & Powles 2018 Ustun et al. 2019 Being transparent also invites potential adaptations from the population, leading to potential shifts. We are motivated by settings where the deployed machine learning models interact with human agents, which will ultimately face data distributions that reflect how human agents respond to the models. For instance, when model is used to decide loan applications, candidates may adapt their features based on the model specification order to maximize their chances of approval; thus the loan decision classifier observes a data distribution caused by its own deployment (e.g., see Figure []] for a demonstration). Similar observations can be articulated for application in insurance sector (i.e. developing policy s.t. customers' behaviors might adapt to lower premium (Haghtalab et al. 2020 education sector (i.e. developing courses when students are less incentivized to cheat (Kleinberg & Raghavan 2020 and so on.
FEATURE
WEIGHT
OrigiNal VALUE
ADAPTED VALUE
Income
S 6,000
$6,000
Education Level
3
College
College
Debr
-10
$40,000
$20,000
Savings
$20,000
Figure 1: An example of an agent who originally has both savings and debt, observes that the classifier penalizes debt (weight - -10) more than it rewards savings (weight +5), and concludes that their most efficient adaptation is to use their savings to pay down their debt.
This paper investigates model transferability when the underlying distribution shift is induced by the deployed model. What we would like have is some guarantee on the transferability of classifier
See Appendix A.1 for more detailed discussions.

---

Under review as a conference paper at ICLR 2023
that is, how training on the available source distribution Dg translates to performance the induced domain D(h), which depends on the model being deployed. A key concept in our setting is the induced risk, defined the error model incurs on the distribution induced by itself:
Induced Risk (Ir == (h())))())))))))) YY)
(1)
Most relevant the above formulation is the strategic classification literature (Hardt et al. 2016a
Chen et al. 2020b). In this literature, agents are modeled as rational utility maximizers and game theoretical solutions were proposed to characterize the induced risk. However, our results are motivated by the following challenges in more general scenarios:
Modeling assumptions being restrictive In many practical situations, it is often hard to faithfully characterize agents' utilities. Furthermore, agents might not be fully rational when they response.
All the uncertainties can lead to far more complicated distribution change in (X, K, Y), as compared to often-made assumptions that agents only change X but not Y (Chen et al., 2020b).
Lack of access response data Another relevant literature to our work is performative prediction (Perdomo et al., 2020). In performative prediction, one would often require knowing (hh) or having samples observed from (hh) through repeated experiments. We posit that machine learning practitioners may only have access to data from the source distribution during training, and although they anticipate changes in the population due to human agents' responses, they cannot observe this new distribution until the model is actually deployed.
Retraining being costly Even when samples from the induced data distribution are available, retraining the model from scratch may be impractical due to computational constraints.
The above observations motivate us understand the transferability of model trained on the source data to the domain induced by the deployment of itself. We study several fundamental questions:
Source risk + Induced risk For a given model h, how different Err (h), the error on the distribution induced by h, from ErED, (h) := PD. (h(X) # Y), the error on the source?
Induced risk => Minimum induced risk How much higher is Erep()) (h), the error the induced distribution, than ming EITD( (h'), the minimum achievable induced error?
Induced risk of source optimal = Minimum induced risk Of particular interest, and special case of the above, how does Errp(ng) (hz), the induced error of the optimal model trained on the source distribution hig == arg mini Errp, (h), compare to h; :- arg min, ErTp(N) (h)?
Lower bound for learning tradeoffss What the minimum error a model must incur on either the source distribution E (h) or its induced distribution Err (h)?
For the first three questions, we prove upper bounds on the additional error incurred when a model trained on source distribution is transferred over to its induced domain. We also provide lower bounds for the trade-offs a classifier has to suffer on either the source training distribution or the induced target distribution. We then show how specialize our results to two popular domain
adaptation settings: covariate shift (Shimodaira) 2000 Zadrozny 2004 Sugiyama et al. 2007 2008
Zhang et al., (2013b and target shift (Lipton et al.) 2018 Guo al. 2020 Zhang et al. omitted proofs can be found in the Appendix.
2013b) All
1.1 RELATED WORKS
Most relevant us are three topics: strategic classification (Hardt al.) 201 6a; Chen et al., 2020b
Dekel et al., 2010: Dong et al. 2018 Chen et al.) 2020al MMller et al. [2020] Kleinberg & Raghavan
2020), a recently proposed notion of performative prediction (Perdomo al.
2020; Mendler- Dennner--ünner
et al. 2020), and domain adaptation (Jiang. 2008 BBe--David et al.) 2010: Sugiyama et al. 2008
Zhang et al. 2019 Kang et al. 2019 Zhang et al. 2020).
Hardt et al. (2016a) pioneered the formalization of strategic behavior in classification based on
a sequential two-player game between agents and classifiers. Subsequently, [Chnn et al. (2020b) addressed the question of repeatedly learning linear classifiers against agents who are strategically trying to game the deployed classifiers. Most of the existing literature focuses on finding the optimal classifier by assuming fully rational agents (and by characterizing the equilibrium response). In contrast, we do not make these assumptions and primarily study the transferability when only having knowledge of source data.
2

---

Under review as a conference paper at ICLR 2023
Our result was inspired by the transferability results in domain adaptations (Ben- David et al. 2010
Crammer et al. 2008 David et al., 2010). Later works examined specific domain adaptation models.
such as covariate shift (Shimodaira) 2000 Zadrozny 2004; Gretton et al. 2009; Sugiyyma et al.
2008; Zhang et al. 2013b a) and target/label shift (Lipton et al.) 2018) Azizzadeneshell et al., 2019). A commonly established solution is perform reweighted training on the source data, and robust and
efficient solutions have been developed to estimate the weights accurately (Sugiyama et al. 2008
Zhang al. 2013b a Lipton et al. 20188 Guo al. 2020
Our work, at the first sight, looks similar to several other area of studies, For instance, the notion of observing an "induced distribution" resembles similarity the adversarial machine learning literature (Lowd & Meek] 2005; Huang et al. [201]] Vorobeychik & Kantarcioglu (0188). One of the major differences between us and adversarial machine learning the true label Y stays the same for the attacked feature while in our paper, both X and Y might change in the adapted distribution D(h). In [ we provide detailed comparisons with some areas in domain adaptations, including domain generalization, adversarial attack and test-time adaptation. In particular, similar to domain generalization, one of the biggest challenge for our setting is the lack of access to data from the target distribution during training.
Appendix A.2]
2 FORMULATION
Suppose we are learning a parametric model h E H for a binary classification problem. Its training data set S := {2,, Yi 3 is drawn from a source distribution Ds, where v, E Rd and y: E {-1,+1) However, h will then be deployed in a setting where the samples come from a test or target distribution Dr that can differ substantially from Ds. Therefore instead of minimizing the prediction error on the source distribution ENTD, (h) == PDs (M(X) 4 Y), the goal is to find h- that minimizes Emp, (h) := PD, (h(X) * Y). This is often referred to as the domain adaptation problem, where typically, the transition from Ds to Dr is assumed to be independent of the model h being deployed.
We consider a setting in which the distribution shift depends on h, or is thought of as being induced by h. We will use (hh to denote the induced domain by h:
Ds encounters model h + D(h)
Strictly speaking, the induced distribution is function of both Ds and h and should be better denoted by (h).). To ease the notation, we will stick with Dhh), but we shall keep in mind of its dependency of Ds. For now, we do not restrict the dependency of D(h) of D and h, but later in Section and we will further instantiate D(h) under specific domain adaptation settings.
The challenge in the above setting is that when training h, the learner needs to earry the thoughts that D(h) should be the distribution it will be evaluated on and that the training cares about. Formally, we the 0-1 error on the distribution / induces:
define the induced risk of a classifier
Induced risk: (h) == PD. (h(X) # Y)
(2)
Denote by hr == arg min Errpay (h) the classifier with minimum induced risk. More generally, when the loss may not be the 0-1 loss, we define the induced l-risk
Induced f-risk:
Erre, (h) EZ-DO z)]
The induced risks will be the primary quantities that we are interested in minimizing. The following additional notation will also be helpful:
Distributions of Y on a distribution D: Dy = Po(Y = y and in particular Dy (h) == PD, (Y = v)-
Py = v), Dyis
Distribution of h on a distribution D: D/. : PD(h(X) y). and in particular Px(h) = (D(N) = y). DAis= := Pp. (h(X)= y).
Marginal distribution of X for a distribution D: Dx = PD (X = z). and in particular Dx Dx(h)= := (X = z), Dxis == PP3 (X = r
Total variation distance Ali & Silvey 1966): drv D == ;= -DP
"The ":=" defines the RHS as the probability measure function for the L.H.. For continuous X, the probability measure shall he read the density function.
3

---

Under review as a conference paper at ICLR 2023
2.1 EXAMPLES OF DISTRIBUTION SHIFTS INDUCED BY MODEL DEPLOYMENT
We provide two example models to demonstrate the use cases for the distribution shift models described in our paper. We provide more details in Section 4.3 and Section 5.3
Strategic Classification An example of distribution shift is when decision subjects perform strate- gic response to a decision rule. It is well-knoww that when human agents are subject to a decision rule, they will adapt their features as get favorable prediction outcome. In the literature of strategic classification, we say the human agents perform strategic adaptation (Hardt et al.) (016a).
It is natural to assume that the feature distribution before and after the human agents' best response satisfies covariate shiff:: namely the feature distribution P(X) will change, but X)) the mapping between Y and X, remain unchanged. Notice that this is different from the assumption made in the classic strategic classification setting Hardt et al. (a). which is to assume that the changes in the feature X does in feature X could potential lead to changes in the true qualification Y, and that the mapping between Y and X remains the same before and after the adaptation. This is a commonly assumption made in recent line of work on incentivizing improvement behaviors from human agents(see, e.g. Chen et al. (2020a): [hhviit et al.] (2020). We use Figure (Left) as a demonstration of how distribution might shift for strategic response setting. In Section verify our obtained results.
change the underlying true qua qualification Y. In paper, we assume that changes
we will use the strategic classification setup to
X
X
X
X;
X;
Figure 2: Example causal graph annotated to demonstrate covariate shift (Left) / target shift (Right) as result of the deployment of Grey nodes indicate observable variables and transparent nodes are not observed at the training stage. Red arrow emphasises h induces changes of certain variables.
Replicator Dynamics Replicator dynamics a commonly used model to study the evolution of an adopted "strategy" in evolutionary game theory (Tuyls et al. 2006 Friedman & Sinervo 2016 [Taylor & Jonker 1978, Raab & Liu, (202). j. The core notion of it is the growth or decline of the population of each strategy depends on its "fitness". Consider the label Y (-1, +1} as the strategy, and the following behavioral response model to capture the induced target shift:
PDN (Y = +1) Fitness(Y= = +1)
PD. (Y +1) Ep. [Fitness(Y))
In short, the change of the Y = +1 population depends on how predicting Y +1 "fits" a certain utility function. For instance, the "fitness" can take the form of the prediction accuracy of h for class +1: Fitness(Y = +1) == Pp. (h(X) +1|Y +1) Intuitively speaking, higher "fitness" describes more success of agents who adopted certain strategy (Y 1 or Y= +1). Therefore, agents will imitate replicate these successful peer agents by adopting the same strategy, resulting in an increase of the population (P (Y)). With assuming P(X stays unchanged, this instantiates one example of a specific induced target shift. We will specify the condition for target shift in demonstrating of how distribution might shift for the replicator dynamic setting. In Section 5.3] we will use a detailed replicator dynamics model to further instantiate results.
Section 5 We use Figure (Right)
TRANSFERABILITY OF LEARNING TO INDUCED DOMAINS
In this section, first provide upper bounds for the transfer error of classifier h (that is, the difference between (IT (h) and Errpy (h)), as well as between (I) (h) and (h+p()))()))) We
then provide lower bounds for max(Errp, (h), (h))))))))) that is, the minimum error a model must incur on either the source distribution Ds or the induced distribution (hh).
4

---

Under review as a conference paper at ICLR 2023
3.1 UPPER BOUND
We first investigate upper bounds for the transfer errors. We begin by showing generic bounds, and further instantiate the bound for specific domain adaptation settings in Section and We begin with answering central question domain adaptation:
How does model h trained on its training data set fare on the induced distribution D(h)?
To that end, define the minimum and h-dependent combined error of two distributions D and DD' as:
AD-D == min Err (h') + Errp(h), AD- (h) == Errp (h) + Errp(h)
A' E'EH
and H-divergennc as (D, D') = 2 s' (P)() + ('()))
I' (h()) N'(X))
The H-divergenne is celebrated measure proposed in the domain adaptation literature (Ben-David
et al. 2010) which will be useful for bounding the difference in errors of two classifiers. Repeating classical arguments from
et al. (2010), we can easily prove the following:
Theorem 3.1 (Source risk = Induced risk). The difference between Errp(m) (h) and ErrDs (h) upper bounded by: Err (h) & ErrD, (h) + >DS->D(N) + (Ddxx(Dss
The transferability of a model between Er (h) and Errp. (h) looks precisely the same as in the classical domain adaptation setting (Ben-David al.) 2010). Nonetheless, arguably more interesting quantity in our setting to understand is the difference between the induced error of a given model h and the error induced by the optimal model hy: (rrp()) (h) (Ir (hT). We get the following bound, which differs from the one in Theorem 3.1
Theorem 3.2 (Induced risk = Minimum induced risk). The difference between Err (h) and
( (he)) is upper bounded by: Err (h) E Ap( wwwpp/utttttttttoooooo Appu ((ng)( du XxxH d (D(G)), D(h)).
The above theorem informs that the induced transfer error is bounded by the "average" achievable error on both distributions D(h) and Dhhy,)), as well as the H x H divergence between the two distributions. Reflecting on the difference between the bounds of Theorem 3.1 and Theorem 3.2] we see that the primary change is replacing the minimum achievable error À with the average of X and A.
3.2 LOWER BOUND
Now provide lower bound on the induced transfer error. We particularly want to show that at least one of the two errors E (h). and (rTD( (h), must be lower-bounded by a certain quantity.
Theorem 3.3 (Lower bound for learning tradeoffs Any model h must incur the fol-
lowing error on either the source or induced distribution: max (h), Errpus)()) z (A)))
The proof leverages the triangle inequality of drv. This bound is dependent on h; however, by the data processing inequality of drv (and f f-divergence functions in general) (Liese & Vajda 2006), we have d (Dujs: (h)) s d Dx (h)). Applying this to Theorem 3.3 yields:
dn (d))
Corollary 3.4. For any model h, max(Errpas ( (r))())())) Z
2
3.3 HOw TO USE OUR BOUNDS
The upper and lower bounds we derived in the previous sections (Theorem 3.2 and Theorem 3.3 depend on the following two quantities either explicitly implicitly: 1) the distribution D(h) induced by the deployment of the model h in question, and 2) the optimal target classifier 17 as well as the distribution D(hī-) it induces. The bounds may therefore in reality we generally cannot compute D(h) without actual deployment, let alone compute hj. Thus in general it unclear how to compute the value of these bounds. Nevertheless, our bounds can still be useful and informative in the following ways:
be of only theoretical interest, since
General modeling framework with flexible hypothetical shifting models The bounds can be evaluated if the decision maker has a particular shift model in mind, which specifies how the population would adapt model. A common special case is when the decision maker posits
5

---

Under review as a conference paper at ICLR 2023
individual-lever agent response model (e.g. the strategic agent (Hardt et al. 201 demonstrate how to evaluate Section (.3). In these cases, the H H-divergence can be consistently estimated from finite samples of the population (Wang et al. 2005), allowing the decision maker to estimate the performance gap of a given h without deploying it. The general bounds provided can thus be viewed framework by which specialized, computationally tractable bounds be derived.
Estimate the optimal target classifier hi from set of imperfect models Secondly, when the decision maker has access to a set of imperfect models hn h2 .. hy E HT that will predict a range of possible shifted distribution D(h2), ... D(he) E D and a range of possibly optimal target distribution lur E H²" the bounds hi can be further instantiated by caleulating the worst case in this predicted set
( (h) (nr
max D'ED" MEET UpperBound(D"' Rt),
max(E (h), E )
min D'ED" MEET
LowerBound Rl).
facing in this paper also shed lights on the danger of directly applying existing standard domain adaptation techniques when the shifting is caused by the deployment of the classifier itself, since the bound will depend the resulting distribution as well. We add discussions on the tightness of our theoretical bounds in Appendix
In addition, the challenge
COVARIATE SHIFT
In this section, we focus on a particular domain adaptation setting known as covariate shift, in which the distribution of features changes, but the distribution of labels conditioned on features does not:
(Y = y X = x)) = PD. (Y = x|x = x), PD( = x) # PDg (X = x)
(3)
Thus with covariate shift, we have
PD( (X = x v.YYY. Y = y) -Pp() -V= = u|x =)) PDD() = =P = = x.) (P = x))
Let wz (h) = Pra) X
Tps (X=x) be the importance weight at v, which characterizes the amount of adapta-
tion induced by h at instance æ. Then for any loss function we have
Proposition 4.1 (Expected Loss on Dhh)). EDO (e(;; x, Y)] = EDg (h) 8(h;; x v)]-
The above derivation was not new and offered the basis for performing importance reweighting when learning under coviarate shift (Sugiyama al. 2008). The particular form informs that wy (h) controls the generation of (hh) and encodes its dependency of both Ds and h, and is critical for deriving our results below.
4.1 UPPER BOUND
We now derive upper bound for transferability under covariate shift. We will focus particularly on the optimal model trained on the source data Ds, which we denote as hig == arg min,e Errs(h). Recall that the classifier with minimum induced risk is denoted as h == arg min Err (h). We can upper bound the difference between h and hig. as follows:
Theorem 4.2 (Suboptimality of htz). Let X be distributed according Ds. We have:
Errpagg) (hi)) Errotn, (hT) ((T)) & / Erroy ((i.)) (v (VVar(wx(()))) + Varlwx(11)))
This result can be interpreted as follows: hiz incurs an irreducible amount of error on the source data set, represented by /Erry (ht,). Moreover, the difference in error between hys and hip is at its maximum when the two classifiers induce adaptations in "opposite" directions; this is represented by the sum of the standard deviations of their importance weights, / /Var(uxx (hz)) + Var(w> Var)w)(())))
Upud and LowerBound are the RHS expressions in Theorem 3.3 and Theorem 3.2

---

Under review as a conference paper at ICLR 2023
4.2 LOWER BOUND
Recall from Theorem 3.3 for the general setting, it is unclear whether the lower bound is strictly positive not. In this section, we provide further understanding for when the lower bound Pyy(Py)s.Py()))) (h)) s.. is indeed positive under covariate shift. Under several assump- tions, our previously provided lower bound in Theorem 3.3 is strictly positive with covariate shift. Assumption 4.3. (M). wx (A)]l 2 [ (N)_ wx(h)]l
where X4 (h) {z wa (2(h) (h) 2 }} and X- (h) {a: w. (h) < 1}.
This assumption states that increased wir (b) value points are more likely to have positive labels. Assumption 4.4. |Exex (N),(())=+1 [1 wx (1)]l 2 ExEx (0)A())=+][ wx (h)]l-
This assumption states that increased w (h) value points are more likely to be classified as positive.
Assumption 4.5. Cov (P = +1 z) - PDy (h(z)) = +1 2), we (h)) > 0.
This assumption is stating that for a classifier f, within all h(x) = +1 or h(X) = -1, a higher PD +1|X = z²) associates with higher (2).)).
Theorem 4.6. Assuming 4.3 4.5
the following lower bound strictly positive for covariate shift:
drv(Dris, Dy (r))) drv(Pris Pa(h)) > 0.
m (h), (r)) 2
2
4.3 EXAMPLE USING STRATEGIC CLASSIFICATION
As introduced in Section 2.1 we consider setting caused by strategic response in which agents are classified by and adapt to a binary threshold classifier. In particular, each agent is associated with a d dimensional continuous feature x E F and a binary true qualification y(z) E {-1, +1]. where y(xx) is a function of the feature vector x. Consistent with the literature in strategic classification (Hardt et al. 2016a), a simple case where after seeing the threshold binary decision rule h(x) = 111 2 Th
1, the agents will best response to it by maximizing the following utility function: u(x,,') = h(xa)- h(z)- -(2 z'), where c(x, x') is the cost function for decision subjects to modify their feature from to x'. We assume all agents are rational utility maximizers: they will only attempt to change their features when the benefit of manipulation is greater than the cost (i.e. when c(z,,') 2) and agent will not change their feature if they already accepted (i.e. h(x) +1). For given threshold Tn and manipulation budget B, the theoretical best response of an agent with original feature x: is: ((r) = arg max,' u(x,, x²) s.l. c(xx x²) B. To make the problem tractable and meaningful, we further specify the following setups:
Setup 1. (Initial Feature) Agents' initial features are uniformly distributed between [0, 1] E R'. Setup 2. (Agent's is Cost Function) The cost of changing from to a' is proportional to the distance between them: c(x, x') = || - ='|].
Setup 2 iimpies that only agents whose features are in between [Tr - Ty) will attempr to change their feature. We also assume that feature updates probabilistic, such that agents with features closer to the decision boundary Tı have a greater chance of updating their feature and each updated feature x' is sampled from a uniform distribution depending on Th, B, and (see Setup 3 & 4): Setup 3. (Agent's 's Success Manipulation Probability) For agents who attempt update their features, the probability a successful feature update is PiX' * X) = 1 [g-76|
B
Setup 4 (Adapted Feature's 's Distribution). An agent's updated feature x', given original x, manipula- tion budget B, and classification boundary 7k. is sampled X' Unif(Tn, TA + | x()-
Setup 4 aims to capture the fact that even though agent targets to change their feature to the decision boundary Th (i.e. the least cost action to get a favorable prediction outcome), they might end up reaching a feature that is beyond the decision boundary. With the above setups, we can specify the bound in Theorem 4.2 for the strategic response setting as follows:
Proposition 4.7 (Strategic Response Setting). Enr (hi) EEr S V Errd, (hip)-
We can see that the upper bound for strategic response depends on the manipulation budget B, and the error the ideal classifier made the source distribution Errp (ht,) This aligns with our intuition
7

---

Under review as a conference paper at ICLR 2023
that the smaller manipulation budget is, the less agents will change their features, thus leading to tighter upper bound on the difference between Errag (hg) and Errn; (hT.). This bound also allows us to bound this quantity even without the knowledge of the mapping between (4) and h, since we
can directly compute Errpy (ht) from the source distribution and an estimated optimal classifier hi-
5 TARGET SHIFT
We consider another popular domain adaptation setting known as targer shift, in which the distribution of labels changes, but the distribution of features conditioned on the label remains the same:
PD(C) (X = x|Y = y) = PD, (X = x|Y- = =y), PD = y) + PD3 (Y = y)
(4)
For binary classification, let p(h) == (1) (Y = +1), and (D) 11) = -ph).. Again,
p(h) encodes the induced adaptation from Ds and h. Then we have for any proper loss function E:
BD(a)le(M: X, Y)] =p(h- ED(A) (e(h; X, Y) +1] + (1 -(())) ( (e(h; X, X,Y)JY- = =
=p(h) ED, [e( X, F)ΙY = +1]+ (1- EDg f) = =-1]
ED le(;; X, Y)IV = +1]. Err_(h) = Epg [ X, Y = -1]. Note that Err, (h), Err (h) are both defined on the conditional source distribution, which is invariant under the target shift assumption.
We will adopt the following shorthands: Err, (h)
5.1 UPPER BOUND
We again upper bound the transferability of h& under target shift. Denote by D+ the positive label distribution on Ds (L'D, (X = x = +1)) and D_ the negative label distribution on Ds
(PDs (X x = -)). Letp
(Y=
Theorem 5.1. For target shift, the difference between Err (hi) and Errpuq, (h+p) bounds as: Erroeng) (his) E z (phhs) p(t)) (1 + p) (hb)) (ha)) (I D-
The above upper bound consists of two components. The first quantity captures the difference between the two induced distributions ((hg) and D(hg)). The second quantity characterizes the difference between the two classifiers his, hij on the source distribution.
5.2 LOWER BOUND
Now we discuss lower bounds. Denote by TPR s (h) and (h) the true positive and false positive rates of h on the source distribution Ds. We prove the following:
Theorem 5.2. For target shift, any model h must incur the following error on either Ds or D(h):
max[Errp, (h), Errpas (h)) > p(h) (1 (PRs(h) FPRs(h)))
2
The proof extends the bound of Theorem 3.3 by further explicating each of drv drv (Dy1s) (h)), (Pv(D Da, (h)) under the assumption of target shift. Since (T) FPR (h)) < unless we have a trivial classifier that has either TPR (h) = 1, FPRs (h) = or ( = 0, (h) = 1, the lower bound is strictly positive. Taking closer look, the lower bound is determined linearly by how much the label distribution shifts: p - (h). The difference further determined by the performance of h on the source distribution through 1 s (h)) For instance, when (h) > 5 (h), the quality becomes FNR (h) - FPRs that is the more error h makes, the larger the lower bound will be.
5.3 EXAMPLE USING REPLICATOR DYNAMICS
Let us instantiate the discussion using a specific fitness function for the replicator dynamics model (Section 2.1.. which is the prediction accuracy of h for class y/:
Fitness
v) == PD3 (h(X)= b/Y =
(5) Plugging
Then we have E Fitness = Emp, (h). and
p(h)
Proy +11+))
(Y++1)
1 1-E (h)
the result back to Theorem 5.1 we have
8

---

Under review as a conference paper at ICLR 2023
DXT
UR
10"1
Volue
10
10-2
Figure 3: Dilf := (rr g
(hgg) Ban y (b ). Max max gErro (MG)), (n (1 )), UB upper bound specified
compute and deploy the source optimal classifier Aig and update the credit score for each individual according to the received decision as the new reality for time step K = R
Theorem [42] and LB lower bound specified in Theoremf..0 For each time stop
Details the data generation again deferred to Appendix [
Proposition 5.3. Under the replicator dynamics model in Eqn. 21 (w(g)) - w(h-))) bounds as:
w(h)) - - PY +1) ErrD (h2) Errog (h+) (P (PR)s
Errps (1-Er (h')) (1 Errp, (hrp)(h;.))
That is, the difference between ErTD(N)) (hg) and (krg (ht) is further dependent on the difference between the two classifiers' performances on the source data Dş. This offers an opportunity to evaluate the possible error transferability using the source data only.
6 EXPERIMENTS
We perform synthetic experiments using real-world data to demonstrate our bounds. In particular, the FICO credit score data set (Board of Governors of the Federal Reserve System (US)
2007) which contains more than 300k records of Trans credit score of clients from different demographic groups. For our experiment on the preprocessed FICO data set (Hardt et al.! 2016b), we convert the cumulative distribution function (CDF) of TransRisk score among different groups into group-wise credit score densities, from which we generate balanced sample to represent population where groups have equal representations. We demonstrate the application of our results in a series of resource allocations. We consider the hypothesis class of threshold classifiers and treat the classification outcome as the decision received by individuals.
For each time step K k. we compute hig, the statistical optimal classifier on the source distribution (i.e.. the current reality for step K = k). and update the credit score for each individual according to the received decision as the new reality for time step K + Details of the data generation is again deferred to Appendix C We report our results in Figure We do observe positive gaps Errp(K3) (hg)) Drr ) (ftrr), indicating the suboptimality of training on Ds. The gaps are well bounded by the theoretical upper bound (UB), Our lower bounds (LB) do return meaningful positive gaps, demonstrating the trade-offs that a classifier has to suffer on either the source distribution or the induced target distribution.
Challenges in Minimizing Induced Risk and Concluding Remarks We presented a sequence of model transferability results for settings where agents will respond to a deployed model. The response leads to an induced distribution that the learner would not know before deploying the model. Our results cover for both a general response setting and for specific ones (covariate shift and target shift). Looking forward to solving the induced risk minimization, the literature of domain adaptation has provided us solutions to minimize the risk the target distribution via nicely developed set of results (Sugiyama et al.) 2008 2007 Shimodaira 2000). This allows us to extend the solutions to minimize the induced risk too. Nonetheless we will highlight additional computational challenges. Let's use the covariate shift setting. The scenario for target shift is similar. For covariate shift, recall
that earlier we derived the following fact:
(Importance Reweighting): ED(a) X, Y)] = (l) [(h; x, v)]
(6)
This formula informs us that a promising solution that uses w. wg(hh to perform reweighted ERM. There are two primary challenges when carrying out optimization of the above objective. Of course, the primary challenge that stands the way is how do we know wz (h). When one could build models to predict the response Dhh) and then w. (h) (e.g., using the replicator dynamics model as we introduced earlier), one could rework the above loss and apply standard gradient descent approaches. We provide concrete example and discussion in Appendix E Without making any assumptions on the mapping between h and D(h), one can only potentially rely on the bandit feedbacks from the decision subjects to estimate the influence of l on D(h)- we also laid out a possibility in Appendix E too. It can also be inferred from Eqn. (6) that the second challenge is the induced risk minimization might not even be convex- due to the limit of space, defer the detailed discussion again the Appendix D
9

---

Under review as a conference paper at ICLR 2023
7 ETHICAL STATEMENT
The primary goal of our study is to put human in the center when considering domain shift. The development of the paper is fully aware of any fairness concerns and we expect positive societal impact. Unawareness of the potential distribution shift might lead to unintended consequence when training a machine learning model. One goal of this paper is to raise awareness of this issue for a safe deployment of machine learning methods in high-stake societal applications.
subset of our results are developed under assumptions (e.g., Theorem 4.6). Therefore we want to caution readers of potential misinterpretation of applicability of the reported theoretical guarantees. Our contributions are mostly theoretical and our experiments use synthetic agent models to simulate distribution shift. A future direction is collect real human experiment data support the findings. Our paper ends with discussing the challenges in learning under the responding distribution and other objectives that might arise.
We believe this is promising research direction for the machine learning community, both as unaddressed technical problem and stepstone for putting human in the center when training machine learning model.
8 REPRODUCIBILITY STATEMENT
We provide the following checklist for the purpose of reproducibility:
Generals:
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you deseribe the limitations of your work? [Yes] We have stated our assumptions and limitations of the results. We also discussed the limitations in the conclusion.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] One of our work's goals is to raise awareness of this issue for a safe deployment of machine learning methods in high-stake societal applications. We discuss the potential misinterpretation of our results in conclusion.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] We present the complete proofs in the appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] We included experiment details in the appendix and submitted the implementation in the supplemen- tary materials.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e-g., with respect to the random seed after running experi- ments multiple times)? [N/A] In controlled experiment, we do not tune parameters and do not observe a significant variance in the results.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL? [No]
10

---

Under review as a conference paper at ICLR 2023
(d) Did you discuss whether and how consent obtained from people whose data you re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
REFERENCES
Syed Mumtaz Ali and Samuel D Silvey. A general class of coefficients of divergence of one distribution from another. Journal of the Royal Statistical Society: Series (Methodological), 28 (1):131-12,, 1966.
Kamyar Azizzadenesheli, Angi Liu, Fanny Yang, and Animashree Anandkumar. Regularizee learning for domain adaptation under label shifts. arXiv preprint (5ti:199330093444 2019.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Vaughan. A theory of learning from different domains. Machine Learning, 79:151-175, 2010.
Board of Governors of the Federal Reserve System (US). Report to the congress credit scoring and its effects on the availability and affordability of credit. Board of Governors the Federal Reserve System, 2007.
Anirban Chakraborty, Manaar Alam, Vishal Dey, Anupam Chattopadhyay, and Debdeep Mukhopad- hyay. Adversarial attacks and defences: A survey, 2018.
Yatong Chen, Jialu Wang, and Yang Liu. Strategic recourse in linear classification. arXiv preprint arXiv:2011.00355. 2020a.
Yiling Chen, Yang Liu, and Chara Podimata. Learning strategy-aware linear classifiers, 2020b.
Koby Crammer, Michael Kearns, and Jennifer Wortman. Learning from multiple sources. Journal of Machine Learning Research, 9(8), 2008.
Shai Ben David, Tyler Lu, Teresa Luu, and Dávid Pál. Impossibility theorems for domain adaptation. In Proceedings of the Thirteenth International Conference on Artificial Intelligncce and Statistics, pp. 129-136. JMLR Workshop and Conference Proceedings, 2010.
Ofer Dekel, Felix Fischer, and Ariel D. Procaccia. Incentive compatible regression learning. J. Comput. Syst. Sci., 76(8):759-77,, December 2010.
Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic clas- sification from revealed preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation, EC '1, pp. 55-70, New York, NY, USA. 2018, Association for Computing Machinery.
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without a gradient. arXiv preprint cs/0408007, 2004.
Daniel Friedman and Barry Sinervo. Evolutionary games in natural, social, and virtual worlds. Oxford University Press, 2016.
Mingming Gong, Kun Zhang, Tongliang Liu, Dacheng Tao, Clark Glymour, and Bernhard Schölkopf. Domain adaptation with conditional transferable components. In International conference on machine learning, pp. 2848. PMLR, 2016.

---

Under review as a conference paper at ICLR 2023
Bryce Goodman and Seth Flaxman. European union regulations algorithmic decision-man making and a "right to explanation". Al Magazine, 38(3):50-57, Oct 2017.
Arthur Gretton, Alex Smola, Jiayuan Huang, Marcel Schmittfull, Karsten Borgwardt, and Bernhard Schölkopf. Covariate shift by kernel mean matching. Dataset shift in machine leurning, 3(4):5, 2009.
Jiaxian Guo, Mingming Gong, Tongliang Liu, Kun Zhang, and Dacheng Tao. Ltf: A label transfor- mation framework for correcting label shift. In International Conference on Machine Learning, Pp. 3843-3853, PMLR, 2020.
Nika Haghtalab, Nicole Immorlica, Brendan Lucier, and Jack Z. Wang. Maximizing welfare with incentive-aware evaluation mechanisms. In Christian Bessiere (ed.), Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 160-166. International Joint Conferences Artificial Intelligence Organization, 2020. doi: 10.24963/ijcai.
2020/23, URL http:::t///oot org/10 2etp://....963/1111 //ijciiiicaaa/// 2020/23
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pp. 111-122, New York, NY, USA, 60, Association for Computing Machinery.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems, pp. 3315-3323, 2016b.
Ling Huang, Anthony Joseph, Blaine Nelson, Benjamin IP Rubinstein, and Doug Tygar. Ad- versarial machine learning. In ACM Workshop on Security and Artificial Intelligence, pp. 43-58, 2011.
Jing Jiang. A literature survey on domain adaptation of statistical classifiers. URL: http://sifaaa. cs.
uiuc. chujjjungguummmiiiloootttoourrr 3-1- 2008
Guoliang Kang, Lu Jiang, Yi Yang, and Alexander Hauptmann. Contrastive adaptation network for unsupervised domain adaptation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4892, 2019.
Jon Kleinberg and Manish Raghavan. How do classifiers induce agents to invest effort strategically? ACM Transactions on Economics and Computation (TEAC), 8(4):1-23, 2020.
Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy M. Hospedales. Learning to generalize: Meta- learning for domain generalization, 2017.
Friedrich Liese and Igor Vajda. On divergences and informations in statistics and information theory. IEEE Transactions Information Theory, 52(10):4394 4412, 2006.
Zachary Lipton, Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. In International conference on machine learning, pp. 3122-3130. PMLR, 2018.
Yang Liu and Mingyan Liu. An online learning approach to improving the quality of crowd-sourcing. ACM SIGMETRICS Performance Evaluation Review, 43(1):217-230, 2015.
Mingsheng Long. Han Zhu, Jianmin Wang, and Michael Jordan. Unsupervised domain adaptation with residual transfer networks. arXiv preprint arXiv: 1602. 2016.
Daniel Lowd and Christopher Meek. Adversarial learning. ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, pp. 641-647, 2005.
Celestine Mendler-Dünnnes Dünnne,, Juan Perdomo, Tijana Zmic, and Moritz Hardt. Stochastic optimization for performative prediction. In Advances in Neural Information Processing Systems, pp. 4929-49299 Curran Associates, Inc., 2020.
John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in disguise.
In International Conference on Machine Learning, pp. 6917-6926. PMLR, 2020.
12

---

Under review as a conference paper at ICLR 2023
Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation, 2013.
Zachary Nado, Shreyas Padhy, D. Sculley, Alexander D' Amour, Balaji Lakshminarayanan, and Jasper Snoek. Evaluating prediction-time batch normalization for robustness under covariate shift, 2021.
Nicolas Papernot, Patrick McDaniel, and Ian Goodfellow. Transferability in machine learning: from phenomena to black-box attacks using adversarial samples, 2016.
Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt. Performative prediction. In International Conference on Machine Learning, pp. 7599-7609. PMLR, 2020.
Reilly Raab and Yang Liu. Unintended selection: Persistent qualification rate disparities and interventions. Advances in Neural Information Processing Systems, 34, 2021.
Andrew Selbst and Julia Powles. "meaningful information" and the right to explanation. In Sorelle A. Friedler and Christo Wilson (eds.), Proceedings of the 1st Conference on Fairness, Accountability and T Transparency, volume 81 of Proceedings of Machine Learning Research, pp. 48 48. PMLR, 23 24 Feb 2018.
Yonadav Shavit, Benjamin Edelman, and Brian Axelrod. Causal strategic linear regression. In International Conference Machine Learning, pp. 8676-8686. PMLR, 2020.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of statistical planning and inference, 90(2):227-244, 2000.
Chuanbiao Song, Kun He, Liwei Wang, and John E. Hopcroft. Improving the generalization of adversarial training with domain adaptation, 2019.
Masashi Sugiyama, Matthias Krauledat, and Klaus-Robert Müller. Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research, 8(5), 2007.
Masashi Sugiyama, Taiji Suzuki, Shinichi Nakajima, Hisashi Kashima, Paul von Bünau, and Motoaki Kawanabe. Direct importance estimation for covariate shift adaptation. Annals of the Institute of Statistical Mathematics, 60(4):699-746, 2008.
Peter D. Taylor and Leo B. Jonker. Evolutionary stable strategies and game dynamics. Mathematical Biosciences, 40(1):145-156, 1978. ISSN 0025-5564.
Karl Tuyls, Pieter Jan'T 'T Hoen, and Bram Vanschoenwinkel. An evolutionary dynamical analysis of multi-agent learning in iterated games. Autonomous Agents and Mulli-Agent Systems, 12(1): 115-153, 2006.
Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Proceedings of the Conference on Fairness, Accountabiliry, and Transparency, pp. 10-19, 2019.
Thomas Varsavsky, Mauricio Orbes-Artcage Carole H. Sudre, Mark S. Graham, Parashkev Nachev, and M. Jorge Cardoso. Test-time unsupervised domain adaptation, 2020.
Yevgeniy Vorobeychik and Murat Kantarcioglu. Adversarial Machine Learning. Morgan & Claypool Publishers, 2018.
Dequan Wang, Evan Shelhamer, Shaoteng Liu, Bruno Olshausen, and Trevor Darrell. Tent: Fully test-time adaptation by entropy minimization, a.
Jindong Wang, Cuiling Lan, Chang Liu, Yidong Ouyang, Tao Qin, Wang Lu, Yiqiang Chen, Wenjun Zeng, and Philip S. Yu. Generalizing to unseen domains: A survey on domain generalization, 2021b.
Qing Wang, S.R. Kulkarni, and S. Verdu. Divergence estimation of continuous distributions based on data-dependent partitions. IEEE Transactions Information Theory, 51(9):3064-3074 2005. doi: 10.1109/TT..2005..0 853314.
Bianca Zadrozny. Learning and evaluating classifiers under sample selection bias. In Proceedings of the twenty-first international conference Machine learning, pp. 14,, 2004.
13

---

Under review as a conference paper at ICLR 2023
Kai Zhang, Vincent Zheng, Qiaojun Wang. James Kwok, Qiang Yang, and Ivan Marsic. Covariate shift hilbert space: A solution via surrogate kernels. In International Conference on Machine Learning, pp. 388 395. PMLR, 2013a.
Kun Zhang, Bernhard Schölkopf, Krikamol Muandet, and Zhikun Wang. Domain adaptation under target and conditional shift. In International Conference on Machine Learning, pp. 819-827.
PMLR, 2013b.
Kun Zhang. Mingming Gong, Petar Stojanov, Biwei Huang, QINGSONG LIU, and Clark Glymour. Domain adaptation as problem of inference on graphical models. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 4965 1965-4976. Curran Associates, Inc., 2020.
Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael Jordan. Bridging theory and algorithm for domain adaptation. In International Conference on Machine Learning, pp. 7404-7413 PMLR, 2019.
14

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
We arrange the appendix follows:
Appendix
provides some real life scenarios where transparent models are useful or required.
Appendix
provides comparisons of our setting and other sub-areas domain adaptation.
Appendix
provides proof for Theorem
Appendix
4
provides proof for Theorem 3.2
Appendix
provides proof of Theorem 3.3
Appendix A.6
provides proof for Proposition 4.1
Appendix
provides proof for Theorem
Appendix
provides proof for Theorem 4.6
Appendix
A.9
provides omitted assumptions and proof for Section 4.3
Appendix
A.
10
provides proof for Theorem 5.1
Appendix
A.
provides proof for Theorem B.1
Appendix provides proof for Proposition B.2
Appendix provides additional lower bound and examples for the target shift setting.
Appendix provides missing experimental results including new experimental results using synthetic datasets generated according to causal graphs defined in Figure 2 We also add additional experimental results on credit score data set.
Appendix discusses challenges in minimizing induced risk.
Appendix provides discussions how to directly minimize the induced risk.
Appendix provides discussions adding regularization to the objective function.
Appendix provides discussions on the tightness of our theoretical bounds.
A.1 EXAMPLE USAGES OF TRANSPARENT MODELS
As we mentioned in Section T there is an increasing requirement of making the decision rule to be transparent due to its potential consequences impacts individual decision subject. Here we provide the following reasons for using transparent models:
Government regulation may require the model to be transparent, especially in public services;
In some cases, companies may want to disclose their models so users will have explanations and are incentivized to better use the provided services.
Regardless of whether models are published voluntarily, model parameters can often be inferred via well-known query "attacks".
In addition, we name some concrete examples of some real-life applications:
Consider the Medicaid health insurance program in the United States, which serves low- income people. There is obligation provide transparency/discloss the rules (model to automate the decisions) that decide whether individuals qualify for the program in fact, most public services have "terms" that usually set stone and explained in the documentation. Agents can observe the rules and will adapt their profiles to be qualified if needed. For instance, an agent can decide to provide additional documentation they need to guarantee approval. For more applications along these lines, please refer to this repor(5)
Credit score companies directly publish their criteria for assessing credit risk scores. In loan application settings, companies actually have the incentive to release criteria to incentivize agents to meet their qualifications and use their services. Furthers. making decision models transparent will gain the trust of users.
15

---

Under review as a conference paper at ICLR 2023
It is also known that it is possible to steal model parameters, if agents have incentives to do sc For instance, spammers frequently infer detection mechanisms by sending different email variants; they then adjust their spam content accordingly.
A.2 COMPARISON OF OUR SETTING AND SOME AREAS IN DOMAIN ADAPTATION
We compare our setting (We address it as IDA, representing "induced domain adaptation") with the following areas:
Adversarial attack Chakraborty et al. (2018); Papernot et al. (2016); Song et al. (2019): 9): in adversarial attack, the true label Y stays the same for the attacked feature, while in IDA, we allow the true label change as well. One can think of adversarial attack as specific form of IDA where the induced distribution has a specific target, that is to maximize the classifier's s error by only perturbing/modifyy moni. Our transferability bound does, however, provide insights for how standard training results transfer to the attack setting.
Domain generalization Wang et al. (202 Li et al. (2017); Muandet et al. (2013): the goal of domain generalization is to learn model that can be generalized to any unseen distribution; Similar to our setting, one the biggest challenges domain generalization also the lack of target distribution during training. The major difference, however, is that focus is to understand how the performance of a classifier trained on the source distribution degrades when evaluated on the induced distribution (which depends how the population of decision subjects responds); this degradation depends on the classifier itself.
Test-time adaptation Varsavsky et al. (2020); Wang et al. (2021a); Nado et al. (202T): the issue of test-time adaptation falls into the classical domain adaptation setting where the adaptation is independent of the model being deployed. Applying this technique to solve our problem requires accessing data (either unsupervised supervised) drawn from D3 (h)
for each h being evaluated during different training epochs.
A.3 PROOF OF THEOREM 3.1
Proof. We first establish two lemmas that will be helpful for bounding the errors of pair of classifiers. Both are standard results from the domain adaption literature Ben- David et al. (2010).
Lemma A.1. For any hypotheses h, h/ E H and distributions D. D',
(D, D')
Errp (h, R/) Erro (h, (h, K') S
2
Proof. Define the-cross prediction disagreement between two classifiers h, ht' on distribution D as Er h²) == (x)( * h'(X)). By the definition of the H diverrgge
dHxH (D, D') = sup PD(h(X) # h'(x) Po (h(X) h'(X))
h.K'H
= 2 sup
EErp(h, h²' Erro (h, A'))
A.
2 2 (Err (h, h²) E Er,
Another helpful lemma for is the well-known fact that the 0-1 error obeys the triangle inequality (see, e.g.. Crammer et al. (2008):
Lemma A.2. For any distribution D over instances and any labeling functions fi. fa. and fa. have Errp(J1, S ErrD(Ji, + Errp(fzzJal
Denote by ht the ideal joint hypothesis, which minimizes the combined error:
h == arg min ErT (h') + Errps (h')
N'EW
16

---

Under review as a conference paper at ICLR 2023
We have:
(r)p(a)))) S E)TD()) (1²) + EOT (h, hi*)
(Lemma A.2
s Errp(yy))) (h²) + Er (h, h²) + [E (h, (h, - Errp, (h, h*)] 1
< (TT)())(H)) + EITDs (h) + EITDs (h") jd D(h))
(Lemma
EIrp, (h) ADg-DD( + (Ds:
(Definition of h*)
A.4
PROOF OF THEOREM 3.2
Proof. Invoking Theorem 3.1 and replacing with h7 and S with D(h7), we have
(rTp(s)(17)) < (MF) + AD())-D((N)) + 2 (D())) D()))
(7)
Now observe that
(M)) & (1T)) + EnT (h, 11))
s (hT)) + E (h, hT) + ErTD()) (b, - Err
< (TTp()(())) + E (h, h7) d (D( D(h)
(by Lemma A.I
Err + Em (b) + E (h7p) +
D(h))
(by Lemma A.2
< EII + (D(K)) + dx (D(h)), 2
((())) D(h))
(by equation
+ Errpon;) (h) + Errp(); (ht) 2 duxH n ((()),
Adding Er)D())) (h) to both sides and rearranging terms yields
2ErT (h) 2 (hā I HITD(N) (h) BrED(nz)))) (h) AD())-D(()) ddxx (D(()) D(h)
D(t (h) AD(M))>D(H)) + (Dx(())))) D(h))
Dividing both sides by 2 completes the proof.
A.5 PROOF OF THEOREM 3.3
Proof. Using the triangle inequality of drv, we have drv(Dr (h)) s drv div(D Dmis) + div(Dnjs: (h)) + Dy))
(8)
and by the definition of drv, the divergence term (Dv(D Dy (h)) becomes
dTv(Dy1s, Dujs) = IP = +1) - PD (1(x)) +1)1
EDş +1+1 ED, [h (X) +
2
2
EDs [Y]
EDS [X()]
2
1
EED ||Y h(x)
2
EmrDs (h)
Similarly, we have
(hv(Da(h), Dy ETrDON (h)
17

---

Under review as a conference paper at ICLR 2023
As result, we have
Errd, (h) + Errp(a) 2 drv(Dyiss drv((u(h)))))))))) Dy
2 Dy div (a(h))
(by equation g
which implies
(a (rrp)) (1) (D - dTv((niss (h))
2
A.6 Proof.
PROOF OF PROPOSITION 4.1
Ep(n)e((;;X)) Y)]
/ PD(M)XX Y = -))((h; x, v) drdy
/ (Y -y/ z)) -PD(N 2)((h;; x. y) drdy
/ PD y x) PD. (X =x) PD(M) (X x²)
PD (X = x) ((h,,r, v) drdy
f PDs = u|X = x) PD. =x) ww ((h;;,,)) dxdy
EED (h) f(h; x. y))
A.7 PROOF OF THEOREM 4.2
We start from the error induced by hg.. Let the average importance weight induced by hig be a(h') = ED, (hz)): we add and subtract this from the error:
Proof.
Err ) = EDS (wg( (x) + v)]
= =EDs (0hh) (1)((z) # v)] + ED, [(wa(h)) w(h3)) (((h)(z) + v)
In fact, ah3))= 1, since
a (hh)) =EDs (ww (h²)l = Ws (2 x)dx
/
(X = 2)) PDs (X= x)
Po, (X =x)dx= PDomn)XX=2)dd xx)x x)dx
Now consider any other classifier h. We have
Enrp(ng)
= ED, (1)(()) * v) + EDg [[ (hg) a(h))) ((1((x)) # +
< EDS [1((xx) # y)] + Epg (h5) ((h))) 1(hg(=)) # y)l
(by optimality of lis Ds)
= EEs (a(h) (x(x)) + +) + Eps [w (h3) - s(b))) 1(b3(z) + fy]
(multiply by @(h3) 1)
= =ED; [w,, (h) 1 (l)(z) # b) + Ep, ((@(h) 3 (h)) 1(h(x) + v)] (add and subtract a ((g))
Eps (13) - (bbg) 1(h5(x) + y)1
= ErTp( (h) + Cov (hz). (z)g(()) *)) Cov(ws 1(h(z) + v))
18

---

Under review as a conference paper at ICLR 2023
Moving the error terms to one side, have
(r)g(ng) (hg) - Errpoy) (h)
< Cov(w=(h3)) 1 (2) # v)) Cov(ws (1))2) + u))
S Var(w,, (hg)) Var(1 v))
(|Cov(XX, X)I S v V/a((X) VVr(Y)
+ v Var(w> (h)) Var (1(x) + y))
v Var(w,, (ht)) (hgs()))(L Errs (h))()))) + / Var(ww, Errp, (h)(1 Errps (h))
Var(ws (ht)) (hg) / Var(wax (h)) ErrD, (h)
(1 ErrD, (h) 1)
( (arlww + (Vrr(wsth))
S Errpy (h)
Since this holds for any h. it certainly holds for h = hī-
A.8 OMITTED ASSUMPTIONS AND PROOF OF THEOREM 4.6
Denote (h) {z (h) 2 1) and X-(h) {x : wa (h) 1}. First we observe that
S PDy =x)(1 wn (h))drr
PX x1(1 wrr (h))dd
This is simply because of I, PD, (X = =x) wa (h)dd = J. PD( (X = x)dx = 1.
Proof. Notice that in the setting of binary classification, we can write the total variation distance between Dyjs and (h) as the difference between the probability of Y = +1 and the probability of -1
drv (Dr1s (h))
PD = =+1) -PD(A)(Y = +1]
/ [Y =+1|X = x)) = =x)dx - / (Y = =1|X r)PDS (X x x) (1) do
S (V= x) x). - (h))ddd
Similarly we have
dryss (h())
//
(D)(((())= =
(X xx) (h))ddr (10)
19

---

Under review as a conference paper at ICLR 2023
We can further expand the total variation distance between Dyis and Dy (h) as follows:
drv(Dris, Dr (l))
/ |Y +1|X = D) (X x)- (1 wr (k))ddz)
1 PD(Y +1IX = r)Pps (X = 2) (1 ww (t
(b)
0
+
PDs (Y = +1|X = r x) (1-==(h)) (h)))
(-(
= =x) - ww (1))ddx { _x+(M) PDS = + = D) (X=
J PD = +1|X = PD (X (x= =x) (1 - W2 (h))dr
(by Assumption 4.3
(-)
PDS = (=====i ++|XX = x) (X = 2) (h) - 1)dr
x4(1)
+ +Ix x (h)
PDs (Y = +1|X = PDs (X x) (w)x() 1)dr
(by equation 9
-f +
z²) (w) 1)dr
Similarly, by assumption 4.4 and equation equation 10 we have
= (Pys PA = + = (x= = x) (w) - 1)dr
Thus bound the difference between dTv(Dr Dy (h)) and drv drv(PA)s. (h)) follows:
div(Dr|s: (h)) drv (i
= / PDo =
PY= +1|X = x) (X = z)- (h) - 1)dx
I |PD(M(() +1|X 2) (X 4) (wo 1)dx
= (V = +1|X = x) - PD. (1(z) = +1 + x = P) (X = x)) (wor (h) 1)dr
ED, (PDs (Y +1|X x) Po. (1()) +1|X = x)) (w) 1)]
(by Assumption 4.5
> ED, PD (Y = +1|X = 2) - (h(x) = +1|X = =w) -
=0
Combining the above with Theorem 3.3
we have
(ax(E ETTo())))))))))) drv div(Dris, Dy (h)) drv (n)h) >
2
A.9
OMITTED DETAILS FOR SECTION
With Setup 2
Setup we can further specify the important weight w. (h) for the strategic response
setting:
20

---

Under review as a conference paper at ICLR 2023
Lemma A.3. Recall the definition for the covariate shift important weight coefficient wg(h) (=))(X=z) (X=z) for our strategic response setting, we have,
00 Th B) a E Th B, Tn)
Th
(2(h)
B
(11)
(-x + Th +B),
x E Thi Th + B)
B
(hh + B, 1]
Proof for Lemma A.3
Proof. We discuss the induced distribution D(h) by cases:
For the features distributed between [0, Th B]: since we assume the agents are rational, under assumption 2 agents with feature that is smaller than [0, T B] will not perform any kinds of adaptations, and no other agents will adapt their features to this range of features either, so the distribution between [0, Th. [3] will remain the same before.
For the target distribution between [TA B, Th can be directly calculated from assumption
For distribution between [T,, + B), consider a particular feature x² E [Th, Th + B), under Setup we know its new distribution becomes:
Th-
PD(L) (x = x=)==) =1
B
dz
a= B
Th
+
1
=1+ s B B
dz
(-x" + Th + 2B)
B
For the target distribution between [r, B, 1]: under assumption 2 and we know that no agents will change their feature to this feature region. So the distribution between [TA + B, 1] remains the same the source distribution.
PD(n (X=)) TDy (X=x) the
Recall the definition for the covariate shift important weight coefficient wy(h) distribution of wn (h) after agents' strategic responding becomes:
[0, Th -B) and I E TT - -B, [T,, + B)
[Th + B, 1]
T
we (b) =
B
(12)
+ + 2B),
0,
otherwise
Proof for Proposition 4.7
Proof. According to Lemma A.3
compute the variance of (.) Var(w, (h))
E (w,, (hw)) - ((w, B. Then by plugging it to the general bound for Theorem 4.2 gives us the desirable result.
21

---

Under review as a conference paper at ICLR 2023
A.10 PROOF OF THEOREM 5.1
Proof. Defining p PD₂ (Y = +1), p(), = (D( (Y = +1), we have
(nrp( = -phh)) EIT ErT- (h3) + (1 (1- pp(h))) Eir (h3)
(by definitions of p(hg), Err (hg), and Err- (hg))
p P-ErT (hr) + (1 - p) Err (his) +(((h)) p) [Err, (hī) Err (ht)] (13)
We can expand (I) as follows:
p Err, (lig) + (1 p) Err_ (hi))
S p Em, (17)) + (1 p) Err- (h7)
(by optimality of hig Dz)
-p(h)) Em (17) + (1 - -p(1T)) Err (hT) + (p - p(h))) [Err (lig)) - Emr (h7.)
EnpoOg (17) (p- - p(h))) [Er, (h+) Em Em-()
Plugging this back into equation 13 we have
Erypagg) BrTp(n;)) (h7) s (p(hi)) (m Err (h:)] + (p - -0((p)))) (Err+(h7) EEr (17))
Notice that
0.r(Err+ Err (h)) -
0.5 --)))
= 0.5 -05 = +1|1 -1)
0.5 - Pp. (h(X) = +1)
where Du is distribution with uniform prior. Then
(p(h3) -p) p) [Err (hg) - Err (hg) = 2((hh)) - p) (0.5 PP, (M(X) = +1))
(p p(hh(()))))))) [Er (E) (hz-)) Err -h;.)) 2(p p(h))) (0.5 PD. PD. (h(X) +1))
Adding together these two equations yields
(p(hg) -
((fs))-r)(BBrr)) [Em (hg) - Err (p- [Err (hrr
- Err (hi.)
-(((h)) p) (0.5 - +1)) (ppp-(hpp)))) (0.5 PD. (lip(X) = +1))
= (p(h)) - p(h7)) - (1 +1) - p(hh)
(X) (x, +1))
+ 2p (Po,, (o) = =+1)
< (p(h3) (1+ (k)(()- +1) PPr, (Xi = +1)1)
+ + [FD. = =1) -P
Pr,, (h
= +1)]
(14)
Meanwhile,
- (1)()= < 0.5 100==+1(h((77) +1) - - +1)1
PPo (x5(X) (4, +1)
+ 0.5 PD PP = +1) PD = -11
0.5 (bg), + (T)) (L
(15)
Combining equation and equation
gives
(p(hş) - p(1))) (1 (1 2 PP,, (hr = +1) Pp, (17(() = +1)1)
2p PP,, (x)
(X) = +1)1
< 1p(h)) -1(hT)) (1 D,
(li)) +())))dvvll (dv((D(h))) D_ (b
+ -p- (p
< - (10)))))))0+0)000(((000(00001110
(Dv (hg), D_ (-()))
22

---

Under review as a conference paper at ICLR 2023
A.11 PROOF OF THEOREM B.1
We will make use of the following fact:
Lemma A.4. Under label shift, (P) = (P), and FP) - (b).
Proof. We have
(P) -PPM))((X) = +1|Y = +1)
/ PD(N(((X)) = +1, X z|Y +1)dr
= / [Poa)(((X) - +1|X = x,Y - ++1)PP(()) (X = x/Y = +1)dæ
/ [(h(()) +1)P (X =x +1)dr
= / I(b(z) = +1)Pps XX = =x = +1)dr
(by definition of label shift)
S PDz (h(X) +1|X Y - P)DP (X x|Y +1)dx
<TP
The argument for TPR; (h) = TPR (h) is analogous.
Now we proceed to prove the theorem.
Proof of Theorem B.7 In section 3.2 we showed general lower bound on the maximum of Erro, (h)
and Err (h):
drv(Dy1s: - (Pp Da(h))
max(E (h), EITD())()))
2
In the case of label shift, and by the definitions of and p(h),
drv drv(Dr Dy (h)) = [Pp, (Y = +1) (( (Y = +1)| 1pp- p(h)l
(16)
In addition, we have
DAss = Psss-Psh((X)) +1) (P)s(h) + (1 pp) FPRs(h)
(17)
Similarly
(h) PD(()) (h(X) +1)
p(h)- TPR, + (1 - (hh)) (h) = p(h) (h)s(h) + (1 -p(h)) (PRs(h)
(by Lemma A.4
(18)
Therefore
drv (n)) -PPy(((()) = -1) (Mx)) = +1)|
=I(p - ((h)) TP)s(A) + (p(h) -p) (P)
(By equation 18 and equation 17
=Ip p(h) (TPRs FPRs(h))
(19)
which yields:
(iv(Dris, Dy Dy (h)) drv(Pn)s: Di(h)) 1p- p(h)](1 (P) (h)
(By equation 16 and equation 19
completing the proof.
23

---

Under review as a conference paper at ICLR 2023
A.12
PROOF OF PROPOSITION B.2 B.2
Proof.
1
(p(hg) p(h7)] PDs (Y +1)
(1 ErrD, (h3)) (hg) (1 EIr, (TRR
(1 Errps (hg)) (1 Brrpg (hi))
EITp, (hī) EIT,, (hT))l (T - TPRs (h
(20)
Errp, (ht)) (1 Errp, (h7-))
The inequality above is due to Lemma of Liu & Liu (2015).
B LOWER BOUND AND EXAMPLE FOR TARGET SHIFT
B. LOWER BOUND
Now we discuss lower bounds. Denote by sPRs (h) and (P) the true positive and false positive rates of h on the source distribution Ds. We prove the following:
Theorem B.1. Under target shift, any model h must incur the following error either the Ds or D(h):
[ (h), Errpas(())
1p 1p-p(h)
-FPR))(()))))()))
2
The proof extends the bound of Theorem 3.3 by further explicating each of dTv Dy (h))),. drv(Da and Dr (h)) under the assumption of target shift. Since (h) 5 < 0 unless TPR; (h) 0, (h) the lower bound strictly positive. Taking a closer look, the lower bound is determined linearly by how much the label distribution shifts: p p(h). The difference further determined by the performance of on the source distribution through 1 - s (h) s For instance, when (h) FPRs (h). the quality becomes FNR (h) FPR that is the more error h makes, the larger the lower bound will be.
we have trivial classifier that has either 5 1, (h)
B.2 EXAMPLE USING REPLICATOR DYNAMICS
Let us instantiate discussion using a specific fitness function for the replicator dynamics model (Section) 2.1. which is the prediction accuracy of h for class +1:
Fitness of Y = +1] = FD (h(X) = +1|Y = +1)
(21)
Then we have E Fitness of Y| = Emt,, (h), and
p(h)
PD. (h(X) = +1|+=++1+ +1)
PD. (Y = +1)
Emr, (h)
Plugging the result back our Theorem 5.1 we have Proposition B.2. Under the replicator dynamics model in Eqn. as:
21
(p(hi) p(h7)) p(rt)) bounds
(p(h3) p(h))))))))))))))()))))) PP PD = +1)
ErrDy (h3) Erro. (hi | TPRs(hi))
Errps (h3) . ErrDs (hip))
That is, the difference between Errp(N)) (hg) and Err (hz) is further dependent on the difference between the two classifiers' performances on the source data Dz. This offers an opportunity to evaluate the possible error transferability using the source data only.
24

---

Under review as a conference paper at ICLR 2023
C MISSING EXPERIMENTAL DETAILS
C.I SYNTHETIC EXPERIMENTS USING DAG
Synthetic experiments using simulated data We generate synthetic data sets from structural equation models described on simple causal DAG in F for covariate shift and target shift. To generate the induced distribution Dhh), posit specific adaptation function A R H + Rd so that when an input & encounters classifier h E H. its induced features are precisely x' A (r. h). We provide details of the data generation processes and adaptation functions in Appendix
We take our training data set (.i,...,, Fnf and learn a "base" logistic regression model ((x)) = o w [0, 1]}, where (+r()) = 2 [a xx) > 1. To compute hg, the model that performs best on the source distribution, we simply vary and take the h, with lowest prediction error. Then, we posit specific adaptation function (xx h,). Finally, to compute h we vary from 0 to 1 and find the classifier h, that minimizes the prediction error on its induced data (A(x1, h .... ( h,)). We report our results in Figure
We then consider the hypothesis class H (/r
10-1
x
Value
10"2
10-1
UB
CS1
CS2
T51
T52
CS1
CS2
TS1
TS2
Datasets
Datasets
Figure 4: Results for synthetic experiments on simulated and real-world data. Diff == E)yg(g)) (ht) (hz)). UB == upper bound specified in Theo-
ErT (h Max == max ( (hi-.), EIT (
rem 4.2 and LB == lower bound specified in Theorem 4.6
Covariate Shift
We specify the causal DAG for covariate shift setting in the following way:
X1 Unif(-1,1)
X2 1.2X, (V( o
X3 ~x? + (N(0
Y = 2sign X2 > 0) -
where o3 and o3 are parameters of our choices. Adaptation function We assume the new distribution of feature Xi will be generated in the following way:
X A(X) = X1 c (h(X) -
where E R > is the parameter controlling how much the prediction 1((X) affect the generating of X namely the magnitude of distribution shift. Intuitively, this adaptation function means that if
feature x is predicted to be positive (h(x:) +1), then decision subjects are more likely to adapt to that feature in the induced distribution; Otherwise, decision subjects are more likely to be moving away from z since they know it will lead to negative prediction.
Target Shift
We specify the causal DAG for target shift setting in the following way:
(Y + 1)/2 ~ Bernoulliaa)
X, Y = y ~ (1, (²))
X; 0.8.1 + +0
X: 0.2Y + 0(0,
7a(-) is the logistic function and R denotes the weights.
25

---

Under review as a conference paper at ICLR 2023
where 1f represents truncated Gaussian distribution taken value between and 1. a, My o².0 and o3 are parameters of our choices. Adaptation function We assume the new distribution of the qualification y" will be updated in the following way:
P(Y = (X) = h Y = y) = Chy, where (h,y) v) E (-1,+1)
where 0 I Chy E RR < represents the likelihood for person with original qualification Y and get predicted as h(X) h to be qualified in the next step (Y' +1).
Discussion of the Results For all four datasets, we do observe positive gaps Erg (ht) EIT pngg (h indicating the suboptimality of training on Ds. The gaps are well bounded by the theoretical results. For lower bound, the empirical observation and the theoretical bounds are roughly within the same magnitude except for one target shift dataset, indicating the effectiveness of our theoretical result. For upper bound, for target shift, the empirical observations are well within the same magnitude of the theoretical bounds while the results for the covariate shift are relatively loose.
C.2 SYNTHETIC EXPERIMENTS USING REAL-WORLD DATA
On the preprocessed FICO credit score data (Board of Governors of the Federal Reserve System (US) 2007 Hardt et al. 2016b). we convert the cumulative distribution function (CDF) of TransRisk score among demographic groups (denoted A, including Black, Asian, Hispanic, and White) into group-dependent densities of the credit score. We then generate a balanced sample where each group has equal representation, with credit scores (denoted as Q) initialized by sampling from the corresponding group- deueddetnnddnt density. The value of attributes for each data point is then updated under a specified dynamics (detailed Appendix C.2.I to model the real-world scenario of repeated resource allocation (with decision denoted as D).
C.2.1 PARAMETERS FOR DYNAMICS
Since we are considering the dynamic setting, we further specify the data generating process in the following way (from time step f to = 1):
X1,1 ~ 1.5Q: + [1,
X1,2 0.8., + 62-
X1,3 A, +V
Y, ~ Bernoulli(g)) for given value of Qe = 4
D. fe(A,, X X Xt,3)
Q+11 = {Q; [1 + aD(D,) + ay (Y)()))oo.))
4 = A, (fixed population)
where (:) represents truncated value between the interval (0, 1]. fe()) represents the decision policy from input features, and 62,62,0 a are parameters of choices. In our experiments, we set
G = 62 62 =
0.1.
Within the same time step, i.e., for variables that share the subscript t, Qs and A, are root causes for all other variables (X,,1, Xx,2, Dr, Yt). At each time step T = I, the institution first estimates the credit score Q, (which is not directly visible to the institution, but is reflected in the visible outcome label Yλ based on (AG,
Xx,2,XX,3)) X1,3), then produces the binary decision D; according to the optimal threshold (in terms of the accuracy).
For different time steps, c.g., from T' to T' = f++1, 1, the new distribution at T f++1 is induced by the deployment of the decision policy D,. Such impact is modeled by multiplicative update in Q from Q with parameters (or functions) (.))) and ay (-) that depend on D, and Y,, respectively. In experiments,
a 0.01 and ay 0.005 to capture the scenario where one-step influence of the decision on the credit score is stronger than that for ground truth label.
26

---

Under review as a conference paper at ICLR 2023
10-1
Value
Value
10-3
10-2
3
4
2
3
5
K
L1 penalty, strong regularization strength.
(b) L1 penalty, strong regularization strength.
Max
Diff
10-1
LB
10-1
US
Value
Value
10
0
3
5
K
(c) L1 penalty, medium regularization strength.
(d) L1 penalty, medium regularization strength.
Max
10-1
10
UB
Value
Value
10-2
3
K
K
(e) penalty, weak regularization strength.
(f) L1 penalty, weak regularization strength.
Figure 5: Results of applying L1 penalty with different strength when constructing hi- The left column consisting of panels (a), (c), and (e) compares Max :=
max (hz Errp (hr)) and LB lower bound specified in Theorem 4.6 The
right column consisting panels (b), (d), and (f) compares Diff Err (hg)
For each time step K = k, compute and deploy the source optimal classifier n and update the credit score for each individual according to the received decision as the new reality for time step K 1.
Err and UB = upper bound specified in Theorem
C.2.2 ADDITIONAL EXPERIMENTAL RESULTS
In this section, we present additional experimental results on the real-world FICO credit score data With the initialization of the distribution of credit score Q and the specified dynamics, we present results comparing the influence of vanilla regularization terms in decision decision-making (when estimating the credit score Q) on the calculation of bounds for induced risks R In particular, we consider L1 norm (Figure 5 and L2 norm (Figure 6) regularization terms when optimizing decision-makin policies on the source domain.
we can see from the results, applying vanilla regularization terms (e.g., L1 norm and L2 norm) on source domain without specific considerations of the inducing- risk mechanism does not provide significant performance improvement terms of smaller induced risk. For example, there is no significant decrease of the term Diff as the regularization strength increases, for both L1 norm (Figure and L2 norm (Figure 6p regularization terms.
"The regularization that involves induced risk considerations will be discussed in Appendix
27

---

Under review as a conference paper at ICLR 2023
10-1
10-1
UB
Value
10
10-2
10
3
4
0
2
3
5
K
L2 penalty, strong regularization strength.
(b) L2 penalty, strong regularization strength.
10-1
Max
10
Diff
LB
UB.
Value
Value
10-7
10-2
10-3
0
3
5
K
(c) L2 penalty, medium regularization strength.
(d) L2 penalty, medium regularization strength.
10
Max
10
UB
Value
Value
10-²
10"3
3
K
K
(e) penalty, weak regularization strength.
(f) L2 penalty, weak regularization strength.
Figure 6: Results of applying L2 penalty with different strength when constructing hg- The left column consisting of panels (a), (c), and (e) compares Max :=
max (hz Errp(r (hr)) and LB lower bound specified in Theorem 4.6 The
right column consisting panels (b), (d), and (f) compares Diff Err (hg)
For each time step K = k, compute and deploy the source optimal classifier n and update the credit score for each individual according to the received decision as the new reality for time step K 1.
Errp(n;))hh) and UB = upper bound specified in Theorem
D CHALLENGES IN MINIMIZING INDUCED RISK
D. COMPUTATIONAL CHALLENGES
The literature of domain adaptation has provided us solutions to minimize the risk on the target distribution via nicely developed set of results (Sugiyama et al. (2008 2007); Shimodaira (2000). This allows us extend the solutions minimize the induced risk too. Nonetheless we will highlight additional computational challenges.
We focus on the covariate shift setting. The scenario for target shift is similar. For covariate shift, recall that earlier we derived the following fact:
ED (6 X)] EEl (h) E(h; v)]
This formula informs that a promising solution that uses W2 (h) to perform reweighted ERM. Of course, the primary challenge that stands the way how do we know Wn (h). There are different methods proposed in the literature to estimate (h) when one has access D(h) Zhang et al. (2013b); Long et al. (0016); Gong et al. (2016). How any of the specific techniques work in our induced domain adaptation setting will be left for more thorough future study. In this section, we focus on explaining the computational challenges even when such knowledge of w. (h) can be obtained for each model being considered during training.
28

---

Under review as a conference paper at ICLR 2023
Though wz (k), ((h; x. y) might both be convex with respect to (the output of) the classifier h, their product is not necessarily convex. Consider the following example:
Example (w2, (h) ((;; x, y) is generally non-convex). Let X' = (0, 1]. Let the true label of each I E X' be y(z) = 1 (a 2 2)- Let E(;; x. y) = } (h(z) - y)², and let h(x) = x (simple linear model). Notice that l is convex in h. Let DD be the uniform distribution, whose density function is
fD (1, 0< Notice that if the training data is drawn from D, then / is the linear classifier
00 otherwise
that minimizes the expected loss. Suppose that, since rewards large values of æ, induces decision subjects to shift towards higher feature values. In particular, let ((h) have density function
22x, 10
0 << S
fD(M)
otherwise
Then for all x E X, wn (h) [oma)(a) Io(a)
2r. Notice that wa (h) 2x is convex in h(x) x. Then
1 (h(x)) y)²
wr (h) E(h; x.y) = =2x
2
Sax²
0 < x <
z(x y)²
[x(x 11)2,
1 S x <
which is clearly non-convex.
Nonetheless, we provide sufficient conditions under which (h) E(h;; x. y) is in fact convex:
Proposition D.1. Suppose (h) and E(h; x. z) are both convex in h, and wy(h) and E(h; x. y)
satisfy vh, hi, y: (h) wa(h)) (,(h; v) - E(h'; (2,)),))))))) v)) 2 0. Then (h) 2(h;,,y) v) is convex.
Proof. Let us use the shorthand (h) := w (h) and E(h) := E(h; x. v). To show that (h) ((h) is convex, it suffices to show that for any E [0, 1] and any two hypotheses h. h' we have
w(a- - h + (1 a)) aa- h²)
E(a 4+ (1 a) h²) a w() E(h) + (1 a) w(h') E(h')
By the convexity of w.
w(a + (1 S a w()) + a1 - w(h)
and by the convexity of
l(a h + (1-
S (1-
a) e(h')
Therefore it suffices to show that
[a (h) + (1 - whh)] (a E(h) + (1 a) [(()) ((()) (1 (1) w(h)) ((h)) s + a(a - 1) (h))((h) - aaa 1) (wh)e(())) + -(e 0
+ a(a - 1) (w(h)) - -(H)) ((h)) <
+ (w(h) - ((h)) -
By the assumed condition, the left-hand side is indeed non-negative, which proves the claim.
This condition is intuitive when each x belongs to a rational agent who responds to a classifier h to maximize her chance of being classified +1: For y +1, the higher loss point corresponds the ones that are close to decision boundary, therefore, more -1 negative label points might shift to it, resulting to larger Wn (h). For y = 1, the higher loss point corresponds the ones that are likely mis-classified as +1, which "attracts" instances to deviate to.
D.2 CHALLENGES DUE TO THE LACK OF ACCESS TO DATA
We discuss the challenges in performing induced domain adaptation. In the standard domain adap- tation settings, one often assumes the access sample set of X, which already poses challenges
29

---

Under review as a conference paper at ICLR 2023
when there is access label Y after the adaptation. Nonetheless, the literature has observed fruitful development of solutions SSugiyama et al. (2008); Zhang et al. (2013)): Gong et al. (2016).
One might think the above idea can be applied to our IDA setting rather straightforwardly by assuming observing samples from Dhh,, the induced distribution under each model & during the training. However, often do not know precisely how the distribution would shift under model until we deploy it. This is particularly true when the distribution shifts are caused by human responding model. Therefore, the ability to "predict" accurately how samples "react" to h plays a very important role Ustun et al. (2019). Indeed, the strategic classification literature enables this capability by assuming full rational human agents. For more general setting, building robust domain adaptation tools that are resistant to the above "prediction error" is also going to be crucial criterion.
E DISCUSSIONS ON PERFORMING DIRECT INDUCED RISK MINIMIZATION
In this section, we provide discussions on how to directly perform induced risk minimization for our induced domain adaptation setting. We first provide a gradient descent based method for particular label shift setting where the underlying dynamic is replicator dynamic described in Section 5.3 Then propose solution for more general induced domain adaptation setting where we do not make any particular assumptions on the undelying distribution shift model.
F. GRADIENT DESCENT BASED METHOD
Here provide a toy example of performing direct induced risk minimization under the assumption of label shift with underlying dynamics as the replicator dynamics described in Section 5.3
Setting Consider simple setting in which each decision subject is associated with 1-dimensional continuous feature x E R and a binary true qualification y E {-1,+1}. We assume label shift setting, and the underlying population dynamic evolves the replicator dynamic setting described in Section 5.3 We consider simple threshold classifier, where Ý = h(x) 1[X 2 0). meaning that the classifier is completely characterized by the threshold parameter 6. Below we will use Y and I(X) interchangeably to represent the classification outcome. Recall that the replicator dynamics is specified as follows:
P PD (Y = Fitness Y = =
(22)
PD. (Y = y) ED. Fitness Y)]
where Ds [Fitness(Y)] Fitness(Y p) (Y y) + Fitness(Y -1 Po. (Y g)). Fitness(Y y y) is the fitness of strategy Y = which is further defined in terms of the expected utility U a of each qualification- citctattionllsssfiaatiino outcome pair (y. 0):
Fitness(Y =y)
Σ plV Y = Up.
where Un. the utility (or reward) for each qualification-clasifcaall outcome combination.P(XI] =y) is sampled according to Gaussian distribution, and will be unchanged since we consider a label shift setting.
We initialize the distributions we specify the initial qualification rate PD. (Y = +1). To test different settings, we vary the specification of the utility matrix Uy. and generate different dynamics.
Formulate the induced risk as a function of h To minimize the induced risk, we first formulate the induced risk as a function the classifier h's parameter 0 taking into account the underlying dynamic, and then perform gradient descent to solve for locally optimal classifier hī-
Recall from Section 5 under label shift, we can rewrite the induced risk as the following form: EDD,) (oon)]((h;x,,, X, Y) =p(h) EDS [6(,; ( X, Y)jY +1] + (L (1- p(h)) ED3 [6 X, X, -1]
where p(h) = (()) (Y = +1).
Since Ep, [[(: YY
+1] and Ep, [e(h; X)) Y -1] are already functions of both h and Ds. it suffices to show that the accuracy on D(h), p(h) = PD(1) (Y = =11, can also be expressed as function of and Ds-
30

---

Under review as a conference paper at ICLR 2023
To this, recall that for threshold classifier Y 1[X 8), means that the prediction accuracy can be written as a function of the threshold and target distribution (hh)
PD = +1)
=PD(N) +1, +1) DD =11Y==111
(D 2 0, +1) ((A) (X s 50,
=/o PD(M)(Y +1) P(X P(x= z|Y 1)
dr unchanged hecausse of lahel shift
PD( = -11 P(X P(x=x = dr
(23)
unchanged
shif
where P(X y) remains unchanged over time, and PD - y) evolves over time according to Equation
22 namely
PD(M) (Y =y)
Fitness, y (Y = =1)
= -P' (Y =3) x
EDs Fitness, (Y))
Σg PDs 18 0 = y, gl Up En ( PDs Y -IY G gو Ug P Y yl
=P' (Y =v)
(24)
Notice that Y is only function of 0, and Uy n.9 are fixed quantities, the above derivation indicates that we can express PY = y) as a function of and Ds. Plugging it back to Equation (23). we can see that the accuracy can also be expressed as function of the classifier's parameter 0, indicating that the induced risk can be expressed as function A. Thus we can use gradient descent using automatic differentiation w.r.t 8 to find optimal classifier ht that minimize the induced risk.
Accuracy on target distribution
0.025
0.020
Agent Natglicctic prreroveenntt
0035
0000
8.28
Agent
Figure 7: Experimental results of directly optimizing for the induced risk under the assumption of replicator dynamic. The X-axis denotes the prediction accuracy of Err Erpp (hg), where hg is the source optimal classifier under each settings. The Y-axis is the percent of performance improvement using the classifier that optimize for hú = arg min Err Brrp ((n)())) (h), which the decision maker considers the underlying response dynamics (according replicator dynamics Equation (22 of the decision subjects. Different color represents different utility function, which is reflected by the specifications of values in Ug.gi within each color, different dots represent different initial qualification rate.
Experimental Results Figure 7 shows the experimental results for this toy example. We can see that for each setting, compared to the baseline classifier hi,, the proposed gradient based optimization
31

---

Under review as a conference paper at ICLR 2023
procedure returns classifier that achieves better prediction accuracy (thus lower induced risk) compared to the accuracy of the source optimal classifier.
E.2 GENERAL SETTING: INDUCED RISK MINIMIZATION WITH BANDIT FEEDBACK
In general, finding the optimal classifier that achieves the optimal induced risk h is a hard problem due to the interactive nature of the problem (see, e.g. the literature of performative prediction Perdomo al. (2020) for more detailed discussions). Without making any assumptions on the mapping between h and D(h), one can only potentially rely on the bandit feedbucks from the decision subjects to estimate the influence of f on (h): when the induced risk a convex function of the classifier h's parameter 0, one possible approach is to use the standard techniques from bandit optimization (Flaxman et al. 2004) to iteratively find induced optimal classifier /7- The basic idea is: at each step 1. T, the decision maker deploy classifier h4, then observe data points sampled from D(ha) and their losses, and use them to construct an approximate gradient for the induced risk as a function of the model parameter Oz. When the induced risk is convex function in the model parameter the above approach guarantees to converge to hy, and have sublinear regret in the total number of steps T.
The detailed description of the algorithm for finding h1. is as follows:
Algorithm 1: One-Ooini bandit gradient descent for performative prediction
Result: return 0r after T rounds
0, + 0
foreach time step 1, 1....,,77 T do Sample unit vector ue Uni
0r +- 02 + ou,
Observe data points 21,..., Fnee" ~ -((0))
(R(OT) 32 ΣE (7)
(O.) (IR(0))
(o(( is an approximation of (A()))))
0.11 < [1(-5) (0: ngt (0.)
b Take gradient step; project onto
(1 - 8)0 {(1 8)0 0 θ}
end
F REGULARIZED TRAINING
In this section, we discuss the possibility that indeed minimizing regularized risk will lead to tighter upper bound. Consider the target shift setting. Recall that p(h) == PD( (Y = +1) and we have for any proper loss function
EDD,) [c(h; X, Y)] p(h) EDs X, = (1-1111p)))) (1: [x;,
Suppose p < p(hz), now we claim that minimizing the following regullarieed/pennliieed risk leads smaller upper bound.
ED [[(h; X,Y)) Y)] + a E n(X) +
2
where in above Duniform is a distribution with uniform prior for Y.
We impose the following assumption:
The number of predicted +1 for examples with Y = +1 and for examples with Y -11 are monotonic with respect to a.
Consider the casier setting with 0-1 loss. Then
E
[|xx 0.5 (0 = Px]]= = +1]) 0.5
0.5 [Ex])=+1(((b(X))) -1y---1)))-
32

---

Under review as a conference paper at ICLR 2023
The above regularized risk minimization problem is equivalent to
(p + 0.5 a) [x)x=++ +1] + (p 0.5 0.5 a) Ex]x==110(h(X),- -1]
Recall the upper bound Theorem 5.1
(rpp(gg((s)) Brrp(ng)) (17)
(p())) p(h
Term
(1 p) (drv(D+ (16g) + dD (hi),, (H-) (h.))))
Term
With properly specified a > this leads to distribution with smaller gap of (p(hs) p(ht)) where hg denotes the optimal classifier of the penalized risk minimization this leads a smaller Term 1 in the bound of Theorem 5.1. Furthermore, the induced risk minimization problem will correspond to an a s.t. a" p(h))-p and the original lig corresponds to distribution of a 0.5
Using the monotonicity assumption, will establish that the second term in Theorem 5,1 will also smaller when we tune a proper a.
G DISCUSSION ON THE TIGHTNESS OF OUR THEORETICAL BOUNDS
General Bounds in Section For the general bounds reported in Section 3 is not trivial fully quantify the tightness without further quantifying the specific quantities of the terms, e.g. the H divergence the source and the induced distribution, and the average error a classifier have to incur for both distribution. This part of our results adapted from the classical literature in learning from multiple domains Ben-David et al. (010). The tightness of using H-divergence and other terms seem to be partially validated therein.
Bounds in Section 4 and Section 5 For more specific bounds provided in Section (for covariate shift) and Section (target shift), however, it is relatively easier to argue about the tightness: the proofs there are more transparent and are easier to back out the conditions where the inequalities are relaxed. For example, in Theorem 5. the inequalities of our bound are introduced primarily the following two places: 1) one is using the optimiality of h3 the source distribution. 2) the other is bounding the statistical difference in hi and h 's predictions on the positive and negative examples. Both saying that if the differences in the two classifiers' predictions are bounded in range, then the result in Theorem 5.1 is relatively tight.
33


Reviews:
[{"review_id": "o6W2VHseOS0", "reviewer": "Reviewer_Cedq", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "\nThis paper formulates a very interesting and novel problem (IDA, induced domain adapatation) in transfer learning. Consider the supervised classification setting where one usually trains a classifier $h : X \\mapsto Y$ from samples $\\{(X, Y)\\}$ drawn from some distribution $\\sim \\mathcal D$. Oftentimes, when the data are generated from human input, the human could possibly modify $(X, Y)$ to adapt to $h$, resulting in a distribution shift over $\\mathcal D$. Therefore, when training $h$, it is important to take this distribution shift into consideration. However, this can become complicated and interactive if the human further adapt to $h$.\n\nThis paper conducts a rather detailed study on this problem. It proves upper and lower bounds for the transfer risks for several important fundamental questions in this setting, as outlined in page 2. Besides, the paper realizes their bounds by both showing how to compute them in practice and computing them on real datasets.\n", "summary_of_the_review": "This paper has good theoretical and empirical results, yet the techniques might not be exciting and the experiments might not be convincing enough due to paucity of datasets evaluated.", "strength_and_weaknesses": "\n### Strength\n\n1. The setting studied in this paper is important, interesting, and novel.\n2. This paper studies most fundamental questions in this setting and presents satisfactory results that covers several fundamental lower and upper bounds in this setting.\n3. As a mainly theoretical paper, this paper is aware of the practical impact of their theoretical results. To this end, this paper shows how to compute their upper bounds in real-world problems and conducts experiments to demonstrate their results. Furthermore, the experimental results corroborates their theoretical results and suggests that the theoretical results could give meaningful upper and lower bounds for the transfer risks.\n\n### Weakness\n\n1. The proof techniques look simple and the techniques themselves might not inspire broader community.\n2. The authors could possibly conduct experiments on more datasets to strengthen their experimental results.\n", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "nlcuvld8yE", "reviewer": "Reviewer_vuF4", "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": "This papers studies the performance of models on the distribution induced by the model itself. The paper first provides examples of when this situation arises. Then, they develop formal definitions of metrics that measures the performance of the model on the induced distributions. These new quantities are inspired by the theory of domain adaptation (DA), like the induced risks that the model should minimize, which is similar to the target risk. Then authors show lower and upper bounds of these quantities. Afterwards, authors use different examples to illustrate their bounds. Finally, their bounds are computed on a real-world dataset.", "summary_of_the_review": "I agree that the problem is appealing. The defined quantites and theorems are also interesting. The main downside is that I would have expected a training procedure to minimize the induced risk. While authors discuss the challenges of this question in appendix, it should also be discussed in the main paper.\n\nThe lack of training procedure to minimize the induced risk and the lack of empirical contributions make that I recommend 'marginally below the acceptance threshold'. I would be happy to increase my score if authors provide additionnal details/toy experiments on how to minimize the induced risk.", "strength_and_weaknesses": "This paper studies a new problem and defines new quantities to understand and study it. It makes the paper mostly theoretical and related to the statistic field. Authors define many quantities inspired from DA. However as in this problem we do not have access to target samples unlike in DA, this problem seems more related to domain generalization (DG). I wonder if some theoretical or training procedure developed in DG could be applied to this problem and maybe this should be discussed in the paper. \n\nRegarding the bounds, they are explained and applied to several examples. They are also evaluated on the FICO credit score dataset.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "n9EJlKj1iiE", "reviewer": "Reviewer_Rs7K", "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": "This paper studies model transferability when human decision subjects respond to the deployed model. It provides a series of lower / upper bound between empirical risk minimizer classifier and the optimal classifier. In particular, teh paper studies two common cases: covariate shift and target shift.", "summary_of_the_review": "The paper gives a series of bounds for the model transferability, the proofs I checked (non-exhaustive) are all good. It would be nice to see more discussions on the tightness of these bounds, as in the general case, the positiveness of the lower bound is not even clear.", "strength_and_weaknesses": "pros：\nthe paper is clearly written, and the introduction of the problem is well motivated. The organization of the paper also makes it easy to follow, with clear notations / explanations to the theorems etc. \n\ncons:\nAs the authors write in Section 3.3, the bounds in the paper is mainly of theoretic interest. I would like to see some disucssions on the tightness of these bounds, even a single example would be helpful. The mathematical tools used are also not deep.\n", "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": "gG7VnspL4As", "reviewer": "Reviewer_tvWE", "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": "In this paper, the authors explore what guarantees we can identify on the performance of classifiers in response to classification subjects which act strategically - that is, attempt to update their inputs so as to achieve a better output. They call this loss the \"induced risk\": the risk the model incurs on the input distribution which its deployment induces. Their results are mostly of two forms: upper bounds on the induced risk above the optimal induced risk, and lower bounds on the minimum of the source risk and the induced risk. The machinery used for their proofs is mostly domain-adaptation-inspired, where the source distribution is the original data, and the target distribution is the strategically modified data.", "summary_of_the_review": "Overall, this paper provides some useful results in the strategic classification space. I have some doubts about the applicability of the covariate shift/label shift assumptions to this setting, and therefore not sure how useful those results are. Additionally, I have some confusion around other assumptions made around the data generative process with replicator dynamics and the experiments. Due to some good results and exposition alongside these concerns, I'm recommending a Weak Reject for now.", "strength_and_weaknesses": "Strengths:\n- These are useful results and I think more general than what has previously been shown in strategic classification\n- paper is mostly pretty clear and exposition is good\n\nFeedback: \n-Sec 4 and 5: it isn't clear to me why Covariate/Target shift would be useful assumptions for the strategic classification setting. One would imagine that the induced distribution will have a much lower P(Y = 1 | X) for X which are right over the decision boundary, for instance; or that P(X | Y = 1) would cluster more closely near the decision boundary in the induced distribution. I'm happy to be convinced otherwise, but it seems to me that by the definition of strategic classification, these results aren't so useful.\n-Sec 4.2: it would be good to explain why these might be natural assumptions: I think I understand it has something to do with people choosing to move their inputs towards the desirable outcome Y=1, but not totally sure\nSec 4.3, Setup 3/4: I think there needs to be a little more definition around how the adapted feature is generated. For instance, if \\tau = 0.5, x = 0.4, and B = 0.2, then the probability of a successful update is 0.5, but it is drawn from the distribution U(0.5, 0,3), which doesn't obviously make sense to me.\n-Prop 4.7: I don't quite understand why as Err_D_S(h*_T) goes up in this bound, the gap increases - it would be nice to get some intuition on this relationship\nReplicator Dynamics: It would be good to have a better description of this in the body of the paper, I'm not so clear on exactly how this works\nExperiments: I don't totally understand the data generation process, even after looking at the supplement. It would be good to have a clearer explanation of the exact strategic modification model here (e.g. what is \\epsilon or \\alpha, as defined in the supplement)\n\nNotes:\nEq (3) - would be good to define the optimal model here: it's not clear at this point in the paper if h*_T is the model with the optimal induced risk, or optimal source risk (you explain later, but should explain here)\nSec 4.2 - should define X_+(h) and X_-(h)\nSec 5: a little bit confusing to me to overload w here as the induced positive rate, when it was the weighting coefficient earlier\nThm 5.2: what is p here?\n\n\n", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject