acceptodds
Under review as a conference paper at ICLR 2027

Trust-Region Optimization for Performative Prediction without Response Modeling

Abstract

Performative prediction studies learning problems in which deployed decisions change the distribution of future data. Optimizing under this feedback requires understanding not only how a decision affects the loss, but also how the population responds to that decision. Existing approaches often make this problem tractable by imposing structure on the population response, but lead to limiting applicability when responses are poorly captured by a fixed model class. Generic black-box optimization avoids response modeling, but discards structure that is readily available in this setting: the loss function itself is often known in performative prediction. We introduce Performative Trust-Region Optimization (PTRO), which bridges these two approaches by optimizing performative risk without specifying or fitting a response model while still exploiting the known loss. The key idea is sampling from the current population to evaluate the known loss at nearby decisions, and use additional deployments only to estimate the effect of population response. This gives a local approximation of performative risk without committing to a model of how the population responds. PTRO then uses a trust-region mechanism to determine and adapt how far this local information can be trusted. Under moment-bounded losses and suitable smoothness and estimator-accuracy conditions, we establish high-probability convergence to an -stationary point of the performative risk with in iterations, with samples per iteration, where is the decision dimension and is the loss-moment order. Experiments illustrate methods built around a specified response model can be more sample-efficient when their structural assumptions are accurate, whereas PTRO remains effective as the population response is poorly captured by a fixed model class. Ablations further show that both exploiting the known loss and adaptive trust-region updates are important for controlling the accuracy and efficiency.

Primary area:
optimization
Keywords:
performative prediction, stochastic optimization, trust-region methods, decision-dependent distributions.

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_HFsrOpenReview ↗
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 PR(x)=Ez∼D(x)[ℓ(z;x)]PR(x)=\mathbb{E}_{z\sim D(x)}[\ell(z;x)]. Their goal is to find an ϵ\epsilon-stationary point satisfying ∥∇PR(x)∥≤ϵ\Vert\nabla PR(x)\Vert\le\epsilon, without assuming a specific structure of distribution map D(⋅)D(\cdot).

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 ts=O(ϵ−2)t_s=O(\epsilon^{-2}) iterations (Theorem 1 and Remark 1) with Niter=O(d3+2/qϵ−4)N_{\text{iter}}=O(d^{3+2/q}\epsilon^{-4}) data samples per iteration (Proposition 2) are sufficient to obtain an ϵ\epsilon-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 ℓ\ell and unknown population response D(⋅)D(\cdot), which not only generalizes existing methods with known structure of D(⋅)D(\cdot), but also avoids treating the optimization as pure black-box using the information of ℓ\ell.

  • 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 dd-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 dd? 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

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 dd, 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(λ\lambda) 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(λ\lambda) 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(λ\lambda) 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(λ\lambda) establishes stationarity in expectation, whereas PTRO guarantees ∣∇PR(xout)∣≤ε|\nabla PR(x_{\mathrm{out}})|\leq\varepsilon 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)O(d^{3+2/q}\varepsilon^{-4}) to O(d3ε−4)O(d^3\varepsilon^{-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)\Omega(d^2) 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)N\leq d^2/(128\varepsilon^4) samples and returns a decision xout∈Rdx_{\mathrm{out}}\in\mathbb R^d, 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 dd or ε\varepsilon. 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.

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 11. 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.

Reviewer_6qTvOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes Performative Trust-Region Optimization (PTRO), a method for optimizing nonconvex performative risk without explicitly modeling the population response. The method uses the known loss function to evaluate the direct effect of a decision and estimates the effect of distribution shifts using finite differences. These estimates are combined into a local trust-region model. The authors provide high-probability convergence guarantees and evaluate PTRO under different population response settings, including heterogeneous and nonlinear responses.

Critical strengths
  1. The paper addresses an important problem by optimizing performative risk without assuming a specific parametric response model. I particularly appreciate how the method exploits the known loss function and estimates only the unknown distributional effect, rather than treating the entire objective as a black box.

  2. The theoretical analysis is a valuable part of the paper. In particular, establishing high-probability convergence guarantees for a trust-region method under unknown decision-dependent distributions is an interesting contribution.

  3. The experimental results are encouraging. PTRO performs particularly well under heterogeneous and nonlinear responses, where model-based baselines struggle. The experiments also include useful ablations demonstrating the benefits of exploiting the known loss function and adapting the trust-region radius.

