1 Introduction↩︎

Performative prediction, as introduced by [1], provides a framework for studying prediction and risk minimization when the data distribution itself changes in response to the deployment of a model. Such phenomena, usually referred to as "performativity," are prevalent in various social prediction contexts, including education, recommendation systems, and criminal prediction, among others [1]–[5]. For instance, consider a college admission process that places significant importance on standardized test scores. This process can incentivize students to invest more effort in test preparation, ultimately leading to a pool of applicants with much higher test scores than initially expected. This phenomenon is also prevalent in real-world applications, particularly in large-scale online recommendation systems, where the high frequency of updates to the recommendation algorithm can reshape users’ future behavior. For example, video platforms such as TikTok, Netflix, and YouTube provide personalized recommendations that can influence users’ future preferences and lead to shifts in the user-advertiser interaction patterns, thereby creating a dynamic and evolving data distribution.

More formally, consider the standard empirical risk minimization (ERM) problem defined by a loss function \(\ell\), a model parameter space \(\Theta \subset \mathbb{R}^{d_\Theta}\) where \(d_\Theta\in\mathbb{Z}_{>0}\), an instance space \(Z = X \times Y\), and a fixed data distribution \(\mathcal{D}\) over \(Z\). The task is to find a model that minimizes the empirical risk defined as: \(\mathsf{ER}(\theta, \mathcal{D}):= \mathbb{E}_{z \sim \mathcal{D}} [\ell(z;\theta)].\) Performative prediction extends this learning task by positing that the data distribution \(\mathcal{D}\) is not fixed but is instead a function of the model parameter \(\theta \in \Theta\). Here, we refer to \(\mathcal{D}(\cdot)\) as a distribution map, and \(\mathcal{D}(\theta)\) as the data distribution induced by the model \(\theta\). The objective is then to minimize the performative risk, defined as \[\begin{align} \mathsf{PR}(\theta, \mathcal{D}(\theta)) := \mathbb{E}_{z \sim \mathcal{D}(\theta)} [\ell(z;\theta)]~. \end{align}\] Intuitively, the performative prediction risk evaluates the performance of the model \(\theta\) on the resulting distribution \(\mathcal{D}(\theta)\) via the loss function \(\ell\). When it is clear from the context, we also use \(\mathsf{PR}(\theta)\) to shorthand the performative risk.

Optimizing the performative risk is generally challenging. In standard ERM, a convex loss function \(\ell\) implies a convex empirical risk. However, as [1] observed, the performative risk \(\mathsf{PR}(\cdot)\) may be non-convex even when the loss \(\ell\) itself is convex. For this reason, earlier works [1], [6]–[8] then focus on computing a performative stable solution instead, which is easier to achieve using standard optimization tools like repeated risk minimization. A performative stable model is loss-minimizing on the data distribution it induces, though other models may incur smaller losses on their respective induced distributions. However, as recent works [9], [10] point out, such stable solutions may be highly suboptimal and, worse yet, may not exist in certain settings.

One major challenge in performative risk minimization is the unknown distribution map between the model parameter \(\theta\) and the distribution \(\mathcal{D}(\theta)\) without making any structural assumption. For example, one can hardly anticipate the click-through rate of an ad without putting out the ad first. In the language of performative prediction, only by deploying a model \(\theta\) can the learner observe data samples that are i.i.d realized from the induced data distribution \(\mathcal{D}(\theta)\). Due to this inherent uncertainty about \(\mathcal{D}(\theta)\), it is impossible to compute the gradient of \(\mathsf{PR}(\theta)\) w.r.t \(\theta\), not to mention finding a model with the lowest performative risk offline. Instead, the learner must interact with the environment and deploy models \(\theta\) to explore the induced distributions \(\mathcal{D}(\theta)\), which involves deploying “imperfect” models on decision subjects.

In this paper, we propose to measure the loss incurred by deploying a sequence of models \(\theta_1, \ldots, \theta_{T_{\textsf{total}}}\) by evaluating the following regret measured with respect to the total number of samples deployed during the process: \[\begin{align} \label{eqn:regret-def} \mathcal{R}_N(\mathcal{A}, \mathsf{PR}) = \sum_{\tau=1}^{T_{\textsf{total}}} \sum_{i=1}^{n_{\tau}} \ell(z_{\tau}^{(i)}; \theta_{\tau})- N \cdot \mathsf{PR}(\theta_{\texttt{OPT}}) \end{align}\tag{1}\] where \(N:=\sum_{\tau=1}^{T_{\textsf{total}}} n_{\tau}\) denotes the total number of observed data samples throughout the process, \(\mathcal{A}\) corresponds to the particular algorithm, and \(\mathsf{PR}\) represents the objective function. This regret measures the suboptimality of the deployed sequence of models relative to a performative optimum \(\theta_{\texttt{OPT}} \in \operatorname{argmin}_\theta \mathrm{PR}(\theta)\) in terms of how much loss they incur on the population with \(N\) decision subjects.

In contrast to earlier studies that primarily assess the final model’s performance based on optimality rather than the cumulative loss incurred throughout the process, we argue that this constitutes a more practical evaluation metric in predictive scenarios involving multiple rounds of human feedback. In particular, since the process of finding the optimal performative model involves deploying sub-optimal models on human agents in the process, it is more appropriate to define regret on the total number of agents that are subjected to the “imperfect’’ algorithmic system rather than only caring about whether the final model is optimal. We believe this provides a unique evaluation metric suitable for performative prediction.

Later in 4.3, we compare our proposed regret definition with the standard regret measured in \(T_{\textsf{total}}\) in more detail and show that our algorithm is, in fact, also sublinear in the total deployment steps \(T_{\textsf{total}}\). This, combined with the fact that sublinear regret implies model convergence (1), also means that our algorithm can guarantee to output a model arbitrarily close to the performative optimal model \(\theta_{\texttt{OPT}}\).

1.1 Our Contributions↩︎

Our main contributions are a two-level zeroth order optimization algorithm that achieves a sublinear regret bound measured using the total number of samples and a novel reparametrization framework attempting to tackle a particular non-convex performative prediction problem.

Reparametrization Framework.

