Tight Lower Bounds and Improved Convergence in Performative Prediction

We thank the reviewer for the constructive comments and careful reading of our manuscript. We answer their questions below and provide important clarifications.

Q1 and W1: Proof sketch for Theorem 2.

To 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.

W2: Examples and sensitivity constants.

For 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.

Minor1: Assumption 2 notation.

The 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.

Minor2: Assumptions restrictivity.

We 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.

Minor2: Related work.

We appreciate the insightful comment. In the revised version, we will expand the related work section to include recent literature [2, 3].

[2] Cyffers, Edwige, et al. "Optimal Classification under Performative Distribution Shift." The Thirty-eighth Annual Conference on Neural Information Processing Systems (2024).

[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).

Q2: Comparison to $\epsilon$-sensitivity in [Mofakhami et al., 2023].

We 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.

We thank the reviewer for the thoughtful and encouraging feedback. We answer their questions and provide important clarifications below.

Minor1: Typo in Eq. 5.

We 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.

Minor2: Discussions on relations between $\chi^2$ and $W1$ distance.

As 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.

Minor3: Clarifying assumption roles.

We 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.

Q1: Convergence under weaker assumptions?

We 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.

Formatting concerns.

Thanks for the suggestion. We’ll make sure to add the non-breaking space (~) in those instances.

We thank the reviewer for the detailed feedback and the positive assessment of our algorithmic, theoretical, and empirical contribution. We answer their questions below.

Q1 (What is the “initial distribution” p(x) in Assumption 2?).

The 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.

[1] Schnabel, Tobias, Adith Swaminathan, Ashudeep Singh, Navin Chandak, and Thorsten Joachims. "Recommendations as Treatments: Debiasing Learning and Evaluation." ICML 2015.

Q2 (realism of Assumption 2 and discussion on assumptions).

We 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)}$.

Q3 (choice of alpha in Lemma 1).

We use uniform weights over the final two iterations $\alpha^{(t)}_{t-1}=\alpha^{(t)}_t=12$ (Eq.14).

Q4 (What if distribution map is misspecified?).

Our 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).

We hope these clarifications fully resolve the reviewer’s concerns, and thank you again for the constructive review.