Stochastic Optimization Schemes for Performative Prediction with Nonconvex Loss

Performative prediction problem is less motivated, i.e., there lacks a icon application such that the problem can only be formulated as a performative prediction problem and cannot be formulated in other forms even considering the special structure of the problem. The numerical experiments lacks a convincing example as well, i.e., why studying the problem. Leveraging the problem structure, many times the problem admits other more classical optimization objectives. It is not the problem of this paper alone but the whole research line.

Thanks for your critical comment on the state of performative prediction research. Many learning problems when applied in a "societal" setting will exhibit performativity. This is an inevitable outcome as the predictions informed by trained models becomes a part of the bigger social system. Further, an important property in performative prediction explored by this line of work is that the learner who trains the model cannot access information about how the distribution shifts, and thus cannot estimate the exact gradient of $V(\theta)$ that depends on ${\cal D}(\theta)$. Due to these limitations (note they are imposed by the application scenario rather than by the algorithm design), we believe that one of the key challenges shall lie in understanding and improving such "non-gradient" dynamics instead of exploring problem structure to efficiently minimize $V(\theta)$.

What happens to the analysis if the distribution is discrete. Then PDF may not exists and Pearson $\chi^2$ sensitivity may not be well-defined.

That's a good observation. We agree that the chi-squared divergence condition in the original C1 does not work with discrete distributions which limit its application. Fortunately, as pointed out by reviewer 71Gw, the above condition can be easily weakened into a sensitivity condition based on the total variation distance which also applies to discrete distribution (see C1' in the response to 71Gw). Nevertheless, our results also apply to cases with the Wasserstein-1 sensitivity condition (see W1).

Regarding Theorem 2, to ensure $\delta$ stationarity, it requires $T=O\left(\delta^{-2}\right)$ and $K=O\left(\delta^{-2}\right)$. It means that to control both the bias and the error accumulated in the iterations, it needs $T K=O\left(\delta^{-4}\right)$ iterations/samples. Is it possible to improve it to $O\left(\delta^{-2}\right)$, i.e., the same complexity as the non performative setting?

We believe that it is possible to improve the sample complexity of $TK$ beyond $O(\delta^{-4})$. This is because from (22), we observe that within the $t$th "inner loop" after each deployment, the SGD-lazy deploy scheme is essentially SGD for $\min_{\theta} J(\theta;\theta_t)$. Now to improve the sample complexity with $K$, one may replace the SGD method with variance reduced SGD such as using the STORM gradient estimator in [a].

However, we suspect that reaching the sample complexity of $O(\delta^{-2})$ would require more work. One of the reasons is that the structure of optimization algorithm is different as the learner does not have access to the (form of) distribution shift, and as explained in our manuscript, this limits the use of standard analysis tool such as (constant) Lyapunov function method. In general, characterizing and achieving the optimal sample complexity of performative optimization with non-convex loss is an exciting future direction to be explored.

[a] Cutkosky and Orabona, "Momentum-based variance reduction in non-convex sgd", NeurIPS 2019.

Table 1 should reflect the bias level and compare the bias level with existing literature. It should also mention what would be the sample complexity needed to ensure an stationary point in this work and other works.

The purpose of Table 1 is to compare the few existing works on non-convex performative prediction, yet other papers may have used other form of solution concepts where the studied algorithms admit various forms of biases. We intend to indicate their differences through displaying their respective convergent point "$\theta_{\infty}$" & algorithm type "Algo". To save space, we have used ${\cal O}(\epsilon)$-SPS to indicate the bias level of SGD-GD analyzed by us. As for the sample complexity, they can be deduced from the "Rate" column. We will improve the presentation of Table 1 in the revision if space allows.

