Distributionally Robust Performative Prediction

Authors: songkai  xue
yuekai  sun
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 18:54:35

Abstract: Performative prediction aims to model scenarios where predictive outcomes subsequently influence the very systems they target. The pursuit of a performative optimum (PO)—minimizing performative risk—is generally reliant on modeling of the distribution map, which characterizes how a deployed ML model alters the data distribution. Unfortunately, inevitable misspecification of the distribution map can lead to a poor approximation of the true PO. To address this issue, we introduce a novel framework of distributionally robust performative prediction and study a new solution concept termed as distributionally robust performative optimum (DRPO). We show provable guarantees for DRPO as a robust approximation to the true PO when the nominal distribution map is different from the actual one. Moreover, distributionally robust performative prediction can be reformulated as an augmented performative prediction problem, enabling efficient optimization. The experimental results demonstrate that DRPO offers potential advantages over traditional PO approach when the distribution map is misspecified at either micro- or macro-level.

Main paper: 
 introduction: 
 In numerous fields where predictive analytics play an important role, decisions made on the basis of machine learning models do not just passively predict outcomes but actively influence future input data. Consider the domain of financial services, such as credit scoring and loan issuance, where a model's decision to grant or deny an application can affect the applicant's future financial behaviors and, consequently, the profile of future applicants. Similarly, in educational settings, the decision process for school admissions can shape the applicant pool, as those who are accepted often share their success strategies, indirectly influencing the preparation of future candidates. These examples highlight the study of performative prediction [29] , a recent framework that facilitates a formal examination of learning in the presence of performative distribution shift resulting from deployed ML models.Delving deeper into the formulations of performative prediction, the concept of a distribution map emerges as pivotal. This map characterizes the impact that a deployed ML model has on the underlying data distribution, which is a crucial element in navigating performative effects. The literature primarily revolves around the pursuit of performative stability (PS), a model which is optimal for the distribution it induces [29, 25, 5, 8] . However, a more ambitious target is the performative optimum (PO), which seeks the minimization of performative risk, the risk of the deployed model on the distribution it induces. Efficiently achieving PO typically necessitates a modeling of the distribution map [26, 14, 15, 24] . Practically, the precise influence of a model on the data ecosystem is intricate and dynamic, making perfect specification an unattainable ideal.In this work, we propose a distributionally robust performative prediction framework that aims to enhance robustness against a spectrum of distribution maps, thereby mitigating the issue of misspecification. Our contributions are summarized as follows: 1) in Section 2, we formalize the DRPO concept, anchoring it within the performative prediction literature as a robust alternative; 2) in Section 3, we provide theoretical insights into the efficacy of DRPO, demonstrating its resilience in the face of distribution map misspecification; 3) in Section 4, we recast distributionally robust performative risk minimization as an augmented performative risk minimization problem, facilitating efficient optimization; 4) in Section 5, we showcase DRPO's advatanges over conventional PO by empirical experiments. The paper concludes with a summary and discussion.Performative prediction. Performative prediction is an emerging framework for learning models that influence the data they intend to predict. The majority of research focuses on performative stability [29, 25, 5, 30, 21, 8, 7] , albeit with a few exceptions aiming at performative optimality. [26] propose a two-stage plug-in method for finding the PO. [14] propose to find the PO by a parametric model of the distribution map. This method is extended by [15] to stateful performative prediction. [18] solves the PO when the problem is outcome performative only. [24] argue that the PO with a misspecified nominal distribution map can still reasonably approximate the true PO, as long as the misspecification level is not significant. This claim is also supported by our theory and experimental findings. Unlike them, we demonstrate that the DRPO is comparable to the PO if the misspecification is small, whereas the DRPO can offer substantial advantages over the PO if the misspecification is moderate to large. Moreover, the DRPO ensures reasonable performance for all distribution maps in an uncertainty collection surrounding the nominal distribution map, rather than just a single distribution map.Distributionally robust optimization. DRO solves a stochastic optimization problem by optimizing under the worst-case scenario over an uncertainty set of probability distributions. Most popular DRO frameworks are based on φ-divergence [13, 2, 11, 12, 20, 9] and Wasserstein distance [11, 27, 6, 31, 4, 3, 10] . The existing DRO literature pays no attention to performative prediction except for [28] . [28] study the repeated distributionally robust optimization algorithm, which repeatedly minimizes the distributionally robust risk at the induced distribution. They show such repeated training algorithm yields a distributionally robust performative stable (DRPS) solution, assuming conditions analogous to the validity of repeated risk minimization [29, 25] in finding the performative stable (PS) solution. Nevertheless, the DRPO solution, which lies at the heart of the distributionally robust performative prediction problem, is not the subject of their study. Furthermore, they lacks theoretical guarantees regarding the proximity of the DRPS to either the PS or PO solution. 
