Zero-Regret Performative Prediction Under Inequality Constraints
Authors: Wenjing Yan
Xuanyu Cao
Venue: NeurIPS 2023 poster (2023)
Keywords: Performative prediction
decision-dependent distribution
inequality constraints
primal-dual algorithm.

Abstract: Performative prediction is a recently proposed framework where predictions guide decision-making and hence influence future data distributions. Such performative phenomena are ubiquitous in various areas, such as transportation, finance, public policy, and recommendation systems. To date, work on performative prediction has only focused on unconstrained problems, neglecting the fact that many real-world learning problems are subject to constraints. This paper bridges this gap by studying performative prediction under inequality constraints. Unlike most existing work that provides only performative stable points, we aim to find the optimal solutions. Anticipating performative gradient is a challenging task, due to the agnostic performative effect on data distributions. To address this issue, we first develop a robust primal-dual framework that requires only approximate gradients up to a certain accuracy, yet delivers the same order of performance as the stationary stochastic primal-dual algorithm without performativity. Based on this framework, we then propose an adaptive primal-dual algorithm for location families. Our analysis demonstrates that the proposed adaptive primal-dual algorithm attains $\mathcal{O}(\sqrt{T})$ regret and constraint violations, using only $\sqrt{T} + 2T$ samples, where $T$ is the time horizon. To our best knowledge, this is the first study and analysis on the optimality of the performative prediction problem under inequality constraints. Finally, we validate the effectiveness of our algorithm and theoretical results through numerical simulations.

