Tight Lower Bounds and Improved Convergence in Performative Prediction
Authors: Pedram Khorsandi
Rushil Gupta
Mehrnaz Mofakhami
Simon Lacoste-Julien
Gauthier Gidel
Venue: NeurIPS 2025 poster ()
Keywords: Performative Prediction
Optimization
Strategic Classification
Primary area: optimization
TL;DR: We provide tightness guarantees for RRM in two frameworks; present Affine Risk Minimizers using past snapshots to surpass RRM lower bounds and attain stability on broader problems; and develop lower bound derivation techniques for retraining schemes.

Abstract: Performative prediction is a framework accounting for the shift in the data distribution induced by the prediction of a model deployed in the real world. Ensuring convergence to a stable solution—one at which the post‑deployment data distribution no longer changes—is crucial in settings where model predictions can influence future data. This paper, for the first time, extends the Repeated Risk Minimization (RRM) algorithm class by utilizing historical datasets from previous retraining snapshots, yielding a class of algorithms that we call Affine Risk Minimizers that converges to a performatively stable point for a broader class of problems. We introduce a new upper bound for methods that use only the final iteration of the dataset and prove for the first time the tightness of both this new bound and the previous existing bounds within the same regime. We also prove that our new algorithm class can surpass the lower bound for standard RRM, thus breaking the prior lower bound, and empirically observe faster convergence to the stable point on various performative prediction benchmarks. We offer at the same time the first lower bound analysis for RRM within the class of Affine Risk Minimizers, quantifying the potential improvements in convergence speed that could be achieved with other variants in our scheme.

Tight Lower Bounds and Improved Convergence in Performative Prediction
Pedram Khorsandi Mila, Quebec AI Institute Université de Montréal
Rushil Gupta Mila, Quebec Al Institute
Mehrnaz Mofakhami
Mila, Quebec AI Institute Université de Montréal
Université de Montréal
Simon Lacoste-Julien' Mila, Quebec AI Institute Université de Montréal Canada CIFAR AI Chair
Gauthier Gidel"
Mila, Quebec AI Institute Université de Montréal
Canada CIFAR AI Chair
Abstract
Performative prediction is framework accounting for the shift in the data distri- bution induced by the prediction of a model deployed in the real world. Ensuring convergence stable solution- one which the post-deployment data distri- bution no longer changes-is crucial in settings where model predictions can influence future data. This paper, for the first time, extends the Repeated Risk Minimization (RRM) algorithm class by utilizing historical datasets from previ- ous retraining snapshots, yielding class of algorithms that call Affine Risk Minimizers that converges to performatively stable point for broader class of problems. We introduce new upper bound for methods that use only the final iteration of the dataset and prove for the first time the tightness of both this new bound and the previous existing bounds within the same regime. We also prove that our new algorithm class can surpass the lower bound for standard RRM, thus breaking the prior lower bound, and empirically observe faster convergence the stable point on various performative prediction benchmarks. We offer at the same time the first lower bound analysis for RRM within the class of Affine Risk Minimizers, quantifying the potential improvements in convergence speed that could be achieved with other variants in our scheme.
Introduction
Decision-making systems increasingly integral critical judgments in sectors such as public policy [Fire and Guestrin, 2019], healthcare [Bevan and Hood, 2006], and education [Nichols and Berliner, 2007]. However, as these systems become more reliant on quantitative indicators, they become vulnerable to the effects described by Goodhart's 's Law: "When a measure becomes target, ceases be a good measure" [Goodhart, 1984]. This principle particularly relevant when predictive models not only forecast outcomes but also influence the behavior of individuals and organizations, leading to performative effects that can subvert the original goals of these systems.
For example, in environmental regulation, companies might manipulate emissions data to meet regu- latory targets without truly reducing pollution, thus distorting the intended environmental protection efforts [Fowlie et al., 2012]. In healthcare, hospitals may modify patient care practices to improve performance metries, potentially prioritizing score improvements over actual patient health outcomes [Bevan and Hood, 2006]. Similarly, in education, the emphasis on standardized test scores can lead
Equul advising. Correspondence to Pedram Khorsandi; <pedram. kwwrsandioooaiiiii @mila quebec>
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

schools to focus narrowly on test preparation, compromising the broader educational experience [Nichols and Berliner, 2007]. These examples demonstrate how decision systems, when overly focused on specific indicators, can be manipulated, resulting in the corruption of the very processes they aim enhance.
Given these challenges, it is essential to develop predictive models that are only accurate but also robust against the performative shifts they may provoke. The work by Perdomo al. [2020] addresses this challenge within the frame- work of Repeated Risk Minimization (RRM), where they explore the dynamics of model re- training in the presence of performative feed- back loops. In their approach, the authors pro- pose an iterative method that adjusts the pre- dictive model based on the distributional shifts caused by prior model deployments, aiming to stabilize the model performance despite the con- tinuous evolution the underlying data distri- bution. By characterizing the convergence prop- erties their method, they provide a theoretical guarantee for the stability of the model per- formative equilibrium.
D(P)
Σ 016
PR(6))
Our work extends this framework by leveraging the datasets collected at each snapshot during the retraining process, introducing new class of al- gorithms called Affine Risk Minimizers (ARM). By utilizing historical data from previous up- dates, we show that it is possible to converge to stable point for broader class of problems that were previously unsolvable, extending beyond the bounds established in prior analyses [Mofakhami al., 2.23]. We derive [2023] and provide the first tightness analysis for the framework Perdomo et al. [2020] as well for newly established rate. Our method, which incorporates historical datasets, demonstrates superior convergence properties both theoretically and experimentally.
An example showing that using older snap- shots (purple) speeds up convergence to the stable point (orange star) compared to only latest snapshot (red). The implementation is provided in the code.
Figure 1:
upper bound under less restrictive assumptions than Mofakhami et al.
Converging to stable point is essential in decision-dependden learning systems. Without stability, iterative retraining may lead to persistent fluctuations, preventing reliable long-term predictions. Prior work has examined convergence rates and the range of problem classes in which iterative schemes achieve stability [Li and Wai, 2024, Narang et al., 2024, Perdomo et al., 2020]. This paper provides the first analytical techniques for examining the tightness of the upper bounds for these methods. In addition, we show that the ARM framework ensures convergence to a stable solution for a broader class of problems, mitigating the limitations of existing approaches.
Contributions. I We establish a new upper bound, enhancing the convergence rate of RRM under less restrictive conditions than [Mofakhami et al., 2023]; 2 We establish the tightness of the analysis both the framework proposed by [Perdomo et al., 2020] and our modification of class of algorithms, named
the framework from Mofakhami et al. [2023]; 3 We introduce Affine Risk Minimizers (ARM), that provides convergence for a wider class of problems by utilizing linear combinations of datasets from earlier training snapshots; 44) We provide both theoretical and experimental enhancements, showcasing scenarios where ARM improves convergence; (5) Finally, we present the first lower bound techniques for iterative retraining schemes and apply it both Perdomo et al. [2020] and our modified framework to establish thcoretical lower bounds for ARM, detailing the maximum potential improvement convergence rates achievable through the use of past datasets.
Related Work
Performative prediction introduces framework for learning under decision-dependent data [Perdomo al., 2020], and has been widely studied in various aspects, from stochastic optimization methods to

---

find stable classifiers [Li and Wai, 2022, Mendler-Dünnerr et al., 2020] to approaches that focus on performative optimal solutions. the minimizer of performative risk [Miller et al., 2021, Jagadeesan et al., 2022, Lin and Zrnic, 2024]. In this work, we focus our analysis performative stable solutions, whose deployment removes the need for repeated retraining in changing environments [Perdomo et al., 2020, Mendler-Dünnee et al., 2020, Jagadeesan et al., 2021, Brown et al., 2022, Mofakhami et al., 2023].
One of the main applications of this framework is strategic classification [Hardt et al., 2016] which involves deploying classifier interacting with agents who strategically adapt their features to alter the classifier's s predictions and achieve their favorable outcomes. Strategic Classification has been widely used in the literature of performative prediction [Perdomo et al., 2020, Mendler- Mendler-Dünner et al., 2020, Miller et al., 2021, Hardt et al., 2022, Mofakhami et al., 2023, Narang et al., 2024, Góis et al., 2025], and we adopt this setting in our experiments to empirically demonstrate our theoretical contributions.
Prior work in performative prediction either assumes the data distribution is a function of the parameters modeled as (()) [Perdomo et al., 2020, Izzo al., 2021, Drusvyatskiy and Xiao, 2022, Dong et al., 2023], or more realistically dependent on the predictions as in D(fe) [Mofakhami et al., 2023, Mendler-Dünne et al., 2022]. Although existing work only assumes one of these settings, our work adheres to both, by providing a tightness analysis of the rates proposed in Perdomo et al. [2020] and Mofakhami et al. [2023] and showcasing scenarios where we can provide an improved convergence by considering the history of distributions. To the best of our knowledge, we are first to provide a lower bound on the convergence rates achievable using any such affine combination of previous snapshots.
For the assumptions, adopt those in Mofakhami et al. [2023] and Perdomo et al. [2020]. While several works pursue performatively optimal solutions by assuming convexity over the performative risk itself, recent efforts such as Zheng al. [2024], Cyffers al. [2024] relax these requirements by considering non-convex objectives or weaker regularity conditions. In contrast, our analysis imposes no convexity assumption on the performative risk, relying only on convexity of the loss function to establish convergence guarantees.
Most related to idea of using previous distributions are works that study gradually shifting environments considering history dependence [Brown et al., 2022, Li and Wai, 2022, Rank et al., 2024]. Brown al. [2022] brought up the notion of stateful performative prediction studying problems where the distribution depends on the classifier and the previous state of the population. This is modeled by transition function that is fixed but priori unknown and they show that by imposing a Lipschitz continuity assumption similar to e-sensitivity to the transition map, they can prove the convergence of RRM to an equilibrium Eestributioncclasifiee pair. In our work, consider specific dependence on history, by using an affine combination of previous distributions, and show that this can lead to an improved convergence than prior work without imposing any additional assumption.
3 Performative Stability and RRM
In the context of performative prediction, two primary frameworks are commonly used to address the challenge of shifting distributions due to the model's 's influence: Repeated Risk Minimization (RRM) and Repeated Gradient Descent (RGD). Throughout this paper, we focus on RRM.
RRM iteratively retrains the model on the distribution it induces until it converges to performatively stable classifier. Formally, consider model fo F with parameters 0 O and a distribution Dff)
that depends on these parameters. The performative risk is defined as:
(R( (.))( (e(fo()),)) v)]
where (ffe y) is the loss function for data point 2 (x, v). A classifier is performatively stable it minimizes the performative risk on the distribution it induces:
Ops arg min BewD(fon))) ( [e(fo())) v)]
The RRM framework updates the model parameters by solving:
gc+1 = arg min B2-D(A)) [e(fo()),))
(3)
8EB
until convergence, i.c., t1+1 x 0².
3

---

