Zero-Regret Performative Prediction Under Inequality Constraints

Summary

The paper provides a new algorithm for performative prediction under general inequality constraints. The proposed algorithm has sublinear regret with respect to the performative optimum if the distribution map follows the location family model. The theory is supported by simulations.

Strengths

The motivation behind introducing constraints in performative prediction is strong and justified. The explicit regret guarantees are compelling. I thought Example 1 was well-motivated, clear, and a great example to keep in mind throughout. Section 3 is well-written and gives a clear step-by-step outline of the main method. The connection to existing work is thorough.

Weaknesses

The novelty has limitations. The main method combines existing ideas in the literature quite directly. The method for constructing a zeroth-order estimate of the gradient follows the same recipe as the two-stage method of Miller et al., and in a way this is the heart of the proposed method. This I see as the most relevant weakness. Below I'm including additional points. It is not clear what the meaning of the time horizon T is in your analyses. Normally this should be the number of collected samples. But in your paper this is not the case, and I think that for this reason your T has a somewhat arbitrary meaning. I would rewrite the result statements to make T the total number of collected samples (I don't think this should change your rates). This is important especially because when you tune n you set it to grow with T as sqrt(T). Assumption 1 is just there to ensure convexity of the objective, right? If so, maybe it's cleaner to state that assumption directly, and give the conditions in Assumption 1 as one way to satisfy the convexity condition. Otherwise, the way things are stated right now, your Example 1 wouldn't be handled by the assumptions? In Lemma 3 (and other results that rely on this lemma) I would probably write something like "there exists a delta(\eta, L_g) such that..." Right now the interval for delta is too cumbersome. You mention that derivative-free methods such as Flaxman et al. could be used for your problem. I think it would be a good idea to spell out exactly what they give you, because although you would lose dimension-dependent factors the results would be applicable much more broadly (all convex problems, not just location families). Location families are interesting but they are too specific.

Questions

In line 45, when you say "exponential structure" you mean exponential families? Line 148, denoted -> denote. I don't understand why you have both eta and delta. In problem (2) they appear together. I don't understand why they are tuned separately in the end? Why are they not treated as a single parameter? The notation in Algorithm 1 is strange. What do you mean by Z_t \sim \D(Z_0 + A-hat_t theta_t)? Also, shouldn't it be the true A and not A_t-hat? Please define PD-PS used in line 306. Line 320, sensitive -> sensitivity. Line 323 says accuracy decreases. You mean error decreases?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

2 fair

Limitations

N/A

Summary

The paper attempts to study the problem of learning where the problem instances arise from a distribution. What is special is that this distribution is dependent on the decision-maker. The specific problem is when the distribution is given by a linear shift over a fixed distribution where the degree of shift is given by the decision parameters itself, and the decision parameters itself need to satisfy an inequality constraint. The authors propose a PD algorithm that (under certain assumptions on the loss function) queries $T+2\cdot\sqrt{T}$ samples and violates $\sqrt{T}$ constraints to yield a $O(\sqrt{T})$ regret across $T$ rounds.

Strengths

The paper makes a good attempt at trying to look at the optimization problem with the inclusion of inequality constraints and it able to consider two simultaneous performance measures, namely, regret and (extent of) constraint violations.

Weaknesses

The paper promises a study in the direction of general optimization under (decision dependent) uncertainty but only tackles the problem in the limited case where the distribution is linear in the decision space. There is no discussion (or any insight) on how these techniques may generalize for more complicated distributions. The algorithm design itself does not appear to be very novel and uses fairly standard statistical estimation techniques.

Questions

How is Eq (4) (gradient of $PR(\theta)$ wrt $\theta$ ) on Pg 4 derived from Eq(1) (Definition of $PR(\theta)$)? Is there any hope (or negative results) in the case where the distribution does not follow a linear behavior wrt to decision parameter ? I would expect the sample complexity to rise wrt to the complexity of the dependence b/w $\theta$ and the distribution function $D(\theta)$. This body of work sounds similar to areas where the prediction problem is different from the optimization problem i.e. areas where the performance measure depends on both the unknown problem parameter as well as algorithm design (decision parameter), and the algorithm itself makes decision based on this caveat. Examples: 1. Customizing ML predictions for online algorithms (Anand et al) 2. Learning Predictions for Algorithms with Predictions (Khodak et al) Can you draw any parallels or is there no connection?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

Authors have addressed limitation adequately.

Summary

The paper studies the problem of performative prediction under inequality constraints and gives an no-regret learning algorithm that obtains $O(\sqrt{T})$ regret and uses $\sqrt{T} + 2T$ samples. In the problem of performative prediction, the data distribution $Z\sim D(\theta)$ depends on the choice $\theta$ of decision maker, and one formulates it as an optimization problem $\min_{\theta}E_{Z\sim D(\theta)}\ell(\theta, Z)$ and one only has sample access to the distribution $D(\theta)$. The major difference from previous work is that the paper considers a constrained optimization problem, where $\theta$ needs to satisfies certain constraints. The paper proposes to use primal-dual gradient descent-ascent to solve the problem. Especially, the paper considers location families (where $Z \sim Z_0 + A\theta$ for some unknown matrix $A$) and provides convergence guarantee when the loss function is well-behaved (e.g. strongly convex and smooth). Numerical experiments are also conducted to verify the practicality of the proposed method.