performative prediction essentials: 
 Let Θ denote the (finite-dimensional) model parameter space, Z denote the data sample space, and P(Z) denote the set of probability measures supported on Z. In performative prediction, we aim to find a θ ∈ Θ that achieves low performative riskEQUATIONwhere ℓ : Z × Θ → R is the (known) loss function, and D true : Θ → P(Z) is the true distribution map. The true performative optimum (true PO) θ PO,true is known to minimize the (true) performative risk:θ PO,true ∈ arg min θ∈Θ PR true (θ) = E Z∼Dtrue(θ) [ℓ(Z; θ)] . (2.2)It is easy to see that if we know the true distribution map, then we can evaluate the true performative risk and find the true performative optimum well up to some finite sample error which is negligible as the sample size goes to infinity. However, the true map D true (•) is unknown in general, thus posing a significant obstacle in the pursuit of evaluating and optimizing the true performative risk.To enable the optimization of performative risk, it is necessary to have a known nominal distribution map D(•) that is believed to closely approximate the unknown true distribution map D true (•). Then one can find the performative optimum (PO) by minimizing the nominal performative risk:θ PO ∈ arg min θ∈Θ PR(θ) = E Z∼D(θ) [ℓ(Z; θ)] . (2.3)Because the distribution map is inevitably misspecified, D( EQUATIONwhere ∆ θ (•), u θ (•), and c(•, •) are known as individual's best response function, utility function, and cost function, respectively. The best response function can be lifted to the measurable space of X × Y so that we have the response mapT θ x y = ∆ θ (x) y = arg max x ′ {u θ (x ′ ) -c(x, x ′ )} y .The nominal distribution map D( Z ∼ D(θ) ⇐⇒ Z d = Z 0 + Aθ where Z 0 ∼ D true (0),where A ∈ R dim(Z)×dim(Θ) is unknown and therefore must be estimated. If we observe the sampling distributions of D(θ 0 ), D(θ 1 ) . . . , D(θ K ), then A is partially identified up to a linear subspace of R dim(Z)×dim(Θ) : A ∈ {M | M (θ k -θ 0 ) = µ k -µ 0 for k ∈ [K]},From an intuitive perspective, the PO solution (2.3) has the potential to achieve low performative risk PR true (θ PO ) when the nominal distribution map D(•) closely aligns with the true distribution map D true (•). However, D(•) and D true (•) may be quite different. In such cases, the PO solution may incur high performative risk. To address this issue, we propose a distributionally robust formulation for performative prediction, where we explicitly incorporate into the learning phase the consideration that the true distribution map D true (•) is different from the nominal one D(•).Let D(•∥•) be the KL divergence, i.e., D(Q∥P ) = φ dQ dP dP = log dQ dP dQ,where φ(t) = t log t for any t > 0. Here dQ/dP is the Radon-Nikodym derivative, and we implicitly require the probability measure Q to be absolutely continuous with respect to P . With the KL divergence, we can define a family of distribution maps around the nominal distribution map. Specifically, the uncertainty collection around D with critical radius ρ is defined asU(D) = { D : Θ → P(Z) | D( D(θ)∥D(θ)) ≤ ρ, ∀θ ∈ Θ}.The radius ρ reflects the the magnitude of shifts in distribution map we seek to be robust to. We remark that the value of ρ can be prescribed or be selected in data-driven ways. We postpone the discussion on critical radius calibration to Section 4. Distributionally robust performative prediction asks to not only perform well on a fixed performative prediction problem (parameterized by the distribution map D), but simultaneously for a range of performative prediction problems, each determined by a distribution map in an uncertainty collection U. This results in more robust solutions, that is, those DRPOs which are robust to misspecification of distribution map. The uncertainty collection plays a key role: it implicitly defines the induced notion of robustness. Moreover, distributionally robust performative prediction yields a natural approach for certifying out-of-sample performance, which is summarized by the following principle. Proposition 2.6 (Generalization principle of distributionally robust performative prediction). Suppose that the uncertainty collection U contains the true distribution map D true , then the true performative risk is bounded by the distribution robust performative risk: PR true (θ) ≤ DRPR(θ) for any θ ∈ Θ.In consequence, we have PR true (θ DRPO ) ≤ DRPR(θ DRPO ).Essentially, if U is chosen appropriately, the corresponding DR performative risk upper bounds the true performative risk, and thus DRPO enjoys provable guarantees on its incurred performative risk.A toy example is employed to facilitate a conceptual understanding of the advantages of DRPO over PO in relation to achieving improved control over the worst-case performative risk.Let Z = R, Θ = [-1, 1], and ℓ(z; θ) = θz. Let the nominal distribution map be D(θ) = N (f (θ), σ 2 ) for some f : [-1, 1] → R and σ 2 > 0. Then the nominal performative risk isPR(θ) = E Z∼N (f (θ),σ 2 ) [ℓ(Z; θ)] = θf (θ).Regularization effect. With the dual formula given in Section 3.1, one can derive the distributionally robust performative risk directly:DRPR(θ) = PR(θ) + √ ρ Penalty(θ),where the penalty function Penalty(θ) = √ 2σ 2 |θ| penalizes the deviation of θ from the origin 0, and the critical radius ρ tunes the level of regularization. That is to say, in this toy example, the distributionally robust performative risk minimization problem is essentially a L 1 -regularized performative risk minimization problem.Better worst-case control. To be more concrete, we let f (θ) = a 1 θ + a 0 for some a 1 , a 0 > 0. For any D ∈ U(D), let the performative risk of D be PR D (θ) = E Z∼ D(θ) [ℓ(Z; θ)]. If D is the true distribution map, then PR D (θ) is the true performative risk that we incur. Through direct calculation (see details in Appendix A), one can show that θ DRPO is more robust than θ PO in the sense of worstcase performative risk control, that is, supD∈U (D) PR D (θ PO ) ≥ sup D∈U (D) PR D (θ DRPO ) + ρσ 2 2a1for any fixed ρ ≤ a 2 0 2σ 2 . This example shows that the worst-case performative risk of the PO can be arbitrarily larger than that of the DRPO, as a 1 → 0. The message that DRPO offers certain advantages over PO in terms of mitigating worst-case performative risk is also supported by the empirical results shown in Section 5. 
strong duality of drpr: 
 The evaluation of distributionally robust performative risk DRPR(θ) given in (2.5) involves an infinite dimensional maximization problem which is generally intractable. Fortunately, it is in fact equivalent to a minimization problem over a single dual variable. Proposition 3.1 (Strong duality of DRPR). For any θ ∈ Θ, we haveDRPR(θ) = inf µ≥0 µ log E Z∼D(θ) e ℓ(Z;θ)/µ + µρ . (3.1)The dual reformulation (3.1) will be served as the cornerstone of developing algorithms for finding the DRPO in Section 4. As a byproduct of Proposition 3.1, a characterization of the worst-case distribution map which attains the supremum in (2.5) is given in Appendix B.Fow now, we are interested in bounding the excess risk:E( θ) = PR true ( θ) -min θ∈Θ PR true (θ) = PR true ( θ) -PR true (θ PO,true ), where θ is an approximate solution to the true PO θ PO,true , which could particually be θ PO and θ DRPO . The excess risk captures the true performance of θ relative to the oracle performative optimum θ PO,true , providing a direct measurement of the suboptimality of θ in terms of performative risk. As follows, we show the excess risk bounds of the PO solution and the DRPO solution, E(θ PO ) and E(θ DRPO ), and compare them. Proposition 3.2 (Excess risk bound of the PO). Suppose that we have bounded loss function |ℓ(z; θ)| ≤ B for any z ∈ Z, θ ∈ Θ and some B > 0. Then we haveEQUATIONComparing Proposition 3.2 and 3.3, we see that the excess risk bound of the DRPO can be localized to the true PO while the excess risk bound of the PO is entangled with the full parametric space Θ.Although we are comparing two upper bounds which can be not tight enough, the comparison sheds lights to the potential benefits of using DRPO over PO solution. Even if in the case of no significant improvement of using DRPO over PO solution, the excess risks of them are comparable, thus doing no harm. Our insight has been verified through a toy example in Section 2.4 and as well experimental results in Section 5. In Appendix C, we generalize Proposition 3.3 to the scenario when the uncertainty collection doesn't cover the true distribution map, i.e., D(D true (θ DRPO )∥D(θ DRPO )) > ρ. 
algorithms: 
 We recall a standard algorithm for performative risk minimization in Appendix E. In the following subsections, we will see that any off-the-shelf algorithms for finding the PO can be utilized as an intermediate algorithm for finding the DRPO by using our proposed algorithms. Moreover, we provide practical considerations for the selection of a critical radius in the last subsection.By the strong duality in Proposition 3.1, DR performative risk minimization is equivalent to the following optimization problem jointly over (θ, µ):min θ DRPR(θ) ⇐⇒ min θ∈Θ inf µ≥0 ψ(θ, µ) = µ log E Z∼D(θ) e ℓ(Z;θ)/µ + µρ . (4.1)This suggests an alternating minimization, summarized in Algorithm 1, where we learn θ DRPO by fixing µ and minimizing on θ and then fixing θ and minimizing on µ alternatively until convergence.Algorithm 1 DR Performative Risk Minimization Update θ ← arg min θ∈Θ E Z∼D(θ) e ℓ(Z;θ)/µ 5:Update µ ← arg min µ≥0 {ψ(θ, µ)} (ψ in (4.1)) 6: end while 7: Return: θThe step of minimizing on θ with fixed µ (Line 4 in Algorithm 1) is itself a performative risk minimization problem, which can be solved by any suitable performative risk minimization algorithm. The step of minimizing on µ with fixed θ (Line 5 in Algorithm 1) can be solved by the line search or the Newton-Raphson method since ψ(θ, µ) is convex in µ. The total cost of Algorithm 1 is therefore comparable to that of the performative risk minimization algorithm used in the intermediate step. Lastly, the alternating minimization algorithm in common practice guarantees global convergence (to stationary point) regardless of how the optimization parameters are initialized. With the strong convexity assumption, the alternating minimization algorithm guarantees convergence to the global minimum.Treating ρ as a hyperparameter which can be tuned by a practitioner, the solution of the dual problem (4.1) can be denoted by(θ ⋆ (ρ), µ ⋆ (ρ)). One can show that µ ⋆ (ρ) is a decreasing function of ρ. An intuition is that as µ → ∞, we have arg min θ∈Θ {ψ(θ, µ)} ≈ arg min θ∈Θ E Z∼D(θ) [ℓ(Z; θ)] ,which reduces to the original performative risk minimization problem, or the distributionally robust performative risk minimization problem with ρ = 0 (see an formal explanation in Appendix F).With this motivation, instead of tuning ρ, we can tune µ (or the inverse of it, denoted by α = µ -1 ) and solve the α-tilted performative risk minimization problem:EQUATIONAlgorithm 2 Tilted Performative Risk Minimization 1: Input: tilt α, nominal distribution map D(θ) 2: Update θ ← arg min θ∈Θ E Z∼D(θ) e αℓ(Z;θ) 3: Return: θwhere TPR(θ) stands for the tilted performative risk and θ TPO is the tilted performative optimum, that is, the performative optimum of the tilted problem. In order to have stronger distributional robustness property, we tune α to be larger. Given the correspondence µ ⋆ (ρ), we should have θ TPO with α equals θ DRPO with ρ = (µ ⋆ ) -1 (1/α). Therefore, the tilted performative risk minimization implicitly solves a corresponding DR performative risk minimization problem. Finally, we remark that exponential tilting is a statistical method that has been around at least since the exponential family [17] was first invented. More recently, it has been applied to operation research [1] and machine learning [22, 23] .The performance of the DRPO is contingent on the uncertainty collection radius ρ, which is typically difficult to choose a priori without additional information. The greater the value of ρ, the higher the level of distributional robustness, and thus the greater the tolerance for distribution map misspecification. Therefore, the selection of ρ reflects a practitioner's risk-aversion preference. In this subsection, we present two simple, yet effective calibration techniques for selecting ρ.Post-fitting calibration. Without additional information, we can only hope to be robust to a prescribed set of distribution maps, say Ξ. The assumption of Proposition 3.3 requires only the uncertainty collection at the DRPO, which reduces to an uncertainty ball centered at D(θ DRPO ), encompassing the true distribution D true (θ DRPO ). Therefore, in order to provide a provable guarantee for all distribution maps in Ξ, the radius ρ can be chosen based on the following criterion: Here D is the estimated KL divergence, and θ DRPO (ρ) is indexed by the radius ρ to highlight its dependence on ρ as a tuning parameter to be calibrated. We implement the post-fitting calibration approach (with bisection search for ρ) in Section 5.1.ρ cal = arg minCalibration To conclude this subsection, we discuss the computational costs of the proposed calibration methods.For general problems, these calibration methods necessitate a grid search, which may be computationally expensive. Fortunately, for specific problems (for example, experiments in Section 5.1), we can exploit the decreasing nature of the estimated KL divergence as a function in ρ. As a result, we can use bisection search rather than grid search to significantly reduce computational costs. 
experiments: 
 We revisit Examples 2.1, 2.2, and 2.3 and compare the PO and the DRPO empirically. For a particular (true) distribution map, either the PO or the DRPO may have the potential to outperform the other in terms of the performative risk evaluated at this particular distribution map. In contrast to the PO, however, the DRPO aims to guarantee reasonable performance for all distribution maps in an uncertainty collection around the nominal distribution map. To ensure the performance of the DRPO on a (set of) specific distribution map(s), the radius ρ (or the tilt α) must be calibrated. Lastly, each shaded region in figures below shows the curve's standard error of the mean from 30 trials.In reference to Example 2.1, we examine strategic classification involving a cost function that is misspecified. The experimental setup resembles that in [29] . The task is credit scoring, specifically predicting debt default. Individuals strategically manipulate their features to obtain a favorable classification.Consider an instantiation of the response map (2.4) such that u θ (x) = -θ ⊤ x and c(x, x ′ ) =1 2ϵ × ∥x strat -x ′ strat ∥ 2 2 + ∞ × ∥x non-strat -x ′ non-strat ∥ 2 2 .Without loss of generality, let the first m features be strategic features and the last d -m features be non-strategic features. Let B = diag(1, . . . , 1, 0, . . . , 0) ∈ R d×d where the first m diagonal elements are 1's and the others are 0's. Then the best response function is∆ θ (x) = x -ϵBθ.For the base distribution D(0), we use a class-balanced subset of a Kaggle credit scoring dataset ( [16] , CC-BY 4.0). Features encompass an individual's historical data, including their monthly income and credit line count. Labels are binary where the value of 1 represents a default on a debt and 0 otherwise. There are a total of 3 strategic features and 6 non-strategic features. We use logistic model for the classifier and the cross-entropy loss with L 2 -regularization for the loss function ℓ.Consider the cost function is misspecified by its performativity level ϵ. We specify the cost function with the nominal performativity level ϵ = 0.5. However, the true performativity level ϵ true might not be 0.5, but in the range of [0.5 -0.5η, 0.5 + 0.5η] for some η ≥ 0.The left plot of Figure 1 shows performative risk incurred by the PO and the DRPO's with various radius ρ's. Note that the PO can be understood as the DRPO with ρ = 0. As ρ increases, the DRPO aims to achieve more uniform performance across a wider range of ϵ true . The middle plot of Figure 1 shows relative improvement in worst-case performative risk 1 of the DRPO to the PO as the radius ρ 1 The relative worst-case improvement of θ to θPO is Recall Example 2.2, we examine a location model for distribution map where the misspecification arises from the estimation error of the model parameter.Let V = [θ 1 -θ 0 | θ 2 -θ 0 | • • • | θ K -θ 0 ] ∈ R d×K and U = [µ 1 -µ 0 | µ 2 -µ 0 | • • • | µ K -µ 0 ] ∈ R d×Kwhere d = dim(Θ). The unknown parameter A can only be partially indentified through the equationAV = U when K < d. A particular estimate of A is A = U V † = U (V ⊤ V ) -1 V ⊤ ,where V † is the Moore-Penrose inverse of V . In fact, the parameter A is only identifiable up to the subspaceW = {U V † + E | span{E ⊤ } ⊂ N (V ⊤ )}, where N (V ⊤ ) is the left null space of V . Precicely, we have AV = U if and only if A ∈ W.In this experiment, we still use the credit data. We observe sampling distribution of D(0), D(e 1 ), and D(e 2 ), where e i is the i-th canonical basis. For the true distribution map, the performativity of the first two features is 0.5, while the performativity of the other 7 features is ϵ true . In short, A true = diag(0.5, 0.5, ϵ true , . . . , ϵ true ). We set the range of ϵ true to be [-0.5η, 0.5η] for η ≥ 0. By using the estiamte A, we model the performativity of the first two features correctly, but wrongly model the other features as non-strategic. This time we fit TPO by Algorithm 2 instead of DRPO.The left plot of Figure 2 shows performative risk incurred by the PO and the TPO's with various tilt α's. As α increases, the TPO performs more uniformly across a wider range of ϵ true . The middle plot of Figure 2 shows relative improvement in worst-case performative risk of the TPO to the PO as the tilt α increases, for different range of misspecification η's. Without misspeicification, η = 0, the PO is for sure better than the TPO. With moderate to large misspecification, η ∈ {2/3, 4/3, 2}, the TPO demonstrates certain advantages over the PO. The right of Figure 2 shows the relationship between the distributionally robust performative risk minimization and the tilted performative risk minimization: fitting DRPO with ρ (which returns the optimal dual variable µ ⋆ ) is equivalent to fitting TPO with α = 1/µ ⋆ . Referencing to Example 2.3, we examine the scenario where the population distribution map is a mixture of two subpopulation distribution maps. We train a classifier using the population distribution map D pop , but target at its performance on both the majority and minority, D maj and D min . The distribution map is therefore misspecified due to subpopulation shift.The experimental setup resembles that in [28] . Note that the credit dataset used in the previous experiments lacks demographic features. To enable oracle access to demographic information, synthetic data is generated for a performative classification task. The synthetic dataset exemplifies a scenario in which a linear decision boundary is not able to effectively classify both the majority and minority groups, necessitating a trade-off between them.Figure 3 shows performative risk of the population, the majority, and the minority incurred by the TPO, as the tilt α increases. The PO (which is TPO with α = 0) exhibits the lowest performative risk at the population, but the greatest disparity between its performance for the majority and minority groups. As α increases, the TPO reduces the performance gap between the two groups at the expense of an increased population performative risk. This suggests that the distributionally robust performative prediction framework has the potential to mitigate unfairness towards the minority group, even in the absence of demographic information. Using a small calibration set with demographics, we can calibrate the tilt α cal 's via the calibration set approach described in Section 4.3. The goal is to calibrate the tilt to satisfy a four-fifth rule2 with minimal population performative risk. The vertical bands in Figure 3 shows the calibrated tilt α cal 's reasonably meet the goal. 
summary and discussion: 
 In this work, we present a distributionally robust performative prediction framework that aims to improve robustness against a variety of distribution maps, thereby mitigating the problem of distribution map misspecification. We show provable guarantees for DRPO as a robust approximation to the true PO when the nominal distribution map differs from the actual one. We developed efficient algorithms for minimizing the distributionally robust performative risk. Empirical experiments are conducted to support our theoretical findings and validate the proposed algorithms.The components of our approach are not new, but we are combining them in a novel way to solve a relevant problem. To be precise, the proposed approach is novel in the context to use the idea of distributional robustness to solve the practical problem of distribution map misspecification in performative prediction. In addition, it is novel to study the solution concept of distributionally robust performative optimum (DRPO), both theoretically and algorithmically.In Appendix H, we extend the KL divergence distributionally robust performative prediction framework to a general φ-divergence distributionally robust performative prediction framework. Furthermore, it is possible to go beyond general φ-divergence. An extension to a Wasserstein DRO version is a natural direction for future research, calling for the development of new algorithms. 3Recall that Z = R, Θ = [-1, 1], ℓ(z; θ) = θz, and the nominal distribution map is D(θ) = N (f (θ), σ 2 ) for some f : [-1, 1] → R and σ 2 > 0. Then the nominal performative risk isPR(θ) = E Z∼N (f (θ),σ 2 ) [ℓ(Z; θ)] = θf (θ).We firstly show that the distributionally robust performative risk is given by DRPR(θ) = PR(θ) + √ ρ Penalty(θ),E Z∼ D(θ) [ℓ(Z; θ)] = inf µ≥0 µ log E Z∼D(θ) e ℓ(Z;θ)/µ + µρ = inf µ≥0 µ θf (θ) µ + σ 2 θ 2 2µ 2 + µρ = θf (θ) + inf µ≥0 σ 2 θ 2 2µ + µρ = θf (θ) + 2ρσ 2 |θ| = PR(θ) + √ ρ Penalty(θ).Therefore, we derive an alternative form of DRPR(θ), which is PR(θ) with an L 1 -regularization term.Now we are in a more concrete setup that f (θ) = a 1 θ + a 0 for some a 1 , a 0 > 0. Recall that for any D ∈ U(D), we denote the performative risk of D bePR D (θ) = E Z∼ D(θ) [ℓ(Z; θ)].We secondly show that supD∈U (D) PR D (θ PO ) ≥ sup D∈U (D) PR D (θ DRPO ) + ρσ 2 2a 1 for any fixed ρ ≤ a 2 0 2σ 2 .Proof. In fact, we haveEQUATIONDRPR(θ DRPO ) = -(a 0 -2ρσ 2 ) 2 4a 1 .By Proposition 2.6, the generalization principle of distributionally robust performative prediction, we have supD∈U (D) PR D (θ DRPO ) ≤ DRPR(θ DRPO ) = -(a 0 -2ρσ 2 ) 2 4a 1 .On the other hand, consider an adversarial distribution map D adv (θ) = N (a 1 θ + a 0 -2ρσ 2 , σ 2 ).One can show that D KL (D adv (θ), D(θ)) = ρ for all θ ∈ Θ, and therefore D adv ∈ U(D). Then supD∈U (D) PR D (θ PO ) ≥ PR D adv (θ PO ) = -(a 0 -2ρσ 2 ) 2 4a 1 + ρσ 2 2a 1 .Therefore we complete the proof.Multi-variate case. We extend the uni-variate example to multi-variate case. Let Z = R d , Θ = [-1, 1] d , and ℓ(z; θ) = θ ⊤ z. Let the distribution map be D(θ) = N d (f (θ), Σ) for some f : [-1, 1] d → R d and Σ is positive semi-definite. One can show that the performative risk isPR(θ) = E Z∼D(θ) [ℓ(Z; θ)] = E Z∼N d (f (θ),Σ) [ℓ(Z; θ)] = θ ⊤ f (θ)and the distributionally robust performative risk isDRPR(θ) = sup D: D∈U (D) E Z∼ D(θ) [ℓ(Z; θ)] = θ ⊤ f (θ) + 2ρθ ⊤ Σθ = PR(θ) + √ ρ Penalty(θ),(A.1) where the penalty function Penalty(θ) = √ 2θ ⊤ Σθ penalizes the deviation of θ from the origin 0, and the critical radius ρ tunes the level of regularization. We also note that in this case the distributionally robust performative prediction problem can be transformed to a second-order cone constrained program (A.1).As a byproduct of the proof of Proposition 3.1, here we provide a characterization of the worst-case distribution map which attains the supremum in (2.5). Proposition B.1 (Worst-case distribution map). Suppose the problem (3.1) is solved by the unique µ ⋆ (θ) > 0 for any θ ∈ Θ. We define a distribution map D satisfying the density ratio equationd D(θ) dD(θ) = e ℓ(Z;θ)/µ ⋆ (θ) E Z∼D(θ) [e ℓ(Z;θ)/µ ⋆ (θ) ] , ∀θ ∈ Θ. (B.1)Then we have that D is the unique worst-case distribution map, that is,D(θ) = arg sup D(θ): D∈U (D) E Z∼ D(θ) [ℓ(Z; θ)]. (B.2)Proposition B.1 shows that the worst-case distribution map D is an exponentially tilted distribution map with respect to the nominal distribution map D, where D puts more weights on the high ends.Figure 4 shows histogram of performative loss for the PO, the DRPO with ρ = 0.02, and the DRPO with ρ = 0.04, under the setup of Experiment 5.1 with ϵ true = 0.5. These plots displayed in a left-to-right manner demonstrate that the DRPO regulates the right tail of the performative losses. Moreover, as the radius ρ increases, there is a corresponding increase in the degree of regulation effects. We upper bound E(θ DRPO ) when the uncertainty collection doesn't cover the true distribution map. To be specific, we analyze the excess risk bound of the DRPO when D(D true (θ DRPO )∥D(θ DRPO )) > ρ. For simplicity of notation, we denote the true PO by θ ⋆ PO , which is denoted by θ PO,true in the main article.Proof of Proposition 3.1. We only have to show that for any fixed θ ∈ Θ, the dual form (3.1) holds. This follows Theorem 1 presented in [13] .We refer the readers to Proposition H.2 for a standard derivation for the dual form of a general φ-divergence distributionally robust performative risk.Proof of Proposition B.1. This follows Proposition 1 presented in [13] and the discussion paragraph right after the proposition.Proof. We have the following decomposition of the excess risk bound of the PO,PR true (θ PO ) -min θ∈Θ PR true (θ) = PR true (θ PO ) -PR true (θ ⋆ PO ) = PR true (θ PO ) -PR(θ PO ) + PR(θ PO ) -PR(θ ⋆ PO )≤0 by definition of θPO+ PR(θ ⋆ PO ) -PR true (θ ⋆ PO ) ≤2 sup θ∈Θ | PR(θ) -PR true (θ)| =2 sup θ∈Θ E Z∼D(θ) [ℓ(Z; θ)] -E Z∼Dtrue(θ) [ℓ(Z; θ)] ≤2B sup θ∈Θ D TV (D true (θ)∥D(θ)) ≤ √ 2B sup θ∈Θ D KL (D true (θ)∥D(θ)).The last two inequalities are due to the asumption of bounded loss, |ℓ(z; θ)| ≤ B, and Pinksker's inequality.Proof. We have the following decomposition of the excess risk bound of the DRPO,PR true (θ DRPO ) -min θ∈Θ PR true (θ) = PR true (θ DRPO ) -PR true (θ ⋆ PO ) = PR true (θ DRPO ) -DRPR(θ DRPO ) ≤0 by generalization principle + DRPR(θ DRPO ) -DRPR(θ ⋆ PO )≤0 by definition of θDRPO+ DRPR(θ ⋆ PO ) -PR true (θ ⋆ PO ) ≤ DRPR(θ ⋆ PO ) -PR true (θ ⋆ PO ) = Var Z∼D(θ ⋆ PO ) [ℓ(Z; θ ⋆ PO )]ρ + o( √ ρ).The last equality is due to the sensitivity property of KL divergence-based DRO [9] .D.4 Proof of C.1Proof. For any distribution P such that D KL (P ∥D(θ DRPO )) ≤ ρ, we have the following decomposition of the excess risk bound of the DRPO,PR true (θ DRPO ) -min θ∈Θ PR true (θ) = PR true (θ DRPO ) -PR true (θ ⋆ PO ) = PR true (θ DRPO ) -E Z∼P [ℓ(Z; θ DRPO )] + E Z∼P [ℓ(Z; θ DRPO )] -DRPR(θ DRPO ) ≤0 by generalization principle + DRPR(θ DRPO ) -DRPR(θ ⋆ PO )≤0 by definition of θDRPO+ DRPR(θ ⋆ PO ) -PR true (θ ⋆ PO ) ≤ PR true (θ DRPO ) -E Z∼P [ℓ(Z; θ DRPO )] + DRPR(θ ⋆ PO ) -PR true (θ ⋆ PO ) = PR true (θ DRPO ) -E Z∼P [ℓ(Z; θ DRPO )] + Var Z∼D(θ ⋆ PO ) [ℓ(Z; θ ⋆ PO )]ρ + o( √ ρ) =E Z∼Dtrue(θDRPO) [ℓ(Z; θ DRPO )] -E Z∼P [ℓ(Z; θ DRPO )] + Var Z∼D(θ ⋆ PO ) [ℓ(Z; θ ⋆ PO )]ρ + o( √ ρ) ≤BD TV (D true (θ DRPO )∥P ) + Var Z∼D(θ ⋆ PO ) [ℓ(Z; θ ⋆ PO )]ρ + o( √ ρ) ≤ √ 2BD KL (D true (θ DRPO )∥P ) + Var Z∼D(θ ⋆ PO ) [ℓ(Z; θ ⋆ PO )]ρ + o( √ ρ).By the arbitrariness of P in the divergence ball D KL (P ∥D(θ DRPO )) ≤ ρ, we complete the proof.We recall a standard algorithm for performative risk minimization when the nominal distribution map D(•) is modeled by a response map T θ : Z → Z and samples from the base distribution D true (0):Z ∼ D(θ) ⇐⇒ Z d = T θ (Z 0 ) where Z 0 ∼ D true (0).This is a popular model for distribution map including strategic classification (see Example 2.1) and location family (see Example 2.2) as prominent examples.It is not hard to see that the nominal distribution map D(•) is fully characterized by the response map T θ and the base measure D true (0) becauseD(θ) d = T θ♯ (D true (0)) for any θ ∈ Θ,that is, the measure D(θ) is the pushforward measure of D true (0) under the transport map T θ . The performative risk can then be reformulated asPR(θ) = E Z∼D(θ) [ℓ(Z; θ)] = E Z∼T θ♯ (Dtrue(0)) [ℓ(Z; θ)] = E Z∼Dtrue(0) [ℓ(T θ (Z); θ)].With the last formula, the performative risk minimization problem becomes a standard (possibly nonconvex) stochastic optimization problem, which can be solved efficiently by any popular stochastic optimization algorithm, e.g., sample average approximation (SAA, [19] ). given the loss function ℓ(z; θ) and the response map T θ (z) are sufficiently differentiable with respect to θ.We refer to Section 1.1 for a summary of existing performative risk minimization algorithms.F An Explanation to the Claim in Section 4.2In Section 4.2, we claim that arg min θ∈Θ {ψ(θ, µ)} ≈ arg min θ∈Θ E Z∼D(θ) [ℓ(Z; θ)] as µ → ∞. This is due to the fact of that e x ∼ x + 1 for x → 0 and the argmax/argmin theorem. Therefore, we have arg min θ∈Θ µ log E Z∼D(θ) e ℓ(Z;θ)/µ + µρ≈ arg min θ∈Θ µ log E Z∼D(θ) ℓ(Z; θ) µ + 1 + µρ ≈ arg min θ∈Θ E Z∼D(θ) [ℓ(Z; θ)]as µ → ∞.For the loss function ℓ(x, y; θ), we adopt the cross-entropy loss with L 2 -regularization, that is,ℓ(x, y; θ) = -y log h θ (x) -(1 -y) log(1 -h θ (x)) + λ 2 ∥θ∥ 2 2 ,where h θ (x) = 1 + exp{-θ ⊤ x} -1 and λ = 0.001. Given a model θ, we predict y = 1{h θ (x) ≥ 0.5}. In addition, each replicate of the experiments is run on a local machine with an Intel Xeon Gold 6154 CPU and 32GB of RAM in less than an hour execution time.The data preprocessing procedure for the credit dataset [16] follows the procedure documented in [29] .After that procedure, the base distribution D true (0) has n = 14878 data points with equal probability mass. We treat the distribution map associated with D true (0) as the underlying test distribution map which is unknown to us. We generate n IID samples from D true (0) to get a training base distribution D(0), that is, D(0) ∼ D true (0) ⊗n , and then we have a training nominal distribution map induced by D(0). This training procedure is repeated for 10 trials, and the shaded region in each of the figures in this paper represents the standard error of the mean calculated from the 10 trials for the corresponding curve.The left of Figure 5 shows performative balanced error rate, which refers to the balanced error rate (BER) on the test model-induced distribution, incurred by the PO and the DRPO's with various radius ρ's. Because the cross-entropy loss serves as a surrogate for classification error, we see patterns of these curves similar to those in the left of Figure 1 : as ρ increases, the DRPO achieves more uniform performance across a wider range of ϵ true . On the other hand, because the performative classification error is not exactly the criterion we minimize, different patterns are also observed: the DRPO with relatively large radius ρ = 0.04 outperforms the PO for all ϵ true ∈ [0, 1]. As indicated by the right of Figure 5 , by increasing ρ the DRPO constantly improves the relative worst-case performance in terms of performative BER for η ∈ {0.6, 0.8, 1.0}. Here the relative worst-case improvement in performative BER of θ to θ PO is defined by maxϵ true BERtrue(θPO)-maxϵ true BERtrue(θ) maxϵ true BERtrue(θPO) × 100%.For implementing the post-fitting calibration procedure in Section 4. Let Σ be the sample covariance of D(0), a plug-in method implies an estimate of the KL divergence, which is given byD(D true (θ DRPO (ρ))∥D(θ DRPO (ρ))) = 0.5(ϵ true -0.5) 2 θ ⊤ DRPO A ⊤ Σ -1 Aθ DRPO .G.2 Partially Identifiable Distribution Map in Section 5.2 (Continued)The data generating procedure is the same as that in Experiment 5.1. The left of Figure 6 shows performative balanced error rate (BER) incurred by the PO and the TPO's with various tilt α's.Similar to the left of Figure 5 , we observe that 1) as α increases, the TPO achieves more uniform performance across a wider range of ϵ true ; 2) the TPO with relatively large tilt α = 0.5 outperforms the PO for all ϵ true ∈ [-1, 1]. The right of Figure 6 shows relative improvement in worst-case performative balanced error rate of the TPO to the PO as the tilt α increases, for different range of misspecification η's. Without misspeicification, η = 0, the TPO has comparable performance to the PO in terms of performative BER. With moderate to large misspecification, η ∈ {2/3, 4/3, 2}, the TPO shows significant advantages over the PO in terms of relative improvement in worst-case performative BER. We adopt the following data generating process similar to that in [28] . Let X ∼ γN (µ A , Σ A ) + (1 -γ)N (µ B , Σ B ). Let γ = 0.8 so that group A is the majority group and group B is the minority group. Let µ A = 1 × 1 d , µ B = 0.8 × 1 d , andΣ A = Σ B = 0.1 × I d . If X comes from group A, then label Y = 0 if X ⊤ 1 d ≤ µ ⊤ A 1 d . If X comes from group B, then label Y = 0 if X ⊤ 1 d ≤ µ ⊤ B 1 d .The distribution map follows:X 1:⌊d/2⌋ ← X 1:⌊d/2⌋ -ϵθ 1:⌊d/2⌋X (⌊d/2⌋+1):d ← X (⌊d/2⌋+1):d so that the first ⌊d/2⌋ features are strategic features, and ϵ controls the strength of performativity.choose d = 10 and ϵ = 0.5 to wrap up the setup. Finally, we assume knowledge of the true performativity and observe IID samples of size n = 12500 from the population base distribution. In short, we eliminate the effect of population distribution map misspecification, and instead concentrate on the effect of subpopulation distribution map shift.Figure 7 shows the performative accuracy, which refers to the accuracy on the model-induced distribution, of the population, the majority, and the minority incurred by the TPO, as the tilt α increases. Because the cross-entropy loss serves as a surrogate for classification error, we see patterns of the three curves similar to those in Figure 3 . The PO (which is TPO with α = 0) exhibits the highest performative accuracy at the population, but the greatest disparity between its performance for the majority and minority groups. As α increases, the TPO reduces the performance gap between the two groups at the expense of an decreased population performative accuracy. This suggests that the distributionally robust performative prediction framework has the potential to mitigate unfairness towards the minority group, even in the absence of demographic information. For implementing the calibration set procedure in Section 4.3, we have to obtain access to a few samples with the group membership information. Here we allow ourselves to observe IID samples of size n cal = 125 with the known group membership from the population base distribution.The KL divergence distributionally robust performative prediction framework can be extended to a general φ-divergence distributionally robust performative prediction framework. Recall that a φ-divergence is defined byD φ (Q∥P ) = φ dQ dP dP,where φ : R + → R + and φ(1) = 0. Here dQ/dP is the Radon-Nikodym derivative, and we implicitly require the probability measure Q to be absolutely continuous with respect to P . Note that if we choose φ(t) = t log t, then we recover the framework presented in the main article. Now we keep φ as a generic function and we will instantiate some popular families of φ-divergence after the presentation of the general framework.With the φ-divergence, we can define a family of distribution maps around the nominal distribution map. Specifically, the uncertainty collection around D with critical radius ρ is defined asU(D) = { D : Θ → P(Z) | D φ ( D(θ)∥D(θ)) ≤ ρ, ∀θ ∈ Θ}.Definition H.1 (φ-divergence distributionally robust performative risk). The φ-divergence distributionally robust performative risk with the uncertainty collection U(D) is defined asDRPR φ (θ) = sup D: D∈U (D) E Z∼ D(θ) [ℓ(Z; θ)]. (H.1)The evaluation of φ-divergence distributionally robust performative risk DRPR φ (θ) given in (H.1) involves an infinite dimensional maximization problem which is generally intractable. Fortunately, it is in fact equivalent to a minimization problem over two dual variables. This is given by the following strong duality result. Proposition H.2 (Strong duality of DRPR φ ). For any θ ∈ Θ, we haveDRPR φ (θ) = inf µ≥0,ν∈R E Z∼D(θ) µφ * ℓ(Z; θ) -ν µ + µρ + ν , (H.2)where φ * (s) = sup t {st -φ(t)} is the convex conjugate of φ.Proof. We only have to show that for any fixed θ ∈ Θ, the dual form (H.2) holds. We introduce the likelihood ratio L(Z) = d D(θ)/dD(θ). By change of variable, we can rewrite the φ-divergence distributionally robust performative risk (H.1) assup D(θ):Dφ( D(θ)∥D(θ))≤ρ E Z∼ D(θ) [ℓ(Z; θ)] = sup L≥0 E Z∼D(θ) [L(Z)ℓ(Z; θ)] | E Z∼D(θ) [φ(L(Z))] ≤ ρ, E Z∼D(θ) [L(Z)] = 1 ,where the supremum takes over measurable functions. This gives us a constrained optimization problem. Let µ ≥ 0 be the Lagrange multiplier for E Z∼D(θ) [φ(L(Z))] ≤ ρ and ν ∈ R be the Lagrange multiplier for E Z∼D(θ) [L(Z)] = 1. The corresponding Lagrangian isL(L, µ, ν) = E Z∼D(θ) [(ℓ(Z; θ) -ν)L(Z) -µφ(L(Z))] + µρ + ν.For regular φ-divergence, we have supD(θ):Dφ( D(θ)∥D(θ))≤ρ E Z∼ D(θ) [ℓ(Z; θ)] = inf µ≥0,ν∈R sup L≥0 L(L, µ, ν) = inf µ≥0,ν∈R sup L≥0 E Z∼D(θ) [(ℓ(Z; θ) -ν)L(Z) -µφ(L(Z))] + µρ + ν = inf µ≥0,ν∈R sup L≥0 E Z∼D(θ) µ ℓ(Z; θ) -ν µ L(Z) -φ(L(Z)) + µρ + ν = inf µ≥0,ν∈R E Z∼D(θ) µ sup t≥0 ℓ(Z; θ) -ν µ t -φ(t) + µρ + ν = inf µ≥0,ν∈R E Z∼D(θ) µφ * ℓ(Z; θ) -ν µ + µρ + ν .Here the last equality holds according to the definition of the convex conjugate φ * (•).To develop an algorithm for finding the DRPO, we introduce the (µ, ν)-augmented performative risk. Definition H.3 ((µ, ν)-augmented performative risk). The (µ, ν)-augmented performative risk is defined by From (H.2) and (H.3), we see that the minimization problem of DRPR φ (θ) over θ is equivalent to the minimization problem of AugPR φ (θ, µ, ν) jointly over (θ, µ, ν), which is itself a performative risk minimization problem. We summarize this procedure in Algorithm 3.AugPR φ (θ, µ, ν) = E Z∼D(θ) µφ * ℓ(Z; θ) -ν µ + µρ + ν . (H.For special choice of φ, the strong duality result (H.2) can be reduced to involving only a single dual variable. Now we instantiate φ-divergence as the Cressie-Read family:ϕ k (t) = t k -kt + k -1 k(k -1) , for k > 1.Like KL divergence, a distributionally robust performative prediction problem induced by a divergence from the Cressie-Read family has a dual reformualtion with single dual variable:DRPR ϕ k (θ) = inf µ≥0 (1 + ρk(k -1)) 1/k E Z∼D(θ) max{ℓ(Z; θ) -µ, 0} k * 1/k * + µ , (H.4)where k * is the conjugate number of k such that 1/k + 1/k * = 1. Therefore, an algorithm parallel to Algirthm 1 can be developed in a similar fashion based on the single-variable dual form (H.4).As a final remark, all of the theoretical results regarding excess risk bounds (see Proposition 3. In this appendix, we provide additional materials for discussion.Extension to Wasserstein distance. It is possible to use Wasserstein distance to define the uncertainty collection within our framework. Our algorithms can be modified to compute Wasserstein DRPO. For example, one can establish the strong duality of Wasserstein DRPO and develop an alternating minimization algorithm similar to Algorithm 1. However, the new algorithm involves an additional step of transport cost-regularized loss maximization due to the more complex dual form of Wasserstein DRO. For the corresponding theory, we expect that the square root of variance in (3.3) would be replaced by the Lipschitz norm of ℓ(•, θ PO,true ).Conservativeness of ρ cal and trade-off in selecting ρ. The main text covers the discussion of the conservativeness of ρ cal in two ways. Firstly, we show the trade-off in selecting ρ. For values of ρ ranging from small to moderate, DRPO outperforms PO in terms of performative risk (and similarly for worst-case performative risk). Conversely, for large values of ρ, PO is better than DRPO.There exists an "sweet spot" of ρ where DRPO yields maximal benefits over PO. This trade-off between DRPO and PO is demonstrated in any "vertical slices" of the left plot of Figure 1 (and similarly in the lines of the middle plot of Figure 1 for worst-case performance). Secondly, we show the performance of the calibrated radius ρ cal in the middle plot of Figure 1 , where the vertical bands indicate the calibrated radius ρ cal . Although ρ cal doesn't achieve the best possible worst-case improvement (which is an impossible oracle), it achieves a comparable performance, especially when η ∈ {0.8, 1.0}. This demonstrates the effectiveness of ρ cal chosen by our calibration method.Difference between TPO and TERM, and difference between DRPO and simple DRO. TPO (see Section 4.2 and Algorithm 2) differs from TERM [22] in that it takes into account performativity, whereas TERM ignores. To be precise, TPO minimizes E Z∼D(θ) [e αℓ(Z;θ) ] while TERM minimizes E Z∼D(0) [e αℓ(Z;θ) ], where D(θ) is the distribution map and D(0) is the base distribution. An analogous explanation applies to the difference between DRPO and simple DRO. TERM (or implicitly equivalently simple DRO) is ineffective in the context of this work's problem setup because it fails to account for performativity. Note that our methods are not doing DRO because the uncertainty set here depends on the model parameter θ. We borrow the idea of distributional robustness, but we have a fundamentally different problem at hand.Absence of small calibration set. The calibration set is not always available. Here we clarify the calibration set method and briefly discuss a possible solution when there is no calibration set. In the experiment of Section 5.3, we only need a small set of calibration data, which aligns with the regime of "weak group information". It is generally difficult to calibrate radius for uncertainty set and most distributional robustness related work only concerns the effect of increasing α and ρ. We do more to demonstrate that there are some practical calibration methods that work. In the absence of any calibration data, one can specify the radius by some prior belief. For example, consider D pop (θ) = γD major (θ) + (1 -γ)D minor (θ) as in Example 2.3. If one believes that γ 1 ≤ γ ≤ γ 2 for some 0 < γ 1 , γ 2 < 1, then one can upper bound the divergence D(D major (θ)∥D pop (θ)) ≤ -log(γ 1 ) and D(D minor (θ)∥D pop (θ)) ≤ -log(1 -γ 2 ). Further, one can choose ρ = max{-log(γ 1 ), -log(1γ 2 )} when using DRPO. However, this choice of radius could be conservative.Algorithmic convergence. The convergence guarantees of the proposed algorithms can be established on a case-by-case basis, depending on the specific "inner" algorithm or solver employed for solving performative risk minimization. Existing algorithmic convergence results for model-based PO solvers [26, 14] can be taped into our algorithms naturally. Moreover, empirical results in Section 5 validate the effectiveness of our proposed algorithms.Broader impacts. This paper presents work whose goal is to advance the field of machine learning, especially the subfield of performative prediction. Despite the development of new algorithms, their direct societal impact are limited to those outlined in the original paper on performative prediction [29] .The minority's performative risk is not 25% higher than that of the majority, as motivated by the four-fifth rule documented in Uniform Guidelines on Employment Selection Procedures, 29 C.F.R. §1607.4(D) (2015).Due to space constraints, we provide additional materials for discussion (e.g., limitations) in Appendix I. 
 
 Appendix:  


