Performative Prediction with Neural Networks
Performative prediction is a framework for learning models that influence the
data they intend to predict. We focus on finding classifiers that are
performatively stable, i.e. optimal for the data distribution they induce.
Standard convergence results for finding a performatively stable classifier
with the method of repeated risk minimization assume that the data distribution
is Lipschitz continuous to the model's parameters. Under this assumption, the
loss must be strongly convex and smooth in these parameters; otherwise, the
method will diverge for some problems. In this work, we instead assume that the
data distribution is Lipschitz continuous with respect to the model's
predictions, a more natural assumption for performative systems. As a result,
we are able to significantly relax the assumptions on the loss function. In
particular, we do not need to assume convexity with respect to the model's
parameters. As an illustration, we introduce a resampling procedure that models
realistic distribution shifts and show that it satisfies our assumptions. We
support our theory by showing that one can learn performatively stable
classifiers with neural networks making predictions about real data that shift
according to our proposed procedure.
Mehrnaz Mofakhami, Ioannis Mitliagkas, Gauthier Gidel
# Performative Prediction with Neural Networks

###### Abstract

Performative prediction is a framework for learning models that influence the data they intend to predict. We focus on finding classifiers that are _performatively stable_, i.e. optimal for the data distribution they induce. Standard convergence results for finding a performatively stable classifier with the method of repeated risk minimization assume that the data distribution is Lipschitz continuous to the _model's parameters_. Under this assumption, the loss _must_ be strongly convex and smooth in these parameters; otherwise, the method will diverge for some problems. In this work, we instead assume that the data distribution is Lipschitz continuous with respect to the _model's predictions_, a more natural assumption for performative systems. As a result, we are able to significantly relax the assumptions on the loss function. In particular, we do not need to assume convexity with respect to the model's parameters. As an illustration, we introduce a resampling procedure that models realistic distribution shifts and show that it satisfies our assumptions. We support our theory by showing that one can learn performatively stable classifiers with neural networks making predictions about real data that shift according to our proposed procedure.

## 1 Introduction

One of the main challenges in many of the decision-making tasks is that the data distribution changes over time. This concept is known as distribution shift or concept drift (Gama et al., 2014; Tsymbal, 2004; Quionero-Candela et al., 2009). With a changing data distribution, the performance of a supervised learning classifier may degrade since it implicitly assumes a static relationship between input and output variables (Fang et al., 2020). _Performative prediction_ is a framework introduced by Perdomo et al. (2020) to deal with this problem when the distribution changes as a consequence of model deployment, usually through actions taken based on the model's predictions. For example, election predictions affect campaign activities and, in turn, influence the final election results. This performative behavior arises naturally in many problems of economics, social sciences, and machine learning, such as in loan granting, predictive policing, and recommender systems (Perdomo et al., 2020; Krauth et al., 2022; Ensign et al., 2018).

So far, most works in this area assume strong convexity of the risk function \(\theta\mapsto\ell(z;\theta)\), which takes as input the model's parameters \(\theta\), and a data point \(z\)(Perdomo et al., 2020; Mendler-Dunner et al., 2020; Brown et al., 2022). For example, Perdomo et al. (2020) show that by assuming strong convexity and smoothness of the loss function along with some regularity assumptions on the data generation process, repeated retraining converges to a performative stable classifier, which is a model that is optimal for the distribution it induces. However, this strong convexity assumption does not hold for most modern ML models, e.g. neural networks. From a different perspective, given a data point \((x,y)\), the risk function can be expressed as a mapping from the prediction \(x\mapsto f_{\theta}(x)\) to a loss between the prediction \(\hat{y}:=f_{\theta}(x)\) and the target \(y\), in which case convexity almost always holds. Consider, for example, the Squared Error loss function in a binary classification problem where \(\ell(f_{\theta}(x),y)=\frac{1}{2}(f_{\theta}(x)-y)^{2}\) for a data point \(z=(x,y)\); it is convex with respect to the model's predictions \(f_{\theta}(x)\), but not necessarily with respect to the model's parameters \(\theta\).

With this in mind, we propose a different perspective and formulation that shifts attention from the space of parameters to the space of predictions. More precisely, we require distributions to be functions of the model's prediction function instead of its parameters. The rationale behind this is that in many scenarios with performative effects of a classifier in the loop, the model's predictions are the quantities of interest rather than its parameters. Actually, the framework assumes the data distribution changes as a result of model deployment, and at the time of deployment, it is the final predictions that matter rather than the parameters which led to those predictions.
Within our formulation, we show that by having a stronger assumption on the distribution map than the original framework, we can relax the convexity condition on the loss function and prove the existence and uniqueness of a performative stable classifier under repeated risk minimization with significantly weaker assumptions with regard to the regularity of the loss. Informally, these assumptions include strong convexity of the loss with respect to the predictions, the boundedness of the derivative of the loss function, and the Lipschitzness of the distribution map with respect to the \(\chi^{2}\) divergence. This more general set of assumptions on the loss function lets us theoretically analyze the performative effects of neural networks with non-convex loss functions; we believe this is a significant step toward bridging the gap between the theoretical performative prediction framework and realistic settings. Our setting and the main theoretical results will be explained in Section 2.

### Background

Before stating our main theoretical contribution, we first recall the key concepts of the performative prediction framework. The main difference between classic supervised learning and the performative prediction framework is that the latter considers the data distribution to be model-dependent, i.e. it assumes that the distribution map directly depends on the model's parameters \(\theta\) and is denoted by \(\theta\mapsto\mathcal{D}(\theta)\). The distribution map is said to satisfy a notion of Lipschitz continuity called _\(\epsilon\)-sensitivity_ if for any \(\theta\) and \(\theta^{\prime}\), \(\mathcal{W}_{1}\left(\mathcal{D}(\theta),\mathcal{D}(\theta^{\prime})\right) \leq\epsilon\|\theta-\theta^{\prime}\|_{2}\), where \(\mathcal{W}_{1}\) denotes the Wasserstein-1 distance. The performance of a model with parameters \(\theta\) is measured by its _performative risk_ under the loss function \(\ell\) which is stated as a function of a data point \(z\) and \(\theta\):

