Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Stochastic Bias and Remedies
Authors: Qiang LI
Michal Yemini
Hoi To Wai
Venue: ICML 2025 poster (2025)
Keywords: Clipped Stochastic Algorithm
Performative Prediction
(Non)convex Optimization
Primary area: optimization->stochastic
TL;DR: This paper studies the convergence properties of two clipped stochastic algorithms: Clipped SGD and DiceSGD, in the performative prediction setting, where the data distribution may shift due to the deployed prediction model.

Abstract: This paper studies the convergence of clipped stochastic gradient descent (SGD) algorithms with decision-dependent data distribution. Our setting is motivated by privacy preserving optimization algorithms that interact with performative data where the prediction models can influence future outcomes. This challenging setting involves the non-smooth clipping operator and non-gradient dynamics due to distribution shifts. We make two contributions in pursuit for a performative stable solution with these algorithms. First, we characterize the stochastic bias with projected clipped SGD (PCSGD) algorithm which is caused by the clipping operator that prevents PCSGD from reaching a stable solution. When the loss function is strongly convex, we quantify the lower and upper bounds for this stochastic bias and demonstrate a bias amplification phenomenon with the sensitivity of data distribution. When the loss function is non-convex, we bound the magnitude of stationarity bias. Second, we propose remedies to mitigate the bias either by utilizing an optimal step size design for PCSGD, or to apply the recent DiceSGD algorithm [Zhang et al., 2024]. Our analysis is also extended to show that the latter algorithm is free from stochastic bias in the performative setting. Numerical experiments verify our findings.

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Stochastic Bias and Remedies
Qiang Li Michal Yemini Hoi-To Wai!
Abstract
the training of prediction models under distribution shifts (Quinonero-Candela et al., 2022) where the data may 'react' to the changing prediction models. A common applica- tion scenario is that the training data involve human input that responds strategically to the model (Hardt et al., 2016). Distribution shifts affect the convergence of SGD-type al- gorithms and their efficacy as the distributions of gradient estimates vary gradually. The modeling of such behavior has led to the performative prediction problem (Perdomo et al., 2020); see the recent overview (Hardt & Mendler-Dünee 2023).
This paper studies the convergence of clipped stochastic gradient descent (SGD) algorithms with decision-deeenddnt data distribution. Our setting is motivated by privacy preserving opti- mization algorithms that interact with performa- tive data where the prediction models can influ- ence future outcomes. This challenging setting in- volves the non-smooth clipping operator and non- gradient dynamics due to distribution shifts. We make two contributions in pursuit for a performa- tive stable solution using clipped SGD algorithms. First, characterize the clipping bias with pro- jected clipped SGD (PCSGD) algorithm which is caused by the clipping operator that prevents PCSGD from reaching a stable solution. When the loss function is strongly convex, we quantify the lower and upper bounds for this clipping bias and demonstrate a bias amplification phenomenon with the sensitivity of data distribution. When the loss function is non-convex, we bound the mag- nitude of stationarity bias. Second, we propose remedies to mitigate the bias either by utilizing an optimal step size design for PCSGD, or to ap- ply the recent DiceSGD algorithm (Zhang et al., 2024). Our analysis is also extended to show that the latter algorithm is free from clipping bias in the performative setting. Numerical experiments verify our findings.
For the performative prediction problem, there is growing literature on developing stochastic algorithms find fixed point solution of the repeated risk minimization procedure, also known as the performative stable (PS) solution(s). In the absence of knowledge of the distribution shift, the latter is the natural solution obtained by stochastic approxima- tion algorithms. In particular, most prior works have only focused on settings when the loss function is strongly con- vex, e.g., (Mendler- Xiao, 2023; Brown et al., 2022: Li Wai, 2022). When the loss function is non-convex, the existing results much rarer. To list few, (Mofakhami et al., 2023) assumes least-square like loss function; (Li & Wai, 2024) provided guarantees for general non-convex performative prediction. As an alternative, prior works also studied stochastic algo- rithms for finding performative optimal solutions by an extra step that estimates the form of distribution shifts (Izzo et al., 2021; Miller et al., 2021; Narang et al., 2023).
et al., 2020; Drusvyatskiy
However, most of the existing works in the performative pre- diction literature have focused on analyzing SGD algorithms admitting a smooth drift term. An open problem in the per- formative prediction literature is to analyze the behavior of clipped SGD algorithms which limit the magnitude of the stochastic gradient at every update step; this in turn distorts the considered distribution shift compared with the nominal dynamics with no clipping. Gradient clipping is used to deal with multiple obstacles in learning algorithms such as the need for privacy preservation (Abadi et al., 2016), deal- ing with gradient explosion in non-smooth learning (Shor, 2012) such as training neural networks (Mikolov et al., 2012: Zhang et al., 2020a), solving et al., 2015), etc. Despite the difficulty with treating the non-
1. Introduction
A recent line of research in statistical learning is analyze the behavior of stochastic gradient (SGD) type algorithms in tackling stochastic optimization problems with decision- dependent distributions. The latter can be motivated by
'Department of System Engineering and Engineering Manage- ment, The Chinese University of Hong Kong, Hong Kong 'Faculty of Engincering, Ilan University, Israel. Correspondence to: Hoi-To Wai <htwai @ @e edw..edu..ke.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).
problems (Hazan

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
smooth drift term with clipping, the clipped SGD algorithm has been analyzed in multitude of works in the standard Li.d. sampling setting with non-decisionnddeenderr data. In fact, (Mai & Johansson, 2021) studied the non-smooth optimization setting, and (Gorbunov et al., 2020) analyzed the convergence under heavy-tailed noise. On the other hand, it was found in (Chen et al., 2020) that the clipped SGD may exhibit an asymptotic bias, i.e. deviation from the optimal/stationary solution, for asymmetric gradient distri- bution, and later on (Koloskova et al., 2023) showed that the bias can be unavoidable. This led to several recent works which considered debiasing clipped SGD, c.g., (Khirirat et al., 2023) studied bias-free clipped SGD for distributed optimization, (Zhang et al., 2024) studied differentially private SGD algorithm using two clipping operators simul- taneously.
$5 presents the numerical experiments.
Notations. Let RR be the d-dimensional Euclidean space equipped with inner product (-1 and induced norm | = (< z). [[|] denotes taking expectation w.r.t all random- ness, E. [ == [-FFF means taking conditional expectation on filtration F. =- a(00, O,, ,,,)), where a(-) is the digma-algebra generated by the random variables in the operand.
2. Problem Setup
This section introduces the performative prediction problem and a simple projected clipped SGD algorithm. Our goal is to learn a prediction//lassifcattii model 0 E X via the stochastic optimization problem:
mingex E ( 2)),
(I)
The current paper aims to study the convergence of clipped SGD algorithms in the performative prediction setting. We focus on the interplay between the distribution shift and the non-smooth clipped updates. Our main contributions are:
where X' S IRd is closed convex set and ((.) is differen- tiable w.r.t. 0.
An intriguing feature of (1) is that the optimization problem is defined along with a decision decision-depender where the distribution of the sample Z ~ D(O) depends on O. For example, it may take the form of the best response for a utility function parameterized by A. This setup models scenario where the prediction model may influence the outcomes it aims to predict, also known as the performative prediction problem: see (Perdomo et al., 2020; Hardt & Mendler-Dünner, 2023).
distribution D D(0)
We show that PCSGD converges in expectation to a neigh- borhood of the performative stable solution, a fixed point studied by Perdomo et al. (2020). For strongly convex losses, while the convergence rate is (1/tt) where t is the iteration number, we show that the clipping opera- tion induces an asymptotic clipping bias. For non-convex losses, we show that in T' iterations, the scheme converges the rate of ((1/VT) towards a biased stationary per- formative stable solution. In both cases, we show that the magnitude of bias is proportional to the sensitivity of distribution shift and clipping threshold.
The challenge in tackling (1) lies in that the decision vari- able O appears in both the loss function {(0; Z) and the distribution D(0). As result, (1) is in general non-convex even if É(-) is (strongly) convex. To this end, a remedy is to study the fixed point solutions deduced from tackling the partial optimization of minimizing Ez ( [e(0; Z)] w.r.t. O when the distribution depends on a fixed O.
For the case of strongly convex losses, we further show that there exists matching lower bound for the asymp- totic clipping bias upon specifying the class of performa- tive risk optimization problem. Together with the derived upper bound, we demonstrate a bias amplification effect of PCSGD when subject to distribution shift in performa- tive prediction.
When E(-) is strongly convex in 6, popular solution con- cept is the performative stable (PS) solution (Perdomo et al., 2020):
As a remedy to the bias effect of PCSGD, we study the re- cently proposed DiceSGD algorithm (Zhang et al., 2024). We show that with doubly clipping mechanism on both the gradient and clipping error, the algorithm can con- verge exactly (nearly) to the PS solution under strongly convex (non-convex) loss.
Definition 1. The solution Prs E X called a PS solution to (1) if it satisfies
0 Ops = arg mingex Ez~D(ere)
(2)
Note that Pps is unique and well-defined provided that (i) the loss function is smooth, (ii) D(0) is not overly sensitive to shifts in 0: see $3.1 for details.
Further, we show that there exists a tradeoff between the differential privacy guarantee and computation complexity that affects the optimal step size selection. The paper is organized as follows. $2 introduces the performative pre- diction problem and the PCSGD algorithm. $3 presents the theoretical analysis for PCSGD. $4 discusses the DiD algorithm and how it mitigates the clipping bias. Our analy- sis includes both strongly convex and non-convex settings.
Alternatively, when E(-) is non-convex in @ and X = Rd, a recent solution concept is the stationary PS (SPS) solution (Li & Wai, 2024):
Definition 2. The solution OSPS E X is called a stationary PS solution to (1) if it satisfies
E (Vt.D((srs)(((((0.))) Z)) =
(3)
2

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
Note that if E(-) is strongly convex, (3) will recover the definition of PS solution in (2).
3. Main Results for PCSGD
In pursuit for a stochastic algorithm that finds Ops or Ssps, we first study the convergence properties of PCSGD, Ad- ditionally, we examine the tradcoff' between model efficacy and privacy preservation of the algorithm.
It is clear that ps. Asps do not solve (1), nor are they stationary solutions of (1), However, they remain reasonable estimates to the solutions of (1). As shown in (Perdomo et al., 2020, Theorem 4.3), the disparity between Pp and the optimal solution to (1) is bounded by the sensitivity of the decision-dependdet distribution (cf. A5).
3.1. Analysis of the PCSGD Algorithm
The analysis of (4) involves challenges that are unique to the distributions. Curiously, the expectation of the unclipped stochastic gradient (ε(O,; Ze+ is not gradient. To see this, consider the special case of
To search for Ops or Osps. SGD-based schemes with greedy deployment, i.e., the learner deploys the latest model at the population after every SGD update, have been widely deployed, see -Mendeer-üünnee et al., 2020; Drusvyatskiy & Xiao, 2023; Li & Wai, 2024).
{(0 = (1/2)||0 Z11
Motivated by privacy preserving optimization (Abadi al., 2016) and improved stability in training deep neural net- works (Zhang et al., 2020a), in this paper we are interested in SGD algorithms which clip the stochastic gradient at each update. With the greedy deployment scheme in mind, our first objective is to study the projected clipped SGD (PCSGD) algorithm for performative prediction:
and Z ~ D(0) + 2 ~ (A0;1). Observe that [ Z++1) = ()-,)0, has a Jacobian of I --44 A which is asymmetric whenever A is asymmetric. Analyzing PCSGD requires studying a non-gradient dynamics with non-smooth drifts induced by the clipping operator. In the subsequent discussion, we analyze PCSGD through identi- fying a suitable I. Lyapunov function depending on properties of the loss function {(-).
Deploy: Z1+1 D(0)).
(4)
Update: O.+1- Px (0.- - 7 cllpp 1)),
(5)
We define the shorthand notation:
where (x) denotes the Fuclidean projection operator onto X. and (-) is the clipping operator: for any g E Rdd,
f(O1. 02) == Ez- [e(01; 2)].
(lip.(g) 9 E IR + min (1,c/11g))2) g:
(6)
Unless otherwise specified, the vector ( 02) refers to the gradient taken w.r.t. the first argument 0,. We begin by stating a few assumptions pertaining to the performative prediction problem (1):
such that > 0 is a clipping parameter. Notice that if - 0o, (4) is reduced to the projected SGD algorithm for
performative prediction analyzed in (Mendler-Dünner et al., 2020; Drusvyatskiy & Xiao, 2023). Additionally, when D(0) is independent of 0, i... D(0)- = D for all 0 E X, the PCSGD algorithm does not exhibit a distribution shift and coincides with a projected version of the standard clipped SGD algorithm examined in (Koloskova al., 2023). Thus, our model and results extend both (Mendler-Dünne) et al., 2020; Drusvyatskiy & Xiao, 2023) and (Koloskova et al., 2023).
A1. For any ① E X. the function f(0; 0) is μ strongly convex w.r.t. O, i.e., for any 0', 00 E X.
f(O'; 0) > f 0) + (V 0) 0' 0) + 2 1 01
A2. The gradient map Vi(;3) is L-Lipcchitz ie.,for any 0,, 0,.02 E X, 21, 22 Z,
[V(((12)1) 2()0222))1 < L(10) - 0211 + +|2 22
For c < 0o and especially when e < [[; Ze+1 Ill the PCSGD recursion pertains a non- non-gradient dynamics with
Moreover, there exists a constant e > -00 such that ((0;2) 2 t" for any O X.
non-smooth drifts due the clipping operator; see Sec. 3.
Prior analysis of PCSGD are no longer applicable in this scenario.
The above assumptions are common in the literature, e.g.. (Perdomo et al., 2020; Mendler- Dünner et al., 2020; Drusvy- atskiy & Xiao, 2023). In addition, we require that
Remark 1. Under the performative prediction setting, (Drusvyatskiy & Xiao, 2023) considered an alternative clip- ping model which approximates the loss function E(O; 2) by linear model Eor (0: := E(0':2) + (V((0': 2) 1 0*), then updates O by applying a proximal gradient method to(O, z) within bounded set. This clips the models under training instead of clipping V 2) as in (4). Such algo- rithm belongs to the class of model based gradient methods whose fixed point is 0r ps when E(-) is strongly convex.
A 3. There exists constant G 2 0 such that supoex,=ez ( G.
This condition can be satisfied if X' is compact; or for cases such as the sigmoid loss functions. Notice that a similar condition used in (Zhang et al., 2020a). In some cases, we will use the following standard variance condition to obtain tighter bound:
3

---

Clipped SGD Algorithms for Performative Prediction:
Tight Bounds for Clipping Bias and Remedies
A4. There exists constants do: 01 2 such that for any
that (8) holds with 6 O(e² + oî) Our bound highlights the dependence on t and the distribution shift parameter 9..
0g O2 X, it holds
From (8), as t + oo, with properly tuned step size, the first term decays sub-exponentially to zero, the second term also converges to zero if 7/- =
Bx~D(0>)
[V((0: (
$ 000 + of [V](((
Regardless of the step size choice, the last term never vanish. It indicates an asymptotic clipping bias of PCSGD and coincides with the observation in (Koloskova et al., 2023) for non-decision- dependent distribution.
Strongly Convex Loss We first discuss the convergence of PCSGD towards Pps under A1. We provide both upper and lower bounds for the asymptotic bias of PCSGD, and demonstrate a bias amplification effect as the sensitivity parameter of the distribution 3 increases (cf. A5). Our result gives the first tight characterization of the bias phenomena in the literature.
As l - the bound in (8) converges to non-vanishing clipping bias term that reads
Bias = SC2/
99)
Even when 3 O, this bias term is improved over (Zhang et al., 2020a) which obtained an (1/cc scaling. It turns out that the above characterization of the bias is tight w.r.t. μ L8. We observe:
To establish the convergence of PCSGD in this case, we will need the following additional assumptions:
A5. There exists? 3 2 0 such that
(I(D()) S 0|10 0'1, V0,0'E EX.
Theorem 4. (Lower bound) For any clipping thresh- old c E G), there exists a function E(0; Z) and a decision-depentee
Notice thut
distribution D(0) satisfying A1, 2, 3, 5, such that for all fxed-points of PCSGD 0xc satisfying
Wi(+')= = inf (e |||= - ='111] JEI(.)
E Ez~D( (eciii.V((O.... Z>}l 0, it holds that
1 - 0psl = 2 (1/(=-L3)))
(10)
is the Wasserstein-1 distance, where J (D(O), D (0') is the set of all joint distributions on Z x Z whose marginal distributions are D(0),
The proof is relegated to SC.
D (6').
Provided that / < f.- Theorems and 4 show that PCSGD admits clipping bias' of 0(1/(H LB)²). It illustrates bias amplification effect where as the sensitivityy level of distribution 3 increases, the bias will increase as B t 4. This is a unique phenomenon to performative prediction where in addition to the clipping level, the data distribution contributes to the bias.
We emphasize that 3 in A5 quantifies the sensitivity of the distribution against perturbation with respect to the decision model 0. It will play an important role for the analysis below. Notice that A1, 2, 5 imply that ||0* 0rsll < 2L0 where 0* E Arg mineex E (e; Z) is an optimal solution to the performative risk minimization problem (Perdomo et al., 2020).
Non-convex Loss Next, we discuss the convergence of PCSGD when the loss function is smooth but possibly non- convex, i.e., without A1.
The first result upper bounds the squared norm of the error 0, : 0.-0ps at the tth iteration of PCSGD in expectation:
Theorem 3. (Upper bound) Under AI, 2, 3, 5. Suppose
Our study concentrates on the case where X' = Rd such that the projection operator is equivalent to an identity operator. We consider the following condition:
that B < 4, the step sizes (re are non-increasing and
satisfy i) Te-1 < 1 K-LΩ ,t and ii) 7/2 < p-LB- Then, for any 2 1, the expected squared distance between O
and the performative stable solution Ops satisfies
A6. There exists 3 2 O such that
drv ( D(0)) < 0 0'1, V0 e X.
E E1
< 1=1
II in))ll001 +
H+1
201 n
7411 +
8C1
n
(8)
drv(D(0), where drv (D(0), D(O')) denotes the total variation (TV) distance between the distributions D(0), D
where := 2(62 + G2), Ci = (maxx c, 2 and j = L8.
The interpretation of 3 is similar to that of A5. Notice that as dr v) 2 W1 (μ, v), A6 yields a stronger requirement the sensitivity of the distribution shift than A5 in general. Moreover, we require that
The proof is relegated to $B. We remark that A3 assumes that the stochastic gradient is uniformly bounded, where G also accounts for the variance of stochastic gradient. If the additional assumption such as A4 holds, it can be proven
'The lower bound in Theorem 4 holds for any B 2 0. When 3 2 4, PCSGD may not converge.

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
A 7. There exists a constant bmax sup ( 2)1 S Emax-
0 such that
To fix idea, we first introduce the definition of (e, d) differen- tial privacy (DP) measure which is customary for measuring the level of privacy leakage of a stochastic algorithm:
The above condition can be satisfied in practical scenarios where (1) involves the training of nonlinear models such as neural networks with bounded outputs.
Definition 6. (Dwork & Roth, 2014) A randomized mecha- nism M: : D + RR satisfies (e, 3)-ddiferentidd privacy if any two adjacent inputs D D' e DD which differs by only I different sample, and for any subset of outputs S C R.
Under the above conditions, we observe the following upper bound on the SPS measure in Definition 2 for the clipped SGD algorithm:
Pr[M(D) E S] S ef Pr[M(DD)) E E +
(12)
Theorem 5. Under A2, 3, 4, 6, 7. Let the step sizes satisfy SUP121 7t S 2(I+a])' Then, for any T 2 1, the iterates
The definition can be understood through the case with e, R O. In such case, the output (which consists of the entire training history) of an DP algorithm on two adjacent databases, Do, D/ will be indistinguishable, thus protecting the identity of each data sample.
{0, 3220 generates by (4) satisfy:
T-1
Σ 741B E (0;00));)))) 800 + 4
7+
To discuss privacy preservation in the framework of (Abadi et al., 2016) using Definition 6, we need to introduce a few specifications on the performative prediction problem (1) and modifications to the PCSGD algorithm. First, we consider a fixed, finite database setting for (1). The database consists of m samples Dg := { The decision-dependen distribution D(0) is defined accord- ingly: Z ~ D()) refers (batch of) sample drawn from the database Du with distribution shift governed by a ran- dom map S X - Z. Let 8; (0) be realization of S; (0),
T-1
+ +86(3,0) c)
(1I)
1=0
where Do := (lf 0o) )*] is an upper bound to the initial optimality gap for performative risk, and
= 8(1 + ) 3) +2 ma
The proof is relegated to $D.
To get further insights, fix any T 2 and set constant step size 7t 1/vT, we let T be random variable chosen uniformly and independently from 10, T 1}. The iterates satisfy:
= E, + (0), ~~ Uniff(mm]).
(13)
Second, we concentrate on a slightly modified version of (4) proposed in (Abadi et al., 2016): set Z D(O:),
< <(A0 Lod
[IV <
+ +88(3,c). c). VT
0.+1 P=(00-
(14)
for = O,.,,, 1, where C++1 ~ N (N, I) is an ar- tificial (Gaussian) noise added to preserve privacy. Com- pared to approaches such as (Chaudhuri et al., 2011) which directly add Laplacian noise to SGD, the algorithm with clipping offers better numerical stability.
We observe that the first term vanishes as T + oc. The second term represents an upper bound the asymptotic bias for the clipped SGD algorithm that scales with the distribution shift's sensitivity B and the clipping threshold Notice that as shown in (Koloskova et al., 2023), the clipped SGD algorithm admits a non-zero asymptotic bias for the case of non-convex optimization. In comparison, our bound can be directly controlled by the clipping threshold.
Overall, we observe that (14) is a randomized mechanism applied on the fixed dataset Du, where the distribution shifts is treated as a part of the mechanism. In fact, we can analyze the DP measure of PCSGD using the following corollary of (Abadi et al., 2016):
Compared the findings for the strongly convex case, while the asymptotic bias persists in Theorem 5 and also depends on B and max{G c, 0}, the latter effects are combined in an additive fashion. Nevertheless, we suspect that this bound on the bias can be improved in the non-convex case. We note that in general, finding tight lower bound for the convergence of clipped SGD in the non-convex, decision- dependent setting is an open problem.
Corollary 1. (Privacy Guarantee) For any S. T //²2. 8 (0, 1). and e >> 0, the PCSGD algorithm with greedy deployment is (e, 6)DD after T iterations if we let o < log(1/8)/
See $E for detailed proof. Corollary 1 states that PCSGD can achieve (e, 5)-DP with an appropriate DP noise level. Furthermore, the /T dependence for Op leads to an ad- ditional source of bias in (8). Together with Theorem 3, the corollary gives a guideline for setting the algorithm's 'ss parameters such as clipping threshold e and step size 7.
3.2. Differential Privacy Guarantees
Our next objective is to study the implications of the conver- gence analysis on the privacy preservation power of PCSGD.
5

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
We are now equipped with the machinery study the impli- cations of previous convergence results with respect to the DP guarantees for strongly convex ((-). Suppose that the DP parameters (E, 6) are fixed. From Corollary I, the DP noise variance op is proportional to T. It follows that increas- ing T' leads to an increase in the error term 6 observed in Theorem and adds to the bias even when ?r - (1/TT). In this light, the next result demonstrates how to design an optimal constant step size that minimizes the upper bound in (8) corresponding to the efficacy of the model:
Algorithm DiceSGD with Greedy Deployment
1: Input: C1. C2, ag, 01. E, 6, Du, op with C2 2 C2, initialization dg. eg = 0.
2: for t. = 0 to T - do
3: Draw new sample Z ~ D(O,) and Gaussian noise
{41 ~ (0, I).I).
4: U++1 clipc, (Vi(0); 7++1)) )} + clipo,(et)
5: au+1 = 0: N (1 + ((+1);
C++1 ex + Ve(O,; 21+ 1/41.
6: end for
Corollary 2. (Finite-lime Analysis) Fix the privacy parame- ters at (e, 6) and clipping threshold at c. Assume that G and a constant step size is used in PCSGD. For all T 2 1, to achieve the minimum for 0z 11?, the optimal constant
7: Output: Last iterate 0r.
tuning the step size y and clipping threshold c, as in Corol- laries 2, 3, it may not be feasible for practical applications as the problem parameters such as fı, G may be unknown.
step size can be set as
7"t log A(P) nf
where (n)) 2(2(c2 (22 (15)
Tha 10
In this section, we discuss how to reduce the clipping bias through applying recently proposed clipped SGD algo- rithm DiceSGD (Zhang et al., 2024). The latter is proven to achieve DP while converging to the exact solution of a convex optimization problem. We adapt this algorithm in the performative prediction setting and show that it removes the clipping bias infficted by PCSGD.
Let o= =
d (1/6(1/6) then (8) simplifies to
m
0r 1|= 0
C1 772
2 + G2
G²
26
E
log
Tp
óc2
Besides the O(1/T) dependence, we observe that 7* is affected by the sensitivity parameter through p?,, and the DP parameters e, 8.
For the subsequent discussion, we consider the uncon- strained setting X' R2. The DiceSGD algorithm is summarized in Algorithm I with the greedy deployment mechanism for the performative prediction setting. Com- pared to PCSGD, the notable differences include the use of two clipping operators in line 4 for forming the stochastic gradient estimate 1 and an error feedback step in line 5 where e, accumulates the error due to clipping. The vector ea Rd is private variable kept by the learner.
Lastly, we examine the case when T >>>>> Observe that by setting ? c2/ for any 02 > 1, the first term in (8) vanishes with sufficiently large T. Similar to the above corollary, enforcing DP guarantee leads to an asymptotic bias in (8) which depends on the interplay between the clipping threshold c, DP noise variance obp. etc. We obtain the following asymptotic guarantee upon optimizing the clipping threshold c:
Corollary 3. (Asymptotic Analysis) Fix the privacy param- eters at (5, Let T >> and set 7t = (1 + c2) (iTT), the optimum asymptotic upper bound for the deviation from ps in Theorem 3 is given by
We remark that the pseudo code describes general imple- mentation which includes the Gaussian noise mechanism for privacy protection. As shown in (Zhang et al., 2024), the use of two clipping operators reduces the privacy leakage. With an appropriate op. the algorithm guaranteed to achieve (e, 8-DD through reparameterization of the notion of Renyi DP, a relaxed notion for DP proposed in (Mironov, 2017). Nonetheless, when the DP requirement is not needed, one may set oßp = 0 for a clipped algorithm with reduced bias.
G2 (108(118)) (T
E 00 - Opsll =
(16)
m²63
which is achieved by setting the clipping threshold as
2Gm2
d dloo(11/)) + 2m
Importantly, the error feedback mechanism is effective in removing the asymptotic bias. To see that this insight can be extended to the performative prediction setting, observe that any fixed point (e, 0) of Algorithm I satisfies
We observe that the asymptotic deviation from 0p is in the order of (dd (d)/(p?=)) which contains the combined effects from the sensitivity of distribution shift and DP requirement.
- -cipp (e) = Ex [clipc, (V((;; v f( 0) clipc, (ë) E E2 E2 (V(())))) (17)
4. Reducing Clipping Bias in Clipped SGD
The previous section illustrates that PCSGD suffers from a bias amplification phenomenon in the setting of perfor- mative prediction, Although the issue can be remedied by
Under the condition C2 2 C1, a feasible fixed point (e, 0) shall satisfy ()(00)) = and ē =
6

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
-B2-D(o) (clipc, ())] since
Non-convex Loss Our last endeavor is show that for the non-convex loss setting. DiceSGD also reduces the bias due to clipping in performative prediction settings, We observe the convergence result:
||]|| s (oz--po]lllciipc (Ve(6; S C1,
(18)
where the first inequality is due to Jensen's 's inequality. The condition (S(0; 0) =0 implies 0- = Ops under strongly- convex {(-).
Theorem 8. Under A2, 4, 6, 7, 8. If set y = 1/VT, then for sufficiently large T, it holds
1 min E [ 0.)1 (1)) [/++ (21)
We conclude by presenting the convergence for the DiceSGD algorithm in the performative prediction setting.
We first observe the assumption:
where b = (fmaxx ((C) - C2) vdd
A8. There exists a constant M such that for any t 2 1, E|||e,|]] M².
The detailed theorem and proof can be found in $G. Our analysis involved a few modifications over (Zhang et al., 2024, Theorem 3.6) for the Deccision-depeneen distribution.
A8 is verified empirically in our experiments for the case of C2 2 C1; see $H. Similar to PCSGD, the DiceSGD algorithm is also a non-gradient algorithm with non-smooth drifts. The following analysis is achieved by designing suitable Lyapunov function for each type of E(-).
Unlike the convergence Theorems 1 & 5 for the PCSGD algorithm, the analysis of DiceSGD relaxes the uniformly bounded gradient assumption (A3) to the variance- based assumption (A4). This relaxation is enabled by the feedback mechanism embedded in the DiceSGD algorithm.
Strongly Convex Loss exists G. B 2 0 with
Notice that A4 implies that there
Importantly, from (21), we observe that when 0, there is no asymptotic bias for DiceSGD. However, we also note that unlike PCSGD, the multiplicative factor b depends on opp Ci, C2 which indicates that the bias due to distribution shift may become more sensitive when using DiceSGD.
Ez~D(O) |I| Ve(0; 2)1() SC + B Opsll? (19)
for any 0 E Rdd Denote j := P LB and 0, == O.
7t6 - Ops, we have
Remark 2. The DP guarantees of DiceSGD with distri- bution shift can be studied by extending (Zhang et al., 2024, Theorem 3.7 & Appendix A.2). Particularly, we can model the distribution shift through a random map- ping f (Z + Do) - Do, similar to the one introduced in Appendix E. Applying the data processing inequality shows that comparable bound for the DP guarantees of the DiceSGD algorithm under distribution shift to (Zhang et al., 2024, Theorem 3.7) can be established.
Theorem 7. Under AI, 2, 4, 5, 8 and (19) holds. Suppose that 3 < 4. there exists ag. 01, b, 2 such that the step ca/(a1 + t), do 2 1/b, ii) Tt < minnfā/ (16b), 8/ū, p/4B²), }, and iii) vi h222111 S
size of DiceSGD satisfies i) 7t
1 + Int11, Then, for any 2 0.
[+1
@0.1% + 8(G2 + do
0
S
1
7h
7+1
i 24
F=1
16T.2 ( + +3)2
3
112
7--1
5. Numerical Experiments
Mb + 1382 122
11+1
(20)
All experiments are performed with Python on a server using single Intel Xeon 6138 CPU thread. In the interest of space, we only consider the experiments with strongly convex ((.) and focus the setting with DP guarantees to validate our theoretical findings. For the sake of fair comparison between the PCSGD and the DiceSGD algorithms, we choose the set X' to be such that the optimal point of the unconstrained and constrained case of (2) will coincide. To maintain the same DP guarantees. we respectively set the DP noise standard deviation for PCSGD and DiceSGD as Dp and p9 according to Corollary 1 and (Zhang et al., 2024, Theorem 3.7). For the DiceSGD algorithm, we set C₁ = Cz. This decision is motivated by the necessity to maintain a balanced trade-off off in Algorithm 1, where augmenting the values of C1 and C2 would entail an increase in the variance of the Gaussian mechanism in line 3.
We present the detailed proof in SF. Under strong convex losses AI, our analysis shows that DiceSGD converges to unique fixed point (0ps) in the mean square sense. Note that the analysis framework here differs significantly from that for non-convex losses.
We observe from (20) that the dominant term on the right- hand-side is the second term which behaves as ((++1)= (L/t).. Consequently, we have
E|00 0, 0psl 12 < 2E B. 1 2 O11/t)
due to A8. In other words, the DiceSGD algorithm is asymp- totically unbiased.
7

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
Opt, - 0.1
Ops,
Noa Opl
Non Opt c
-Os/
Ops!?
Opt ( = 0.2
0ps!"
10y
Opt, -
10
Noa Opl _8 0.2
Non Opt c 0.01
PCSGD f 0.01
PCSGD 2- 0.05
10
10
10
10-2
DivSSGD
DinSGD /I 0.05
SGD - 0.01
10
10a
10
10
10
10
10
10P
Iterations L
Privacy budget
Distribution sensitivity B
Figure 1. Quadratic Minimization (First) The performative stability gap ||0, - 0ps| 2 (Second) Trade off between privacy budget e and bias. (Third) Bias amplification effect due to 8.
PCSGD 3= 0.01
DieSGD 3- D01
Test Time Nog. Rate
Tes: Tree Pos. (aat
PCSCD 3= 0.1
121
DieSCD 3-D D.1
6ps
PCSCD =-1
PCSDD A 0.001
PCSGD 3= 0.1
DivSGD
100
PCSGD 0.01
DoeSGD
PCSGD 8' 0.1
PCSGD - 0.
17
DieSCD
8.
DioSGD 0.1
Dee8GD A 000
PCSCD -1
61%
ittrations
Iterations
Trerations
Figure 2. Logistic Regression (First) Gap between iterations and performative stable point 100, 0rsl (Second) Test true negative rate with shifted distribution. (Thirdy Test true positive accuracy with shifted distribution.
We remark that additional experiment details and results can be found in Appendix H. including an example for the case with non-convex loss in Appendix H.3.
Our next experiments examine the trade-off between clip- ping bias of PCSGD |0r pssl? and privacy budget E or distribution sensitivity B. We 2.32, T 10a B E {0.1, or f0.01, 0.13, while keeping the other parameters unchanged. Using Corollary 2, we set the optimal step size according to 7 in (15), and the non-optimal step size scenario when the presence of distribution shift is unknown. From Fig. 1 (second & third plots), setting the optimal step size y adapted to distribution shifts achieves a smaller bias in all settings. Meanwhile, as the privacy budget decreases 4 or the sensitivity of distribution shift increases ,3 1 a the bias of PCSGD increases.
=1,b 6, e* s
Quadratic Minimization. The first problem is concerned with the validation of Theorems 3, 4, and 7. Here, we consider a scalar performative risk optimization problem with synthetic data
log(1/A(w)) to simulate the nf
min
+ a2)))/11 OEX
where D(0) is a uniform distribution over the data points m such that Z, Bpp) is Bernoulli and a > (bž,- _50mm
0,b > 0.p < 1/2. We also set X' = (-10, 10) and observe that for 0 < < the performative stable solution is
Logistic Regression. We consider the real dataset CiveMeSomeCredii (Kaggle, 2011) with m = 15776 samples and d = 10 features. We split the training/test sets using the ratio 7 3. The learner aims to find a classifier via minimizing the regularized logistic loss:
m Ops- I-a3 where p Em Z; is the sample mean.
8a
We set p 0.1, 0.1, 1/m, E (0.01, 0.05),
10,6 6 = c C = Cg- = 1. the sample size 10a. The step size is 7/2 100+7 with the initialization 0, = 5. In Fig. 1 (first plot), we compare 10, 0ps| against the iteration number t using plain SGD with DP noise, PCSGD and DiceSGD. As observed, adding the DP noise compro- mises SGD's convergence. PCSGD cannot converge to Pp due to the clipping bias which increases as 3 t. Mean- while, DiceSGD finds a bias-free solution as converges to Ps at rate O(1/t).
10
E(0; 2) = a(() (log(1 +exp(x 00)--xx T 0) + |1012
where 7) = 10 /m m is regularization parameter, = (I,y) E Rd x 10 is the training sample, a(z) = + 1 is a label weight, y = 0 (y = 1) denotes a customer with- out (with) history of defaults. The strategic behavior of the population, i.e., their features æ are adapted to through
8

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
maximizing quadratic utility function.
Advances in Neural Information Processing Systems, 33:
13773-13782, 2020.
We fix the privacy budget at = 8 1/m, clipping thresholds c = C C2 = 1, step size "/, 50/ (0/(5000++)) and sensitivity parameter 3 E {0.001, 0.0.01,.001,0111 0.1}. From Fig. 2 (first plot), we observe the gap 10, Pp of DiceSGD decays at (1/tt) as + sc, PCSGD achieve the steady state due to bias after the transient stage. This coin- cides with Theorems 3 & 7. In Fig. (second & third plots), we compare the test accuracy against the iteration number Here, the trajectory becomes more unstable as 1. An interesting observation is that increasing the sensitivity 3 leads to lower true positive rate.
Drusvyatskiy, and Xiao, Stochastic optimization with decision-dependent distributions. Mathemalics of Opera- tions Research, 48(2):554 998, 2023.
Dwork, and Roth, The algorithmic foundations of dif- ferential privacy. Foundations and Trends in Theoretical Computer Science, 933-4)2211-400 2014.
Gorbunov, E., Danilova, M., and Gasnikov, A. Stochas- tic optimization with heavy-tailed noise via accelerated gradient clipping. Advances in Neural Information Pro- cessing Systems, 33:15042-15053, 2020.
6. Conclusions
This paper initiates the study of clipped SGD algorithms in the performative prediction setting. In both cases with strongly convex and non-convex losses, bias amplification effect with the PCSGD algorithm and proposed several remedies including an extension of the DiceSGD algorithm to performative prediction.
Hardt, M. and Mendler-Dünner, C. Performative prediction: Past and future. arXiv preprint arXiv:2310. 16608, 2023.
discovered
Hardt, M., Megiddo, N., Papadimitriou, C., and Wootters, M. Strategic classification. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pp. 111-222 2016.
Impact Statement
Hazan, E., Levy, K., and Shalev- Shwartz, S. Beyond con- vexity: Stochastic quasi-convex optimization. Advances in neural information processing systems, 28, 2015.
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Izzo, Z., Ying, L., and Zou, J. How to learn when data reacts to your model: performative gradient descent. In International Conference on Machine Learning, pp. 4641- 4650. PMLR, 2021.
Acknowledgments
This work was supported by the Shun Hing Institute of Advanced Engincering, The Chinese University of Hong Kong, under Project #MMT--5--23.
Kaggle. Give me some credit, Improve on the state of the art in credit scoring by predicting the probability that somebody will experience financial distress in the next two years., 2011. URL https://www kaggle. com/ http///veeeeeeeeeeeeeeeeeeeeeeee
References
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-11 018-318,2200 2016.
Khirirat, S., Gorbunov, E., Horváth, S., Islamov, R., Karray, F,, and Richtárik, P. Clip21: Error feedback for gradient 2023.
clipping. arXiv preprint
Koloskova, A., Hendrikx, H., and Stich, S. U. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In International Conference on Machine Learning, pp. 17343-17363. PMLR, 2023.
Brown, G., Hod, S., and Kalemaj. I. Performative prediction in stateful world. In International Conference Artifi- cial Intelligence and Statistics, pp. 6045-6061. PMLR, 2022.
Li, Q. and Wai, H.-T. State dependent performative pre- diction with stochastic approximation. In International Conference on Artificial Intelligence and Statistics, pp. 3164 3186. PMLR, 2022.
Chaudhuri, K., Monteleoni, C., and Sarwate, A. D. Differ- entially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Li, Q. and Wai, H.TT. Stochastic optimization schemes for performative prediction with nonconvex loss. arXiv preprint arXiv:2405. 00.005/79922 77922, 2024.
Chen, X., Wu, S. Z., and Hong, M. Understanding gra- dient clipping in private sgd: geometric perspective.

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
Li, Q., Yau, C.-Y,, and Wai, H.-T. Multi-agent performative prediction with greedy deployment and consensus seek- ing agents. Advances in Neural Information Processing Systems, 11:38449-88460 2022.
Zhang, X., Bu, Z.,, Wu, Z. S., and Hong, M. Differentially private sgd without clipping bias: An error-feedback ap- proach. In ICLR, 2024.
Mai, V. V. and Johansson, M. Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness. In International Conference on Machine Learning, pp. 7325-7335. PMLR, 2021.
Mendler-Dünner, C.,, Perdomo, J., Zrnic, T., and Hardt, M. Stochastic optimization for performative prediction. Advances in Neural Information Processing Systems, 33: 4929-4933 2020.
Mikolov, T. et al. Statistical language models based on neural networks. Presentation at Google, Mountain View, 2nd April, 80(26), 2012.
Miller, P., Perdomo, J. C., and Zrnic, T. Outside the echo chamber: Optimizing the performative risk. International Conference on Machine Learning, pp. 7710- 7720. PMLR, 2021.
Mironov, I. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pp. 263- 275. IEEE, 2017.
Mofakhami, M., Mitliagkas, I., and Gidel, G. Performa- tive prediction with neural networks. In International Conference on Artificial Intelligence and Statistics, pp. 11079-11093, PMLR, 2023.
Narang, A., Faulkner, E.,, Drusvyatskiy, D., Fazel, M., and Ratliff, I.. J. Multiplayer performative prediction: Learn- ing in decision-dependent games. Journal of Machine Learning Research, 24(202):1-56, 2023..
Perdomo, J., Zmic, T., Mendler- Dünner, C., and Hardt, M. Performative prediction. In International Conference Machine Learning, pp. 7599-7609. PMLR, 2020.
Buinonero-Candela, J., Sugiyama, M., Schwaighofer, A., and Lawrence, N. D. Dataset shift in machine learning-
Mit Press, 2022.
Shor, N. Z. Minimization methods for non-differentiable functions, volume 3. Springer Science & Business Media, 2012.
Zhang, J., He. T., Sra, S., and Jadbabaie, A. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2020a.
Zhang, J., Karimireddy, S. P., Veit, A., Kim, S., Reddi, S., Kumar, S., and Sra, S. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33:15383-15599, 2020b.
10

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
A. Useful Facts
In the proof of Theorems 3 & 7, we utilize the following Lemma which is introduced in (Li et al., 2022, Lemma 6). The lemma upper bounds the coefficients of contraction equations in the form of (28) and (45):
Lemma 1. (Ii et al., 2022, Lemma 6) Consider a sequence of non-negative, non-increasing step sizes (11121- Let > 0. p E 2+ and 711 < 2/a. If
S + a P
2 1+1
7++1
for any t 2 1, then
2 -t, 11
(1 va)
(22)
t=j+1
The proof of this lemma presented in (Li et al., 2022, Lemma 6) and is therefore omitted.
Additionally, we rely on the following lemma that provides smoothness guarantees regarding the performative prediction gradients:
Lemma 2. Under A2, 5. For any 0, 0,,0,0 0' E RR. it holds that
IV 0) (((0,, 0 - L|00 - 011l L3 ||0 0'
(23)
The proof of this lemma can be found in (Drusvyatskiy Xiao, 2023, Lemma 2.1).
B. Proof of Theorem 3
We outline the main steps in proving the convergence for PCSGD. In particular, we shall consider the general form of PCSGD in (14) where the DP noise is introduced. To this end, we aim at proving the following bound:
Theorem. Under AI, 2, 3, 5. Suppose that 3 < t. the step sizes (11111 are con-increasing and satisfy i) "h-1 S
1+ - Yt, and ii) 7t S L- Then, for any 2 1. the expected squared distance between 0, and the performative stable solution 0ps satisfies
201
8C1 112
0 < II
M+11 +
2=1
where ej 2(c + G²) + po Ci == (max(G e, 0}) and == = p - LB.
To simplify notations, we define
(g)) == clip, (V((;; Z++1), b, = -
(0, Ops).
(24)
Recall that Ô, 0, Ops, the following lemma characterizes the one-step progress of PCSGD.
Lemma 3. Under A2, 3, 5. For any t 2 0, it holds
Exl1O.+11 < (1- (1-2p744
1110., (0- mninfc?,G91 + - 27 (0.1Ee Er
(25)
The proof is in $. The inner product term above involving E, [b.] captures the clipping bias and the distribution shift, The latter is the difference between the clipped stochastic gradient and the expected gradient induced by D(Ors).
Such term is unlikely to be small except for a large clipping threshold c. For example, (Zhang et al., 2020b, Lemma 9) applied an indicator function trick to bound [E,[b,]] by G/c. We improve their treatment on the bias term via better use of the smoothness property (cf. Lemma 2) to obtain:

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
Lemma 4, Under A2, 5, the following upper bound holds:
-24+1 (0:- 0ps (bbb)) - 22L37+11 110, Opsll + j0n+1 10, - 0pssl? + 47++1 Ct,
(26)
1
with the constants Ci == (max - c, 03) : : - LB.
See $B.2 for the detailed proof. The first two terms on the right hand side of Eq. (26) vanishes as 10, Opsll + 0. Meanwhile, the term # has led an inevitable clipping bias. Notice that this term vanishes only in the trivial case of 2 G, i..,, the clipping threshold is larger than any stochastic gradient. Otherwise, this bias will propagate through the algorithm and lead to an asymptotic bias.
Proof of Theorem 3. Combining Lemmas 3, 4 leads to the following recursion:
4C,
E 1 s (1 - 1m++)) +
7c+1 + rh2t1 (2c² + 2G +dodp)
(27)
Recall that 01 (2c² + 20 + )p). Taking full expectation both sides of (27) leads to:
0
0++1 2 S
I+1
II
(1
(m))))
06||
+
C1
++1
[-1
(1
Mng +
4C1
H+1
[+1
(1
(7()))
i=1
i=1
j=++1
i=1
f=++1
++1
|6=1²
8C1
201
(1 (m))
+
7
(28)
j
where we used Lemma 1 in the last inequality for step size satisfying sup121 7/ S 7.
B.1. Proof of Lemma 3
Proof. Recall the notation Vg( (V((O;; Z.+1)) which we introduce in (24). Then, we deduce the following chain
10 Opsl 11 (a)
Px (0: - 7+11 [[((.)) + +G+11 Px (Ops + 7+t (f(OPs:
(b)
0 - M+1 (g.(.)) + S+t1] - 0rs + 7+1 (/ 0rs)
10. - pps 1|2 2 [g. + +G+1 V rs; 0rs)
2 (0, ps Vg(0.) + +G+1 (0pps PS))
where in equality (a), we applied the definition of 0ps in (2). Inequality (b) is due to the non-expansive property of the projection operator. Introducing notation b. (g( (f(0; which define in (24) into the above inequality gives us
00++1 - -pssl < 10, - Opsl + + ()(0,) + G+1 - Oppps
2n (0: - 0Ps b + 51+1 + (f(; - (f(Ops: 0ps))
(a) $ (1 1p) 11, 0ps 1| + 1t4 (g(0.) + 6++ - V/(p:
2n (0. 0ps b. + ((+1).
where inequality (a) is due to strong convexity of ((-;)),, i..., (02 Ops V/(0,; 0ps) - VS(Ops: Ops)) 2 0 0psll
Taking conditional expectation with regards to 0, on both sides gives us
E, |1 - 0pssl s (1 2p l1 0psll 2n+1 (0, Ops E,(b,))
(29)
+ 2 E, ()) + G+1 (s(Pss:ppp 0ps)
12

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
For the last term of right-hand-side of the above inequality, we have
t (g(0,) + - (.
- E. - ( +
Vg 3 + I|s++1ll
@ E,ll - [
do
+ do
(b)
S 2E,, [|clip. (V:(O, -x +2 PPS) )|2 + do S 2( G²) doop.
where (a) is obtained since the additive perturbing noise is zero mean and statistically independent of the stochastic gradient, (b) is due to A and definition of clipping operator.
Substituting above upper bound (29) leads to
E, 01+1
0psll
I (1 2p7(+1) 00 0psll - (0, Pps E, (y]))
+ 22t1 (2e² + 2G + doBp).
which finishes the proof Lemma
B.2. Proof of Lemma
Proof. Applying the Cauchy-Schwarz inequality on the inner product (0ps 0, [,[[6]] yields the following upper bound:
-2 (0: 0rs [b.)) s 2 |00 0rsll [E,[b]]]--
We now proceed to upper bounding
[, [b,]1|:
[[,]b,]]| = E2 ((())) - Vf(0;;
Vg(0;; v.(0;:
< [g(0,; 0.) - v[(0;00)]++1](00003 - Vs(0,;0ss)
< (Zz-D(..) (clip, (VE(((;))) - VE(O,; + LB |00 -Psll
where the last inequality is due to Assumption and Lemma D.4 of (Perdomo et al., 2020). Moreover,
E B2,)(0,)
min L, |V((0
ve(0(:2)
1--min min (1, |V((0,
(30)
< E.
||VE(0 2)1l
E [max (0, (VV[(0 =)]l - c)] S max(G c; 0,
where we have used Assumption 3 in the last inequality. Finally, we obtain
-2 (0,
0ps [E,bb,]> s 21+1 |00 0psl (max(G - c, c, + LB 0 0psll)
= 2L ||0: 0rs| + 27. 0. Orsll max - 0.
< 2L |10, 0psll 2 + f 0| - 0psll 4
(max(G c, 0,)
where in the last inequality, used the Hölder's inequality zy S ax + x² and set 2i/2
C. Proof of Theorem 4
Proof. Let a, b, B and denote by B(p) the Bernoulli distribution with mean 0 < 1. We consider the following quadratic loss function:
mingex E (()))))((0
13

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
where f(0;z) = =0 az)² and Z D(0) - b2 30, Z B(p).
(31)
We require that ab 2 2c. When Z D(0), we note that the stochastic gradient is in the form:
vi(0: 2) = 0 alb2 - 30) = (1 111--:8 aB)0 0 + abZ.
Problem (31) satisfies A2 with μ - 1, L = a and A5 with the parameter 33.
Consider the following point:
pc
0x
(1 (1- p1 aB)
We claim that 20 is fixed point of the clipped SGD algorithm. Note that the stochastic gradient Ox with Z ~ 2() when - = 0 is not clipped, since
[11 a,30 + ab 0l = (1 (1-a x (-(1 p)(1 aB)
pc
C,
where the last inequality is due to the assumption
1. Meanwhile, when = 1, the stochastic gradient is:
(1 - a3 + ab = pc
1-p + ab 2 - + 2c =
where the last inequality uses the condition ab 2 2c. In particular, we have that:
E Ex-pro)(cip,,(V((( 2)) = (1 - p) [[1 aB) + pc
The above shows that 2: is a fixed point of the Clipped SGD algorithm.
On the other hand, the performative stable solution, Pss. of problem (31) solves the following equation,
Eg-D(Ops) (V((0ps))) = Ez (rs + aZ) = Ps + a(p ps) = 0.
we get that
pa
Prs 1 a3
Finally, we can lower bound the asymptotic bias of clipped SGD
00 - 0rssl =
(1- p) -ll-a---
pc
pa
p2
C = ( (1
aB) + 1 - aB
= (1 ag)²
a
1 -
Finally, we aim prove that 0x unique. We remark that the limiting points of clipping SGD satisfies
El.p = O,
which is equivalent to
clip. a0)0 + ab) + (1-p) p) clip.l(1 - a3)0 = 0.
(32)
Case 1: (1 0 + ab > cnd (1 a.3)0 < c, then, we will get 0...
Case 2: (1 0 0+ + ab > e and (1 a > c, then
xc=
Case 3: (1-a3)0- + ab cand (1 a < c, i.e, it requires that 0 <
ah T-a3 then from (32), we obtain that
p [1 a3)0 + ab| + (1- p) x [1 a3)0 = 0.
Solve it, we get
pob 1-a3-
a3 Note that
0 pab
- ab
1 a3
1 1- a33
which is impossible, since ab 2 2c and p, > 0. In conclusion, there is only one solution of (32). This concludes the
proof.
14

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
D. Proof of Theorem 5
In this section, we consider a special case of (I) where X' PCSGD with DP noise (14).
Rd Similar to $B, we also consider the general setting of
Theorem. Under A2, 3, 4, 6, Lel the step sizes satisfy supp21 7t 2(1+o7)
Then, for any T 2 the iterates {0))220
generates by (4) satisfy:
T-1
T-1
M+11 E
S + 4L + o [V
Σ t=0
+ (b(3
2 1141
N+1
where Dg == (fu; 0o) (*) is an upper bound to the initial optimality gap for performative risk, and
b(3,c) c) = L3 (Vo8 - o + +(1 + 07) + max - ( c,
where L = Lmax-
Proof of Theorem with general op- For fixed E Z, applying A2 leads to
I 110+1 -b112
((0(1:2)) ((0 + (V((0:22 0.+1 - 0.)
2
L7 (V + Setal 1|
= =[(0(; 2) M 7+1 ( clip. (VE((112241)) + Se+1) +
2
L1241 (g(()) + G++1 ||
= =((0,;) 7 (Vi(0,;)) V.(O.) + (++1) +
2
The second line is due to the update rule of (4). In the last line, we recall the notation ())))) == clip. #++1)) Taking integration on fixed z with weights given by the p.d.f. of D(O.). i.e,, s(()po, (2)dz on both sides above inequality yield
f(0++1:0, & f(0;; 0,) 7+1 (V (g(O.) + (4+1) + L 2
(5(0,) + Setall"
Taking conditional expectation E,|-] on the clipping stochastic gradients leads to
f(0++1:0,) - f(0,; 0,) 7 (V.( E. ( + I 2
F + G
E,
(33)
where we use the property that S++1 _00 T). J). For the last term in above, we observe the following chain,
(a) Vg(O.) + G++1 ||] E, (g((o)) || ofp s E. [[ + +OP
[E((0(0) - (S,0, 0,) [+) +Op of + ob + of) [V)
where (a) used the definition of clipping operator (6) and (b) used A4. Substituting above results (33) gives
Lrdz (o) o +1 (1+0)) (34)
f 00)++1:0)) < ((....)) 7+41 (v)(0.)))) E. (8(()))
2
The inner product term can be lower bounded by
- (0 0,) E. (o(0.)) = || - -
z - (Vv VS(0,))))
15

---

(n) Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
Vf(00 maxfG - c, [V 0.)] 2 max - -,, 0)²,
where (a) is due to (30) in Lemma and the last inequality due the fact that zy I ax² + x2 for any a 0. Substituting
back (34) gives
f(0(+1:0:) S f(0; (f((0;001l" + maxff c2 + L7-1 (o) + oP + [1+
Rearranging terms,
L(1 + + [V)();))) & (()); - -(0++1;0.) + - cc,00= L(og
o
2 2
2
1 1-
The step size condition suP/21 7t S 2((+o;) implies that 1(1+0p)e44
());;)))11 < (.) f(0++1;0.) + ma 0)2 L(ag + o
(35)
2 M+1
Next, taking full expectation on both sides and decomposing the term f(0,; 0,) f(0.+1: 0.) as:
(0,; 0.) ((0+1 0.)] ([S 0.)
0 + 1[ - ((0+1 0.)]
1 R[ 0.) f(0 0.+1)) T,3 00+1 0.l
(0)
1 B[f(0,;) 0:) (0.41: 11
Vg(O.) + Ce+1
(2)
E. Vo(O.) + Ge+ 1|"
x [[ 0.) - ((0 0.+1) 7.
(36)
(4)
$ E[f(0, 0.) f(0 0(+1)l LL
Vo88 + ob + 1V
S [E[ f(0+1 0+41)
LB
( oi + of + +1+
8L3
[V;(00;))11)
8Lg
Inequality (a) is due to (Li & Wai, 2024, Lemma 3), (b) is due to the update rule (4) and (c) is implied by [EX]² s B[X²). In (d), we apply A4. Back to (35), we have
Y++ E (V, 0.) S E[ 0.) - ((0++1;0(+1) L'o obp)
2 7ot1 + b(3,c) 7++1,
where b(3,c) c) is constant depending on distribution shifting strength and clipping threshold, which defined as
b(3,c) : L. (V0g 08 + oh + 8(1 8(1+0))ī 2 max - c, 032.
(37)
Taking summation from f. = 0,,,,.... T gives us
L(o + -bp)
T-1 b(8,c)
7e+ E ( $
s Ao
Σ
2
Σ
2411
2
Set 7/ 1/VT and divide ET-1 7 on both sides yields the theorem.
16

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
E. Proof of Corollary 1
Proof. Let o and aur denote an outcome and an auxiliary input, respectively. We wish to prove
Pr(M(aur, Z) = o) f e² Pr(M(auz, Z') = o) + 6,
where and Z' are two adjacent datasets, i.e., they are only different by one sample. Let us define the privacy loss of an outcome o on two datasets Z and Z' as
Pr(M(aux, Z) = 0)
c(o; Mo;Ma,uu aux, Z, Z') = log Pr(M (aux, Z') o)
and its log moment generating function as
a (>; ouz, Z, Z') := log M,,,aa,,,,,, coo aux, Z, Z,)),,,
where M is the mechanism we focus on, À > 0 is the variable of log moment generating function. Taking maximum over conditions, the unconditioned log moment generating function is
(M; auu Z, Z')
max 2,2'
The overall log moment generating function can be bounded following according to composability in (Abadi et al., 2016, Theorem 2)
(M
M (A)-
t=1
Let 1. denotes the probability each data sample is drawn uniformly from the dataset Dg. Recall (13), which leads to
E = 7 8, (0) where i is chosen uniformly from [m]] and (0) is generated according to the random mapping S X - Z. We can define this relationship by the random mapping f (Z Do) + Do. where for X C g and Y C 12 we let X + denote the set with all the variables {a: + y x E X, y E Y] and the randomness follows from the uniform distribution o E [m] and the random mapping S, : X' - Z. By (Dwork Roth, 2014, Proposition 2.1) using the post processing function f. after the privacy mechanism M,, ic. f M, does not compromise differential privacy.
Observe that the distribution shift due S,( in (13) cannot compromise differential privacy (Dwork & Roth, 2014, Th and A < ²²
Proposition 2. Let 160
log we apply (Abadi et al., 2016, Lemma 3) to bound the unconditioned
grar"
log moment generating function as
a-M (A)
X2 2)e²
+0
)
=0
(P22222
(1 - d)OO
o
op
Finally, we only need to verify that there exists some that satisfies the following inequalities
qcp
A
T
exp(->e/2) <
A
log
DP
2
c²
qo
< log(1/5)
We can verify that when cT 1/m and op explicit constant c1. This finishes the proof.
all above conditions can be satisfied for some
F. Proof of Theorem 7
For the convenience of derivations, we introduce the following notations: 0, 02 - -ee Its update rule is
0zt1 = 0,11 70+16++1
0. - 7 + Gi) 7: (e: + V((0, 2)) - v141)
(38)
O. 7441 - 7411 (et Vi(0,; #41))
17

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
0, (71 7141) - 7441 (G++1 V((00)=(1))
We remark that if we choose a constant step size, i.c, "/ = 7, then 0.+1 = 0, - 76+1 + VE(0;; which degenerates to the case in the proof of (Zhang et al., 2024).
Meanwhile, we can obtain the feedback error et's update rule:
et+1 = e + Ve(0, - clipcs (et) cipc, (V((0,;2++)
(39)
where we define a a² following:
1,
Ci |eel f a' min
C2 Ve(0 241)
a min
(40)
We aim to analyze the squared distance between 0.41 and pps.
0 0ps 2 = 0, + (n - 1411e - 7+11 (VE(0 + (e+1) 0ps 2
12
0. - Ops
+ l1( - -+1eem 7 [V((( (++1 + S1+1l11
+ 2 0, Pps (r6 - - - -V+1 + +
Tacking conditional expectation E/|-] on both sides leads to
|| 2 11 1111)=11
E, 0.+1 Pps
s 0. 0ps
(41)
2 F. [[V[ ze+ 1]1 + do
+ 202(0 - Ors (7: - 1)-1)
2 (0. - 0ps V f(,;; 0.) (s(Ops, 0ps))
where we use inequality (a + b)2 < 2a + 262, S4+1 ~ (0, I) and the fact that V ff(pps, = 0.
Applying (19) leads to following upper bound:
E, 0: -Pss| 2 < (1 20,_
0, 0ps
+ +(2 -+1)² ||eel?
(42)
22 [G + doop] +2 0, 0rs (7t - 7
1)11) (
:
27+1 (Ø, Ors Vf 0,) (Ors, 0rs)
B=
Now, let's consider the term B, first. Using Holder's inequality, have
Bi 4(7 7++1) ||0. 0rs
2 + ||ea11?
For the term Bz, we observe the following chain,
B2
0,
Ops
f(0;; 02) V.(0,, 0p)) +
+ Vf f(Opps:pss)
(0)
/1 0. 0ps
0. 0rs V. 0.) V 0rs))
Ors 0. (S 0.) (((): (Ors - -00s--,1 - vr(0:;)s))
0,
0ps
18

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
0 ps
0, PP
L + 3)
0 -
LB 0. 0ps
(c)
P 0, PPs
L(1 + 8)
00. 0ps |hselll
21(1 + (3) 2 +
2 0: 0ps
L(1 + 8)
0 0ps
ve |leell?
21 + 3)
2L (1 8)2 2 |e 1
0 OPS
N 71
2
where in inequality (a), we have used A2, in inequality (b), we have used A5 and Lemma D.4 of (Perdomo et al., 2020), and
in equality (c). use the definition of 0, 0, 7/Ee.
Substituting above upper bound for B1 and B2 to (41) gives us
E 0 Ops] ||
S (1 - + 242 + 4(7 - - 00, Ops
+ +2 + ddop))
(43)
+ 66m 1178-10m 1 4L3 + B)2
Ve Y++1 ||ee|1?
Setting 7o-11 S (A(22 ensures that
Ops| || < (1-10//2) ((x12))) + +((7 (0-1-7++))
Ex
12+1
0, - Ops]
-2 + dopp)
(44)
41,2 3)3 6(T - 2+1)² ((tx)~+1)2
7 787+11 |lee|1
n is constant step size, then 7 -h+1 = 0. For diminishing step size case " prove that 7/- -t- 1 S br Therefore, (44) becomes
if a0 2 1, 0, we can
E, 12.1011005p -0rs s 511 (1- (ū/2) + 467
00.-0rs
+ +2( dobp)ri+1
4L 332 + 662 1
mirct) |le.
If sup it S
then we have 1 (m/2) 4672+1 < (4144)441- Thus.
165
Eg 0 Ops |
s (1 - (m/4))++1) 0 - 0ps || + 2(G + dobp)rin
+ 66 x + 412 + 9)2
7 n ||eel1.
Taking full expectation on both sides and applying A8 leads to
E 0 Ops S (1 (ū/44)x+1) 00 Ops
Ops
+ 2(2 + dopp)) 6bb 22701
4L 2I + 3)²
Ā 782+1.
Suppose that sup121 72/1241 5 + by then we have
$ (1- 11--(p) (7/ (1/4))041) 0, 0ps 2 + +2 + dobp
4L. 2 + :3)2
0 - 0ps
76
41.2 4T.21/22(11 8)2
+ 662 22 +
1+11
19

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
Solving the above recursion leads to
0++1 - 0ps S (1-
++1
0
0ps
2
+ 2(2
do
++1
71
(1
4 7t)
j=i+1
4L2 + 333
1+1
11) + 2
(1
1
j=++1
4L 2 + B)²
t-1
5
1+1
(1
P
n1)
11
4
==1
j=++1
1+1
II
(a/
| - 0ps 0pps
2 8(G + do
16L2M² + B)2
m+1
72+1
240 M
16L M² + 3)²
(45)
n
1t+1
where the last inequality follows from Lemma 1. Thus, we can now conclude the proof.
G. Proof of Theorem
Theorem (formal). Under A2, 4, 6, 7, 8. Let y denotes the constant step size. If it holds that y 1/((2L(1 + of)), then the iterates generated by DiceSGD admits the following bound for any 2 1,
40o + b3 2Ly [o + oØ] +2L2M222 T*
min
E (1; S
(46)
where Do [0 rep; 0o) - e*] an upper bound for the initial error and the constant b is defined as
b maxx (Ci +G++02 + vdopp).
In particular, for sufficiently large T, setting 7 1/VTT yields the bound in (21) of the main paper.
Proof. *Consider the DiceSGD algorithm with constant step size 7/41 = 7. Similar to $F, we define 0. 0z yer and
notice the following recursion:
0 7 (S++1 Ve(O,; Ze+1))
To facilitate the derivations, define the shorthand notation: V ft == ((,;; 0.). For any fixed sample Z, applying A2 leads to the following upper bound:
((141.2)) S ((0,))) (V((0,,)) 0..1 - - + 2 0 0.
Taking integration the fixed with weights given by the p.d.f. of D(0;) the both sides of above inequality yields
f(0 0.) < f(0,, 0.) + (VS(0., 0.+1 - θ.) + L
0.+1 0.
LT²
-[ 0.) (V, 0.) v((0;; Z+11) + |15+t1 + Vi(O.; 1)12
Taking the conditional expectation E,[-] yields
L22 1AL E, [IGG+1 + Ve(O;; 1)1 2
(, < -v)
+
(47)
We notice that our proof differs from that (Zhang et al., 2024, Theorem 3.6) is simpler than the latter due to the addition
20

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
Notice that
B2 V((;; - op og (1 (1+03)VV/(00000)
and under A8, it holds that
((VI((,, (f(0;;))) = f + - Vf((0;;))
E + ElV 0,) 0,)
(9)
I
f +
- 0:11 -
2
2
L
122
f
E re.l - V.
2
2
where (a) is due to Lemma 2. Substituting back into (47) and taking full expectation lead to
L
22
B[J(O++1, 0.)] s B[J(O,, 0.) Ly(1 + of) V +
1
+ ag + 2
2
Of 0,)l 2 f
Ly²
1o + og +
22
2
2
where the last inequality is due to 7 S 1/(2 + -f)). Recall that we have bounded a similar term in (36):
E [(00.+10)))) f(0-1;00000::)) S Lmax3 110, Oc+1ll m (IC) + C2) + vdooe).
under A6 & 7. This yields
L
L22
- E [ E[f(0,, - f(00+1, 0c+1)l + max (cr + C2 + vdo
+ 2
Popp + to + 2
Summing up the inequality from /. = 00 and dividing by Ty/4 yields
T
E[VAI t=
Ty [ 0o) 5r] 4l
+ vdo + 217 sopp + +ogl + 22??
For sufficiently large T, setting 7 1/VT yields the bound in the desired theorem.
H. Details of Numerical Experiments
This section provides additional details for the numerical experiments in $5.
H.1. Validating A8 Empirically
Fig. plots the average of ||e, for DiceSGD as a function of L. Observe that [|e/]] is always bounded for both of our numerical examples, thus validating our A8 empirically.
H.2. Addtionna Details of Numerical Experiments
We provide additional details for the numerical experiments on the logistics regression problem.
Detailed Setup. We develop strategic classification example adapted from (Perdomo et al., 2020, Sec. 5). Consider the learner bank operator who aims to minimize the logistic loss given by
{(;; z) a(=) (log(1 + exp( (Ir ())) (z 0)) 7/2 2
(48)
where 17 > 0 is a regularizztion parameter, = (x,y) Rd x {0, 1} is the training sample, a(z) = y + is a label weight, y (y= = 1) denotes a eustomer without (with) history of defaults.
21

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
3000
DieSCD 2- 0.06
DieeSGD $ 0.01
DiesSGD 0.001
033
DieeSGD = 0.01
2000
DieeSGDD / = 0.1
0.5
1000
01
10'
10
10a
000
Iterations
iteratons
Figure 3. Behavior of et with DiceSGD for quadratic minimization (left) and logistic regression (right).
Training samples are contributed by m users (e.g., customers served by the bank) that form a base distribution Do- Unif(1 De )m)) Upon knowing about the classifier model 0, the customer queried by the bank/leamnrr may shift his/her profile strategically. A possible model is:
Z D(0) Z (x), with i Unif((m]), V4 Dss 3q. arg max, Ux; Ty, 0):
(49)
For example, (x;; F 0) 1 x)) who are trying to evade detection.
|| F.1l with cu. B > models strategical users with history of defaults max
Additional Experiments. Fig. 4 (Left) plots the performative risk EE- [[(0 as a function of the number of iterations t. We observe that DiceSGD can achieve lower performative risk at faster rate compared to PCSGD. Furthermore, increasing sensitivity t leads to lower train true positive rate, which is compatible with our Theorems 3 and
In the training set, records with positive labels (y 1) account for 6.624%. while negative samples (y 0) comprise 93.37%. To evaluate model performance, we have presented the test true negative/positive rate in Fig. 2 (second & third). The training true negative/positive rate is shown in Fig. 4 (Middle& Right). For self-completeness, we recall the definition positive (negative) label accuracy as follows:
TP posineg
True Positive (Negative) rate
TP pos/neg + FN pos/ngg
where TP posheg denotes the number of samples with positive (negative) labels correctly classified as positive (negative), whereas Foppo/egg represents the number of samples with positive (negative) labels incorrectly classified as negative (positive).
c-1
c-1
PCSGD 0.001
DieBCDD : 0.001
PCSGD
performative risk
PUSGD = 0.01
Toin True Nog. Rate
DieSGD / 0.01
PCSGD 8 0.1
20-
PCSGD
DieeSDD 0.1
Train Thoe Pret
0.-
PCSGD 3
DisSGD (
POSGD 5 0.01
DisSGD
DioSUD --
0.5
PCSGD A 0.1
Dixd8DD J) - 0.1
69
DieeGD 3 =
10
10
iterations
Iterations
Iterations
Figure Logistic Regression (Left): Performative Risk V(0). (Middle) (Right): Train true neg./pos. rate.
H.3. Additional Numerical Experiments on Non-convex Loss
In this subsection, we present additional simulations on non-convex loss based on synthetic data to support Theorems 5 8.
22

---

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
Synthetic Data with Linear Model. We consider the following binary classification problem using a linear model. We adopt the following sigmoid loss function:
2(0:z) := (1 + exp(c yx'oon TO))
2 1101
(50)
which is smooth but non-convex for small regularization parameter 77 0. The data distribution D = { ys ) is generated by Unif[-1,1]] 1), with m 10 and the label Di sgn( (z; (0)) E {+1). The shift dynamics are given by {(x, 30; / i=1- We randomly flip 10% of the labels to obtain the final labels yr. In detail, we set = 10, c = 0.1, and 3 E 0.5.. The batch size is b = 1, and the stepsize is constant, - 1/vT, with T = 10
We implement the PCSGD, DiceSGD, and Clip21 algorithms (in the n case) (Khirirat et al., 2023). From Fig. (5), we observe that the SPS-stationarig measures in 2 for the algorithms initially decrease and eventually saturate a certain level, which is consistent with the predictions of Theorems 5 & 8.
10
10"
10-1
(8) 0,31
10-4
7 0g)
10-4
PCSGD 0 0.1
PCSGD 8 0.5
10"
DiceSGD
DiceSGD ==
Clip215GD f= 0.1
Clip215GD /= 0.5
10-
Iterations
Iterations
Figure 5. Synthetic Data with Sigmoid Loss. SPS measure J[:;; 0.)11 of PCSGD, DiceSGD, and Clip21 algorithm with greedy deployment schemes versus itcration number t.
We set the parameters as following: injected noise variance a 1, two clipping thresholds 1, and T
23


Reviews:
[{"review_id": "a8xzQ8veJL", "reviewer": "Reviewer_svSm", "summary": "In this work the authors study the convergence of clipped stochastic gradient descent (SGD) algorithms with decision-dependent data distribution. They explain the performative prediction problem, which is a more general and challenging problem than standard optimization, and they define the performative stable (PS) and stationary PS (SPS) solutions of this. In order find a PS solution they introduce the Projected Clipped SGD (PCSGD) and provide convergence guarantees of this algorithm for stongly convex and general non convex objectives. They also extend their analysis in the Differential Privacy (DP) setting. Additionally, they adapt the previously introduced DiceSGD algorithm for the performative prediction problem and they also offer convergence guarantees of this algorithm for stongly convex and general non convex objectives. Finally, the authors provide numerical experiments applying their algorithms PCSGD and DiceSGD in quadratic minimization and logistic regression problems.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your comments and careful review. Our point-by-point replies are listed below.\n\n> The definition of $\\sigma_{DP}^2$ in Theorem 3?\n\nWe apologize for the careless typo. Indeed, Theorem 3 should be presented without $\\sigma_{DP}^2$. This term is actually introduced later in (14) and is included in the analysis of L579-597 that generalizes Theorem 3. \n\n> Additional bounded gradient assumption vs [Perdomo et al., 2020].\n\nWe made sure that the assumptions needed are justified for common performative prediction problem setups. For the bounded gradient assumption (A3), we have only required $\\nabla \\ell$ to be bounded over $\\theta \\in {\\cal X}$. \n\n- For strongly-convex $\\ell$: as we focus on **projected** clipped SGD, if ${\\cal X}$ is compact, then A3 is naturally implied using the  Lipschitz gradient assumption (A2). As such, we respectfully disagree with \"assuming both smoothness and bounded gradient is too strong\" since the first implies the latter in compact sets. Note that this projection-based algo, however, prompted us to develop a more general analysis than [Perdomo et al., 2020] & [Mendler-Dunner et al., 2021].\n- For non-convex $\\ell$, loss functions such as sigmoid loss satisfy A3, and such condition is needed also in SOTA results such as [Li and Wai, 2024].\n\n> Additional Assumptions on bounded gradients (A3) and boundedness of $\\ell$ (A7) used compared with [Koloskova et al., 2023, Theorem 3.3].\n\nWe emphasize that the inclusion of distribution shift $\\beta>0$ has led to significant challenge in our proof for the non-convex $\\ell$ case. It is unfair to directly compare our result with that in [Koloskova et al., 2023] which assumes $\\beta=0$. \n\nTo see the challenge, consider a special case with $c \\gg 1$ where there is no clipping. The PCSGD with ${\\cal X} = \\mathbb{R}^d$ is then reduced to SGD-GD in [Mendler-Dunner et al., 2021]. As discussed in [Li and Wai, 2024] and references therein, analyzing SGD-GD **without strongly convex $\\ell$** has not been successfully done without extra assumptions such as assuming nonlinear least square loss, or bounded $\\ell$ as in [Li and Wai, 2024]. In this regard, we only use a similar set of assumptions as [Li and Wai, 2024]. We also remark that bounded gradient assumption is also used in [Zhang et al., 2020b] for clipped SGD analysis. \n\nLastly, as explained above, the set of assumptions for the non-convex case are justified too, e.g., with sigmoid loss as $\\ell$.\n\n\n\n> Experiment: Compare PCSGD and DiceSGD with more algorithms? Conduct more real-world experiments where training data involve human input that responds strategically to the model.\n\nWe conducted an additional experiment comparing PCSGD, DiceSGD with DP-Clip21-GD algorithm proposed in [Khirirat et al., 2023], see [https://ibb.co/DD9FxR71  ] -- we adopted $n=1$ & set the other param.s according to (65) in [Khirirat et al., 2023]. Observe that DiceSGD achieves better convergence.\n\nWe fully agree with the necessity to conduct real world experiments. However, as an academic paper focusing on the theoretical understanding of performative behavior, we are unable to provide real world experiments at the moment due to limited resources. We notice that [Perdomo et al., 2020; Hardt & Mendler, 2023] also reuse standard static datasets and design distribution shift dynamics like we do, e.g., in the logistics regression example on the GiveMeSomeCredits dataset. \n\nThere is indeed a challenge in designing real world experiments as such experiments would inevitably involve human subjects, where prior approval for compliances with ethical standards will be needed. Overcoming such challenge is beyond the aim of this research whose goal is to advance theories of performative prediction. Nevertheless, it is a promising research direction for the community.", "claims_and_evidence": "Most of the claims are clear with supporting proofs, however I think the presentation of the theorems needs some improvement. For example, in Theorem 3, what is $\\sigma\\_{DP}^2$? I understand what $\\sigma\\_{DP}^2$ is in the context of Section 3.2, however it has not been introduced earlier.", "methods_and_evaluation_criteria": "The authors propose the PCSGD and DiceSGD to solve the performance prediction problem and they provide guarantees that their algorithms converge in a PS solution up to a neighborhood. My main concern is the number of assumptions they make to guarantee convergence. \n\nFor example, Theorem 3 assumes strong convexity, $\\beta$-sensitivity, smoothness *and* bounded gradients (Lipschitzness). In contrast, [Perdomo et al, 2020, Thm 3.5] assume strong convexity, $\\beta$-sensitivity, and smoothness. Assuming both smoothness and bounded gradients is too strong. \n\nAnother example, Theorem 4 assumes smoothness, some kind of bounded variance, bounded gradients (Lipschitzness) and boundedness of $\\ell$ on top of the standard $\\beta$-sensitivity. Again if we compare with [Koloskova et al, 2023, Thm: 3.3] (essentially $\\beta=0$) they only assume smoothness and bounded variance.", "theoretical_claims": "I have checked all of the proofs in the appendix. There a few points I don't understand. As I said before, I don't understand what $\\sigma\\_{DP}^2$ is in Theorem 3. \nWhen I check the proof I see that it appears in the proof of the intermediate Lemma 3, in line 635. If I understand correctly you have \n$$\\begin{align}\n    \\theta\\_{t+1}\n    &=P\\_X(\\theta\\_t-\\gamma\\_{t+1}clip\\_c(\\nabla\\ell(\\theta\\_t;Z\\_{t+1})))\\text{ by line 129} \\\\\n    &=P\\_X(\\theta\\_t-\\gamma\\_{t+1}\\tilde{\\nabla}g(\\theta\\_t))\\text{ by line 591}\n\\end{align}$$\nSo no need for $\\sigma_{DP}^2$? Do I miss something?", "experimental_designs_or_analyses": "The authors provide numerical experiments applying their algorithms PCSGD and DiceSGD in quadratic minimization and logistic regression problems focusing only on the DP setting. In the logistic regression experiments, they only try PCSGD/DiceSGD with different $\\beta$. I would expect to have comparisons with other algorithms as well. It would also be interesting to see a few more real-world experiments, for example in the intro, you mention \"A common application scenario is that the training data involve human input that responds strategically to the model\"", "relation_to_broader_scientific_literature": "The authors propose two new methods, PCSGD and DiceSGD, for solving the performative prediction problem. This problem was introduced and solved in [Perdomo et al, 2020]. The clipped SGD has been studied extensively in the literature and DiceSGD was introduced in [Zhang et al, 2024]. A recurring issue is that the convergence guarantees that the authors provide, make a lot more assumptions than either of the previous works.", "essential_references_not_discussed": "All essential references are discussed.", "other_strengths_and_weaknesses": "Strengths:\n1. Propose novel methods, PCSGD and DiceSGD, to solve the performance prediction problem. \n2. Provide convergence guarantees for these methods.\n3. Validate their theory via numerical experiments.\n\nWeaknesses:\n1. What is $\\sigma_{DP}^2$ in Theorem 3? (see Claims And Evidence/Theoretical Claims)\n2. The authors make many more assumptions for their convergence results compared to the literature (see Methods And Evaluation Criteria)\n3. There could be a few more experiments (See Experimental Designs Or Analyses)", "other_comments_or_suggestions": "None.", "questions_for_authors": "See weaknesses.", "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": "FJlUwji7kJ", "reviewer": "Reviewer_ETQW", "summary": "This paper examines the convergence behavior of clipped stochastic gradient descent algorithms in the performative prediction setting, where the subsampling distribution depends on the previous iterate. The theoretical analysis addresses both strongly convex and non-convex objective functions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Difference in analysis vs existing works.\n\nIndeed, some of the techniques we applied are standard and grounded in existing works, yet we emphasize that this is the first rigorous study of clipping bias with performative prediction. The lower bounding result in Theorem 4 is new as it emphasizes on the tightness of the upper bounds in Theorem 3. It shows that bias analysis in Theorem 3 is unlikely to be improved with different analysis. We elaborate more on this point in our response to your last comment.\n\n> Interaction between distribution shift and differential privacy beyond worst case \n\nWe agree, especially as the co-evolution of DP clipped SGD algorithm and distribution shift is an exciting venue for future investigation. That said, our results derived from worst case sensitivity offers a faithful approximation of possibly non-linear interaction. Evidences are (i) the form of distribution shift with linear dependence on $\\theta$, which achieves the worst case sensitivity bound, is motivated by a best response dynamics with utility maximization [Perdomo et al., 2020], also see response to rev. KRfQ; (ii) Theorems 3, 4 show that our analysis under the sensitivity assumption is tight.\n\n> Statement about Rényi-DP and $e_t$.\n\nWe apologize for the careless typos. \n\n- The discussion about Renyi-DP in L302 (right col) refers to $(\\epsilon,\\delta)$-DP as in Def. 6. In Appendix A.2 [Zhang et al., 2024], the DiceSGD is first shown to satisfy Renyi-DP, and the standard DP property is established subsequently. \n- The term $e_t$ is in $R^d$. We will revise notations throughout the paper.\n\n> Q: Guarantees for the convex case.\n\nWe refer to the response to Rev. KRfQ. In short, Theorems 5 & 8 can partially cover the non-strongly-convex case, yet the analysis is still an open problem for performative prediction using SGD in general, even without clipping.\n\n> Q: Comparison with existing results involving clipping techniques in DP optimization.\n\nOur work is the first to address the convergence of clipped SGD in performative prediction. Below is a brief comparison to related works:\n\nVs. [Mendler-Dunner et al., 2020] & others on performative prediction -- We conduct analysis for SGD with distribution shifts to clipped SGD which entails a non-continuous mean-field. Such analysis is the first of its kind to our knowledge. \n\nVs. [Koloskova et al., 2023] & others on clipped SGD -- We study the effects of distribution shift on clipped SGD dynamics with a non-gradient mean field prior to clipping. One new finding is that the clipping bias crucially depend on the strength of distribution shift. \n\nSubject to space limitation, we will include a detailed comparison in the revised version.\n\n> Q: Clarify (i) novelty and main message, (ii) distinction between Clipped-SGD-based performative prediction and standard analyses of Clipped-SGD, and elaborate on the effect of performativity.\n\nOur main contribution and novelty lie in conducting the first rigorous study of *clipped SGD algorithms in the presence of distribution shift (i.e., performative prediction)*. We show that there is an inevitable bias that can be excaberated by distribution shifts, and show that DiceSGD can remedy the bias by extending the latter analysis. Besides the above takeaways for practitioners, here are some novel technical challenges overcome by this work:\n\n- For the stochastic processes generated by PCSGD or DiceSGD, the clipping operator turns the dynamics into a non-continuous one, and distribution shift introduces non-gradient mean-field behavior, it is not possible to adopt existing analysis to work out the convergence analysis.\n- For PCSGD, a notable challenge is in Lemma 4 that controls the error of clipped stochastic gradient $b_t = clip_{c}( \\nabla \\ell(\\theta;Z) ) - \\nabla f( \\theta; \\theta ))$. Existing work such as [Zhang et al., 2020b] only took a crude bound insufficient for our analysis. Our final result yields a bias of $(max\\\\{G-c,0\\\\})^2$ that becomes bias-free with large $c$. As comparison, the bias in [Koloskova et al., 2023] is $O( min\\\\{ \\sigma, \\sigma^2/c \\\\})$ which does not vanish even if $c>G$.\n- For DiceSGD, existing result in [Zhang et al., 2024] only works for constant step and non-convex setting without distribution shifts. We made a major revamp including (38) to handle time varying step, (42) to handle non-gradient pre-clipped mean field, etc.\n- We also respectfully disagree with that using A5 & A8 \"simplify the analysis and allow the application of existing techniques\". A5 is general assumption used in almost all papers on performative prediction, it does not directly simplify the analysis as the effects of distribution shift on PCSGD recursion is non-explicit. A8 is used in controlling the error in DiceSGD in (42), again its role is not immediately clear from a direct inspection. The non-convex loss case also require a non-obvious design for Lyapunov function as $f( \\tilde{\\theta}, \\theta )$, see Appendix G.", "claims_and_evidence": "The claim is clearly stated and well-supported by both theoretical proofs and empirical results.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "The experimental design seems reasonable to me.", "relation_to_broader_scientific_literature": "(DP) Optimization", "essential_references_not_discussed": "Please refer to my response to Question 2.", "other_strengths_and_weaknesses": "Strengths:\n* The paper provides a rigorous analysis of clipping bias and convergence in the performative prediction setting, addressing both convex and non-convex objectives.\n\nWeaknesses:\n* The analytical techniques employed in this paper are largely grounded in existing literature. For example, the privacy accounting builds on the moment accountant framework proposed by Abadi et al. (2016), while the convergence analysis draws from methodologies developed by Li et al. (2022), Perdomo et al. (2020), and Zhang et al. (2024).\n\n* The treatment of distribution shift is based on a worst-case bound. It would be valuable to further investigate the interaction between distribution shift and differential privacy, as this could uncover additional insights into the practical implications of the proposed algorithms.", "other_comments_or_suggestions": "* Lines 301–302: The claim that the algorithm achieves $(\\varepsilon, \\delta)$-Rényi Differential Privacy is not standard. Typically, Rényi DP (RDP) is parameterized solely by $(\\alpha, \\varepsilon)$, where $\\alpha > 1$ is the Rényi order. The inclusion of a $\\delta$ parameter suggests a composition or conversion to approximate DP (i.e., $(\\varepsilon, \\delta)$-DP), which should be clarified. Please revise the statement to reflect the standard formulation of RDP or explain the intended interpretation.\n\n\n* Algorithm 1, Line 1: Is $e_t$ a scalar or a vector? The notation is ambiguous and could benefit from clarification. If $e_t$ represents a step size, noise scale, or another parameter, please specify its role and dimensionality explicitly to avoid confusion.", "questions_for_authors": "* The paper considers two cases: strongly convex and non-convex objectives. Would similar theoretical guarantees or insights extend to the convex (but not strongly convex) case? Clarifying whether the techniques or results generalize to this intermediate setting would strengthen the contribution.\n\n* I was unable to locate a dedicated related work section. Are there key prior works the authors could discuss to better contextualize their contributions? A comparison to existing results in differentially private optimization—particularly those involving clipping techniques—would be valuable\n\n* Could the author further clarify the novelty of this work? The contribution remains somewhat unclear, particularly regarding the core message the paper intends to convey. If the primary goal is to analyze clipped (stochastic) gradient descent, then what is the specific technical contribution? It appears that certain assumptions—especially Assumptions A.5 and A.8—simplify the analysis and allow the application of existing techniques for studying clipped gradient descent. \n\n* Continuing from the previous point, it remains unclear whether clipped-SGD-based performative prediction is significantly different from standard analyses of clipped SGD under Assumption A.5. The authors are encouraged to clarify this distinction and elaborate on whether the performative aspect introduces fundamentally new challenges or insights beyond existing clipped SGD frameworks.", "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": "KWjgTUQW26", "reviewer": "Reviewer_5Ee1", "summary": "The paper claims error bounds for the estimate obtained using projected clipped SGD (PCSGD) and DiceSGD algorithm in the problem of performative prediction, where an artificial noise can be added to preserve data privacy. While PCSGD is known for its stability, the output of the algorithm exhibits bias from the performative stable solution in this setting, as its lower and upper bound is proved in the paper. The expected bounds are also proven for DiceSGD, where its result is asymptotically unbiased.\n\n## Update after rebuttal\n\nMy questions about the paper have been clarified, and I intend to maintain my original recommendation score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Experiments: There is no setting where the loss function is nonconvex, so the reported experiments do not validate the claim regarding nonconvex loss (Theorem 5).\n\n\nWe conducted an additional binary classification experiment in **[https://ibb.co/Jjx0XMRg ]**, where we simulated PCSGD, DiceSGD, Clip21 [Khirirat et al., 2024] under different $\\beta$-sensitivity. We adopted the sigmoid loss function:\n\n$$\n\\ell(\\theta; z) = (1 + \\exp(c \\cdot y x^\\top \\theta))^{-1} + \\frac{\\eta}{2} \\|| \\theta \\||^2\n$$\n\nwhich is smooth but **non-convex**. The data distribution ${\\cal D}^o$ is generated by $Unif[-1, 1]$, and the label $y_i \\in \\\\{ \\pm 1 \\\\}$. The shift dynamics are given by $\\\\{(x_i - \\beta \\theta; y_i)\\\\}_{i=1}^{1e3}$. We observed that the SPS stationarity measures in (3) of the algorithms initially decrease and eventually saturate at a certain level, which is consistent with the predictions made by Theorems 5 and 8.\n\n\n\n> In both PCSGD and DiceSGD, the noise $\\zeta \\sim \\mathcal{N}(0, \\sigma^2_{DP}I)$ is employed for DP, but $\\sigma_{DP}^2$ depends on $T$. It may be difficult to choose an appropriate $\\sigma_{DP}$ if the number of required SGD iterations is not known in advance.\n\nThis is a good observation. However, we believe that obtaining a DP bound independent of $T$ would be difficult under the current setting. The reason is that the potential attacker have access to the training history of $T$ iterations. The larger $T$ is, intuitively there will be more privacy leaks. We observe similar conclusions in [Abadi et al., 2016], [Zhang et al., 2024].\n\n> In Figure 1, what randomized mechanism for differential privacy is used? How exactly does the value of the privacy budget affect training?\n\nWe are using the Gaussian mechanism, see (14), for DP. In our numerical exp, the privacy budget affects the DP noise variance as studied in Corollary 1.\n\n> Is there a particular reason why Clipped-SGD is selected for performative prediction? If it is for stability, for example, other methods such as implicit SGD [1] could also be considered.\n\nThe clipped SGD algorithm is selected in our context due to its popularity and wide range of applications, e.g., DP enabled training, robust optimization, etc. This motivated us to analyze its convergence behavior in the context of performative prediction, where the distribution shifts may occur naturally in several key applications of clipped SGD. \n\nSimilar to clipped SGD which introduced non-smooth behavior to the stochastic process, we believe that analyzing algorithms such as Implicit SGD in the performative prediction setting is an interesting direction. Thank you for the suggestion.", "claims_and_evidence": "The expected error bounds of PCSGD and DiceSGD claimed in the proposed theorems are supported with proofs and numerical experiments, along with the effect of differential data privacy.", "methods_and_evaluation_criteria": "The evaluated bias reported in the experiment result goes along with the claims made in the theory section about the estimation bias and differential privacy.", "theoretical_claims": "Theoretical claims seem sound.", "experimental_designs_or_analyses": "The designs for the numerical experiments sound valid. However, it seems there is no setting that the loss function is nonconvex, so the experiments reported does not validate the claim made regarding nonconvex loss (Theorem 5).", "relation_to_broader_scientific_literature": "Data privacy issues are becoming an important issue in the digital age nowadays. For a more performant model, the size of the training data and the model itself are increasing, which also raises the risk of exposing individual information within the training data. It will become increasingly necessary to explore training methods that protect data privacy at a minimal cost to model performance.", "essential_references_not_discussed": "No special reference I would like to discuss.", "other_strengths_and_weaknesses": "In the both PCSGD and DiceSGD, the randonmized Gaussian noise $\\zeta \\sim N(0, \\sigma_{DP}^2I)$ is employed for differential privacy guarantees, but the proposed $\\sigma_{DP}^2$ for guraunteeing $(\\epsilon,\\delta)$-differential privacy also depends on the number of iterations $T$. It may be difficult to choose appropriate magnitude of the noise if the number of appropriate SGD iterations is not available at the first hand.", "other_comments_or_suggestions": "No additional comments.", "questions_for_authors": "1. Regarding to the result of the quadratic minimization (Figure 1), what is the randomized mechanism for differential privacy used in here? How exactly does the value of privacy budget $\\epsilon$ effect the training?\n\n2. Is there a particular reason that the clipped SGD is selected for performative prediction? If for stability, for example, other methods can be considered such as implicit SGD [1].\n\n[1] Lee, Y., Lee, S., & Won, J. H. (2022, June). Statistical inference with implicit sgd: proximal robbins-monro vs. polyak-ruppert. In International Conference on Machine Learning (pp. 12423-12454). PMLR.", "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": "gVjlbvDrc3", "reviewer": "Reviewer_KRfQ", "summary": "The paper studies the problem of Performative Prediction: that is when the data distribution also depends on the model weights. This problem also includes the case of differentially private algorithms. The paper studies clipped SGD for finding a stable solution.  Under various assumptions, the paper provides upper bounds and lower bounds for the distance to the stable solution in the strongly convex case. The algorithm extends to the nonconvex case and differential privacy. The paper further studies the DiceSGD algorithm with two clipping operators. Under the assumption that the error feedback is bounded in expectation, the authors show that the bias from the clipped algorithm goes to 0.\n\n## Update after rebuttal: \nThe authors have addressed my question. I maintain my positive assessment of the paper.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> To demonstrate practical applications of the algorithm, the paper needs to include real datasets with clear justifications/considerations for how the decision-dependent distributions are modeled.\n\nPlease refer to the response to Reviewer svSm. \n\n> The appearance of $\\zeta_{t}$ and $\\sigma_{DP}^2$ in Theorem 3.\n\nThank you very much for the careful review and we apologize for these careless typos. \n\nIndeed, Theorem 3 should be presented without $\\sigma_{DP}^2$, while we remark that the theorem in L579-597 presents a general version of the result. As for the noise $\\zeta_{t+1}$, it should appear in the inner product terms in L647-652. That said, it does not affect the next step in (29) as the noise is zero-mean.\n\n> Validation of Assumption 8: The bound for $|e_{t}|$ is quite large in Figure 3. The concern is how meaningful the bound is if it is so large.\n\nThe bound is meaningful as we observe in Theorem 7 that the relevant term to it is in the order of $O( M^2 \\gamma_t^2 )$ which can be dominated by the $O( \\gamma_t )$ term as $\\gamma_t$ is diminishing such as when $\\gamma_t = O(1/t)$. Particularly, as seen in Fig. 3, the empirical upper bound for $M^2$ is around $10^3$, and its effect on $\\| \\tilde{\\theta}_t \\|^2$ becomes negligible ($\\approx 10^{-6}$) with $\\gamma_t = 50/(5000+t)$, $t \\geq 10^6$.\n\n> Experiments: The reason for the choice of the data distribution is unclear.\n\nThese choices follow from the literature in performative prediction such as [Perdomo et al, 2020]. For both cases in our experiments, the distribution shifts are designed to model strategic behavior where the data owners (users) maximize a quadratic utility function adapting to the new $\\theta$, e.g., for logistics regression for defaults detection, we have $(x^\\star,y) \\sim {\\cal D}(\\theta)$ given by:\n\n$x^\\star = \\arg\\max_{x} U(x;\\bar{x},\\theta) =\\frac{- y <{\\theta},{x}>}{\\max\\\\{ \\epsilon_{\\sf U}, \\| \\theta \\| \\\\}}  - \\frac{1}{2\\beta} || x-\\bar{x} ||^2$\n\nwhere $(\\bar{x},y)$ is drawn from the base distribution. In doing so, users with a default history shift their profile towards having a lower chance to be detected as fraud ($y=1$). \n\n> Typos\n\nIndeed, in the proof of Lemma 3, it should point to (2) instead of (7). We will revise it.\n\n> Do you have any guarantees for the non-strongly convex case?\n\nTo our best knowledge, there is no known convergence guarantee for SGD with distribution shift with non-strongly convex loss function, even without clipping. The main challenge is that in the latter case, SGD (or even GD) may not converge to a unique solution even when the distribution shift is fixed. \n\nHaving said that, the non-strongly convex case can be partially covered by our Theorem 5 & 8 for the non-convex case, provided that $\\{ \\sup_{z \\in Z} |\\ell(\\theta_t ; z)| \\}_{t \\geq 0}$ is bounded. That said, we admit that the obtained bound is weaker than the strongly convex case.\n\n\n> Is the dependence on the dimension necessary?\n\nThe dependence on dimensionality arises from the setting that $\\zeta_{t+1} \\sim {\\cal N}(0, \\sigma_{DP}^2 {\\bf I})$ in (14) which is the same as in (Abadi et al., 2016) for satisfaction of the DP guarantee. This leads to $E[ || \\zeta_{t+1} ||^2 ] = d \\sigma_{DP}^2$. The same $d$-dependence would appear in Sec 3.3 of (Koloskova et al., 2023) if a similar design for the DP noise is adopted. Note that their paper took $\\zeta_{t+1} \\sim {\\cal N}(0, (\\sigma_{DP}^2/d) {\\bf I})$.", "claims_and_evidence": "The theoretical claims appear to be correct. The experimental results support these claims.", "methods_and_evaluation_criteria": "The evaluation is based on simple experiments and small datasets. For the purpose of validating the claims, they are fine. To show actually applications of the algorithm, the paper needs to show on real datasets with clear justifications/considerations for how the decision-dependent distributions are modeled.", "theoretical_claims": "- I checked Theorem 3 and 4, both are correct, except some typos. In the main paper, Theorem 3 made reference to $\\sigma_{DP}$ before it was introduced later. In the proof in the appendix, $\\zeta_t$ was also used (without proper introduction), and disappear in Line 647-652. \n- Validation of Assumption 8: The bound for $|e_t|$ is quite large in Figure 3, the question is how meaningful the bound $M$ is if it is so large.", "experimental_designs_or_analyses": "For the purpose of validating the theoretical claims, I think experimental setup in the paper is sufficient, although it is unclear the reason for the choice of the data distribution.", "relation_to_broader_scientific_literature": "The paper studies a problem of recent interest and the paper offers concrete theoretical guarantees for clipped SGD in this setting.", "essential_references_not_discussed": "None that I'm aware of.", "other_strengths_and_weaknesses": "- Personally I find the presentation hard to follow and I would prefer that the results and theorem statements are presented in a more concise way.", "other_comments_or_suggestions": "- In the proof of Lemma 3, the authors several times referred to Eq. 7 which didn't match the intended purpose.", "questions_for_authors": "- Do you have any guarantees for the non-strongly convex case?\n- Is the dependence on the dimension necessary?", "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:

Meta-review: Summary: This paper studies the convergence of clipped SGD algorithms with decision-dependent data distribution. In particular, the paper characterizes the stochastic bias with projected clipped SGD (PCSGD) algorithm, which is caused by the clipping operator that prevents PCSGD from reaching a stable solution (focusing on both strongly convex and non-convex problems). In addition, the paper proposes remedies to mitigate the bias, either by utilizing an optimal step size design for PCSGD. Numerical experiments verifying the theoretical results are also presented.

On Reviews: All reviewers gave a score 3 (weak accept) for this work. This classifies the paper as borderline. However, by reading the reviews and going through the paper, i believe the strengths outweigh the weaknesses. The weaknesses/questions mentioned in the reviewers were handled nicely by the authors during the rebuttals as well. 

I find the paper well-written, with clear and easily understandable contributions. Studying the convergence of clipped SGD algorithms with decision-dependent data distribution is a timely topic. I advise the authors to incorporate the feedback they received into the updated version of their work. I recommend acceptance.
Decision: Accept (poster)