Decision: The paper revisits the performative learning setting in which the learner wishes to control the risk of a model over a test distribution that is sensitive to the choice of the model that is deployed. This is a novel niche topic but certainly an interesting and challenging setting that is connected to more well-known questions in ML such as covariate shift, lifelong ML or robust estimation. More precisely, the paper draws connections with distributionally robust optimization by studying methods to determine the worst-case performative risk over a set of distribution maps (that map parameters to test distributions) that contains the true distribution map.

While staying technically close both to ideas found in the original papers on performative prediction and to techniques originating from the distributionally robust optimization literature, this paper introduces novel ideas on a recent topic of interest which justify acceptance for the conference.

Reviews: review: paper_summary: paper_summary: Summary: The paper revisits Performative Prediction, a setting proposed in 2020 where the chosen model used to minimize a prediction loss also induces a distribution shift in the data through a distribution map. When the true distribution map is unknown, the learner must use a nominal map to approximate the change of distribution resulting from the chosen model, but this may result in large errors. Using a distributionally robust formulation of the problem, they propose a way to guarantee that the learnt performative optimum has bounded error (if the chosen radius is well calibrated). 

Overall, I believe the paper proposes good ideas and could be accepted. I have a few comments below, as well as some more minor ones about the writing. I will consider revising my score after the rebuttal.
strength_weakness: strength_weakness: Lack of discussions of the trade-offs / pros and cons. 

