Stochastic Optimization Schemes for Performative Prediction with Nonconvex Loss

Authors: qiang  li
hoi-to  wai
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 05:29:09

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 a bias-free SPS solution. Numerical experiments corroborate our theories.

Main paper: 
 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 as an example. On one hand, email service providers design filters to protect their users by identifying spam emails. On the other hand, spammers aim to circumvent these filters to 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 to 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 [Quiñonero-Candela et al., 2022] .The scenarios described can be captured by the recently proposed performative prediction problem, which called the above dataset shift phenomena as the 'performative' effect. Perdomo et al. [2020] proposed to study the risk minimization problem with a decision-dependent data distribution:EQUATIONwhere ℓ(θ; z) is a loss function that is continuously differentiable with respect to (w.r.t.) θ for any given data sample z ∈ Z, and Z ⊆ R p is the sample space. The dependence on θ in D(θ) explicitly captures the distribution shift effect of prediction models on data samples. The objective function V (θ) is also known as the performative risk.Literature Ncvx-ℓ Ncvx-V Sensitivity Algorithm Rate θ ∞ [Izzo et al., 2021 ] Miller et al., 2021] ✗ ✗ W 1 2-Phase O(T -1 ) min V (θ) [Mendler-Dünner et al., 2020] ✗ ✓ W 1 SGD-GD O(T -1 ) PS [Mofakhami et al., 2023 ]✗ ✓ Loc. † 2-Phase O(T -1 2 ) ∇V (•) = 0 [✗ ‡ ✓ χ 2 RRM ‡ Linear ‡ PS ‡ ✓ ✓ TV or W 1 SGD-GD O(T -1 2 ) O(ϵ)-SPS This Work ✓ ✓ TV or W 1 SGD-Lazy ⋆ O(T -1 2 ) O(ϵK -1 2 )-SPSTable 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(θ), D(θ ′ )) ≤ ϵ∥θ -θ ′ ∥ such that d(•, •) is a distance metric between distributions. 'θ ∞ ' indicates the type of convergent points: 'PS' refers to performative stable solution [cf. ( 4)], 'SPS' refers to Def. 1. † Izzo et al. [2021] assumed that D(θ) belongs to the location family, i.e., D(θ) = N (f (θ); σ 2 ).‡ Mofakhami et al. [2023] considered ℓ(θ; z) = l(f θ (x), y) with strongly convex l(•, y). The RRM requires solving a non-convex optimization at each recursion.⋆ SGD-Lazy refers to the SGD method with lazy deployment scheme, which fixes the deployed model for K iterations before the next deployment; see §4.The decision variable θ in (1) affects simultaneously the distribution and the loss function. As such, optimizing V (θ) directly is often difficult. Mendler-Dünner et al. [2020] considered the following stochastic gradient (SGD) recursion: for any t ≥ 0 and let γ t+1 > 0 be a stepsize, θ t+1 = θ t -γ t+1 ∇ℓ(θ t ; Z t+1 ), where Z t+1 ∼ D(θ t ).(EQUATIONThe above is known as the greedy deployment scheme with SGD (SGD-GD), where the learner deploys the current trained model θ t before drawing samples from D(θ t ). 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 a new model only once every few iterations, or repeated risk minimization; see [Mendler-Dünner et al., 2020 , Perdomo et al., 2020 , Zrnic et al., 2021] .Existing convergence analysis of (2) are limited to the case when ℓ(θ; z) is strongly convex 1 w.r.t. θ. 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 an 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 D(•), measured w.r.t. the Wasserstein-1 (W 1 ) distance, is upper bounded by a factor proportional to the strong convexity modulus of ℓ(θ; z) [Mendler-Dünner 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] , state-dependent learning [Brown et 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 ℓ(θ; z) is smooth but possibly non-convex. This is a more common scenario in machine learning than the strongly convex loss considered in the prior works, e.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 ℓ(θ; z) and the distribution D(θ), utilizing advanced algorithms that demand extra knowledge on D(θ), etc., as we overview below.Related Works. In the non-convex setting, the most related work to ours is [Mofakhami et 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 ℓ(θ; z) = l(f θ (x); y) where l(ŷ; y) is strongly convex w.r.t. ŷ, (ii) it only analyzes the case of training NN using a 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 ℓ(•; z).Other works departed from tackling the PS solution and considered alternative algorithms to directly minimize V (θ). For example, Roy et al. [2022] assumed that unbiased estimates of ∇V (θ) is available and studied the convergence of stochastic conditional gradient algorithms towards a stationary solution of V (θ), 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 (θ). Notice that estimating ∇V (θ) requires knowledge on D(θ) 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(θ) via a 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 V (θ). We remark that [Zhao, 2022] studied conditions to ensure V (θ) 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 a biased SPS solution. Assume that the distribution shift is ϵ-sensitive, i.e., it holds d(D(θ),D(θ ′ )) ≤ ϵ∥θ -θ ′ ∥ for some distance measure d(•, •) between the shifted distributions D(θ), D(θ ′ ), SGD- GD converges at a rate of O(T -1 2 ) in expectation to an O(ϵ)-SPS solution.The bias level is further improved to O(ϵ 2 ) when the gradient is exact.• Our analysis relies on constructing a time varying Lyapunov function that may shed new lights for non-gradient stochastic approximation [Dieuleveut et al., 2023] . We studied two alternative conditions on the distance metric between distributions. When d(•, •) is the Wasserstein-1 distance, SGD-GD converges to a biased SPS solution for Lipschitz loss function. When d(•, •) is the total variation (TV) distance, SGD-GD converges to a biased SPS solution for bounded loss function. • We extend the analysis to the lazy deployment scheme with SGD [Mendler-Dünner et al., 2020] .The latter scheme finds a bias-free SPS solution 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 on the distribution 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.Notations. Let R d be the d-dimensional Euclidean space equipped with inner product F t := σ({θ 0 , θ 1 , • • • , θ t }), where σ(•) is the sigma-algebra generated by the random variables in the operand and {θ t } is the sequence of iterates generated by the SGD-GD scheme (2). 
stationary condition for performative stability: 
 If the loss ℓ(θ; z) is strongly convex w.r.t. θ, then the decoupled performative risk J(θ; θ) admits a unique minimizer w.r.t. θ for any θ. It has hence motivated [Perdomo et al., 2020] to study the performative stable (PS) solution θ P S which is defined as a fixed point to the map T ( θ) := arg min θ∈R d J(θ; θ), i.e., θ P S = T (θ P S ).(4)In the above, the uniqueness and existence of θ P S follows by observing that T (•) is a contraction if and only if the sensitivity of D(θ), i.e., the 'smoothness' of D(θ) w.r.t. θ, is upper bounded by the inverse of condition number of ℓ(θ; z). The convergence of SGD-GD follows by analyzing (2) as a stochastic approximation (SA) scheme for the repeated risk minimization (RRM) procedure θ ← T (θ) [Mendler-Dünner et al., 2020] .For the case of non-convex 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(θ; θ). Our remedy is to concentrate on the following non-convex counter part to the PS solution: Definition 1. (δ stationary performative stable solution) Let δ ≥ 0, the vector θ δ-SP S ∈ R d is said to be an δ stationary performative stable (δ-SPS) solution of (1) if:EQUATIONWe also say that θ SP S is an (exact) SPS solution if it satisfies (5) with δ = 0. In other words, δ ≥ 0 measures the stationarity of a solution. Notice that if ℓ(θ; z) is strongly convex w.r.t. θ, 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 is a subtle but critical difference since ∇J(θ; θ) may not be the gradient of any function in θ. For example, consider ℓ(θ; z) = (1/2)∥θ -z∥ 2 and D(θ) ≡ N (Aθ, I) for some square but asymmetric matrix A, the map ∇J(θ; θ) = (I-A)θ has a Jacobian of I-A which is not symmetric. Furthermore, we observe that the mean field for SGD-GD scheme (2) is ∇J(θ; θ), which is not a gradient. The SGD-GD scheme is thus a special case of non-gradient SA scheme [Dieuleveut et al., 2023] .To get further insight, as investigated in [Dieuleveut et al., 2023] , a common analysis framework of non-gradient SA scheme is by identifying a smooth Lyapunov function linked to the recursion (2). When ℓ(•; z) is strongly convex, we may study the Lyapunov functions as the squared distance ∥θ -θ P S ∥ 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 et 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, we demonstrate how to address this challenge by identifying a time varying Lyapunov function for SGD-GD. 
main results: 
 This section presents theoretical results on the SGD-GD scheme with non-convex loss. We first show how to construct a 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 (1): A1. For any z ∈ Z, there exists a constant L ≥ 0 such thatEQUATIONwhere ∇ℓ(θ; z) denotes the gradient of ℓ(θ; z) w.r.t. θ. Moreover, there exists a constant ℓ ⋆ > -∞ such that ℓ(θ; z) ≥ ℓ ⋆ for any θ ∈ R d .A2. For any fixed θ 1 , θ 2 ∈ R d , the stochastic gradient ∇ℓ(θ 1 ; Z), Z ∼ D(θ 2 ) is unbiased such that E Z∼D(θ2) [∇ℓ(θ 1 ; Z)] = ∇J(θ 1 ; θ 2 ), and there exists constants σ 0 , σ 1 ≥ 0 such thatEQUATION)Note that A1, 2 are standard assumptions that hold for a wide range of applications and the respective stochastic optimization based training schemes. For instance, A1 requires the loss function to be smooth, while A2 assumes the stochastic gradient estimates to have a variance that may grow with ∥∇J(θ 1 ; θ 2 )∥ 2 . For the non performative prediction setting where the data distribution is not shifted by θ, i.e., D(θ) ≡ D, these assumptions guarantee that SGD algorithm (i.e., SGD-GD with Z t+1 ∼ D) to converge to a stationary solution of (1) with a suitable step size schedule [Ghadimi and Lan, 2013] . In particular, in this case A1 implies that E Z∼D [ℓ(θ; Z)] is a smooth function and serves as a Lyapunov function for the SGD algorithm.In this light, it might be tempting to use the performative risk V (θ) [cf. (1)] as the Lyapunov function for (2) and directly adopt the analysis in [Dieuleveut et al., 2023] . However, the condition A1 is insufficient to guarantee that V (θ) is smooth, and the mean field of (2) may not be aligned with ∇V (θ). Instead, from A1, 2, we proceed with a descent-like lemma for the iterates of SGD-GD: Lemma 1. Under A1, 2. Suppose that the step size satisfies sup t≥1 γ t ≤ 1/(L(1 + σ 2 1 )), then for any t ≥ 0, the sequence of iterates {θ t } t≥0 generated by SGD-GD (2) satisfiesEQUATIONProof. Fix any z ∈ Z, applying A1 and the recursion (2) lead toEQUATIONfor any t ≥ 0. Note that z ∈ Z can be any fixed sample while Z t+1 is the r.v. drawn from D(θ t ) in (2). Let p θt (z) ≥ 0 denotes the pdf of D(θ t ). We then multiply p θt (z) on both sides of the inequality and integrate w.r.t. z ∈ Z, i.e., taking the operator Z (•)p θt (z)dz. This yieldsJ(θ t+1 ; θ t ) ≤ J(θ t ; θ t ) -γ t+1 ⟨∇J(θ t ; θ t ) | ∇ℓ(θ t ; Z t+1 )⟩ + Lγ 2 t+1 2 ∥∇ℓ(θ t ; Z t+1 )∥ 2 , (10) since ℓ(θ; z)p θt (z)dz = J(θ; θ t ) according to definition (3). We next evaluate the conditional expectation, E t [•], on both sides of the above inequalityEQUATIONUsing A2, we note thatE t [∥∇ℓ(θ t ; Z t+1 )∥ 2 ] ≤ σ 2 0 + (1 + σ 2 1 )∥∇J(θ t ; θ t )∥ 2 .Reshuffling terms and using the step size condition yield the desired result (8); see §A for a detailed proof.For sufficiently small γ t+1 > 0 and when θ t is not SPS, eq. ( 8) implies the descent relation E t [J(θ t+1 ; θ t )] < J(θ t ; θ t ). This suggests that at the tth iteration, the function J t (θ) := J(θ; θ t ) may serve as a Lyapunov function for the SGD-GD scheme. Meanwhile, J t (θ) is a 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 be decomposed as:EQUATION)The first part is a difference-of-sequence 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 a closer look, the residual is the difference of evaluating θ t+1 on J t (•) and J t+1 (•), i.e.,EQUATIONThe above further depends on the differences between the distributions D(θ t ), D(θ t+1 ), 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 E[J t+1 (θ t+1 ) -J t (θ t+1 )].From (8), we anticipate the convergence of SGD-GD towards a biased SPS solution if it holdsE[J t+1 (θ t+1 ) -J t (θ t+1 )] = O(E[∥θ t -θ t+1 ∥]) = O(γ t+1 E[∥∇ℓ(θ t ; Z t+1 )]∥). Now, as seen from ( 13), establishing such relation would require D(θ) to satisfy a certain sensitivity criterion when subject to perturbation in θ. 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. (ϵ sensitivity w.r.t. Wasserstein-1 distance) There exists ϵ ≥ 0 such thatEQUATIONfor any θ, θ ′ ∈ R d . Notice that the Wasserstein-1 distance is defined asW 1 (•, •) := inf P ∈P(•,•) E (z,z ′ )∼P [∥z -z ′ ∥ 1 ], where P (D(θ), D (θ ′ ))is the set of all joint distributions on Z × Z whose marginal distributions are D(θ), D (θ ′ ).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 L 0 > 0 such that for all z, z ′ ∈ Z, andEQUATION)Our key observation is that the above conditions imply the desired Lipschitz continuity property on J(θ; •). In fact, we have:EQUATION)The proof, which is a variant of [Drusvyatskiy and Xiao, 2023, Lemma 2 .1], can be found in §B.TV distance Sensitivity. Although W1 holds for a 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 L 0 (and thus the Lipschitz continuity constant of ℓ(θ; •) given by L 0 ϵ) to be small. As an alternative, we consider a slightly stronger sensitivity condition on D(θ) via the total variation (TV) distance.C1. (ϵ sensitivity w.r.t. TV distance) For any θ, θ ′ ∈ R d , there exists a constant ϵ ≥ 0 such thatEQUATION)where δ T V (•, •) is the total variation distance defined as δ T V (µ, ν):= sup A⊂Z |µ(A) -ν(A)| = 1 2|p µ (z) -p ν (z)| dz such that µ, ν are two probability measures supported on Z and p (•) (z) denotes their probability distribution functions (p.d.f.s).Although C1 is slightly strengthened from W1, it allows us to relax the Lipschitz continuity assumption W2 on the loss. Particularly, we consider replacing W2 by: C2. There exists a constant ℓ max ≥ 0 such that sup θ∈R d ,z∈Z |ℓ(θ; z)| ≤ ℓ max .The above condition requires ℓ(•; •) to be uniformly bounded. Compared to W2, it can be easier to verify and ℓ max is typically small. For example, it holds with ℓ max = 1 for the case of sigmoid loss.Similar to W1, 2, we observe that the above conditions imply J(θ; •) is Lipschitz continuous:EQUATION)See §C. The only difference with Lemma 2 is that (18) has a different Lipschitz constant. Remark 1. It is worth noting that in lieu of C1, Mofakhami et al. [2023] assumed the following sensitivity condition with respect to the Pearson χ 2 divergence, i.e.,EQUATION)where f θ (•) represents the output of a neural network parameterized by θ, p θ (•) and p θ ′ (•) are the probability density functions (p.d.f.s) of the induced distributions D(θ) and D(θ ′ ), respectively.Our TV distance sensitivity condition in C1 constitutes a weaker condition since for any bounded sample space Z, the following holds:W 1 (D(θ), D(θ ′ )) ≤ diam(Z) • δ T V (D(θ), D(θ ′ )) ≤ diam(Z) 2 χ 2 (D(θ), D(θ ′ )),as shown in [Gibbs and Su, 2002, Sec. 2] , where diam(Z) := sup z,z ′ ∈Z ∥z -z ′ ∥ denotes the diameter of the sample space.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 supEQUATION)Then, for any T ≥ 1, the iterates {θ t } t≥0 generated by SGD-GD satisfyEQUATION)where ∆ 0 := J(θ 0 ; θ 0 ) -ℓ ⋆ is an upper bound to the initial optimality gap of performative risk.Using a fixed step size schedule, we simplify the bound as: Corollary 1. Under A1, 2, the alternative conditions W1, 2, or C1, 2. Let T ≥ 1 be the maximum number of iterations and set γ t = 1/ √ T . Let T be a random variable chosen uniformly and independently from {0, 1,EQUATION)As T → ∞, the first term in ( 22) vanishes as O(1/ √ T ) and the above shows that the SGD-GD scheme finds an O(σ 0 ϵ + (1 + σ 2 1 ) ϵ 2 )-SPS 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(σ 0 ϵ + (1 + σ 2 1 ) ϵ 2 ). The latter estimate highlights the role of the stochastic gradient's variance. To see this, let us concentrate on the case when ϵ is small. When stochastic gradient is used such that σ 0 > 0, SGD-GD finds an O(ϵ)-SPS solution; while with deterministic gradient, i.e., when ∇ℓ(θ t ; Z t+1 ) = ∇J(θ t ; θ t ) with σ 0 = σ 1 = 0, SGD-GD finds an O(ϵ 2 )-SPS solution. Such a 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 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 σ 0 , σ 1 can be controlled by the latter.Remark 2. Prior analysis in [Mendler-Dünner et al., 2020, Drusvyatskiy and Xiao, 2023] showed that with µ strongly convex loss ℓ(•; z), both the existence/uniqueness of the PS solution and the convergence of SGD-GD to the PS solution critically depend on the condition ϵ < µ/L (in addition to our A1, 2, W1). When ϵ > µ/L, it is shown that the SGD-GD scheme may even diverge. In contrary, Theorem 1 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. 
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 a new classifier in real time can be time consuming. As inspired by [Mendler-Dünner 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 ≥ 1 denotes the epoch length of lazy deployment, we haveEQUATIONFor simplicity, we focus on the case with a constant step size γ > 0. Observe that the lazy deployment scheme is a double-loop algorithm where the index t denotes the number of deployments and the index k denotes the SGD update. To analyze the convergence of ( 23), we further require the stochastic gradient to be uniformly bounded: A3. There exists a constant G ≥ 0 such that sup θ∈R d ,z∈Z ∥∇ℓ(θ; z)∥ ≤ 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 §E:Theorem 2. Under A1, 2, 3, and the alternative conditions W1, 2, or C1, 2. Let T ≥ 1 be the maximum number of deployments to be run, we set γ = 1/(K √ T ) and let T be a random variable chosen uniformly and independently from {0, 1, • • • , T -1}. For any T ≥ L 2 (1 + σ 2 1 ) 2 /K 2 , the iterates generated by the lazy deployment scheme with SGD (23) satisfy:EQUATION)where we recall that L was defined in (20) and ∆ 0 = J(θ 0 ; θ 0 ) -ℓ ⋆ .In (24), the first three terms decay as O(1/ √ T ) similar to SGD-GD, the last term simplifies to O( Lϵ/ √ K) to be controlled with 1/ √ K. The lazy deployment scheme ( 23) finds a bias-free SPS solution when T → ∞, K → ∞, contrasting with SGD-GD which admits a bias level of O( Lϵ).We remark that the above result can be anticipated. During the tth deployment, (23) runs an SGD recursion for min θ J(θ; θ t ) where it will find a stationary solution for the non-convex optimization as K → ∞. The lazy deployment scheme resembles RRM and we expect that it may find a bias-free SPS solution as inspired by [Mofakhami et al., 2023] which studied a similar algorithm. 
numerical experiments: 
 We consider two examples of performative prediction with non-convex loss based on 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] :EQUATION)For small regularization β > 0, ℓ(•; z) is smooth but non-convex. To define the data distribution, we have a set of m unshifted samplesD o ≡ {(x i , y i )} m i=1 with feature x i ∈ R d and label y i ∈ {±1}. For any θ ∈ R d , D(θ) is a uniform distribution on m shifted samples {(x i -ϵ L θ, y i )} m i=1, where ϵ L > 0 controls the shift magnitude. Applying SGD-GD to the setup yields a scheme such that A1, 2, W1 (with ϵ = ϵ L ) are satisfied, and W2 holds as ∥θ t ∥ is bounded in practice. To generate the training data, the unshifted samples D o are generated first as x i ∼ U[-1, 1] d , i.e., the uniform distribution, ȳi = sgn(⟨x i | θ o ⟩) ∈ {±1} such that θ o ∼ N (0, I), then a randomly selected 10% of the labels are flipped to generate the final y i . Furthermore, we set m = 800, d = 10, c = 0.1, β = 10 -3 , ϵ ∈ {0, 0.1, 0.5, 2}. For (2), the batch size is b = 1 and the stepsize is γ t = γ = 1/ √ T with T = 10 6 .First, we validate the convergence behavior of SGD-GD in Theorem 1. In Fig. 1 (left), we compare ∥∇J(θ t ; θ t )∥ 2 against the number of iteration t for the SGD-GD scheme over 10 repeated runs. The shaded region indicate the 95% confidence interval. We observe that after a rapid transient stage, (middle) Loss value J(θ t ; θ t ) of SGD-GD against iteration no. t. (right) SPS measure ∥∇J(θ t ; θ t )∥ 2 of greedy (SGD-GD) and lazy deployment against number of sample accessed. We fix ϵ L = 2. the SPS stationarity ∥∇J(θ t ; θ t )∥ 2 saturates and stay around a constant level, indicating that the SGD-GD converges to a biased-SPS solution. Increasing ϵ L leads to an increased bias, corroborating with Theorem 1 that the bias level is O(ϵ). Fig. 1 (middle) further evaluate the performance of the trained classifier θ t in terms of the performative risk value. Second, we compare the lazy deployment scheme in §4 with K ∈ {5, 10} and stepsize γ = 1/(K √ T ). For fairness, we test SGD-GD with batch size of b ∈ {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 et al. [1999] dataset with m = 4601 samples, each with d = 48 features. We split the training/test sets as 8 : 2. Our aim is to study the behavior of SGD-GD when training NN classifier. To specify (1), we let z ≡ (x, y) where x ∈ R d is the feature vector, y ∈ {0, 1} is label (0 for not spam, 1 for spam). Consider the regularized binary cross entropy loss:EQUATION)where f θ (x) denotes the NN classifier. The unshifted data is denoted byD o = {(x i , y i )} m i=1. Sampling from the shifted data distribution D(θ) is achieved through (i) uniformly draw a sample z ≡ (x, ȳ) from D o , (ii) maximize the following utility function:EQUATION)to get z ≡ (x, ȳ) ∼ D(θ). In practice, we take the approximation x ≈ x -ϵ NN ∇ x f θ (x).In our experiment, we set ϵ NN ∈ {0, 10, 100}, batch size as b = 8. For SGD-GD, we use γ t = γ = 200/ √ T and for lazy deployment, we use γ = 200/(K √ T ) with T = 10 5 . The NN encoded in f θ (x) consists of three fully-connected layers with tanh activation and a sigmoid output layer, i.e.,f θ (x) = Sigmoid θ ⊤ (1) • tanh(θ ⊤ (2) • tanh(θ ⊤ (3) x)) ,where θ (i) := [w (i) ; b (i) ] concatenates the weight and bias for each layer with d 1 = 10, d 2 = 50, d 3 = 57 neurons, making a total of d = 3421 parameters for θ. For the training, we initialize these parameters as N (0, 1) for weights and constant values for the biases.Fig. 2 (left) compares the SPS measure ∥∇J(θ t ; θ t )∥ 2 against the iteration number t using SGD-GD. As observed, SGD-GD converges to a near SPS solution and the behavior seems to be insensitive to ϵ NN . We speculate that this is due to the shift model ( 27) but would relegate its study to future work. Fig. 2 (middle & right) compare the greedy and lazy deployment schemes with ϵ NN ∈ {10, 10 4 } against the number of samples used. Compared to SGD-GD, lazy deployment performs relatively better as ϵ NN ↑, as seen from the no. of samples needed to reach ∥∇J(θ t ; θ t )∥ 2 = 10 -4 in the plots. This agrees with (24) which shows the dominant term as O(ϵ/ √ K) and ϵ is related to ϵ NN . 
