Stochastic Optimization Schemes for Performative Prediction with Nonconvex Loss
Authors: Qiang LI
Hoi To Wai
Venue: NeurIPS 2024 poster (2024)
Keywords: Non-convex optimization
Performative prediction
Stochastic optimization algorithm
Primary area: optimization
TL;DR: This paper studies the performative prediction with smooth but possibly non-convex loss and analyzes a greedy deployment scheme with stochastic gradient descent algorithm.

Abstract: This paper studies a risk minimization problem with decision dependent data distribution. The problem pertains to the performative prediction setting in which a trained model can affect the outcome estimated by the model. Such dependency creates a feedback loop that influences the stability of optimization algorithms such as stochastic gradient descent (SGD). We present the first study on performative prediction with smooth but possibly non-convex loss. We analyze a greedy deployment scheme with SGD (SGD-GD). Note that in the literature, SGD-GD is often studied with strongly convex loss. We first propose the definition of stationary performative stable (SPS) solutions through relaxing the popular performative stable condition. We then prove that SGD-GD converges to a biased SPS solution in expectation. We consider two conditions of sensitivity on the distribution shifts: (i) the sensitivity is characterized by Wasserstein-1 distance and the loss is Lipschitz w.r.t.~data samples, or (ii) the sensitivity is characterized by total variation (TV) divergence and the loss is bounded. In both conditions, the bias levels are proportional to the stochastic gradient's variance and sensitivity level. 
Our analysis is extended to a lazy deployment scheme where models are deployed once per several SGD updates, and we show that it converges to an SPS solution with reduced bias. Numerical experiments corroborate our theories.