Departing from previous work, we allow \(\mathsf{PR}(\theta)\) to be non-convex in the model parameter \(\theta\), but suppose it is convex in the data distribution parameter \(\phi \equiv \varphi(\theta)\). Informally, under mild conditions, we show that non-convex \(\mathsf{PR}(\theta)\) can be reparameterized as a new (convex) function \(\mathsf{PR}^\dagger(\phi)\) over the induced data distribution parameter \(\phi\). We discuss detailed parametrization procedure in 3.

Zeroth-Order Optimization Algorithm with Performativity.

Given the parametrization framework proposed above, we propose a two-level zeroth-order optimization procedure, which, to our knowledge, is novel in performative prediction. We believe our method enjoys the following benefits:

Our main results can be summarized as follows:

The \(N_\mathsf{KL}\) term in our regret depends on the sample efficiency of the estimator for KL divergence. The detailed discussion is provided in 4.2.

1.2 Related Work↩︎

Our work most closely relates to performative prediction and zeroth-order optimization. Due to page limit, we include additional related work in 12, including detailed comparisons of our work to three closely related jobs [9], [11], [12], and more recent developments of performative prediction.

Performative Prediction.

Performative Prediction, first explored in [1], has recently received many follow-up works, including but not limited to [6]–[11], [13], [14] and [15]. These works mostly focus on the performative stability and the performative optimality, including developing an algorithmic procedure that converges to performatively stable or optimal points. Similar to this line of research [9]–[11], [13], our work also focuses on performative optimality.

Zeroth-Order Optimization.

Our algorithms and techniques are based on the line of work on zeroth-order optimization (also known as bandit optimization) initiated by [16], which studies how to optimize an unknown convex function \(f\) using only function value query access to \(f\). [17] and [18] later extend the technique that allows multiple points query and show that two points suffice to guarantee that the regret bounds that closely resemble the regret bounds for the full information case. The reparameterization approach proposed in our paper mirrors the intuition behind the algorithms proposed for learning from revealed feedback or preferences (see, e.g., [4], [19], [20]), which consider a Stackelberg game involving a utility-maximizing learner and strategic agent. Our work, focusing on performative prediction with an environment response exogenously characterized by a distribution map \(\mathcal{D}(\cdot)\), differs from theirs in problem consideration.

1.3 Key Notations↩︎

Let \(d_\Theta\in \mathbb{Z}_{>0}\) denote the dimension of the model parameter \(\theta\), and let \(D_\Theta:= \sup\{\|\theta-\theta'\|, \forall \theta,\theta' \in \Theta\}\) denote the diameter of the model parameter space \(\Theta\). The data distribution \(\mathcal{D}(\theta)\) has a parametric continuously differentiable density \(p(z; \varphi(\theta))\) where \(\varphi(\theta)\) denote the distribution parameter for \(\mathcal{D}(\theta)\). We use \(\varphi(\cdot)\) to denote the distribution parameter mapping while \(\phi\) to denote a given distribution parameter. Let \(d_\Phi\in \mathbb{Z}_{>0}\) denote the dimension of the model parameter \(\phi\), and let \(D_\Phi:= \sup\{\|\phi-\phi'\| ~|, \forall \phi,\phi' \in \Phi\}\) denote the diameter of the model parameter space \(\Phi\). When it is clear from the content, we use \(\varphi(\theta)\) to represent \(\mathcal{D}(\theta)\) the distribution \(\theta\) induces. Let \(\vartheta^*(\phi)\) denote the optimal model parameter that induces a specific target distribution parameter \(\phi\) – in case of having multiple model parameters that potentially induce the same distribution parameter \(\phi\), \(\vartheta^*(\phi)\) is the one that achieves the minimum performative prediction risk.

1.4 Structure of the Paper↩︎

The rest of the paper is organized as follows: In 2, we introduce the problem formulation and provide a warm-up setting when \(\mathsf{PR}(\theta)\) is convex over the model parameter \(\theta\). Using this simple setting, we introduce the zeroth-order optimization technique we use, which will serve as the building block to solve for a more complicated setting (i.e., when \(\mathsf{PR}(\theta)\) is not convex over \(\theta\)). We also present a fundamental fact in convex optimization that sublinear regret implies model convergence (1), which unifies the goal of regret minimization and model optimality in our setting. In 3, we provide an overview of our proposed solution. In 4.1, we describe the outer algorithm, and 4.2 describes the inner algorithm called \(\operatorname{\mathsf{LearnModel}}\), which is used to solve a subroutine problem using black-box oracle. 4.3 contains the overall regret analysis. Lastly, in 5, we discuss the limitations and potential future work. All omitted proofs can be found in the Appendix.

2 Preliminaries↩︎

We begin by formally defining our problem.

2.1 Problem Formulation↩︎

The objective of performative prediction is to minimize the performative risk defined as \(\mathsf{PR}(\theta):= \mathbb{E}_{z \sim \mathcal{D}(\theta)} [\ell(z;\theta)]~.\) A model \(\theta_{\texttt{OPT}} \in \Theta\) is said to be performatively optimal if \(\mathsf{PR}(\theta_{\texttt{OPT}}) = \min_{\theta \in \Theta} \mathsf{PR}(\theta)\). To find the performatively optimal model, one usually needs to have the full knowledge of the underlying distribution map \(\mathcal{D}: \Theta \rightarrow \Phi\). In this work, we consider a more practical scenario where the distribution map \(\mathcal{D}\) is not known in advance, and to learn the performatively optimal model, the learner has to adaptively deploy models to gradually learn the underlying distribution map.

Formally, we consider the following repeated interaction between the learner and the environment consisting of decision subjects where we can only query through samples. The interaction proceeds for \(T_{\textsf{total}}\) steps, at each time step \(\tau = 1, \ldots, T_{\textsf{total}}\): (1) the learner deploys a model \(\theta_{\tau}\in\Theta\); (2) the learner observes \(n_\tau\) data samples \(\{z_{\tau}^{(i)}\}_{i\in[n_\tau]}\) where each \(z_{\tau}^{(i)}\overset{\text{iid}}{\sim} \mathcal{D}(\theta_{\tau})\); (3) the learner incurs empirical loss \(\ell(z_{\tau}^{(i)}; \theta_{\tau})\) for each sample.