Improved Rates and Optimality of Analysis
Both Perdomo et al. [2020] and Mofakhami et al. [2023] derive convergence rates for RRM under distinct assumptions. The assumptions made in these studies reflect the sensitivity of the distribution map D() to changes in the model and the structural properties of the loss function. Specifically, Perdomo al. [2020] focuses Wasserstein -eaersttei--bbeddddd sensitivity and convexity with respect to the model parameters, while Mofakhami et al. [2023] introduces a framework with Pearson x² x--baeed sensitivity and strong convexity with respect the predictions. Building these foundations and motivated by Mofakhami et al. [2023], we now outline the assumptions for our framework, which departs from Mofakhami al. [2023] only in Assumption 1 below.
Assumption C-sensitivity w.E.t Pearson X2 divergence: The distribution map D(fo). with pdf Pt maintains e-sensitivity with respect Pearson x² divergence. Formally, for any fa, for F:
((D(fo), D(fo)) & cl fo fo.113..
where
115o - Sor 11.00 = / [1.0(0)) fo (x)dx
A EF,
(5)
and
((D())) / (N (z) (=))) (
dz.
(6)
(z)
This assumption, inspired by prior work, is Lipschitz continuity on D(.), implying that if two models with similar prediction functions are deployed, the distributions they induce should also be similar.
Assumption Norm equivalency: The distribution map D(fo) satisfies norm equivalency with parameters C 2 and S C. For all for for, fo- F:
cllso
for 11fo 10-112- S Ci for 113a..
where
- - forl / [1fe(z) for (x))l p(z) dx,
(8)
and p(x) is the initial distribution, referred to as the base distribution.
The base distribution p(æ), following prior formulations in the literature [Perdomo et al., 2020, Mofakhami et al., 2023, Brown et al., 2022], corresponds to the pre-deployment data distribution. organic distribution is also consistent with
This interpretation of p(x)) as an intervention-free other areas of the literature. Schnabel et al. [2016] demonstrate this in the context recommender systems, where unbiased test sets like Yahoo! R3 are constructed to reflect user behavior prior to any algorithmic influence.
This assumption holds whenever the distribution map satisfies the bounded density ratio property. ie.. cPjs (x) S p(x) S Cp.. (x) for fo F. In such cases, one can define small constants : infe,r Piy (w)
We measure these constants in Appendix for our p(z) and C == supg,z x p(x)
Pta(z)
experimental setup in Section
Assumption Strong convexity w.r.. predictions: The loss function 9 + Elg. 8) is y-strongly convex. For any differentiable function f, for all y, U1, 92 E y::
((i1,)) v) 2 E(52.u) (01- ( Vil(o2.v)
2100 02ll
Assumption 4 Bounded gradient norm: The loss function {(fo(z), 4) has a bounded gradient norm, with an upper bound M supz,y, 0 (f (()()(())))))))))))))))()))))( (x).))l.
Building upon Mofakhami et al. [2023], we introduce a new theorem that demonstrates faster linear convergence for RRM, showing that stability can be achieved under less restrictive conditions.

---

