Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Stochastic Bias and Remedies

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.

Please refer to the response to Reviewer svSm.

The appearance of $\zeta_{t}$ and $\sigma_{DP}^2$ in Theorem 3.

Thank you very much for the careful review and we apologize for these careless typos.

Indeed, 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.

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.

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

Experiments: The reason for the choice of the data distribution is unclear.

These 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:

$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$

where $(\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$).

Typos

Indeed, in the proof of Lemma 3, it should point to (2) instead of (7). We will revise it.

Do you have any guarantees for the non-strongly convex case?

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

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

Is the dependence on the dimension necessary?

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

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

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

$$\ell(\theta; z) = (1 + \exp(c \cdot y x^\top \theta))^{-1} + \frac{\eta}{2} \|| \theta \||^2$$

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

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.

This 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].

In Figure 1, what randomized mechanism for differential privacy is used? How exactly does the value of the privacy budget affect training?

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

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.

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

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

Difference in analysis vs existing works.

Indeed, 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.

Interaction between distribution shift and differential privacy beyond worst case

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

Statement about Rényi-DP and $e_t$.

We apologize for the careless typos.

• 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.
• The term $e_t$ is in $R^d$. We will revise notations throughout the paper.

Q: Guarantees for the convex case.

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

Q: Comparison with existing results involving clipping techniques in DP optimization.

Our work is the first to address the convergence of clipped SGD in performative prediction. Below is a brief comparison to related works:

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

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

Subject to space limitation, we will include a detailed comparison in the revised version.

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.

Our 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:

• 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.
• 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$.
• 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.
• 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.

We thank you for your comments and careful review. Our point-by-point replies are listed below.

The definition of $\sigma_{DP}^2$ in Theorem 3?

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

Additional bounded gradient assumption vs [Perdomo et al., 2020].

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

• 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].
• 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].

Additional Assumptions on bounded gradients (A3) and boundedness of $\ell$ (A7) used compared with [Koloskova et al., 2023, Theorem 3.3].

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

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

Lastly, as explained above, the set of assumptions for the non-convex case are justified too, e.g., with sigmoid loss as $\ell$.

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.

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

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

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