\[PR(\theta)\stackrel{{\text{def}}}{{=}}\operatorname*{\mathbb{E }}_{z\sim\mathcal{D}(\theta)}\ell(z;\theta).\]

A classifier with parameters \(\theta_{\text{PS}}\) is _performatively stable_ if it minimizes the risk on the distribution it induces. In other words, it is the fixed point of repeated retraining.

\[\theta_{\text{PS}}=\arg\min_{\theta\in\Theta}\operatorname*{\mathbb{E}}_{z \sim\mathcal{D}(\theta_{\text{PS}})}\ell(z;\theta).\]

Perdomo et al. (2020) demonstrate that with an \(\epsilon\)-sensitive distribution map, \(\gamma\)-strong convexity of \(\ell\) in \(\theta\) and \(\beta\)-smoothness of \(\ell\) in \(\theta\) and \(z\) are sufficient and _necessary_ conditions for repeated risk minimization to converge to a performatively stable classifier if \(\frac{\epsilon\beta}{\gamma}<1\). We show, however, that by slightly changing the assumptions on the distribution map, we can break their negative result regarding the necessary strong convexity and show that one can converge even when the loss is non-convex in \(\theta\).

### Our contributions

Our paper provides sufficient conditions for the convergence of repeated risk minimization to a classifier with unique predictions under performative effects in the absence of convexity to the model's parameters. The key idea in our framework is that the distribution map is no longer a function of the parameters \(\theta\), but a function of model's predictions, denoted by \(\mathcal{D}(f_{\theta})\) where \(f_{\theta}\) is in \(\mathcal{F}\), the set of parameterized functions by \(\theta\in\Theta\). We also express the loss \(\ell\) as a function of the prediction \(f_{\theta}(x)\) and the target \(y\), where both can be multi-dimensional. Following is the informal statement of our main theorem.

**Theorem 1**.: _(Informal) If the loss \(\ell(f_{\theta}(x),y)\) is strongly convex in \(f_{\theta}(x)\) with a bounded gradient norm, and the distribution map \(f_{\theta}\mapsto\mathcal{D}(f_{\theta})\) is sufficiently Lipschitz with respect to the \(\chi^{2}\) divergence and satisfies a bounded norm ratio condition, then repeated risk minimization converges linearly to a stable classifier with unique predictions._

We will state this theorem formally in section 2. The critical assumption we make on the distribution map is Lipschitz continuity, which captures the idea that a small change in the model's predictions cannot lead to a large change in the induced data distribution, as measured by the \(\chi^{2}\) divergence. This is more restrictive than the Lipschitz continuity assumption of Perdomo et al. (2020) with \(\mathcal{W}_{1}\), since for the \(\chi^{2}\) divergence to be finite, distributions should have the same support. However, we show that this still holds in realistic settings, and we discuss that this stronger assumption on the distribution map is a price we have to pay to relax the assumptions on the loss function significantly and have convergence guarantees for neural networks with non-convex loss functions.

In section 4, we demonstrate our main results empirically with a _strategic classification_ task, which has been used as a benchmark for performative prediction (Perdomo et al., 2020; Miller et al., 2021; Brown et al., 2022). Strategic classification involves an institution that deploys a classifier and agents who strategically manipulate their features to alter the classifier's predictions to get better outcomes. We propose a resampling procedure called _Resample-if-Rejected (RIR)_ in Section 3 to model the population's strategic responses and show that it results in a distribution map that satisfies the conditions of Theorem 1.

Within this process, a sample \(x\) is drawn from the base distribution and is rejected with some probability dependent on \(f_{\theta}(x)\) and accepted otherwise; in case of rejection, another sample from the base distribution will be drawn.

A real-life example that this procedure may be able to model is regarding posting content on social media. Actually, social media use many ML models to automatically regulate the content posted by the users. Consequently, some users' posts may be rejected by the automatic regulation because their content was considered to violate the platform's community guidelines. In some situations, the authors might consider this rejection unfair and may tweak some parts of the post in order to get accepted. In our experiments, we
model this resubmission by resampling some strategic features (i.e., features that do not drastically affect the content and that are easily modifiable) of the post.

### Related work

Prior work on performative prediction focused on learning from a data distribution \(\mathcal{D}(\theta)\) that could change with the model's parameter \(\theta\)(Perdomo et al., 2020; Mendler-Dunner et al., 2020; Brown et al., 2022; Drusvyatskiy and Xiao, 2022; Miller et al., 2021; Izzo et al., 2021; Maheshwari et al., 2022; Ray et al., 2022; Li and Wai, 2022; Dong and Ratliff, 2021; Jagadeesan et al., 2022). In this work, we propose to strengthen the standard \(\epsilon\)-sensitivity assumption on the distribution map initially proposed by Perdomo et al. (2020). To a certain extent, we propose a novel \(\epsilon\)-sensitivity assumption for the performative prediction framework that allows us to relax the convexity assumption on the loss function. Such relaxation is essential if we want to consider the practical setting of classifiers parametrized by neural networks.

At a technical level, our analysis is inspired by Perdomo et al. (2020, Theorem 3.5). However, because our quantity of interest is a distance in the function space (see Theorem 2) our proof significantly differs from Perdomo et al. (2020). We require a different notion of \(\epsilon\)-sensitivity and an additional assumption (Assumption 2) in order to control the variation of the functional norm defined in Assumption 1.

Various prior works have focused on finding performatively stable classifiers (Perdomo et al., 2020; Brown et al., 2022; Mendler-Dunner et al., 2020; Li and Wai, 2022), but to the best of our knowledge, none of them analyze the convergence of repeated retraining with loss functions that might be non-convex to the model's parameters.