Critical weaknesses
  1. An important related work appears to be missing. The authors of [1] also study nonconvex optimization with unknown decision-dependent distributions and exploit the known loss function to improve zeroth-order optimization. I believe this work deserves a more detailed discussion, and comparing PTRO with their methods, possibly in their experimental settings, would strengthen the evaluation. Another recent, closely related method is PISO [2], which uses residual tracking to estimate the unknown gradient component. Although [2] appeared after the submission deadline, it could provide a useful additional baseline.

  2. My second concern is the sampling and deployment cost. PTRO requires O(d3+2/qϵ−4)O(d^{3+2/q}\epsilon^{-4}) samples per iteration, leading to a total sample complexity of O(d3+2/qϵ−6)O(d^{3+2/q}\epsilon^{-6}) under the stated iteration bound. More importantly, each iteration requires dd additional coordinate-wise deployments, which could be expensive in real-world applications involving high-dimensional models. This raises concerns about the practical scalability of the method.

  3. I found a potential issue in the proof of Theorem 1 concerning the initial trust-region radius. In Appendix D.4, the initialization term in BϵB_\epsilon becomes zero when α0<αˉ\alpha_0<\bar{\alpha}, making the iteration bound independent of how small α0\alpha_0 is. To illustrate the issue, consider the deterministic one-dimensional problem PR(x)=1−cos⁡xPR(x)=1-\cos x, with D(x)=δ0D(x)=\delta_0, initialized at x0=π/2x_0=\pi/2 and with ϵ=0.5\epsilon=0.5. This problem satisfies the stated regularity and estimator-accuracy assumptions. Let γinc=2\gamma_{\mathrm{inc}}=2. Since the trust-region radius can increase by at most a factor of two per iteration, we have ∣xk−x0∣≤α0(2k−1)|x_k-x_0|\leq\alpha_0(2^k-1). Now consider any sufficiently large fixed TT for which Theorem 1 gives a positive lower bound on the probability of reaching an ϵ\epsilon-stationary point. We can choose 0<α0<min⁡{αˉ,0.1/(2T−1)}0<\alpha_0<\min\{\bar{\alpha},0.1/(2^T-1)\}. Then, for every k<Tk<T, we have ∣xk−π/2∣<0.1|x_k-\pi/2|<0.1, implying ∣∇PR(xk)∣>cos⁡(0.1)>0.5|\nabla PR(x_k)|>\cos(0.1)>0.5. Thus, the probability of reaching an ϵ\epsilon-stationary point within TT iterations is actually zero, contradicting the stated finite-time guarantee. The issue appears to arise from not accounting for the iterations required to increase an arbitrarily small initial trust-region radius. While the asymptotic convergence rate may still hold with a corrected bound, I believe this part of the proof needs to be revisited.

[1] Y. Hikima, H. Sawada, and A. Fujino. "Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependent Distributions." International Conference on Machine Learning (ICML), 2025.

[2] E. M. Chayti, A. Mirrokni, and M. Jaggi. "Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking." arXiv preprint arXiv:2610.13871, 2026.

Questions for authors
  1. Could the authors discuss the differences between PTRO and the guided zeroth-order methods in Hikima (2025)? Would it be possible to compare them experimentally, including in the settings considered in Hikima (2025)?

  2. How practical is PTRO for high-dimensional models, given its dimension-dependent sample complexity and the need for dd additional deployments per iteration? Could randomized perturbations help reduce this cost?

  3. Could the authors clarify the initialization term in Theorem 1 and the iteration-counting argument in Appendix D.4? In particular, how does the current bound account for the iterations required when α0\alpha_0 is arbitrarily small?

4 comments

We sincerely thank the reviewer for the careful and constructive assessment. We particularly appreciate the recognition of PTRO's use of the known loss structure, its high-probability convergence analysis, and its robustness under heterogeneous and nonlinear population responses. We agree that the three concerns are important: positioning relative to recent methods, deployment efficiency, and the initialization argument. We address them below, including a correction to the theorem statement.

