Optimal Classification under Performative Distribution Shift
Authors: Edwige Cyffers
Muni Sreenivas Pydi
Jamal Atif
Olivier Cappé
Venue: NeurIPS 2024 poster (2024)
Keywords: Performative learning
classification
performative gradient
distribution shift
pushforward
robustness
Primary area: optimization
TL;DR: We derive new performative gradient estimator and prove convexity results for learning performatively optimal classifier.

Abstract: Performative learning addresses the increasingly pervasive situations in which algorithmic decisions may induce changes in the data distribution as a consequence of their public deployment.  We propose a novel view in which these performative effects are modelled as push forward measures. This general framework encompasses existing models and enables novel performative gradient estimation methods, leading to more efficient and scalable learning strategies. For distribution shifts, unlike previous models which require full specification of the data distribution, we only assume knowledge of the shift operator that represents the performative changes. This approach can also be integrated into various change-of-variable-based models, such as VAEs or normalizing flows. Focusing on classification with a linear-in-parameters performative effect, we prove the convexity of the performative risk under a new set of assumptions. Notably, we do not limit the strength of performative effects but rather their direction, requiring only that classification becomes harder when deploying more accurate models. In this case, we also establish a connection with adversarially robust classification by reformulating the performative risk as a min-max variational problem. Finally, we illustrate our approach on synthetic and real datasets.

Optimal Classification under Performative Distribution Shift
Edwige Cyffers Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRISIAL, F-59000 Lille edwige. cyffers@iniia..ff
Muni Sreenivas Pydi Université Paris Dauphine, Université PSL, CNRS, LAMSADE, 75016 Paris
Jamal Atif
Oliver Cappé
Université Paris Dauphine, Université PSL, CNRS, LAMSADE, 75016 Paris
École Normale Supérieure, Université PSL., CNRS, Inria, DI ENS, 75005 Paris
Abstract
Performative learning addresses the increasingly pervasive situations in which algorithmic decisions may induce changes in the data distribution consequence of their public deployment. We propose novel view in which these performative effects are modelled as push-forward measures. This general framework encom- passes existing models and enables novel performative gradient estimation methods, leading to more efficient and scalable learning strategies. For distribution shifts, unlike previous models which require full specification of the data distribution, only assume knowledge of the shift operator that represents the performative changes. This approach can also be integrated into various thange-of-variabe based models, such as VAEs normalizing flows. Focusing classification with a linear-in in an-parameters performative effect, we prove the convexity of the perfor- mative risk under new of assumptions. Notably, we do not limit the strength performative effects but rather their direction, requiring only that classification becomes harder when deploying more accurate models. In this case, also establish a connection with adversarially robust classification by reformulating the minimization of the performative risk as min-max variational problem. Finally, we illustrate our approach on synthetic and real datasets.
Introduction
Machine learning models are increasingly deployed in real-world scenarios where their predic- tions can influence the users' behaviors, thereby altering the underlying data distribution. This phenomenon, though rooted in long long-standing economic theory [Morgenstern] 1928 Muth 1961]. has recently attracted interest in the machine learning community under the name performative
prediction [Perdomo et al.) 2020 Hardt and Mendler-Dünner/ 2023]. Consider for instance social ranking system: it consistently favors particular subpopulation of individuals, user behavior might shift towards mimicking the main characteristics of this subgroup conversely, some features of this subpopulation can undergo modification as consequence of the selection by the system, both effects leading to subtle alterations of the original data distribution. More generally, performative learning captures dynamics at stake in strategic classification, where individuals are confronted by algorithmic decisions that impact their life- such as loan acceptance, college admission, probation and might thus try to overturn predictions by optimizing some their features.
This feedback loop, where predictions influence future data, poses new challenges and necessitates the development of novel approaches within statistical learning theory and practice (Perdomo et al.)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

2020
Jagadeesan et al., 2022, Drusvyatskiy and Xiao 2023 Hardt and Mendler-Dünne 2023
Zezulka and Genin| 2023 Perdomo et al. | [220] proposed to formalize performative learning as generalized risk minimization problem, with the performative risk being defined as
PR(0) = Ee [(( 0)],
where E is a loss function, 0 a model's parameters, and Z an observable random variable drawn from distribution Po also parametrized by 0 itself. In light of the difficulty of minimizing PR(0) directly, one can define a decoupled performative risk as DPR (f, 8¹) = Eg [e( Z: 8') clarifying the interplay between the model's prediction and the distribution change. This can be seen as a Stackelberg game that stabilizes when neither the modeler (learned parameters) nor the environment (distribution) has incentive change their states. Solving the performative learning problem consists in minimizing this risk under the constraint that 0 = 0'. because the testing samples will follow the distribution corresponding to the deployed model. and thus (R( DPR(0, 9). Minimizing DPR(0, 0') w.r.t. o' for fixed O corresponds to the classical machine learning setting. In contrast, estimating the performative effect, i.c., knowing how optimize for a given 0' is more challenging as, per definition, one can only perform statistics from samples collected for values of the parameters @ for which the model has already been deployed. Hence, performative learning does require some form of counterfactual extrapolation, i.e., what will happen to the data distribution when the parameter O changes from its current setting?
Hence, instead of focusing on methods finding performatively optimal points, OPO E arg min (R(O). many previous works, following Peerdomo et al. 2002)), focus finding stable points Ops arg min DPR(Ops, 0), through methods that iteratively minimize the empirical risk. This line of research is appropriate in settings where the performative effect can be tamed. If it is sufficiently small, explicitly taking into account the performative changes of distribution is not required and optimal and stable points will be close enough [Perdomo et al., 2020). However, real use cases do not always satisfy such strong assumptions (see further discussion in Section 4 In general, stable points may not be good proxys for perfornatively optimal points, particularly in settings where the performative effect cannot be bounded priori.
Towards this goal, another line of research focuses on finding the optimal points 0po- Izzo al. 2022] propose to use Monte Carlo sample-based approximations of the gradient of the performative risk, V PR))). based on the score function estimator (see Section 2 below). Miller al. [202]] use a two-stage approach that deploys random models to estimate the performative effect in the first stage, and then minimizes the estimated performative risk in the second stage. A drawback of both of these approaches is the restrictive set of assumptions needed to show that the algorithms converge. While Izzo et al. [2022] assume the convexity of PR(0) along with smoothness and boundedness
contitions, Miller et al. [2221] assume that the loss function is simultaneously strongly convex and smooth. Moreover, the score function estimator of Izzo et al. (022) necessitates full knowledge of a parametric form of Po. which is unrealistic in practice. Alternatively, Jagadeesan et al. [2022] resort to derivative-free (or zeroth-order) optimization strategies. However, such an approach is appropriate only when it is possible to sequentially deploy a large number of model instances, and it does not scale with the dimension of the parameter O.
The present work is connected to the second line of the research explored above, where the focus is on finding the optimal point 8yo. Our contributions are as follows.
(i) Model the performative effect as a push-forward operator This novel approach provides a new explicit expression of the performative gradient. Not only does this approach allow estimation of the performative gradient in settings where previous methods couldn't 't, but we show that in typical use cases, the variance of this new estimator is significantly smaller.
(ii) Convexity for Performative Classification We then focus on the specific task of strategic classi- fication, as this performative learning problem encompasses various real-use cases with important socictal impact such as college admission or credit decisions. Our second contribution is to provide new convexity results on the performative risk in this case. Whereas existing results were only proving convexity under assumptions restricting the performative effect to be small compared to the (assumed) strong convexity of the loss function 2(2; 6), our results leverage structural assumptions on the performative effect that ensure that the performative risk is convex without any restriction on the strength of the performative effect.
(iii) Linking Performative and Robust Learning We establish a connexion between performative
learning and adversarially robust learning, paving the way to transferring robustness results to the
2