The goal of the learner is to design an online model deployment policy \(\mathcal{A}\) such that it minimizes her cumulative empirical risk over all observed data samples: \[\begin{align} \mathcal{R}_N(\mathcal{A}, \mathsf{PR}) = \sum_{\tau=1}^{T_{\textsf{total}}} \sum_{i=1}^{n_{\tau}} \ell(z_{\tau}^{(i)}; \theta_{\tau})- N \cdot \mathsf{PR}(\theta_{\texttt{OPT}}) \end{align}\] where \(N:=\sum_{\tau=1}^{T_{\textsf{total}}} n_{\tau}\) denotes the total number of observed data samples throughout the process. The reason we introduce \(T_{\textsf{total}}\) instead of \(N\) directly is that each step (\(\tau\)) of our algorithm performs different tasks, where we would impose different requirements of samples to be collected. This shall become clear later when we present our algorithm in the following sections.

2.2 Warmup Setting: When \(\mathsf{PR}(\theta)\) is Convex in \(\theta\)↩︎

In this section, we analyze a simple scenario when we assume that the performative risk \(\mathsf{PR}(\theta)\) is convex over the model parameter \(\theta\). The technique we use to solve this simple case will be the building block to solve the later more challenging problem where \(\mathsf{PR}(\theta)\) is not convex over the model parameter \(\theta\).

Recall that when the learner deploys a model \(\theta\), she observes a set of data samples which are i.i.d drawn from the underlying data distribution \(\mathcal{D}(\theta)\). This enables us to compute an unbiased estimate \(\widetilde{\mathsf{PR}}(\theta)\) for the performative risk \(\mathsf{PR}(\theta)\) of the deployed model \(\theta\): \[\begin{align} \widetilde{\mathsf{PR}}(\theta) = \frac{1}{n_\tau}\sum_{i=1}^{n_\tau} \ell(z_\tau^{(i)}; \theta), ~~ \text{and}~~ \mathbb{E}[\widetilde{\mathsf{PR}}(\theta)] = \mathsf{PR}(\theta), \forall \theta \in \Theta \end{align}\] where the expectation is over the randomness of the observed samples. Since \(\mathsf{PR}(\theta)\) is convex over the model parameter \(\theta\), one can use an off-the-shelf zeroth-order convex optimization technique [17] to solve this problem and get the following regret guarantee:

We defer the proof and the details of 4 to 7. In particular, 4 deploys two models at each time step, in doing so, one can show that the regret bounds closely resemble bounds for the full information case where the learner knows the distribution map \(\mathcal{D}(\cdot)\). The proof of the above result builds on the main result of [17], and also incorporates an improved analysis of the gradient estimate due to [18].

2.3 Useful Fact: Sublinear Regret Implies Convergence in Model Optimality↩︎

A folklore fact in online and zeroth-order optimization is that if a function \(f\) is convex and we wish to converge to an approximately optimal point, it suffices to show a query algorithm that achieves \(o(n)\) regret after \(n\) queries. In particular, we have the following proposition:

This proposition establishes a strong link between achieving sublinear regret and the convergence toward an optimal model. It implies that if our proposed algorithm attains a sublinear regret as defined in Equation 1 , this automatically suggests that we can obtain an almost optimal model, which is exceptionally close to the truly optimal model, denoted as \(\theta_{\texttt{OPT}}\). This closeness is achieved simply by averaging the models \(\theta_1, \ldots, \theta_{T_{\textsf{total}}}\) throughout the deployment process. This helps us unify the goal of regret minimization and finding the optimal model.

3 Optimizing \(\mathsf{PR}\) via Reparameterization: An Overview of Our Solution↩︎

When \(\mathsf{PR}(\theta)\) is not convex over the model parameter \(\theta\), the zeroth-order convex optimization technique used in 2.2 is not directly applicable. Instead, we leverage the structure of \(\mathsf{PR}(\theta)\) and reparameterize it as a function of the induced data distribution \(\mathcal{D}(\theta)\). In particular, we consider the setting where the data distribution \(\mathcal{D}(\theta)\) has a parametric continuously differentiable density \(p(z; \varphi(\theta))\), and the functional form \(p(z; \phi)\) is known to the learner but the distribution parameter \(\phi\) remains unknown. Under mild conditions, we show that the performative risk \(\mathsf{PR}(\theta)\) can be reformulated as a function of the induced distribution distribution parameter \(\phi \equiv \varphi(\theta)\), namely, \[\begin{align} \mathsf{PR}(\theta) = \mathsf{PR}^\dagger(\varphi(\theta)) \equiv\mathsf{PR}(\vartheta^*(\phi))~, \end{align}\] and \(\mathsf{PR}^\dagger(\phi)\) is convex over the distribution parameter \(\phi\) (See more details in 4.1).

Here we provide two real-life settings to justify our model:

With this reparameterization, one can operate on the space of distribution parameters and hopefully apply the zeroth-order convex optimization technique. However, one notable challenge is in zeroth-order convex optimization, the learner is usually assumed to have direct query access to the unknown convex function \(f\). Namely, when querying point \(x\), the learner is able to immediately obtain the information about the (noisy) value \(f(x)\). In our setting, such direct access is, unfortunately, not available since the mapping \(\varphi(\cdot)\) is not known to the learner. Indeed, the learner can only deploy a model \(\theta\) to observe the empirical performative risk \(\widetilde{\mathsf{PR}}(\theta)\) which is evaluated over the observed data samples drawn from the induced data distribution \(\mathcal{D}(\theta)\). Hence, to evaluate the value \(\mathsf{PR}^\dagger(\phi)\) on a target data distribution with the parameter \(\phi\), we use another algorithm called \(\operatorname{\mathsf{LearnModel}}\) as a subroutine to find a model \(\bar{\theta}\) such that \(\varphi(\bar{\theta}) \approx \phi\) (See 4.2).

Summary of our proposed procedure.

Intuitively, the outer loop optimizes the objective function \(\mathsf{PR}\) in the distribution parameter space \(\phi\in \Phi\) iteratively and tries to find the optimal data parameter \(\phi *\), while the inner loop (\(\operatorname{\mathsf{LearnModel}}\)) tries to find a model parameter to induce the particular data parameter that the outer loop is currently iterating on.³ A graph illustration of our algorithm procedure in given in 1.