"Toy" experiments on simple models.

--


Major remarks:

* Overall, the paper is not too hard to follow despite a number of slightly awkward writing issues that I’ve listed further below. However I am missing a real discussion section that puts into perspective the chosen approach and the obtained result. I would like to see a conclusion with a take-home message. I think the problem of not knowing the true distribution map is important but the distributionally robust approach chosen here is only one way to resolve it that focuses on worst-case guarantees. I think this is best shown in the experiment section but there are not many comments on it. For now the “summary and discussion” is essentially a summary with some pointers to extra results in appendix. What are the pros and cons of such approach? How general is it when the family of distribution maps is more complex than a linear function? When should one use this approach? 

* Strategic classification example: Example 2.1 is a bit ill-defined because neither u nor c depend on \theta. In Section 5, it is a bit clearer as it is instantiated on a simple example (perhaps overly simple, is that common in this literature?). In the end the Kaggle data you cite is only used to estimate a base distribution but then all data is simulated, right? Figure 1 (left) shows that for a large interval of values of \epsilon_{true}, the performative risk obtained with the nominal map is actual lower than the distributional risk. I feel like the comment on this result l. 300-302 could be a bit expanded and insist on why this is typical for DR approaches. 



Minor remarks:

* Your introduction clearly went through a beautiful GPT pass: “Delving deeper into the formulations of performative prediction, the concept of a distribution map emerges as pivotal.” While I generally don’t mind GPT assistance, I think this sentence does not carry much meaning. I think your introduction fails to really convey the motivation for distributionally robust guarantees, and how they differ from other existing guarantees. The sentences are complex and convoluted (e.g. “Practically, the precise influence of a model on the data ecosystem is intricate and dynamic, making perfect specification an unattainable ideal.”). I’d recommend making a pass sentence by sentence and making sure that everything is said efficiently and simply.