Exploiting convexity in the model's predictions has previously been explored by Bengio et al. (2005), who noticed that most of the loss functions to train neural networks are convex with respect to the neural network itself. There have been many works trying to leverage this property to show convergence results applied to neural networks in the context of machine learning (Bach, 2017; Chizat and Bach, 2018; Mladenovic et al., 2021). However, none of these results are in the context of performative prediction. Jagadeesan et al. (2022) proposes an algorithm to find classifiers with near-optimal performative risk without assuming convexity. First, their work focuses on a different notion of optimality (namely, performatively optimal points). Second, they focus on regret minimization, while our work is concerned with finding a performatively stable classifier with gradient-based algorithms and having guarantees to make sure we converge to such a stable classifier within a reasonable number of steps.1

Footnote 1: For a \(\delta\)-approximate optimum, Jagadeesan et al. (2022) propose an algorithm that requires \(O(1/\delta^{d})\) repeated minimizations for the last iterate where \(d\) is some notion of dimension. In comparison, in Theorem 2 we require \(O(\log(1/\delta))\) minimizations.

Similarly to our work, 2 assume that the performativity of a model occurs through its predictions and consider the distribution a function of the predictive model. However, this paper has a different focus entirely; they try to find a set of conditions under which the causal effect of predictions becomes identifiable. Additionally, they focus on a subset of performative prediction problems where predictions only influence the target variable and not the features \(X\). Hence, their analysis does not capture strategic classification.

## 2 Framework and Main Results

To propose our main theorem, we first need to redefine some of the existing concepts. As mentioned earlier, we assume \(\mathcal{D}(\theta)\) to be a mapping from the model's prediction function \(f_{\theta}\) to a distribution \(\mathcal{D}(f_{\theta})\) over instances \(z\), where \(f_{\theta}\) is in \(\mathcal{F}\), the set of parameterized functions by \(\theta\in\Theta\). Each instance \(z\) is a pair of features and label \((x,y)\). With this new formulation, the objective risk function will be defined as follows:

**Definition 2.1** (_Performative Risk_).: _Performative risk (PR) is defined as follows:_

\[PR(f_{\theta})\stackrel{{\text{def}}}{{=}}\operatorname*{\mathbb{E }}_{z\sim\mathcal{D}(f_{\theta})}\ell(f_{\theta}(x),y).\]

In this work, we focus on finding a performatively stable classifier, which minimizes the risk on the distribution its prediction function entails:

**Definition 2.2**.: _A classifier with parameters \(\theta_{\text{PS}}\) is performatively stable if:_

\[\theta_{\text{PS}}=\arg\min_{\theta\in\Theta}\operatorname*{\mathbb{E}}_{z\sim \mathcal{D}(f_{\theta_{\text{PS}}})}\ell(f_{\theta}(x),y).\]

Repeated retraining is the algorithm we use to find a stable classifier, which is defined formally as follows:

**Definition 2.3** (_Rrh_).: _Repeated Risk Minimization (RRM) refers to the procedure where, starting from an initial \(\theta_{0}\), we perform the following sequence of updates for every \(t\geq 0\):_

\[\theta_{t+1}=G(\theta_{t})\stackrel{{\text{def}}}{{=}}\arg\min_{ \theta\in\Theta}\operatorname*{\mathbb{E}}_{z\sim\mathcal{D}(f_{\theta_{t}})} \ell(f_{\theta}(x),y).\]

### Assumptions

In order to provide convergence guarantees for repeated retraining, we require regularity assumptions on the distribution map and the loss function. A natural assumption we make on \(\mathcal{D}(.)\) inspired by prior work is Lipschitz continuity, formally referred to as \(\epsilon\)-_sensitivity_. Intuitively, this assumption states the idea that if two models with similar
prediction functions are deployed, then the induced distributions should also be similar. We refer to the _base distribution_\(\mathcal{D}\) as the distribution over (features, label) pairs before any classifier deployment.

**Assumption 1**.: _(A1) [\(\epsilon\)-sensitivity w.r.t Pearson \(\chi^{2}\) divergence] Suppose the base distribution \(\mathcal{D}\) has the probability density function (pdf) \(p\) over instances \(z=(x,y)\). The distribution map \(\mathcal{D}(.)\) which maps \(f_{\theta}\) to \(\mathcal{D}(f_{\theta})\) with the pdf \(p_{f_{\theta}}\) is \(\epsilon\)-sensitive w.r.t Pearson \(\chi^{2}\) divergence, i.e., for all \(f_{\theta}\) and \(f_{\theta^{\prime}}\) in \(\mathcal{F}\) the following holds:_

\[\chi^{2}(\mathcal{D}(f_{\theta^{\prime}}),\mathcal{D}(f_{\theta}))\leq \epsilon\|f_{\theta}-f_{\theta^{\prime}}\|^{2},\]

_where \(\|f_{\theta}-f_{\theta^{\prime}}\|^{2}:=\int\|f_{\theta}(x)-f_{\theta^{\prime }}(x)\|^{2}p(x)dx\) and \(\chi^{2}(\mathcal{D}(f_{\theta^{\prime}}),\mathcal{D}(f_{\theta})):=\int \frac{(p_{f_{\theta^{\prime}}}(z)-p_{f_{\theta}}(z))^{2}}{p_{f_{\theta}}(z)}dz\)_

**Assumption 2**.: _(A2) [Bounded norm ratio] The distribution map \(\mathcal{D}(.)\) satisfies bounded norm ratio with the parameter \(C\geq 1\) if for all \(f_{\theta},f_{\theta^{\prime}},f_{\theta^{\prime}}\in\mathcal{F}\):_

\[\|f_{\theta}-f_{\theta^{\prime}}\|^{2}\leq C\|f_{\theta}-f_{\theta^{\prime}} \|^{2}_{f_{\theta^{\prime}}},\]

_where_

\[\|f_{\theta}-f_{\theta^{\prime}}\|^{2}_{f_{\theta^{\prime}}}=\int\|f_{\theta} (x)-f_{\theta^{\prime}}(x)\|^{2}p_{f_{\theta^{\prime}}}(x)dx\]

_is a notation for an \(f_{\theta^{\prime}}\)-dependent norm. In other words, this assumption says that_