Theorem (RRM convergence modified Mofakhami's framework) Suppose the loss ((fo(x); V)
y-sttrongly convex with respect to (z) (A3) and that the gradient norm with respect to fo(x) is bounded by M = x. ()L(Jo()); v) (A4). Let the distribution map D(-) be e-sensitive with respect to the Pearson x2 divergence (A satisfy norm equivalency with parameters C' 1 and c S C (A2), and the function space F be convex and compact under the norm -|I
Then, for G( = arg min Ez- (ff(lz) ((fo()))) y), with 2 = (x, v), we have":
BE0
llfG() - facoll I VeM llfe - for 1lso-
Y
By the Schauder fixed-point theorem, stable classifier Jops exists, and if JeM < 1, RRM converges unique stable point fops linear rate:
VCM ?
[e Sepsllsops
I[ - Sepellsens
This shows that RRM achieves linear convergence to stable classifier, provided that LEM Y < 1,
ensuring that the mapping is contractive and guarantees convergence. This result improves upon Mofakhami et al. [2023] by climinating the constant from the rate, as defined in Assumption Additionally, this approach
achieve improved rates of convergence, as discussed in Theorem 8, where we show how the new definition of c-sensitivity leads to faster convergence.
Despite these improvements, the following theorem establishes for the first time a lower bound under the given assumptions, indicating that the convergence rate cannot be further improved without additional conditions:
Theorem (Tight lower bound modified Mofakhami's framework) Suppose that Assump- tions 1-4 hold, with parameters e, M, and y such that JFM < 1. Under these conditions, there exists problem instance such that, utilizing RRM, the following holds:
Ie Sepill sops =
VEM 7
If instead VEM > 1, the bound is 9(1), indicating non-convergence.
This result establishes the tightness of the convergence rate under the specific assumptions outlined earlier, demonstrating that the bound cannot be improved without imposing more restrictive assump- tions. The full proof of this theorem can be found in Appendix D. A similar tightness analysis for the framework proposed by Perdomo al. [2020] is provided in the following section, confirming that both frameworks achieve optimal convergence guarantees given their respective conditions.
4.1 Tightness Analysis in Perdomo et al. [2020]'s Framework
In their work, Perdomo al. [2020] make set of assumptions that differ from Assumption 1-4. Their é-sensitivity assumption is with respect to the Wasserstein distance, and their strong convexity assumption is with respect the parameters. Formally, they make the following of assumptions to show the convergence of RRM
Assumption The distribution map + D(f) is c-sensitive wit Wi:
Wi (D D(O)) cll0 8'112,
the loss function - E(2 f) of the performative risk (1) is y-strongly convex for any z E Z and Vol(z 8)) is B-Lipschitz for any 0 E θ
Throouhoou this work, whenever refer fa(M), it denotes fg. where θ e G(Ø).
5

---

Under these assumptions and for &e < 1, Perdomo et al. [2020] showed that RRM does converge to a performatively stable point a rate:
Bc
100 - Opsl S
110 Opsll-
(10)
We note that c-sensitivity with respect to the x2 divergence (Assumption 1) is generally a stronger condition than e-sensitivity with respect the Wasserstein distance Wi, particularly when the input space has small diameter [Mofakhami et al., 2023J. While x² sensitivity implies tighter control over equivalent, and does not necessarily
the induced distributional shifts, the notions imply the other. Hence, each framework is analyzed under its respective assumption.
Theorem (Tight lower bound Perdomo's framework) There exists a problem instance and an initialization 0, following Assumption 5 such that employing RRM. we have:
((
4/3
110º 0psll =S
1100 - 0psl|
(11)
The proof uses quadratic loss {(z, 0) 211 2 21 and performative distribution Neee,, o?) satisfying e-sensitivity under Wi. Hence, the RRM update 0++1 ff matches the contraction
factor (e (e in Perdomo et al. [2020], confirming the bound's 's tightness. More detailed proof of this result is provided in Appendix C.
Our theorems show that given the assumptions in either framework, the convergence rate for RRM reaches a fundamental lower bound. This implies that further improvements in convergence speed novel optimization framework.
would require either more restrictive assumptions
In the next section, we present, for the first time, an approach that breaks the RRM algorithm class by exploiting data from earlier training snapshots, and thereby surpasses the established lower bound, providing improved convergence guarantees.
Usage of Old Snapshots: Affine Risk Minimizers
Instead of relying solely on the current data distribution induced by D(for), ), we leverage datasets from previous training snapshots (D(fo: ) The new scheme optimizes model parameters over an aggregated distribution:
0c+1 = arg argggin Biz, w) (((So(v), v)l BE8
(12)
where Dj is an affine combination of previous distributions, formulated as:
D. Σ a D(for),
a (6)
=1
(13)
1=0
We refer to this class of algorithms as Affine Risk Minimizers. As demonstrated in Appendix A (Lemma 9). the set of stable points for this class of algorithms coincides with those obtained through standard RRM. The following lemma formalizes the convergence of ARM under the stated assumptions, using only the average of the final two training snapshots.
Lemma (2-Snapshots ARM recurrence) Consider the class of problems for which Assump- tions 1-4 are satisfied, and let the distribution map D(.) be &-sensitive with respect to the base distribution within the convex function space F. Formally, for any fe, for E F,
((D((o)) < C llfo - fo
'Note that 2 convergence rate vacuous. In that case, performatively stable point may not exist.

---

where llfe ffo is defined in Equation 8. The distribution at iteration t is given by
D. - D( D(oo-1).
1
(14)
Under these conditions, the following convergence property holds for the iterative sequence generated by Equation 12:
v/3 VeM
[| for
mc
(15)
where m. max foe-1ll -1l, Ilfor-1 fll
The problem class defined here aligns with that in Theorem 2 for the case C' R 1. Now, the following theorem provides theoretical evidence of improved convergence, which will be further supported by experiments in Section 7.
Theorem (2-Snapshots ARM convergence) If (33 yeM
1, the sequence described in Lemma forms Cauchy sequence, converging stable point.
Relaxing the earlier condition VEM < the threshold v3 R 1.155, this theorem demonstrates modest but tangible improvement allowing ARM to breach the lower bound Theorem and shows stable point remains possible under
that when JEM the same conditions, contrast standard RRM, which does not converge. A detailed proof of this theorem, along with Lemma 1, is provided in Appendix E, where we show that the algorithm generates Cauchy sequence and converges the stable point. We prove the convergence for schemes that use the average of the last snapshots, for any but the best result is obtained for far.
V3 R 1.155 with C' ~ 1, convergence
In the following section, we explore the lower bound for the convergence rates achievable using any affine combination of previous snapshots.
6 Lower Bounds for Affine Risk Minimizers
We established the potential for convergence across wider class of problems using ARMs. This prompts the question of how much the convergence class can be improved, which we address in this section.
We propose the first distinct lower bounds for the framework described in Section 4 and that of Perdomo et al. [2020] for the class of Affine Risk Minimizers. The lower bound for our framework is presented in this section, while the corresponding result for Perdomo et al. [2020] is detailed in the following.
Theorem (ARM lower bound modified Mofakhami's framework) Suppose that Assump- tions 1-4 hold. Then, there exists problem instance in this regime, and for any algorithm in the Affine Risk Minimizers class, such that:
VeM ((11 7
))
llf fors Seps Qt
(16)
This demonstrates that the convergence rate for the class of problems satisfying Assumptions 1-4 cannot exceed the given lower bound.
6.1 Lower Bound with Perdomo et al. [2020]'s Assumption
show that the convergence rate for RRM provided in Equation 10 optimal among the class of Affine Risk Minimizers up to factor 2.
7

---

Theorem 6 (ARM lower bound Perdomo's framework) There exists problem instance and an initialization 8, following Assumption 5 such that for any algoritim in the Affine Risk Minimizers class, we have:
110 - -psl| = ((((()))
|100 0psl|
(17)
Proof Sketch. The proofs of Theorems 5 and 6 are inspired by the idea of introducing a new dimension each iteration by Nesterov's lower bound for convex smooth functions [Nesterov, 2014]. We construct problem instance satisfying Assumption 5 and derive the iteration dynamics of RRM establish lower bound its convergence rate.
We introduce a structured transformation of the parameter space, different from the one introduced in Nesterov [2014], using the matrix
0
0
0
A
0
E Rdxd
:
This matrix ensures that if a vector is in the span of (ci,..,,e:) where e, is the standard basis vector in Rdd, then Av extends the span to include 61+1- This property allows us to control the iterative exploration of dimensions in the distribution mapping.
We define the loss function as {(fo(z).)) = 2110 / == and set the distribution map to D(0) N/ (5 A0 + t1, o²) This choice ensures that each RRM iteration follows the update rule
g++1 (5A00- + +01)
From Lemma 9 (Appendix A), we know that any Affine Risk Minimizer converges the same set of stable points as RRM. Since the problem instance we constructed has a unique stable point, it
remains explicitly compute this point and derive lower bound by summing the contributions from
undiscovered dimensions, completing the proof. A detailed proof is provided in Appendix F. O
To further illustrate this, Figure 2 provides empirical evidence supporting the theoretical lower bound derived for Perdomo et al. [2020]. The figure shows the convergence of ||0 Ops|| over multiple iterations for various combinations of previous snapshots. As indicated by the dotted line, the lower bound is never violated, demonstrating that the theoretical result holds in practice. The experimental setup for these results is also detailed in Appendix F. We also extend our result more general case for ARM in the following theorem (with proof in Appendix F.I).
Theorem (Proximal ARM lower bound) Let Assumption 5 hold and generate the iterates via
g++1 arg min B(zaa) [((f(()) v)] 1 11,
(18)
BEE
where Dr is any mixture distribution defined in Equation 13. Then there exists problem instance and an initialization Go such that every algorithm in the Affine Risk Minimizers class satisfies
1 - 0psll Ops|l= =
((
<.3 2
|100 0rssl
(19)
The proximal ARM update in Equation 18 is the ARM version of the proximal formulation of RRM introduced by Drusvyatskiy and Xiao [2022]. In fact, the lower bound of Theorem 7 continues to hold for the standard RRM method, since RRM corresponds to the special case of ARM in which the mixture distribution D. places all its weight on the most recent iterate. Thus, this result demonstrates that the proof technique we have developed for establishing exponential lower bounds is not limited to the ARM family but extends naturally to other iterative decision -eeeednnnd optimization procedures. In the supplementary material, we also present convergence rates for Proximal RRM for the first time on the framework of Perdomo et al. [2020], filling a gap the literature, though these rates offer no improvement over standard RRM.
8

---

Bell
ARc (16.51
5.0
188
2012
16
24
40
48
(iterations)
t (tterations)
Figure 2: Convergence of |0t 0ps] over iter- ations t for different values of 7, which defines the aggregation of datasets from training snap- shots: D. Σ -i=t-r+1- (..)). The dotted line shows our lower bound from Perdomo et al. [2020], with c 2.49, 3 1, and y 5.0. The experiment, consistent across all methods, validates the bound by showing that | Ops does not drop below it, supporting our theory.
Figure 3: Loss shift due performativity for the credit-scoring environment. To accurately measure Performative Risk, average over 500 runs per method. Increasing the aggregation win- dow
2 4 + t/2 all) reduces the loss shifts and, consequently, reaches the stable point faster.
7 Experiments
We conduct experiments in two semi-synthetie environments to evaluate whether aggregating past snapshots improves convergence the performatively stable point. We present an empirical com- parison of different averaging windows for prior snapshots. At each time step t, we form D, by aggregating the datasets from the training snapshots as
Dr Σ D(for), 1-1-+41
where compare methods using various values of including 1,2, 2, and 'all' (which includes all snapshots up to time t).
We first discuss our evaluation metric, then present detailed case studies on the credit scoring environment Mofakhami et al. [2023] (Section 7.1) and the rideshare markets Narang et al. [2024] (Appendix J).
Evaluation Metric. Throughout our experiments, we focus on changes in loss a result of performativity. We define AR, i.e. the loss shift due to performativity at time t, as the absolute difference in loss observed by a model before and after the data distribution has changed due to performative effects while keeping the model's state constant.
AR, = DE [C[ (x), y)] EL-D(S ()(e(fo (x)), v)]l
(20)
This metric allows for clearer comparisons between methods by minimizing overlap in the plots, unlike the performative risk (Equation 1).
7.1 Credit Scoring
Setup. Inspired by Mofakhami et al. [2023], we use the Resample-if-Rejectel (RIR) procedure to model distribution shifts in controlled experimental setting. This methodology involves users strategically altering their data to influence the classification outcome.
Let us consider a base distribution with probability density function p and a function g: : ff(()) + g(fo(() indicating the probability rejection based on the prediction fe(x) IR. The modified distribution Pjo, under the RIR mechanism, evolves as follows:
Sample from p.
With probability 1- g(ff((()) (z)), accept and output Otherwise, resample from p.

---

Our data comes from Kaggle's Give Me Some Credit dataset', which includes features z E R' and labels y E {0. 1], where y indicates defaulting applicant. We partition the features into Two sets: strategic and non-strategic. We assume independence between strategic and non-strategic features. While non-strategic features remain fixed, the strategic features are resampled using the RIR procedure with a rejection probability ((fo(z)) [z) + 6. We use a scaled sigmoid function after the second layer. This scales (x) to the interval [O, - 5). ensuring that g g(fa(z)) E [ó, 1] remains valid probability, Further implementation details are available in Appendix I.
Theorem 8 Let fo(x)) E [0, 8) for all 0 E O, where 0 < 5 < 1 is fixed. Then, for g(fo(x)) = fa( + 5, RIR is e-sensitive defined in Assumption I with O $).
This result provides example where rate surpasses the rate previously derived in Mofakhami et al. [2023] (O(6-) 2) within the same framework). In addition, Mofakhami et al. [2023] derived the remaining constants in the rate for this setup, and these constants remain unchanged in our result. Furthermore, for any value of M and y, our rate can guarantee convergence for a wider class of problems. The proof of this theorem, along with justifications for the improved rate, is presented in Appendix H. Mofakhami et al. [2023] derive the
The outcomes of this study are shown in Figure 3. For larger window sizes (r), omit the initial iterations the figure because they follow the same update rule as smaller 7 methods, leading identical values. Figure 3 demonstrates the advantage of using older snapshots in the optimization process. As the window size increases from 1 to 2, we observe a near-half reduction in the loss shift, particularly in the early iterations, with the improvement persisting even after 50 iterations. While larger windows continue to reduce the loss shift, the marginal gains decrease as window size increases. This evident from the similarity between the curves for window sizes 1/2,, and 'all'. The decreasing marginal gains elicit a trade-off against the time, memory, and resource consumption. As the window size increases, both time per iteration and the memory consumption increase linearly. Thus, the user has to pick the right aggregation window based on the application and the resources available to achieve the desired convergence speed while respecting the logistical constraints. The corresponding performative risk plot can also be found in Appendix I.
Results.
8 Conclusion
In this paper, we introduced a new class of algorithms for improved convergence in performative prediction by utilizing historical datasets from previous retraining snapshots. Our theoretical contri- butions include establishing a new upper bound for last-iterate methods, demonstrating the tightness of this bound, and surpassing existing lower bounds through the aggregation of historical datasets. We have also presented the first lower bound analysis for Repeated Risk Minimization (RRM) within the class of Affine Risk Minimizers. Our empirical results validate the theoretical findings, showing that using prior snapshots leads to more effective convergence to a stable point. These contributions provide new insights into performative prediction and offer alternative approach enhancing learning in dynamic environments.
Acknowledgments
This research was supported by the Canada CIFAR AI Chair Program and the NSERC Discovery Grants RGPIN-2023-002 resources provided by Caleul Quebec (calculquebec. ca) and the Digital Research Alliance of Canada (alliancecan, ca), which enabled part of the experiments. Simon Lacoste-Julies is CIFAR Associate Fellow the Learning Machines Brains program. We also thank António Góis and Alan Milligan for their valuable feedback, which notably contributed to this work.
and RGPIN-2025-05123, We gratefully acknowledge the computational
'Give Some Credit Dataset, 2011: http://wwwgg....ce//////aaaaaaaa
10

---

References
Gwyn Bevan and Christopher Hood. What's measured is what matters: Targets and gamingg in the english public health system. Public Administration, 2006. https://doi. 1t1.1/.111.0111111///......1
1467-9299.. 20w..0000000000 00600.x.
Gavin Brown, Shlomi Hod, and Iden Kalemaj. Performative prediction in stateful world, In AISTATS, 2022. https://proceeding/ mlr wwwpp//eiie//rooriiiiee http:///gg.......rrr/s///////ora
html.
Edwige Cyffers, Muni Sreenivas Pydi, Jamal Atif, and Olivier Cappé. Optimal classification under performative distribution shift. NeurIPS, 2024. https://openrreveww net/ nermffrrm?id- 3J5hv05UaW.
Roy Dong, Heling Zhang, and Lillian Ratliff. Approximate regions of attraction in learning with decision-dependent distributions. In AISTATS, 2023. attps://procaedingg mlr. m.r.press/ v206/dong233 html.
D.C. Dowson and B.V. Landau. The fréchet distance between multivariate normal distributions. Journal of Multivariate Analysis, 12(3):450-455, 1982.
com/
Dmitriy Drusvyatskiy and Lin Xiao. Stochastic optimization with decision-dependden distributions. http://..orrr/....////ooooooooo
Mathematics of Operations Research, 2022.
www. 2022. 2022.1287.
Michael Fire and Carlos Guestrin. Over-optimization of academic publishing metrics: observing Goodhart's Law in action. GigaScience, 8(6):giz053, 2019. https://ddi.org/1///
gigascience/ginn giz0053.
Meredith Fowlie, Stephen P. Holland, and Erin T. Mansur. What do emissions markets deliver and to whom? evidence from southern california's 's nox trading program. American Economic Review, aeaweb. org/ wttp://rriceeeid=111 1257//es 102.2. 0.2.2.965.
2012. https: //wpw..//www..// wwwp::wwwwwww..ptpptwwtwwwwww...
António Góis, Mehrnaz Mofakhami, Fernando P. Santos, Gauthier Gidel, and Simon Lacoste- Julien. Performative prediction on games and mechanism design. In AISTATS, 2025. https:
//proceedings mlr. press/v258 v258/ gowsgoa..aaet....
/atpa//////////ii2..a.aas html.
Ziv Goldfeld, Rami Pellumbi, and Kia Khezeli. Lecture 6: f-divergences, In ECE 5630: Information Theory for Data Transmission, Security and Machine Learning, 2020. https://people.ec. cornell. edu/ wdw/eivg/
Letttoreeeture6e6_____ .df.
C. A. E. Goodhart. Problems of Monetary Management: The UK Experience, pages 91-121. Macmillan Education UK, 1984. https://dol https://abb.orr//0...o
1007 100110079999 /ttp://0.100//7781--339-11111111 wtt//o.//.../....ooo
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classificatto... In ITCS. Association for Computing Machinery, 2016. https: http:///ooo..oo/1.11.4....31 2840730.
Moritz Hardt, Meena Jagadeesan, and Celestine Hondler-Dünner Performative power. In Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, NeulPS. Curran Asso- ciates, Inc., 2022. httpss//proceeedings new.eeeeeeennnneneneeeeeeeeeeeee neurips cccpaper__aaeeeeeeeeeeeeeeeeeeee wiwes/ httee///pper//22//ieeee 90e73f3cf Ptt.aa442222222///02222eeeeeeeee ConfrrCee .pf..
Zachary Izzo, Lexing Ying, and James Zou. How learn when data reacts your model: Perfor- mative gradient descent. In ICML, 2021.
mlr, vttvv/1/////2221..//
html.
Meena Jagadecsan, Celestine Mendler-Dünner and Moritz Hardt. Alternative microfounda- tions for strategic classification. In ICML, 2021. https://proceedings mlr press/v139/ jagadeesan21a html.
Meena Jagadeesan, Tijana Zrnic, and Celestine Mendler-Düinner. Regret minimization with perfor- mative feedback. ICML., 2022.
html.

---

Qiang Li and Hoi-To Wai. State dependent performative prediction with stochastic approximation. In AISTATS, 2022. https://prooceedings. mlr. wtt...persss//1/2222e. html.
Qiang Li and Hoi To Wai. Stochastic optimization schemes for performativv prediction with noncon- /9252.
vex loss. In NeurIPS, 2024. http::///earrrrss.cc///ttaa/////
Licong Lin and Tijana Zmic. Plug-in performative optimization. In ICML, 2024. https:// proceedings mlr.
Celestine Mendler-Dünner, Juan Perdomo, Tijana Zmic, and Moritz Hardt. Stochastic optimization for performative prediction. In NeurIPS, 2020. https://prooeeedingg. hew.eeeddddnnnnnenn...e... neurips seurips.cccpapee... cc/paper files/
pdf.
Celestine Mendler-Düinne, Frances Ding, and Yixin Wang. Anticipating perforatiiiyyyy by predicting from predictions. In NeurIPS, 2022. https://ddi acm. wwt..oorg//////ooo http:///0..555/00000000066666660
John P Miller, Juan C Perdomo, and Tijana Zrnic. Outside the echo chamber: Optimizing the performative risk. In ICML, 2021. https://prooceedings mlr prosss///v13///1111e12... html.
Mehrnaz Mofakhami, Ioannis Mitliagkas, and Gauthier Gidel. Performative prediction with neural networks. In arxiv, 2023. https://araae prggabs//304.....
Adhyyan Narang, Evan Faulkner, Dmitriy Drusvyatskiy, Maryam Fazel, and Lillian J. Ratliff. Multiplayer performative prediction: learning in decision-dependent games. JMLR, 2024. https: //www, //wwrjjml...... wwtg/pppers./eeeeeee http:/pppps/olmmeeeee/
24tpeee2//22222222002222 0131. pdf.
Yurii Nesterov. Introductory Lectures on Convex Optimization: Basic Course. Springer, edition, 2014. https://dl. acm. org/doi//ni 255.5/000005555500222....
Sharon L. Nichols and David C. Berliner. Collateral damage: How high-stakes testing corrupts apa. org/record/
America's 's schools. Harvard Education Press, 2007.
2007-03254-003
Frank Nielsen and Kazuki Okamura. On the f-divergences between densities of multivari- ate location or scale family. Statistics and Computing, 2024. https://doi. org/10.1007/
s1 a11222-0233 11-22-023-1073--11
Juan Perdomo, Tijana Zmic, Celestine Mendler-Dinner, and Moritz Hardt. Performative prediction. In ICML, 2020. https:/
mlr. http://111/peedoo20eaa.. hhml.............mmmmmmmmmmm....
Ben Rank, Stelios Triantafyllou, Debmalya Mandal, and Goran Radanovic. Performative rein- forcement learning in gradually shifting environments, 2024. 09838.
Juliusz Schauder. Der fixpunktsatz in funktionalraümmen. Studia Mathematica, 2(1):171-180, 1930.
https://doi. http::://doooor/11000/
org/10. hetg//..4044/sae 20004/sm22-00 170-1800
Tobias Schnabel, Adith Swaminathan, Ashudeep Singh, Navin Chandak, and Thorsten Joachims. Recommendations treatments: Debiasing learning and evaluation. In ICML, 2016. https:
//proceedings... mlr prres/v44/schnseee html..
Xue Zheng, Tian Xie, Xuwei Tan, Aylin Yener, Xueru Zhang, Ali Payani, and Myungjin Lee, Profl: Performative robust optimal federated learning, 2024. https: //ta://///xi../// wwwpsiivvoorg/aeeeeeeeee mtrg/bbs/2411 18075.
12

---

A Auxiliary Lemmas and Technical Results
Lemma (Expectation of a Gaussian Weighted Exponential Function) Let x N(1, o I) Then the expected value of exp
-
given by:
E
X
exx
|x|
exp
|
1 0²
H 02 ( 2
2
20
0z)
Proof:
The expected value is expressed as:
E
x
exp
2e
|
Rm
xexp
(-1 1| |x|(²)
(-
2e
(2TO2)
exp
(-
20 ||x 1012?
1
dx.
Merging the exponentials:
exp
1 1 e e
2
+ o²
||x|2 +
x2x²(11
o²
1
exp
(- ||al|1
20
Completing the square yields:
[ 1 exp ( 2
1
1//22
1²)
12)
|
x
1 +
exp
20²
1
02 (
+ +
Since the integral is over Gaussian distribution with mean term, we obtain:
n/o" +
after multiplying by the constant
1 =exp exp
(-1ke]1²
(1
1
#
E[x exp
2n 2=22
2c
02
Lemma (Young's Product Inequality) Let a, b 2 0 and let p,q be conjugate exponents, i.e. 1. Then
ab < a 1
which, as a result, one can derive,
(a+ S 2a² 2b?
Lemma 4 (Bound on Chi-Square Divergence for Convex Combinations) Let and Q and R be probability distributions on R. For any a E [0, 1]. the following inequality holds:
(aP (a (1- a.), aQ a)) a²
[x² x RQ)
We begin by expanding the chi-square divergence using its definition, followed Young's inequality.
Proof:
followed by applying
(ap(x) + (1-a)r1a ( da
(1-P+((-a)la) (1- a)
og( + - (1-a))(r))
2 000
(p(z) - g(x))2
ag(x)) + (1 air dx
(p(x) - x(x)))
+ +a² a)) / (p(x) - q(x))²
((x))
< 3
dr r(x)
(xx)
(by convexity of for positive x)
< <a'x3 Q) + 2a a)x R) + +2) (Q, R)
(by Young's inequality Lemma 3 on the last term)
13

---

Lemma 5 (Inverse of an antisymmetric of a Jordan Normal Form Matrix) Let A E Raxd be defined as:
0
0
1
0
1
1
0
and let bl - cA be an invertible matrix where ; S and A is as defined above. Then the inverse of
(bI cA) applied to e,, the first standard basis vector, has the following form for large d:
1
== (bl cA)
1
L cL
C - 1)
Moreover, the below is:
Σ l (())
for d 2 2T when large, and t S T.
Proof: The matrix A has the following form:
0 1
00
0
0
1
A
Thus, (bl cA) takes the form:
0
0
0
-
We continue by computing the inverse of the lower triangular matrix with diagonal entries d1, Ag...., bay...,Aa Ya and subdiagonal entries of -1 as shown below:
A
0
0
1
A2
0
0
0
0
-1
X
N/
3
1
A3
:
A x .
x
x and subdiagonal
Using the formula above (diagonal entries \ 1. A2 entries of 11) the inverse of bi cA will have the form:
b
1
Ad
b
0
-)
0
c
11
1)
1)-d -d
1)-2 22
( - 11
14

---

Now, applying this inverse to the vector e. where = [1 0
0]", we get the following:
(bT cA)-14 1
33
L cL
[ 1)-4
Sum of the entries from index to d is:
Ev-
v. cL
+1 -1) (
+ -1)-0
1=1
This is geometric series. The closed form of the sum is:
d Σ
b 1 -)
()-(d-++1)
v.
cL
1)
1=t
For large d 2 2t and
1, this sum be approximated by the leading term:
Σ
d
-1)- -1)-
b
vi
R
cL
11-1
i=1
Thus, applying the inequality sum:
I x for all x < 1, we obtain the following lower bound for the
T-1
Σv: = Ω cT ( (9))
Lemma Let N( En) and Nu E2) be two multivariate normal distributions with means Py H2 Rd and covariance matrices E,, En E Raxd, The squared I-Wasserstein distance between these distributions is bounded by:
S ||4 2 22 WP(N(H, E,), (u,, Ex))
This expression bounds the Wasserstein distance between two multivariate normal distributions, as shown in Dowson and Landau [1982].
Lemma Let NH, Σ) and N (H E) be two multivariate normal distributions with means My E IRd and a shared covariance matrix E E Rdxdd The -d-divergence between these distributions is bounded by:
x2 2), E)) = 1 - -() 'I (1--1 u2)) < 5 (1) -12) 1Z m2).
This provides the -ddivergeecee between two multivariate normal distributions, as shown in Nielsen and Okamura [2024].
Lemma 8 Any projection proj(-) from Rd into any convex set C TRd is continuous function.
Proof:
To prove that the projection is continuous, we need to show that if Fn - IRd then proje + (r))
Let y/ = (rr) and y (x) Since yn C and yo. minimizes the distance Fn, have:
|| ynll I || vll for all n.
15

---

As - 2, the right-hand side 1| - yll + || - yll, and thus || - yn is bounded. Since the sequence {yn } is bounded and lies the compact set has convergent subsequence you + By the continuity of the distance function, we have:
2 5l lim |
Unu.
As y proje(r) minimizes the distance from to C, it follows that ÿ y, and thus yr y- Therefore, (T.) + (x)) proving continuity.
Lemma The set of stable points for any method in the class of Affine Risk Minimizers is equivalent the set of stable points for standard RRM.
Proof: Consider the mapping for an affine risk minimizer using the last 7 iterates, defined as:
G0 0
(0-1)= = (6', 8'-1_ 0 0
where
0f = arg min [((ff(())))))))))) 1)l.
At a stable point, the mapping satisfies:
(0', 0--1 0-- = (0',0-11 0
which implies that:
0f = 0 = -.. 0 A: We now show that every stable point for this mapping is also stable point for the standard RRM mapping, defined as:
G(O
From the definition of D., we have:
D. Σ
( D(0') 1) 0
since Ei11, 0g
(1) = 1. Therefore:
8¹ arg min E.-.D [e(fo()). arg min ((())))))_)(((((())))))))))))))) otgp::00000000aaammmm.moooooe1a0 BE
G(0
implying that any stable point for G, is also stable point for G.
Conversely, if 0t 0--1 stable point of G, then iterating the mapping G, times yields the sequence:
g++1
similar argument shows that this stable point satisfies:
g++ arg min E D (( arg min EZ-D., [e(fo(z) BEB
BEG
because:
HT--1
Di+:
Σ
(1) a
D(0') D(
Which leads to,
G- g++1 .....,
1........7)))) 0l+)) (0'-1 lr ..... l'tt-11
showing that this stable point is also stable for Gr.
Thus, the set of stable points is equivalent for both mappings.
Lemma Let a real number with 0 < a < 1. Then for every integer 2 0,
[1/2]
1
2 (2
16

---

Lemma 11 Let A1 and A2 be two probability distributions and let B1 and B2 be another two probability distributions. Then, we have
A A
B
+
B2
x²
Sx²(A1. B1) + x B2).
2
Proof:
To compute the X2 divergence between the averages A and B B2 we start with the
definition:
((())tp) (a)+to"
x2 Ai
A2
B1 + 13
dx.
2
2
pp(
Simplifying the numerator, we get:
1
(pf()) pz) P2 (x)) dx.
(z)) + P 12 (z)
Applying the inequality (a b)2 < 2n² 212,
further bound this follows:
1 2(p) (x) ( (x)) (()) P2 (x))²
dx.
p (x) (z) p2 (2)
-00
By distributing the terms, this becomes:
(nf(x) (f
+ (x) - (x)) pf(x) p (z)
dr.
(f(x) + (x)
Now, since P (x)
( and p I
ppa we can split the integral as follows:
(wf(z) (x)) pf + (p)(2) - (2)) dr.
By definition the x² divergence, this final expression is equivalent to: x22, B1) + x² (A2, B2).
Thus, have shown that
x² A
Aq
B1 + B2 S 5x2(AI, + x2 B2),
2
which completes the proof.
Lemma 12 Let 17 fato fa(o-- Suppose the function space F is convex, and
e'ee G(0) arg min E2 (f( (x),
where = = y) Pfo represents the distribution induced by the model fe. and is continuously differentiable loss function. Then the following inequality holds:
TV V ((Foree)()) v) Ps. (2) 2.0
Refer to Mofakhami et al. [2023] for the proof.
Lemma 13 Suppose a nonnegative sequence (at) satisfies the recurrence
a++1 S max(ae, 0t-1)
for all and some 0 <EST. Then for every integer &. 2 0, one has a. [1/3) max(an, a1}-
Proof: Set = max(ag. 01). We proceed by unrolling the recursion in pairs:
02 CA, ag max/az, a1} < cA, a4 S max/as, a2} < 2A, ... and general, each two steps introduce least one additional factor of e, yielding the claimed bound.
17

