Two-timescale Derivative Free Optimization for Performative Prediction with Markovian Data

Summary

The performative prediction problem targets real-world application using deployed models, and this method studies the optimiazation method for such a scenario. Since directly optimiazing the non-convex objective is challenging, this paper utilizes weighted Markovian samples of states to estimate the gradient and update with designed timescale step size.

Strengths

1. The paper is in general well-written. 2. The motivation is clear for tackling the targeted problem. 3. The theoretical derivation and understanding are well-presented. 4. The authors conduct various experiments settings to examine the the proposed method.

Weaknesses

1. The experiments are conducted on toy examples and illustrate the efficacy of the method. The question would arise for applying the method for more challenging task setting. Also, how does the method perform in comparison with other strategies that also fit with such tasks? 2. What the limitation of the proposed method? As it targets online deployed models and involves the Markov Chain sampling, what is the computational cost?

Questions

In general, the paper is well-written and would require background knowledge to understand the theoretical parts. My questions are listed: 1. L90: "Let S be a (measurable) sample space, and µ, ν are two probability measures defined on S." and L114: "sample a vector µ uniformly from S^d-1". Does that imply that µ is uniformly distributed among S? 2. Given that Πθ(·) is unknown (L105-106) while the Markov kernel Tθ(·, ·) is based on Πθ(·), how would the Markov kernel conduct toward sampling? 3. L138-140: "Under this setting, suppose that the previous state/sample is Z, the next sample follows the distribution Z′ ∼ Tθ(Z, ·) which is not necessarily the same as Πθ(·)." It might needs some theoretical background to understand this, so my question is that since Πθ(·) serves a stational distribution given θ, why Z not converge to certain point and then Z′ should be sampled from the same distribution?

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

3 good

Contribution

3 good

Limitations

Please see the weaknesses and questions part.

Summary

This paper proposes a derivative-free two-time scale for performative prediction problem. The two-timescale facilitates a faster accumulation of samples to compute a gradient with smaller bias. For smooth nonconvex objective, the work proves a iteration complexity of $O(\epsilon^{-3})$ for the $\epsilon$-staitonary point. They illustrate results via numerical experiments.

Strengths

1. This paper deals with an important problem: derivative-free optimization of nonconvex function under performative prediction setup. 2. The convergence rate seems reasonable. 3. The experiments are well-motivated.

Weaknesses

1. **The applications are shown for squared loss. But it is not a bounded loss and does not satisfy Assumption 3.2. This leads me to believe that Assumption 3.2 is made for the convenience of theoretical analysis.** In fact, **one of the major challenges in the decision-dependent noise or state-dependent Markov noise setup is that the algorithm is often not stable** for unconstrained optimization (see [1,2] below). Assumption 3.2 helps to avoid this issue. **So Assumption 3.2 is crucial for Lemma E.3 and Lemma B.i (i=1,2,3,4). Then the theoretical analysis of the algorithm does not apply to squared loss which is one of the most popular loss functions.** 2. The proof techniques required are pretty similar to Wu et al., 2020 ([3] below). In fact, **the main result is almost same as Corollary 4.9 of Wu et al., 2020. It's just that Corollary 4.9 of Wu et al., 2020 is wrapped in the cover of reinforcement learning but the algorithm, underlying proof techniques, and result are same.** Wu et al., 2020 does achieve a faster rate of $\tilde{O}(\epsilon^{-2.5})$ although I guess here the poor rate is due to derivative-free algorithm. [1] Liang, Faming. "Trajectory averaging for stochastic approximation MCMC algorithms." (2010): 2823-2856. [2] Andrieu, Christophe, Éric Moulines, and Pierre Priouret. "Stability of stochastic approximation under verifiable conditions." SIAM Journal on control and optimization 44, no. 1 (2005): 283-312. [3] Wu, Yue Frank, Weitong Zhang, Pan Xu, and Quanquan Gu. "A finite-time analysis of two time-scale actor-critic methods." Advances in Neural Information Processing Systems 33 (2020): 17617-17628.

Questions

1. It is not clear to me whether the derivative-free approach helps to deal with state-dependence of the Markov chain like mentioned in line 105-112? In other words, say there is a gradient oracle such that $g_{k}^{(m)}=\nabla l(\theta_k^{(m)},Z_{k}^{(m)})$. What will happen to the convergence rate of the algorithm then? 2. Please highlight the technical novelties required compared to Wu et al., 2020 (apart from the zeroth-order approximation). See point 2 of Weakness for details. I may change my score depending on the reply.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited 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

2 fair

Contribution

1 poor

Limitations

N/A

Summary

The paper studies performative prediction when the data is stateful, in particular generated via a controlled Markov chain, and the learner's loss is possibly nonconvex. The paper develops a two-timescale derivative-free optimization algorithm for this setting and shows a O(1/eps^3) sample complexity for finding a point with squared gradient norm at most eps.

Strengths

There aren't many convergence results in performative prediction for nonconvex settings, so this is one strength. The stateful setting has been studied before in several papers, but this paper studies this setting under quite a bit of generality. The treatment of the stateful setting in this paper is probably my favorite treatment of the setting in the literature. The paper is very clearly written and easy to follow, also providing intuition for the ideas behind the analysis, which I appreciated.

Weaknesses

There are some limitations to the conceptual novelty, in the sense that a similar algorithm has been studied outside of performative prediction, and the controlled Markov chain model for the distribution map has been studied. It would be good to be more precise about the differences to the recent works in performative prediction studying the stateful setting (bottom of page 2). The problem is perhaps arguably a bit niche since it goes away if the performativity is not stateful, which is the most commonly studied observation model in performative prediction. In that case, a simple application of the Flaxman et al. "gradient descent without a gradient" algorithm suffices. The issue in this paper is that we can't sample from the stationary distribution directly so a naive application of the Flaxman et al. algorithm doesn't work. All this being said, the stateful setting is very well-motivated and deserves its own analyses, and this paper gives a clever solution.