1. Relationship to Guided Zeroth-Order Methods Thank you for bringing Hikima et al. (2025) to our attention. We agree that it is highly relevant: both approaches optimize nonconvex objectives under unknown decision-dependent distributions and exploit the known loss without fitting a parametric response model. We will add a comparison in the related-work section.

The key distinction is how the known loss information enters optimization. Guided zeroth-order (GZO) methods use the direct-effect gradient ∇x1R\nabla_{x_1}R to guide randomized perturbations, but still estimate the full performative gradient through two-point loss evaluations. Specifically, GZO-NS estimates the guide using fresh samples, while GZO-HS reuses samples from the current and previous two-point evaluations, avoiding additional sampling for the guide. PTRO instead directly incorporates ∇x1R\nabla_{x_1}R into its local model and uses finite differences only for the unknown response-gradient component ∇x2R\nabla_{x_2}R. Then it uses a trust-region acceptance mechanism to validate candidate improvements and adapt the step radius.

This distinction becomes particularly important when the direct-effect gradient is poorly aligned with the full performative gradient. The effectiveness of GZO's guidance depends on the alignment between ∇x1R\nabla_{x_1}R and ∇PR=∇x1R+∇x2R\nabla PR=\nabla_{x_1}R+\nabla_{x_2}R. When the response effect is small, the guide closely approximates the full gradient; when the response effect substantially changes its direction, guidance based on the direct effect becomes less informative. PTRO explicitly estimates both contributions rather than relying on their alignment.

Theoretical guarantees also differ: Hikima et al. establish an expected squared-gradient guarantee with total sample complexity O(σ3d4ϵ−6)O(\sigma^3d^4\epsilon^{-6}), using constant-size minibatches per iteration. PTRO establishes a high-probability stationarity guarantee with O(ϵ−2)O(\epsilon^{-2}) iterations and sufficient per-iteration sampling O(d3ϵ−4)O(d^{3}\epsilon^{-4}). These bounds are not directly comparable since the assumptions and convergence criteria differ. In particular, Hikima et al. assume uniformly bounded variance of the on-policy loss, whereas PTRO assumes a uniform qq-th moment bound over both evaluation and deployment decisions.

Our additional experiments illustrate the practical consequences of this distinction in both directions.

On our MixL and MixN response settings, the direct-effect and full performative gradients are poorly aligned, with squared cosine similarity at most 0.20.2 along the evaluated trajectories. PTRO achieves the best performance in these settings, consistent with the benefit of explicitly estimating the response-gradient contribution.

We also evaluate PTRO on the benchmark of Hikima et al. (2025), with detailed results provided in a separate comment. In this benchmark, the response-gradient magnitude is only approximately 1010–1414 percent of the full gradient at initialization, and the cosine similarity between the direct-effect and full gradients is approximately 0.990.99. This is a favorable setting for guided perturbations. Accordingly, GZO-HS performs best at the original budget of 10410^4 samples, benefiting from strong alignment and sample reuse.

As the sampling budget increases, the comparison reverses. At 2×1042\times10^4 samples, PTRO begins to achieve the lowest mean loss across all tested τ\tau. At 4×1044\times10^4 samples, PTRO achieves both the lowest mean loss and the highest AUC for every τ\tau.

Taken together, these results reveal a meaningful tradeoff : GZO-HS is highly sample-efficient when its guide is well aligned with the true gradient, whereas PTRO benefits from explicitly modeling the response-gradient contribution and validating updates through the trust-region mechanism, particularly when gradient alignment is poor or sufficient samples are available.

2. Sampling and Deployment Cost

We thank the reviewer for highlighting deployment scalability. We clarify three points.

First, we sharpen the theoretical sample-complexity bound without changing PTRO. Revisiting our analysis gives a sufficient per-iteration sample complexity of O(d3ϵ−4)O(d^3\epsilon^{-4}), improving the submitted O(d3+2/qϵ−4)O(d^{3+2/q}\epsilon^{-4}) bound without modifying the algorithm or introducing additional assumptions. The extra d2/qd^{2/q} factor arose from a coordinate-wise concentration argument stronger than required by the trust-region convergence proof.