\[\mathbb{E}_{p(x)}[\|f_{\theta}(x)-f_{\theta^{\prime}}(x)\|^{2}]\leq C\, \mathbb{E}_{p_{f_{\theta^{\prime}}}(x)}[\|f_{\theta}(x)-f_{\theta^{\prime}} (x)\|^{2}],\]

_where \(p(x)\) and \(p_{f_{\theta^{\prime}}}(x)\) are pdfs for the marginal distribution of \(X\) according to \(\mathcal{D}\) and \(\mathcal{D}(f_{\theta^{\prime}})\) respectively._

The distribution map satisfies the bounded norm ratio condition if the bounded density ratio property holds, i.e. \(p(x)\leq C\;p_{f_{\theta}}(x)\) for every \(f_{\theta}\in\mathcal{F}\). We will show how the bounded density ratio holds in our example in Section 3.

Our notion of Lipschitz Continuity uses the Pearson \(\chi^{2}\) divergence--interchangeably referred to as \(\chi^{2}\) divergence--to measure the distance between distributions, as opposed to Perdomo et al. (2020) who use \(\mathcal{W}_{1}\) distance. Using \(\chi^{2}\) divergence is more restrictive since the distributions should have the same support for the \(\chi^{2}\) divergence between them to be finite.

As stated in Remark 1, \(\epsilon\)-sensitivity with respect to \(\chi^{2}\) implies \(K\sqrt{\epsilon}\)-sensitivity with respect to \(\mathcal{W}_{1}\) for a constant \(K\) that depends on the diameter of the space \(d_{max}\). If \(\frac{d_{max}}{\sqrt{2}}<\sqrt{\epsilon}\), our notion of \(\epsilon\)-sensitivity w.r.t \(\chi^{2}\) is indeed stronger than the corresponding notion of \(\epsilon\)-sensitivity w.r.t \(\mathcal{W}_{1}\). However, in Proposition 1 we show that within our settings, we cannot replace \(\chi^{2}\) with \(\mathcal{W}_{1}\) and still get convergence results.

**Remark 1**.: _For two distributions \(\mathcal{D}(x)\) and \(\mathcal{D}^{\prime}(x)\), the \(\mathcal{W}_{1}\) distance is upper bounded by a coefficient of the square root of \(\chi^{2}\) divergence (Peyre et al., 2019, Figure 8.2):_

\[\mathcal{W}_{1}(\mathcal{D}(x),\mathcal{D}^{\prime}(x))\leq\frac{d_{max}}{ \sqrt{2}}\sqrt{\chi^{2}(\mathcal{D}(x),\mathcal{D}^{\prime}(x))},\]

_where \(\mathcal{X}\) is a metric space with ground distance \(d\) and \(d_{max}=\sup_{(x,x^{\prime})}d(x,x^{\prime})\) is the diameter of \(\mathcal{X}\). If we define \(\epsilon\)-sensitivity of \(\mathcal{D}(.)\) w.r.t \(\mathcal{W}_{1}\) as_

\[\mathcal{W}_{1}(\mathcal{D}(f_{\theta}),\mathcal{D}(f_{\theta^{\prime}}))\leq \epsilon\|f_{\theta}-f_{\theta^{\prime}}\|,\qquad(A1)^{\prime}\]

_then \(\epsilon\)-sensitivity w.r.t \(\chi^{2}\) implies \(\frac{d_{max}}{\sqrt{2}}\sqrt{\epsilon}\)-sensitivity with respect to \(\mathcal{W}_{1}\):_

\[\mathcal{W}_{1}(\mathcal{D}(f_{\theta}),\mathcal{D}(f_{\theta^{\prime}}))\leq \frac{d_{max}}{\sqrt{2}}\sqrt{\epsilon}\|f_{\theta}-f_{\theta^{\prime}}\|.\]

Despite the downsides of our assumptions on the distribution map, these assumptions still hold in some realistic settings, an example of which is a resampling procedure proposed in Section 3. The idea of this distribution shift is that individuals are more likely to change their features (by resampling them) if there is a high chance that they will receive an unfavorable classification outcome, which is quantified by the model's prediction.

While imposing a more restrictive assumption on the distribution map, we significantly relax the assumptions on the loss function. In particular, we no longer need to assume that loss is convex to the model's parameters, which opens the door to consider deep neural networks as classifiers in our analysis. We still require some mild assumptions on the loss function \(\ell\) that are as follows:

**Assumption 3**.: _(A3) [Strong convexity w.r.t predictions] The loss function \(\ell(f_{\theta}(x),y)\) which takes as inputs the prediction \(f_{\theta}(x)\) and the target \(y\), is \(\gamma\)-strongly convex in \(f_{\theta}(x)\). More precisely, the following inequality holds for every \(f_{\theta},f_{\theta^{\prime}}\in\mathcal{F}\):_

\[\ell(f_{\theta}(x),y) \geq\ell(f_{\theta^{\prime}}(x),y)+\] \[(f_{\theta}(x)-f_{\theta^{\prime}}(x))^{\top}\nabla_{\hat{y}}\ell( f_{\theta^{\prime}}(x),y)+\] \[\frac{\gamma}{2}\|f_{\theta}(x)-f_{\theta^{\prime}}(x)\|^{2},\]

_where \(\nabla_{\hat{y}}\ell(f_{\theta}(x),y)\) is the gradient of the function \(\hat{y}\in\mathbb{R}^{d}\mapsto\ell(\hat{y},y)\) at \(f_{\theta}(x)\)._

**Assumption 4**.: _(A4) [Bounded gradient norm] The loss function \(\ell(f_{\theta}(x),y)\) has bounded gradient norm, i.e., the norm of its gradient with respect to \(f_{\theta}(x)\) is upper bounded with a finite value \(M=\sup_{x,y,\theta}\|\nabla_{\hat{y}}\ell(f_{\theta}(x),y)\|\)._