* Related work: “[28] study the repeated distributionally robust optimization algorithm, which repeatedly minimizes the distributionally robust risk at the induced distribution.” -> repetition, use \citet

* “The radius ρ reflects the the magnitude of shifts”-> double the

* “The dual reformulation (3.1) will be served as the cornerstone of developing algorithms” -> will serve? also “cornerstone of developing”? not sure about this sentence either

* Section 5 did not go through the same scrutiny of spell checks / GPT: l 315: “indentified”, l.324: ”estiamte”

* Please correctly use \citet and \citep everywhere, cf https://medium.com/@vincefort/phd-lessons-part2-ce830329c86f for guidelines, copied below for your convenience:
“Once you have an entry in your .bib file for a paper that you want to cite, say the key is author2022paper, you have two major ways of citing it: within the text or as a parenthesis. You can set the within-text citation as “Following \citet{author2022paper}, we do …” and it will render as “Following Author et al. (2022), we do …”. The parenthetical citation is set as “… this has been shown in prior work \citep{author2022paper}” and renders as “… this has been shown in prior work (Author et al. 2022)”. Make sure to not confuse the two types, as it can be a bit confusing for the reader and impair the flow.”
questions: questions: What are the pros and cons of such approach? How general is it when the family of distribution maps is more complex than a linear function? When should one use this approach?
limitations: limitations: Experiments are on semi-simulations and use very simple model. 