3.1 Examples of \(\mathsf{PR}\) Being Convex in \(\phi\) not in \(\theta\)↩︎

We first provide three examples in which our condition (\(\mathsf{PR}\) loss is convex in the induced distribution parameter \(\varphi_\theta:= \phi(\theta)\), but non-convex in the model parameter \(\theta\)) holds. See more examples and derivation details in 8.

Notice that the example provided can be generalized to any distribution map \(\phi(\theta)\) that satisfies \(\varphi(\theta) = \theta^\alpha\) for any \(\alpha> 1\), and any \(\ell_\beta\) loss for even \(\beta\) value. In addition, Example 1 can also be any generalized monotone polynomial function \(\varphi(\theta)\).

4 Our Algorithm and its Performance Guarantee↩︎

In this section, we provide the details of our proposed algorithm, and also the associated performance analysis.

4.1 The Outer Algorithm: A Reparameterization Approach↩︎

As we mentioned, in this work, we study the scenario where \(\mathsf{PR}(\theta)\) is not convex over the model parameter. The high-level idea is that we can reparameterize the performative risk \(\mathsf{PR}(\theta)\) as a function \(\mathsf{PR}^\dagger(\phi)\) over the data distribution parameter \(\phi\). In particular, we first reformulate the learner’s loss function so that it can be expressed as a function only in the induced data distribution. For each data distribution \(\phi \in \Phi\), assume the set of learner’s actions (deployed model parameters) that induce \(\phi\) is \(\Theta^*(\phi) = \{\theta \in \Theta | \varphi(\theta) = \phi \}\) Among all of the learner’s actions that induce \(\phi\), the optimal one that achieves the minimal \(\mathsf{PR}\) loss across the whole population is: \[\begin{align} \vartheta^*(\phi) = \mathop{\mathrm{\arg\!\min}}_{\theta\in \Theta^*(\phi )} \mathsf{PR}(\theta ) \end{align}\] where ties are broken arbitrarily. Now we can rewrite learner’s objective function as a function of \(\phi\) \[\begin{align} \label{eq:reformulate-objective-function} \mathsf{PR}^\dagger(\phi) = \mathsf{PR}(\vartheta^*(\phi )) \end{align}\tag{2}\]

To make the problem tractable, we consider following generic class of \(\mathsf{PR}^\dagger(\cdot)\) that is convex and Lipchitz continuous.

With reparameterizing \(\mathsf{PR}(\theta)\) as a function \(\mathsf{PR}^\dagger(\phi)\) over the induced data distribution parameter \(\phi\), we now wish to minimize a bounded, \(L^\dagger\)-Lipschitz function \(\mathsf{PR}^\dagger(\cdot): \Phi \to \mathbb{R}\), where \(\Phi \subset \mathbb{R}^{d_\Phi}\) has bounded diameter \(D_\Phi\), by operating on the distribution parameter space \(\Phi\).

Instead of having immediate query access in zeroth-order convex optimization algorithm, in our setting, we cannot directly evaluate the (noisy) value \(\mathsf{PR}^\dagger(\phi)\) for a particular data distribution parameter, but may query the following oracles:

2 achieves this task. Specifically, it returns both \(\bar{\theta} \in \Theta\) and \(\bar{\phi} \in \Phi\) such that with probability at least \(1-p\), \(|\mathsf{PR}(\bar{\theta}) - \mathsf{PR}(\theta_\texttt{OPT})| \leq \epsilon\) and \(|\mathsf{PR}^\dagger(\bar{\phi}) - \mathsf{PR}^\dagger(\varphi(\theta_\texttt{OPT}))| \leq \epsilon\).

For analysis purpose, we also define regret in \(T\), the total number of steps \(\operatorname{\mathsf{Minimize}\mathsf{PR}}\) has to go through in order to get an \(\epsilon\)-suboptimal model parameter w.r.t the \(\mathsf{PR}\) objective function: \[\begin{align} &\mathcal{R}_T(\operatorname{\mathsf{Minimize}\mathsf{PR}}, \mathsf{PR})\\ =& \sum_{t=1}^T \left[ \operatorname{\mathsf{Estimate}\mathsf{PR}}(\hat{\theta}_t^+) + \operatorname{\mathsf{Estimate}\mathsf{PR}}(\hat{\theta}_t^-) - 2 \mathsf{PR}(\theta_\texttt{OPT}) \right] \end{align}\]

We demonstrate the following regret bound for this algorithm:

The above [theorem:regret-bound-for-indirectly-convex-functions] requires that the output of \(\operatorname{\mathsf{LearnModel}}\) is \(\epsilon_\mathsf{LM}\)-close to the target distribution parameter \(\phi\) with probability at least \(1 - p_\mathsf{LM}\). Later in 4.2, we show how we achieve this by developing an zeroth-order convex optimization algorithm with the objective of minimizing the \(\mathsf{KL}\) divergence of two distributions.

4.2 Inner Algorithm: Inducing a Target Distribution Using \(\operatorname{\mathsf{LearnModel}}\)↩︎

In this section, we show how to solve the sub-problem \(\operatorname{\mathsf{LearnModel}}\) mentioned in 2: given a target distribution with the parameter \(\phi\in \Phi\), find a model \(\theta\in \Theta\) whose corresponding distribution parameter \(\varphi(\theta)\) is close to \(\phi\).

Objective function for \(\operatorname{\mathsf{LearnModel}}\).

To this end, we consider minimizing the \(\mathsf{KL}\) divergence between \(\phi\) and \(\varphi(\theta)\): ⁶ \[\begin{align} \label{eqn:kl-divergence} \mathsf{KL}(\phi|| \varphi(\theta)) := \int_z p(z; \phi) \log \frac{p(z; \phi)}{p(z;\varphi(\theta))} dz \end{align}\tag{3}\] where \(p(z;\phi)\) denotes the pdf for the target distribution \(\phi\), and \(p(z;\varphi(\theta))\) denotes the pdf for the distribution induced by deploying \(\theta\).