We can easily see that these two assumptions on \(\ell\) are satisfied by the Squared Error loss: \(\ell(f_{\theta}(x),y)=\frac{1}{2}\|f_{\theta}(x)-y\|^{2}\). This function is \(1\)-strongly convex with a bounded gradient norm of \(\sqrt{d}\) if \(y\) is a one-hot vector in \(\mathbb{R}^{d}\) and \(f_{\theta}(x)\in[0,1]^{d}\) for any \(\theta\). More broadly, when the predictions are bounded, e.g. in \([0,1]^{d}\), then the quantity \(M\) in
Assumption 4 always exists for continuously differentiable loss functions which makes it a very mild assumption.

In Section 2.2 we show that if assumptions \(A1-A4\) are satisfied for a distribution map and a loss function, then RRM converges to a unique stable classifier if \(\frac{\sqrt{C\epsilon}M}{\gamma}\) is less than \(1\). Proposition 1 shows that replacing \(\epsilon\)-sensitivity w.r.t \(\chi^{2}\) (\(A\) 1) with \(\epsilon\)-sensitivity w.r.t \(\mathcal{W}_{1}\) (\(A1\))\({}^{\prime}\) while keeping other assumptions would break this convergence result, in the sense that RRM will oscillate between two models forever. This justifies why we cannot use \(\mathcal{W}_{1}\) within our analysis.

**Proposition 1**.: _Suppose that the loss \(\ell(f_{\theta}(x),y)\) is \(\gamma\)-strongly convex in \(f_{\theta}(x)\), and has a derivative bounded by \(M\). If the distribution map satisfies the bounded norm ratio property with a parameter \(C\), and it is \(\epsilon\)-sensitive w.r.t \(\mathcal{W}_{1}\) (\(A1\))\({}^{\prime}\), RRM may diverge for any value of \(\epsilon\), particularly even if \(\frac{\sqrt{C\epsilon}M}{\gamma}<1\)._

Proof.: Consider a supervised learning problem where a model with parameters \(\theta\) uses the prediction function \(f_{\theta}(x)=\frac{\tanh(\theta)+2}{\epsilon}x\) where \(x\in[0,3\epsilon]\). Take the base distribution on \(X\) as a uniform distribution over this interval.

The loss function is defined as

\[\ell(f_{\theta}(x),y)=\frac{-15\gamma}{4}(f_{\theta}(x)-y)+\frac{\gamma}{2}f_ {\theta}(x)^{2}+\frac{\gamma}{2}y^{2}+\gamma(\frac{15}{4})^{2}.\]

This \(\ell\) is non-negative, \(\gamma\)-strongly convex w.r.t \(f_{\theta}(x)\), and its derivative in \(f_{\theta}(x)\) is bounded.

Let the distribution of \(X\) according to \(\mathcal{D}(f_{\theta})\) be a point mass at \(f_{\theta}(\epsilon^{2})=\epsilon(\tanh(\theta)+2)\) and the distribution of \(Y\) be invariant w.r.t \(f_{\theta}\).

\(\mathcal{D}(f_{\theta})\) is \(\epsilon\)-sensitive w.r.t the Wasserstein-1 distance:

Choose \(f_{\theta}\) and \(f_{\theta^{\prime}}\) arbitrarily. It is easy to see that

\[\mathcal{W}_{1}(\mathcal{D}(f_{\theta}),\mathcal{D}(f_{\theta^{\prime}}))\leq \epsilon|\tanh(\theta)-\tanh(\theta^{\prime})|. \tag{1}\]

\[\|f_{\theta}-f_{\theta^{\prime}}\|^{2} =\int_{0}^{3\epsilon}(f_{\theta}(x)-f_{\theta^{\prime}}(x))^{2}p( x)dx\] \[=\int_{0}^{3\epsilon}\frac{(\tanh(\theta)-\tanh(\theta^{\prime}) )^{2}}{\epsilon^{2}}x^{2}p(x)dx\] \[=\frac{(\tanh(\theta)-\tanh(\theta^{\prime}))^{2}}{\epsilon^{2}} \frac{1}{3\epsilon}\int_{0}^{3\epsilon}x^{2}dx\] \[=\frac{(\tanh(\theta)-\tanh(\theta^{\prime}))^{2}}{3\epsilon^{3}} \frac{(3\epsilon)^{3}}{3}\] \[=3\left(\tanh(\theta)-\tanh(\theta^{\prime})\right)^{2}. \tag{2}\]

As a result,

\[\|f_{\theta}-f_{\theta^{\prime}}\|=\sqrt{3}|\tanh(\theta)-\tanh(\theta^{ \prime})|. \tag{3}\]

Combining (1) and (3) results in the \(\epsilon\)-sensitivity:

\[\mathcal{W}_{1}(\mathcal{D}(f_{\theta}),\mathcal{D}(f_{\theta^{\prime}}))\leq \epsilon\|f_{\theta}-f_{\theta^{\prime}}\|.\]

Also, this distribution map satisfies the bounded norm ratio property with any \(C>3\) since:

\[\|f_{\theta}-f_{\theta^{\prime}}\|_{f_{\theta^{\prime}}}^{2}\] \[=\big{(}(\tanh(\theta)-\tanh(\theta^{\prime}))(\tanh(\theta^{*})+ 2)\big{)}^{2}\] \[>(\tanh(\theta)-\tanh(\theta^{\prime}))^{2}, \tag{4}\]

where we used the fact that \((\tanh(\theta^{*})+2)>1\).

Putting (2) and (4) together, we can write

\[\|f_{\theta}-f_{\theta^{\prime}}\|^{2}\leq C\ \|f_{\theta}-f_{\theta^{\prime}}\|_{f _{\theta^{*}}}^{2}\]

for every \(C>3\).

The update rule of RRM is as follows:

\[\theta_{t+1} =\operatorname*{argmin}_{\phi}\mathbb{E}_{z\sim\mathcal{D}(f_{ \theta_{t}})}[\ell(f_{\phi}(x),y)]\] \[=\operatorname*{argmin}_{\phi}\ell(f_{\phi}(x),y)\bigg{|}_{x= \epsilon(\tanh(\theta_{t})+2)}.\]

Taking the derivative of the loss and setting it to zero results in:

\[(\tanh(\theta_{t+1})+2)(\tanh(\theta_{t})+2)=\frac{15}{4}.\]

So if \(\theta_{t}=\tanh^{-1}(\frac{-1}{2})\), then \(\theta_{t+1}=\tanh^{-1}(\frac{1}{2})\) and if \(\theta_{t}=\tanh^{-1}(\frac{1}{2})\), then \(\theta_{t+1}=\tanh^{-1}(\frac{-1}{2})\).

In conclusion, while the loss function satisfies assumptions (A3) and (A4) and the distribution map satisfies conditions \((A1)\)\({}^{\prime}\) and (A2), RRM oscillates between \(\tanh^{-1}(\frac{-1}{2})\) and \(\tanh^{-1}(\frac{1}{2})\) with \(\theta_{0}=\tanh^{-1}(\frac{-1}{2})\), for any value of \(\epsilon,\gamma,C>3\), including when \(\frac{\sqrt{C\epsilon}M}{\gamma}<1\). 

### Convergence of RRM

Here we state our main theoretical contribution, which provides sufficient conditions for repeated risk minimization to converge to a stable classifier with unique predictions.

**Theorem 2**.: _Suppose that the loss \(\ell(f_{\theta}(x),y)\) is \(\gamma\)-strongly convex w.r.t \(f_{\theta}(x)\) (A3) and the norm of its gradient w.r.t \(f_{\theta}(x)\) is upper bounded with \(M=\sup_{x,y,\theta}\|\nabla_{\hat{\theta}}\ell(f_{\theta}(x),y)\|\) (A4). If the distribution map \(\mathcal{D}(.)\) is \(\epsilon\)-sensitive w.r.t Pearson \(\chi^{2}\) divergence (A1) and satisfies bounded norm ratio property with parameter \(C\) (A2), then:_

\[\|f_{G(\theta)}-f_{G(\theta^{\prime})}\|\leq\frac{\sqrt{C\epsilon}M}{\gamma}\|f_ {\theta}-f_{\theta^{\prime}}\|.\]

_So if \(\frac{\sqrt{C\epsilon}M}{\gamma}<1\), \(G\) is a contractive mapping and RRM converges to a stable classifier at a linear rate:_

\[\|f_{\theta_{t}}-f_{\theta_{PS}}\|\leq\alpha,\]

\[\text{for}\quad t\geq(1-\frac{\sqrt{C\epsilon}M}{\gamma})^{-1}\log(\frac{\|f_{ \theta_{0}}-f_{\theta_{PS}}\|}{\alpha}).\]
As we mentioned earlier, assumptions (A3) and (A4) on \(\ell\) are satisfied by the commonly-used Squared Error loss function, and this holds even in the presence of deep neural networks as predictors. To illustrate our results, we propose the _Resample-if-Rejected_ procedure in the following section and show that it satisfies assumptions (A1) and (A2). We provide a proof sketch for Theorem 2 here, though the full proof is available in Supplementary materials.

Proof Sketch.: Fix \(\theta\) and \(\theta^{\prime}\) in \(\Theta\). Let \(h\) and \(h^{\prime}\) be mappings from \(\mathcal{F}\) to \(\mathbb{R}\) defined as follows:

\[h(f_{\hat{\theta}})=E_{z\sim\mathcal{D}(f_{\theta})}[\ell(f_{\hat{\theta}}(x), y)]=\int\ell(f_{\hat{\theta}}(x),y)p_{f_{\theta}}(z)dz.\]

\[h^{\prime}(f_{\hat{\theta}})=E_{z\sim\mathcal{D}(f_{\theta^{\prime}})}[\ell(f_ {\hat{\theta}}(x),y)]=\int\ell(f_{\hat{\theta}}(x),y)p_{f_{\theta^{\prime}}}(z )dz.\]

Because of the strong convexity of \(\ell(f_{\theta}(x),y)\) in \(f_{\theta}(x)\) and the fact that \(f_{G(\theta)}\) minimizes \(h\), we can show that

\[-\gamma\|f_{G(\theta)}-f_{G(\theta^{\prime})}\|_{f_{\theta}}^{2}\geq\] \[\int\big{(}f_{G(\theta)}(x)-f_{G(\theta^{\prime})}(x)\big{)}^{ \top}\nabla_{\hat{y}}\ell(f_{G(\theta^{\prime})}(x),y)p_{f_{\theta}}(z)dz, \tag{5}\]

where

\[\|f_{G(\theta)}-f_{G(\theta^{\prime})}\|_{f_{\theta}}^{2}=\int\|f_{G(\theta)}( x)-f_{G(\theta^{\prime})}(x)\|^{2}p_{f_{\theta}}(x)dx.\]

Because of this \(f_{\theta}\)-dependent norm, assumption 2 is required so we can remove this dependency later.

Using \(\epsilon\)-sensitivity of \(\mathcal{D}(.)\) w.r.t the \(\chi^{2}\) divergence, and the bounded gradient norm assumption which states that there exists a finite value \(M\) such that \(M=\sup_{x,y,\theta}\|\nabla_{\hat{y}}\ell(f_{\theta}(x),y)\|\), alongside the fact that \(f_{G(\theta^{\prime})}\) minimizes \(h^{\prime}\), we derive that

\[\int\big{(}f_{G(\theta)}(x)-f_{G(\theta^{\prime})}(x)\big{)}^{ \top}\nabla_{\hat{y}}\ell(f_{G(\theta^{\prime})}(x),y)p_{f_{\theta}}(z)dz\geq\] \[-M\sqrt{\epsilon}\|f_{G(\theta)}-f_{G(\theta^{\prime})}\|_{f_{ \theta}}\|f_{\theta}-f_{\theta^{\prime}}\| \tag{6}\]

which provides a lower bound on the RHS of (5).

Combining (5) and (6) with the fact that the distribution map \(\mathcal{D}(.)\) satisfies the bounded norm ratio property with parameter \(C\) results in

\[\|f_{G(\theta)}-f_{G(\theta^{\prime})}\|\leq\frac{\sqrt{C\epsilon}M}{\gamma}\| f_{\theta}-f_{\theta^{\prime}}\|.\]