There is little discussion of the challenges of this DR approach when distribution maps are more complex (non-linear), high-dimensional.
paper_summary: paper_summary: The paper proposes a framework that applies distributionally robust optimization to optimizing performative to obtain the distributionally robust performative optimum (DRPO). Specifically, the framework optimizes the worst case performative risk over the uncertainty set of distribution maps. The paper presents theoretical guarantees that bound the excess risk the approach as well as the benchmark approach. The paper also proposes tractable optimization algorithms for solving the distributionally robust problem and presents numerical simulations demonstrating the benefits of the proposed method.
strength_weakness: strength_weakness: The paper presents the distributionally robust optimization approach in an idealized setting where the form and structure of the distribution map is well defined and only a few key parameters need to be estimated. It would be more helpful to see how to arrive at this idealized setting from raw data. Overall, the paper could include more details about performative prediction to help readers understand how their approach fits into the bigger picture.

The paper's numerics and theoretical guarantees also do not allow readers to get a clear idea on how and if the distributionally robust approach improves excess risk. The theoretical guarantees while useful do not seem to necessarily be tight, so the improvement on the rates of the bounds does guarantee better empirical performance. Additionally, the numerics do not seem to study the excess risk metric (at least in the main body) which makes it hard to verify tightness of the theoretical guarantees and understand the practical benefits of the distributionally robust approach.
questions: questions: 1. The paper proposes two algorithms for the distributionally robust framework. Which algorithm is used in each of numeric examples and are there benefits using one over the other? Or is one algorithm just a special case of the other? 
2. Can more insight be shed on the differences between the two excess risk bounds (prop 3.2 and prop 3.3)? In what settings are the two bounds and subsequently the excess risk significantly different?
limitations: limitations: The authors adequately addressed limitations and potential negative societal impact of their work.
paper_summary: paper_summary: The paper addresses the performative prediction problem wherein the deployment of a model leads to a shift in the true data distribution via a distribution-shift map. In standard performative prediction, the distribution map is unknown - it is either assumed to be of a simple form like a location-scale shifting map, or estimated via a few deployments of models to see how the data is reacting. This paper proposes a distributionally robust performative prediction setting, where the objective is to minimize the distributionally robust performative risk (DRPR) which is the worst-cases performative risk over a set of distribution maps that contains the true distribution map. The uncertainty set is defined using KL divergence, and standard results from distributionally robust optimization (DRO) are used to obtain a dual form for DRPR. The paper then proposes to optimize the dual form of DRPR using an alternative minimization approach. The paper also proposes a simple calibration procedure to set the radius of uncertainty appropriately. The paper also proposes "tilted" performative risk minimization akin to the recently proposed tilted ERM (TERM). The proposed approach is validated via simulation on simple settings such as strategic classification with misspecified cost function, perfirmative prediction where the true distribution map is a linear location shifting functional.
strength_weakness: strength_weakness: - The theoretical results follow straightforwardly from existing results on distributionally robust optimization (DRO). The novelty is simply in bringing together the DRO framework and performative prediction.
- One of the steps in the proposed alternative minimization algorithm for DRPR itself is a performative risk minimization problem, which needs multiple deployments to solve. This means that the proposed DRPR framework needs even more deployments than standard performative risk minimization - it seems unrealistic for such an approach to work in a "real-world" setting.
questions: questions: - Can you try to extend the result on regularizing effect of DRPR beyond the toy example in section 2? It seems like this should be possible. 
- What is the effect of setting the parameter in tilted performative risk minimization to a negative value? It will be nice to compare this setting to the corresponding setting in TERM.
limitations: limitations: Yes, the authors have adequately addressed the limitations.
paper_summary: paper_summary: In this paper, the authors propose a new framework and algorithm for finding performatively optimal solutions in the performative prediction framework. Performative optima are in general hard to find, and to do so, a number of approaches start by trying to estimate the underlying distribution map: a task which incurs fundamental statistical or modeling error. The main contribution of the paper is that the authors bring to bear tools from the robust optimization literature to find solutions which explicitly account for this error and are provably robust to it. The main technical results of the paper are structural theorems bounding the performance of the distributional robust performative optima, and guidelines around the selection of hyperparameters for their algorithm. 