I think some of the discussion in Section 3.1 could be simplified. Instead of assuming the chi squared divergence condition, one can get Lemma 3 by assuming that D(theta) is Lipschitz in TV distance (i.e. $||D(\theta) - D(\theta')|| \leq \epsilon ||\theta - \theta'||$), together with C2. The chi squared condition seems a bit odd and nonstandard because it is not a Lipschitz condition.

Thanks for your valuable suggestion. Indeed, as you said, the chi-squared condition (C1) can be replaced by a weaker TV distance condition. The argument is as follows.

First, we recall the definition of TV distance as $\delta_{TV}(\mu, \nu) = \sup_{A\subset {\sf Z} } \left| \mu(A) - \nu(A) \right| = \frac{1}{2} \int \left| p_{\mu}(z) - p_{\nu}(z) \right| {\sf d}z$ where $\mu, \nu$ are two measures supported on ${\sf Z}$ and $p_{(\cdot)}(z)$ denotes their pdfs. Note that we have $\delta_{TV}(\mu,\nu) \leq (1/2)\sqrt{\chi^2(\mu,\nu)}$ [Gibbs and Su, 2002, Sec. 2]. Accordingly, we may replace C1 by its weakened version:

C1' There exists a constant $\tilde{\epsilon}\geq 0$ such that $\delta_{TV}\left({\cal D}(\theta_1), {\cal D}(\theta_2)\right) \leq \tilde{\epsilon} \| \theta_1 - \theta_2 \|$ for any $\theta_1, \theta_2\in \mathbb{R}^d$

Using C1' and C2, we derive a similar result as Lemma 3 with the following chain

$$\begin{aligned} \left| J(\theta, \theta_1) - J(\theta, \theta_2)\right| &= \left| \int \ell(\theta; Z) (p_{\theta_1}(z) - p_{\theta_2}(z)) {\sf d}(z) \right| \leq \int |\ell(\theta; z)| \cdot \left| p_{\theta_1}(z) - p_{\theta_2}(z) \right| {\sf d}z \leq \ell_{max} \cdot \int \left| p_{\theta_1}(z) - p_{\theta_2}(z) \right| {\sf d}(z) \end{aligned}$$ $$\leq \ell_{max} \cdot 2\delta_{TV}({\cal D}(\theta_1), {\cal D}(\theta_2)) \leq 2\ell_{max} \tilde{\epsilon} || \theta_1 - \theta_2 ||$$

The rest of our convergence analysis for SGD-GD or SGD-lazy deploy follows immediately with the above modification. Again, we thank the reviewer for pointing this out and will make sure to include the above proofs in the revision!

Personally, I find it more appropriate to see Theorem 1 as a lemma and Corollary 1 as the main theorem.

We chose to describe our theoretical results in this way as we wish to include general conditions for the step size $\gamma_{t}$, such as diminishing and constant step sizes.

In the paragraph starting with line 275, you mention the relationship of Theorem 2 with RRM convergence and Mofakhami et al. My understanding was that they required a particular strong convexity condition, as noted in Table 1. So your result even for RRM may be new. Could you comment on this?

Though our Theorem 2 suggests a new finding for an RRM-like strategy, we believe that such strategy of SGD + lazy deployment with $K \to \infty$ strategy is not strictly equivalent to RRM. A subtle difference is that RRM (e.g., in [Mofakhami et al.]) requires finding an exact minimizer to the risk minimization problem given a fixed data distribution at each iteration, yet SGD + lazy deployment may only find a stationary point to the risk minimization problem (with non-convex loss) even when $K \to \infty$. As such, we have restrained from claiming it as a new finding for RRM. We will elaborate more in the revision.

The discussion about the time-varying Lyapunov function (e.g. starting at line 179) reminded me of the perspective from Drusvyatskiy and Xiao. They show that SGD in a performative context can be thought of as standard SGD on the equilibrium distribution, at the stable point. I’m wondering if you’ve thought about if there exists an analogue of this perspective in your nonconvex setting?

Although this is an interesting point, we believe that drawing such analogue for the nonconvex setting is difficult since the equilibrium distribution may not be unique in the latter case. In fact, the inability to apply the Lyapunov function $J(\theta;\theta_{PS})$ is also the reason why we had to develop a new time varying Lyapunov function in the nonconvex setting.

Other Problems

We also thank the reviewer for pointing out other typos and small issues in the paper. We will correct them in the revision.

The experiment setting is relatively simple but it's a minor issue since this is a theoretical work and the experiment is showcasing the concept.

We chose a simple experiment setting to demonstrate the effects of key parameters such as sensitivity strength $\epsilon$ and lazy deployment period $K$ to better validate the theoretical findings. We believe that this is an appropriate choice given the theoretical nature of this work.

Are there some other real applications besides the spam filter? Could the author provide more insight into this theoretical work and other policy-making applications with real-world influence?

Examples of performativity are pervasive in the real world, especially in the financial market and strategic training tasks, such as insurance, hiring, admission, and healthcare. In these scenarios, individuals often adjust their behaviors to receive predictions in their favor. For instance, in the hiring process, job applicants may prepare more relevant projects based on the job description provided by a company’s HR. When an employer conducts an interview and decides whether to hire an applicant, the applicant may have a higher chance of being hired if s/he is better prepared.

From a theoretical perspective, a crucial point we explored in this paper is that decisions are often made via models that are trained thru a non-convex optimization process, which has not been addressed in previous works on performative prediction. One takeaway from our findings is that - with reference to the results on lazy-deployment vs greedy-deployment SGD - when a decision maker (company) frequently changes its job description requirements, its trained model may experience greater bias that may lead to reduced performance.

The definition of SPS, as the authors mentioned, only considers the gradient regarding the loss function, while missing the gradient over the distribution parameter, which may not perfectly reflect the stationarity convergence of the objective function.

This is a valid observation. However, we remark that SPS is a stationary solution concept suitable for the arguably more "natural" algorithms for performative prediction -- including SGD-GD, SGD with lazy deployment, repeated risk minimization. These algorithms do not require a-priori knowledge of the form of data distribution shift, nor attempt to learn the latter. We believe these class of algorithms are important as they are applicable to scenarios when the learner is agnostic to the distribution shift. The definition of SPS generalizes that of performative stable (PS) solution [Perdomo et al., 2020] since for (strongly) convex $\ell(.)$, the definitions of SPS and PS solutions are equivalent. Note algorithms for achieving a stationary point for $V(\theta)$ has been explored in works like [Izzo et al., 2021], which represents a different research direction in the performative prediction community.

Some assumptions are still a bit unrealistic (for example, the global upper bound assumption in C2), it is not clear whether they are satisfied in the numerical experiments.

Admittedly, while assumptions like C2 may appear to be slightly strong, our theory remains applicable to a number of applications in ML including our numerical experiments. For the synthetic data experiments, the sigmoid loss function is upper bounded by 1. Similarly, in the neural network experiments, the loss is also upper bounded due to the sigmoid function applied in the last layer. Both simulations satisfy one of the required sets of assumptions (W1+W2 or C1+C2). We will expand the discussion on how these examples satisfy the assumptions in the revision. We also remark that C1 can be further relaxed to C1' using a weakened notion of distribution sensitivity; see the response to 71Gw.