Second, we agree that randomized finite differences can reduce the number of perturbed deployments used by an individual gradient estimator, but fewer perturbations do not automatically imply accurate full-gradient estimation.

To illustrate the information limitation, consider reconstructing an arbitrary unknown unit vector in Rd\mathbb R^d from exact linear directional measurements. Even if each deployment reveals its corresponding directional measurement without noise, the expected squared reconstruction error after mm adaptively chosen measurements is at least 1−m/d1-m/d under a uniform spherical prior. Consequently, constant-accuracy full-gradient reconstruction with high probability requires Ω(d)\Omega(d) directional measurements in this model.

More broadly, PTRO provides a trust-region framework for performative optimization, with coordinate-wise finite differences serving as one implementation under our current assumptions. We recognize that this choice may not be the most deployment-efficient in all settings. Exploring alternative gradient estimators that satisfy the required accuracy conditions could offer opportunities to improve deployment efficiency, particularly when additional structural or statistical information is available.

Third, empirical scaling is milder than the sufficient bound suggests. Our existing dimension-scaling study in Appendix E.5, covering d∈10,50,100,200d\in \\{10,50,100,200\\}, shows that quadratic sampling growth nearly eliminates the observed performance gap across dimensions on the tested problem. This indicates that the theoretical sufficient batch sizes can be conservative in practice.

We additionally establish a worst-case lower bound of Ω(d2ϵ−4)\Omega(d^2\epsilon^{-4}) total samples for a constructed family of smooth performative optimization problems (see our response to Reviewer HFsr). Although this bound does not match PTRO's upper bound, it demonstrates that at least quadratic dimension dependence is unavoidable for this family, indicating that part of the sample-complexity dependence is intrinsic to the problem.

3. Initialization condition in Theorem 1

We agree that the current statement of Theorem 1, which allows arbitrary α0>0\alpha_0>0, does not account for the potentially large number of iterations required to increase an arbitrarily small initial trust-region radius. We would like to clarify that our intended iteration-counting analysis assumes (α0≥αˉ\alpha_0\ge\bar\alpha), but this initialization condition was inadvertently omitted from the theorem statement.

This intended initialization is reflected in Appendix D.4. In particular, the initialization term

\frac{u}{u+1} \max\left\\{ 0, \left\lceil \frac{\ln(\alpha_0/\bar{\alpha})} {\ln(1/\gamma_{\mathrm{dec}})} \right\rceil \right\\}.$$ accounts for the number of radius contractions from an initial radius at or above $\bar\alpha$. We will explicitly add ($\alpha_0\ge\bar\alpha$) to the assumptions of Theorem 1 and clarify the corresponding initialization argument in Appendix D.4. Under this condition, the reviewer's counterexample with ($\alpha_0 < \bar{\alpha}$) does not apply, and the convergence guarantee for the intended initialization regime remains unchanged. We appreciate the reviewer for identifying this omission and helping us improve the precision of our theoretical guarantee. We hope that these clarifications, additional theoretical results, and new experimental evidence address the reviewer's concerns, and we would be grateful if the reviewer could reconsider the assessment in light of these updates.

Table 1: Strategic classification benchmark of Hikima et al. (2025) at three sample budgets.

NS and HS denote GZO-NS and GZO-HS

The 10k budget corresponds to the original setting.

All methods are tuned using equal-sized hyperparameter grids on held-out seeds. Results are averaged over 20 runs.

Bold values indicate the best mean.

Train loss (↓)

τ\tau10k NS10k HS10k PTRO20k NS20k HS20k PTRO40k NS40k HS40k PTRO
0.50.9220.6450.6810.8570.6200.6140.6300.6070.602
10.6600.6260.6650.8150.6070.6060.6200.6020.597
20.6750.6180.6490.6460.6090.6040.6140.6020.595
40.6760.6130.6410.6370.6050.6030.6110.6210.594
80.6820.6120.6370.6260.6050.6030.6090.6240.594

Test AUC (↑)

τ\tau10k NS10k HS10k PTRO20k NS20k HS20k PTRO40k NS40k HS40k PTRO
0.50.7250.7440.7270.7350.7490.7540.7460.7540.757
10.7310.7420.7270.7520.7550.7560.7500.7560.761
20.7430.7500.7310.7540.7550.7580.7520.7590.764
40.7470.7540.7360.7570.7580.7570.7560.7530.765
80.7500.7540.7380.7550.7580.7570.7590.7530.765
Reviewer_6qTvOpenReview ↗