In general, \({\mathsf{KL}}(\phi|| \varphi(\theta))\) measures how much a distribution with the parameter \(\varphi(\theta)\) is away from the target distribution with the parameter \(\phi\): if the two distributions \(\phi_1,\phi_2 \in \Phi\) satisfy \(\phi_1 = \phi_2\), then \({\mathsf{KL}} (\phi_1||\phi_2) = 0\), otherwise \({\mathsf{KL}} (\phi_1||\phi_2) >0\). Intuitively, the lower the value \({\mathsf{KL}} (\phi_1||\phi_2)\) is, the better we have matched the target distribution with our approximate distribution induced by the chosen model. However, \(\mathsf{KL}(\phi|| \cdot )\) is generally not convex nor Lipschitz. Hence, to make the problem tractable, we will make several assumptions. We view these assumptions as comparatively mild, and provide examples shortly after stating the assumptions we need.

Here, we provide examples to demonstrate that the above assumptions are comparatively mild. The following is an example showing the convexity of \(\mathsf{KL}(\phi|| \varphi(\cdot))\).

In the above Assumption 2b, we assume a family of distribution called the \((\ell_2, K)\)-Lipschitz continuous. This Lipschitz continuity over the parametrization of probability distributions allows us to have the following Lipschitz condition of the function \(\mathsf{KL}(\phi||\varphi(\cdot))\) over the model parameter \(\theta\):

The above Assumption 2c is about the continuity on the distribution parameter \(\phi\in \Phi\). Intuitively, this assumption ensures that if the parameters of two distribution are close, then their total variation distance is close as well. With this assumption, we can show that the distance between two distribution parameters \(\|\phi_1 - \phi_2\|\) can be bounded by the KL divergence between the corresponding data distributions.

Intuitively, the above result ensures that given a target distribution parameter \(\phi\), as long as a model \(\theta\) whose corresponding data distribution is close (i.e., \(\mathsf{KL}(\phi || \varphi(\theta))\) is small) to the distribution with the parameter \(\phi\), then \(\varphi(\theta)\) is close to \(\phi\). We will use [lemma:phi-bound-by-KL] in the proof of our main theorem in 4.3.

Algorithm for \(\operatorname{\mathsf{LearnModel}}\).

When \(\mathsf{KL}(\phi|| \varphi(\cdot))\) is convex and Lipschitz over the model \(\theta\), its minimizer can be computed using algorithms similar to 2. In our problem, given a target data distribution with the parameter \(\phi\), we can use the observed data samples to approximately compute the \(\mathsf{KL}(\phi|| \varphi(\theta))\) when deploying a model \(\theta\). Indeed, we assume an existence of an oracle \(\operatorname{\mathsf{EstimateKL}}(\phi, (z_t^{(i)})_{i\in[n_t]})\) which takes the observed samples \((z_t^{(i)})_{i\in[n_t]}\) realized from the induced data distribution \(\mathcal{D}(\theta)\) and the target data distribution parameter \(\phi\) as input to approximate the value \(\mathsf{KL}(\phi|| \varphi(\theta))\). We remark that such oracle has been widely used in the literature on KL divergence estimation [22].

With the oracle \(\operatorname{\mathsf{EstimateKL}}\) to approximately compute the KL divergence, we are now ready to present our inner algorithm \(\operatorname{\mathsf{LearnModel}}\) (see 3).

Similar to before, for analysis purpose, we also define regret of \(\operatorname{\mathsf{LearnModel}}\) in \(S\), the total number of rounds \(\operatorname{\mathsf{LearnModel}}\) has to go through in order to output a \(\epsilon_\mathsf{LM}\)-suboptimal model parameter w.r.t the \(\mathsf{KL}\) objective function: \[\begin{align} & \mathcal{R}_S(\operatorname{\mathsf{LearnModel}}, \mathsf{KL}) \\ = ~ & \sum_{s=1}^S \left[ \widetilde{\mathsf{KL}}(\phi||\varphi(\theta_{s}^+)) + \widetilde{\mathsf{KL}}(\phi||\varphi(\theta_{s}^-)) - 2\mathsf{KL}(\phi||\vartheta^*(\phi)) \right] \end{align}\] where \(\vartheta^*(\phi)\) is the model that can induce the target distribution \(\phi\). Using the similar arguments in [theorem:regret-bound-for-indirectly-convex-functions], we first show the following regret guarantee for \(\operatorname{\mathsf{LearnModel}}\):

[theorem:regret-bound-for-learnmodel] characterizes the regret as a function of the total number of deployments of the procedure in \(\operatorname{\mathsf{LearnModel}}\). Together with regret characterization of the outer algorithm in [theorem:regret-bound-for-indirectly-convex-functions], we can get the final regret bound.

4.3 Putting All Pieces Together↩︎

As shown in the previous section, both the outer algorithm (\(\operatorname{\mathsf{Minimize}\mathsf{PR}}\) – in 4.1) and inner algorithm (\(\operatorname{\mathsf{LearnModel}}\) – in 4.2) achieve a sublinear regret w.r.t the total number of steps (\(T\) and \(S\)) when outputting an \(\epsilon\)-optimal solutions. In this section, we combine the results in 4.1 and 4.2 to conclude the analysis for \(\operatorname{\mathsf{Minimize}\mathsf{PR}}\) (2) for convex \(\mathsf{PR}^\dagger(\phi)\). The main result of this section is summarized as follows:

[theorem:total-regret] show that our procedure is sublinear in the \(N\), the total number of samples we deploy during the process. Notice that this also implies that our method is sublinear w.r.t. the total number of deployments \(T_{\textsf{total}}= S \times T\). To see this, recall that the total number of samples \(N\) required throughout the process is \(N =2(2N_{{kl}} \times S + 1) T\); if we measure the regret w.r.t. the total number of deployments, \(N_{{kl}}\) will be constant, and thus the regret will still be sublinear w.r.t. \(T_{\textsf{total}}\). In addition, recall from 1, the lowest regret optimal classifier implies the optimal classifier up to some addictive error, which means that by having a sublinear regret in \(N\) (and \(T_{\textsf{total}}\)), we also get a model that is arbitrarily close to the performative optimal model.

4.3.0.1 Empirical Evaluation Using Toy Example