---

performative learning field. In particular, this result gives new insights on the empirical evidence in favor of using regularization in the presence performative effets. Finally, we illustrate our findings on synthetic and real-world datasets.
Push-forward Model for Performative Effects
In this section, we study the general performative learning setting without yet specializing the classification context. In Section 2. we introduce the push-forward model of performative learning and derive the expression of the gradient of the performative risk under this model. In Section [2.2] we present a reparameterizzaiion-aen to the score function based estimator considered by Izzo et al. 2022
estimator for the gradient of the performative risk, and compare it
2.1 The Push-forward Model
We aim to minmmize the performative risk defined in eq. (T) where the observation drawn from the distribution Po. which depends on the parameter 0 E IR? of the learning model. For this to be tractable, one needs additional hypotheses on the nature of the performative effect. We propose to represent the performative effect through push-forward measure, which matches the intuition of having an untouched distribution that is steered by the performative effect.
Assumption 1 Pewwarf Performative Model). For a given model parameter E RP, the samples' distribution under the performative effect is given by I' s0: 0);P where sp(=;)) is differentiable invertible mapping on R. depending on 8.
This assumption can be equivalently stated by the probabilistic representation Z (UU where U IP (the symbol = denoting equality in distribution). If P admits density, then so does Po with density function given by Po(2) = [2; (); 0)) where (1: 0) = (.; In this last (x:9))
(:;0).
formula, (2v 0) refers to the Jacobian matrix where (2;4(2;;
dz;
From an abstract point of view, such a representation of parametrized family of distributions exists under very general conditions. However, the above model is more interesting in scenarios where (-; 0) simple operator, for instance linear one, is the case in most of the examples considered by Perdomo et al. [2020), Miller et al. [202T]. and the dependence with respect to o can also be made explicit. This representation also modular in the sense that yo could be chosen the composition cı;;; f) (p (w; 0)), where Pp L (Z) corresponds to fixed (not depending on 0) representation of Z in a feature space and (-:0) models the performative effect in the representation space. Although we will not explicitly consider such cases in the rest of the paper, this representation of the performative effect is particularly attractive when using embedding tools based on kernels [Hofmann al. 2008 neural nets (e.g., VAEs [Kingma and Welling 2013 or
normalizing flows Paaaaaakaiios et al. 2021 Kobyzev et al. 2021
This structural assumption the performative effect yields new estimator for the performative gradient, which may be seen as an instance of the 'reparametrization trick" used VAEs, normalizing flows by Kucukelbir al. 2017]. Mohamed al. 20200) also refer this approach "pathwise" gradient estimation.
Theorem 1 (Performative Risk Gradient). Under Assumption [. the gradient of the performative risk given by
(2) where V v.((2; 0) and V Vo((2;0) 0) denote respectively the gradient with respect to the first and the second parameter of the loss, and Jo y(u; 0) is the transpose of the Jacobian with respect to
Ve PR(() = Ee Vol(Z: + Es [J (l
Proof. Notice that under assumption] I we can rewrite the decoupled risk with a change of variable as DPR(0, 0¹) = [E[((p(U;; 0'). This expression leads to the following.
Ve PR(()= = V Vo 0)] E [vee(p(U:0))0)) + J ((U;0)V
which gives eq. under change of variable.
3

---

2.2 Estimating the Performative Gradient
From Theorem [ is clear that the gradient of performative risk in eq. 2 is composed of two terms the first term corresponds to the classical risk minimization, while the second one which we will refer to as the performative gradient in the following captures the performative effect. The first term can be estimated by estimator.
2i=1 Ve(Z;; 0) as usual. For the second term, we propose the following
Definition (Reparameterization based Performative Gradient Estimator), The performative gradient Va DPR(O, ler= admits as unbiased estimator:
GPP
Ju ((
(3)
This estimator allows performing gradient descent to minimize the performative risk and thus, if the performative objective is well behaved, to converge the performative optimal point. GRP should be compared to the following estimator used by Izzo et al. [2022]. which relies on the well-known score function formula -see ELEuuy 1991 Kleijnen and Rubinstein, 1996 Mohamed al. 2020) and references therein.
G&F
While both GBP and GSP estimate the same quantity Vo DPR(O, f')o0==0, GB has two distinet advantages over G.F First, computing G& requires access the analytical form of pe. which fairly unrealistic in a learning scenario, whereas our estimator GRP only requires knowledge of sp, paving the way for peri-paraatttic approach in which the performative effect is modelled explicitly, but not the distribution of the data. For general maps (p, GBP still requires to use the inverse mapping th, however this is not required situations where the Jacobian Jø (u; f) does not depend on w. Specifically, when yp is shift operator, one obtains very simple expression for ČRP as shown in the following example.
Example 1 (Shift Operator). If the performative effect can be modelled by shift operator, i.e. O) U (O), the GRP estimator is given by:
G = J IT(O)
V ve(Z;)))
where Jg (I) is the Jacobian of the performative shift II(#).
In addition to removing the need to know Po. a second advantage of GRP is that can lead to significant decrease of the variance of the estimates, illustrated by the following example.
Example 2 (Perfomative Gaussian Mean estimation). Let l(2; 0) = || -113 and Z U + ITO, that is, IT(0) ITO is a linear shift operator. We will assume NN Ia), so that pa(z) x expl-Il= - TT0 ((o2)) where II represents the performative effect. The gradient of DPR(0,0) w.r.. the distributional parameter is given both by
Va DPR(0,0)) = E,
= 11t Eol2 0' B +a]
(repurameterization)
1 E
Eg Eel log -IT
[||U + al|²U]
(score function)
202
where a 110 0. Hence, in this case Čap II E + a), while ČSS
IIT 2 Ex= ||U + ulI Both of these expressions have equal expectation II10 8') which corresponds to the gradient of DPR(B, has covariance T² TI/n while the score-based estimator ČSP has covariance:
(R,0) 8') w.r.t. 6. However, the reparametrization estimator G
ITTT'IIn
1 111T (d + 6d 8)0² 2(d + 4)]la/12 /|2
/o2 la + aa? II.
4

---

The details of this computation can be found in appendix A.1 Both estimators are unbiased but note that while Gg would always be an unbiased estimator of the performative gradient without any further assumption on the distribution of U, the unbiasedness of G. relies the fact that U is Gaussian. G-RP has a covariance that does not depend on 0, O' nor on the dimension d. contrast, G covariance includes a factor that increases with d², making it unreliable in high dimensions. It also includes additional terms that grow with the norm of II0 0', so the estimator becomes less reliable when the performative effect is strong.
One could argue that the previous result does not provide fair comparison between both estimators, GSF's variance can be reduced by subtracting baseline. Indeed, G Σi= (e(Z;: 8)
V log po(Z,, (2,) is also an unbiased estimator of the gradient of the performative effect (for any choice of the baseline m), as the score function has, by definition, zero expectation. Tuning m properly may reduce the variance by creating a so-called control variate -see, e.g., (eereeeensm et al. 2004 for the use of this principle in policy gradient methods. However, similar calculations (detailed in appendix A.1) show that the minimum covariance that can be achieved by subtracting a
baseline is
'I' (((1 + d/2)o² + [|a|3)) Ia + aa") II. n
which is still larger than the covariance of GRP by a factor that grows with the model dimension d. The fact that the reparameterization- based estimator is preferable when considering the Gaussian distribution with quadratic loss function was observed before by Mohamed et al. [2020] in the scalar case. The above computations however show that the difference between the two approaches gets more and more significant as the dimension increases. The case of other distribution/loss function combination still needs to be investigated.
3 Classification under Performative Shift
In this section, we specialize to the setting of binary classification which encompasses various machine learning applications where performative effects are expected. Usually, this setting involves desirable class and an undesirable one. For example, the desirable class might represent college admission, loan acceptance, no-spam email, probation. In this setting, one can also expect that individuals belonging to the favored class we designate this class do not need to alter their features, or only with small changes. On the contrary, individuals with negative predictions in class 0 have incentive to modify their features, resulting in significant performative effect.
We particularize the arguments introduced in section 2 to the setting of binary classification,, by fixing (xr, y). with a covariate vector & E R4 and a label E {0, 1). As is done classically -see, e.g.. Bach 2024] we further assume that the classifier fx()) is real valued function that depends parameter B E Rº and that a convex loss surrogate 4 is used, such that the loss function {(2; 0) is We model the performative effect as label-dependent push forward models,
equal to (f
i.c., that, under lp..
X|y=1 _ 90 (U1; and Xly=o (),
where (P and şo represent the performative changes affecting class-conditional distributions of classes and I respectively. the classifier fa(x) is sufficiently expressive, changes such that Pi Po will not create performative effects. We thus focus on scenarios where the performative changes affect each class-depended distribution differently. For concreteness, we will assume the following.
Assumption 2. Po = 1) = fixed and not subject performative effects.
Assumption 3. 1 does not depend 0, and for simplicity, we assume it is the identity function.
Assumption 4. (o(ue: 0) uu II(@) is shift operator.
Assumption is consequence of the intuitive property that even if the distribution is modified, the ground truth labels are not impacted by the performative effect. Assumption 3 alllows to focus on the performative effect on the unfavored class and simplifies the presentation but could be easily relaxed. Finally, assumption is restricting the performative change shift, which does simplify the problem but still corresponds to realistic model for feature alteration.
5

---

It is important to stress that, despite the fact that this performative effect is modelled as shift, the joint distribution of Z (X, Y) does not belong to the location- scale family discussed by MMller et al.. [202]] Under these assumptions, the decoupled performative risk takes the following form:
(0, 0*) F. + ((-1)² for (X)) pF ( (Ui))) + (1 Ser + ITO)))) (4)
where the performative effect is only manifested in the second term, which corresponds to class O.
Remark (Localization of the Performative Shift). In eq. 4. we refer to Un which corresponds to the covariates of the second class in the absence of performative effect, i.e., when 0 = 0. However, for a shift operator, for any value of 6. one may equivalently write that, under Fo. X - (0Ug; f), lu; 0)
[I) II(@) and Ug is distributed under P Thus eq. (4) can equivalently be rewrilten by laking expectation under an arbitrary parameter value 0, upon defining the performative effect as Ug- (0) (T) and the linear model as fo(x)) = x² 0).
where p(u;
4 Convexity of Performative Risk
Identification of the cases in which the performative risk PR(0) is convex is an important step towards generalizing results obtained in the context of traditional (ic., non performative) learning theory. Existing results mainly exploit the fact that if the loss function is strongly convex, a sufficiently small performative effect cannot break this convexity. For this reason, it is often assumed [Miller et al. 2021 Hardt and Mendler- Dünner 2023) that the change in the distributions has a bounded sensitivity with respect to the parameters, using the 1 1-Wasserstein distance:
W1 (Po, Por) & ||0 01112-
Note that in setting, such exists and corresponds to the operator norm of II()). In order to preserve convexity, it is then needed that e < p 1/2L when the risk is L-smooth and p-strongly convex. The pricing model, considered by Izzo al. [2022] is very simple example showing that the performative risk can be convex while not fulfilling this criterion.
Example 3 (Pricing Model). Given a fixed set of d resources, the pricing model aims at finding the prices f E TRd for the d ressources that maximize the overall profit given the elasticity of the demand level:
f(z;0) = = with Z -
(5)
where 11 is a diagonal matrix with positive elements, encoding the elasticity of the demand level to raise in price of each resource, and μ = B[U] contains the baseline demand levels for each resource.
In this example, the performative risk PR(0)= = -i= -1, )0, is a strongly convex quadratic function minimized at 6: (2T() In contrast, the decoupled performative risk DPR(0, 8') -(a HO0 is still convex, but not strongly convex in 0 and is always minimized in 0' at infinity. Despite its simplicity, this example is thus not covered by existing theorems, and retraining procedures considered by Perdomo et al. 22200] fail by diverging.
Moreover, this example highlights that requiring small sensitivity for the performative effect does not match the true convexity conditions. The performative risk is indeed strongly convex as long as the II, are positive, irrespectively of their magnitude. In contrast, in this example, the performative risk would become non-convex if one of the II; were negative, even with small magnitude.
This motivates the search for related phenomenons in the classification context, by looking at conditions for ensuring the convexity of eq. ( Indeed, we show that in the classification setting, one can also observe convexity without restriction on the magnitude of the performative effect. For this, we consider the case of linearly parameterized models, which we denote for simplicity by fe(x) = x
Note that, as discussed in Section our model of performative effect is composable and hence, we could also consider the more general linearly parameterized model in which fa(x) = (fz)) with a linear-in-the- teeer--nttheeppaamtteer performative effect in the feature space such that (xX) U + I1(0). For ease of notation, we stick to the case where &b is the identity function in the following. Using standard arguments, the choice of convex loss surrogate & then entails that DPR(8, 8') is convex function of 8', For the same reason, if (I()) = IIØ is linear-in- parameters shift operator, DPR(6, 8') is also convex in O. Note however that, unless there is no performative effect (i.e., if II = 0), eq. is not jointly convex in (0, 0'). The following result show that it is nonetheless the case that the performative risk PR(0)= = DPR(O, 0) is convex under the condition that IT is a positive semidefinite matrix (sec proof in appendix A.2
immea-in-parameter

---

Theorem 2 (Convexity of Classification Performative Risk). Under assumptions 4 for linearly
parameterized classifier fo(x) = and linear shift operator I1(0) IIB, the performative risk PR(() is convex when IT is a positive semidefinite matrix and one of the following conditions holds.
(a) & is the quadratic loss function;
(b) ① is a convex non increasing function (such as hinge, logistic or exp loss).
This theorem allows us extend the known convexity results losses that are not strongly convex, and to performative effects with arbitrary magnitude.
1-|-L -2
1-12 -2
<
Figure 1: Profile risk for classifying two Gaussian centered in Mi (0, 0) and A1 (-1,1) with quadratic loss and various values of X for the diagonal coefficients of II. The performative risk remains convex long II is positive semidefinite i.e. À O, and becomes non-convex whenever some of the X are negative.
Remark 2 (Generalization to Performative Effect Affecting Both Classes). One could remove assumption 3 to allow class to change under performative effect. The convexity of PR(O) remains if (i u 11,0, where 11, a positive semidefinite matrix. Similarly, the classification task becomes harder with performative effects and the performative risk is convex.
5 Connection with Robustness and Regularization
In order to enforce strong convexity of the loss function ((:;0,, previous works on performative prediction have considered the of an additional regularization term-see, e.g., Section 5.2 of [Perdomo et al. 2020] where logistic regression is used with ridge regularizer. When doing so, has been observed empirically that the retraining method performs quite well. To build on this observation, we show below that for linear-in teee-the-pppe the-parameter performative effeett that tends to make the classification task harder, the performative optimum may indeed be interpreted version of the base classification problem. This regularization does not take the form of and additive penalty but can be interpreted as the solution of a specific adversarially robust classification objective. In this section, we use the slightly stronger assumption that II is symmetric positive definite matrix, in order to ensure that both ||о] = (u To and ||
regularized
(o (1=1)-1 2/2/ are norms on Rdd
Theorem 3 (Variational Formulation of the performative Risk). Under assumptions 2 to 4 for linearly parameterized classifiers fo(x)) xx' 0 and linear shift operators IT(0) = ТTO, and assuming that & is a convex non increasing function and that II is symmetric positive definite, the performative risk may be rewritten as
PR(0) pE[ P)E
max
40- AU)
(6)
[AUo:]] [11
Intuitively, for classification-calibreee calibrated loss function BBrrlettt et al. 2006
Bach 2024 and classes
with identical covariances, we expect 0 to align with the direction of μr (0) Ho (6) so that, when II
is positive definite, the performative shift IIØ has itself positive dot product with (0) (o))). The reformulation of the performative risk eq. ( formalizes this intuition by showing that performative optimum is associated to an adversarially robust classification task [Goodfellow et al. 2015, Madry al.) 2018 Ribeiro et al. 2023] in which the points of class 0 are allowed to shift towards those of class 1, so to increase the overall loss. Compared to objectives found in the robust

---

classification literature, the specificity of eq. (6) lies in the fact that the tolerance (or budget) on the adversarial displacement AUg depends on both II and B.
To understand the role played by the || ||1 and || -lu-- norms, consider the particular case where only subset of the variables have a performative effect, i.e., if we let and Ug be partitioned into
0p and Uo
0,
U
with 1pp = 71 and 11, = el, one obtains, letting tend to zero, that the performative risk is equal to PR(O) - (UT 0)] (1- AlCoolll
(-(U7,,0, + (Uv.p + AUO.p)))p))
max
The above expression shows that in this case, only the coordinates subject to the performative effect appear in the adversarial reformulation.
In the proof of Theorem (see appendix A.3 observe that the second term of eq. (6) may also be rewritten as (1 - E) (-U
RJ Similarly to the case studied by Ribeiro et al. [2023), the term ||@]] that appears inside the surrogate loss function + has regularization effect. Note however that it is not equivalent to the use of a standard ridge regression penalty on 0. The following theorem provides bound the performative optimum that highlights the role played by II on the significance of this regularization effect.
for linearly parameterized classifiers fa(x) = x²'O and linear drift operators 11(0) = II0 when 4 is a conver non increasing function and Il symmetric positive definite matrix, the minimizer or of PR(() satisfies the following condition.
Theorem 4 (Regularization Bound). Define μ4 ElU.). Under assumptions
|II 1 (pp) -11 p)Po)ll
10 In
1-p P
Theorem 4 shows that the performative optimum has a smaller value in |/n norm when the performative effect is stronger, that is, when 1I gets larger. In the particular case where Il = 7/. eq. (7) rewrites as 2//21|00|| S > | (1 - -ooool//
p) and thus larger values of y decrease the r.h.s. while the l...s increases for identical values of ||0*), showing that ||0*|] has to decrease to zero.
Experiments
In this sectior we test the performance of our algorithm Reparametrization-bon Performative Gradient (RPPerfGD) with respect to existing algorithms. Three baselines were introduced in Perdomo et al. 20200. First, Repeated Risk Minimization (RRM) computes at each step the next 0 to minimize the non-performative risk, leading to the update rule 01+11 = arg ming DPR(0', 0'). In practice, we found that this algorithm is unstable as soon performative effects become significant. We thus report separately the results obtained with this algorithm in appendix [B.2] A second baseline is Repeated Gradient Descent (RGD), which ignores the performative effect but limits itself to a gradient step towards this minimization g++1 = ft experiments, it is often chosen to add regularizer to the objective function, which is particularly interesting in the context of performative learning, as discussed in section [ Hence, we report Regularized Repeated Gradient Descent (RRGD), that corresponds to the repeated gradient with loss function including an additional ridge penalty on 0, leading to more conservative behavior that is also more robust to performative effects. Finally, we also compare to the Score Function Performative Gradient Descent (SFPerJGD) which estimates the performative part of the gradient using the GRP estimator based on the ecore-function approach (see section 2 This was previously used in small dimensions in Miller et
Vø DPR (0, lor In numerical
2021
'The code is available atlttps://githhb http::///ttttuuocco//oooo/aa////

---

405
475
Algorkamaa
Aganiimr
K360 sthori0
(b)
200
ow. :5
SPhriD
1.12
111
0-:3
18.20
Thebo har home of EiP M77
RAGD SFRWICO
0.0
15
0.0
(d)
Figure 2: (a) Logistic regression to classify two Gaussian distributions centered in (0, 0) and
(-1,-1) and different magnitudes of performative effects 7, We report the accuracy for three different magnitudes of the performative effects, from performative effect (7 0) to strong one (7 = 1). (b) we report the position of the parameter its 2D-space, starting from (0, 0) and following different paths depending the algorithm. (c) Accuracy of classification with quadratic loss on two Gaussian distributions dimension with various levels variance o of the distributions. (d) Same experiments but using the learnt II for RPPerfGD. (e) In this case, distance between the true matrix and the estimated version. Note that RGD and RRGD the estimation of IT is not used in the algorithm.
(f) Logistic regression for the Housing dataset with various magnitude of performative shift on the coordinates 0, 4 and 6. Accuracy averaged over 20 runs.
Influence of the performative effect In fig. 26 we illustrate how taking into account the perfor- mative effect allows to mitigate regimes with strong distribution shift. We generate two Gaussian distributions, one fixed for class 1 and one moving with mean u(0)² -(1, 1) + d0ag(0.1, 0.9). where 7 the magnitude parameter effect. We learn a logistic regression and report the accuracy of the predictions as well as the trajectory of the parameter in (61, f2)-space. As expected, when there is no performative effect (7 0), all methods are equivalent. As soon there are performative effects, Performative gradient takes advantage over other methods. RRGD proposes an interesting tradeoff in terms of performance: agnostic to the performative effect, still moderates its value and thus the magnitude of the performative effect.
Stability of the estimator In fig. 2c we illustrate the result of example 2 by training classifier with the square loss, showing that the acore-based estimator used in SFPerfGD becomes unstable in high dimensions. We use Gaussian distributions of dimension 7 with two dimensions subject to performative effects. vary the variance of the distributions. When the scale a is small, the variance of the estimator increases to the point of making learning impossible with unstable trajectories of the parameter 0. Even when the scale is small enough to ensure convergence, RPPerfGD provides faster convergence illustrating its better scalability for high dimensions.
Estimation of IT We estimate IT in fig. 2d and fig. 2e by running a ridge regression along the successive deployments of the model as described in Algorithm the ridge penalty ensures that initially the estimate of II is close to zero making the RPPerfGD updates very similar to those of

---

RGD and it is easy to check that order d deployments are enough to obtain a non void estimate of II. While this plug-in approach is not guaranteed to converge from a theoretical standpoint, we observe results that very similar to the case where IT is fully known.
Houses price prediction To simulative performative effects from a dataset, we follow the method- ology of Perdomo al. [2020], by shifting the coordinate of a factor A0; if the i-th coordinate could be easily modified, and keeping its real value intact otherwise. We use the binarized version of the Housing datasef where the outcome is whether the price is high not. Assuming that seller wants to obtain a high price, the high price is the favored class. Some characteristies are harder to tamper with such the location the income, whereas other be slightly adjusted such as the houschold and the number of bedrooms (a room could be promoted bedroom), Coordinates 0, 4 and 6 are thus shifted while other remains identical. We see that when the magnitude of the shift increases, RPPerGGD outperforms RGD. In particular, it seems that RPPerGGD succeeds in converging faster than the non performative approach.
Algorithm 1: RPPerfGD with IT learning
Input :Stepsize n, regularizer X, starting o.. Loss & Output:Paramett 0g and diagonal matrix II
Ho t 0.xx // initialize
as a zero matrix of size x d
for k E (0,..., 1} do
Receive samples { 18 Fitl D(fx) with no samples of label -1 denoted (
Compute V
Σ = Vol(xi 0z)// Non performative part of the gradient
Compute V2 I E V ( 0z)// Performative part of the gradient
over negative samples
But1 t 0₂ - nV V2) // Gradient Descent step
I1, + argmin Σ5 Ex | IT0 + |||l||| // is the estimated
mean of the class
7 Conclusion
In this work, we have investigated the consequences of assuming novel, more explicit, model for performative effects under the form of a fosh-forward shift of distribution. We have demonstrated that it comes with practically important consequences, such as enabling more reliable performative gradient estimation in large dimensional models.
In the classification case, we observed that when the change of distribution given by linear-in- parameters shift, the performative risk is convex under relatively general assumptions. It would be interesting to study how these results may extend to non-linear models for the performative effect.
Finally, we have shown that certain kinds of performative effect induce implicit regularization of the risk minimization problem. Moreover, this regularization effect alternatively be viewed through the lens of adversarial robustness. It would be useful to explore whether this reformulation can be used optimize the performative risk without explicit model for the performative effect.
Acknowledgments
This work supported by grants ANR-20-THIA-001 program "AI PhD@ and ANR-22- PFSN-0014 under the France 2030 program. The authors thank Francis Bach, Bruno Loureiro and Kamélia Daudel for their helpful insights.
References
Francis Bach. Learning Theory from First Principles. MIT Press, 2024.
hittps://wwy http::://wwwwwpollccccm org/d/823
10

---

Peter L. Bartlett, Michael I. Jordan, and Jon D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 473(101), 2006.
Dmitriy Drusvyatskiy and Lin Xiao. Stochastic optimization with decision-dependen distributions. Mathematics of Operations Research, 48(2), 2023.
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
Evan Greensmith, Peter I.. Bartlett, and Jonathan Baxter. Variance reduction techniques for gradient estimates in reinforcement learning. J. Mach. Learn. Res., 5, 2004.
Moritz Hardt and Celestine Mendler-Dünner. Performative prediction: Past and future, 2023. arXiv:2310. 16608.
Thomas Hofmann, Bernhard Schölkopf, and Alexander Smola. Kernel methods in machine learning. Annals of Statistics, 36(3), 2008
Zachary Izzo, James Zou, and Lexing Ying. How to learn when data gradually reacts to your model. In International Conference on Artificial Intelligence and Statistics, 2022.
Meena Jagadeesan, Tijana Zmic, and Celestine Mendler-Dümner. Regret minimization with perfor- mative feedback. In International Conference on Machine Learning, 2022.
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes, 2013. arXi:1312.6114 14.
Jack P.C. Kleijnen and Reuven Y. Rubinstein. Optimization and sensitivity analysis of computer simulation models by the score function method. European Journal of Operational Research, 88 (3), 1996.
Ivan Kobyzev, Simon J. D. Prince, and Marcus A. Brubaker, Normalizing flows: An introduction and review of current methods. IEEE Trans. PAMI, 43(11), 2021.
Alp Kucukelbir, Dustin Tran, Rajesh Ranganath, Andrew Gelman, and David M. Blei. Automatic differentiation variational inference. Journal of Machine Learning Research, 18(14), 2017.
Pierre L' L'Ecuyer. An overview of derivative estimation. In Proceedings of the 23rd conference Winter simulation, 1991.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
John Miller, Juan C. Perdomo, and Tijana Zrnic Outside the echo chamber: Optimizing the performative risk. In International Conference on Machine Learning. 2021.
Shakir Mohamed, Mihaela Rosca, Michael Figurnov, and Andriy Mnih. Monte carlo gradient estimation in machine learning. Journal of Machine Learning Research, 21, 2020.
Oskar Morgenstern. Wirtschaffxprognose:: Eine Untersuchung ihrer Voraussetzungen und Möglichkeiten. Springer Vienna, 1928.
John F. Muth. Rational expectations and the theory of price movements. Econometrica: journal of the Econometric Sociery, 1961.
George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshminarayanan. Normalizing flows for probabilistic modeling and inference. J. Mach. Learn. Res., 22(1), 2021.
Juan Perdomo, Tijana Zmic, Celestine Mendler-Düinner, and Moritz Hardt. Performative prediction. In International Conference on Machine Learning, 2020.
Antonio H. Ribeiro, Dave Zachariah, Francis Bach, and Thomas B. Schön. Regularization properties of adverse linear regression. Conference on Neural Information Processing Systems, 2023.
Sebastian Zezulka and Konstantin Genin. Performativity and Prospective Fairness, October 2023. arXiv:2310.0833

---

A Supplementary Material
A.1 Proofs for Example
2 Using the notations of 2xample 2 the score function estimator may we written as 11" 1 G. where
G = ||U + al|²U with U N (0, La) and E I is deterministic vector depending on the parameters 0, and the performative effect. To compute the expectation and covariance matrix of G we will use Isserlis' (or Wick's probability) theorem which state that
(a) EUU ... Usami .I = O, for any (i.....; 22m-1) E (l....,d)2m.. 2m (b)
ElU U22m] = 2m
Σ
55.k1
jjmkk
k1. I.... D.m. PE((
where P((i,..... f2m) denotes all the distinct ways partitioning (fj....,,2n)) into non-overlapping (unordered) pairs and ó is the Kronecker delta. It is easily checked that the number of partitions in P((i,,.... 12m }) is equal to (2m) mn! product of all odd numbers between and 2m
which is also equal to the 2m
For the expectation, G [[ + ||a|| + 2a U)U 2B(U0?)a = 20²a, as the expansion of other terms would involve and odd number coordinates of U.
Let M = EEGG" we have
Mij = E Σ u axx)
Σ
U1 +
U.U
1=1
1=1
E
(URU ULat UPat torayUhii dz U:U,}
omitting terms in the expansion that involve and odd number of coordinates of U (which have expectation). Now, we apply Isserlis' theorem to each term in this decomposition, starting with the lowest order (rightmost) ones:
LL -1la|(00200
d d = 40
E
Aajay URUGUUU
ajay (8ijóui + 8udd + 6αδ,x) = 40 4|1|12 + 2a )o1
k=1
021la|22
> (dij + 20mddss)
-dlla|1((d 2)0g
oiuto, = の (d:g + 26 + 25 + 25 + 86 = od 6d + 8)
where the last decomposition is obtained by examination of the (9) {K, k, 1, j in 3 pairs of indices. Putting all together, one obtains
15 possible partitions of
M (ld2 6d 8)0 + 2(d 4)]|a|13a** + +|al|to?) Ia tataa
which yields
Cov(G) = (ld2 + 6d 8)0 + 2(d 4)lla|13o* ||a||* 0²) Ta + 40taa"
(8)
Subtracting scalar baseline yields the estimator & (IlU + all m)U which has the same expectation as G. In terms of covariances, one has
Cov(G) Cov(G) m²a 2mE (II all?UUT)
12

---

The rightmost expression, when expanded, features terms have already been met in the computation above and it is easy check that
(IU + +al = ((d+ 2)0* + +|aa|2 1|aa|2002 I2)
Hence,
Cov(G) Cov(G) + (m² - 2m + 2) + ||all l7
In the above equation, the scalar term m² - -2m((d + 2) + |aal(0²2 is minimized by choosing
( 2)o² + ||a]l² and is equal to ((d 2)0² |all3) 0². which, combined with eq. (
yields
Cov(G) 2 (2(d+ 2)0 + 4||a||30*) La + a0"
(9)
A.2 Proof of Theorem
Proof. For (a), eq. 4 may be rewritten
PR(0) p 1) + (1- p) + 110) + 1)
Denoting B(U,) μ4, and CU:)(U E, for i {0, 1}, one has
+ (1 ()(( - -o) + (uo + ITO) 0 + 1) PR(0) = pIR(((U - 11) -0--1(111)) (--())))
= =1110|| + +1 - (1-11000 //0))] - (1 p)[110 + ((ro + ITO) + 1)
Both squared norms are convex as well as the squares of, respectively, an affine function and a convex second order polynomial (as II is positive semidefinite).
For (b), examining
PR(O) = p (E(T( (1- (1-00CC00000-0)00((-000000 00)
(10)
one observes that
4 (uf'0) is convex by our assumption on & (for any value of w1);
(uo + 110) 0 is a convex second order (multivariate) polynomial in 0 when II is positive
semidefinite and + (-v) is convex non decreasing, hence d--(uo + 110)² 0) is also convex.
Thus PR(O) is also convex in 0 as the expectation of convex functions.
A.3 Proof of Theorem
Proof. To obtain eq. 66, as v + ((-v) is non decreasing, one has
max ① (-(wo + To) (-166 [Amo:]]Auo Ml ((19 (Auo:l Ano n-1 10]]n)
(Auo) )T)))
max
for any outcome ug of the random variable Up. The maximization occurs for Auo 110, which does not depend on ug, leading to (Auo)" = ||0 and thus
Φ (Up + AU) (-U [0011))
max [AUs: sl00
whose expectation is recognized as the second term of eq. (10
A.4 Proof of Theorem
4
Proof. Recall from the proof of Theorem
2 that the performative risk can be rewritten as follows.
PR(0) = [E( - 0)
= (1- -1-00000011100000000000011111111
13

---

Let up = PM1 (1 - p)H-- We have,
( = PR(() 2 PR((")
(1-
10 [[:]
(P(BBU700++(0000000000000000 10'1R))
100 lH)
+ (pn) - (0-0))00000 + -100
= 1 (1700 (1 p) llii llii)
where we have successively used Jensen's inequality and the convexity Φ. Since & non- increasing, we must have S 1 0r (1 p) |0 Il Denoting 3 = II holds that
(1 p) || - / TT LB = ||T 2 |
I I $ 1-p
where that last inequality is obtained using Souchy-Schwande Hence, ||0||n ||:3|| s
B Numerical Experiments
B.1 Full parameters list
In this section, we report all the parameters needed reproduce the figures in the paper. Note that we always use the same step size for all the methods, This choice stems from the fact that the methods equivalent (up the regularization parameter) when there is no performative effect.
Table I: Parameters used for figure fig. 2b
Parameter
Value
Number of iterations (num iter)
100
Sample size (n))
1000
Scale (a)
0.5
Average number of iterations (num -ttrr average)
100
Step size (step_size)
0.1
Regularization parameter (A)
10 10-2 2
Table 2: Parameters used for figure fig. 2c
Parameter
Value
Number of iterations (num iter)
25
Sample size (n)
1000
Initial scale (scale,)
0.5
Transition probability matrix (IT)
diag(
1,,
0,
Mean of class (μ)
[ 2 0.5
0.5
0
0
Average number iterations (num_iter averrae)
100
Step size stte_siiz)
0.1
Regularization parameter (A)
10-1
B.2 Repeated Risk Minimization
In this section, we report the same learning tasks as those reported in the main text, but for Repeated Risk Minimization (RRM). In every setting, as soon as the performative effect is not negligible, the technique diverges. To ensure the readability of the figure and avoid shrinking the differences between the other algorithms, report it separately.
14

---

Table 3: Parameters used for fig.
2
Parameter
Value
Number of iterations (num_iter)
15
Sample size (n)
18000
Number of runs (n runs)
20
Step size (step_size) size)
0.2
Regularization parameter (A)
5 10-3
41
0 KMN
PMN
Recatoos
01
taratoon
(b)
Figure 3: (a) Learning a logistic regression between two Gaussian distributions centered (0, 0) and (-1, 1) and different magnitude of performative effects (b) Accuracy of classification with quadratic loss on two Gaussian of dimension with various level noise o
NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We define our approach with pushforward measure in section the application to classification insection 3 the new theorems convexity in section 4 and the relation
with robustness in section
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss our model as pushforward measures in section 2 and we discuss our theorems ensure convexity in section 4 For the experiments, acknowledge the lack of true performative datasets and use the same simulations approximation as in previous work, described in section
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All thcorems defined with their full set of assumptions, with proofs just after them or in the supplementary material (appendix A).
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
15

---

Justification: The experiments are described in section 6 Additional choice of parameters are reported appendix [
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: the code will be publicly released after publication
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The detailed parameters are in Appendix (appendix B). The choice parame- ters quite limited as the studied models have very simple architcture
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: All figures report standard deviation over the runs, as stated in legend.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [NA]
Justification: The experiments are only using small datasets so all runs were done on single laptop where the time of execution very small (few seconds per run).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The paper is conform to the NeurlPS code of Ethics.
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is theoretical and should have directly any societal impacts. In fact, raising the attention on the feedback loop that might occurs in performative learning could lead positive societal impact, better understood.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
16

---

Answer: [Yes]
Justification: We only reuse one dataset (Housing) and we cite it.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
17


Reviews:
[{"review_id": "sSbyu5X37o", "reviewer": "Reviewer_PyL2", "summary": "The authors address the challenge of performative prediction, a scenario in which the predictor's outcomes influence the underlying data distribution. They introduce a novel formulation for the gradient of the performative risk, thereby enabling the implementation of stochastic optimization methods. This new formulation offers an advantage over existing approaches by producing a gradient estimator with lower variance, particularly in cases where the data distribution shift is linear. Additionally, the authors establish a weaker sufficient condition for the convexity of the performative risk in situations involving linear classifiers and linear distributional shifts. Furthermore, they demonstrate that transform-invariant learning leads to parameter regularization. Empirical evaluations reveal that the proposed method achieves superior stable accuracy compared to existing techniques.", "questions": "- How might your approach be extended to non-linear shift scenarios?", "limitations": "The authors adequately address the limitations and potential impacts.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This well-written paper addresses a crucial problem in performative prediction that is highly relevant to the conference. The authors' theoretical contributions are clearly presented.\n\nThe proposed estimator for the performative gradient is novel and innovative. Its advantages over existing estimators are verified through an analysis of the estimator's variance under the linear shift scenario. The lower variance of this estimator results in faster convergence of the stochastic gradient descent, demonstrating its practical utility.\n\nThe authors' finding of a sufficient condition for the convexity of the performative loss under the linear shift setup is also a significant contribution. The benefits of this condition are adequately demonstrated, particularly in practical examples where existing techniques fail to verify the convexity of the performative loss.\n\nThe experimental results effectively demonstrate the superiority and stability of the proposed estimator compared to existing methods. These results indicate that the authors' method achieves greater stability while simultaneously improving accuracy, underscoring its practical applicability.", "weaknesses": "One potential limitation of the study is that the authors' analyses are primarily limited to linear shift cases. The linear shift assumption is relatively strong and may not hold in many practical scenarios. Moreover, the variance reduction effect is confirmed only under the linear shift setup, leaving the benefits of the proposed estimator in other situations unclear.\n\nThe implications of Theorem 4 require further clarification. The claim that the magnitude of $\\theta^*$ becomes smaller for a larger $\\Pi$ is questionable, as the norm $\\\\cdot\\_\\Pi$ is also affected by the magnitude of $\\Pi$. This relationship warrants a more detailed explanation or additional analysis.\n\nThe assertion that knowing $\\varphi$ is more practical than knowing $p_\\theta$ may be an overstatement. Both assumptions appear to be equally unrealistic in practical applications, and this comparison could benefit from a more nuanced discussion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for his/her positive review and address his/her questions below.\n\n**Restriction to Linear Shifts** Theorem 2 proves convexity under general assumptions thanks to the linearity of the shift, and it is unlikely that convexity holds without this assumption. However, our approach to compute the performative gradient can also be used for non-linear shifts; it will only lack the theoretical guarantees. Thus, we agree with the reviewer that it is a limitation of our work, but we believe that it is an assumption that is more general than those found in previous works on performative learning (not being limited in particular to \"small\" performative effects). On the variance reduction effect, we also agree that we proved it for the specific combination of Gaussian noise and quadratic loss only. The proof given in appendix A.1, however, suggests that it could also be extended to non-linear drifts in the Gaussian/quadratic case. The comparison between both estimators is an open question that deserves a more systematic comparison, using other distribution/loss function combinations (e.g., Laplace noise could be more favorable for the use of the score function estimator as $\\nabla_\\theta \\log p_\\theta(z)$ would then have constant magnitude), and exceeds the scope of this paper.\n\n**Effect of Norm of $\\Pi$** We agree with the reviewer that the comment under Theorem 4 is a bit hasty, we will make it clearer in the final version. The effect can be seen as follows: if $\\Pi$ gets larger the r.h.s. decreases while the l.h.s. increases for identical values of $\\theta$ (due to the fact that the norm depends on $\\Pi$ as noted by the reviewer); hence values of $\\theta$ have to be \"smaller\". The example given in lines 282--286 also illustrates this effect.\n\n\n**Knowledge of $\\varphi$** We refer to the responses to reviewers eHFF and uddR on this point.  \n\n**Questions on Extension to Non-Linear Shift Scenarios** As discussed above, this case is similar from a practical point of view and the same learning algorithm can be used but convexity of the performative learning would be most likely lost. Extension to transformations other than shifts however should be more difficult due to the necessity to consider the derivative of the log-Jacobian term. Note that the shift only needs to be linear in an embedding space, which covers already a large spectrum of situations.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PucLqrQAZe", "reviewer": "Reviewer_uddR", "summary": "This paper considers a specific performative effect that's characterized as a transformation on the original probability measure on covariate X, which is novel in the literature. The authors propose to restrict the performative effect of deploying model with parameter \\theta to such a multiplier function \\varphi_\\theta, which is mainly a shift operator in the discussion of this paper and can be viewed as a strong restriction on shift pattern. Authors also show the benefit of scalability of performative gradient estimation based on this performative effect, and demonstrate the convexity of performative risk can be achieved through direction of performative effect instead of its magnitude, in the context of binary classification and shift operator. This finding is interesting and novel in the literature. Moreover, authors show the connection with robustness and regularization by a minimax reformulation.", "questions": "1.\tCan the authors provide some intuitions on the dimension-freeness of \\hat{G}_\\theta^{R P}? I think it's a bit counterfactual since the shift \\Pi \\theta is put on the covariate X.", "limitations": "See weaknesses.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.\tThis paper clearly presents its assumption, main theorems with illustrative examples, which makes this paper easy to follow.\n2.\tThis paper generalizes the performative shift pattern in former literature without restricting to location-scale family, and reveal another path to convexity of performative risk, which is innovative.\n3.\tConnection with robustness and regularization is also presented to strengthen the background of this paper.", "weaknesses": "1.\tThe main weakness is the generality of the performative effect, \\Pi \\theta, a shift on covariate, since it's the factual pattern considered in this paper. For general \\varphi_\\theta, this paper doesn't discuss how to identify or effectively estimate such transformation function \\varphi_\\theta. Moreover, the knowledge on shift matrix \\Pi is also susceptible, since the specific mechanism of the distribution shift is usually unknown in the context of performative prediction.\n2.\tIn the synthetic experiments, I think the authors should explore more abundant \\varphi_\\theta and show the benefit of scalability for high-dimensional \\theta. In fact, the experiments mainly shown in the main paper is still restricted to the 2-dimensional simple setting of Izzo et al. 2022 and neither validate such scalability nor explore general \\varphi_\\theta. In addition, the colors used for denote different methods should be more distingushable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for his/her positive review and address his/her questions below.\n\n**Knowledge of $\\Pi$** We agree with the reviewer that knowing $\\Pi$ entirely is indeed a limitation. In addition to the answers on this point given in response to reviewer PyL2 we point out that, from a theoretical point of view, the convexity arguments obtained in the paper require that $\\Pi$ is known: even in the simpler cases, the performative risk would not be convex if it was to be optimized w.r.t. both $\\theta$ and $\\Pi$. From a more practical point of view, for linearly parameterized shifts, it is very natural to estimate $\\Pi$ by ridge regression along the successive deployments of the model: the ridge penalty ensures that initially the estimate of $\\Pi$ is close to zero making the RPPerfGD updates very similar to those of RGD and it is easy to check that order $d$ deployments are enough to obtain a non void estimate of $\\Pi$. Of course, the behavior of the RPPerfGD algorithm that uses the values of $\\Pi$ estimated along the trajectory of successive model deployments would need to be studied more precisely (probably requiring more specific choices of stepsizes than in the convex case). From a practical point of view however,  we provide in the global response PDF an additional figure pertaining to the example of Section 6 showing that in this case this approach is very effective. We will add this discussion in the final version of the paper.\n\n**Comments on the Experiment Section**\nWe changed the colors to more contrasted ones. Note that figure 2b explores the impact of dimension with 7 dimensions, and the Housing dataset is also in 8 dimensions so our experiments are not limited to the 2-dimensional setting, and experiments in higher dimensions exhibits similar behaviors than in two dimensions. We also refer the reviewer to our answer to eHFF and our additionnal experiments, and would be happy to provide other similar plots during the discussion periods if a specific point can add value to the paper.\n\n**Dimension Freeness of the Covariance Estimator** The computations in Appendix A.1 shows that estimating the performative gradient is in this case fully equivalent, up to multiplication by $\\Pi^T$,  to the estimation of the mean of a multivariate Gaussian with a $\\sigma^2 I$ covariance matrix. Hence, the covariance matrix of the estimator is indeed dimension-independent. We agree with the reviewer however that in terms of interpretation of this finding there is a hidden dependence in the dimension here as the RMS error in estimating the mean of a multivariate normal is scaling as the square root of the dimension.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IcnOHDAmrL", "reviewer": "Reviewer_eHFF", "summary": "This paper studies the performative learning problem, where the goal is to minimize some measure of *performative risk*, $PR(\\theta) := \\underset{\\theta}{\\mathbb{E}}[\\ell(Z; \\theta)]$, where the difficulty is that random variables come from some distribution the depends on the deployed model parameters $\\theta$, i.e. $Z \\sim \\underset{\\theta}{\\mathbb{P}}$. The paper models the performative effect of some model parameters $\\theta$ as a pushforward measure under some differentiable, invertible mapping that depends on $\\theta$. This pushforward measure view of performative learning admits a couple of main results:\n\n1. This gives a new expression for the performative gradient (the quantity $\\nabla_{\\theta} PR(\\theta$)).\n2. For strategic classification, a specific performative learning scenario, we find that performative risk is convex under linearity assumptions on the performative shift and the classifier model. \n3. Under the same assumptions as (2), we can rewrite the performative risk as a min-max problem, connecting the performative risk in this classification scenario to adversarially robust classification.", "questions": "I have a couple of questions that may stem from my unfamiliarity with the literature:\n\n1. How restrictive is the assumption that the performative effect can be modeled by a \"shift operator\"? I didn't fully understand how natural this assumption is, and some motivation to this assumption would help the presentation. However, I understand that this might just stem from my lack of exposure to the literature.\n2. In order to estimate the gradient in Definition 1, you must have access to the form of the operator that defines the pushforward performative model, $\\psi$. How realistic is it to assume that one has access to this in a non-synthetic scenario?", "limitations": "The authors have addressed limitations in the NeurIPS paper checklist. They also motivated the problem of performative learning in their Introduction.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Overall, the paper is well-written, with a couple of clarity suggestions (in \"Weaknesses\") that may make the presentation smoother. The technical results are sound and, to my limited knowledge of the performative learning literature, the proposal to model performative shifts as a pushforward measure seems novel and interesting. However, I must emphasize that I am not very familiar with the literature on performative learning, so I cannot judge well the impact of such an approach on existing work.\n\n**Originality:** The main original contribution of this work is modeling the performative effect as a pushforward measure, which seems novel to my limited knowledge. The main results of the paper drop out of this modeling assumption, which seems flexible and general. However, I have a couple of questions towards how natural the specific instantiations of this pushforward measure are, particularly the \"shift operator\" used in many of the results (see \"Questions\").\n\n**Quality:** I cannot give too informed a judgment of the quality of the results in comparison to other literature on performative learning, but to my reading, the technical results and evaluation seem sound. The authors provide a comparison to the gradient estimator for the performative effect of Izzo et al. (2022) and demonstrate their method's efficacy in comparison. The analysis seems sound, but I have no reference for how important this comparison is or whether there are better baselines in the literature to compare to.\n\n**Clarity:** The paper is well-written overall, but I have a couple of suggestions for presentation in \"Weaknesses.\" \n\n**Significance:** As an outsider to the subfield, I cannot give a fully informed judgment on the significance of this paper, but, taking the comparison to Izzo et al. (2022) into account and viewing the displayed experiments, it seems that this modeling assumption does lead to an effective gradient estimator for performative risk.", "weaknesses": "As I am an outsider to the subfield, I cannot comment too much on the relative weaknesses of this approach to others in performative learning. I am also not aware of current results in this subfield, but it seems like optimizing this notion of performative risk is still in nascent stages if theorems like Theorem 2 exist just to show situations in which we can prove that it is convex and apply standard optimization techniques to the problem. As such, I can only give a couple of suggestions that may improve the clarity of the paper's presentation:\n\n1. Throughout the paper, the term \"performative effect\" is used quite heavily, but I believe it lacks a formal definition. I assume that we are to take the performative effect as, ultimately, the distribution $\\mathbb{P}_{\\theta}$, but it wasn't completely clear to me on a first reading of the introduction. Explicitly defining this term in the intro may help.\n2. On Page 3, when introducing the pushforward measure, I would define the \"pound\" symbol. I wasn't aware of this notation until I looked it up on Wikpedia.\n3. Small nitpick: on page 3, \"$\\mathbb{P}$ admits a density\" should specify the density $p(\\cdot)$ that $\\mathbb{P}$ admits.\n4. In the Experiments section, I didn't find your algorithm \"Reparametrization-based Performative Gradient (RPPerfGD)\" clearly defined. I assume that the algorithm just uses the gradient in Equation 3 (Definition 1) as an estimator of the gradient and performs gradient descent, but it would be helpful to explicitly write that in the Experiments section next to the baselines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for his/her positive review and address his/her questions below. We are also grateful for the four suggestions made in the weakness section to improve the clarity of the manuscript and will made the required changes in the final version of the manuscript.\n\n**Modelling the Performative Effect as a Shift** We consider that it is indeed a key specific contribution of this paper, which was not present in earlier works on performative prediction. As noted in the paper, this assumption is however inspired by the field of adversarially robust classification where the adversary-induced distribution change is also modelled by shifts of the individual data points (where an argument also used in the proof of Theorem 3 shows that the worst case shift is indeed identical for all data points when using a linear model). In addition to exhibiting novel cases in which the performative risk can be convex in classification tasks, we believe that this assumption is also important in providing a way to interpret the effect of the performative changes. To the best of our knowledge, Theorem 2 and 3 are the first results in the literature that show that, at least in the case of linear-in-parameters shifts, if the performative change tends to bring the two class distributions closer together, then it essentially leads to a regularization effect on the parameter (when compared to a model without performative changes of distribution). We believe that this idea could be used more generically to design new approaches to performative learning.\n\n**Knowing $\\varphi$ vs Knowing $p_\\theta$** While we do agree that knowing $\\varphi$ is a restrictive assumption, we still argue (and this is one of the main messages of the paper) that it is very different from knowing $p_\\theta$. Knowing $p_\\theta$ means that there is no learning problem anymore: whatever the loss function, the performative optimum could be found without training data, at worse using Monte Carlo simulations. On the other hand, even if $\\varphi$ is known one still needs to use training data to find the performative optimum (as $\\varphi$ does not fully define the data distributions, but only how they shift). Note also that, as argued in the paper, the shift could be taking place in an embedding space which adds even more generality. Finally, $\\varphi$ could also be known up to some parameters only. In the Example of Section 6, for instance one can indeed estimate the diagonal elements of $\\Pi$ using ridge regression from a very limited number of deployments and we provide in the global response PDF two additional figures showing that we need few iterations to have a good estimate of $\\Pi$ and that the gradient trajectories obtained by plugging in the value of $\\Pi$ estimated this way are very similar to those of RPPerfGD when using the exact value of $\\Pi$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their careful assessment of the manuscript and their helpful suggestions to improve the clarity. We are happy to see that reviewers recognize that our "proposed estimator for the performative gradient is novel and innovative" (PyL2) and that our assumptions are "flexible and general" (eHFF) and the connection with robustness "strengthen the background of this paper" (uddR). We provide in PDF a new experiment with estimation of $\Pi$ during the successive deployments, reporting the impact on the accuracy and the convergence of $\Pi$. More details and the code of this experiment will be included in the final version of the paper. We answer specifically to each reviewer below.

Meta-review: This paper proposed a new method to estimate the gradient under a performative distribution shift setting. They relied on a specific "Push-forward Performative Model" assumption. While some reviewers pointed out that the experiments are relatively of a small scale, and the estimation of the pushforward map is not easy, all reviewers agreed that the paper should be accepted due to the innovations presented; especially due to the theoretical convexity and variance-reduction results.
Decision: Accept (poster)