Zero-Regret Performative Prediction Under Inequality Constraints
Wenjing Yan Xuanyu Cao
Department of Electronic and Computer Engineering The Hong Kong University of Science and Technology yan@connect. ust hk, eexcao@ust.ha hk
Abstract
Performative prediction is a recently proposed framework where predictions guide decision-making and hence influence futurre data distributions. Such performative phenomena are ubiquitous in various areas, such as transportation, finance, public policy, and recommendation systems. To date, work performative prediction has only focused on unconstrained scenarios, neglecting the fact that many real- world learning problems subject to constraints. This paper bridges this gap by studying performative prediction under inequality constraints. Unlike most existing work that provides only performative stable points, aim find the optimal solutions. Anticipating performative gradients is a challenging task, due the agnostic performative effect data distributions. To address this issue, we first develop robust primal-dual framework that requires only approximate gradients up to a certain accuracy, yet delivers the same order of performance as the stochastic primal-dual algorithm without performativity. Based on this framework, we then propose an adaptive primal-dua algorithm for location family. Our analysis demonstrates that the proposed adaptive primal-dual algorithm attains ((VT) regret and constraint violations, using only VT + 2T samples, where T is the time horizon. To our best knowledge, this is the first study and analysis on the optimality of the performative prediction problem under inequality constraints. Finally, we validate the effectiveness of our algorithm and theoretical results through numerical simulations.
1 Introduction
Stochastic optimization plays a critical role in statistical sciences and data-driven computing, where the goal is to leam decision rules (e.g., classifiers) based on limited samples that generalize well to the entire population. Most prior studies on stochastic optimization [Heyman and Sobel 2004 Karimi et al. 2019 Powell| 2019 rely the assumption that the data of the entire population lation follows a static distribution. This assumption, however, does not hold in applications where the data distributions change dynamically in response to decision-makers' actions (Hardt al. 2016
Dong et al.) 2018). For instance, in transportation, travel time estimates [Mori et al. [0155 influence routing decisions, resulting in realized travel times; in banking, credit evaluation criteria Abdou and Pointon 2011 guide borrowers' behaviors and subsequently their credit scores; and in advertising, Sánchez et al.) 2020) shape customer preferences, leading to consumption patterns. Such interplay between decision-making and data distribution arises widely in various areas, such transportation, finance, public policy, and recommendation systems.
recommendations
The seminal work [Perdomo et al. 2020 formalized the phenomenon as performative prediction, which represents the strategic responses of data distributions to the taken decisions via decision-
Conresponding Author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

dependent distribution maps Cuinonero-Candelr et al. 2008 Since then, an increasing body of research has been dedicated to performative prediction problems. Most existing studies are focused on identifying performative stable points [Li and Wai, 2022, Li et al.
2022 Drusvyatskiy and Xiao
2022, Brown et al., 2022 Mendler-Dünner et al. 2020] Wood et al., 2021 Ray el. [022], given the complexities of the decision-inducee distribution shifts and the unknown decision- -deenddndd distributions. The proposed algorithms typically iteratively retrain the deployed models until conver- gence. However, performative stability generally does not imply performative optimality. Aiming to achieve optimal performance, a few recent works designed effective algorithms by leveraging rich performative feedback (Jagadessan et al. 2022]. ,. or by making some parametric assumptions on the underlying distribution maps. For instance, the distribution maps belong to the location family with linear structure [Miller et al. [02T] or are from the exponential family Izzo et al. 2021
All the aforementioned work on performative prediction is focused on unconstrained learning prob- lems. However, in the real world, many performative prediction applications are subject to constraints [Detassis et al. 202T] Wood and Dall' Anese [022a]. Constraints can be used to ensure the satisfaction of desired properties, such as fairness, safety, and diversity. Examples include safety and efficiency constraints in transportation [Metz 2021], relevance and diversity constraints in advertising [Khamis] 2020J. and risk tolerance and portfolio constraints in financial trading [Föllmer and Schied [002].
etc. In addition, constraints can serve as side information to enhance the learning outcomes, e.g., by narrowing the scope of exploration or by incorporating prior knowledge /Serafini and Garcez (2016):
Wu et al. (0018) As performative shifts can rarely be analyzed offline, incorporating constraints on what constitutes safe exploration [Turchetta et al. 2019 or facilitates optimization [Wood and
Dall' Anese 20226) is of crucial importance.
Despite its importance, research on performative prediction under constraints has been neglected so far. Although some work [Izzo et al. [02T]] Piliouras and Yu [022] restricted decision variables to certain regions, this feasible set restriction was simply handled by projections. This paper bridges this gap by studying the performative prediction problem under inequality constraints, for which simple projection is inadequate to handle. Unlike most existing work that provides only performative stable points, we aim to find the optimal solutions. As aforementioned, finding performative optima is a challenging task because now need to anticipate performative effect actively rather than simply retrain models in a myopic manner.
However, the performative effect on distribution maps is unknown, which hinders the computation of exact performative gradient. To solve this problem, we develop a robust primal-dual framework that admits inexact gradients. We ask the following questions: How does the gradient approximation error affect the performance of the primal-dual framework? Under what accuracy can the approx- imate gradients maintain the performance order of the stochastic primal-dual algorithm without performativity? How to construct effective gradient approximations that attain the desired accuracy? We answer the above thoroughly. Our idea hinges on enhancing gradient approximation with the parametric knowledge of distribution maps. In particular, we follow existing studies [Miller et al., 2021 2021[Jagader Jagadeesan et al. 2022 and focus the family of location maps. Location family exhibit favorable linear structure for algorithm development while maintaining broad generality to model many real-world applications. Distribution maps of this type are ubiquitous throughout the performa- tive prediction literature, such as strategic classification [Hardt et af.] 2016 [Perdomo et al. 22020] linear regression [Miller al. [202T], email spam classification [Li al. 20022) ride-share Narang et al. 2022]. among others. Nevertheless, we emphasize that our robust primal-dual framework is applicable to other forms of distributions with effective gradient approximation methods.
To our best knowledge, this paper provides the first study and analysis on the optimality of performa- tive prediction problems under inequality constraints. We highlight the following key contributions:
We develop a robust primal- framework that requires only approximate gradients up to an accuracy of O(VT), yet delivers the same order of performance as the stochastic primal-dual algorithm without performativity, where T is the time horizon. Notably, the robust primal- dual framework does not restrict the approximate gradients to be unbiased and hence offers more flexibility to the design of gradient approximation.
Based on this framework, we propose an adaptive primal-dual algorithm for location family, which consists of an online stochastic approximation and an offline parameter estimation for the performative gradient approximation. Our analysis demonstrates that the proposed algorithm achieves O( ((VT) regret and constraint violations, using only vT + 2T samples.

---

Finally, we conduct experiments on two examples: multi-task linear regression and multi- portfolio. The numerical results validate the effectiveness of our algorithm and theoretical analysis.
1.1
Related Work
The study on performative prediction was initiated in [Perdomo et al. 2020]. where the authors defined the notion of performative stability and demonstrated how performative stable points can be found through repeated risk minimization and stochastic gradient methods. Since then, substantial efforts have been dedicated to identifying performative stable points in various settings, such as
single-agent [Mendler- Mlendler-Dünnee Dünner et al.) [020]] Drusvyatskiy and Xiao 2022 Brown et al. [022], multi-
agent [Li et 2022 Piliouras and Yu 2022], games NNarag et al. 2022]. reinforcement learning 2023], and online learning [Wood et al.) 2021] Wood and Dall' Anese
[Mandal et al.
2022a
few recent works aimed to achieve performative optimality, more stringent solution concept than performative stability. In (Miller et al. [202]], the authors evaluated the conditions under which the performative problem is convex and proposed two-stage algorithm find the performative optima for distribution maps in location family. Another paper on performative optimality is [Izzo et al. 2021]. which proposed PerfGD algorithm by exploiting the exponential structure of the underlying distribution maps. Both works took advantage of parametric assumptions on the distribution maps. Alternativll,, (Jagadeesan et al. [022] proposed performative confidence bounds algorithm by leveraging rich performative feedback, where the key idea is to exhaustively explore the feasible region with an efficient discarding mechanism.
A closely related work is [Woo and Dall' Anese problems with decision-dependent distributions. The paper focused on performative stable points (equilibrium points), whereas we aim at the performative optima, which is more challenging. An- other difference is that (Wood and Dall' Anese 20226 only demonstrated the convergence of the proposed primal-dual algorithm in the limit, without providing an explicit finite-time convergence rate. In contrast, we provide O (VTT) regret and (( constraint violation bounds for the proposed algorithm in this paper.
2022b], which studied stochastic saddle-point
Problem Setup
We study performative prediction problem with loss function é (0; 2). where 0 ④ is the decision variable, Z E IR is an instance, and @ E R2 is the set of available decisions. Different from in stationary stochastic optimization where distributions of instances are fixed, in performative prediction, the distribution of Z varies with the decision variable 0, represented by Z D(0). In this paper; we consider that the decision variable subject to a constraint g (0) < O, where g(.) θ -> R... The constraint g(-) can be imposed on A to ensure certain properties, such as fairness, safety, and diversity, or to incorporate prior knowledge. We assume that g(-) is available at the decision-min maker in advance of the optimization. Ideally, the goal of the decision-make is to solve the following stochastic problem:
mingge
Ez-D(a) s.t. g ( -00
where E2>D (0; Z) is referred to as performative risk, denoted by PR(O).
Problem is, however, impossible to be solved offline because the distribution map D(0) is unknown. Instead, the decision-maker needs to interact with the environment by making decisions to explore the underlying distributions. Given the online nature of this task, measure the loss of sequence of chosen decisions 0,, ,r by performative regret, defined as
Reg (7) Σ (E[P((0.)) PR((ro)),
where the expectation is taken over the possible randomness in the choice (0.) and 0po is the performative optimum, defined
Ppo E arg mingee
Ez-D(o) (0;;
s.t. g ( 0.
Performative regret measures the suboptimality of the chosen decisions relative to the performative
optima. Another performance metrie for problem I on evaluating the decision sequence {0,) is
3

---

constraint violation, given by
(T) ET= Big, (0:)), Vi [m]]
where we use the symbol [m]] to represent the integer set {1, mm throughout this paper.
Applications pertaining to problem ① are ubiquitous. Next is an example.
Example (Multi-Asset Portfolio). Consider a scenario where an investor wants to allocate his/her investment across set of I assets, such as stocks, bonds, and commodities. The objective is to maximize the expected return subject to certain constraints, including liquidity, diversity, and risk tolerance. Let 2, denote the rate of return of the ith asset and 0, denote its weight of allocation, Vi E 10. The investment can affect the future rates of return of the assets and, consequently, the particular asset may overall expected return of the portfolio. For example, excessive investment and 0 = [01,... 0t)]
lead to a decline in the rate of return of other assets. Let z = [z1,-... 221] Then, the expected return of the portfolio is E(rp] == Eg~D(0)2 z 0. Typically, the risk of the portfolio is measured by the variance of its returns, given by 0" TO where V is the covariance matrix of z. One common approach to model liquidity is using the bid-ask spread, which measures the gap between the highest price buyer is willing to pay (the bid) and the lowest price seller is willing to accept (the ask) for a particular asset. Denote the vector of the bid-ask spread of the assets by (81,...
Then, a liquidity construint on the portfolio can be defined as s I S S. where S is the maximun allowable bid-ask spread. The multi-asset portfolio problem can be formulated as:
.i] ,
mine - EEz-D00 O s.t. Ei_ 5 0 1
c, s s c. S, and T
@ S
where restricts the maximum amount of investment to one asset, and p is the risk tolerance threshold.
In this paper, our goal is to design online algorithm that achieves both sublinear regret and sublinear constraint violations with respect to the time horizon T, i.e., Reg(T) S o(T) and (io, S (TT), for all i E [m]. Then, the time-average regret satisfies Reg(T constraint violations satisfy Vio, < o(1), for all i E [m]] Both asymptotically go to zero as T' goes to infinity. Therefore, the performance of the decision sequence (0, ) generated by the algorithm approaches that of the performative optimum Opo as T goes to infinity.
S o(1), and the time-average
3 Adaptive Primal-Dual Algorithm
3.1 Robust Primal-Dual Framework
In this subsection, we develop a robust primal-dual framework for the performative prediction problem under inequality constraints. Our approach involves finding a saddle point for the regularized Lagrangian of problem (T.. The Lagrangian, denoted by L( A), is defined as
A() = PR(O) + X g(0) 6y |
(2)
where 0 is the primal variable (decision), À is the dual variable (multiplier), 17 is the stepsize of the algorithm, and is control parameter. In ( we add the regularizer 67 ||| to suppress the growth of the multiplier X, so as to improve the stability of the algorithm. 2
To find the saddle point of the Lagrangian L( A), utilize alternating gradient update on the primal variable and the dual variable A. The gradients of L( A) with respect to and À are respectively given by
VoL(O, -VPR(()) + Vog(0) VAC =g(0) - 5n,,
where Vog(O) is the Jacobian matrix of g()) In 3 VoPR(O) is the gradient of the performative risk PR(O), given by
VoPR(O) EZ~D Vol EN (0: 2) Vo lo
(4)
where po (Z) is the density of D(0).
Since the data distribution D(0) unknown, the exact gradient of the performative risk PR(0) is unavailable. posing a significant challenge to the algorithm design. In this paper, we tackle this

---

issue using robust primal-dual framework. The main idea is to construct gradient approximations from data and then perform alternating gradient updates based on the inexact gradients. Denote by VoPR, (0) the approximation of the gradient (QP at the ith iteration. Correspondingly, an approximation for the Lagrangian gradient Vo A) at the ith iteration is given by
VoL. A) = PR, Vog(O) X, Vt (T].
The robust alternating gradient update is then performed as
0+1 = ITe 0: (o))
(5)
A++1 = + -V+ (0 xx)]
(6)
Then, the next question is how to construct effective gradient approximations that achieve satisfactory performance.
By 4.. the expectation over D()) in the gradient V VoPR(0) can be approximated by samples,
while the unknown probability density pe (2) presents the main challenge. Most existing research circumvented this problem by omitting the second term in VePR(O)) ().. This essentially gives performative stable point. However, as pointed out in [Miller et al. 2021]. performative stable points can be arbitrarily sub-optimal, leading to vacuous solutions. Instead, if we have further knowledge about the parametric structure of po Z), the complexity of gradient approximation can be greatly reduced. In this regard, (Miller et al. 2021 and [Jagadeesan et al. [022 exploited the linear structure of location family, and [Izoo et al. 2021 considered distribution maps within exponential family. Following [Miller al. 2021] Jagadeesan et al. 2022], we focus on the family of location maps in this paper because it exhibits a favorable linear structure for algorithm development while maintaining broad generality to various applications. Next, we develop an adaptive algorithm for problem (T) with location family distribution maps based on the above robust primal- framework.
3.2 Algorithm Design for Location family
In the setting of location family, the distribution map depends on O via linear shift, i.e.
~ D(0) + Z _ Zo + A6,
where Zo ~ Do is a base component representing the data without performativity, E R captures the performative effect of decisions, and _ means equal distribution. Denote by Σ the covariance matrix of the base distribution Do. Note that Do is still unknown. Plugging the distribution definition into we obtain more explicit expression for VRPR(0) as
VOPR(O) EZ,~D, Vol (0: Zu A0) A 2 (0; Zo + A0)
To compute VoPR(0), still need to address two problems: the unknown base distribution Do and the unknown performative parameter A. We tackle them as follows.
Offline Stochastic Approximation: We approximate the base distribution Do offline by sample average approximation [Kleywegt et al. 20022. Specifically, before the start of the alternating gradient update, we first draw samples Zo. f==1 from D(0). These samples are used to approximate the expectation over Zo throughout the algorithm iteration. Hence, the sample complexity from this expectation approximation is fixed at n.
Online Parameter Estimation: We estimate the parameter A via online least squares. In each round of the alternating gradient update. we first take the current decision 0, and its perturbed point 0, + u to observe samples Z, D (0,) and Z/ (0, + +u), respectively, where u, an injected noise specified by the decision-maker. We have E|Z,- - 2, u. Au, Then, the least-square problem at the ith iteration is designed as
minA 1 ||
Z, -u
Let A be the estimate of A at the (t - 1)th iteration. Based on it, we construct a new estimate Ao for A by using gradient descent on the above least-square objective. This gives the update
A, = A, + G [z Z, A.- u.
5

---

Algorithm Adaptive Primal-Dual Algorithm
Take decision 0- and observe samples Zo.: Do. Vi [n].
2: Initialize 0 ε e arbitrarily. Set A = and Ao = 0.
3: for f. = 1 to T do
4: Take decision 0, and observe Ze D (0t).
5: Generate noise u,.
6: Take decision 0, + u, and observe 2/ ~ D D(, 1 Ut).
7: Update parameter estimate by A, = Ac-1 + 21 Zi Zz A u.
8:
Update gradient approximation Vo (o.R.(O.) by 18)
9: Compute (0,, A₂) - (gPR. + Vog (T,))
Update the primal variable by 0++1 IT 0: 1) VoLi 2.))
Compute (xC A,) g(0)) ónjA,
Update the dual variable by A++1 [J + VV x0)
13: end for
where Co is the stepsize online least squares at the /th iteration.
Adaptive Primal-Dual Algorithm: With the above preparation, we obtain approximation for the gradient VoPR(O:) at the tth iteration as
V (0,) = = Σ Vel (0: Zo. + A.0.) + A, VZ (0:: + A.0.)]
(8)
Given VoPR, (0.), we develop an adaptive primal-dual algorithm for the constrained performative prediction problem (1) based on the robust primal-dual framework in $ [3.1] which is presented in Algorithm [ In Algonthm | the initial decision is randomly chosen from the admissible set O. Both the dual variable and the parameter estimate Ag are initialized to be zero. The algorithm maintains two sequences. One is the estimate A,, which is updated based on the newly observed samples Z, and Zí as given in Step 7. The other the alternating gradient update the primal and dual variables, which are respectively given in Step 10 and Step 12.
Remark 1. While this paper considers the distribution maps within the location family, we emphasize that the proposed robust primal-duat framework does not restrict to any form of distribution. For instance, the exponential family considered in fTzzo et al. 2027) with their gradient approximation method can be directly applied to our robust primal- framework.
4 Convergence Analysis
In this section, we analyze the convergence performance of the proposed adaptive primal-dual algorithm. We first provide the convergence result of the robust primal-dual framework. Then, we bound the error of gradient approximation in our adaptive algorithm for the location family. With these results, the convergence bounds of the adaptive primal-dual algorithm are derived. Our analysis is based on the following assumptions.
Assumption (Properties of l (0; Z)). The loss function E (0; 7) is B-smooth, Lo Lo-Lipschitz con- tinuous in 0, Lz-Lipschitz continuous in Z, "to-strongly convex in 0, and "12 "iz-strongly convex in Z. Moreover, we have " B /Yz 0.
Assumption 2 (Compactness and Boundedness of +). The of admissible decisions O is closed, convex, and bounded, i.e., there exists constant R > such that ||0|] S R, vO E e.
Assumption 3 (Properties of g())). The constraint function g ()) is convex, Lg-Lipschite continu- ous, and bounded, i.e., there exists constant C such that [|g 0) C, 40 O.
Assumption (Bounded Stochastic Gradient Variance). For any [r]] and O. there exists 2 0 such that
E Ez VoL (0; Zo, A0) A ZZ + A0) voPR(0) <

---

Assumption iis standard in the literature of performative prediction. Assumptions 2 and 3 are widely used in the analysis of constrained optimization problems [Tan et al. 2018 Yan al. 2019 Cao and Başar 2020), even with perfect knowledge of objectives. Assumption stochastic gradient of (0( Additionally, to ensure a sufficient exploration of the parameter space, we make the following assumption on the injected noises (uz)t=1-
4 bounds the variance of the
Assumption 5 (Injected Noise). The injected noises {ue}e= are independent and identically
distributed. Moreover, there exist positive constants K1, K2, and Rig such that for any t. [7]. the random noise U2 satisfies
K1 3 E [u EE I| S K2, and E | u.u. u
I rigl [.uu
Consider a Gaussian noise that ~ N (0, D), Vt E [T], we have K1 = 1, K2 = d, and K3 3d.
With the above assumptions, we provide some supporting lemmas below. First, we show e-sensitivity of the location family given in (7).
Lemma 1 (e-Sensitivity of D(O)). Define T (A) = maxx0ll2=1 ||0 The location family given in ( s-sensitive with purameter e S Tmax (A). That is, for any 0, O' E O we have
W1 (D(O), (0')) S <=| 0000l,, where Wi (D, denotes the Wasserstein-1 distance.
0'11z,
See $ of the supplementary file for the proof. Building upon Lemma T we have the following I Lemma about the performative risk PR(0).
I Lemma 2 (Lipschitz Continuity and Convexity of PR(()). Consider the location family given in
7 With Assumption and Lemma 7 we have that: 1) the performative risk PR(O) L-Iipschitz continuous for T. S Too + m.z
A); 2) the performative risk PR(O) () is y-sttrnglyy convex for
7 max {he B² //z, - 2eB + 720 min {A)]
where miin == min 01 |A0
See & B of the supplementary file for the proof. Based on the Lipschitz continuity and convexity of PR(O). we provide the convergence result of the robust primal-dual framework below.
Lemma 3 (Convergence Result of Robust Primal-Dual Framework). Set v VT. Then, there
11-V-222
32n L
exists constant 8 E
such that under Assumptions 1 3 for T
4n
32L2. g. the regret satisfies:
Σ (E[PR(0.) - PR (OPo))
< <2vT (2R² + c 202+2221 222) 7-6
1
VOP VoPR(())
EL
2a
vT
where (0,7) is constant. Further, for any i [m]. the constraint violation satisfies:
E
Σn - (0,) Svi+8 (2R+ V2C + 2T. VT
(2
+ +
(+++V2)
T Va
V2
VoPR. (OP - VOPR(
Remark 2. Lemma reveals the impact of gradient approximation error on the convergence perfor- mance of the robust primal-dual framework. By Lemma 3 if the accumulated gradient approximation error is less than (VTT), both the regret and the constraint violations are bounded by O(VT). Although stochastic primal-duc dual methods for constrained problems without performativity also use approximated (stochustic) gradients, they generally require unbiased gradient approximation (Tan) al. 2018 Yan et al.) 2019: Cao and Bagar. 2022]. This requirement, however, difficuli to satisfy in performative prediction since the unknown performative effect of decisions changes the data distribution. contrast, the robust primal-duue framework does not restrict the approximate gradients be unbiased and hence offers more flexibility to the design of gradient approximation.
Proof of I Lemma 3 is provided of the supplementary file. In the next lemma, we bound the gradient approximation error of the adaptive primal-dual algorithm.
7

---

Lemma 4 (Gradient Approximation Error). Set & = (t-())+22 Vt E [T]. Then, under
2
Assumptions 1 and
S the accumulated gradient approximation error is upper bounded by:
V (O,) - VoPR(O.)
I 2To" + + (1 + 20 max (A))) (l(
where ā. == max
2n33
|A
A l
Sng tr(
). In Algorithm 7 we set Ao = 0, and thus we have
max
28a
|
Sk2 tr(2))
of
Remark 3. Lemma 4 demonstrates that the gradient appreximation error of the adaptive primal-dud algorithm is upper bounded by (n + In(T)) we we set the number of initial samples n 2 VT, - V (o.R S O(TT). According to Lemma this suffices to
huve Eí E voPR(O.) I
make the regret and constraint violation bounds to be O(VT).
Proof of Lemma Dis presented in of the supplementary file. Combining Lemma 3 and Lemma 4 yields the regret and constraint violations of Algorithm IT which is elaborated Theorem below.
+ and St Theorem 1. Set = VT
m1(1-1)22g Vt E [2]. Then, there exists a constant
11-1322 L2 2n7"
1+ /1-1-32n 22
8 E
such that under Assumptions 1 for z 32L the 7 is upper bounded by:
4np
regret of Algorithm
Eh (E(R((O)) - PR (Oro)) S SNVI (2R² - C2 + +
3 ) N
7-a
7-a
In
2 + +x
(2L3 + R² (1 + 2cr max (A))).
Further, for any i [m], the constraint violation is upper bounded by:
E Et= Di (0i) Evi+ō (2R +T)) VT
v2
2
r vn
Va
T
2V((1+0)(n(T)
T
+ +V Va
V2
(2L2 + 8² R² (1 20 max (A)))
Vn
Remark 4. Theorem demonstrates that Algorithm achieves O(VT + T//)) regret and O(VT T Tn) constraint violations. By setting n = vT, we have T/n = /T and T iv== VT, and hence both the regret and constraint violations are upper bounded by O(VT). This indicates that Algorithm 7 Nattains the same order of performance as the stochastic primal-dual algorithm without performativity (Tan et al. 20188 Yan et al. 2019/.
requires a total of VT + 2T samples. Among them, VT samples are dedicated to approximate the expectation over the base component Zo- Furthermore, each iteration requires an additional 2 samples to construct the online least-square objective, accumulating the remaining 2T samples.
Remark S. Throughout the time horizon T, Algorithu /
Numerical Experiments
This section verifies the efficacy of our algorithm and theoretical results by conducting numerical experiments on two examples: multi-task linear regression and multi-assed asset portfolio.
We first consider multi-task linear regression problem in an undirected graph G = (V, E), where represents the node set and represents the edge set. Each node handles a linear regression task (O,) = B(x. (=),(.))) (0;; (x,, v.)), where 0 is the parameter vector and (x,, y.) is feature-label pair. The loss function each task (0,; 9:)) = 1/2 (w: - 0. x;) Vi E V. The parameters of each connected node pair are subject to proximity constraint |10 0, < b
v(i,j) E E. The entire network aims to solve the following problem:
ming,
Diev (x.. - 0, 0.xxi. x, s.t. 110, 0, < bg V(i.j) EE
8

---

(a)
(b)
(c)
10a
10P
10a
-0.2
10A
10
-0.4-
10"4
-0.0
10a2
10"2
10
APDA: C-10
Baseiieeze
10
PDP5 2-
10
Baseine:s 1-10
-1.0
10"3
10
10
10a
10
101
10a
10P
101
10?
107
10
102
107
terations
Iterations
Iterations
Figure 1: Multi-task linear regression. (a)
Re
(b)
r.]Viox (c) 10 0poll:: (d) || - A A
Vio,
Regg(())
(a)
(b)
(c)
(d)
107
0.0
10a1
6-
101
0.5
10-1
10a1
109
-1.0
10-1
APDA cel
10"1
PDPS re1
-2.0
10
10
PIPS 2+30
-25
Boseline c-10
10
107
10'
10a
10a
10a
10
10'
10a
10a
30'
10a
10'
terations
terations
Beeations
Iteraioons
Figure 2: Multi-asset portfolio.
Reg(()
(b)
[1]] (c) 110, 0pO 12: (d) || AlE
Vin, (t)
(e)
The second example considers the multi-assed portfolio described in Example details are provided in s[Foo the supplementary file.
The simulation
We compare the proposed adaptive primal-dual algorithm (abbreviated as APDA) with two approaches. The first approach is "PD-PS", which stands for the primal-dual (PD) algorithm used to find the performative stable (PS) points. The algorithm PD-PS similar to APDA, but it uses only the first term in Eq. (8) as the approximate gradient. The second approach is "baseline", which runs the same procedures as APDA with perfect knowledge of A, i.e., the performative effect is known. We consider four performance metrics: (a) relative time-average regret Reg(t) T-Heg(Ij' (b) relative time-average [1]] (c) decision deviation |00, 0poll2. and (d) parameter estimation
constraint violation Vio,(t)
error A,
l...
Fig. 1 and Fig. 2 show the numerical results of the multi-task linear regression and the multi-asset portfolio, respectively. In both figures, consider two settings for the sensitivity parameter of D(0), namely 8 = 1 and e = 10. The results of these two figures are qualitatively analogous. First, we observe that APDA outperforms PD-PS significantly that both the relative time-average regret and the decision derivation of the former achieve an accuracy around or up to 10-3 for the setting of T 105. while these of the latter have worse performance for E = 10. The relative time-average constraint of all cases converges to zero or negative numbers. This corroborates the sublinearity
and converge constants for
the regret and the constraint violations of APDA, shown in Theorem [ More importantly, this result implies that the larger the sensitivity parameter E, the stronger the performative power is and, consequently, the worse PD-PS performs. In contrast, by tracking the performative gradient, APDA adapts to the unknown performative effect and performs well constantly. Moreover, both subfigures (d) show that the error of parameter estimates decreases sublinearly with iterations, validating the effectiveness of the online parameter estimation. Last but not least, the performance of APDA close to the performance of the baseline, which manifests the effectiveness of proposed APDA algorithm.

---

Conclusions
This paper has studied the performative prediction problem under inequality constraints, where the agnostic performative effect of decisions changes future data distributions. To find the performative optima for the problem, we have developed robust primal-dual framework that admits inexact gradients up to an accuracy of ((VT), yet delivers the same O(vT) regret and constraint violations as the stochastic primal-dual algorithm without performativity. Then, based on this framework, we have proposed an adaptive primal-dual algorithm for location family with effective gradient approximation method that meets the desired accuracy using only /T + 2T samples. Numerical experiments have validated the effectiveness of our algorithm and theoretical results.
Acknowledgments and Disclosure of Funding
The work was supported by the National Natural Science Foundation of China Grant 62203373.
References
Hussein A Abdou and John Pointon. 2011. Credit scoring, statistical techniques and evaluation criteria: review of literature. Intelligent systems accounting, finuune and management 18. 2-3 (2011). 59-88.
Gavin Brown, Shlomi Hod, and Iden Kalemaj. 2022. Performative prediction in stateful world. In International Conference on Artificial Intelligence and Statistics. PMLR, 9445-
Xuanyu Cao and Tamer Başar. 2020. Decentralized multi- agent stochastic optimization with pairwise constraints and quantized communications. IEEE Transactions on Signal Processing 68 (2020), 3296-3996 -311..
Xuanyu Cao and Tamer Bayar. 2022. Distributed constrained online convex optimization over multiple access fading channels. IEEE Transactions on Signal Processing 70 (2022), 3468-3483.
Fabrizio Detassis, Michele Lombardi, and Michela Milano. 2021. Teaching the old dog tricks: Supervised learning with constraints. Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 3742- 3749.
Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. 2018. Strategic classification from revealed preferences. Proceedings of the 2018 ACM Conference on Economics and Computation. 55-70.
Dmiirit Drusvyatskiy and Lin Xiao. 2022. Stochastic optimization with decision-deepnndent distributions. Mathematics of Operations Research (2022).
Hans Föllmer and Alexander Schied. 2002. Convex measures of risk and trading constraints. Finance and stochastics 6 (2002), 429-4429 447.
Ricardo Colomo-Palacion and Rafacl Valencia-Garefa. 2020. A social-semanne Francisco recommender system for advertisements. Information Processing Management 57, 2 (2020), 102153.
Michael Grant and Stephen Boyd. 2014. CVX: Matlab software for disciplined convex programming, version 2.1.
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. 2016. Strategic classification. In Proceedings of the 2016 ACM conference on innovations theoretical computer science. 111-122.
Daniel Heyman and Matthew J Sobel. 2004. Stochastic models in operations research: stochastic optimization. Vol. 2. Courier Corporation.
Zachary Izzo, Lexing Ying, and James Zou. 2021. How to learn when data reacts your model: performative gradient descent. In International Conference on Machine Learning. PMLR, 4641-4650.
Meena Jagadcesan, Tijana Zmic. and Celestine Mendler- Dunnee. 2022. Regret minimization with performative feedback. In International Conference on Machine Learning. PMLR, 9760-97877
Belhal Karimi, Blazej Miasojedow, Eric Moulines, and Hoi-To Wai. 2019. Non-asymptotic analysis of biased stochastic approximation scheme. In Conference on Learning Theory. PMLR, 1944-1974.
Susie Khamis. 2020. Branding diversity: New advertising and cultrall strategies. Routledge.
10

---

Anton J Kleywegt, Alexander Shapiro, and Tito Homem-de Mello. 2002. The sample average approximation method for stochastic discrete optimization. SIAM Journal on optimization 12, 2 (2002). 479-502.
Qiang Li and Hoi-To Wai. 2022. State dependent performative prediction with stochastic approximation. In International Conference on Artificial Intelligence and Statistics. PMLR, 3164-3186.
Qiang Li, Chung Yau, and Hoi Wai. 2022. agent Performative Prediction with Greedy Deployment and Consensus Seeking Agents. In Advances in Neural Information Processing Systems.
Debmalya Mandal, Stelios Triantafyllou, and Goran Radanovic. 2023, Performative reinforeement learning. In International Conference on Machine Learning PMLR, 23642 23680.
Celestine Mendler- Dünnnr, Juan Perdomo, Tijana Zmic, and Moritz Hardt. 2020. Stochastic optimization for performative prediction. Advances in Neural Information Processing Systems 33 (2020), 4929 4939.
David Metz. 2021. Time constraints and travel behaviour. Transportation planning and technology 44, (2021), 16-29.
John Miller, Juan C. Perdomo, and Tijana 7mic. 2021. Outside the echo chamber: Optimizing the performative risk. International Conference on Machine Learning. PMIR, 7710-7720.
Usue Mori, Alexander Mendiburu, Maite Álvarez, and Jose A Lozano. 2015. A review of travel time estimation and forecasting for advanced traveller information systems. Transportmetrica A: Transport Science 11, (2015), 119-157.
Adhyyan Narang, Evan Faulkner, Dmitriy Drusvyatskiy, Maryam Fazel, and Lillian Ratliff. 2022. Learning in Stochastic Monotone Games with Décision-Depenaee Data. In International Conference Artificial Intelligence and Statisties. PMLR, 5891 5912.
Juan Perdomo, Tijana Zmic, Celestine Mendler-Düine and Moritz Hardt. 2020. Performative prediction. In International Conference on Machine Learning. PMLR, 3599-7609.
Georgios Piliouras and Fang-Y Yi Yu, 2022. Multi-agent performative prediction: From global stability and optimality to chaos. arXiv preprint arXiv:2201. 10483 (2022).
Warren B Powell. 2019. A unified framework for stochastic optimization. European Journal of Operational Research 275, (2019), 795-821.
Joaquin Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. 2008. Dataset shift machine learning. Mit Press.
Mitas Ray, Lillian Ratliff, Dmitriy Drusvyatskiy, and Maryam Fazel, 2022. Decision-dependent risk minimiza- tion in geometrically decaying dynamic environments. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 36. 8081-8083
Luciano Serafini and Artur d' Avila Garcez. 2016. Logic tensor networks: Deep learning and logical reasoning from data and knowledge. arXiv preprint 1606 04422 (2016).
Conghui Tan, Tong Zhang, Shiqian Ma, and Ji Liu. 2018. Stochastic primal-dual method empirical risk minimization with O(1) per-iteration complexity. Advances in Neural Information Processing Systems 31 (2018).
Matteo Turchetta, Felix Berkenkamp, and Andreas Krause. 2019. Safe exploration for interactive machine learning. Advances in Neural Information Processing Systems 32 (2019).
Killian Wood, Gianluca Bianchin, and Emiliano Dall' Anese. 2021. Online projected gradient descent for stochastic optimization with decision-dependent distributions. IEEE Control Systems Letters (2021), 1646-1651.
Killian Wood and Emiliano Dall' Anese. 2022a. Online Saddle Point Tracking with Decision-Dependent Data. arXiv preprint arXiv:2112.02693 (2022).
Killian Wood and Emiliano Dall' Anese, 2022b. Stochastic saddle point problems with decision-dependent distributions. arXiv preprint arXiv:2201.0231/ (2022).
Yu Wu, Wei Wu, Can Xu, and Zhoujun 2018. Knowledge enhanced hybrid neural network for text matching.
In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 32.
Yan Yan. Yi Xu, Qihang Lin, Lijun Zhang, and Tianbao Yang. 2019. Stochastic Primal- -ual Algorithms with
Faster Convergence than O(IvVI) for Problems without Bilinear Structure, arXiv preprint arXiv:1904.10112 (2019).


Reviews:
[{"review_id": "5gT7JnncsT", "reviewer": "Reviewer_NMva", "summary": "This paper studies the problem of performative prediction under inequality constraints. The authors propose an adaptive, robust primal-dual algorithm that achieves sublinear regret and constraint violations, where the regret is with respect to the performative optima (instead of just a performative stable point). The algorithm is robust in the sense that it only requires approximate gradients up to a certain accuracy level and doesn't require the estimated gradients to be unbiased.", "questions": "* I really like example 1 (multi-asset portfolio). However, I have one question - can you elaborate on how \"excessive investment in a particular asset can lead to a declination of its rate of return\"?\n\n* Do you have thoughts on whether the sample complexity of $\\sqrt{T} + 2 T$ is tight?\n\n* Can you provide some intuition for why the third part of Assumption 5 is needed?\n\n* What is the dependence of the bounds on the dimension $d$? For example, for the case of Gaussian noise, $\\kappa_2 = d$ and $\\kappa_3 = 3d$ (line 250) and in Lemma 4 this can result in a factor as large as $d$ (through the definition of $\\bar{\\alpha}$. Can this dependence be improved? Do existing results in the performative prediction literature (and results on performative regret in the unconstrained setting) have a similar dependence?\n\n* (This is a comment, not a question.) It would help to include some proof sketches in the main paper. (I have not checked the proofs in the appendix.)", "limitations": "Limitations: Assumptions are clearly stated in Section 4. (The assumption that one can query the distribution could be stated more explicitly.)\nNegative societal impact: N/A.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* The main paper is very clearly written. The remarks around lemmas and theorems are helpful in interpreting the formal results.\n\n* The proposed primal-dual algorithm is very nice in the sense that (i) the gradient estimators don't need to be unbiased; and (ii) the authors prove a regret bound in terms of the accumulated gradient approximation error. This can be a valuable contribution to the research community.\n\n* The theoretical results are supplemented by good experimental results on multi-task linear regression and multi-asset portfolio.", "weaknesses": "* The model assumes the learner can query the distribution for samples (lines 204 - 213). In particular, the learner can query the performative risk at $\\theta_t$ and $\\theta_t + u_t$. This is a strong assumption and should be stated more explicitly. What if the learner cannot query the distribution and only observes a single sample (or, say, $k$ samples) in each round depending on $\\theta_t$? This is more similar to the setting of Jagdeesan et al.\n\n* I acknowledge that Assumption 1 is standard in the literature on performative prediction, but I find the strong-convexity assumption quite strong.\n\n* There is no discussion on lower bounds for the sample complexity.\n\n* The bound seems to have a factor of $d$ (the dimension). It is unclear to me whether this can be improved and how this compares to existing results in the performative prediction literature and results on performative regret in the unconstrained setting. (See one my questions below.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and for recognizing our contribution to the research field of performative prediction. Our point-to-point responses to concerns on weaknesses and questions are given below:\n\n**Reply to Weaknesses:**\n\n**1. Reply to Weakness 1:**  Thank you for the comment. Our algorithm only needs to query the data distribution $D(\\theta)$, not the performative risk. Specifically,  we first draw $n$ samples from the distribution $D (\\mathbf{0})$ at the start of our algorithm. Then, at each iteration, we requires two samples $Z_t \\sim D\\left(\\theta_t\\right)$ and $Z^\\prime_t \\sim D\\left(\\theta_t+u_t \\right)$, where $\\theta_t$ is the current decision and $u_t$ is an injected noise. This setting aligns with [Jagdeesan et al., 2022] and is standard in the literature of performative prediction. We apologize for any potential misunderstanding in our paper, and we have clarified this in the revised version.\n\n\n**2. Reply to Weakness 2:**  Thank you for the comment. We agree with the reviewer that the strong-convexity assumption on the loss function is relatively strong, although it is standard in performative prediction. To enforce strong-convexity, a common approach is to add a regularizer $||\\theta||_2^2$ on the loss function,  as adopted by [Narang et al., 2022] and [Mandal et al., 2022]. It may be possible to eliminate the strong-convexity assumption in constrained performative prediction by utilizing techniques for nonconvex-concave problems. We leave it as a future research direction.\n\n**3. Reply to Weakness 3:**  Thank you for the comment. We have added a remark on the sample complexity of our algorithm in Section 4 of our revised manuscript, as cited below:\n\n >\"Over the time horizon $T$, Algorithm 1 requires a total of $\\sqrt{T}+2T$ samples. In these samples, $\\sqrt{T}$ samples are used to approximate the expectation over $Z_{0}$. Additionally, $2$ samples are required at each iteration to construct the online least-square objective.  \"\n\n\n**4. Reply to Weakness 4:**  Thank you for the comment.  Please find the answer to this comment in Reply to Question 4. \n\n**Reply to Questions:**\n\n**1. Reply to Question 1:**  Thank you for the question. Excessive investment in a single asset can lead to an overvaluation of that asset relative to its underlying fundamentals. If the asset's price becomes overvalued, it may deter other investors from buying into the asset, reducing its demand in the market. This reduction in demand can lead to a decline in the asset's price as investors try to sell their holdings to avoid potential losses, further exacerbating the decline. \n\n**2. Reply to Question 2:**  Thank you for the question. Our algorithm achieves the same order of sample complexity, i.e., $\\mathcal{O}(T)$, as the stochastic algorithm that performs gradient updates based on a single sample in each iteration. Moreover, compared to three other papers ([Miller et al., 2021], [Jagadeesan et al., 2022], and [Izzo et al., 2021]) on performative optimality, the sample complexity of our algorithm is of the same order as that of [Miller et al., 2021], while is lower than that of [Jagadeesan et al., 2022] and [Izzo et al., 2021], whose sample complexity are both $\\mathcal{O}(T\\log(T))$.\n\n**3. Reply to Question 3:**  Thank you for the question. In online least-squares, the update rule of the parameter estimate is $\\hat{\\mathbf{A}}_{t+1} = \\hat{\\mathbf{A}}_t - \\zeta_t(\\hat{\\mathbf{A}}_t \\mathbf{u}_t - (Z^\\prime_t - Z_t))\\mathbf{u}_t^\\top$, where $\\zeta_t$ is the stepsize. To evaluate the parameter estimation error, we compute \n\n$$||\\hat{\\mathbf{A}}_{t+1} - \\mathbf{A}||_F^2 =||\\hat{\\mathbf{A}}_t  - \\mathbf{A}  - \\zeta_t(\\hat{\\mathbf{A}}_t \\mathbf{u}_t - (Z^\\prime_t - Z_t))\\mathbf{u}_t^\\top||_F^2.$$\n\nDecomposing the above equation yields a term related to $||\\mathbf{u}_t||_2^2 \\mathbf{u}_t \\mathbf{u}_t^\\top$. Thus, we need the third part of Assumption 5.\n\n\n**4. Reply to Question 4:**  Thank you for the question. Our regret bound is given by $\\mathcal{O}(d\\sqrt{T})$ if we take the decision dimension $d$ into consideration. The factor $d$ arises in our regret bound due to the parameter estimation error. We cannot remove $d$ from our bound because the estimation error of the online least-squares is proportional to the number of parameters that need to be estimated. \n\nIn the literature, the performance bounds of other papers on performative optimality also depend on the decision dimension $d$ by $\\mathcal{O}(d)$, including [Miller et al., 2021], [Jagadeesan et al., 2022], [Izzo et al., 2021], and [Narang et al., 2022].\n\n**5. Reply to Question 5:**  Thank you for the comment. We have added a proof sketch at the start of the Section 4. Specifically, in our analysis, we first provide the convergence result of the robust primal-dual framework, which depends on the accumulated gradient approximation error. Then, we bound the error of gradient approximation by our adaptive algorithm. With these results, the convergence bounds of the proposed adaptive primal-dual algorithm are derived. \n\n**We would be happy to discuss with the reviewer should there be any other concerns/questions. Thank you very much!**\n\n\n"}, {"review_id": "FOxQ2p6Lvc", "reviewer": "Reviewer_PDku", "summary": " This paper studies performative prediction under inequality constraints. In particular, the paper develops a robust primal-dual framework that requires only approximate gradients up to a certain accuracy but achieves the same order of performance as the stationary stochastic primal-dual algorithm even without performativity. Based on this framework, the authors propose an adaptive primal-dual algorithm for location families. The paper also presents the regret analysis and the perform numerical simulations to validate their findings. ", "questions": "1. Can the author be more explicit about the dependency on the sample required per iteration? In particular, for line 282, why does the initial sample $n\\geq \\sqrt{T}$ implies the sum of the expected gradient difference is bounded by $O(\\sqrt{T})$?", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper studies and analyze the optimality of the performative prediction problem under inequality constraints, which is an important yet missing piece in the literature. As far as I know, this is the first paper attempts to provide a solution to this problem. The paper is well-written, easy to follow, and the proposed robust primal-dual method is intuitive. The theoretical analysis is throughout and it also provides empirical study to justify the findings.", "weaknesses": "The major weakness of the paper is the assumptions are very strong, and the setting is somewhat restricted. For example, the proposed algorithm only works for a particular family of distribution, namely the location family, and it requires an accurate estimation of all the parameters involved in the computation, which might not be realistic. However, it is also almost unavoidable for the performative prediction setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and for recognizing our contribution to the research field of performative prediction. Our point-to-point responses to concerns on weaknesses and questions are given below:\n\n**Reply to Weaknesses:**  \n\n1) >The major weakness of the paper is the assumptions are very strong.\n\n**Reply:** Thank you for the comment.  We agree with the reviewer that the assumptions made in our paper are relatively strong, although they are standard in the literature of performative prediction and constrained optimization. It may be possible to eliminate some of the assumptions, such as the strong-convexity of the loss function may be removed by utilizing techniques for nonconvex-concave problems [Valkonen, 2021] [Zhao, 2020]. We leave it as a future research direction.\n\n•\tValkonen, Tuomo. \"First-order primal–dual methods for nonsmooth non-convex optimisation.\" Handbook of Mathematical Models and Algorithms in Computer Vision and Imaging: Mathematical Imaging and Vision (2021): 1-42.\n\n•\tZhao, Renbo. \"A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization.\" arXiv preprint arXiv:2003.04375 (2020).\n\n\n2)\t> The setting is somewhat restricted. For example, the proposed algorithm only works for a particular family of distribution, namely the location family. and it requires an accurate estimation of all the parameters involved in the computation, which might not be realistic.  However, it is also almost unavoidable for the performative prediction setting.\n\n**Reply:** Thank you for the comment. The proposed robust primal-dual framework has no restrictions on data distributions but only requires that the gradient approximation is up to a certain accuracy. To be specific, the regret bound of the primal-dual framework is given by \n\n$$ \\sum_{t=1}^T \\left(\\mathbb{E}PR(\\theta_t) -   PR(\\theta^*)\\right) \\leq \\frac{\\gamma \\sqrt{T}}{\\gamma-a} \\left(2R^2 + C^2 + 2L^2 \\right) + \\frac{\\gamma}{\\gamma-a}\\left(\\frac{1}{2a} + \\frac{1}{\\sqrt{T}} \\right) \\sum_{t=1}^T\\mathbb{E} ||\\nabla \\widehat{PR}_t(\\theta_t)-\\nabla PR(\\theta_t)||_2^2,$$\n\nwhere $a \\in (0,\\gamma)$ is a constant and $\\gamma$ is the strongly-convex parameter of the performative risk. Denote by $\\mathbf{e}(T) := \\sum_{t=1}^T \\mathbb{E} ||\\nabla \\widehat{ PR}_t(\\theta_t) - \\nabla PR(\\theta_t) ||_2^2$. Then, the regret of the robust primal-dual framework is upper bounded by $\\mathcal{O}\\left(\\sqrt{T}+\\mathbf{e}(T)\\right)$. To achieve an $\\mathcal{O}(\\sqrt{T})$ regret bound, we only require that the accumulated gradient approximation error $\\mathbf{e}(T)\\leq\\mathcal{O}(\\sqrt{T})$, and there is no restriction on the forms of distributions.\n \nIn this paper, as an example, we consider distribution maps of the local family, where the performative effect is linear w.r.t. the decision. Our robust primal-dual framework can be applied to other distribution families if they have effective gradient approximation methods. For instance, the exponential family considered in [Izzo et al., 2021] with their gradient approximation method can be directly applied to our robust primal-dual framework.\n\nWe thank the reviewer for pointing this out. We have clarified the generalizability of our robust primal-dual framework to other distributions in the revised manuscript.\n\n**Reply to Questions:** \n\n1)  > Can the author be more explicit about the dependency on the sample required per iteration?\n\n**Reply:** Thank you for the question. First, at the start of our algorithm,  we draw $\\sqrt{T}$ samples from $\\mathcal D(\\mathbf{0})$. These samples are used to approximate the base distribution $\\mathcal{D}_0$ throughout the algorithm iteration. Then, at each iteration, we require two samples $Z_t \\sim \\mathcal{D}(\\theta_t)$ and $Z^\\prime_t \\sim \\mathcal{D}(\\theta_t+u_t )$, where $\\theta_t$ is the current decision and $u_t$ is an injected noise. These two samples are for constructing the online least-square objective to update the estimate of the parameter $\\mathbf{A}$. Overall, our algorithm requires $\\sqrt{T} + 2T$ samples.\n\n2)  >In particular, for line 282, why does the initial sample $n\\geq \\sqrt{T}$ implies the sum of the expected gradient difference is bounded by $\\mathcal{O}(\\sqrt{T})$?\n\n**Reply:** Thank you for the question. From Lemma 4, the error of our gradient approximation is upper bounded by:\n\n $$ \\sum_{t=1}^T \\mathbb{E} ||\\nabla \\widehat{PR}_t(\\theta_t) - \\nabla  PR(\\theta_t) ||_2^2\n    \\leq \\frac{2T\\sigma^2}{n} + \\frac{4}{n} \\left(2L_Z^2 + \\beta^2 R^2 (1 + 2\\sigma(\\mathbf{A}))  \\right)\\bar{\\alpha}\\ln(T) = \\mathcal{O}\\left( \\frac{T}{n} + \\ln{T}\\right), $$\n\n\nwhere  $\\bar{\\alpha}:=\\max\\left(\\left(1+\\frac{2\\kappa_3}{\\kappa_1} \\right) ||\\hat{\\mathbf{A}}_1 - \\mathbf{A}||_F^2 ,  \\frac{8\\kappa_2~tr(\\Sigma)}{\\kappa_1^2}\\right)$.    \n\n  Since $ \\ln(T) \\leq \\sqrt{T}$, when the number of initial samples $n \\geq \\sqrt{T}$, we have $\\mathcal{O}\\left( \\frac{T}{n} + \\ln{T}\\right) \\leq \\mathcal{O}( \\sqrt{T}) $ and thus  the expected gradient difference $ \\sum_{t=1}^T \\mathbb{E} ||\\nabla \\widehat{ PR}_t(\\theta_t) - \\nabla  PR(\\theta_t) ||_2^2 \\leq \\mathcal{O}( \\sqrt{T}) $.\n\n**We would be happy to discuss with the reviewer should there be any other concerns/questions. Thank you very much!**"}, {"review_id": "NFECox3l5c", "reviewer": "Reviewer_qFHm", "summary": "The paper studies the problem of performative prediction under inequality constraints and gives an no-regret learning algorithm that obtains $O(\\sqrt{T})$ regret and uses $\\sqrt{T} + 2T$ samples.\n\nIn the problem of performative prediction, the data distribution $Z\\sim D(\\theta)$ depends on the choice $\\theta$ of decision maker, and one formulates it as an optimization problem $\\min_{\\theta}E_{Z\\sim D(\\theta)}\\ell(\\theta, Z)$ and one only has sample access to the distribution $D(\\theta)$. The major difference from previous work is that the paper considers a constrained optimization problem, where $\\theta$ needs to satisfies certain constraints.\n\nThe paper proposes to use primal-dual gradient descent-ascent to solve the problem. Especially, the paper considers location families (where $Z \\sim Z_0 + A\\theta$ for some unknown matrix $A$) and provides convergence guarantee when the loss function is well-behaved (e.g. strongly convex and smooth).\n\nNumerical experiments are also conducted to verify the practicality of the proposed method.", "questions": "The theoretical result mainly focus on the cumulative regret, but as an optimization problem, it is also important to obtain a good decision at the end of $T$ rounds. Do you think taking the average of $\\theta_1,\\dots,\\theta_T$ would be result in a feasible decision with optimality guarantee?\n\nI have a few questions regarding the writing of the paper:\n\n(1)  Algorithm Line 4,6, it should be $A$ instead of $\\hat{A}_t$?\n\n(2) Assumption 3, what do you mean by saying the vector valued function $g(\\theta)$ is convex? \n\n(3) Line 266, the LHS should be $g_i$ instead of $g_m$, right?", "limitations": ".", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The performative prediction task is a well-studied problem and the constrained one (studied by this paper) is well-motivated. The primal-dual method proposed in this paper is practical and the author also provides regret guarantee under assumptions. The writing is clear and easy to read.", "weaknesses": "The technical novelty is limited, the primal dual method (and its robustness to gradient error) is fairly common in the literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and for recognizing our contribution to the research field of performative prediction. Our point-to-point responses to concerns on weaknesses and questions are given below:\n\n**Reply to Weaknesses:** Thank you for the comment. The primal-dual method is widely used in the literature as an effective tool for solving constrained optimization problems. However, performative prediction poses several technical challenges that are unique to this field. \n\nThe first challenge is that the data distribution in performative prediction varies with the decision taken, leading to a changing optimization objective, i.e., performative risk. Although the current loss function is also unknown in online optimization, it is revealed after the current decision is made. On the other hand, in performative prediction, due to the uncertainty of the underlying distribution, the exact performative risk remains unknown throughout the optimization process. This leads to the second challenge in our problem. Most existing work simplifies this problem by identifying performative stable points that minimize the loss function under the distribution it induces. However, performative stability does not necessarily imply performative optimality. \n\nIn our paper, we aim to find the performative optima for the constrained performative prediction problem, which is a more stringent solution concept than performative stability. To solve this problem, we design a robust primal-dual framework that accepts inexact gradient approximations up to a certain accuracy. Our primal-dual framework does not restrict the approximated gradients to be unbiased, offering more flexibility for the gradient approximation design. Convergence analysis with a biased approximated gradient is more challenging than the unbiased case. However, we prove that the proposed primal-dual framework delivers the same order of performance as the stochastic primal-dual algorithm without performativity. \n\nMoreover, our robust primal-dual framework can be applied to any form of distribution families if they have effective gradient approximation methods. Thus, it is more general than the algorithms proposed in two other papers  [Miller et al., 2021] and [Izzo et al., 2021] that focus on the optimality of performative prediction without constraints. Specifically, [Miller et al., 2021] present an algorithm that applies only to the location family, while the algorithm of [Izzo et al., 2021] only works for the exponential family.\n\nOur another technical contribution is the design of an adaptive gradient approximation method for the distribution of the location family. This gradient approximation method attains an $\\mathcal{O}(\\sqrt{T})$ regret using only $\\sqrt{T}+2T$ samples. Lastly, we emphasize that we are the first to study performative prediction under inequality constraints, which is of great significance to the field of performative prediction. Our contributions have been acknowledged and recognized by other reviewers, as evidenced by the citations provided below:\n\n- The reviewer “Puku”: “This paper studies and analyze the optimality of the performative prediction problem under inequality constraints, which is an important yet missing piece in the literature. As far as I know, this is the first paper attempts to provide a solution to this problem. The paper is well-written, easy to follow, and the proposed robust primal-dual method is intuitive. The theoretical analysis is throughout and it also provides empirical study to justify the findings.”\n\n-  The reviewer “NMVA”:  “The proposed primal-dual algorithm is very nice in the sense that (i) the gradient estimators don't need to be unbiased; and (ii) the authors prove a regret bound in terms of the accumulated gradient approximation error. This can be a valuable contribution to the research community.”\n\n-  The reviewer “9 way”: “The motivation behind introducing constraints in performative prediction is strong and justified. The explicit regret guarantees are compelling.”\n\n**Reply to Questions:** \n\n**1. Reply to Question 1:**  Thank you for the question. We agree with the reviewer that the average of the decisions $\\boldsymbol \n{\\theta}_1,\\cdots,\\boldsymbol{\\theta}_T$ is a decision with an optimality guarantee. This is because, under the assumptions made in our paper, we have proved that the performative risk ${PR}(\\boldsymbol{\\theta})$ is convex with respect to $\\boldsymbol{\\theta}$ in Lemma 2. \n\nBy applying Jensen's inequality, we obtain $PR\\left( \\frac{1}{T}\\sum_{t=1}^T \\boldsymbol\\theta_t \\right) \\leq \\frac{1}{T}\\sum_{t=1}^T PR(\\boldsymbol\\theta_t)$. This implies $PR\\left( \\frac{1}{T}\\sum_{t=1}^T \\boldsymbol\\theta_t \\right) - PR(\\boldsymbol\\theta^*) \\leq \\frac{1}{T}\\sum_{t=1}^T PR(\\boldsymbol\\theta_t) - PR(\\boldsymbol\\theta^*) \\leq \\mathcal{O}\\left(\\frac{1}{\\sqrt{T}}\\right)$. \n\nSimilarly, under assumption 3,  each entry of the constraint function $\\mathbf{g}(\\theta)$ is convex. Then, we have \n$\\mathbb{E}\\left[g_i\\left( \\frac{1}{T}\\sum_{t=1}^T \\boldsymbol\\theta_t \\right) \\right]\\leq \\mathbb{E}\\left[ \\frac{1}{T}\\sum_{t=1}^T g_i(\\boldsymbol\\theta_t)\\right] \\leq \\mathcal{O}\\left(\\frac{1}{\\sqrt{T}}\\right)$, $\\forall i\\in[m]$. \n \n\nTherefore, the average of the decisions $\\boldsymbol \n{\\theta}_1,\\cdots,\\boldsymbol{\\theta}_T$ converges asymptotically to the performative optimal point as the iteration number $T$ goes to infinity. \n\n\n**2. Reply to  questions regarding the writing of the paper:**  We thank the reviewer for pointing these out.  We have carefully proofread the manuscript and rectified all the typos. For the question (2), \"the vector valued function $\\mathbf{g}(\\theta)$ is convex\" means that each entry of the vector-valued function $\\mathbf{g}(\\theta)$ is convex.\n\n**We would be happy to discuss with the reviewer should there be any other concerns/questions. Thank you very much!**\n"}, {"review_id": "0sDrmxPuCG", "reviewer": "Reviewer_yrZY", "summary": "The paper attempts to study the problem of learning where the problem instances arise from a distribution. What is special is that this distribution is dependent on the decision-maker. The specific problem is when the distribution is given by a linear shift over a fixed distribution where the degree of shift is given by the decision parameters itself, and the decision parameters itself need to satisfy an inequality constraint. The authors propose a PD algorithm that  (under certain assumptions on the loss function) queries $T+2\\cdot\\sqrt{T}$ samples and violates $\\sqrt{T}$ constraints to yield a $O(\\sqrt{T})$ regret across $T$ rounds.\n", "questions": "How is Eq (4) (gradient of $PR(\\theta)$ wrt $\\theta$ ) on Pg 4 derived from Eq(1) (Definition of $PR(\\theta)$)?\n\nIs there any hope (or negative results) in the case where the distribution does not follow a linear behavior wrt to decision parameter ? I would expect the sample complexity to rise wrt to the complexity of the dependence b/w $\\theta$ and the distribution function $D(\\theta)$. \n\nThis body of work sounds similar to areas where the prediction problem is different from the optimization problem i.e. areas where the performance measure depends on both the unknown problem parameter as well as algorithm design (decision parameter), and the algorithm itself makes decision based on this caveat. \nExamples: \n1. Customizing ML predictions for online algorithms (Anand et al)\n2. Learning Predictions for Algorithms with Predictions (Khodak et al) \nCan you draw any parallels or is there no connection?", "limitations": "Authors have addressed limitation adequately. ", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper makes a good attempt at trying to look at the optimization problem with the inclusion of inequality constraints and it able to consider two simultaneous performance measures, namely, regret and (extent of) constraint violations.", "weaknesses": "The paper promises a study in the direction of general optimization under (decision dependent) uncertainty but only tackles the problem in the limited case where the distribution is linear in the decision space. There is no discussion (or any insight) on how these techniques may generalize for more complicated distributions. The algorithm design itself does not appear to be very novel and uses fairly standard statistical estimation techniques.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and for recognizing our contribution to the research field of performative prediction. Our point-to-point responses to concerns on weaknesses and questions are given below:\n\n**Reply to Weaknesses:**\n\n1.\t> The paper promises a study in the direction of general optimization under (decision dependent) uncertainty but only tackles the problem in the limited case where the distribution is linear in the decision space. There is no discussion (or any insight) on how these techniques may generalize for more complicated distributions. \n\n**Reply:** Thank you for the comment . As replied to Weakness 2 of the reviewer \"PDku\", our robust primal-dual framework is not limited to any distribution forms. The location family merely serves as an application example, and our framework can be applied to other distribution forms with effective gradient approximation methods. For instance, the exponential family considered in [Izzo et al., 2021] with their gradient approximation method can be directly applied to our robust primal-dual framework.\n\nWe thank the reviewer for pointing this out. We have clarified the generalizability of our robust primal-dual framework to other distributions in the revised manuscript.\n\n2.\t>The algorithm design itself does not appear to be very novel and uses fairly standard statistical estimation techniques.\n\n**Reply:** Thank you for the comment. This paper is the first to study performative prediction under inequality constraints. Compared with conventional constrained optimization problems, performative prediction poses several unique challenges. \n\nThe first main challenge is that the data distribution in performative prediction varies with the decision taken, leading to a changing optimization objective, i.e., performative risk. Another challenge is that, in performative prediction, the performative risk remains unknown throughout the optimization process due to the uncertainty of the underlying distribution. Therefore, anticipating performative gradients is a challenging task. Most existing work simplifies this problem by identifying performative stable points. However, performative stability does not necessarily imply performative optimality. In our paper, we aim to find the performative optima, which is more challenging than working on performative stability. \n\nTo address these challenges, we design a robust primal-dual framework. Unlike most existing work on stochastic optimization, our framework does not require unbiased gradient approximations. It is worth noting that convergence analysis with a biased approximated gradient is more challenging than the unbiased case. However, we prove that our robust primal-dual framework delivers the same order of performance as the stochastic primal-dual algorithm without performativity. Our technical contributions have been acknowledged and recognized by the reviewers PDku and NMva,  which is evidenced by their comments on our algorithm.\n\n\n**Reply to Questions:**\n\n**1.  Reply to Question 1:** Thank you for the question.  The derivation of Eq. (4) is given below:\n\nDenote by $p_\\theta(Z)$ the density of $D(\\theta)$. We have\n\n$PR(\\theta) = \\mathbb{E}_{Z\\sim D(\\theta)} \\ell (\\theta; Z)$\n\n$ ~~~~~~~~~~~= \\int_Z \\ell(\\theta; Z) p_\\theta(Z) dZ.$ \n\n\nThen, $\\nabla_\\theta PR(\\theta) = \\int_Z\\nabla_\\theta \\ell\\left(\\theta; Z\\right) p_\\theta(Z) + \\ell\\left(\\theta; Z\\right) \\nabla_\\theta p_\\theta(Z) dZ$. \n\nSince $\\nabla_\\theta p_\\theta(Z) = \\nabla_\\theta \\exp(\\log(p_\\theta(Z))) =p_\\theta(Z) \\nabla_\\theta \\log(p_\\theta(Z))$, we have \n\n$\\nabla_\\theta PR(\\theta)  = \\mathbb{E}_{Z\\sim D(\\theta)} $ \n\n$\\left[\\nabla_\\theta \\ell(\\theta; Z) + \\ell(\\theta; Z)\\nabla_\\theta \\log(p_\\theta(Z))  \\right]$. \n\n **2. Reply to Question 2:** Thank you for the question. As replied to Weakness 1, the proposed robust primal-dual framework can be applied to any distribution families that have effective gradient approximation methods.  \n\nAs pointed out by the reviewer, the sample complexity for gradient approximation depends on the parametric assumptions on the distribution map $D(\\theta)$. For example, [Izzo et al., 2021] assume that $D(\\theta)$ is in an exponential family with density $p(Z, f(\\theta))$. The corresponding gradient has unknown quantities $\\mathbb{E}_{Z\\sim D(\\theta)} \\nabla \\ell\\left(\\theta; Z\\right) $, $ f(\\theta) $ and $\\frac{df}{d\\theta }$. [Izzo et al., 2021] demonstrated that approximating these quantities requires $n\\geq\\mathcal{O}(log(T))$ samples at each iteration. Therefore, the sample complexity of their algorithm is $\\mathcal{O}(T(log(T))$, higher than ours. \n\n **3. Reply to Question 3:**  We appreciate the reviewer for bringing this to our attention. In performative prediction, decisions can actively shape the system being predicted. It considers the feedback loops and interactions between the decisions and the system. In contrast, the basic idea of the prediction problem in 1 and 2 is to incorporate ML predictions in the design of online algorithms to improve their performance. These two approaches are similar in the sense that improving decision-making by estimating unknown quantities. However, several key distinctions set them apart. Firstly, performative prediction involves a dynamic interplay between the decisions made and the underlying system. In contrast, the prediction problem does not influence the system through the decisions taken. Furthermore, in online optimization, the current loss function becomes apparent after the decision has been made, while in performative prediction, the performative risk remains unknown throughout the optimization process. Nevertheless, we believe that research on performative prediction can draw some insights from the prediction problem on incorporating prediction into decision-making. We take it as a promising research direction.\n\n\n**We would be happy to discuss with the reviewer should there be any other concerns/questions. Thank you very much!**"}, {"review_id": "syoNJWaBpY", "reviewer": "Reviewer_9Way", "summary": "The paper provides a new algorithm for performative prediction under general inequality constraints. The proposed algorithm has sublinear regret with respect to the performative optimum if the distribution map follows the location family model. The theory is supported by simulations.", "questions": "In line 45, when you say \"exponential structure\" you mean exponential families?\n\nLine 148, denoted -> denote.\n\nI don't understand why you have both eta and delta. In problem (2) they appear together. I don't understand why they are tuned separately in the end? Why are they not treated as a single parameter?\n\nThe notation in Algorithm 1 is strange. What do you mean by Z_t \\sim \\D(Z_0 + A-hat_t theta_t)? Also, shouldn't it be the true A and not A_t-hat?\n\nPlease define PD-PS used in line 306.\n\nLine 320, sensitive -> sensitivity.\n\nLine 323 says accuracy decreases. You mean error decreases?", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The motivation behind introducing constraints in performative prediction is strong and justified. The explicit regret guarantees are compelling. I thought Example 1 was well-motivated, clear, and a great example to keep in mind throughout. Section 3 is well-written and gives a clear step-by-step outline of the main method. The connection to existing work is thorough.", "weaknesses": "The novelty has limitations. The main method combines existing ideas in the literature quite directly. The method for constructing a zeroth-order estimate of the gradient follows the same recipe as the two-stage method of Miller et al., and in a way this is the heart of the proposed method. This I see as the most relevant weakness. Below I'm including additional points.\n\nIt is not clear what the meaning of the time horizon T is in your analyses. Normally this should be the number of collected samples. But in your paper this is not the case, and I think that for this reason your T has a somewhat arbitrary meaning. I would rewrite the result statements to make T the total number of collected samples (I don't think this should change your rates). This is important especially because when you tune n you set it to grow with T as sqrt(T).\n\nAssumption 1 is just there to ensure convexity of the objective, right? If so, maybe it's cleaner to state that assumption directly, and give the conditions in Assumption 1 as one way to satisfy the convexity condition. Otherwise, the way things are stated right now, your Example 1 wouldn't be handled by the assumptions?\n\nIn Lemma 3 (and other results that rely on this lemma) I would probably write something like \"there exists a delta(\\eta, L_g) such that...\" Right now the interval for delta is too cumbersome.\n\nYou mention that derivative-free methods such as Flaxman et al. could be used for your problem. I think it would be a good idea to spell out exactly what they give you, because although you would lose dimension-dependent factors the results would be applicable much more broadly (all convex problems, not just location families). Location families are interesting but they are too specific.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your review and for recognizing our contribution to the research field of performative prediction. Our point-to-point responses to concerns on weaknesses and questions are given below:\n\n**Reply to Weaknesses:**\n\n**1.** Thank you for the comment. The main contributions of this paper are listed below:\n\n- We are the first to study the performative prediction problem under inequality constraints, which is ubiquitous in the real world but currently understudied. \n- We developed a robust primal-dual framework that requires only approximate gradients up to an accuracy of $\\mathcal{O}(\\sqrt{T})$, yet delivers the same order of performance as the stochastic primal-dual algorithm without performativity.\n- Based on this framework, we propose an adaptive primal-dual algorithm for location families, which achieves $\\mathcal{O}(\\sqrt{T})$ regret and constraint violations, using only $\\sqrt{T} + 2T$ samples.\n\nWe understand that the reviewer is suggesting that our adaptive parameter estimation for the location family bears some resemblance to the two-stage algorithm in [Miller et al., 2021]. However, they are different approaches. More importantly, we would like to emphasize that parameter estimation does not constitute the main contribution of this paper. The location family serves as a mere application example of our robust primal-dual framework, which can be applied to other distribution forms with effective gradient approximation methods. Our contributions have been recognized by other reviewers, as cited below.\n\n- PDku: “This paper studies and analyze the optimality of the performative prediction problem under inequality constraints, which is an important yet missing piece in the literature. The proposed robust primal-dual method is intuitive. The theoretical analysis is throughout and it also provides empirical study to justify the findings.”\n- NMva: “The proposed primal-dual algorithm is very nice in the sense that (i) the gradient estimators don't need to be unbiased; and (ii) the authors prove a regret bound in terms of the accumulated gradient approximation error. This can be a valuable contribution to the research community.”\n\n**2.**  Thank you for the comment.  In our algorithm, the time horizon $T$ refers to the number of iterations or decisions taken. The term \"time horizon\" follows the field of online optimization. We employ the number of iterations in our convergence analysis because it better reflects the convergence speed of an optimization algorithm. Generally, the convergence speed is of more concern than the number of samples when evaluating the rate of convergence of an algorithm. We agree with the reviewer that changing $T$ to the number of samples will not affect the rate of our algorithm since the required samples are in the same order as the number of iterations.\n\n**3.**  $1)$ Thank you for the comment. Assumption 1 pertains to the properties of the loss function, which is commonly made in the literature of performative prediction. Under Assumption 1, we demonstrate the convexity of the performative risk for distribution maps within the location family. Directly assuming the convexity of the performative risk is uncommon in the literature, and hence, we do not do so. \n\n$2)$  Example 1 serves to demonstrate a practical application of performative prediction with constraints. The loss function of Example 1 does not need to meet the assumptions of our algorithm. To apply our algorithm to Example 1, we can add a regularizer $||\\theta||_2^2$ on its loss function to make it strongly convex. This approach is widely used in the literature, such as in [Narang et al., 2022] and [Mandal et al., 2022]. \n\n**4.**  Thank you for the helpful comment! We have changed the related descriptions throughout our paper according to this comment.\n\n**5.**  Thank you for the comment. Derivative-free methods approximate the gradient $\\nabla_\\theta PR (\\theta)$ by querying the objective at random points around the current iterate. For example, by the derivative-free method in [Flaxman et al. (2005)], the gradient $\\nabla_\\theta PR (\\theta)$ can be approximated as $\\nabla_\\theta PR (\\theta) \\approx \\frac{d}{\\xi} \\mathbb{E}PR(\\theta + \\xi u)u$. The analysis results in [Flaxman et al. (2005)] demonstrate that the convergence bound of this method is in $\\mathcal{O}(d^2)$ w.r.t. the data dimension $d$.\n\n\n**Reply to Questions:**\n\n**1.**  Thank you for the question. As you correctly pointed out, \"exponential structure\" in line 45 refers to exponential families. To avoid misunderstanding, we have clarified this in the revised manuscript.\n\n**2.**  Thank you for the helpful comment!  We have rectified this typo. \n\n**3.**  Thank you for the question. $\\eta$ is the stepsize of the algorithm, and $\\delta$ is a control parameter that determines the strength of the regularizer $-\\frac{\\delta\\eta}{2}||\\lambda||^2$. Both parameters appear in the regularizer term for convergence analysis purposes. We want to carefully design the values of these two parameters to eliminate some $\\lambda$-related terms in the convergence bound. This careful selection is necessary to improve the efficiency of our algorithm.\n\n**4.**  Thank you for the question. We have revised the notation to $Z_t\\sim D(\\theta_t)$, which means that the sample $Z_t$ is drawn from the distribution $D(\\theta_t)$.\n\n**5.**  Thank you for the helpful comment! We have included a more detailed description of the PD-PS algorithm in our manuscript. PD-PS stands for the primal-dual algorithm used to find the performative stable points. The algorithm is similar to APDA but uses only the first term in Eq. (8) as the approximate gradient. \n\n**6.**  Thank you for the helpful comment! We have rectified this typo.\n\n**7.**  Thank you for the helpful comment! We have revised the description.\n\n\n**We would be happy to discuss with the reviewer should there be any other concerns/questions. Thank you very much!**\n"}]

Author rebuttal:

Meta-review: This paper generated quite a bit of discussion bother during the author-reviewer conversations and after. Overall, it had two scores of 7, while the support from other reviewers was lukewarm. This state along with the average score puts the paper near the borderline of the acceptance-rejection region for the conference.

On one hand, the reviewers appreciate that this work addresses a missing piece in the literature on performative prediction and that it is written well. On the other hand, even staunch supporters point out that the restrictions here are severe, e.g., operating only a particular family of linearly parametrized distributions and strong convexity. In totality, I agree that the authors study a new variation of the performative prediction problem and the work could be valuable to the community, and I also concur also with Reviewer 9Way that the proposal here combines existing techniques (e.g., dual descent is a common approach in online convex opt with approximately satisfied functional constraints), thereby offering possibly limited technical novelty. 

I am tentatively recommending to accept the paper, although I do encourage the authors to see if they can broaden the scope of applicability of their results (beyond linear parametrized distributions) even at the cost of some dip in clarity.
Decision: Accept (poster)