We provide empirical results using a toy example to demonstrate the efficiency of our method. In particular, we compare our proposed method (which minimizes \(\text{PR}\) as a function of the distribution parameter \(\phi\) after reparametrization) with the baseline method (which directly minimizes \(\mathsf{PR}\) as a model parameter \(\theta\)). We observe that under different settings, both methods converge. However, our proposed method (shown in orange) is more efficient: it demonstrates a much faster convergence rate on average over multiple runs, indicating that our reparametrization method is effective when dealing with distributions that are non-convex in \(\theta\) but convex in \(\phi\) (as per Assumption 1). The plot can be found in 13. The details for reproducing our experimental results can be found at https://github.com/UCSC-REAL/PP-bandit-feedback.

5 Practical Consideration and Future Works↩︎

Since our method uses a double-loop zeroth order optimization method, the convergence is likely to be slow in practice. Thus, it requires extra consideration regarding the convergence rate, and efficiency can vary based on particular settings. In particular, the success of our method depends on the fast deployment of the frequently updated models. One potential way to speed up the deployment process may be performing parallelization, which accelerates the optimization process and reduces the time required to find a suitable solution (see, e.g., [23] for a detailed reference). In our algorithm, parallelization can be applied to several places, e.g., the two-point estimations can be computed in parallel and potentially speed up the process.

Acknowledgements↩︎

Y. Chen and Y. Liu are partially supported by the National Science Foundation (NSF) under grants IIS-2143895 and IIS-2040800.

Impact Statement↩︎

Since the process of finding the optimal performative model involves deploying sub-optimal models on human agents, sample efficiency is important. Thus sample complexity needs to be taken into consideration when choosing the particular KL divergence oracle used in \(\operatorname{\mathsf{LearnModel}}\). Additionally, the concept of performativity highlights a significant broader impact of our work: the importance of recognizing scenarios where predictions can modify the very environment they’re meant to predict. Take, for example, an online advertising platform utilizing machine learning models to tailor ads for users. These models, by analyzing user behaviors and traits to serve personalized ads, might inadvertently influence both user and advertiser actions, thereby establishing a feedback loop. This dynamic underscores the need for a mindful approach in deploying predictive models, especially in settings sensitive to the outcomes of such predictions.

6 Appendix Arrangement↩︎

We arrange the appendix as follows:

7 Omitted Algorithm and Proof for 2↩︎

7.1 Omitted Proof for 1↩︎

7.2 Omitted algorithm and proof for 4↩︎

4 is a straightforward generalization of the algorithm introduced by [17], while we generalize their setting where the function can be evaluated exactly to the setting where noisy evaluation is allowed.

To prove [lemma:regret-bound-for-model-convex-performative-risk], we first provide a series of lemmas and claims that will be useful later.

7.2.0.1 Overall Regret Analysis for [lemma:regret-bound-for-model-convex-performative-risk]

We can now complete our regret bound for [lemma:regret-bound-for-model-convex-performative-risk]. Recall the lemma statement:

8 Missing Proofs and Additional Examples for 3↩︎

8.0.0.1 Derivations for 3

Since \(\phi\) is strictly increasing in \([0, 1]\), the inverse mapping \(\phi^{-1}\) is well-defined, and we can reformulate the performative risk \(\mathsf{PR}(\theta)\) as a function of \(\varphi_\theta\), denoted \(\mathsf{PR}^\dagger(\varphi_\theta)\), as follows: \[\begin{align} \mathsf{PR}(\theta;x) &= \mathbb{E}_{y \sim \mathsf{Bern}(\varphi_\theta)}[\ell(\theta;x,y)] \\ &= \varphi_\theta \ell(\theta;x,1) + (1- \varphi_\theta) \ell(\theta;x,0) \\ &= \varphi_\theta \ell\left(\phi^{-1}(\varphi_\theta);x,1\right) + (1- \varphi_\theta) \ell\left(\phi^{-1}(\varphi_\theta);x,0\right) \\ &=: \mathsf{PR}^\dagger(\varphi_\theta;x) \end{align}\]

Plugging in \(\ell\), we have \[\begin{align} \mathsf{PR}^\dagger(\varphi_\theta;x) &= -\varphi_\theta \cdot \left(\phi^{-1}(\varphi_\theta)x - 1\right)^2 - (1- \varphi_\theta) \cdot \left(\phi^{-1}(\varphi_\theta)x\right)^2 \\ &= -\varphi_\theta \cdot \left(\sqrt{\varphi_\theta}x - 1\right)^2 - (1- \varphi_\theta)\varphi_\theta x^2 (\varphi_\theta) = \sqrt{\varphi_\theta}} \end{align}\] Note that for all \(x \in [0,1]\), \(\mathsf{PR}^\dagger(\varphi_\theta;x) = \mathsf{PR}(\theta;x)\) is convex in \(\varphi_\theta\) over \([0,1]\). In contrast, \[\begin{align} \mathsf{PR}(\theta;x) &= \theta^2 \cdot \ell(\theta;x,1) + (1-\theta^2) \cdot \ell(\theta;x,0) \\ &= -\theta^2\cdot (\theta x - 1)^2 - (1 - \theta^2) \cdot (\theta x)^2 \end{align}\] which is non-convex in \(\theta\) over \([0,1]\) for all \(x \in [0,1]\).

Notice that 3 can be generalized to any distribution map \(\phi(\theta)\) that satisfies \(\phi(\theta) = \theta^\alpha\) for any \(\alpha> 1\), and any \(\ell_\beta\) loss for even \(\beta\) value. Below in 6, we provide the plot for for \(\phi(\theta) = \theta^4\) with \(\ell_4\) norm loss (\(L_4\) norm is defined as \(L_4(x, y)=\left(\sum_{i=1}^d\left|x_i-y_i\right|^4\right)^{\frac{1}{4}}\) where \(d\) is the dimension of \(x\) and \(y\)). The original \(\mathsf{PR}\) loss \(\mathsf{PR}(\theta)\) is in red, which is non-convex), and the reformulated PR loss \(\mathsf{PR}^\dagger (\theta)\) is in blue via reparameterization, which is convex).

In addition, 3 can also be a generalized monotone polynomial function \(\phi(\theta)\). For example, \(\phi(\theta) = c \theta^2 + d \theta\), for \(d\geq 0, d \geq -2c\).

8.0.0.2 Derivations for 4

