Stochastic Optimization Schemes for Performative Prediction with Nonconvex Loss

Summary

A nice paper that studies nonconvex performative prediction optimization. Proposed a new stationarity notion and demonstrated convergence for SGD with greedy deployment.

Strengths

1. Extending the convergence measurement from the strongly convex case to the nonconvex case and proposing the stationary performative stable notion. 2. Extremely clear and easy to follow with key insights for the performative prediction problems. 3. Novel convergence guarantees. 4. The lazy deployment is quite interesting. It is equivalent to using mini-batch in some sense.

Weaknesses

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

Questions

1. What happens to the analysis if the distribution is discrete. Then PDF may not exists and Pearson $\chi^2$ sensitivity may not be well-defined. 2. Regarding Theorem 2, to ensure $\delta$ stationarity, it requires $T=O(\delta^{-2})$ and $K=O(\delta^{-2})$. It means that to control both the bias and the error accumulated in the iterations, it needs $TK = O(\delta^{-4})$ iterations/samples. Is it possible to improve it to $O(\delta^{-2})$, i.e., the same complexity as the non performative setting? 3. Table 1 should reflect the bias level and compare the bias level with existing literature. It should also mention what would be the sample complexity needed to ensure an $\delta$ stationary point in this work and other works.

Rating

6

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

See questions above.

Summary

The paper studies convergence of stochastic gradient descent in a performative prediction context. The main result shows that SGD converges to an analogue of performative stability, which the paper terms “stationary performative stability” (up to a bias term). The results characterize the rate of convergence and the magnitude of the bias.

Strengths

The results in this paper significantly expand the scope of optimization in performative prediction, which has so far largely focused on convex loss functions. In fact, most results require strongly convex losses. Moreover, prior work typically makes an assumption on the magnitude of the performative effects, captured by the sensitivity parameter epsilon; the convergence results of this paper do not require a bound on epsilon and show that the sensitivity determines the distance to stationary performative stability. The lack of assumption about epsilon is a major advantage. There are some other works, e.g. Jagadeesan et al., that do not require a bound on epsilon, but this work requires knowing epsilon to run the optimization method. The additional analysis of the lazy deploy scheme, which approximates RRM and thus incurs no bias in the limit, is a nice addition. The observation about the different dependence of the bias on epsilon depending on whether the gradients are stochastic or not is another nice result.

Weaknesses

This is not really a major weakness, but I think some of the discussion in Section 3.1 could be simplified. Instead of assuming the chi squared divergence condition, one can get Lemma 3 by assuming that D(theta) is Lipschitz in TV distance (i.e. ||D(\theta) - D(\theta')|| \leq \epsilon ||\theta - \theta'||), together with C2. The chi squared condition seems a bit odd and nonstandard because it is not a Lipschitz condition. In A2, the first part of the sentence is not an assumption; it’s true just by the definition of J? In Lemma 1, Theorem 1 (and possibly other places) please use parentheses in the step size condition. It should be 1/(L(1+sigma1^2)). Very minor suggestion: personally I find it more appropriate to see Theorem 1 as a lemma and Corollary 1 as the main theorem. Please don’t use the symbol T in Theorem 2 for the random step because you use that symbol in eq. (4).

Questions

In the paragraph starting with line 275, you mention the relationship of Theorem 2 with RRM convergence and Mofakhami et al. My understanding was that they required a particular strong convexity condition, as noted in Table 1. So your result even for RRM may be new. Could you comment on this? The discussion about the time-varying Lyapunov function (e.g. starting at line 179) reminded me of the perspective from Drusvyatskiy and Xiao. They show that SGD in a performative context can be thought of as standard SGD on the equilibrium distribution, at the stable point. I’m wondering if you’ve thought about if there exists an analogue of this perspective in your nonconvex setting?

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

There is not much discussion of limitations, though I don't think it is necessary.

Summary

This paper studied the `performative prediction’ that means when predictive models are used to make consequential decisions like policy making, it can trigger actions that influence the outcome they aim to predict. And we know a system with unlimited positive feedback will eventually be destroyed. On the optimization side, this work considered a risk minimization problem with a decision-dependent data distribution. It means the loss function specified by model parameters $\theta$ and the data distribution. They analyzed stochastic gradient descent (SGD) with a greedy deployment scheme (SGD-GD) in a setting that only requires the smoothness of non-convex loss function $l$. They showed the algorithm convergence to stationary performative stable (SPS) solutions with two types of distance metrics of distributions. Numerical examples of both synthetic and real data are provided to justify their theoretical result.

Strengths

Pros: It's a solid extension of the SGD-GD works of [Mofakhami et al., 2023] and [Mendler-Dünner et al., 2020] with smooth but not necessarily non-convex loss $l$. It’s a big step forward compared to the strongly convex loss in previous work. They provide both real and synthetic experiments to justify their claims.

Weaknesses

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

Questions

The reviewer is generally positive about this work. One question would be: Are there some other real applications besides the spam filter? Could the author provide more insight into this theoretical work and other policy-making applications with real-world influence?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

This work studied performative prediction problems in nonconvex regimes and proposed the first algorithm, SGD-GD, with convergence guarantees in this case, it was further extended to a lazy deployment scheme so that the algorithm is bias-free.

Strengths

1. First convergence analysis of gradient-based algorithms for performative prediction problems in nonconvex regimes. Which is a novel contribution. 2. Proposed a new convergence measurement for nonconvex performative prediction problems 3. The writing is great and the storyline is easy to understand

Weaknesses

1. The definition of SPS, as the authors mentioned, only considers the gradient regarding the loss function, while missing the gradient over the distribution parameter, which may not perfectly reflect the stationarity convergence of the objective function. 2. Some assumptions are still a bit unrealistic (for example, the global upper bound assumption in C2), it is not clear whether they are satisfied in the numerical experiments.

Questions

/

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

/

Discussions

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

Response to the author

The reviewer thanks the author for the response. After reading the rebuttal discussion from all reviewers, the reviewer would like to maintain the score.