- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3(+1)
- Soundness
- 3
Read review
Paper summary
This paper studies the performative prediction problem. Formally, the authors aim to optimize the performative risk . Their goal is to find an -stationary point satisfying , without assuming a specific structure of distribution map .
Under this formulation, they propose Performative Trust-Region Optimization (PTRO). The algorithm contains two important steps: i) a local approximation for the effect of population response using estimated gradients, and ii) a dynamically maintained trust region radius to ensure reliable updates. Under smoothness assumptions, they show that a total number of iterations (Theorem 1 and Remark 1) with data samples per iteration (Proposition 2) are sufficient to obtain an -stationary point with high probability.
Finally, they provide experiments to validate the performance and robustness of their proposed PTRO algorithm, showing improved performance when the population response becomes more complex.
Critical strengths
-
They consider a setting of known loss function and unknown population response , which not only generalizes existing methods with known structure of , but also avoids treating the optimization as pure black-box using the information of .
-
The experiment provides evidence of the improved performance of PTRO algorithm, especially for complex population response.
Critical weaknesses
-
The comparison between their PTRO and the existing DFO$(\lambda)$ method is not so clear. It seems that DFO$(\lambda)$ can handle the same problem setting. Though the experiment shows PTRO have better performance, the improvement is not established by the theory.
-
The total -depencence for the total number of required samples in the theoretical claims is larger than existing methods.
-
There are several critical problems in the presentation, including:
- The statement of Lemma 1 is awkwardly worded.
- One of Table 2 and 3 in Appendix B is redundant.
Questions for authors
- Can you explain your main improvement/difference compared to DFO$(\lambda)$?
- Can you explain why your theoretical results have a relatively worse dependence on ? Is it from the difficulty of general setting or the analysis itself?
Other suggestions
- Please consider fixing the presentation issue mentioned in the weakness part. In addition, line 310 and 315 defines accuracy conditions used later, but the shorts ZO$(\cdot,\cdot,\cdot)$ and FO$(\cdot,\cdot)$ are not used in the main text (they are only used in the Appendix). Please consider rearrange the sentences.
3 comments
Proof sketch for the proposition we gave above:
Step 1: Limited information from the samples.
Each sample is a linear measurement of the unknown coefficients with independent Gaussian noise of variance . Its information matrix has trace equal to the sum of the squared measurement weights:
\sum_{j=1}^{d} \left[\cos^2(sx_j)+\sin^2(sx_j)\right] =\frac{64\varepsilon^4}{d}.$$ So $N$ samples gives \$ \operatorname{tr}(M) =N\frac{64\varepsilon^4}{d} \leq \frac{d^2}{128\varepsilon^4} \frac{64\varepsilon^4}{d} =\frac d2. \$ *Step 2: Many gradient directions remain uncertain.* Condition on the observations and the algorithm's randomness. The output $x_{\mathrm{out}}$ is now fixed, and the unknown coefficients have a Gaussian posterior with covariance $(I+M)^{-1}$. This also holds for adaptive sampling. By Step 1, the $2d$ nonnegative eigenvalues of $M$ sum to at most $d/2$. Thus, at least $3d/2$ eigenvalues are at most $1$. Along their eigenvectors, the posterior variance is \$ \frac{1}{1+\lambda}\geq\frac12. \$ Let $U$ be the subspace spanned by these eigenvectors. Every unit direction in $U$ therefore retains posterior variance at least $1/2$. Meanwhile, \$ \frac{\partial PR(x)}{\partial x_j} =\frac{8\epsilon}{\sqrt d} [-a_j\sin(sx_j)+b_j\cos(sx_j)] ,\$ let \$ q_j(x) = -a_j\sin(sx_j)+b_j\cos(sx_j).\$ The $d$ coefficient directions defining $q_j(x)$ are orthonormal: different $j$ use disjoint coefficient pairs, and each direction has squared length $\sin^2(sx_j)+\cos^2(sx_j)=1$. Let $V$ be their span at $x=x_{\mathrm{out}}$. Both $U$ and $V$ lie in the $2d$-dimensional coefficient space, so $$\dim(U\cap V) \geq \dim(U)+\dim(V)-2d \geq \frac{3d}{2}+d-2d =\frac d2.$$ Thus, at least $d/2$ directions both determine the gradient and retain substantial uncertainty. The $d$-dimensional space determining $q(x_{\mathrm{out}})$ (thus determining gradient) and uncertain $\frac{3d}{2}$ in the same $2d$ space, so they much overlap at least \$ d+\frac{3d}{2}-2d=\frac d2 \$ dimensions. Therefore, at least $d/2$ directions determining the gradient retain posterior variance at least $1/2$. *Step 3: The probability of stationarity is small.* The gradient calculation gives $$\|\nabla PR(x)\|^2 =\frac{64\varepsilon^2}{d}\|q(x)\|^2.$$ Thus, \$ \|\nabla PR(x)\|\leq\varepsilon \quad\Longleftrightarrow\quad \|q(x)\|^2\leq\frac d{64}. \$ Let $v_1,\ldots,v_m$ be orthonormal directions that both affect the gradient and retain posterior variance at least $1/2$ (uncertain directon), where $m\geq d/2$. Choose an orthonormal basis $v_1,\ldots,v_m$ of $U\cap V$, where $m\geq d/2$. Define $Y^r=\sum_{j=1}^{d} [v^r_{2j-1}a_j+v^r_{2j}b_j], \quad r=1,\ldots,m,$ let $Y=(Y^1,\ldots,Y^m)$. Thus, $Y$ is an $m$-dimensional vector recording the unknown coefficients along these directions. Conditional on the observations and the algorithm's randomness, it is Gaussian with covariance at least $\frac12 I_m$. Because these directions lie in $V$, projection onto them cannot increase the norm: \$ \|Y\|^2\leq\|q(x_{\mathrm{out}})\|^2.\$ Because they also lie in $U$, the conditional covariance of $Y$ satisfies $C\succeq\frac12 I_m$. For this Gaussian vector, \$Y\mid observations, algorithm \\ randomness \sim\mathcal N(\mu,C), C\succeq \frac12 I_m. \$ $$\mathbb{E}\left[e^{-\|Y\|^2}\right] = \frac{\exp\!\left[-\mu^\top(I_m+2C)^{-1}\mu\right]} {\sqrt{\det(I_m+2C)}} \leq 2^{-m/2}.$$ Applying Markov's inequality, \begin{align*} \Pr\left( \|\nabla PR(x_{\mathrm{out}})\|\leq\varepsilon \right) \leq \Pr\left(\|Y\|^2\leq d/64\right) \leq e^{d/64}\mathbb{E}\left[e^{-\|Y\|^2}\right] \leq e^{d/64}2^{-m/2} \leq e^{d/64}2^{-d/4} \leq e^{-0.157d}. \end{align*} These inequalities hold conditional on every observation transcript and therefore also hold after averaging. *Step 4: Obtain fixed, bounded coefficients.* Let $B$ be the event that all $2d$ coefficients lie in $[-4,4]$. For a standard Gaussian variable $G$, $\Pr(|G|\leq4)>0.9999$, so $\Pr(B)>0.9999^{2d}.$ Consequently, $$\Pr\left( \|\nabla PR(x_{\mathrm{out}})\|\leq\varepsilon \,\middle|\, B \right) \leq \frac{e^{-0.157d}}{0.9999^{2d}} \leq e^{-0.15d}.$$ This probability averages over bounded coefficient choices. Therefore, at least one fixed choice $a_j,b_j\in[-4,4]$ has the claimed probability bound.Thanks for your response. I will keep my overall rating for this paper.
We thank the reviewer for the constructive feedback and for recognizing the value of exploiting the known loss function while avoiding a parametric model of the population response. We also appreciate the positive assessment of our theoretical soundness and empirical results. We address the comparison with DFO, the dependence on d, and the presentation issues below.
1. PTRO differs from DFO in both gradient estimation and optimization mechanism. The reviewer is correct that derivative-free optimization (DFO) can address the same problem by treating the performative risk as a black-box objective. The main differences are:
(1) Gradient estimation: DFO(λ) uses randomized one-point zeroth-order estimates based on loss evaluations, whereas PTRO exploits the known loss structure and uses finite differences only to estimate the unknown population-response contribution.
(2) Optimization mechanism: DFO(λ) employs gradient-based updates, whereas PTRO uses a trust-region mechanism to evaluate candidate steps, accept or reject them based on observed improvement, and adapt the trust-region radius.
As discussed in Section 6.1, DFO(λ) also makes progress but exhibits greater fluctuations, consistent with the higher variability of its randomized one-point gradient estimator. We will clarify this distinction in the revised manuscript.
2. Dimension dependence is partly intrinsic to the problem.
(1) PTRO and DFO establish different convergence guarantees.
The sample-complexity bounds are not directly comparable across methods, as they rely on different assumptions and establish different convergence guarantees. In particular, DFO(λ) establishes stationarity in expectation, whereas PTRO guarantees ∣∇PR(xout)∣≤ε with high probability. Moreover, several methods with more favorable dimension dependence rely on a specified parametric population-response model, while PTRO does not. Achieving our conditional high-probability gradient-accuracy requirement entails additional sampling and concentration control.
(2) Our refined analysis improves the dimension dependence without additional assumptions.
After revisiting our analysis, we have refined the sample-complexity bound from O(d3+2/qε−4) to O(d3ε−4), without any algorithm modification or additional assumptions.
(3) Dimension dependence is partly intrinsic to the problem.
we additionally provide a lower bound establishing an intrinsic Ω(d2) sample requirement in the worst case. This shows that substantial dimension dependence is unavoidable.
Proposition For any adaptive, randomized algorithm that uses at most N≤d2/(128ε4) samples and returns a decision xout∈Rd, there is a problem in the family below for which $ \Pr \left( |\nabla PR(x_{\mathrm{out}})|\leq\varepsilon \right) \leq e^{-0.15d}. $
Thus, quadratic dependence on dimension in total sample complexity is unavoidable in the worst case for this family. It is not intended to establish tight sample-complexity bounds in either d or ε. Closing the gap with PTRO's upper bound remains an interesting direction for future work.
Construction. Let
\quad \ell(z;x)=z,$$ where \$ F(x)=\frac{8\varepsilon^2}{d} \sum_{j=1}^{d} \left[a_j\cos(sx_j)+b_j\sin(sx_j)\right], \quad s=\frac{\sqrt d}{\varepsilon}. \$ The coefficients $a_j,b_j$ are unknown, and \$ PR(x)=\mathbb{E}_{z\sim D(x)}[z]=F(x). \$ For the proof, first draw all $2d$ coefficients independently from $\mathcal{N}(0,1)$. At the end, we restrict them to $[-4,4]$ and identify a fixed choice with the claimed bound. Due to the space limit, we provide the proof sketch in a separate comment. **3. Presentation issues.** We thank the reviewer for identifying these issues. We will clarify Lemma 1, revise the overlapping tables in Appendix B, and introduce the ZO/FO abbreviations where they are used.