\[\begin{align} \mathsf{PR}(\theta) &= \mathbb{E}_{x\sim \mathcal{D}(\theta)} \ell(x;\theta)\\ &= \mathbb{E}_{x\sim N(\varphi(\theta), \sigma^2)} (\theta x)^2\\ &= \theta^2 (\sigma^2 + \varphi(\theta)^2) \end{align}\] when \(\varphi(\theta) = \sqrt{\theta}\), \(\mathsf{PR}(\theta)\) is not convex in \(\theta\). To see this: \[\begin{align} \mathsf{PR}(\theta) = \theta^2(\sigma^2 + \theta) \end{align}\] On the other hand, since \(\phi = \varphi(\theta) = \sqrt{\theta}\), we have \[\begin{align} \mathsf{PR}(\phi) = \phi (\theta^2 + \phi) \end{align}\] which is convex in \(\phi\).

8.0.0.3 Derivations for 5

\[\begin{align} \mathsf{PR}(\theta) &= \mathbb{E}_{y\sim \mathcal{D}(\theta)} (\ell(\theta; x, y))\\ &= - \mathbb{E}_{\text{Uniform}[0, \varphi(\theta)]} (\theta x - y)^2\\ &= \theta^2 x^2 - \theta x \varphi(\theta) + \frac{1}{3} \varphi(\theta)^2 \end{align}\] when \(\varphi(\theta) = \theta^2\), we have \[\begin{align} \mathsf{PR}(\theta) = \theta^2 x^2 - \theta^3 x + \frac{1}{3}\theta^4 \end{align}\] which is non-convex in \(\theta\). On the other hand, denote \(\phi = \varphi(\theta)\), we have \(\theta = \sqrt{\phi}\), plug it into \(\mathsf{PR}\), we have: \[\begin{align} \mathsf{PR}(\phi) = \phi x^2 - \phi \sqrt{\phi} + \frac{1}{3} \phi^2 \end{align}\] which is convex in \(\phi\).

9 Omitted Proof for 4.1↩︎

We present a series of lemmas and claims that are helpful for proving [theorem:regret-bound-for-indirectly-convex-functions].

9.0.0.1 Regret analysis for the outer algorithm in total number of step \(T\)

We can now complete our regret bound for \(\operatorname{\mathsf{Minimize}\mathsf{PR}}\) (2). We recall the theorem statement for [theorem:regret-bound-for-indirectly-convex-functions]:

10 Omitted Proof for 4.2↩︎

We first provide a proof for [lemma:lip-phi-in-KL]. Recall the lemma statement:

Next, we provide the proof for [lemma:phi-bound-by-KL]. Recall the lemma statement:

We then show the example provide by [example:convex-kl] is convex in \(\theta\). Recall the example:

Below we provide proof for it being convex in \(\theta\):

10.0.0.1 Regret Analysis and convergence guarantee of \(\operatorname{\mathsf{LearnModel}}\) in total number of steps \(S\)

We can now complete our regret bound for \(\operatorname{\mathsf{LearnModel}}\) (3). Recall the theorem statement:

11 Omitted Proof for 4.3↩︎

We start with leveraging [theorem:regret-bound-for-indirectly-convex-functions] to show the following convergence guarantee for \(\operatorname{\mathsf{Minimize}\mathsf{PR}}\) (2).

Similarly, we have the convergence guarantee for \(\operatorname{\mathsf{LearnModel}}\) as well:

Now are are ready to prove [theorem:total-regret]. Recall the theorem statement:

12 Additional Related Work↩︎

In this section, we provide additional related work in performative prediction and a detailed comparison of our work and some closely related work.

Performative prediction is a new type of supervised learning problem in which the underlying data distribution shifts in response to the deployed model [1], [7], [8], [10], [12], [24]–[26]. It is also called the decision-dependent risk minimization problem [12], [27], [28]. In particular, [1] first propose the notion of the performative risk defined as \(\mathsf{PR}(\theta):= \mathbb{E}_{z \sim \mathcal{D}(\theta)}[\ell(\theta;z)]\) where \(\theta\) is the model parameter, and \(\mathcal{D}(\theta)\) is the induced distribution due to the deployment of \(\theta\).

One of the major focuses of performative prediction is to find the optimal model \(\theta_{\textsf{OPT}}\) which achieves the minimum performative prediction risk: \(\theta_{\textsf{OPT}}:= \mathop{\mathrm{\arg\!\min}}_{\theta\in \Theta} \mathsf{PR}(\theta)\), or performative stable model \(\theta_{\textsf{ST}}\), which is optimal under its own induced distribution: \(\theta_{\textsf{ST}}:= \mathop{\mathrm{\arg\!\min}}_{\theta\in \Theta}\mathbb{E}_{z \sim \mathcal{D}(\theta_{\textsf{ST}})}[\ell(\theta;z)]\) . In particular, one way to find a performative stable model \(\theta_{\textsf{ST}}\) is to perform repeated retraining [1].

In order to get meaningful theoretical guarantees on any proposed algorithms, works in this field generally require particular assumptions on the mapping between the model parameter and its induced distribution (e.g., the smoothness of the mapping), or require multiple rounds of deployments and observing the corresponding induced distributions, which can be costly in practice [6], [11]. A few recent works are on finding performative optimal solutions without explicitly making the convexity assumption. For example, [13] does not explicitly convexity assumption, but they focus on optimization heuristics that are not guaranteed to minimize performative regret. below, we will provide the discussions for three of them.

In addition, minimizing the performative risk often requires knowing a specific model for the distribution map \(\mathcal{D}(\cdot)\) that can be fit. To ensure performative risk minimization is tractable, one also requires imposing structural assumptions on the distribution map. For example, [10] makes parametric assumptions on \(\mathcal{D}(\theta)\) and assumes that \(\mathcal{D}(\theta)\) has a continuously differentiable density \(p(z; \varphi(\theta))\), where \(\varphi(\cdot): \Theta \rightarrow \Phi\) represents the mapping from the model parameter space \(\Theta\) to the data distribution parameter space \(\Theta\). [9] assume the underlying data distribution follows a location family distribution, and then impose a mixture dominance assumption on the distribution map \(\mathcal{D}(\cdot)\) from which it follows that \(\mathsf{PR}(\theta)\) is convex; this again leads to a gradient-based optimization algorithm. Similar work include [6], [7], [10], [14], to name a few.

12.0.0.1 Comparison with [9]