So for \(\frac{\sqrt{C\epsilon}M}{\gamma}<1\), RRM converges to a stable classifier based on the Banach fixed-point theorem.

Setting \(\theta=\theta_{t-1}\) and \(\theta^{\prime}=\theta_{PS}\), we can show that this convergence has a linear rate. 

## 3 \(\epsilon\)-Sensitivity of the RIR procedure

An example of strategic classification, which was introduced in section 1.2, occurs in social media when users' posts get rejected because they violated the platform's policies. In these cases, users usually re-post the same content but with different words in order to get accepted. Inspired by this application, we propose the _Resample-if-Rejected (RIR)_ procedure to model distribution shifts. Consider we have a base distribution with pdf \(p\) and a function \(g:f_{\theta}(x)\mapsto g(f_{\theta}(x))\) which indicates the probability of rejection. Here we assume that \(f_{\theta}(x)\) is a scalar. Let \(\text{RIR}(f_{\theta})\) be the distribution resulting from deploying a model with prediction function \(f_{\theta}\) under this procedure, and take \(p_{f_{\theta}}\) as its pdf. The sampling procedure of \(p_{f_{\theta}}\) is as follows:

* Take a sample \(x^{*}\) from \(p\).
* Toss a coin whose probability of getting a head is \(1-g(f_{\theta}(x^{*}))\). If it comes head, output \(x^{*}\), and if it comes tail, output another sample from \(p\).

Consider \(X\) to be a random variable with probability distribution \(p(x)\). \(p_{f_{\theta}}\) is defined mathematically as

\[p_{f_{\theta}}(x) =p(x)\Big{(}1-g(f_{\theta}(x))\Big{)}+p(x)\mathbb{E}_{X}[g(f_{ \theta}(X))]\] \[=p(x)(1-g(f_{\theta}(x))+C_{\theta}),\]

where \(C_{\theta}=\mathbb{E}_{X}[g(f_{\theta}(X))]=\int g(f_{\theta}(x^{\prime}))p(x^ {\prime})dx^{\prime}\).

The following theorem shows that the distribution resulting from the RIR procedure satisfies our conditions on the distribution map. This Theorem is proved in the Supplementary materials.

**Theorem 3**.: _If \(f_{\theta}(x)\in[0,1-\delta]\)\(\forall\theta\in\Theta\) for some fixed \(0<\delta<1\), then for \(g(f_{\theta}(x))=f_{\theta}(x)+\delta\), \(\text{RIR}(.)\) is \(\frac{1}{\delta}\)-sensitive w.r.t \(\chi^{2}\) divergence (A1) and satisfies the bounded norm ratio property (A2) for \(C=\frac{1}{\delta}\)._

**Remark 2**.: _Consider a strategic classification task where the distribution reacts to a model with the prediction function \(f_{\theta}\) in accordance with the RIR procedure. Suppose the predictions satisfy \(f_{\theta}(x)\in[0,1-\delta]\), the label \(y\) is in \(\{0,1-\delta\}\), and we use the Squared Error loss \(\ell(f_{\theta}(x),y)=\frac{1}{2}\big{(}f_{\theta}(x)-y)^{2}\) which is 1-strongly convex. According to Theorem 3, the distribution map is \(\frac{1}{\delta}\)-sensitive w.r.t \(\chi^{2}\) divergence and satisfies the bounded norm ratio property for \(C=\frac{1}{\delta}\). Also, \(M=\sup_{x,y,\theta}|\ell^{\prime}(f_{\theta}(x),y)|\) is equal to \(\sup_{x,y,\theta}|f_{\theta}(x)-y|=1-\delta\). Putting all these together, the convergence rate of RRM in Theorem 2 is equal to:_

\[\frac{\sqrt{C\epsilon}M}{\gamma}=\frac{1-\delta}{\delta}.\]

_Hence, whenever we have \(\delta>0.5\), RRM converges to a unique stable classifier._
We will use this remark in the experiments section.

In supervised learning, \(x\) corresponds to a set of features. So far in the RIR procedure, we resample the whole set of features, though we also can resample only a subset of them, and Theorem 3 still holds in this case if strategic and non-strategic features are independent as shown following the proof of this theorem in Supplementary materials. In our simulations in the next section, \(x\in\mathbb{R}^{d}\) is the set of features of individuals applying to get loans from a bank. These features are divided into two sets: _strategic_ and _non-strategic_. Strategic features are those that can be (easily) manipulated without affecting the true label, e.g. Number of open credit lines and loans. Non-strategic features, however, can be seen as causes of the label and include monthly income for example. In our experiments, we resample only strategic features as these are the ones that people can manipulate more easily.

## 4 Experiments

We complement our theoretical results with experiments on a credit scoring task and illustrate how they support our claims. We implemented our simulations based on Perdomo et al. (2020)'s code in the Whynot Python package (Miller et al., 2020), and changed it according to our settings so we can use auto-differentiation of PyTorch2. The strategic classification task of credit scoring is a two-player game between a bank that predicts the creditworthiness of loan applicants, and individuals who strategically manipulate their features to alter the classification outcome. We run the simulations using Kaggle's _Give Me Some Credit_ dataset (Kaggle, 2011), with features \(x\in\mathbb{R}^{11}\) corresponding to applicants' information along with their label \(y\in\{0,1\}\), where \(y=1\) indicates that the applicant defaulted and \(y=0\) otherwise.

