Optimal Classification under Performative Distribution Shift

Summary

This paper studies the performative learning problem, where the goal is to minimize some measure of *performative risk*, $PR(\theta) := \underset{\theta}{\mathbb{E}}[\ell(Z; \theta)]$, where the difficulty is that random variables come from some distribution the depends on the deployed model parameters $\theta$, i.e. $Z \sim \underset{\theta}{\mathbb{P}}$. The paper models the performative effect of some model parameters $\theta$ as a pushforward measure under some differentiable, invertible mapping that depends on $\theta$. This pushforward measure view of performative learning admits a couple of main results: 1. This gives a new expression for the performative gradient (the quantity $\nabla_{\theta} PR(\theta$)). 2. For strategic classification, a specific performative learning scenario, we find that performative risk is convex under linearity assumptions on the performative shift and the classifier model. 3. Under the same assumptions as (2), we can rewrite the performative risk as a min-max problem, connecting the performative risk in this classification scenario to adversarially robust classification.

Strengths

Overall, the paper is well-written, with a couple of clarity suggestions (in "Weaknesses") that may make the presentation smoother. The technical results are sound and, to my limited knowledge of the performative learning literature, the proposal to model performative shifts as a pushforward measure seems novel and interesting. However, I must emphasize that I am not very familiar with the literature on performative learning, so I cannot judge well the impact of such an approach on existing work. **Originality:** The main original contribution of this work is modeling the performative effect as a pushforward measure, which seems novel to my limited knowledge. The main results of the paper drop out of this modeling assumption, which seems flexible and general. However, I have a couple of questions towards how natural the specific instantiations of this pushforward measure are, particularly the "shift operator" used in many of the results (see "Questions"). **Quality:** I cannot give too informed a judgment of the quality of the results in comparison to other literature on performative learning, but to my reading, the technical results and evaluation seem sound. The authors provide a comparison to the gradient estimator for the performative effect of Izzo et al. (2022) and demonstrate their method's efficacy in comparison. The analysis seems sound, but I have no reference for how important this comparison is or whether there are better baselines in the literature to compare to. **Clarity:** The paper is well-written overall, but I have a couple of suggestions for presentation in "Weaknesses." **Significance:** As an outsider to the subfield, I cannot give a fully informed judgment on the significance of this paper, but, taking the comparison to Izzo et al. (2022) into account and viewing the displayed experiments, it seems that this modeling assumption does lead to an effective gradient estimator for performative risk.

Weaknesses

As I am an outsider to the subfield, I cannot comment too much on the relative weaknesses of this approach to others in performative learning. I am also not aware of current results in this subfield, but it seems like optimizing this notion of performative risk is still in nascent stages if theorems like Theorem 2 exist just to show situations in which we can prove that it is convex and apply standard optimization techniques to the problem. As such, I can only give a couple of suggestions that may improve the clarity of the paper's presentation: 1. Throughout the paper, the term "performative effect" is used quite heavily, but I believe it lacks a formal definition. I assume that we are to take the performative effect as, ultimately, the distribution $\mathbb{P}_{\theta}$, but it wasn't completely clear to me on a first reading of the introduction. Explicitly defining this term in the intro may help. 2. On Page 3, when introducing the pushforward measure, I would define the "pound" symbol. I wasn't aware of this notation until I looked it up on Wikpedia. 3. Small nitpick: on page 3, "$\mathbb{P}$ admits a density" should specify the density $p(\cdot)$ that $\mathbb{P}$ admits. 4. In the Experiments section, I didn't find your algorithm "Reparametrization-based Performative Gradient (RPPerfGD)" clearly defined. I assume that the algorithm just uses the gradient in Equation 3 (Definition 1) as an estimator of the gradient and performs gradient descent, but it would be helpful to explicitly write that in the Experiments section next to the baselines.

Questions

I have a couple of questions that may stem from my unfamiliarity with the literature: 1. How restrictive is the assumption that the performative effect can be modeled by a "shift operator"? I didn't fully understand how natural this assumption is, and some motivation to this assumption would help the presentation. However, I understand that this might just stem from my lack of exposure to the literature. 2. In order to estimate the gradient in Definition 1, you must have access to the form of the operator that defines the pushforward performative model, $\psi$. How realistic is it to assume that one has access to this in a non-synthetic scenario?

Rating

6

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors have addressed limitations in the NeurIPS paper checklist. They also motivated the problem of performative learning in their Introduction.

Summary