[9] identifies mixture dominance condition for any particular model parameter pairs under which the performative risk is convexity. In particular, they posit a simple distribution map in which \(\varphi(\theta) = \phi_0 + M\theta\), where \(M \in \mathbb{R}^{d_\Phi \times d_\Theta}\) and \(\phi_0 \in \Phi\) is some “base” distribution parameter; in other words, they assume that the data population reacts to a model by shifting each of their features according to some linear transformation of the model parameter. Their algorithm for this special case works in two stages: first estimating \(\varphi_0\) and \(M\) by deploying random models; then, once this distribution map has been accurately estimated, the performative loss is convex in \(\theta\), and can be optimized offline. The distribution map estimation takes \(O(d_\Theta/\epsilon)\) samples to obtain an \(\epsilon\)-suboptimal model.

12.0.0.2 Comparison with [11]

For example, closely related is a recent paper that proposes using the Lipschitz bandit approach to solve the performative prediction problem [11]. The major differences between this work and their work are: first, we define the regret w.r.t \(N\) rather than w.r.t \(T\), which is a more realistic measure in the performative prediction setting; second, their regret has exponential dependency on the “zooming dimension” \(d\) (which is roughly the model parameter \(d_\Theta\)), while our dependency on the model and distribution dimensions are both linear.

12.0.0.3 Comparison with [12]

Another closely related work is [12] uses zeroth-order methods for the convex-concave minimax problem. Specifically, they proposed to formulate the performative prediction problem as the Wasserstein distributionally robust learning with decision-dependent data problem, and further reduce it to a constrained finite-dimensional smooth convex-concave min-max problem, and propose a zeroth-order random reshuffling-based algorithm to solve the problem without assuming any other structure on the curvature of the min-max loss. Similar to ours, they also use the zeroth-order method to perform their optimization procedure; different from ours, they approach the performative prediction problem through the angle of robustness, which accounts for model misspecification in their analysis.

12.0.0.4 Other Aspects of performative prediction

Also related are the recently developed lines of work on the multiplayer version of the performative prediction problem [15], [27], [29], [30]. While existing strategic classification and performative prediction problems focus primarily on the interplay between a single learner and the population that reacts to the learner’s actions, this line of work takes into account competition from multi-learners, and develop performatively stable equilibria and Nash equilibria of the game. Similarly, [28] confront multiple interactive models in some dynamic environments. Another line of work is the economic aspects of performative prediction [31], [32]. From the optimization aspect, [33] focuses on the optimization aspect of finding the performative optimal point and offers an online stochastic primal-dual algorithm for tracking equilibrium trajectories. Also related is the recent development of the concept called induced domain adaptation [2], whose primary focus is to study the transferability of a particular model trained primarily on the source distribution and provide theoretical bounds on its performance on its induced distribution, which is helpful in estimating the effect of a given classifier when repeated retraining is unavailable.

12.0.0.5 Theoretical comparisons to some existing methods in the convex case

When the problem reduces to a convex, differentiable Lipschitz case, our algorithm will be reduced to the convex case provided in 2.2 (the warm-up setting), which achieves a \(\tilde{O}(\sqrt{d N})\) regret bound. This implies that our algorithm achieves a \(\Delta\)-suboptimal model with \(O(d/\Delta^2)\) samples (see [lemma:regret-bound-for-model-convex-performative-risk]).

Here, we compare the three papers that the reviewer mentioned:

• [10] focus on a single-distribution Gaussian distribution with a fixed variance setting while we cover a boarder range of settings. Their theoretical guarantee shows that the proposed method converges to a performative optimal point as the number of iterations \(T\approx \sigma^{-4/5}\) where \(\sigma\) bounds the output of PR from the PR of the optimal performative point. The sample required at each iteration is \(O(1/\sigma^2\log T)\).

• [9] show that when the distribution maps \(\mathcal{D}(\cdot)\) form a location-scale family and when the model dimension is \(O(d)\), computing a \(\Delta\)-suboptimal classifier requires \(O(d/\delta)\) samples. We do not require these assumptions.

• [1] focus on achieving a performative stable point while we focus on attaining a performative optimal point.

13 Plots For Empirical Results↩︎

References↩︎

---

1. \(\widetilde{O}(\cdot)\) suppresses polylogarithmic factors in \(N\) and the failure probability \(1/p\).↩︎

2. Samples that the learner deploys along the way of finding the performative optimal model.↩︎

3. One may wonder how to find the optimal \(\vartheta^*(\phi)\) when there are two model parameters \(\theta\) and \(\theta^{\prime}\) that realize the same \(\phi\) (i.e., \(\varphi(\theta)=\varphi\left(\theta^{\prime}\right)\) and \(\mathsf{PR}\left(\theta^{\prime}\right) \geq \mathsf{PR}(\theta))\). Recall that the objective function for \(\operatorname{\mathsf{LearnModel}}\) is to find any model \(\theta\) that leads to the particular target data parameter \(\phi\) such that \(\varphi(\theta)=\phi\). It is quite possible that multiple models can induce the same target data parameter; however, since the goal is to find any one of them, having multiple model parameters won’t be an issue – in fact, it can only help speed up the process↩︎

4. We can also verify that 3 does not satisfy the mixture dominance assumption.↩︎

5. The sample required for each round of estimate EstimatePR is \(\mathcal{O}(1)\); this is because EstimatePR itself is an unbiased estimator, so even with one sample, in expectation, the estimation will be unbiased.↩︎

6. For notation simplicity, here, we use \(\mathsf{KL}(\phi_1|| \phi_2)\) to represent \(\mathsf{KL}(\mathcal{D}_1|| \mathcal{D}_2)\) where the data distribution \(\mathcal{D}_1\) and \(\mathcal{D}_2\) has the parameter \(\phi_1\) and \(\phi_2\), respectively.↩︎

7. A distribution \(\mathcal{D}(\theta)\) with the density function \(p(\cdot | \varphi(\theta))\) parameterized by \(\theta \in \Theta\) is called \((\ell_2, K)\)-Lipschitz continuous [21] if for all \(z\) in the sample space, the log-likelihood \(f(\theta) = \log p(z|\varphi(\theta))\) is Lipschitz continuous with respect to the \(\ell_2\) norm of \(\theta\) with constant \(K(z)\).↩︎