Footnote 2: [https://github.com/mhrnz/Performance-Prediction-with-Neural-Networks](https://github.com/mhrnz/Performance-Prediction-with-Neural-Networks)

In our simulations, we assume that the data distribution induced by the classifier \(f_{\theta}\) shifts according to the RIR procedure where strategic features are resampled with the probability of rejection \(g(f_{\theta}(x))=f_{\theta}(x)+\delta\). Assuming that strategic and non-strategic features are independent, resampling strategic features can be implemented by simply choosing these features from another data point at random. For the classifier, we used a two-layer neural network with a hidden-layer size of 6. The choice of hidden layer size in our network was arbitrary; Figure 3 shows convergence for different hidden size values. In the network, we use a LeakyReLU activation after the first layer, and a scaled-sigmoid activation function after the second layer to bring the outcome \(f_{\theta}(x)\) to the interval \([0,1-\delta]\). This way we make sure that \(g(f_{\theta}(x))\in[\delta,1]\) is a valid probability and the assumption of Theorem 3 is satisfied. Since the outcome \(f_{\theta}(x)\) is in \([0,1-\delta]\), we change the label \(1\) to \(1-\delta\). So \(y=1-\delta\) corresponds to default, and the higher the value of \(f_{\theta}(x)\), the greater the chance of rejection. The objective is to minimize the expectation of the Squared Error loss function over instances, i.e. \(\mathbb{E}[\frac{1}{2}(f_{\theta}(x)-y)^{2}]\).

The definition of RRM requires solving an exact minimization problem at each optimization step; however, we solve this optimization problem approximately using several steps of gradient descent until the absolute difference of two consecutive risks is less than the tolerance of \(10^{-9}\). Also, note that running the same configuration twice might result in different plots because of the randomness that exists in the resampling phase.

Figure 1 shows the evolution of the log of performative risk (left) and accuracy (right) through iterations of RRM for \(\delta=0.9\). The blue lines show the changes in risk (accuracy) after optimizing on the distribution induced by the last model, and the green lines show the effect of the distribution shift on the risk (accuracy). We chose to plot the log of performative risk instead its own value only for illustration purposes. As discussed in Remark 2, for this \(\delta\), all the conditions of Theorem 2 including \(\frac{\sqrt{\mathcal{C}_{\mathcal{M}}}}{\sqrt{\mathcal{C}_{\mathcal{M}}}}<1\) are satisfied, and the

Figure 1: Evolution of log of performative risk (left) and accuracy (right) through iterations of RRM for \(\delta=0.9\). The blue lines show the changes in risk (accuracy) after optimizing on the distribution induced by the last model, and the green lines show the effect of the distribution shift on the risk (accuracy).
Theorem claims that in this case, RRM converges to a stable model; this is supported by our results in Figure 1.

Figure 2 shows the log of Performative Risk for different values of \(\delta=0.1,0.4,0.7,0.9\). The plot for \(\delta=0.9\) is generated through a different run than Figure 1. Based on Remark 2, for \(\delta=0.7\) and \(\delta=0.9\) we should see convergence behavior, though for \(\delta<0.5\), our theory neither gives a guarantee of convergence nor claims that repeated retraining will diverge, so we might or might not see convergence behavior for \(\delta=0.1\) or \(\delta=0.4\). What we see in Figure 2 is aligned with our expectations. It is important to note that for smaller \(\delta\), the value of \(\epsilon\) which indicates the strength of performative effects is larger, and for high performative effects, it is more difficult for the model to converge since the distribution is allowed to move more after the model's deployment.

On a high level, we interpret the stable classifier to be a model that relies less on non-strategic features for classification. Throughout the training, for a fixed data point \(z=(x,y)\) where \(x=(x_{s},x_{f})\) for \(x_{s}\) being the strategic features and \(x_{f}\) being the non-strategic ones, the model sees the same \(x_{f}\) but different values for \(x_{s}\) chosen randomly, all with the same label \(y\). So intuitively, the model would learn to rely less on strategic features and more on non-strategic ones for classification, and this makes it more robust to the strategic behavior of agents.

## 5 Discussion and Future Work

In this paper, we contribute the first set of convergence guarantees for finding performative stable models on problems where the risk is allowed to be non-convex with respect to parameters. This is an important development: our results pertain to modern machine learning models, like neural networks.

We achieve these stronger results by appealing to functional analytical tools, but also making slightly stronger assumptions on the performative feedback loop: rather than assuming that the distribution is \(\epsilon\)-sensitive to parameters as measured by Wasserstein distance, we instead assume that the distribution is \(\epsilon\)-sensitive to _predictions_ as measured by the \(\chi^{2}\) divergence.

On one hand, only assuming sensitivity to predictions instead of parameters is a step in the right direction. None of the big applications of performative prediction justify sensitivity to model parameters. As a matter of fact, many of the applications would motivate moving one step further in that direction: performative behavior in machine learning systems often manifests as a function of _decisions_ or _actions_ that rely on a prediction. Those decisions or actions are observed by a population that reacts by changing its behavior. We leave this important problem setting of studying sensitivity to decisions for future work.

On the other hand, \(\chi^{2}\) sensitivity is stronger and implies Wassertstein sensitivity. Furthermore, because we use a

Figure 2: Evolution of log of performative risk for different values of \(\delta=0.1,0.4,0.7,0.9\) through iterations of RRM.
variable norm that depends on parameters in our analysis, we make an extra assumption that the fixed norm is upper-bounded by a coefficient of this variable norm. While we provide in Section 3 a well-motivated, concrete example of a performative problem that satisfies both of these conditions, it is nonetheless an interesting open question to wonder how much our analytical assumptions can be loosened.

## 6 Societal Impact

We believe that the deployment of models that can have an impact on the behavior of people (i.e., are performative) should be considered with care, more especially for some critical applications such as elections or regulation of content on social media platforms. Our work proposes a new analysis of an existing algorithm that aims at learning performatively stable classifiers. Since the nature of our work is mainly theoretical and does not introduce new algorithms, it does not have a direct societal impact beyond the one described in the original paper on performative prediction. However, since our work supports the use of much more powerful models (e.g., NNs) in performative problems, and this increased power comes with increased responsibility, we should be mindful of the potential for undue influence on society while using this framework.

## Acknowledgements

We thank Quentin Bertrand, Michael Przystupa, and Reza Bayat for their helpful feedback on the manuscript. We would also like to thank Amjad Almahairi for our insightful discussions. Ioannis Mitliagkas acknowledges support by an NSERC Discovery grant (RGPIN-2019-06512), a Samsung grant and a Canada CIFAR AI chair.