Concerns Addressed and Score Updated

Thank you for the detailed response and clarifications. My main concern has been satisfactorily addressed, and I have updated my score accordingly.

Reviewer_3knmOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduces Performative Trust-Region Optimization (PTRO) to minimize performative risk without explicitly modeling as most literature did.

The key intuition is to decouple the problem: it evaluates the direct loss change using data from the current distribution, while estimating the indirect population shift locally via finite-difference perturbations. A trust-region mechanism then adaptively tunes step sizes and rejects unreliable trial steps.

The authors establish high-probability convergence to an ϵ\epsilon-stationary point in O(ϵ−2)\mathcal{O}(\epsilon^{-2}) iterations. Experiments on credit scoring show that while parametric baselines win when their response assumptions hold, PTRO is more robust with model misspecification.

Critical strengths
  1. Decoupling the known loss evaluation from the unknown population shift makes sese. It avoids the common practice (or, trap) of making fragile parametric assumptions.

  2. The high-probability convergence guarantees are technically sound.

Critical weaknesses
  1. Using coordinate-wise finite differences requires O(d) deployments every iteration, which scales poorly as the feature dimension grows. In practice, it may be hard to say it's a good efficient practice to deploy perturbed models in real time to live users?

  2. The empirical results rely on a single credit-scoring dataset with synthetic response functions (and the results therein are not persuasive either). Testing on a broader set of environments would make the claims much more convincing.

Questions for authors
  1. When a candidate step is rejected by the trust-region test, a batch of samples from that suboptimal deployment has already been drawn, which might lead to bad consequences in deployed in practice. How can this negative real-world impact be mitigated in safety-critical settings?

  2. Is it possible to incorporate off-policy replay samples or importance weighting to improve sample efficiency without breaking the current theoretical guarantees?

  3. Have you thought about experiments on more practical datasets?

2 comments

We thank the reviewer for recognizing the value of decoupling direct loss evaluation from population-response estimation, as well as the soundness of our convergence analysis. We appreciate the concerns regarding deployment scalability, empirical generalizability, and the practical consequences of deployments. We address them below.

1.Dimension dependence is partly intrinsic to the problem

(1)Dimension dependence is not just a consequence of using coordinate-wise finite differences.

Identifying an arbitrary dd-dimensional response gradient requires dimension-dependent deployment information.

For example, consider an unknown unit vector θ∈Rd\theta \in \mathbb R^d and $D_\theta(x)=\delta_{\theta^\top x}, \qquad \ell(z;x)=\frac12|x|^2-z.$

Then $ PR(x)=\frac12|x|^2-\theta^\top x, \qquad \nabla PR(x)=x-\theta. $

Each deployment reveals only the scalar θ⊤x\theta^\top x. Then for k<dk<d deployments, there exists a unit vector θ\theta orthogonal to all deployed decisions, making these observations consistent. Consequently, every deployed point satisfies $ |\nabla PR(x)|^2 =|x-\theta|^2 =|x|^2+1\ge 1. $

Thus, without additional structure, fewer than dd deployments cannot guarantee visiting an ϵ\epsilon-stationary point for ϵ<1\epsilon<1.

Moreover, randomized estimators may reduce per-iteration deployments, but do not automatically eliminate dimension dependence without additional structure or information is available.

(2) Our main contribution is a trust-region framework for performative optimization rather than a particular gradient estimator.

We adopt coordinate-wise finite differences as a choice under our current assumptions, while alternative estimators may be more suitable under different structural or statistical assumptions, provided they satisfy the required gradient-accuracy conditions.

2. Controlled experiments isolate response misspecification, and we are expanding the evaluation to assess generalizability.

We thank the reviewer for this constructive suggestion. We agree that evaluating PTRO on a broader range of datasets and application domains would provide stronger evidence of its practical generalizability.

(1) Controlled synthetic population-response in our original experiments serves a specific purpose.