---

B Proof of Theorem 1
The proof of Theorem 1 largely follows the approach in Mofakhami et al. [2023]. To facilitate readability, we have restated the common parts from the proof Mofakhami al. [2023].
Fix and in O Let F R and F - be two functionals defined as follows:
h(1z)) F ((A))) = ())ss
(21)
/ ((Ta(#). (z)dz
(((aa) Fe
(22)
where each data point z is pair of features x and label y.
For a fixed 2 = (I, y). due to strong convexity of {(fo(x), y) in fo(x) we have:
(z)) (aao)-((ffoorrr (z)(()))))))) 2 (faro (x) - fa(r) ()((fo(()(x)..)
=1loocoo( [x)0)
(23)
Taking an integral over a w.r. Pfe(s); and knowing that (|Sa(e) Sa(en)?, J (I) (c we get the following:
(f (Jc(o(()) (((e))(1)) (t)
MJG())) h(Sa(1) 2
7 |l f..
(24)
Similarly:
h(faw))) - h((c()) 2 (ʃ (F - fa(o)(2)) (e (1))
+ 2 | - 10
(25)
Since Sa(0) minimizes h, the following result can be achieved through the convexity of the function space, (Lemma 12):
I (Javo)()) (x)) (s) 2 0.
(26)
Adding (24) and (25) and using the above inequality, we conclude:
- -cren 2 2 (Jacosoo) - (x))) T V Vgl(Uarer(a) (27)
This is key inequality that will be used later in the proof.
Now recall that there exists M such that M = supx.v.0 |/ (VL((o(())))) v) and the distribution map over data is e-eesiiive w.r. Pearson x² divergence, i.e.
(D((f)) < ell fo 11?
(28)
18

---

With this in mind, we do the following calculations:
If (Ja()) (x)) (o)) ( Vol / (Jc(e)(0) Sa(o)(x)) T ( ( (z)dz
= -I/ (Focos(t)) [x))) " (o (pso Pso (z)) dz
2 / (Faros(t)) - (z)) ( (z) pso (2)) dz
M / [[ (2)
(pts (1)
pso (z)) dz
M / [[acee(()) (x))
Pro Pro(z)
- Psg (z)
Pro (z) dz
(2)
M/ / (x) (1)))
Pfo Pf)(2)
Pfo (z)
Pro (z)dz
(2)
Cauchy-Schwand Tneq
(x(o (
$
(2) 2 (/ (P/b()) (Plol))-P(o(x)
M
Pso (2)d2
Pso
-)) - fawells (D D(fo))
(+) comes from the fact that [f fz)dxz s fff(()) and the Cauchy-Schwaan inequality states that [E[X|] /E[X?]][Y?) conclude from the above derivations that:
I/ (1))))(w)) (()))) (1)) V (o / (Vcco(()- (c(o)(x:)) V (1)) (z)dz
$ Milff - facerlls v (D D(fo)).
(29)
Similar to inequality (26), since Sarer minimizes hi, one can prove:
f (f(1o)()) (Favo)()- (x)) (y((fcio((4) (z) 2 0.
(30)
From (27) we know that f (foro) fa(o) (x)) v v=((fa(or(())))))) (z)dz is negative, so with this fact alongside (29) and (30), we can write:
f (fc(o)()) - fa(er) (x))
(31)
Combining (27) and (31), obtain:
yllfar fato Ml (
(28) M (x3(D(fo), <
VCM life - forll
+ [|fa(() - faomlls &
(32)
To prove the existence of fixed point, we use the Schauder fixed point theorem [Schauder, 1930]. Define
u: U:fE arg E ((f(x))
PEF 2~D())
For this function, U(fo) fa(0)- So instead of Equation 32, we can write:
[[(()))) u(fo < VeM Il for 11.0
(33)
Using Assumption derive the following bound,
(v
VeM Il - forl
[U(()) u( =
(34)
7
19

---

This inequality shows that for any fa, F, nim llfe. fe, O, then lim [f. Uff )ll 0, which proves the continuity of u with respect to the norm ||-II. Thus, since continuous function from the convex and compact set J to itself, the Schauder fixed point theorem ensures that 2/ has fixed point. Therefore, fors exists such that fa(()) = S0p.
If set Ops and 0' 0f for Ops being any sample in the set of stable classifiers, know that G()) = Bps and G(Ø") = 8" So we will have:
VEM ll Sops Topsllsops"
|s fops roos
(35)
Thus,
VEM
VEM
Sopsll Fops S
Sops 1lpp
11J00
-Jees fops
(36)
Note that Equation 36 applies to any stable point. Suppose there are two distinct stable points. faps and foz.. By the definition of stable points and using Equation 33, we have:
VEM
-U(op = -llopg - -Sopylls
11obs - Sops lops'
Under the assumption that VEM 1, the inequality above ensures that faps Sope and the stable point must be unique. Thus, Equation confirms that RRM converges a unique stable classifier a linear rate when JEM < 1.
'I is important clarify that fabs fuz, does not imply Vr foz. (x) Soz (x). Instead, it indicates
that [lops S0zg 0.
20

---

C Proof of Theorem 3
In this section, examine the tightness of the analysis presented in Perdomo al. [2020] by considering a specific loss function and designing particular performativity framework. We focus on the loss function {2,, 0) = 3 e =11 which is y-strongly convex with respect to the parameter 0 and its gradient w.r.t. 0 is 3-Lipschitz, aligning with the assumptions stipulated in Perdomo et al. [2020].
We model performativity through the following distribution: 2 ~ NN(O,, o²) According to Lemma the 1-Wasserstein distance between two normal distributions upper bounded by:
W Wi(N of), (12, of)) I V(ni 22)² - e| - -021
it follows that the distribution mapping specified is e-sensitive, as described in Perdomo et al. [2020]. Under these conditions, the RRM process results in the following update mechanism:
0++1 - (
This arises because:
B² 2 -30= +
0- = arg min ((0)))))(( 0]] arg min E 2(01)))
27
0 302 arg min 2 02 BeBg 3 0
arg min D(r)
2
8 2
This progression directly corresponds to the upper bound suggested by Perdomo et al. [2020], confirming that the analysis is tight. No further refinement of the analytical model would mean faster convergence rate for the given set of assumptions as detailed in Perdomo et al. [2020].
21

---

D Proof of Theorem 2
We define the model fitting function as fo 0, and the corresponding loss function is:
1 2y /1f6(2) M proj 10 (x)
((x,
where projj. |- denotes the projection onto the surface of a ball with radius 0.95. By setting 0 E θ {= ||=|| < 0.05 min A/ ) ensure that the gradient norm remains smaller than M. Since the loss function y-strongly convex, satisfies both Assumptions 4 and 3.
Throughout this proof ||0 82ll = fl.fe. - seall for any choice of 6'.
We define the distribution mapping follows:
D(0) -N
N (N 1
The diverreee between two distributions D(01) N(,, o) and D(02) N(u,, σ), where H1 = Veli and μ/2 = Ved2, with o = 2. is given by (Lemma 7):
(N((,, Nu2, 2)) S (u p2) x (μ) u2) ==|001 - 02112 =ellfo, - foz 11?
Thus, the x² diveeregee hetween the distributions bounded by <l|0: - 02112 making it e-sensitive according to Assumption 1. Note that
With this set up one would derive the update rule:
MM IR [proo(())) +
M erf
2E [x]
g++1 proja
proje
v22
Using,
2x
erf
2 x
Vx S 0.05,
1/2
and given that [[x] Vel- < 0.05 min
(EM
1 by the definition of θ the condition holds.
MM [x)]
proje (AMve g²
g
proje
Assuming we start with 0 in the feasible set and operate in the regime where MVE < 1, the projection into the feasible be omitted. Therefore, we have:
M
VE
0c M
00
is clear that 0 is the stable point in this setup, so:
110 Ops/l = =5 (0(((M))
(MVV
In other words:
ll.o Sape Illops = Ω [MvE
((VVE
For the case where Mye > 1, the projection remains constrained to the surface of the ball O, preventing convergence to the stable point.
22

---

E Proof of Lemma and Theorem 4
This proof is heavily inspired by the proof of Theorem I in Appendix B. We start by restating the stronger assumption that was added in Lemma and that implies other standard assumptions for this paper.
Assumption 6 e-sensitivity with respect to Pearson x² divergence (version 2): The distribution map D(fo) maintains c-sensitivity with respect to Pearson x² divergence. For all for for E F:
(((())) - ج 1lo Sorl1?
(37)
where Il fo defined in Equation
Note that, Assumptions 2 and 6, imply Assumption 1:
((D(O)) S Ellf - for 11? S ell5o - -sor 10011
Following the methodology described for Theorem 2 in Mofakhami et al. [2023], we begin by defining the functional evaluations consecutive time steps as follows:
(f() = EEnD (C(f. 2) = ((fg:))p(2)) dz,
ht (fa) EuwD. 1( =]] (()a-1)) (z)dz,
where pz(2) denotes the probability density function of sample 2 from the distribution Dz.
Utilizing the convexity of & and Lemma from Mofakhami et al. [2023], following the line of argument Equation 17 of Mofakhami al. [2023], we establish the following inequality:
-1 - for / (fo for
for (x)) - V Vgl(for(T), v)p((z)
(38)
where [] Sec 12,, represents the squared norm, calculated as:
1s So lp-
(z)) (ol
and p(()) = Ei=0 Pfa-- (Ir), Using the bounded gradient assumption, we deduce:
I (fo- (x) (x)) T (=)
-Mllfo+t forlop (2(D,,Dr_i)
(39)
Now combining equations 38 and 39 we get,
yllfom - for ll. S M V (D,
(40)
Note that Equation 40, is a direct consequence of Assumptions 3-4, 6, and doesn't 't rely on definition of D, (refer Equation 32 for the proof). other words, we define our method the mapping
u(So. Sa..) = arg min Bie, DC fo..) [E(((r), v)l.
fEF
where D(fe, ... fo..) Σn EE_D( D(Se.) then.
711 ... - USe; for Ml, S M ... fo.), D(Se; -oo,)))) (41)
So.)
where, Ps probability density function of distribution D(fe, ... fe.). We use this information further on in the proof.
The remaining task is to bound the x divergence. Start by defining:
D.
D(fa-.)
23

---

Which implies:
Dj n1 - D. Dfo=)) and Di-1 - D(for a) n --
D.
Now, using this one can derive:
(D)) (D((o) D(fo-n))
+ 2 - (D(()o))) D.) + ())()))))) D.)
(by Lemma 4)
(D(o))) ((for-))
+ ( n2
(D((()r), D(So-1))
71
+
(-)
1
x (D((or)))) D(Sor-nt.))
(Proposition 6.1 of Goldfeld et al. [2020], convexity of f-divergence w.r.. its arguments)
C 33
fl for-a|1
1 ) m-1
Σ
11 - 112-
+
2 E |
Σ
11ae-n
for-n4al12
(by e-sensitivity)
m 6 )( 1) + mm )
a-
Σ 1 =mm m
2(n 1)(2n 1)
n? +
3n
1=1
where mf maxosicnnllsee flloo---- - f1 Which further gives us,
em?
4n2 + 5
(D)
C
3n2
And in conclusion, derive the following bound:
VeMma
4n2
6r + 5
I| foc
VCy
3n2
Using Assumption we further obtain:
Cl - Soc 10.1 = c (x)
C n-1 / - (fol))))))
(42)
M - Sor 1o 2 11 so
Substituting this back into the previous inequality, finally get:
VeMma
4n 6n + 57
[|
(43)
7
3n2
24

---

Note the n = 2 minimizes the bracket above amongst the integers. 6 Continuing with n = 2, we have:
v3
VeMms
for
(44)
2
Convergence to a Stable Point. establish the following bound:
By expanding the max term in Equation 44, using Lemma 13, we
L1]
v3
VEM ?
If for
fu,
2
with fo = max fo
l1 Ilfo - foo Combining this inequality with Lemma 10 and assuming
VEM < 4433, 2
obtain:
v3
(3VEM
- Se c
fo.
(45)
2
Where c v3 VEM
For clarity, let a
V3
2
vENS )
rresuuting in:
[lfarix
forl] Σ fl fociell S fa fool
Σa
= 2a 1 11-a=-1
(assaming a<1))
a²
1- Ilfo - fooll
S 2 1 I-aa
1fo: - -fool.
Notice that the right-hand side of this inequality independent of k. With a
(
v3 yEM
1
for any d >> O, there exists > 1 such that for all m t, fl foe || < 8. Thus, the sequence is Cauchy with respect to the norm || ||; and by the compactness (and therefore completeness) F, converges point f*.
To show that f* is stable point, we start by showing the continuity of the mapping
U(Jn S0,) arg min D(a,))-((ee ((([())))))
JEF
where D(So, soz) = Dífe, D-D(ee) Applying Lemma 11 and Assumption 6, we obtain:
2
+ (D D(fo foz)) S (D +x ((((o) W Illmm - 1o; & Sogl13
E
Combining this with equations 41 and 42, we derive:
7 [ Soz) U(So Jo: )112 <
Soz): D(Jo; So;))
(46)
SeM2 Soz 112 + 1l Soz 112)
Thus, for any sequence lim,, (fog, Sog) foz),
eM2 72 (1lfoz for 112 + |15oz foz1l
lim [[] fog) - fo=)) lim
This implies that if lim (for foz) (for, foz). then lim |e](Fog Sog) U1 (for fo=)1 )| 0.
By the continuity of U, we conclude:
lim for+1 lim U(for for-1) u t-sac
lim for, lim fo-1) u(f" (-250 10000
This establishes that f fop is stable point.
"We can derive a convergence guarantee for any n. The values of n < 5 yields a bracket of S 1 and thus can match or improve the class of convergence compared to just the last iterate. For larger rt's, s, we still have convergence, but smaller class of functions the bracket >
25

---

Proof of Lower bound in Perdomo et al. [2020] Framework
In this proof, we begin by considering a loss function defined as follows:
{(2, 0) 7 110
8 22 7
(47)
This function is y-strongly convex for the parameter and its gradient with respect to is 3-Lipschitz in sample space. The necessary assumptions the loss function, outlined in Perdomo et al. [2020], are satisfied by this formulation.
We define the matrix A within Rdxd as:
0
0
1
0
A =
1
1
0
The critical property of this matrix is that if a vector b The key property of this matrix is that if vector b E spanfe; S t), then Ab E spanfe; i S t + 1), where each e₃ Rd is standard basis vector with all coordinates zero except for the i-th coordinate, which is 1. This structure enables the introduction of a new dimension only the end of each RRM iteration. With the correct initialization, this ensures that the updates remain within a minimum distance from the stable point due undiscovered dimensions.
We define D(0) as the distribution of given by:
2 N
(~ A0 + o1,
Note that since spectral radius A is 2, the mapping D(-) defined as above would be e-sensitive. Under this setting, the first-order Repeated Risk Minimization (RRM) update, starting with 0g = e1, is described by:
Ø++1
( A0' + +e1)
Due to the properties of matrix A, we conclude that g--1 E spanfes Vi S +t+1). The stationary point fss of this setup is located at:
- Ops 2 21 EA)
e1,
Note that at time step & the best model within the feasible set is 0r span(e; Vi < t). Given that one can conclude that the best Li-distance to stationary point achievable at time step t is lower bounded by the sum over the last d t entries of 0rs. Setting d 2T and using Lemma 5 we get
(
EB 27
1|0 0ps
Similar to Repeated Risk Minimization (RRM). the Repeated Gradient Descent (RGD) method introduces new dimension in each iteration step. Specifically, the gradient update rule RGD is given by:
Ea-D(nn) Vol(z, 70" + A0 +ei).
This formulation ensures that each step effectively augments the dimensionality of the parameter space being explored only by a single dimension. Consequently, the lower bound established for RRM also applies to these RGD settings.
26

---

F.1 Lower Bound for Proximal RRM
We proceed to use the exact same setup as Appendix Keeping in mind that the only changing factor here would be the optimization oracle at each step of RRM. Consider the general case of
0++1
arg min [(z, y)-n, [((fo(a), a) + 2 110 2 w A50
1101
(48)
2
2
with Dj defined as:
Dj = Σ a D(fa.) s.t. Σ a =1.
(49)
1=0
Now given that the loss is strongly convex, the minimizer retrieves unique point according the mapping:
1
0++1
X + (BL v)~ [z] + X04)
(50)
Same before, using Lemma 9, search for the stable point using the standard RRM update rule, which in this setup would be the following:
ac+1
+ (5 + e1) + 20²)
This update rule for + oc would retrieve the stationary point Ops.
7 w 1 B
Ops-
e1
Note that again, because of the structure of matrix A, Equation 50 can introduce a new dimension only after taking one step of RRM. Therefore, the best method any method in the ARM class can do is to only match the first coordinates of the stationary point. So Li-distance to stationary point achievable at time step is lower bounded by the sum over the last d entries of 0ps. Setting d 2T and using Lemma we get
conclude that the best
1|0º Arsll =Ω
e
+ w) )
27

---

G Proof of Lower Bound for Modified Mofakhami et al. [2023] Framework
We define the model fitting function as (x) 0, and the corresponding loss function is:
Mx. 0) 2 750(2) M(1 ö)ze 2 ||]l|
This loss is y-strongly convex, ensuring unique minimizers and stable convergence properties. Additionally, we assume
{=|||=]| v ? J. ensuring that the gradient norm || M(1
5M
5)re 1 ||ll remains bounded by M. This holds because the mapping f(z) re 1| is chosen such that, f R + [0, 1].
Observe that, for all foo, So, fo E F, we have 110 0011
0'1 = 115o for so-:
[.fo(()) - for (x)]1 Pse. (2) de / 110 0'112150 (x) do = 110 0
[1 for 1..0
We define the distribution mapping follows:
D -N (v
02E
61
0.021)
AO
L
where is a lower triangular matrix:
0
0 0
1
1
A
0
Matrix A has the property that if 6 is in the span of {ei,..., e.), then Ab will be in the span of ( 1i+1). J. Here, e; denotes the standard basis vector, where its i-th element is and all other elements are O. This makes crucial for ensuring that each update step involves interactions that span progressively larger subspaces.
The x- diveergee between two distributions D(01) NN1, Σ) and D(O2) = N E), where M1 = de AO + L and μ2 = 122 0ee A0' + 51 with Σ = I² according to Lemma 7:
=v
1 0²c A) A) - -2112.
(N Σ), (p2, Σ)) $
2 (11 42) U2) -12
TI 7 - m2) = 0² (1
2
Since the spectral norm of matrix 2, we have:
(D())), D(62) S c|l0 = cl15o for 11s..
Thus, the >i-divergence between the distributions is bounded by <ll0 - 01112 ensuring that the divergence scales with the difference between 0 and 6'_
The update rule for 0 is:
g++1 proje
M (1 8)E
De + [|==]]]]
7
M (1 8) exp
||[x]]| 202
E E[r]
proje
This is the unique minimizer the loss function due to the 7-strong convexity. Additionally, this is continuous mapping from compact convex there exists stable fixed point, denoted as Ops. satisfying:
itself. By Schauder 's fixed-point theorem,
8ps = proja Mcc2200s (1 6)E[[] = -proja
M Mco.00ps (1 (1-8)
( (/2
ABps + 61 21)
))
28

---

|B|o|]1
)
1-
where Cp2,8ps
2n²
S
Assuming
I Mye 1 and
v2
we get that,
+1
2
61 Mco (1 6) (v² A0 +
Mca2 (1 1 2
o2e
Mc MCps,0ppl (1 6)
6)
A0 +
7
I.
7
12(1 --)0psll + M(1 - 8)
7L
2 (1 5)6 + M(1 8)
1
7L
Choosing I, 2M(1-8)
7(6-32) guarantee the term in the projection operation would have norm
smaller than 8, i.e. it would be θ So you can drop the projection operation from the equality above.
Thus, the stable point would hold true in the following equality:
Co2,0ps Vo2cM
G1
0Ps
I -
A
V2
7
L
The same assumptions stated above would allow us use Lemma
110 0psll =Ω ((1-0) Co2 Ups
VoRcM
V2
To lower bound Cp2,0ps. we note that ||[[>]|| E [0, 5 + 7(6+54) and minimize the exponential term with respect to o²:
2M(1-6)
||||||
1
exp (-c5),
20
Where > 0 is constant independent of 6. Setting
v 2
to maximise of and lim & - 0, we
achieve:
( 1 7 )
||0' - 0rsll =
Hence,
= )
vCM
for fors 1lspps =Ω (
29

---

H
Proof of Theorem
Consider a feature vector z divided into strategic features 2, and non-strategic features 2,, so that ( We resample only the strategic features with probability g g(fo(r)), representing the probability of rejection for x. The pdf of the modified distribution pso is:
Pro (r) = p(x) (1 - ((f=((((()))) + J. pla', x1) (e), p(a,))
where the integral is over all possible values of x', with xy held constant, since only the strategic features are resampled. The first temn represents the option that accept the first sample at æ; the second term represents the possibility that we reject the first sample at x' (x',, Byy and then resample at I, to obtain x well.
Assuming the strategic and non-strategic features are independent, we can rewrite this expression as:
Ps. (1 s(fo(=))) + / o' =x, e(fo(x')) p(xx)dz', #/
-p(o)((- / g(fo(1 (x)))x, (2 f)x, (r,)da's
- o(fo(z))) [ (ox(
(51)
= =p(z)(1-
= p((x) (1- ,(fo(1))) [ (Uxo="")xxxxxx))
= p((x) (1 (L=)(((()))++++ Co(zy))
where px, and px, are the marginal distributions the strategic and non-strategic features, respec- tively, and we define:
Co(og) = -f px. ( xy)) de',.
Since 0 < fe(x) < - for some > 0, follows that s g(oo(t)) S 1 for every x. Therefore, 8 S Co( S1
In the RIR procedure, the distribution of the label y given æ is not affected by the predictions so for every (z, we have Pso (z) Pfo (x)p(y(a) for any fo- This results in the following equality:
x ((D(O)) (p (z) Psa (2))
(p (x) P1)(2)))
dz
dx
(
Dfo (1)
We prove that this mapping is e-sensitive with respect to x² divergence, where 1 (1+ 1- d
2V8
/ (p (x) - (x)) dr
)
(T)
- -or dr
/ p(x)² [fo(x) - for (C)()
fo(x) (
- 1 / p(x) (fo(x) - for (x)) (Colz,) - (x)
- 2ff((x)) - fo (x)) (Co(Ts) Ca( do
This inequality follows from the fact that 8 Co(xy) and s(fe(x)) 2 0. therefore [=gte) < 4 Continuing, have:
30

---

= = (fo(=)) for (x))² dx
+ / px, (Co(t)) (Co((z)) (o(())) dx,
px, (Cx(t)) - -or( [ px, (x.( - So (x)) dee drg
/ p(x) (fo(1) fo (x)) dr - I (ool)) dxy
8
$ / p(z) (fo(x) - for (z))² dx
This comes from the fact that Say px, (=)) So (o "1)ddr' =C((o)) (x)) We use equation 51 to replace p(æ).
1 + (o) (z) dx
= =
-
1
10. + 1 /
- (focz) for (z)) dx
Cauchy Schwarz I
Il forl3. + 1
( Co(x dx) (f (fo(x) - for (x)) dx
(foo))
1 <
5 fl for 11,0 + Px (()0)))) (al (( so do)
1/2
1/2
Since (x)( is bounded random variable in [ö. 1], its variance is less than (1-6)² according to Popoviciu's inequality. Also since for any 0 E @ we have fo(x) S we can infer [ (x) - for (x)] S
1 f1 -o
1
(ʃ p(xx) (fo(x) for dx
1/2
1 I forl17.
1-6 8
(f (fplt) (fo(z) -
1/2
for (x))
dx
1- 8
$ forl1
llfe forll
28
From Appendix A.3 in Mofakhami al. [2023], we know that I1.o Sor S 31150 - Ser 117, Hence,
(((()) - ( 1
1
1 1-6
llfo for 17.
2/8
Rate Improvement Arguments: By using Assumptions 4 and 6 from Mofakhami et al. [2023], it be shown that the method is Ce-sensitive defined in Assumption 1. Specifically,
(( s ellfe 1 Cellfe
1
In this case, our rate aligns with the rate from Mofakhami et al. [2023], demonstrating that in all cases where their rate holds, our approach offers least an equivalent or faster rate. However, there are instances where our rate results in smaller constant than C'e. As outlined in Appendix A.3 of Mofakhami et al. [2023], the same RIR framework derives C = } under Assumption 2 and e = 1/ with respect to Assumption 6, yielding Ce = _े We show that instead of Ce = _t. we
obtain 1/2 (1 + 2v8 which is strictly smaller for any < 1. This shows that this rate is strict improvement over Mofakhami al. [2023].
1-6)
31

---

1.73xx10
1.734x10-2
10732x10-2
PR(G))
1,73x10-
1.728x10" 10
10"?
1.724x
1.722x10
1.72x10-2
16
24
32
40
48
(Iterations)
Figure 4: Log performative risk for the credit scoring environment across the RRM iterations. The numbers the plot are averaged over 500 runs. Increasing the size of aggregation window 7 from 1 + 2 4 + t/2 + all reduces the oscillations in the risk and converges the same point. Note that the plot starts from iteration 5 for better readability as the initial risk values were very high.
I Performative Risk for Credit-Scoring
Figure 4 shows the log performative risk for the credit-scoring environment. This metric has been adapted from Mofakhami et al. [2023]. Figure further substantiates our claims as we see lower oscillations in the risk for larger aggregation windows. We also note that although larger windows yield more stable trajectories, they can incur worse performative risk along the way before ultimately settling. Furthermore, methods converge to roughly the same performatively stable point-an as predicted by the theory unique stable point in Lemma 9 since the difference in log performative risk at the end of 50 iterations is negligible between all methods. However, as pointed out in Section 7, all methods oscillate in a similar range, thus hindering the readability of the plot.
Hyper-pan parameters. For our experiments, we fix the value of å 0.55. The RRM procedure is carried out for maximum of iterations with learning rate of 3e-4 and Adam optimizer run over A100-40G GPUs. Each run only took few minutes. Further, all the experimental results and plots are averaged over 500 runs, where each run for each method has the same model initialization. Thus, the only source of randomization is the sampling under RIR mechanism, where the sampling changes across different runs but is the same for the methods given a specific run.
32

---

-4.4
+4.3
PRUPd (1a3)
4R.
-5.6
-6.0
9
15 18
12 ((Reeration)
18
20
(Iteraation)
Loss shift due to performativity
Performative Risk
The plot shows loss shift due to performativity and performative risk across the iterations for player in the game between two firms. The values in the plot are means over 200 runs. Increasing the aggregation window size leads to lower loss shifts even in this simple game and hence, faster convergence than just relying on the dataset from the current timestamp.
Figure 5:
Revenue Maximization in Ride Share Market
Setup. This is two-player semi-synthetic game between two ride-share providers, Uber and Lyft, both trying maximize their respective revenues, Each player takes an action in this game by setting their price for the riders across 11 different locations in the same city of Boston, MA. The price set by one firm directly influences the demand observed by both firms. The demand constitutes the data distribution and at each time step, total of 25 demand samples are sampled for a firm i, and the optimal response is found by minimizing Equation 53 for a maximum of 40 retraining steps on CPU. Each run took only few seconds. The simulations use the publicly available Uber and Lyft dataset from Boston, MA on Kaggle'.
Notations and Equations. Let = 1,2 denote the two firms in the game. Inspired by Narang al. [2024], each firm i observes demand z; that depends linearly on the firm's price x; and its opponent's 's price x as follows:
z, =
A x A
~ (Z 1)
(52)
where Zbase the mean demand observed at each of the 11 locations, as measured the kaggle dataset. Each demand sample is vector of dimension 11.
A; and A are fixed matrices representing the price elasticity of demand, i.e. the change in demand due to unit change in price for the player and (opponent) respectively. We introduce interactions between the ride prices by making A matrices non-diagonal. Additionally, note that the price elasticities Aj will always be negative as the firm will experience less demand if it increases its price. Similarly, the price elasticities A-j will be positive.
location and the demand in a different location within the same city
Each player observes a revenue of 2 "; Thus, the loss function that each player i seeks to minimize in the RRM framework can be described as:
arg min BEjnD, 2 X;
x
(53)
where À a hyperparameter for the regularization term (= 70 for our experiments). For any player i, each element of is clipped to be between the range of |-30, 30) and the initial price xf is sampled randomly from a uniform distribution on [0, 1].
Results. Figure 5 shows the plot for loss shift due to performativity and the performative risk versus the iterations averaged over 200 runs. For this plot, we assume player the player who makes the predictions and adjusts to the performative effects introduced due to the actions of player 2. It can be clearly observed that as we increase the aggregation window from + - + 1/2 + all, we
UUer and Lyft dataset from Boston, MA, 2019: Attps://www.ket kaggle. com http:///g.....ttaat/////////s/// wtt.m///aattttt///llaa/a
uber- and lyff--tttte dataset- sesttasst--ootto-aa boston-ma
33

---

mostly lower loss shifts and hence, an improvement in the convergence rate. Since we start at random price value, taking the past into account in the beginning makes the algorithm worse but the effect is neutralized as the data from more time steps is observed. Given the simple linear nature of the problem, this is significant improvement and provides evidence for our claims about using the data from the previous snapshots. Secondly, performative risk plot in figure 5 also highlights that all methods converge to points having very close values performative risk, with the methods having larger showing oscillations with smaller amplitude.
34

---

K Proximal RRM Convergence in Perdomo et al. [2020] Framework
Theorem 9 (Proximal RRM Convergence) Suppose the loss {( ()=;0) is 3-jointly smooth and y-strongly convex. If the distribution map D(-) is e-sensitive, then
x + 10 ob?
G(Ø) arg min B [[(2;0)
(54)
+
2
we have, for all 0, 0' E O,
cB cB
|G(0)-G(O)) &
10 0'1--
7
Furthermore, if cB-> < 1, then G a contraction, possesses unique fixed point pps, and the 7+x proximal RRM iterates oet1 = G(O+) converge linearly:
[33 (x ) 10u - pplll
|10 - Ppsll S
Proof. Fix O and f'. Let
(()) (1) + + 110-011 -Ip, f'(d) Ez-D(or((;;0)=
2 110' - dlI
Because (();)) is strongly convex, both f and f' are (7 + A) A)-stronyly convex. Hence
f(G(0) H(G())) 2 (G(0) - G(O)) (of(G(()) 7+} |[((8) GI (55)
((((') - f(G(0)) 2 (G(0') - (())) T (G(()) Since f is minimized at G(O), the inner product in 56 is non-negative. Combining 55 and 56 yields (G(0)- - G(OD)) Vof(G(()) I -(7 +
7 |[((0') - G( (56)
2
(57)
Define the regularized loss
A 110 011
(o(=;)) = ((2;0) +
2
The map
2 - (G(0) - G(O)) V G((((=;((0))
B B||G(0) G(
is 1-Lipschitz in a because of the 3-joint smoothness of l. The e-sensitivity of D(.) then implies
sup [())((])(>))) E. B()D())(())) se110 0'|].
(58)
iss 1-Lip
Using the 1-Lipschitz function above in 58 gives
(G10)-((0)) -( (E Valo(z; G((') VLN S c|0- 0'11.
Unfolding bg and rearranging, we obtain
- - I((0)) - -
- -0'
(59)
Since G(1') minimizes f', we have (C())-C(()) T (of(G(()) 2 0. Thus - - cc - 0'll (( - G(H)) s (G(f)- - G( Vvf((((()
+ + G |10 1 0'l
(60)
by the Cauchy- Sluchy-Schwarzznneee inequality. Combining 59 and 60 gives
(-eß a) ||0 0'1 [|G(0) G(O')I < (G(O) C(O') T Vof(G(0)).
(61)
and substituting the upper bound 57 for the right-hand side yields
(-cB3 - >) ||0 - 0'll (G( - G( V -(7 + A) [[((() 12
(62)
Since [[G(0) - [ 2 0, dividing both sides of 62 by (7 + ()) - - gives
cB +
||G(0) G(O')l <
7 + 10 0'|
(63)
35

---

Stability of the Proximal RRM Solution in Standard RRM
We examine whether the fixed point of the Proximal RRM introduced in Theorem 9 coincides with the performatively stable point of RRM.
Assume that < 1, Under this condition, a performatively stable point of RRM exists and it's
unique. Because the proximal term vanishes at é Ops. optimality of Ops yields
E D(Ops) (2;)rs) I BEwD((Ps) ((2 RewD((Ps) {(=; + 110ss - 201 Ap.
Hence
X 2 10ps ~1
0ps
arg min D(0 {(z; Φ) +
(64)
so 0ps is also a fixed point of the Proximal RRM.
Note that, for any À > O,
cB S
3 + X 7+
1
S
(65)
By Theorem 9, inequality 65 guarantees that the Proximal RRM admits unique fixed point, denoted by 0gg. Since ps satisfies 64 and the minimiser of 64 is unique, we conclude
O2s 0ps.
Thus, under oB <1, 1, the performatively stable solution of RRM identical the unique fixed point of the Proximal RRM.
36

---

L Limitations
Despite our contributions, several limitations warrant discussion. First, although we prove that ARM achieves performative stability under a broader set of sensitivity conditions than standard RRM, this does not necessarily translate into faster convergence rates. Second, while the underlying techniques can extend to other iterative schemes, such as Repeated Gradient Descent (RGD), and more general gradient-based methods, we do not provide explicit convergence analyses or lower- bound characterizations for these alternatives. Finally, our entire treatment assumes deterministic, non-stochastic setups with exact access to full distributions; we leave the problem of accommodating sampling noise and stochastic gradients for future work.
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We provide support for all the claims made in the submission.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in Appendix L.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
38

---

Justification:
All the assumptions required are prescribed in the main text.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The experimental setup to reproduce the results for both experiments provided in the Appendix and I.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
39

---

Answer: [Yes]
Justification: Code will be provided in the supplementary material. Link to the public datasets used throughout the experiments is provided in the text.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
Sabllii/guides/ooeeStiieee ios.oddeeoobmssssoooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https: /CodeSubmiiise //n /nips. ctaps.cc/public/gut htt.iiiiiigidddeeddduuuuiiiiiiia combbbmsssiinnn ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Details are provided in the Appendix and I. Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Because the methodology requires linear memory overhead, couldn't 't retain the intermediate data needed for error bars, and since variance grows with more steps, demanding an impractically large number of runs mitigate, we report only mean trends.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
40

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Details provided in the Appendix and
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https::/ //teurii///urrps....
Answer: [Yes]
Justification:
Our paper follows NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
[NA]
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
41

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Original owners of the experimental setups used in the paper referenced.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
42

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
43

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https / :00te//eeeeeeeeee///22////////// for what should or should not be described.
44


Reviews:
[{"review_id": "5tyOTtcjxy", "reviewer": "Reviewer_6Knm", "summary": "The paper introduces a new class of algorithms for the performative optimization problem. Theoretically, the proposed method not only matches their shown lower bounds but also improves upon the performance of existing Repeated Risk Minimization (RRM) approaches. Numerical experiments are provided to demonstrate the practical effectiveness of the method.", "questions": "Q1: In Assumption 2, what is defined as the \"initial distribution\"? \n\nQ2: Also, for Assumption 2, is this assumption common in the literature of PO or for applications? Could the authors provide some settings satisfying the assumptions? \n\nQ3: How are alpha's in (13) specified in Lemma 1? Will any arbitrary choice of alpha_i^(t) work in this case?\n\nQ4: What if the distribution map is misspecified? Will the algorithm still work given some misspecification error?", "limitations": "NA", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nS1: Introduce a new algorithmic class, ARM, with a better convergence rate than existing RRM.\nS2: Theoretically show upper bounds of the proposed algorithm class, matching the provided lower bound and breaking the lower bound for existing RRM.\nS3: Numerical experiments are also included to show the performance.\n\nWeaknesses:\nW1: It would be better to further interpret the assumptions, especially Assumption 2, including whether they are normal in the literature or some specific examples satisfying the assumptions.", "was_revised": true, "final_justification": "Thank you for your notification. I am satisfied with the authors' response, and all my questions are resolved. So I still keep on the positive side.", "rebuttal": "We thank the reviewer for the detailed feedback and the positive assessment of our algorithmic, theoretical, and empirical contribution. We answer their questions below.\n\n> **Q1 (What is the “initial distribution” p(x) in Assumption 2?).**\n\nThe initial distribution is the base distribution 𝑝(𝑥) introduced in Eq. (8), identical to the reference distribution referred to as the base distribution in Mofakhami et al. (2023) and the baseline distribution in Perdomo et al. (2020). Conceptually,  𝑝(𝑥) corresponds to the pre-deployment or organic exposure distribution—i.e., the distribution of inputs before any model intervention occurs. This notion is also standard in the recommender systems literature: for instance, Schnabel et.al. [1] use the Yahoo! R3 dataset, which provides an unbiased test set where a subset of 5,400 users was each shown 10 randomly selected songs to rate. Since the songs were chosen uniformly at random, the resulting test data is Missing Completely At Random (MCAR), offering an intervention-free ground truth. We will clarify this in the final version.\n\n[1] Schnabel, Tobias, Adith Swaminathan, Ashudeep Singh, Navin Chandak, and Thorsten Joachims. \"Recommendations as Treatments: Debiasing Learning and Evaluation.\" ICML 2015.\n\n\n> **Q2 (realism of Assumption 2 and discussion on assumptions).**\n\nWe will include a dedicated paragraph in the revision discussing the assumptions in greater depth. All four assumptions are directly inherited or adapted from prior work in performative prediction—specifically, Mofakhami et al. (2023) and Perdomo et al. (2020). In particular, Assumption 2 is structurally identical to the norm-equivalence condition introduced by Mofakhami et al., who also derive explicit expressions for the constants in our RIR experimental setup: namely, $C=\\frac{1}{\\delta}$ and $c=\\frac{1}{2-\\delta}$ for $0<\\delta<1$. This connection is currently mentioned briefly in Appendix H (line 726), and we will expand on it in the final version. We will also include additional discussion in the appendix outlining some conditions under which Assumption 2 holds in practice. In particular, it holds if the possible densities have common supports with a lower and upper bounded ratio; then we can use something like $c:=\\inf_{\\theta, z \\in support} \\frac{p_{f_{\\theta}}(z)}{p(z)}$ and $C:=\\sup_{\\theta, z \\in support} \\frac{p_{f_{\\theta}}(z)}{p(z)}$.\n\n> **Q3 (choice of alpha in Lemma 1).**\n\nWe use uniform weights over the final two iterations $\\alpha^{(t)}_{t-1}=\\alpha^{(t)}_t=12$ (Eq.14).\n\n> **Q4 (What if distribution map is misspecified?).**\n\nOur analysis focuses on RRM and ARM, which do not query the distribution map \\$D(\\cdot)\\$ but instead rely on empirical datasets collected post-deployment, assuming access to an (infinite) sample. While we do not address the misspecification from finite sample sizes in this work—particularly for ARM—this issue has been previously analyzed in the context of RRM by Perdomo et al. (2020).\n\n\nWe hope these clarifications fully resolve the reviewer’s concerns, and thank you again for the constructive review."}, {"review_id": "ohS5HFfEll", "reviewer": "Reviewer_n4o8", "summary": "The authors study repeated risk minimization in the context of performative prediction, where a deployed model influencens the data-generating distribution. Repeated risk minimization converges, under certain assumptions, to a stable state at which the chosen model is minimizes risk on the distribution it generates. In other words, the model is a fixed point of the risk minimization operator.\n\nThe paper presents tight upper and lower bounds on the the linear convergence of repeated risk minimization under two different sets of assumptions from prior work, one by Mofakhami et al. (2023) and one by Perdomo et al. (2020). Both sets of assumptions require strong convexity of the loss and the property that a small model change can only lightly affect the resulting distribution (called sensitivity of the distribution map). In addition, certain gradient norms have to be small. \n\nThe two sets of assumptions differ in how distance in distribution space is measured, and what norms are bounded, leading to incomparable and complementary convergence guarantees.\n\nIn addition, the authors study a new class of algorithms, affine risk minimizers, that use previously encountered datasets to speed up convergence.", "questions": "Minor comments:\n\n- There may be a typo in Equation 5 in the definition of the subscrip to the norm. Should it be f_\\theta or f_{\\theta^*}?\n\n- It would be helpful to state the relationship between \\chi^2-divergence and Wasserstein distance W1 to make the comparison of the results easier. I understand that Mofakhami et al. (2023) had some discussion about this, but the reader may not know that work. It's worth restating some of it for clarity.\n\n- Along the same lines, it would help to provide some guidance on when each of the two results is preferable. \n\nQuestions:\n\nAre you aware of settings where affine risk minimizers converge under strictly weaker assumptions? Even a proof of concept would be interesting, in my opinion.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Performative prediction is a widely studied problem and within this area the convergence of retraining has seen much of the attention. The paper presents solid technical results, taking a good step on top of existing work. Conceptually, not too much is new, but the results require a good bit of new technical material. It's to have matching upper and lower bounds for both the Mofakhami assumptions and the Perdomo assumptions.\n\nI like the idea of affine risk minimizers. It's quite natural in practice to mix in data from previous iterations and not just the most recent datasets. This makes a lot of sense. It's nice to see that this leads to improvements, even if the improvements are only in terms of constant factors in the base of the exponential. It would've been even nicer to see some settings where affine risk minimizers achieve weaker assumptions and not just faster convergence.\n\nTo summarize, this is a solid technical contribution in the area of performative prediction that merits acceptance.", "was_revised": true, "final_justification": "I maintain my positive evaluation after the discussion period.", "rebuttal": "We thank the reviewer for the thoughtful and encouraging feedback. We answer their questions and provide important clarifications below.\n\n> **Minor1: Typo in Eq. 5.**\n\nWe clarify that the original notation is correct, though we agree it can be confusing. The purpose of Eq. 5 is to define the norm structure that will be used throughout the paper. While we write $𝑓_{\\theta^\\*}$, the variable $\\theta^\\*$ here refers to an arbitrarily chosen reference parameter and is not meant to indicate an optimal solution. We will make this clarification explicit in the revised version to avoid confusion.\n\n> **Minor2: Discussions on relations between $\\chi^2$ and $W1$ distance.**\n\nAs suggested, we will include a brief discussion in the revision that clarifies the connection between the $\\chi^2$ divergence and the Wasserstein distance $W1$. As noted in Remark 1 in Mofakhami et. al  (2023), $\\epsilon$-sensitivity w.r.t. $\\chi^2$ divergence is a stronger condition than $\\epsilon$-sensitivity w.r.t. the Wasserstein distance in cases where the diameter of the input space is small enough. However, since one does not always imply the other, we analyze each framework separately based on its respective assumptions.\n\n> **Minor3: Clarifying assumption roles.**\n\nWe also appreciate the suggestion to contextualize our assumptions. In the revised version, we will add a dedicated paragraph comparing the assumptions used in Perdomo et al. (2020) and our adapted version of those in Mofakhami et al. (2023), with emphasis on how these relate to our theoretical bounds.\n\n> **Q1: Convergence under weaker assumptions?**\n\nWe agree that it is of interest to identify settings where affine risk minimisers converge under strictly weaker assumptions. We note that Theorem 4 already provides an instance of such a setting: it guarantees convergence under relaxed constants, which are weaker than those of previous results (lines 217-220). Namely, when $1\\leq \\frac{\\sqrt{\\epsilon}M}{\\gamma} < 1.155$, 2-snapshots ARM converges whereas RRM does not converge. We will make this clearer in the next revision.\n\n> **Formatting concerns.**\n\nThanks for the suggestion. We’ll make sure to add the non-breaking space (~) in those instances."}, {"review_id": "nwFJDFMBHX", "reviewer": "Reviewer_xaNN", "summary": "This paper proposes a new set of assumptions in performative prediction and the corresponding RRM convergence results. Then based on this result, the authors proved the tightness of the convergence speed of [Perdomo et al., 2020] and [Mofakhami et al., 2023]. Next, the authors proposed a new iterative optimization scheme of PP where each time all historical datasets are used (ARM). This brings an improved (but still linear) convergence rate and more relaxed conditions for the convergence of ARM.", "questions": "- What are the challenges to prove the tightness of convergence rates?\n- Can you compare your Assumption 1 to the Assumption 1 in [Mofakhami et al., 2023]? Will it be significantly more restrictive?\nOther questions seen weaknesses.", "limitations": "yes (in Appendix)", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "> Strengths\n\n- The theoretical results on tightness analysis make sense to me. I scanned through Appendix D and the proof seems to be plausible.\n- The ARM formulation is clear and the proof sketch for Theorem 5 and 6 are clear.\n- The writing style of the main paper is easy to follow.\n\n> Weaknesses\n\n- It is better to provide a proof sketch in main paper. Especially for Theorem 2 which is an extension of [Mofakhami et al., 2023], what are the challenges to prove a tight lower bound? Which different proof techniques are used? \n- In Theorem 4, the distribution map needs to satisfy $\\frac{\\epsilon}{C}$ sensitivity and the $C$ is a condition in Assumption 2. But currently I cannot get how large $C$ would be. Can you provide some examples? Afterall, the increased convergence speed is still linear, so the constant $C$ may not be negligible? \n\n> Minor\n- In Assumption 2, is that \"for all $f_{\\theta}, f_{\\theta'}$ and $f_{\\theta^{*}}$\"?\n-  The authors may discuss how restrictive their assumptions are and the related work should include some discussions on recent related literature which have relaxed the convexity assumptions of PP (e.g., [1], [2], and also [Li and Wai, 2024] in your related work section).\n\n[1] Cyffers, Edwige, et al. \"Optimal Classification under Performative Distribution Shift.\" The Thirty-eighth Annual Conference on Neural Information Processing Systems (2024).\n\n[2] Zheng, Xue, Tian Xie, Xuwei Tan, Aylin Yener, Xueru Zhang, Ali Payani, and Myungjin Lee. \"ProFL: Performative Robust Optimal Federated Learning.\" arXiv preprint arXiv:2410.18075 (2024).", "was_revised": true, "final_justification": "I encourage the authors to include the intended modifications and highlight the things in Appendix H. Currently I will retain the positive score.", "rebuttal": "We thank the reviewer for the constructive comments and careful reading of our manuscript. We answer their questions below and provide important clarifications.\n\n> **Q1 and W1: Proof sketch for Theorem 2.**\n\nTo our knowledge, no prior lower bounds have been established for this class of algorithms. While our analysis builds on standard tools, the application to this setting is novel, particularly the use of the specific distribution mapping, which has not been previously reported in the literature to our knowledge. Due to space constraints, we were unable to include the full sketch in the main paper, but we will add a high-level overview of the proof in the revised version.\n\n> **W2: Examples and sensitivity constants.**\n\nFor the lower bound (Theorem 2), the example we construct satisfies the sensitivity condition with constant $C = 1$. This suffices to show that the proposed improvement can outperform the convergent problem class addressed by standard RRM. Additionally, Appendix H (line 726) presents another example in the RIR setup with $C = \\frac{1}{\\delta}$ for $\\delta < 1$. We will move this calculation to the main text and make the constants more explicit. See also the end of our answer to Q2 for Reviewer 6Knm for another setup of explicit computation of $C$ that we will add in the appendix.\n\n> **Minor1: Assumption 2 notation.**\n\nThe reviewer is correct to point out that Assumption 2 should apply to all $f_\\theta$,  $f_{\\theta'}$, and $f_{\\theta^\\*}$. We will correct this in the revised version.\n\n> **Minor2: Assumptions restrictivity.**\n\nWe agree that a clearer discussion of how restrictive the assumptions are—and how their interpretation has evolved in recent literature—would improve the paper. We will add a paragraph after the assumptions section comparing our conditions to those in related work, including recent efforts that relax strong convexity or sensitivity requirements.\n\n> **Minor2: Related work.**\n\nWe appreciate the insightful comment. In the revised version, we will expand the related work section to include recent literature [2, 3].\n\n[2] Cyffers, Edwige, et al. \"Optimal Classification under Performative Distribution Shift.\" The Thirty-eighth Annual Conference on Neural Information Processing Systems (2024).\n\n[3] Zheng, Xue, Tian Xie, Xuwei Tan, Aylin Yener, Xueru Zhang, Ali Payani, and Myungjin Lee. \"ProFL: Performative Robust Optimal Federated Learning.\" arXiv preprint arXiv:2410.18075 (2024).\n\n> **Q2: Comparison to $\\epsilon$-sensitivity in [Mofakhami et al., 2023].**\n\nWe agree that a clearer discussion of the restrictiveness of our assumptions would improve the paper. In Appendix H, we provide an illustrative example comparing our assumption to the $\\epsilon$-sensitivity condition in Mofakhami et al. (2023). In their setup, $\\epsilon = \\frac{1}{\\delta}$, while in ours it becomes $\\epsilon = \\frac{1}{\\delta}\\left(1 + \\frac{1 - \\delta}{2\\sqrt{\\delta}}\\right)$ for $0<\\delta<1$. As shown in Theorem 8 and discussed in Appendix H, this still yields a faster convergence result. We will include additional discussion in the revision, clarifying the implications and practical restrictiveness of our assumptions."}]

Author rebuttal:

Meta-review: This paper considers the performative prediction problem and studies an improved RRM convergence results over [Mofakhami et al., 2023]. The new results consist of giving a laxer criterion for linear convergence and tight characterization of the convergence rate. Moreover, an affine risk minimizer is proposed which enjoys further improved rates. 

The initial reviews of the paper is quite positive, where the reviewers found the submission to propose a new class of algorithm based on the affine risk minimizer that is able to achieve better rate than traditional performative prediction works. There are no particular disadvantage for the paper and it has therefore passed the acceptance threshold. The authors are reminded to take the comments into account when preparing the camera ready version.
Decision: Accept (poster)