Stochastic Optimization Schemes for Performative Prediction with Nonconvex Loss
Qiang Li
Hoi-To Wai
Department of Systems Engineering and Engineering Management The Chinese University of Hong Kong, Shatin, Hong Kong SAR of China (liqiang, htwai]@se. cuhk. edu.
Abstract
This paper studies a risk minimization problem with decision dependent data dis- tribution. The problem pertains to the performative prediction setting in which a trained model can affect the outcome estimated by the model. Such dependency creates a feedback loop that influences the stability of optimization algorithms such stochastic gradient descent (SGD). We present the first study performative prediction with smooth but possibly non-convex loss. We analyze a greedy deploy- ment scheme with SGD (SGD-GD). Note that in the literature, SGD-GI is often studied with strongly convex loss. We first propose the definition of stationary performative stable (SPS) solutions through relaxing the popular performative sta- ble condition. We then prove that SGD-GD converges to biased SPS solution in expectation. We consider two conditions of sensitivity the distribution shifts: the sensitivity is characterized by Wasserstein-11 distance and the loss is Lipschitz w.r.t. data samples, or (ii) the sensitivity characterized by total variation (TV) divergence and the loss is bounded. In both conditions, the bias levels are propor- tional the stochastic gradient's variance and sensitivity level. Our analysis extended to a lazy deployment scheme where models are deployed once per several SGD updates, and we show that converges to SPS solution with reduced bias. Numerical experiments corroborate our theories.
Introduction
When trained models are deployed in social contexts, the outcomes these models aim to predict can be influenced by the models themselves. Taking email spam detection email service providers design filters to protect their users by identifying spam emails. On the other hand, spammers aim to circumvent these filters distribute malware and advertisements, Each time a new classifier is deployed, spammers who are interspersed within the general population may alter the characteristics of their messages evade detection. The above example pertains to the strategic classification problem [Dalvi et al., 2004, Cai et al., 2015, Hardt et al., 2016, Björkegren et al., 2020] and can be modelled by dataset shifts (Quinonero-Cande
example. On one hand,
et al., 2022].
The scenarios described can be captured by the recently proposed performative prediction problem, which called the above dataset shift phenomena the 'performative' effect. Perdomo et al. [2020] proposed to study the risk minimization problem with a decision deeeedend data distribution:
mingeR V(0) := R [e( Z)],
where ((0: is loss function that is continuously differentiable with respect to (w.r..) 0 for any given data sample E Z, and Z C IRP is the sample space. The dependence on in D(0) explicitly captures the distribution shift effect of prediction models data samples. The objective function V V(0) is also known as the performative risk.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Literature
Nevx-é
Nevx-V
Sensitivity
Algorithm
Rate
000
[lzzo al., 2021]
X
Loc.
2-Phase
O(T :
=
[Miller et al., 2021]
X
W
2-Phase
O
min ((0)
[Mendler- Mendler-Dünner et al., 2020]
X
W1
SGD-GD
O(T-1)
PS
[Mofakhami et al., 2023]
XI
X"
RRM
Lincar
PSt
TV or W1
SGD-GD
O(T-5)
O(c)-SPS
This Work
TV or W1
SGD-Lazy*
O
((P))-SP
Table 1: Comparison of Results in Existing Works. "Sensitivity" indicates the distance metric
imposed on D()) when the latter is subject to perturbation, given in the form d(D(0), D(0')) s
ello 0'll such that -)(--) is distance metric between distributions. '0 indicates the type of convergent points: 'PS' refers to performative stable solution [cf. (4)), "SPS' refers to Def. 1.
11z0 et al. [2021] assumed that D()) belongs to the location family, i.e., D(0) (f))
*oofakhami et al. [2023] considered f(O: 2) = {f)( y) with strongly convex E(- y). The RRM requires solving non-convex optimization at each recursion.
* *SGD-Lazz refers the SGD method with lazy deployment scheme, which fixes the deployed model for K iterations before the next deployment; see $4.
The decision variable O in (1) affects simultaneously the distribution and the loss function. As such, optimizing V(0) directly is often difficult. Mendler-Dümme et al. [2020] considered the following stochastic gradient (SGD) recursion: for any t 2 0 and let 7 > 0 be stepsize,
01+1- 0 7+1 Zi+1), where Z1+1 D(O.).
The above is known the greedy deployment scheme with SGD (SGD-GD), where the learner deploys the current trained model O, before drawing samples from D(O.). The SGD-GD scheme describes a training procedure when the learner is unaware of the performative phenomena with the data distribution D.)), which is plausible in many applications. Relevant studies to (2) include lazy deployment where the learner deploys new model only once every few iterations, repeated risk minimization; see Hendler-Dünnee et al., 2020, Perdomo et al., 2020, Zmic et al., 2021].
Existing convergence analysis of (2) are limited to the case when E(O; z) is strongly convex! w.r.t. O. Perdomo et al. [2020] introduced the concept of performative stable (PS) solution as the unique minimizer of (1) with fixed distribution. The PS solution, while being different from optimal or stationary solution to (1), is shown to be the unique limit point of the recursion (2) provided that the sensitivity of the distribution map (--), measured w.r.t. the Wasserstein-1 (W1) distance, is upper bounded by a factor proportional to the strong convexity modulus of E(O; x) Mendler-Düünne et al., 2020]. Furthermore, such convergence condition is proven to be tight [Perdomo et al., 2020] and the analysis has been extended to proximal algorithm [Drusvyatskiy and Xiao, 2023], online optimization [Cutler et al., 2023], saddle point seeking [Wood and Dall' Anese, 2023], multi-agent consensus learning [Li et al., 2022], non-cooperative learning [Wang et al., 2023, Narang et al., 2023, Piliouras and Yu, 2023], sepeedde learning [Brown al., 2022, Li and Wai, 2022], etc.
This paper provides the first analysis of SGD-GD and related stochastic optimization schemes in performative prediction when {(0; z) is smooth but possibly non-convex. This is more common scenario in machine learning than the strongly convex loss considered in the prior works, c.g., it covers the case of training neural network (NN) models. We notice that existing works are limited to imposing structure on the loss function ((0: 2) and the distribution D(0), utilizing advanced algorithms that demand extra knowledge on D(0), etc., as we overview below.
Related Works. In the non-convex setting, the most related work ours is [Mofakhami al., 2023] which proved that a variant of PS solution can be found when training NN in the performative prediction setting, i.e., a special case with non-convex loss. However, their analysis is restrictive: (i) it requires a loss function of the form f(0; z) = {(f(()) y) where E(j; y) is strongly convex w.r.t. I. (ii) it only analyzes the case of training NN using repeated risk minimization (RRM) procedure which exactly minimizes a non-convex objective function at each step. In comparison, we concentrate on stochastic (first order) optimization schemes and require only smoothness for 2(;
Note that (0)) is still non-eo.vex.

---

Other works departed from tackling the PS solution and considered alternative algorithms to directly minimize V@0). For example, Roy et al. [2022] assumed that unbiased estimates of (V(@) is avail- able and studied the convergence of stochastic conditional gradient algorithms towards stationary solution of ( Li and Wai [2022] assumed bounded biasedness w.r.t. (V()) in (2) and show that (2) converges to a biased stationary point of V(0). Notice that estimating V (V()) requires knowledge on D(0) which has to be learnt separately. To circumvent this difficulty, two phases algorithms are studied in [Miller et al., 2021, Izzo et al., 2021] that learn D(0) via large batch of samples at the first stage, then optimize later (see [Zhu et al., 2023] for a two-timescale type online algorithm), derivative free optimization are studied in [Miller et al., 2021, Ray et al., 2022, Liu et al., 2023], and confidence bound methods in [Jagadeesan et al., 2022]. In addition, Miller et al. [2021] proposed a mixture dominance assumption that can imply the strong convexity of ( We remark that [Zhao, 2022] studied conditions to ensure V(0) to be weakly convex. Our work does not require such advanced algorithms and show that stochastic (first order) optimization converges towards a similar solution as the PS solution. We display a comparison between these related works in Table 1.
Our Contributions: This work provides the first analysis of stochastic gradient-based methods for performative prediction with smooth but possibly non-convex losses. Our contributions are:
We propose the concept of stationary performative stable (SPS) solutions which is a relaxation of the commonly used performative stable (PS) condition [Perdomo et al., 2020]. The relaxation is necessary for handling non-convex losses using first-order methods.
We show that the stochastic gradient method with greedy deployment (SGD-GD) finds biased SPS solution. Assume that the distribution shift is e-sensitive, i.e., it holds d(D( D(O))) < <ll0- - 0'|l for some distance measure d((,.) between the shifted distributions D(0), (00",, SGD-
GD converges at a rate of (T- in expectation to an (c)-SPS solution. The hias level is further improved ((e2) when the gradient is exact.
Our analysis relies on constructing time varying Lyapunov function that may shed new lights for non -rnddreddent stochastic approximation [Dieuleveut et al., 2023]. We studied two alternative conditions on the distance metric between distributions. When d(..-) is the Wasserstein- I distance, SGD-GD converges to a biased SPS solution for Lipschitz loss function. When d(:,-) is the total variation (TV) distance, SGD-GD converges biased SPS solution for bounded loss function.
We extend the analysis to the lazy deployment scheme with SGD Mendler-Dünnee et al., 2020]. The latter scheme finds an SPS solution with reduced bias as the epoch length of lazy deployment grows.
Lastly, we provide numerical examples on synthetic and real data to validate our theoretical findings. The rest of this paper is organized as follows. $2 introduces the problem setup and assumptions for establishing our convergence results of SGD-GD. Furthermore, we highlight the challenges in analyzing non-convex performative prediction. $3 introduces the concept of SPS solutions and presents the convergence results for SGD-GD under two alternative assumptions shifts. We also outline the use of a time varying Lyapunov function to handle the dynamic nature of SGD-GD. $4 shows the results for the lazy deployment scheme. Lastly, $5 provides numerical experiments to illustrate our results.
the distribution
Notations. Let Rd be the d-dimensional Euclidean space equipped with inner product (-) and induced norm ||>||| / (x 2²). Let S be (measurable) sample space, and μ, are two probability measures defined as S. E[-] denotes taking expectation w.r.t all randomness, Ex[-] := EE, [-[F)]] means taking conditional expectation on the filtration J, := a ((Op,, O,, O,,... Oe))), where o-)) the sigma-algebra generated by the random variables in the operand and {0.) is the sequence of iterates generated by the SGD-GD scheme (2).
2 Stationary Condition for Performative Stability
This section prepares the analysis of (1) with SGD-GD and related schemes in the non-convex loss setting. To fix idea, we define the decoupled performative risk and the decoupled partial gradient:
J J(0:: 02) EZ=DDe,) ((0:))) VJ(0 02) Ez=D(e.) [VE(0;; Z)].
(3)
3

---

Observe that while V(0) = 0) V.(000) + VV(@) in general since VJ(0; 0) only represents a partial gradient of (0): see [lzzo et al., 2021]. In (2), the conditional expectation of the stochastic gradient update term satisfies E, z+) VJ(0,; 0²).
If the loss z)::)) is strongly convex w.r.t. 0, then the decoupled performative risk [@; 0) admits a unique minimizer w.r.t. 0 for any 0. It has hence motivated [Perdomo et al., 2020] to study the performative stable (PS) solution Ops which is defined as fixed point to the map
T(0)= arg mingeR [(; 0). i.c., PpS T(Ops).
(4)
In the above, the uniqueness and existence of Ors follows by observing that T-)) is contraction and only if the sensitivity of D(0), i.e., the 'smoothness' of D()) w.r.t. 0, upper bounded by the inverse of condition number of E(0; z). The convergence of SGD-GD follows by analyzing (2)
as a stochastic approximation (SA) scheme for the repeated risk minimization (RRM) procedure 0 + T(0) [Mendler-Dünnee et al., 2020].
For the case of non-conver loss in this paper, the analysis becomes more nuanced since the map T(-) is no longer well-defined, e.g., there may exist more than one minimizers to minę J(0; 0). Our
remedy is to concentrate on the following non-convex counter part to the PS solution:
Definition 1. (6 stationary performative stable solution) Let 8 > 0, the vector 05-SPS Rd is said to be an ó stationary performative stable (6-SPS) solution of (1) if:
VJ(Os-SPs:: (s-Ss))) [Ez-D(00-sPp) [V((O> 2)] 6.
(5)
We also say that 0SPs is an (exact) SPS solution if it satisfies (5) with 5 = 0. In other words, 5 2 0 measures the stationarity of solution. Notice that if (() is strongly convex w.r.t. 0, then an SPS solution is also a PS solution defined in [Perdomo et al., 2020].
Although (5) is similar to the usual definitions of stationary solution in smooth optimization, there a subtle but critical difference since ( 0) may not be the gradient of any function in A. For example, consider ((0; =) = (1/2) - zil and (0) ((A0, I) for some square but asymmetric matrix A, the map (.((0; 0) = (1 (1-AA] A)0 has a Jacobian of / -- A which is not symmetric. Furthermore, we observe that the mean field for SGD-GD scheme (2) (O; 0), which is a gradient. The SGD-GD scheme is thus a special case of non-gradient SA scheme [Dieuleveut et al., 2023].
To get further insight, investigated in [Dieuleveut al., 2023], common analysis framework of non moo-ooonniinn gradient SA scheme is by identifying a smooth Lyapumov function linked to the recursion (2). When f(:; z) is strongly convex, we may study the Lyapunov functions the squared distance |0 - Orsl| 2 [cf. (4)] It can be shown that the properties required in [Dieuleveut et al., 2023] are satisfied under the conditions analyzed by [Mendler- Dünner al., 2020]. However, in the case of non-convex loss, identifying a suitable Lyapunov function for non-gradient SA scheme is hard. In the next section, demonstrate how to address this challenge by identifying a time varying Lyapunov function for SGD-GD.
3 Main Results
This section presents theoretical results on the SGD-GD scheme with non-convex loss. We first show how to construct time varying Lyapunov function tailor made for (2). We then show the convergence of SGD-GD under two different sets of conditions.
We introduce two basic and natural assumptions on the risk minimization problem (I):
A1. For any z E Z, there exists a constant 2 such that
-))(0=)) v - < L 110 0'11, V0,0 0' E Rd
(6)
where vE(0;2) z) denotes the gradient of ((; w.r.t. O. Moreover, there exists a constant 8 -00 such that {(0) 2 E* for any dR.d.
A2. For any fixed 0,, 0g E IRd, the stochastic gradient v ; 2). Z D(02) is unbiased such that EZ-D(O.) (V((,; Z)] = ( 02), and there exists constants Tp, 01 2 0 such that
E Ez~D(en)
VE(0;: VJ(0,; 02]0 < of + of [V](0; 02)1

---

Note that AI, 2 are standard assumptions that hold for a wide range of applications and the respective stochastic optimization based training schemes. For instance, Al requires the loss function to be smooth, while A2 assumes the stochastic gradient estimates to have a variance that may grow with [0 1; 02) I22 For the non performative prediction setting where the data distribution is not shifted by 0, i.e., D(O)= = DD these assumptions guarantee that SGD algorithm (i.e., SGD-GD with stationary solution of (1) with suitable step size schedule [Ghadimi and Lan, 2013]. .013..1.. In particular, in this case Al implies that (E= Z)] is a smooth function and serves Lyapunov function for the SGD algorithm.
Z++1 D) converge
In this light, might be tempting to use the performative risk V(0) [ef. (1) as the Lyapunov function for (2) and directly adopt the analysis in [Dieuleveut et al., 2023]. However, the condition A is insufficient to guarantee that V()) smooth, and the mean field of (2) may not be aligned with (O). Instead, from A1, 2, proceed with descent-like lemma for the iterates of SGD-GD:
Lemma 1. Under AI, 2. Suppose that the step size satisfies sup f S 1/(L(1 of)), then for any t 2 0, the sequence of iterates {0r) generated by SGD-GD (2) satisfies
7--1 VJ(O,;
s J(,,; 0.) [1 fo
(8)
Proof. Fix any E applying Al and the recursion (2) lead
L
((0++132) S ((0,;)) - 7 (Vi(O,=)) Ve(O,; Z++1) + VeE 2411
(9)
for any 2 0. Note that = E Z can any fixed sample while Ze+1 is the r.v. drawn from D(0,) ) in (2). Let po, (z) 2 0 denotes the pdf of D(),). We then multiply pe, (2) on both sides of the inequality and integrate w.r.t. 2 E Z, i.e., taking the operator f2())oo, (z)dz. This yields
Inet1 2
1(0++1:0,) < J(O;; 0.) 1 (V. 0.) Ve(0;; Zz+1))
|V Z+1)) (10)
since [((0:))po, (z)d= = J(0; 0,) according definition (3). We next evaluate the conditional expectation, E.l--) on both sides of the above inequality
LitH1 2
[[ J(0, - 70+1 [,00
0.11
E. ((I (1I)
Using A2, we note that F, [ ((,;; 2++1) oه (1 f 0,) Reshuffling terms
and using the step size condition yield the desired result (8); see $A for detailed proof.
For sufficiently small 1 O and when 0 is not SPS, eq. (8) implies the descent relation Ex[J(0++1: 0,)] < 0z). This suggests that at the ith iteration, the function Je(O)= == J(; 0,)
may serve as Lyapunov function for the SGD-GD scheme. Meanwhile, (O) time varying Lyapunov function. The said descent relation does not necessarily imply the convergence towards an SPS solution. Instead, the first term on the right hand side of (8) can decomposed as:
(e,) - J. = (l,) - Je41(0144)) + [[J[41 - Je Je(0(+1))
(12)
residual
The first part is a differeence-of-sequeee which is summable, while the second part is a residual term. The convergence of SGD-GD with non-convex losses hinges on bounding the latter residual. Taking closer look, the residual is the difference of evaluating 0.41 on Je(-) and Je+1 i...
B
Z') J.(0.+ = [B2--100) (( (1(0
0(0 Z)]
(13)
The above further depends the differences between the distributions D(0,). ((0++)), i.e., the sensitivity of the data distribution w.r.t. perturbation in Next, we study sufficient conditions that imply the convergence of SGD-GD through bounding [[]++1 (,)+++1).
5

---

3.1 Sufficient Conditions for Convergence of SGD-GD
From (8), we anticipate the convergence of SGD-GD towards biased SPS solution if it holds ([ J, [1)+++]]] = (
0 ||]) 0 Z+11)]l), Now, as seen from (13), establishing such relation would require ( satisfy a certain sensitivity criterion when subject to perturbation in 0. Our subsequent discussions are organized according to various distributional distance measures on sensitivity.
Wasserstein-1 Sensitivity, Our first set of conditions uses the Wasserstein-1 distance for measuring the sensitivity of data distribution. The measure is commonly used in the studies of performative prediction, e.g., as pioneered by [Perdomo et al., 2020, Mendler-Dünner et al., 2020]:
W1. (e sensitivity w.r.. Wasserstein-1 distance) There exists 2 such that (i(D(0), D(0') S <'1l
(14)
for any 0.0' E Rd. Notice that the Wasserstein-1 distance is defined as Wi(:.) =
inf PEP(..) E(z,"")>< [||= [[||===']] I where P (D()). D (0') is the set of all joint distributions on Z whose marginal distributions are D (e").
In this case, we require the loss function to be Lipschitz continuous w.r.t. shifts in the data sample z. W2. There exists a constant Lo > 0 such that for all 2, z' E Z, and Rd.
|{(0: 2) ((0) 2') ) I Lo || 2'11-
(15)
Our key observation is that the above conditions imply the desired Lipschitz continuity property on J(;:)). ) In fact, we have:
Lemma 2. Under W1, 2. For any 11,02, 0 E Rd,, it holds
[J(0,;)) - 0(0:02) S Loe ||0 021l
(16)
The proof, which a variant of [Drusvyatkkiy and Xiao, 2023, Lemma 2.1], can be found in SB.
TV distance Sensitivity. Although W1 holds for number of applications, such as the location family distributions (e.g.. [Miller et al., 2021, Perdomo et al., 2020, Narang et al., 2023]), the assumption of Lipschitz loss function in W2 can be difficult to verify, especially if we want Lo (and thus the Lipsehitz continuity constant of E(O:)) given by Loe) to small. As an alternative, we consider a slightly stronger sensitivity condition on D(0) via the total variation (TV) distance.
C1. (e sensitivity w.r.t. TV distance) For any 0 O' E Rd,, there exists constant 2 0 such that 8rv (Dv()) D(O))) S 0011-- where (rv(:))) is the total variation distance defined as drv suP (APA)(AAA m(A) J - PP) such that p, v.v are two probability measures supported on Z and (() denotes their probability distribution functions (p.dfs)).
(17)
Although Cl is slightly strengthened from W1, it allows to relax the Lipschitz continuity assump- tion W2 on the loss. Particularly, we consider replacing W2 by:
C2. There exists a constant max 2 O such that supoer" [(0:2)] < Emaz-
The above condition requires .(:: to be uniformly bounded. Compared to W2, it can be easier to verify and feaz typically small. For example, it holds with Lmax for the case of sigmoid loss.
Similar to W1, 2, we observe that the above conditions imply J(0:-) is Lipschitz continuous:
Lemma 3. Under CI, 2. For any 0,, 02, 0 E IRd, it holds that
(J(0;0)) J(; 02)l < 2mmant 0 - 021l
(18)
See &C. The only difference with Lemma 2 is that (18) has different Lipschitz constant.
Remark 1. It is worth noting that in lieu of CI, Mofakhami al. [2023] assumed the following sensitivity condition with respect to the Pearson x² divergence, i.e.,
(D(()) = (poo()) - po (2))² dz = O-1)fo(-) for (-113)
(19)
(=

---

where f-)-) represents the output of a neural network parameterized by 6. po(.) and per (-) are the
probability density functions (p.d.fs) of the induced distributions D and D(O'), respectively.
Our TV distance sensitivity condition in CI constitutes a weaker condition since for any bounded sample space Z, the following holds:
W1 (((()) & diam(Z) 8rv (D(()) diam(Z) 2
V (x))))))
as shown in [Gibbs and Su, 2002, Sec. 2J, where diam(Z) sup,,>'e z'1l denotes the diameter of the sample space.
3.2 Convergence SGD-GD with Non-convex Loss
Equipped with Lemmas 2, 3, we are ready to present the convergence result for SGD-GD with smooth but non-convex losses. Observe the following theorem whose proof can be found in $D:
Theorem 1. Under A1, 2. Let the step sizes satisfy sup121 To S 1/( of)) Moreover, let
== Lo if WI, 2 hold, or L = mas if C1, 2 hold.
(20)
Then, for any 2 1, the iterates (0: (220 generated by SGD-GD satisfy
T-1
L
T-1
V.]0; (.), 0,)1 Ao + Le (oo + +1+ of)
Σ
7-1 000
Σ
n+1
(21)
4
t=0
1=0
where Ao == J(Ou; 0o) - l. is an upper bound to the initial optimality gap of performative risk.
Using fixed step size schedule, we simplify the bound as: Corollary 1. Under AI, the alternative conditions WI, 2, CI, 2. Let T 2 be the maximum number of iterations and set "/t 1/VT.. Let T be random variable chosen uniformly and
independently from {0, 1, T 17-1.. 1}. For any T 2 L² + ot)?, , the iterates by SGD-GD satisfy
L
1
E (NTJ(OT:0T)) 0T)1 < 4 Do
2 00
+ +4Lc (oo +1 (1+ of)
(22)
VT
bias
As T' + oc, the first term in (22) vanishes as O(I/vT) and the above shows that the SGD-GD scheme finds O(a, + (1 + of) S-SS solution. This yields the first convergence guarantee for performative prediction with non-convex loss via a stochastic optimization scheme.
Lastly, an interesting observation is that the bias level is controlled at O + (1 + c²) The latter estimate highlights the role of the stochastic gradient's variance. see this, let us concentrate on the case when is small. When stochastic gradient is used such that dp > 0, SGD-GD finds an O(c)-SPS solution; while with deterministic gradient, i.e., when Ve(O,; 2++1) = [ 0.) with ao
0, SGD-GD finds an O solution. Such distinction in the bias levels indicate that a unique property of non-convex performative prediction where the asymptotic performance of SGD-GD is sensitive to the stochastic gradient's 's noise variance. Furthermore, our result suggests that adjusting the minibatch size in SGD-GD may have a significant effect on reducing the bias level since dg, 01 can be controlled by the latter.
Remark 2. Prior analysis in [Mendler-Dimmer al., 2020, Drusvyatskiy and Xiao, 2023) showed that with μ strongly convex loss E(;;;), both the existence/uniqueet convergence of SGD-GD to the PS solution critically depend on the condition e < u// (in addition to our Al. 2, W1). When e >> p// L, it is shown that the SGD-GD scheme may even diverge. In contrary, Theorem does not exhibit such an explicit condition on for the convergence results (21), (22) to hold. This happens because our result requires the loss function itself to be Lipschitz [cf. W2] or bounded [cf. C2], which may not be satisfied by their strongly convex losses.
of the PS solution and the
4 Extension: Lazy Deployment Scheme with SGD
Implementing the SGD-GD scheme (2) requires deploying the latest model every time when drawing samples from D--). This may be difficult to realize since deploying new classifier in real time can
7

---

be time consuming. As inspired by [Mendler- Dünerr et al., 2020], this section studies an extension of (2) to the lazy deployment scheme where the new (prediction) models are deployed only once per several SGD updates.
To describe the extended scheme, let K denotes the epoch length of lazy deployment, we have
0 = 0., - Ve( where Zt,A-1 ~ D(O;), k = 0..., K 1,
(23)
0.+1- 1,+ 0s.k-
For simplicity, we focus on the case with a constant step size 7 > O. Observe that the lazy deployment scheme is a double-loop algorithm where the index denotes the number of deployments and the index & denotes the SGD update. To analyze the convergence of (23), we further require the stochastic gradient to be uniformly bounded:
A3. There exists constant G 2 0 such that suppgRd, |[ =) G.
Despite being a stronger assumption, the above remains valid for practical non-convex losses, e.g.. sigmoid loss. We observe the following convergence results whose proof is in SE:
Under A1, 2, 3, and the alternative conditions W1, 2, Cl, 2. Let > 1 be the maximum number of deployments to be run, we set 7 = (/(TT)T) and let T be a random variable chosen uniformly and independently from 10,1,-.. 1. .T' - 1}. For any T 2 L + of)²/K² /K2, the iterates generated by the lazy deployment scheme with SGD (23) satisfy:
Theorem 2.
8A0 VT
4L
2LG
8Le (v2Koo + +2(K + +of)le),
E | S
(24)
KVT
3T
K
where we recall that L was defined in (20) and Do = J(0o; 0o) - l.
In (24), the first three terms decay as O(IVTT) similar to SGD-GD, the last term simplifies to ((L))² ) The lazy deployment scheme (23) finds an ((Le)))-SPS solution when T 00, K + oo, contrasting with SGD-GD which admits a bias level of ((Lc).
We remark that the above result can be anticipated. During the tth deployment, (23) runs an SGD recursion for ming [0; 0.) where will find a stationary solution for the non-convex optimization as K + oo. The lazy deployment scheme resembles RRM and we expect that it may find a reduced bias SPS solution as inspired by [Mofakhami al., 2023] which studied a similar algorithm.
Numerical Experiments
We consider two examples of performative prediction with non-convex loss based synthetic data and real data. All simulations are performed with Pytorch on a server using a Intel Xeon 6318 CPU. Additional results can be found in $F.
Synthetic Data with Linear Model. We first consider a binary classification problem using linear model. To enhance robustness to outliers, we adopt the sigmoid loss function [Ertekin et al., 2010];
(0::)) == + explce y(u )))) -1 + (8/2) 2|0]].
(25)
For small regularization 3 > 0, e(: 2) is smooth but non-convex. To define the data distribution, we have set of unshifted samples D (11 )m with feature x; Rd and label y; E {+1).
For any 0 Rd D(0) is uniform distribution on m shifted samples {(x; 0 ys) )))) where eL > 0 controls the shift magnitude. Applying SGD-GD to the setup yields a scheme such that A1, 2, W1 (with ( satisfied, and W2 holds as ||0' is bounded in practice. To generate the training data, the unshifted samples D are generated first Z; 21| 1] i.e., the uniform distribution. T sgn((z;, 0*)) E {=1} such that 6 ~ (O, I), then a randomly selected 10% of the labels flipped to generate the final y. Furthermore, we set
800, d 10, 0.1, 10 3, e (0, 0.1, 0.5, 2). For (2), the batch size is b and the stepsize 71 7 T with T 108.
First, we validate the convergence behavior of SGD-GD in Theorem In Fig. 1 (left), we compare [[V) 0.)l against the number of iteration for the SGD-GD scheme over repeated runs. The shaded region indicate the 95% confidence interval. We observe that after rapid transient stage,
8

---

17.4
SGD-GD 0=
SGD-GD
10"
SGD F=
5GD-GD 0.1
SGD 0.0.5
119/(0, e,1112
SGD.GD 2=2
SGD-GD c
SGD-GD 0.5
(1V),, 8.112
V/0,))
10-1
Lasy K-
Lary K- 10,0m
44
Greedy K- -- 25
10
10a
Greedy Km 1ows
107
100
30'
"To""
101 10" 155
10
Iterations
Iterations
of sample accessed
Figure 1: Synthetic Data (left) SPS measure [0, 0 1 of SGD-GD against iteration no. t. (middle) Loss value (0;; 0,) of SGD-GD against iteration no. t. (right) SPS measure [V; 0 of greedy (SGD-GD) and lazy deployment against number of sample accessed. We fix et, = 2.
10-2
SGD-GD c 6
10-1
K-
10302
10-1
SGD-GD - 100
SGD-GD
16-1
Greedy K 16
16,b-1
10-1
Groedy K k=1.0=66
19) 8.1l
[19] e-]l
10--
[19(6, amll?
20-1
20--
20-1
20-4
16
1266
10
10-4
20-1
10-
107
107 20
107
124
20
10
102
201
10+
Iterations 2
no of sample accessed
no of sample accessed
Figure 2: Real Data with Neural Network Benchmarking with SPS measure [O, 0 (left) Against for SGD-GD with parameters CNN E f0, 10, 100). (middle & right) Against no. of samples with greedy (SGD-GD) and lazy deployment when ENN = 10 & eNN = 10 respectively.
the SPS stationarity [[; 2 saturates and stay around a constant level, indicating that the SGD-GD converges to biased-SPS solution. Increasing ez. leads to increased bias, corroborating with Theorem that the bias level is (E)) Fig. 1 (middle) further evaluate the performance of the trained classifier O, in terms of the performative risk value. Second, we compare the lazy deployment scheme in $4 with K (5, 10) and stepsize 7 = 1/(KyT). For fairness, we test SGD-GD with batch size of b E {5, 25} and compare the SPS stationarity against the number of samples accessed. The results in Fig. 1 (right) verifies Theorem 2 where increasing K effectively reduces the bias level.
Real Data with Neural Network. Our second example deals with the task of training a neural network (NN) on the spambase Hopkins al. [1999] dataset with
4601 samples, each with = 48 features. We split the training/test sets as 8 2. Our aim to study the behavior of SGD-GD when training NN classifier. To specify (1), we let (z, y) where x E Rd is the feature vector, E {0, 1} is label (0 for not spam, for spam). Consider the regularized binary cross entropy loss:
2(0:2) ((fe(z):v) yy (og((ff (1 y) log(1 fa(x)) + (3/2) |1012,
(26)
where fx()) denotes the NN classifier. The unshifted data is denoted by D = {(r, v: )m Sampling from the shifted data distribution D(0) achieved through (i) uniformly draw sample z (z, from D (ii) maximize the following utility function:
arg max, (a': 5. 0) - fo((') zin || x
(27)
to get 2 = (x, ~ D(O). In practice, we take the approximation x Rs x eNN (o
In our experiment, we set ENN E {0, 10, 100}. batch size as b = 8. For SGD-GD, we use = 7 200/vT and for lazy deployment, we use 7 200/(KVTT) with T = 105. The NN encoded in fz(r) consists of three fully-connected layers with tanh activation and sigmoid output layer, i.e.,
fo(z) = Sigmoid (T) ttan(( (a
where 0()) == [w (())) concatenates the weight and bias for each layer with d, = 10, d2 = 50, dg 57 neurons, making total of 3421 parameters for For the training, we initialize these parameters as (00, (0, 1) for weights and constant values for the biases.

---

Fig. 2 (left) compares the SPS measure [ 0:)1l against the iteration number t using SGD-GD. As observed, SGD-GD converges near SPS solution and the behavior seems be insensitive to <NN- We speculate that this is due to the shift model (27) but would relegate its study to future work. Fig. (middle & right) compare the greedy and lazy deployment schemes with 6NN E {10, 104) against the number of samples used. Compared to SGD-GD, lazy deployment performs relatively better as ENN 1, as seen from the no. of samples needed to reach || [0,; 0 10-4 -4 in the plots. This agrees with (24) which shows the dominant term as (E²²) and is related to ENN-
Conclusions
This paper provides the first study the performative prediction problem with smooth but possibly non-convex loss. We proposed a stationary performative stable (SPS) condition which is the counter- part performative stable condition used with strongly convex loss. Using the SPS solution concept, we studied the convergence of greedy deployment and lazy deployment schemes with SGD. We prove that SGD-GD finds a biased, (cc)-SPS solution, while the lazy deployment scheme finds a reduced bias SPS solution when the lazy deployment epoch is large. As an initial work on this subclass of problems, our findings can lead more general analysis on algorithms under the non-convex performative prediction framework.
Acknowledgement
The project was supported in part by CUHK Direct Grant #4055208. The authors would like thank the anonymous reviewer for pointing out the possibility of extending our convergence analysis to sensitivity measures defined by the TV distance.
References
Daniel Björkegren, Joshua Blumenstock, and Samsun Knight. learning, arXiv preprint arXiv:2004.080 038665, 2020.
Manipulation-proof machine
Gavin Brown, Shlomi Hod, and Iden Kalemaj. Performative prediction in stateful world. In International conference on artificial intelligence and statistics, pages 6045-6061. PMLR, 2022.
Yang Cai, Constantinos Daskalakis, and Christos Papadimitriou. Optimum statistical estimation with strategic data sources. In Conference on Learning Theory, pages 280-296. PMLR, 2015.
Joshua Cutler, Dmitriy Drusvyatskiy, and Zaid Harchaoui. Stochastic optimization under distribu- tional drift. Journal of machine learning research, 24(147):1-56, 2023.
Nilesh Dalvi, Pedro Domingos, Mausam, Sumit Sanghai, and Deepak Verma. Adversarial classifica- tion. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 90-108, 2004.
Aymeric Diculeveut, Gersende Fort, Eric Moulines, and Hoi-To Wai. Stochastic approximation beyond gradient for signal processing and machine learning. IEEE Transactions on Signal Processing, 2023.
Dmitriy Drusvyatskiy and Lin Xiao. Stochastic optimization with decision-depenndnt distributions. Mathematics of Operations Research, 48(2):954 998, 2023.
Seyda Ertekin, Leon Bottou, and C Lee Giles. Nonconvex online support vector machines. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(2):368-338 2010.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, 23(4):2341-236 2013.
Alison Gibbs and Francis Edward Su. On choosing and bounding probability metries. International statistical review, 70(3):419 413-4549-335,,0 2002.
10

---

Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pages 111-122, 2016.
Mark Hopkins, Erik Reeber, George Forman, and Jaap Suermondt. Spambase. UCI Machine Learning Repository, 1999. DOE:
Zachary Izzo, Lexing Ying, and James Zou. How to learn when data reacts to your model: perfor- mative gradient descent. In International Conference on Machine Learning, pages 4641-4650. PMLR, 2021.
Meena Jagadeesan, Tijana Zrnic, and Celestine Mendler-Dünner. Regret minimization with perfor- mative feedback. In International Conference on Machine Learning, pages 9760-9785. PMLR, 2022.
Qiang Li and Ho Wai. State dependent performative prediction with stochastic approximation. In International Conference on Artificial Intelligence and Statistics, pages 3164-3186. PMLR, 2022.
Qiang Li, Chung- Yiu Yau, and Hoi-To Wai. Multi-agent performative prediction with greedy deployment and consensus seeking agents. Advances in Neural Information Processing Systems, 01:38449-38466 2022.
Haitong Liu, Qiang Li, and Hoi-To To Wai. Two-timescale derivative free optimization for performative prediction with markovian data. ArXiv preprint arXiv:2310.05792. 2023.
Celestine Mendler-Dünne Juan Perdomo, Tijana Zmic, and Moritz Hardt. Stochastic optimization for performative prediction. Advances in Neural Information Processing Systems, 13:4929-4933 2020.
John P Miller, Juan C Perdomo, and Tijana Zmnc. Outside the echo chamber: Optimizing the performative risk. In International Conference Machine Learning, pages 7710-7720. PMLR, 2021.
Mehrnaz Mofakhami, Ioannis Mitliagkas, and Gauthier Gidel. Performative prediction with neural networks. In International Conference on Artificial Intelligence and Statistics, pages 11079-11093, PMLR, 2023.
Adhyyan Narang, Evan Faulkner, Dmitriy Drusvyatskiy. Maryam Fazel, and Lillian J Ratliff. Mul- tiplayer performative prediction: Learning in decision -diienend games. Journal of Machine Learning Research, 24(202) 2023.
Juan Perdomo, Tijana Zmnie, Celestine Mendler-Dinner, and Moritz Hardt. Performative prediction.
In International Conference on Machine Learning, pages 7599-7609. PMLR, 2020.
Georgios Piliouras and Fang-Yr Yi Yu. Multi-agent performative prediction: From global stability and optimality chaos. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 1047-1074, 2023.
Joaquin Quinonero-Candela. Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset shift in machine learning. Mit Press, 2022.
Mitas Ray, Lillian J Ratifff Dmitriy Drusvyatskiy, and Maryam Fazel. Decision-deeendent risk minimization in geometrically decaying dynamic environments. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 8081-8088, 2022.
Abhishek Roy, Krishnakumar Balasubramanian, and Saeed Ghadimi. Constrained stochastic noncon- vex optimization with state-dependent markov data. In Advances in Neural Information Processing Systems, volume 35, pages 23256-23270, 2022.
Xiaolu Wang, Chung Yiu Yau, and Hoi-To Wai. Network effects in performative prediction games. In International Conference on Machine Learning, pages 365 365400 PMLR, 2023.
Killian Wood and Emiliano Dall' Anese. Stochastic saddle point problems with decision-dependent distributions. SIAM Journal on Optimization, 1343)1194311967, 2023.

---

Yulai Zhao. Optimizing the performative risk under weak convexity assumptions. arXiv preprint arXiv:2209.00771, 2022.
Zihan Zhu, Ethan Fang, and Zhuoran Yang. Online performative gradient descent for learning nash equilibria in decision-ddpendent games, Advances in Neural Information Processing Systems, 36, 2023.
Tijana Zrnic, Eric Mazumdar, Shankar Sastry, and Michael Jordan, Who leads and who follows in strategic classification? In Advances in Neural Information Processing Systems, volume 34, pages 15257-15269, 2021.
12

---

A Proof of Lemma 1
Proof. Under A1, for any fixed E Z, we have that
E(0(+1:2) & ((0())) + (Ve(0(;)) 0c+1 - 02) + 2 110++1-011 0el
2 [(0 2) 7++1 (V)(0);)) ve(0;; 12+1)) + Init1 |e((0; I1+1
where the second inequality is due to the update rule of (2) recall that Ze+1 D(O,). Taking integration on 2 with weights given by the p.d.f. of ( i.., f())po. (z)d2, on both sides of above inequality leads to
J(0+=1:0,) s J(O,; 0,) - 7441 (VJ(0,; 0,) Ve(0,; 2(+1) + 2 ~ [V 2+11
As [ Z+1)] = (J(0,; 0.), taking the conditional expectation [x[[] on both sides yield E, [1(0+11: 0,) J(,,: 0,) 7 (.,
L 2ー2
7 EE [IVe(0=
7
(28)
(4) J(0,; 0.) -7++1 [VJ(0;;
2 72+1 (B, [VE Z+1) VJ((0;; v.;00; -10000000"+++V0000000000001
L
< J( 0.) 7--1 [J;;; 0.)11 - - (0) (1 (1=0
where (a) used A2 and the property:
E, Ve(e; Z 111 = E, |V Z,-1) - 0 0> + [V
and (b) is due to the variance bound in A2. Rearranging terms (28) leads to
51- + (1+o)m4) 7+11 [0, 01) - J(0,; 0,) (0,+1 0,)] 2 g8r2
L
The step size condition implies 1 (1 + o2) 2 1/2. This concludes the proof.
B Proof of Lemma 2
Proof. Our proof is modified from Lemma 2.1 of [Drusvyatskiy and Xiao, 2023]. By W2, since =) is Lophchtt z, we have
(e; 01) [(; 02) [Ez-D(e) Z) (x= Z') (D(()))
Applying W1 gives
(J(0,0,) 02) < Loe 0 -021.
which finishes the proof.
C Proof of Lemma 3
Proof. Under C1 & C2, we observe
/ ((0;2) (z) - -pe, (z))dz
[J(0, J(0,0,,)))))
/ [e(0:2)] lpo. (2) Po. (2) dz
$ Emax / Ipe, (2) po. (2)) d(2)
S Emer 28Tv (D()),,),,
(
- 28 2mmax 0211-
where (a) is due to the Scuchy-Schwarziiee inqquality (b) due to the stated assumptions Cl.
13

---

D Proof of Theorem 1
Proof. We recall from Lemma the following relation:
1++1
L VJ(0,; & (,,) - 1(0+41:00] 00
(29)
2
We notice that Lemmas 2, imply
[(0: J(0: - 7. |00 -011,,
where L. = La if WI, hold, L. - maa if C1, hold. Subsequently, the first term on the right hand side of (29) can be bounded by
[, 0,) ((0 0.) = [. 0.) J(0 0 + 0++1) ((( 0.)1
s (0, 0.) J(0+:1: 0 L.. E, 0:1]]
[,, 0₂) - 02 + 1. Ze+0;;
Notice that
Le 1/VE(( Z++1)ll mtiLey E, Z(11)1
(6)
$ ne
0u + 1 o7 [][(0;
s4ile
do (1 + + +
[V, 0.) 0.)
4Lc
where (a) is due the Cauchy-Schwarz inequality ||||X||| - E X [3], (b) is due to the chain:
E, |V((0;
[VV 0.)1 E. |[ Z++1) VJ(0,, 0.)1
I < + (1 (1
+ VJ+
and (c) is due to the Young's inequality. Substituting back into (29) gives
1++1 [V, 0.)1 < (O,,; (0 0c+1)] i (oo + +l+of)]e)
L
2 10
Notice that taking full expectation and summing both sides of the inequality from / = 0 to T yields the theorem.
E Proof of Theorem 2
Proof. The first steps of our proof resemble that of Lemma and is repeated here for completeness. Under AI, for any fixed
Z, we have that
2(0 ((0,+41)2 < ((0rxx: 2) + (T((0,,;)) 0r, + 110 - 01,11l
LT²
< <((0r, 7 Ve( V((() 1c)+
Ve(OO. 21,+1)11
where the second inequality is due to the update rule of (2) as we recall that Z(41 D(0,). Taking integration with weights given by the p.d.f. of D(0,), i.c., f(-)pe, (z)dz, on both sides of above incquality leads to
(V.J( 0,,)) Ve(O [ 7 (VE((1, Z
J(0,,.+1: 0,,)) S J(O
As Zr,++1 D(O,,)), we have B., (VE(O,(( Ze ((,,,, 0r,)), where E. denotes the conditional expectation on the filtration
Fi, (0o 00.1. 0o.k. 01.,. Or, 0,.1..... (0,,)))
14

---

Taking the conditional expectation E on both sides yield
L22 En, (V Zr,+1)]l (30)
Be (000) 0z.0
J( 01,0) - [
+ 22
L 2 [E, [e 2.,+11 VJ((O,ni 0,,00 1 0r,01
L "
(08 +1:++1++00) (VJ00::.000
- J 0r,0) (,
2
where (a) used A2 and the property:
Eg,* [VVe 2 = E,, (7((00,,22,,4111 - VJ(OL.:: + [VJ(0r,;
and (b) due to the variance bound A2. Rearranging terms (30),
[[VJ(00, 02,0) - J(OrAi (.. - (1-"u+oin) >
T. 00r (31)
The step size condition implies 1 [1 2 2
[VJ(Or,,; < (O,,s: 01,0) [(0,)(() + 00?
Taking summation on l from 0 K leads
LK
(TJ(6r,,00,,01)) < (( 02.)) (0,,)
0.,)]
o372
(32)
2
Recall that 1.+1.0 0++1 = 0.,k. Subsequently, the first term the right hand side of (32) can be bounded by
(0 0,) (0.+1 0.) < (o, 1(0 0 E 0(+1) (( 0.1l
(0,; 0.) J(0++:
0++1
0.1l]
K-1
= {0,; 0.) - 1(0++1: 02+1) + 7 E.
Ve(Or, 2, Z,,411
Notice that through careful use of A2 and the independence between stochastic gradients, have
E,
Vi(O,,s Ze.+1i
k=0
K-1
2E,
(( (., - 0.))
+ 2E,
VJ VJ(O,,;;0) 01)
K
2
E, Ze,41)) (.)0+,)))-(( + 2E,
VJ ( b 0i)
(33)
k=
k=
K-1
K
2Koo + 207
Es [|VJ(Or.:0)))1) + 2E,
VJ 0.)
k==
K-1
5
2Ko² + 2(K + of)
Σ E,
VJ 0.)1
k=0
15

---

Using vo + <a+bfor a, 2 0, we have
K-1 Ve(O,,u: Z
K-1
E
S <VKKo + 2 + +of)
Σ
E
[IV
k=
(34)
R-1
S V2Koo + 2(K + + Le +
E
[V: 0:)1
4Te
where the last inequality used the property Va 2 (32) and taking full expectation on both sides give us
+ 2c
for any O. Substituting above results
K-
E (OOL,, o2)) < [[(0, 0.) -((0411,0-11)
(35)
LK
+ (V2Koo + +2(K + +of) + 2
0072
Next, we lower bound the left hand side by observing:
K- 11
E 0r.00
VJ 0J11 - IV. 0,) - 2/(00.0,)11
R=0
A=
KE J(o.. 0:)1
Σ
E 100, Ool
K-1
(c)
KE (0. 0.)11
Σ
E
Ve((O,, Zzee)
K-1
2
KE KE VJ 0,)11 11-
Σ
k
E
VV(E,,,, 21,
k=0
K-1
KE KEI|VJ(,,000 0311 17
Σ
k
Σ
G2
2
km0
1
KE VJ 01)1 LG222 K(K - 1)(2K -
2
6
KE VJ. 0.)1 LG K
where (a) is due to the fact that ||a| >
2 la b11 |16| for any a, E R", (b) is due to A1, (c)
is obtained from the updating rule (23). In (d). we used the additional assumption A3. The last chain
is due to ΣK-1 2-2 K(K 1)(2K 11)
Ka when K 2 1. Substituting the above lower bound to
(35) and rearrange terms lead to
7K
E EIV 0.)1 EE 0(0,41,0 +
12 7 R3
8
LK
+ (V2Koo + 2(K + +o)
+
2 o07
Taking summation from 1 = 1,, T gives us
K T-1
T
EIVJ((A, 0.)1I < E ([ 0o) - J(Or
1 K3
12
TLK
TTic (V2Koo +(K + +o]) +
222
Dividing 7KT/8 on both sides, we have
E E 0.)1
8Ao
ALO
2 2²2
84. K
(v2Kon 2(K +of)ic).
TK
3
where we recall Ao == J(0o: 0o) Lmaz.
16

---

Additional Numerical Results
This section provides additional details for the numerical experiments that were omitted due space limitation.
Synthetic Data with Linear Model Fig. shows the trajectories of training and testing accuracy with the SGD-GD scheme under different shift parameters, using the same settings as in Fig. (left & right). Note that the testing dataset with 200 samples is generated from the same procedure described in the main paper with the same ground truth 0º, but without the label flipping step. In this case, although increasing the shift leads larger risk value J(0;; 0.) and more biased stationary solution in terms of || [ 0 [cf. Fig. 1 (left & middle)), the test/train accuracy remain relatively stable regardless of the shift parameter. We remark that as observed from [Miller et al., 2021, Fig. 2], increasing the shift parameter does not always lead to deteriorated or improved model accuracy. Importantly, the effects can be unpredictable in general, especially when only biased SPS solutions guaranteed.
Text Accuncy
0.6
Train
0.4
SGD-GD
SGD-GD 0.1
SGD-GD 0.5
SGD-GD ==
68
Iterations
Iterations
Figure 3: Synthetic Data (Leff) Training accuracy under different sensitivity parameter Eg. (Right) Testing accuracy under different EL.
Fig. 4 shows the trajectories of loss values (O,; 0z), training and testing accuracy with the greedy and lazy deployment scheme using the same settings as Fig. (right). We observe similar behaviors as indicated in Fig. 3. Moreover, we notice that although the lazy deployment scheme converges to less biased SPS solution than greedy deployment scheme utilizing the same number of samples, the initial convergence speed is slower. This can be predicted from Theorem 2 as the lazy deployment scheme is simulated with larger noise variance do.
m5
0.0
Gready 1
Lazy K,5,0
88-
Train Accuracy
Test Accuracy
0.6
Lazy
Lazy K- 10.b
Lazy 10,b
Greedy K=1,0=25
Greedy K=1,0=25
Greedy K 1,0m3
5/-
GredyK=1,0
8.5
0.2
80-
n0 of sample accessed
no sample accessed
110 sample accessed
Figure 4: Synthetic Data (Left) Loss V(0) against of sample accessed. (Middle) Training accuracy under different sensitivity parameter e,, (Right) Testing accuracy under different é
Real Data with Neural Network Model Similar the above paragraph, Fig. 5, 6. 7 show the trajectories of train/test accuracy. for greedy/lazy deployment scheme when E {10. 10*) for completeness. The figures demonstrate similar behavior described in the main paper. Moreover. we observe that the sensitivity parameter has small effect in the training/testing acccuracies of the trained models.
17

---

0.00
1.50
0612
1.500
Accuracy.
663
8.51
2.770
0.004
Text
0.000
SGD-GD =-0
4572
SGD-GD =
SGD-GD 10
0.600
SGD-GD 100
0590
10
167
15
10
Iterations
iterations
Figure 5: Real Data with Neural Network (Leff) Training accuracy under different sensitivity parameter e. (Right) Testing accuracy under different
0.81
0.58
Train Accurcy
0.82
Test Accurary
6:57
0.57
Lazy K = 4,
Lazy K 4=
Lazy K- -6
Lazy K-1.00-
6:8
Greedy
0.3
Greedy K=
of sample accessed
no sample accessed
Figure 6: Real Data with Neural Network (left & right) Training accuracy under different deploy- ment scheme when CNN = 10.
0.67
10003
2:50
12000
0:50
Troin Accurcyy
Accuracy
0:58
637
0:51
0.55
Lazy K- 4,b b
Lazy 4,
Lazy K =
6.55
Lazy b=
Greedy K 1,b 16
Greedy = b, 16
835
10
10a
10"
100
10
127
10'
19'
16a
of sample accessed
no of sample accessed
Figure 7: Real Data with Neural Network (left & right) Training accuracy under different deploy- ment scheme when ENN 10a.
18

---

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

---

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

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The paper will provide open access to source code, ensuring that the main experimental results can be faithfully reproduced.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / httppsscccppbccccccceecce heabblic/giidee CodeeSbbm ssi aasonnooicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper specifies all training and test details, including data splits, hyperpa- rameters and etc.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: This paper reports the confidence intervals for experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
21

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We described the computation platform used in Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question:
Does the research conducted in the paper conform, in every respect, with the wttppssccccpppccccpcpeppcccccppe Ceaellic/EEhiitteee Etwicciueeeeieesss
NeurlPS Code of Ethics https:
Answer: [Yes]
The authors have ensured that the research conducted the paper complies with the NeurlPS Code of Ethics, preserving anonymity.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents work whose goal is to advance the field Machine Learning. There many potential societal consequences of work, none which we feel must be specifically highlighted here.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
22

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our data were obtained from openly available datasets and modes classical machine learning model, mitigating any risk of misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We have appropriately cited and described the sources of our data.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
23

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "bJ4CgU3fVT", "reviewer": "Reviewer_eMX9", "summary": "This work studied performative prediction problems in nonconvex regimes and proposed the first algorithm, SGD-GD, with convergence guarantees in this case, it was further extended to a lazy deployment scheme so that the algorithm is bias-free.", "questions": "/", "limitations": "/", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. First convergence analysis of gradient-based algorithms for performative prediction problems in nonconvex regimes. Which is a novel contribution.\n2. Proposed a new convergence measurement for nonconvex performative prediction problems\n3. The writing is great and the storyline is easy to understand", "weaknesses": "1. The definition of SPS, as the authors mentioned, only considers the gradient regarding the loss function, while missing the gradient over the distribution parameter, which may not perfectly reflect the stationarity convergence of the objective function. \n2. Some assumptions are still a bit unrealistic (for example, the global upper bound assumption in C2), it is not clear whether they are satisfied in the numerical experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The definition of SPS, as the authors mentioned, only considers the gradient regarding the loss function, while missing the gradient over the distribution parameter, which may not perfectly reflect the stationarity convergence of the objective function.\n\nThis is a valid observation. However, we remark that SPS is a stationary solution concept suitable for the arguably more \"natural\" algorithms for performative prediction -- including SGD-GD, SGD with lazy deployment, repeated risk minimization. These algorithms do not require a-priori knowledge of the form of data distribution shift, nor attempt to learn the latter. We believe these class of algorithms are important as they are applicable to scenarios when the learner is agnostic to the distribution shift. The definition of SPS generalizes that of performative stable (PS) solution [Perdomo et al., 2020] since for (strongly) convex $\\ell(.)$, the definitions of SPS and PS solutions are equivalent. Note algorithms for achieving a stationary point for $V(\\theta)$ has been explored in works like [Izzo et al., 2021], which represents a different research direction in the performative prediction community.\n\n\n> Some assumptions are still a bit unrealistic (for example, the global upper bound assumption in C2), it is not clear whether they are satisfied in the numerical experiments.\n\nAdmittedly, while assumptions like C2 may appear to be slightly strong, our theory remains applicable to a number of applications in ML including our numerical experiments. For the synthetic data experiments, the sigmoid loss function is upper bounded by 1. Similarly, in the neural network experiments, the loss is also upper bounded due to the sigmoid function applied in the last layer. Both simulations satisfy one of the required sets of assumptions (W1+W2 or C1+C2). We will expand the discussion on how these examples satisfy the assumptions in the revision. We also remark that C1 can be further relaxed to **C1'** using a weakened notion of distribution sensitivity; see the response to 71Gw.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qyoDmnOoWs", "reviewer": "Reviewer_JTrB", "summary": "This paper studied the `performative prediction’ that means when predictive models are used to make consequential decisions like policy making, it can trigger actions that influence the outcome they aim to predict. And we know a system with unlimited positive feedback will eventually be destroyed. On the optimization side, this work considered a risk minimization problem with a decision-dependent data distribution. It means the loss function specified by model parameters $\\theta$ and the data distribution. They analyzed stochastic gradient descent (SGD) with a greedy deployment scheme (SGD-GD) in a setting that only requires the smoothness of non-convex loss function $l$. They showed the algorithm convergence to stationary performative stable (SPS) solutions with two types of distance metrics of distributions. Numerical examples of both synthetic and real data are provided to justify their theoretical result.", "questions": "The reviewer is generally positive about this work. One question would be: \n\nAre there some other real applications besides the spam filter? Could the author provide more insight into this theoretical work and other policy-making applications with real-world influence?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Pros:\n\nIt's a solid extension of the SGD-GD works of [Mofakhami et al., 2023] and\n[Mendler-Dünner et al., 2020] with smooth but not necessarily non-convex loss $l$. It’s a big step forward compared to the strongly convex loss in previous work.\n\nThey provide both real and synthetic experiments to justify their claims.", "weaknesses": "Cons:\n\nThe experiment setting is relatively simple but it's a minor issue since this is a theoretical work and the experiment is showcasing the concept.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The experiment setting is relatively simple but it's a minor issue since this is a theoretical work and the experiment is showcasing the concept.\n\nWe chose a simple experiment setting to demonstrate the effects of key parameters such as sensitivity strength $\\epsilon$ and lazy deployment period $K$ to better validate the theoretical findings. We believe that this is an appropriate choice given the theoretical nature of this work.\n\n\n> Are there some other real applications besides the spam filter? Could the author provide more insight into this theoretical work and other policy-making applications with real-world influence?\n\nExamples of performativity are pervasive in the real world, especially in the financial market and strategic training tasks, such as insurance, hiring, admission, and healthcare. In these scenarios, individuals often adjust their behaviors to receive predictions in their favor. For instance, in the hiring process, job applicants may prepare more relevant projects based on the job description provided by a company’s HR. When an employer conducts an interview and decides whether to hire an applicant, the applicant may have a higher chance of being hired if s/he is better prepared.\n\nFrom a theoretical perspective, a crucial point we explored in this paper is that decisions are often made via models that are trained thru a non-convex optimization process, which has not been addressed in previous works on performative prediction. One takeaway from our findings is that - with reference to the results on lazy-deployment vs greedy-deployment SGD - when a decision maker (company) frequently changes its job description requirements, its trained model may experience greater bias that may lead to reduced performance.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zXV7bsbSnT", "reviewer": "Reviewer_71Gw", "summary": "The paper studies convergence of stochastic gradient descent in a performative prediction context. The main result shows that SGD converges to an analogue of performative stability, which the paper terms “stationary performative stability” (up to a bias term). The results characterize the rate of convergence and the magnitude of the bias.", "questions": "In the paragraph starting with line 275, you mention the relationship of Theorem 2 with RRM convergence and Mofakhami et al. My understanding was that they required a particular strong convexity condition, as noted in Table 1. So your result even for RRM may be new. Could you comment on this?\n\nThe discussion about the time-varying Lyapunov function (e.g. starting at line 179) reminded me of the perspective from Drusvyatskiy and Xiao. They show that SGD in a performative context can be thought of as standard SGD on the equilibrium distribution, at the stable point. I’m wondering if you’ve thought about if there exists an analogue of this perspective in your nonconvex setting?", "limitations": "There is not much discussion of limitations, though I don't think it is necessary.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The results in this paper significantly expand the scope of optimization in performative prediction, which has so far largely focused on convex loss functions. In fact, most results require strongly convex losses. Moreover, prior work typically makes an assumption on the magnitude of the performative effects, captured by the sensitivity parameter epsilon; the convergence results of this paper do not require a bound on epsilon and show that the sensitivity determines the distance to stationary performative stability. The lack of assumption about epsilon is a major advantage. There are some other works, e.g. Jagadeesan et al., that do not require a bound on epsilon, but this work requires knowing epsilon to run the optimization method. The additional analysis of the lazy deploy scheme, which approximates RRM and thus incurs no bias in the limit, is a nice addition. The observation about the different dependence of the bias on epsilon depending on whether the gradients are stochastic or not is another nice result.", "weaknesses": "This is not really a major weakness, but I think some of the discussion in Section 3.1 could be simplified. Instead of assuming the chi squared divergence condition, one can get Lemma 3 by assuming that D(theta) is Lipschitz in TV distance (i.e. ||D(\\theta) - D(\\theta')|| \\leq \\epsilon ||\\theta - \\theta'||), together with C2. The chi squared condition seems a bit odd and nonstandard because it is not a Lipschitz condition.\n\nIn A2, the first part of the sentence is not an assumption; it’s true just by the definition of J?\n\nIn Lemma 1, Theorem 1 (and possibly other places) please use parentheses in the step size condition. It should be 1/(L(1+sigma1^2)).\n\nVery minor suggestion: personally I find it more appropriate to see Theorem 1 as a lemma and Corollary 1 as the main theorem.\n\nPlease don’t use the symbol T in Theorem 2 for the random step because you use that symbol in eq. (4).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> I think some of the discussion in Section 3.1 could be simplified. Instead of assuming the chi squared divergence condition, one can get Lemma 3 by assuming that D(theta) is Lipschitz in TV distance (i.e. $||D(\\theta) - D(\\theta')|| \\leq \\epsilon ||\\theta - \\theta'||$), together with C2. The chi squared condition seems a bit odd and nonstandard because it is not a Lipschitz condition.\n\nThanks for your valuable suggestion. Indeed, as you said, the chi-squared condition (**C1**) can be replaced by a weaker TV distance condition. The argument is as follows. \n\nFirst, we recall the definition of TV distance as $\\delta_{TV}(\\mu, \\nu) = \\sup_{A\\subset {\\sf Z} } \\left| \\mu(A) - \\nu(A) \\right| = \\frac{1}{2} \\int \\left| p_{\\mu}(z) - p_{\\nu}(z) \\right| {\\sf d}z$ where $\\mu, \\nu$ are two measures supported on ${\\sf Z}$ and $p_{(\\cdot)}(z)$ denotes their pdfs. Note that we have $\\delta_{TV}(\\mu,\\nu) \\leq (1/2)\\sqrt{\\chi^2(\\mu,\\nu)}$ [Gibbs and Su, 2002, Sec. 2]. Accordingly, we may replace **C1** by its weakened version: \n\n**C1'** There exists a constant $\\tilde{\\epsilon}\\geq 0$ such that $\\delta_{TV}\\left({\\cal D}(\\theta_1), {\\cal D}(\\theta_2)\\right) \\leq \\tilde{\\epsilon} \\| \\theta_1 - \\theta_2 \\|$ for any $\\theta_1, \\theta_2\\in \\mathbb{R}^d$\n\nUsing **C1'** and **C2**, we derive a similar result as Lemma 3 with the following chain\n$$\n\\begin{aligned}\n    \\left| J(\\theta, \\theta_1) - J(\\theta, \\theta_2)\\right| &= \\left| \\int \\ell(\\theta; Z) (p_{\\theta_1}(z) - p_{\\theta_2}(z)) {\\sf d}(z) \\right|\n    \\leq \\int |\\ell(\\theta; z)| \\cdot \\left| p_{\\theta_1}(z) - p_{\\theta_2}(z) \\right| {\\sf d}z\n    \\leq \\ell_{max} \\cdot \\int \\left| p_{\\theta_1}(z) - p_{\\theta_2}(z) \\right| {\\sf d}(z)\n\\end{aligned}\n$$\n$$\\hspace{+3.5cm}\n \\leq \\ell_{max} \\cdot 2\\delta_{TV}({\\cal D}(\\theta_1), {\\cal D}(\\theta_2))\n    \\leq 2\\ell_{max} \\tilde{\\epsilon} || \\theta_1 - \\theta_2 ||\n$$\nThe rest of our convergence analysis for SGD-GD or SGD-lazy deploy follows immediately with the above modification. Again, we thank the reviewer for pointing this out and will make sure to include the above proofs in the revision!\n\n> Personally, I find it more appropriate to see Theorem 1 as a lemma and Corollary 1 as the main theorem.\n\nWe chose to describe our theoretical results in this way as we wish to include general conditions for the step size $\\gamma_{t}$, such as diminishing and constant step sizes. \n\n> In the paragraph starting with line 275, you mention the relationship of Theorem 2 with RRM convergence and Mofakhami et al. My understanding was that they required a particular strong convexity condition, as noted in Table 1. So your result even for RRM may be new. Could you comment on this?\n\nThough our Theorem 2 suggests a new finding for an RRM-like strategy, we believe that such strategy of SGD + lazy deployment with $K \\to \\infty$ strategy is not strictly equivalent to RRM. A subtle difference is that RRM (e.g., in [Mofakhami et al.]) requires finding an exact minimizer to the risk minimization problem given a fixed data distribution at each iteration, yet SGD + lazy deployment may only find a stationary point to the risk minimization problem (with non-convex loss) even when $K \\to \\infty$. As such, we have restrained from claiming it as a new finding for RRM. We will elaborate more in the revision.\n\n\n> The discussion about the time-varying Lyapunov function (e.g. starting at line 179) reminded me of the perspective from Drusvyatskiy and Xiao. They show that SGD in a performative context can be thought of as standard SGD on the equilibrium distribution, at the stable point. I’m wondering if you’ve thought about if there exists an analogue of this perspective in your nonconvex setting?\n\nAlthough this is an interesting point, we believe that drawing such analogue for the nonconvex setting is difficult since the equilibrium distribution may not be unique in the latter case. In fact, the inability to apply the Lyapunov function $J(\\theta;\\theta_{PS})$ is also the reason why we had to develop a new time varying Lyapunov function in the nonconvex setting. \n\n> Other Problems\n\nWe also thank the reviewer for pointing out other typos and small issues in the paper. We will correct them in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TVhGNWtXzi", "reviewer": "Reviewer_kiFq", "summary": "A nice paper that studies nonconvex performative prediction optimization. Proposed a new stationarity notion and demonstrated convergence for SGD with greedy deployment.", "questions": "1. What happens to the analysis if the distribution is discrete. Then PDF may not exists and Pearson $\\chi^2$ sensitivity may not be well-defined. \n2. Regarding Theorem 2, to ensure $\\delta$ stationarity, it requires $T=O(\\delta^{-2})$ and $K=O(\\delta^{-2})$. It means that to control both the bias and the error accumulated in the iterations, it needs $TK = O(\\delta^{-4})$ iterations/samples. Is it possible to improve it to $O(\\delta^{-2})$, i.e., the same complexity as the non performative setting?\n3. Table 1 should reflect the bias level and compare the bias level with existing literature. It should also mention what would be the sample complexity needed to ensure an $\\delta$ stationary point in this work and other works.", "limitations": "See questions above.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Extending the convergence measurement from the strongly convex case to the nonconvex case and proposing the stationary performative stable notion.\n2. Extremely clear and easy to follow with key insights for the performative prediction problems. \n3. Novel convergence guarantees. \n4. The lazy deployment is quite interesting. It is equivalent to using mini-batch in some sense.", "weaknesses": "Performative prediction problem is less motivated, i.e., there lacks a icon application such that the problem can only be formulated as a performative prediction problem and cannot be formulated in other forms even considering the special structure of the problem. \nThe numerical experiments lacks a convincing example as well, i.e., why studying the problem.\n\nLeveraging the problem structure, many times the problem admits other more classical optimization objectives. It is not the problem of this paper alone but the whole research line.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Performative prediction problem is less motivated, i.e., there lacks a icon application such that the problem can only be formulated as a performative prediction problem and cannot be formulated in other forms even considering the special structure of the problem. The numerical experiments lacks a convincing example as well, i.e., why studying the problem. Leveraging the problem structure, many times the problem admits other more classical optimization objectives. It is not the problem of this paper alone but the whole research line.\n\nThanks for your critical comment on the state of performative prediction research. Many learning problems when applied in a \"societal\" setting will exhibit performativity. This is an inevitable outcome as the predictions informed by trained models becomes a part of the bigger social system. Further, an important property in performative prediction explored by this line of work is that the learner who trains the model cannot access information about how the distribution shifts, and thus cannot estimate the exact gradient of $V(\\theta)$ that depends on ${\\cal D}(\\theta)$. Due to these limitations (note they are imposed by the application scenario rather than by the algorithm design), we believe that one of the key challenges shall lie in understanding and improving such \"non-gradient\" dynamics instead of exploring problem structure to efficiently minimize $V(\\theta)$. \n\n> What happens to the analysis if the distribution is discrete. Then PDF may not exists and Pearson $\\chi^2$ sensitivity may not be well-defined.\n\nThat's a good observation. We agree that the chi-squared divergence condition in the original **C1** does not work with discrete distributions which limit its application. Fortunately, as pointed out by reviewer 71Gw, the above condition can be easily weakened into a sensitivity condition based on the total variation distance which also applies to discrete distribution (see **C1'** in the response to 71Gw). Nevertheless, our results also apply to cases with the Wasserstein-1 sensitivity condition (see **W1**).\n\n\n> Regarding Theorem 2, to ensure $\\delta$ stationarity, it requires $T=O\\left(\\delta^{-2}\\right)$ and $K=O\\left(\\delta^{-2}\\right)$. It means that to control both the bias and the error accumulated in the iterations, it needs $T K=O\\left(\\delta^{-4}\\right)$ iterations/samples. Is it possible to improve it to $O\\left(\\delta^{-2}\\right)$, i.e., the same complexity as the non performative setting?\n\nWe believe that it is possible to improve the sample complexity of $TK$ beyond $O(\\delta^{-4})$. This is because from (22), we observe that within the $t$th \"inner loop\" after each deployment, the SGD-lazy deploy scheme is essentially SGD for $\\min_{\\theta} J(\\theta;\\theta_t)$. Now to improve the sample complexity with $K$, one may replace the SGD method with variance reduced SGD such as using the STORM gradient estimator in [a]. \n\nHowever, we suspect that reaching the sample complexity of $O(\\delta^{-2})$ would require more work. One of the reasons is that the structure of optimization algorithm is different as the learner does not have access to the (form of) distribution shift, and as explained in our manuscript, this limits the use of standard analysis tool such as (constant) Lyapunov function method. In general, characterizing and achieving the optimal sample complexity of performative optimization with non-convex loss is an exciting future direction to be explored.\n\n[a] Cutkosky and Orabona, \"Momentum-based variance reduction in non-convex sgd\", NeurIPS 2019.\n\n> Table 1 should reflect the bias level and compare the bias level with existing literature. It should also mention what would be the sample complexity needed to ensure an stationary point in this work and other works.\n\nThe purpose of Table 1 is to compare the few existing works on non-convex performative prediction, yet other papers may have used other form of solution concepts where the studied algorithms admit various forms of biases. We intend to indicate their differences through displaying their respective convergent point \"$\\theta_{\\infty}$\" & algorithm type \"Algo\". To save space, we have used ${\\cal O}(\\epsilon)$-SPS to indicate the bias level of SGD-GD analyzed by us. As for the sample complexity, they can be deduced from the \"Rate\" column. We will improve the presentation of Table 1 in the revision if space allows.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
### General Response
We thank all the four reviewers for their careful reviews and valuable suggestions. We summarize our general responses and proposed improvement to the paper as follows:

- Our work provides one of the first convergence theories on SGD-greedy deployment scheme applied to performative prediction with non-convex losses, i.e., a stochastic optimization problem with decision dependent samples. To do so, we developed several innovations: (a) the concept of SPS solution for "equilibrium" solution defined w.r.t. a partial stationarity condition, (b) a time varying Lyapunov function that tracks the progress of SGD-GD in the absence of a unique equilibrium solution. These innovations have led to new findings that seems to be unique for non-convex performative prediction, namely, SGD-GD may converge to a biased SPS solution, and the bias can be reduced/eliminated with a lazy deployment variant. We believe that these findings/innovations will be of interest to the performative prediction community, as well as studies on stochastic algorithms in general.
- We are grateful for the constructive suggestions. Particularly, we have weakened the condition **C1** based on $\chi^2$ divergence into that based on the weaker TV distance; see **C1'** in the response to reviewer 71Gw. This allows our main theories to be applied on more general settings for performative prediction. 
- We also thank reviewer kiFq for raising the issue about reducing the sample complexity to reach an (unbiased) SPS solution. We listed some ideas in the response below but this is an important future direction that we would like to explore.

We found that these suggestions improves the paper quality and will include them into the revision. We look forward to further discussion with the reviewers in the next phase of this review process. Thank you!

Meta-review: This paper considers a variant of SGD where the distributions of stochastic gradients depend on the values of $\theta_t$ when applied to nonconvex problems. Due to this variation, the original proof of SGD converges to a stationary point cannot be easily applied. The main contribution of this paper is designing the decoupled performative risk $J$ and the decoupled partial gradient $\partial J$ in (3). Then the authors manage to apply similar steps of plain SGD except that the sum of the norms of full gradients are bounded by the $J$ functions, not the batch objective $V$, which is quite clever.
Decision: Accept (poster)