conclusions: 
 This paper provides the first study on the performative prediction problem with smooth but possibly non-convex loss. We proposed a stationary performative stable (SPS) condition which is the counterpart of 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, O(ϵ)-SPS solution, while the lazy deployment scheme finds a bias-free SPS solution when the lazy deployment epoch is large. As an initial work on this subclass of problems, our findings can lead to more general analysis on algorithms under the non-convex performative prediction framework.  
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our data were obtained from openly available datasets and modes are classical machine learning model, mitigating any risk of misuse.Guidelines:• The answer NA means that the paper poses no 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 a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: 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 a 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was 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. 
crowdsourcing 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 as details about compensation (if any)?Answer: [NA] Justification: Our paper does not involve crowdsourcing or research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution 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. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: Our paper does not involve crowdsourcing or research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on 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 to adhere to 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. 
 
 Appendix: Proof. Under A1, for any fixed z ∈ Z, we have thatℓ(θ t+1 ; z) ≤ ℓ(θ t ; z) + ⟨∇ℓ(θ t ; z) | θ t+1 -θ t ⟩ + L 2 ∥θ t+1 -θ t ∥ 2 ≤ ℓ(θ t ; z) -γ t+1 ⟨∇ℓ(θ t ; z) | ∇ℓ(θ t ; Z t+1 )⟩ + Lγ 2 t+1 2 ∥∇ℓ(θ t ; Z t+1 )∥ 2 ,where the second inequality is due to the update rule of (2) as we recall that Z t+1 ∼ D(θ t ). Taking integration on z with weights given by the p.d.f. of D(θ t ), i.e., (•)p θt (z)dz, on both sides of above inequality leads toEQUATION) (a) = J(θ t ; θ t ) -γ t+1 ∥∇J(θ t ; θ t )∥ 2 + L 2 γ 2 t+1 E t ∥∇ℓ(θ t ; Z t+1 ) -∇J(θ t ; θ t )∥ 2 + ∥∇J(θ t ; θ t )∥ 2 , (b) ≤ J(θ t ; θ t ) -γ t+1 ∥∇J(θ t ; θ t )∥ 2 + L 2 γ 2 t+1 σ 2 0 + (1 + σ 2 1 ) ∥∇J(θ; θ t )∥ 2 ,where (a) used A2 and the property:E t ∥∇ℓ(θ t ; Z t+1 )∥ 2 = E t ∥∇ℓ(θ t ; Z t+1 ) -∇J(θ t ; θ t )∥ 2 + ∥∇J(θ t ; θ t )∥ 2 ,and (b) is due to the variance bound in A2. Rearranging terms in (28) leads to1 - L 2 (1 + σ 2 1 )γ t+1 γ t+1 ∥∇J(θ t ; θ t )∥ 2 ≤ J(θ t ; θ t ) -E t [J(θ t+1 ; θ t )] + L 2 σ 2 0 γ 2 t+1 .The step size condition implies 1 -L 2 (1 + σ 2 1 )γ t+1 ≥ 1/2. This concludes the proof.Proof. Our proof is modified from Lemma 2.1 of [Drusvyatskiy and Xiao, 2023] . By W2, sinceℓ(θ; z) is L 0 -Lipchitz in z, we have |J(θ; θ 1 ) -J(θ; θ 2 )| = |E Z∼D(θ1) ℓ(θ; Z) -E Z ′ ∼D(θ2) ℓ(θ; Z ′ )| ≤ L 0 W 1 (D(θ 1 ), D(θ 2 )). Applying W1 gives |J(θ; θ 1 ) -J(θ; θ 2 )| ≤ L 0 ϵ ∥θ 1 -θ 2 ∥ , which finishes the proof. C Proof of Lemma 3 Proof. Under C1 & C2, we observe |J(θ, θ 1 ) -J(θ, θ 2 )| = ℓ(θ; z)(p θ1 (z) -p θ2 (z))dz (a) ≤ |ℓ(θ; z)| • |p θ1 (z) -p θ2 (z)| dz ≤ ℓ max • |p θ1 (z) -p θ2 (z)| d(z) ≤ ℓ max • 2δ T V (D(θ 1 ), D(θ 2 )) (b) ≤ 2ℓ max ϵ||θ 1 -θ 2 ||.where (a) is due to the Cauchy-Schwarz inequality, (b) is due to the stated assumptions C1.Proof. We recall from Lemma 1 the following relation:EQUATION)We notice that Lemmas 2, 3 imply|J( θ; θ) -J( θ; θ ′ )| ≤ Lϵ ∥θ -θ ′ ∥,where L = L 0 if W1, 2 hold, or L = ℓ max if C1, 2 hold. Subsequently, the first term on the right hand side of ( 29) can be bounded byE t [J(θ t ; θ t ) -J(θ t+1 ; θ t )] ≤ E t [J(θ t ; θ t ) -J(θ t+1 ; θ t+1 )] + E t [|J(θ t+1 ; θ t+1 ) -J(θ t+1 ; θ t )|] ≤ E t [J(θ t ; θ t ) -J(θ t+1 ; θ t+1 )] + Lϵ E t [∥θ t+1 -θ t ∥] = E t [J(θ t ; θ t ) -J(θ t+1 ; θ t+1 )] + γ t+1 Lϵ E t [∥∇ℓ(θ t ; Z t+1 )∥].Notice thatγ t+1 Lϵ E t [∥∇ℓ(θ t ; Z t+1 )∥] (a) ≤ γ t+1 Lϵ E t ∥∇ℓ(θ t ; Z t+1 )∥ 2 (b) ≤ γ t+1 Lϵ σ 0 + 1 + σ 2 1 ∥∇J(θ t ; θ t )∥ (c) ≤ γ t+1 Lϵ σ 0 + (1 + σ 2 1 ) Lϵ + 1 4 Lϵ ∥∇J(θ t ; θ t )∥ 2 ,where (a) is due to the Cauchy-Schwarz inequality b) is due to the chain:E[∥X∥] ≤ E[∥X∥ 2 ], (E t ∥∇ℓ(θ t ; Z t+1 )∥ 2 = ∥∇J(θ t ; θ t )∥ 2 + E t ∥∇ℓ(θ t ; Z t+1 ) -∇J(θ t ; θ t )∥ 2 ≤ σ 2 0 + (1 + σ 2 1 )∥∇J(θ t ; θ t )∥ 2 ≤ σ 0 + 1 + σ 2 1 ∥∇J(θ t ; θ t )∥ 2and (c) is due to the Young's inequality. Substituting back into (29) givesγ t+1 4 ∥∇J(θ t ; θ t )∥ 2 ≤ E t [J(θ t ; θ t ) -J(θ t+1 ; θ t+1 )] + γ t+1 Lϵ σ 0 + (1 + σ 2 1 ) Lϵ + L 2 σ 2 0 γ 2 t+1 .Notice that taking full expectation and summing both sides of the inequality from t = 0 to T -1 yields the theorem.Proof. The first steps of our proof resemble that of Lemma 1 and is repeated here for completeness. Under A1, for any fixed z ∈ Z, we have thatℓ(θ t,k+1 ; z) ≤ ℓ(θ t,k ; z) + ⟨∇ℓ(θ t,k ; z) | θ t,k+1 -θ t,k ⟩ + L 2 ∥θ t,k+1 -θ t,k ∥ 2 ≤ ℓ(θ t,k ; z) -γ ⟨∇ℓ(θ t,k ; z) | ∇ℓ(θ t,k ; Z t,k+1 )⟩ + Lγ 2 2 ∥∇ℓ(θ t,k ; Z t,k+1 )∥ 2 ,where the second inequality is due to the update rule of (2) as we recall that Z t+1 ∼ D(θ t ). Taking integration on z with weights given by the p.d.f. of D(θ t ), i.e., (•)p θt (z)dz, on both sides of above inequality leads toJ(θ t,k+1 ; θ t,0 ) ≤ J(θ t,k ; θ t,0 ) -γ ⟨∇J(θ t,k ; θ t,0 ) | ∇ℓ(θ t,k ; Z t,k+1 )⟩ + L 2 γ 2 ∥∇ℓ(θ t,k ; Z t,k+1 )∥ 2 .As Z t,k+1 ∼ D(θ t,0 ), we have E t,k [∇ℓ(θ t,k ; Z t,k+1 )] = ∇J(θ t,k ; θ t,0 ), where E t,k [•] denotes the conditional expectation on the filtrationF t,k = σ({θ 0 , θ 0,1 , • • • , θ 0,K , θ 1,1 , • • • , θ t , θ t,1 , • • • , θ t,k }).Taking the conditional expectation E t,k [•] on both sides yieldE t,k [J(θ t,k+1 ; θ t,0 )] ≤ J(θ t,k ; θ t,0 )-γ ∥∇J(θ t,k ; θ t,0 )∥ 2 + Lγ 2 2 E t,k ∥∇ℓ(θ t,k ; Z t,k+1 )∥ 2 (30) (a) = J(θ t,k ; θ t,0 ) -γ ∥∇J(θ t,k ; θ t,0 )∥ 2 + L 2 γ 2 E t,k ∥∇ℓ(θ t,k ; Z t,k+1 ) -∇J(θ t,k ; θ t,0 )∥ 2 + ∥∇J(θ t,k ; θ t,0 )∥ 2 , (b) ≤ J(θ t,k ; θ t,0 ) -γ ∥∇J(θ t,k ; θ t,0 )∥ 2 + L 2 γ 2 σ 2 0 + (1 + σ 2 1 ) ∥∇J(θ t,k ; θ t,0 )∥ 2 ,where (a) used A2 and the property:E t,k ∥∇ℓ(θ t,k ; Z t,k+1 )∥ 2 = E t,k ∥∇ℓ(θ t,k ; Z t+1 ) -∇J(θ t,k ; θ t,0 )∥ 2 + ∥∇J(θ t,k ; θ t,0 )∥ 2 ,and (b) is due to the variance bound in A2. Rearranging terms in ( 30),EQUATION)The step size condition implies 1-L 2 (1 + σ 2 1 )γ ≥ 1 2 . γ 2 ∥∇J(θ t,k ; θ t,0 )∥ 2 ≤ J(θ t,k ; θ t,0 ) -E t,k [J(θ t,k+1 ; θ t,0 )] + L 2 σ 2 0 γ 2 .Taking summation on k from 0 to K -1 leads toEQUATION)Recall that θ t+1,0 = θ t+1 = θ t,K . Subsequently, the first term on the right hand side of ( 32) can be bounded byE t [J(θ t ; θ t ) -J(θ t+1 ; θ t )] ≤ E t [J(θ t ; θ t ) -J(θ t+1 ; θ t+1 )] + E t [|J(θ t+1 ; θ t+1 ) -J(θ t+1 ; θ t )|] ≤ E t [J(θ t ; θ t ) -J(θ t+1 ; θ t+1 )] + Lϵ E t [∥θ t+1 -θ t ∥] = E t [J(θ t ; θ t ) -J(θ t+1 ; θ t+1 )] + γ Lϵ E t K-1 k=0 ∇ℓ(θ t,k ; Z t,k+1 ) .Notice that through a careful use of A2 and the independence between stochastic gradients, we haveEQUATIONEQUATIONwhere the last inequality used the property √ x ≤ c 2 + x 2c for any c > 0. Substituting above results to (32) and taking full expectation on both sides give usEQUATION+ γ Lϵ √ 2Kσ 0 + 2 2(K + σ 2 1 ) Lϵ + LK 2 σ 2 0 γ 2 .Next, we lower bound the left hand side by observing:K-1 k=0 E ∥∇J(θ t,k ; θ t,0 )∥ 2 (a) ≥ K-1 k=0 E 1 2 ∥∇J(θ t , θ t )∥ 2 -∥∇J(θ t,k ; θ t ) -∇J(θ t , θ t )∥ 2 (b) ≥ 1 2 KE ∥∇J(θ t , θ t )∥ 2 -L K-1 k=0 E ∥θ t,k -θ t ∥ 2 (c) = 1 2 KE ∥∇J(θ t , θ t )∥ 2 -L K-1 k=0 E k-1 ℓ=0 γ∇ℓ(θ t,ℓ ; Z t,ℓ ) 2 ≥ 1 2 KE ∥∇J(θ t , θ t )∥ 2 -Lγ 2 K-1 k=0 k k-1 ℓ=0 E ∥∇ℓ(θ t,ℓ ; Z t,ℓ )∥ 2 (d) ≥ 1 2 KE ∥∇J(θ t , θ t )∥ 2 -Lγ 2 K-1 k=0 k k-1 ℓ=0 G 2 = 1 2 KE ∥∇J(θ t , θ t )∥ 2 -LG 2 γ 2 • K(K -1)(2K -1) 6 ≥ 1 2 KE ∥∇J(θ t , θ t )∥ 2 -LG 2 γ 2 • K 3 3 ,where (a) is due to the fact that ∥a∥ 2 ≥ 1 2 ∥a + b∥ 2 -∥b∥ 2 , for any a, b ∈ R n , (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 toK-1 k=0 k 2 = K(K-1)(2K-1) 6 ≤ K 33 , when K ≥ 1. Substituting the above lower bound to (35) and rearrange terms lead toγK 8 E ∥∇J(θ t , θ t )∥ 2 ≤ E [J(θ t , θ t ) -J(θ t+1 , θ t+1 )] + 1 12 γ 3 LG 2 K 3 + γ Lϵ √ 2Kσ 0 + 2 2(K + σ 2 1 ) Lϵ + LK 2 σ 2 0 γ 2 . Taking summation from t = 0, 1, • • • , T -1 gives us γK 8 T -1 t=0 E ∥∇J(θ t , θ t )∥ 2 ≤ E [J(θ 0 , θ 0 ) -J(θ T , θ T )] + T 12 γ 3 LG 2 K 3 + γT Lϵ √ 2Kσ 0 + 2 2(K + σ 2 1 ) Lϵ + T LK 2 σ 2 0 γ 2 .Dividing γKT /8 on both sides, we have1 T T -1 t=0 E ∥∇J(θ t , θ t )∥ 2 ≤ 8∆ 0 γKT + 4Lσ 2 0 γ + 2 3 γ 2 LG 2 K 2 + 8 Lϵ K √ 2Kσ 0 + 2 2(K + σ 2 1 ) Lϵ ,where we recall ∆ 0 := J(θ 0 ; θ 0 ) -ℓ max .This section provides additional details for the numerical experiments that were omitted due to space limitation.Synthetic Data with Linear Model Fig. 3 shows the trajectories of training and testing accuracy with the SGD-GD scheme under different shift parameters, using the same settings as in Fig. 1 (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 θ o , but without the label flipping step. In this case, although increasing the shift leads to a larger risk value J(θ t ; θ t ) and more biased stationary solution in terms of ∥∇J(θ t ; θ t )∥ 2 [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 a deteriorated or improved model accuracy.Importantly, the effects can be unpredictable in general, especially when only biased SPS solutions are guaranteed. Fig. 4 shows the trajectories of loss values J(θ t ; θ t ), training and testing accuracy with the greedy and lazy deployment scheme using the same settings as in Fig. 1 (right). We observe similar behaviors as indicated in Fig. 3 . Moreover, we notice that although the lazy deployment scheme converges to a 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 a larger noise variance σ 0 . Real Data with Neural Network Model Similar to the above paragraph, Fig. 5 , 6, 7 show the trajectories of train/test accuracy, for greedy/lazy deployment scheme when ϵ ∈ {10, 10 4 } for completeness. The figures demonstrate similar behavior as described in the main paper. Moreover, we observe that the sensitivity parameter ϵ NN has a small effect in the training/testing acccuracies of the trained models. Learning. There are many potential societal consequences of our 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 or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 or 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 a system learns from feedback over time, improving the efficiency and accessibility of ML).Note that V (θ) is still non-convex. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 
2. 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.
questions: questions: /
limitations: limitations: /
paper_summary: paper_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.
strength_weakness: strength_weakness: Cons:

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.
questions: questions: The reviewer is generally positive about this work. One question would be: 

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?
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

In A2, the first part of the sentence is not an assumption; it’s true just by the definition of J?

In Lemma 1, Theorem 1 (and possibly other places) please use parentheses in the step size condition. It should be 1/(L(1+sigma1^2)).

Very minor suggestion: personally I find it more appropriate to see Theorem 1 as a lemma and Corollary 1 as the main theorem.

Please don’t use the symbol T in Theorem 2 for the random step because you use that symbol in eq. (4).
questions: 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?

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?
limitations: limitations: There is not much discussion of limitations, though I don't think it is necessary.
paper_summary: paper_summary: A nice paper that studies nonconvex performative prediction optimization. Proposed a new stationarity notion and demonstrated convergence for SGD with greedy deployment.
strength_weakness: strength_weakness: 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.
questions: 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. 
2. 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?
3. 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: limitations: See questions above.

Comments: title: Response to the author
Discussions
comment: The reviewer thanks the author for the response. After reading the rebuttal discussion from all reviewers, the reviewer would like to maintain the score.
Thank you for the detailed response! Everything makes sense.
Thanks for the clarifications.
Thank you for reading and replying to the responses. 

We agree with the reviewer that from the perspective of solving a stochastic optimization problem, using additional structure to decouple the source of randomness and decision may lead to better algorithms, e.g., lower sample complexity. However, we believe that an important aspect is that there are a number of scenarios for performative prediction where the learner does not **know** this "additional structure". Worse still, the learner may not even be aware of the distribution shift in the problem. 

A concrete example is the training of classifiers (e.g., for spam emails) - specifically in an online setting where the classifier has to be updated using current training data, note the latter may come from a decision dependent distribution $Z_{t+1} \sim D(\theta_t)$. On the other hand, it is likely that the learner does not know the form of decision-dependency in the training data since knowing the latter requires precisely knowing the behavior of the (normal and spam) email users. As a result, the only knowledge available to the learner is the current training data sample $Z_{t+1}$ and the form of cross entropy loss used for formulating the stochastic gradient $\nabla \ell( \theta; Z_{t+1} )$. In the absence of knowledge of $D(\theta)$, it would be impossible for the learner to exploit the problem structure and derive a reformulation to the performative optimization problem.
Thanks for the detailed responses. My concerns are mostly addressed. I will keep the score. 

Purely for discussions, understanding and improving "non-gradient" dynamics is definitely important. However, if in various applications of performative prediction optimization, there admit a more classical stochastic optimization formulation using additional structure that can decouple the source of randomness and the decision, it is unclear why one has to model it as a more general performative prediction optimization problem.