Questions

1. Can you please clarify the differences to prior work studying stateful performative prediction? 2. Do you have a sense of why SGD has these strange dips in Figure 1? 3. In lines 181-182, you say that the geometric dynamically environment of Ray et al. (2022) constitutes a special case of your assumptions. Can you give more natural examples of stateful distribution maps that satisfy your assumptions but are different from Ray et al.?

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

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

4 excellent

Contribution

3 good

Limitations

NA

Summary

This paper is on performative prediction i.e. a setting where the data distribution changes in response to the predictions of a learned model. The prototypical example of such a setting is where a learned model is used to make loan decisions, and then people or companies adjust their behavior based on knowledge of the learned model in order to secure more favorable loan terms. This paper extends prior work on performative prediction to the setting where the data distribution follows a controlled Markov process, where the control is given by the predictive model. While this setting has been studied before, this paper removes previous structural assumptions on (1) the loss function used to evaluate the model and (2) the dependence of the data distribution on model. Notably the loss function is not assumed to be convex, and so convergence is established to a stationary point (i.e. a point where the magnitude of the gradient is small). The algorithm designed is based on standard methods for derivative-free optimization, with a two-timescale step-size modification that updates model parameters more slowly than the generation of gradient estimates in order to deal with high variance in the gradient estimator.

Strengths

The extension of algorithms for performative prediction to the setting without convexity of the loss expands the range of techniques for such problems. The paper clearly discusses the differences with prior work and gives a concise and intuitive overview of the modifications required to make derivative-free optimization work for this setting.

Weaknesses

While I do appreciate the generality of extending algorithms for performative prediction beyond convex losses (as well as beyond the mixture dominance assumption on the data distribution), there are a couple of limitations that arise from assuming so little about the loss and data distribution. 1. The algorithm converges to a stationary point of the performative risk, rather than to a point that approximately minimizes the preformative risk. Of course this is necessary in the completely unstructured setting considered here, but it is clearly a weaker statement than e.g. the initial work of Perdomo et. al. that showed (for strongly convex losses) convergence of repeated risk minimization to a point that is close to an actual minimizer of the performative risk. This paper should state more clearly that such a strong result cannot be hoped for in the setting considered. In particular, the claim on line 43 seems somewhat misleading as written. 2. Removing the convexity assumption seems to come at the cost of introducing an additional assumption. In particular, Assumption 3.3 requires that the distribution map $\Pi_{\theta}$ is Lipschitz with respect to the total variation distance, rather than the Wasserstein 1 distance used in prior work. This is a **much stronger** assumption in many natural settings e.g. the mean of $n$-independent random $\pm 1$ valued variables has a distribution that converges in Wasserstein 1 distance to the Gaussian distribution at a rate of $\frac{1}{\sqrt{n}}$, but has the maximum possible total variation distance of 1 from the standard Gaussian distribution. 3. The algorithm has a slower convergence rate than those in prior work, as the authors show is necessary in this highly general setting. The original paper introducing performative prediction shows that repeated risk minimization converges at a linear rate, and thus allows us to leverage whatever fast optimization method fits the particular problem for each risk minimization step. In contrast, the algorithm in this paper requires us to essentially sample many, many random perturbations of the model and then deploy/evaluate each one in order to obtain gradient estimates, making it highly impractical for real-world problems. To summarize, the generality of the setting has several drawbacks in terms of the solution quality, performance of the algorithm, and most notably the additional assumption described in (2) above. While some of these drawbacks are provably necessary (again with the notable exception of the issue in (2)), taken together they suggest that perhaps this complete lack of structure is not a particularly good model of the types of problems for which performative prediction is interesting.

Questions

1. Is the Lipschitz assumption with respect to the total variation distance necessary in this setting? 2. Are there any intermediate models with assumptions weaker than strong convexity of the loss, but stronger than the assumptions made in this paper that could also be interesting?

Rating

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

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

3 good

Contribution

2 fair

Limitations

Yes.

Summary

The paper considers the performative prediction problem, where the goal of learner is to optimize the expectation of the known loss function over a decision-dependent unknown data distribution that evolves according to an underlying controlled Markov chain. Authors presents a stochastic derivative-free optimization algorithm $DFO(\lambda)$ that achieves $O(d^2/\varepsilon^3)$ sample complexity using gradient accumulation mechanism and two-timescale diminishing step-sizes.

Strengths

- The presented algorithm achieves a $O(1/\varepsilon^3)$ sample complexity under a challenging setting of Markovian data. - The other possible types of gradient estimator were considered that creates a more complete picture in the presented setup. - The presentation of the paper is clear.

Weaknesses

- No presented lower bound for this problem, thus it is not clear is the presented rates improbable or not.

Questions

- What could be challenges to generalize the proposed algorithm to the milder assumption on the Markov chain, i.e. V-ergodicity instead of the uniform ergodicity. - What is the bias of the first version of two-point estimate $g_{2pt-I}$? On which variables it depends in the worst case? - Is there some stronger assumptions on the Markov chain under which it is possible to recover $O(1/\varepsilon^2)$ rates as in i.i.d. case? - Can be this algorithm applied to the reinforcement leaning problem?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

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

3 good

Contribution

3 good

Limitations

This is a theoretical paper that does not need to address the potential societal impact.

Thank you for the response

Thank you for the response. The examples at the end are interesting and helpful.

Thanks for the reponse.

I am happy with the responses. I have increased my score.