Disclosure: I previously reviewed this paper for ICML and I was disappointed that it was not accepted to the conference then. I thought it was a very strong paper back then and I think the authors have done an even better job now.
strength_weakness: strength_weakness: The paper has very few weaknesses, but to be somewhat nitpicky, I think that the authors would do well to clarify the computational complexity behind some of their algorithms and make precise statements regarding when and why the robust optimization problem can be solved, assuming that the non-robust (nominal) performative optimization problem is tractable. Please see below for further comments.
questions: questions: “L77: it is easy to see..” Aren’t there cases where the optimization problem is still computationally, if not statistically, intractable?

Assume that PR(theta) = E_{z~ D(theta)} ell(z, theta) is a tractable optimization problem. I understand that the mapping x —> exp(x) is a monotonic transformation, but could you provide a formal statement showing why one would still be able to tractably solve this modified version of the problem, assuming that the first version is tractable?

Could you spell out in more detail exactly what the grid search is over when you state that L270 “for general problems, these calibration methods necessitate a grid search….”
limitations: limitations: Yes, these have been discussed to the extend necessary.

Comments: title: Thanks for your reply, please consider adding these discussions in the paper
comment: Thank you for taking the time to review our work! We did not hear from you during the author-reviewer discussion period. Please feel free to talk to the other reviewers and the area chair during the reviewer-AC discussion period:)
Thank you for taking the time to review our work! We did not hear from you during the author-reviewer discussion period. Please feel free to talk to the other reviewers and the area chair during the reviewer-AC discussion period:)
Thank you for your kind suggestion:) We will properly incorporate the discussion of the first set of questions (pros and cons, etc.) into Section 6, as well as other discussions into Appendix I.
Thank you for your kind suggestion:) We will properly incorporate this reduction viewpoint into Section 4.1.
Thank you for your replies, I remain in favour of accepting this paper. Please consider adding some of these clarifications to the paper, in particular the first questions (pros and cons, etc.). I just feel like robustness is an interesting addition to Performative prediction but it comes at a cost, it has limitations, that would be worth discussing.
Thank you for the clarifications, stating out this reduction more clearly in the paper would be a good addition.