These controlled experiments are designed to isolate specific challenges in performative optimization and identify when avoiding explicit response modeling is beneficial. It allows us to systematically vary heterogeneity, nonlinearity, and model misspecification and keeping the underlying data and evaluation conditions comparable across methods.

Main experiment (Section 6.1): Under a homogeneous linear response, where the parametric assumptions are correctly specified, model-based methods can be more sample-efficient than PTRO. In contrast, under heterogeneous responses, PTRO achieves better stationarity than the response-model-based baselines under the same sample budget.

Heterogeneity study (Appendix E.2): This experiment isolates the effect of population heterogeneity by varying the mixture proportion. PTRO maintains stable stationarity and favorable sample efficiency across the full range of mixture proportions, while response-model-based methods become less reliable as heterogeneity increases.

(2) Our results highlight a trade-off rather than universal superiority

Correctly specified parametric models can offer better sample efficiency, whereas PTRO is more robust when those models are misspecified. Our experiments support this comparison under the tested response mechanisms, rather than establishing universal superiority across application domains.

(3) We are extending the evaluation . To address the reviewer's concern about empirical scope, we have extended our experiments to the larger Folktables ACSIncome dataset. These experiments are updated into the revised manuscript.

Q1. Deployment risks can be mitigated through bounded exploration and additional safety safeguards.

We agree that rejecting a trial step does not undo its effect on users exposed to that deployment. This is an important practical concern in deployment-based optimization.

PTRO's trust-region mechanism provides control over exploratory updates. PTRO restricts each trial decision to ∣xk+−xk∣≤αk|x_k^+-x_k|\leq\alpha_k, limiting the magnitude of possible deterioration rather than allowing unrestricted exploratory changes.

When the loss function is uniformly LℓL_\ell-Lipschitz in the decision variable, then for any fixed zz,

\le L_\ell|x_k^+-x_k| \le L_\ell\alpha_k.$$ Thus, the trust-region radius directly bounds the change in individual loss associated with a trial decision Moreover, rejected steps are not adopted, and the trust-region radius is reduced, limiting subsequent exploration. For safety-critical applications, additional constraints could restrict trial decisions to a certified safe region or require safety checks before deployment. Such safeguards would complement PTRO's acceptance mechanism by screening potentially harmful decisions before users are exposed. We will clarify these practical safeguards and limitations in the revised manuscript. **Q2. Historical data reuse is promising, but preserving theoretical guarantees requires additional assumptions.** We appreciate this suggestion and agree that reusing historical observations could reduce the need for repeated deployments. Off-policy replay. As discussed in Section 5.3, the decoupled-risk formulation may allow the distribution-dependent risk component to be estimated through local interpolation or regression using nearby historical deployments. This could reduce the need for fresh coordinate-wise perturbations. But establishing convergence guarantees would require additional assumptions on the coverage and geometry of historical deployment points, together with control of approximation and estimation errors. Importance weighting. Samples collected under a previous deployment $x'$ could be reused to estimate expectations under a new deployment $x$ by weighting them with $w(z)=\frac{dD(x)}{dD(x')}(z)$, the density ratio between the target distribution $D(x)$ and the historical distribution $D(x')$. But this requires $D(x)$ to be absolutely continuous with respect to $D(x')$ and the importance weights to have controlled variance. Both approaches offer potential ways to trade additional statistical assumptions for reduced deployment costs. Establishing such guarantees is an interesting direction for future work. **Q3. We are adding experiments on a larger real-world dataset.** As mentioned above, we did additional experiments and updated the result into the revised manuscript.. We hope these clarifications, additional experimental efforts, and discussion of practical limitations help address the reviewer's concerns. We would appreciate it if the reviewer could reconsider their assessment in light of these responses and forthcoming results.

Comments on the paper

1 comment

We sincerely thank the reviewers and AC for their time and consideration.

During the rebuttal, we have made several improvements:

  • Theory: Tightened the sample-complexity bound, established a new worst-case lower bound, and clarified the initialization condition in Theorem 1.
  • Experiments: Added evaluations on new dataset and comparisons with recent guided zeroth-order methods.
  • Manuscript: Revised the manuscript accordingly to incorporate these results and address presentation issues.

We appreciate the reviewers' thoughtful feedback, which has helped us improve the paper.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.