Strengths

The performative prediction task is a well-studied problem and the constrained one (studied by this paper) is well-motivated. The primal-dual method proposed in this paper is practical and the author also provides regret guarantee under assumptions. The writing is clear and easy to read.

Weaknesses

The technical novelty is limited, the primal dual method (and its robustness to gradient error) is fairly common in the literature.

Questions

The theoretical result mainly focus on the cumulative regret, but as an optimization problem, it is also important to obtain a good decision at the end of $T$ rounds. Do you think taking the average of $\theta_1,\dots,\theta_T$ would be result in a feasible decision with optimality guarantee? I have a few questions regarding the writing of the paper: (1) Algorithm Line 4,6, it should be $A$ instead of $\hat{A}_t$? (2) Assumption 3, what do you mean by saying the vector valued function $g(\theta)$ is convex? (3) Line 266, the LHS should be $g_i$ instead of $g_m$, right?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

2 fair

Limitations

.

Summary

This paper studies performative prediction under inequality constraints. In particular, the paper develops a robust primal-dual framework that requires only approximate gradients up to a certain accuracy but achieves the same order of performance as the stationary stochastic primal-dual algorithm even without performativity. Based on this framework, the authors propose an adaptive primal-dual algorithm for location families. The paper also presents the regret analysis and the perform numerical simulations to validate their findings.

Strengths

This paper studies and analyze the optimality of the performative prediction problem under inequality constraints, which is an important yet missing piece in the literature. As far as I know, this is the first paper attempts to provide a solution to this problem. The paper is well-written, easy to follow, and the proposed robust primal-dual method is intuitive. The theoretical analysis is throughout and it also provides empirical study to justify the findings.

Weaknesses

The major weakness of the paper is the assumptions are very strong, and the setting is somewhat restricted. For example, the proposed algorithm only works for a particular family of distribution, namely the location family, and it requires an accurate estimation of all the parameters involved in the computation, which might not be realistic. However, it is also almost unavoidable for the performative prediction setting.

Questions

1. Can the author be more explicit about the dependency on the sample required per iteration? In particular, for line 282, why does the initial sample $n\geq \sqrt{T}$ implies the sum of the expected gradient difference is bounded by $O(\sqrt{T})$?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

NA

Summary

This paper studies the problem of performative prediction under inequality constraints. The authors propose an adaptive, robust primal-dual algorithm that achieves sublinear regret and constraint violations, where the regret is with respect to the performative optima (instead of just a performative stable point). The algorithm is robust in the sense that it only requires approximate gradients up to a certain accuracy level and doesn't require the estimated gradients to be unbiased.

Strengths

* The main paper is very clearly written. The remarks around lemmas and theorems are helpful in interpreting the formal results. * The proposed primal-dual algorithm is very nice in the sense that (i) the gradient estimators don't need to be unbiased; and (ii) the authors prove a regret bound in terms of the accumulated gradient approximation error. This can be a valuable contribution to the research community. * The theoretical results are supplemented by good experimental results on multi-task linear regression and multi-asset portfolio.

Weaknesses

* The model assumes the learner can query the distribution for samples (lines 204 - 213). In particular, the learner can query the performative risk at $\theta_t$ and $\theta_t + u_t$. This is a strong assumption and should be stated more explicitly. What if the learner cannot query the distribution and only observes a single sample (or, say, $k$ samples) in each round depending on $\theta_t$? This is more similar to the setting of Jagdeesan et al. * I acknowledge that Assumption 1 is standard in the literature on performative prediction, but I find the strong-convexity assumption quite strong. * There is no discussion on lower bounds for the sample complexity. * The bound seems to have a factor of $d$ (the dimension). It is unclear to me whether this can be improved and how this compares to existing results in the performative prediction literature and results on performative regret in the unconstrained setting. (See one my questions below.)

Questions

* I really like example 1 (multi-asset portfolio). However, I have one question - can you elaborate on how "excessive investment in a particular asset can lead to a declination of its rate of return"? * Do you have thoughts on whether the sample complexity of $\sqrt{T} + 2 T$ is tight? * Can you provide some intuition for why the third part of Assumption 5 is needed? * What is the dependence of the bounds on the dimension $d$? For example, for the case of Gaussian noise, $\kappa_2 = d$ and $\kappa_3 = 3d$ (line 250) and in Lemma 4 this can result in a factor as large as $d$ (through the definition of $\bar{\alpha}$. Can this dependence be improved? Do existing results in the performative prediction literature (and results on performative regret in the unconstrained setting) have a similar dependence? * (This is a comment, not a question.) It would help to include some proof sketches in the main paper. (I have not checked the proofs in the appendix.)

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Limitations: Assumptions are clearly stated in Section 4. (The assumption that one can query the distribution could be stated more explicitly.) Negative societal impact: N/A.

Post response

Thank you for the responses! They were clarifying.