This paper considers a specific performative effect that's characterized as a transformation on the original probability measure on covariate X, which is novel in the literature. The authors propose to restrict the performative effect of deploying model with parameter \theta to such a multiplier function \varphi_\theta, which is mainly a shift operator in the discussion of this paper and can be viewed as a strong restriction on shift pattern. Authors also show the benefit of scalability of performative gradient estimation based on this performative effect, and demonstrate the convexity of performative risk can be achieved through direction of performative effect instead of its magnitude, in the context of binary classification and shift operator. This finding is interesting and novel in the literature. Moreover, authors show the connection with robustness and regularization by a minimax reformulation.

Strengths

1. This paper clearly presents its assumption, main theorems with illustrative examples, which makes this paper easy to follow. 2. This paper generalizes the performative shift pattern in former literature without restricting to location-scale family, and reveal another path to convexity of performative risk, which is innovative. 3. Connection with robustness and regularization is also presented to strengthen the background of this paper.

Weaknesses

1. The main weakness is the generality of the performative effect, \Pi \theta, a shift on covariate, since it's the factual pattern considered in this paper. For general \varphi_\theta, this paper doesn't discuss how to identify or effectively estimate such transformation function \varphi_\theta. Moreover, the knowledge on shift matrix \Pi is also susceptible, since the specific mechanism of the distribution shift is usually unknown in the context of performative prediction. 2. In the synthetic experiments, I think the authors should explore more abundant \varphi_\theta and show the benefit of scalability for high-dimensional \theta. In fact, the experiments mainly shown in the main paper is still restricted to the 2-dimensional simple setting of Izzo et al. 2022 and neither validate such scalability nor explore general \varphi_\theta. In addition, the colors used for denote different methods should be more distingushable.

Questions

1. Can the authors provide some intuitions on the dimension-freeness of \hat{G}_\theta^{R P}? I think it's a bit counterfactual since the shift \Pi \theta is put on the covariate X.

Rating

5

Confidence

4

Soundness

2

Presentation

3

Contribution

2

Limitations

See weaknesses.

Summary

The authors address the challenge of performative prediction, a scenario in which the predictor's outcomes influence the underlying data distribution. They introduce a novel formulation for the gradient of the performative risk, thereby enabling the implementation of stochastic optimization methods. This new formulation offers an advantage over existing approaches by producing a gradient estimator with lower variance, particularly in cases where the data distribution shift is linear. Additionally, the authors establish a weaker sufficient condition for the convexity of the performative risk in situations involving linear classifiers and linear distributional shifts. Furthermore, they demonstrate that transform-invariant learning leads to parameter regularization. Empirical evaluations reveal that the proposed method achieves superior stable accuracy compared to existing techniques.

Strengths

This well-written paper addresses a crucial problem in performative prediction that is highly relevant to the conference. The authors' theoretical contributions are clearly presented. The proposed estimator for the performative gradient is novel and innovative. Its advantages over existing estimators are verified through an analysis of the estimator's variance under the linear shift scenario. The lower variance of this estimator results in faster convergence of the stochastic gradient descent, demonstrating its practical utility. The authors' finding of a sufficient condition for the convexity of the performative loss under the linear shift setup is also a significant contribution. The benefits of this condition are adequately demonstrated, particularly in practical examples where existing techniques fail to verify the convexity of the performative loss. The experimental results effectively demonstrate the superiority and stability of the proposed estimator compared to existing methods. These results indicate that the authors' method achieves greater stability while simultaneously improving accuracy, underscoring its practical applicability.

Weaknesses

One potential limitation of the study is that the authors' analyses are primarily limited to linear shift cases. The linear shift assumption is relatively strong and may not hold in many practical scenarios. Moreover, the variance reduction effect is confirmed only under the linear shift setup, leaving the benefits of the proposed estimator in other situations unclear. The implications of Theorem 4 require further clarification. The claim that the magnitude of $\theta^*$ becomes smaller for a larger $\Pi$ is questionable, as the norm $\\cdot\_\Pi$ is also affected by the magnitude of $\Pi$. This relationship warrants a more detailed explanation or additional analysis. The assertion that knowing $\varphi$ is more practical than knowing $p_\theta$ may be an overstatement. Both assumptions appear to be equally unrealistic in practical applications, and this comparison could benefit from a more nuanced discussion.

Questions

- How might your approach be extended to non-linear shift scenarios?

Rating

5

Confidence

2

Soundness

3

Presentation

3

Contribution

2

Limitations

The authors adequately address the limitations and potential impacts.