acceptodds
Under review as a conference paper at ICLR 2027

AdaBiO: Stochastic Bilevel Optimization For Non-Convex Performative Risk

Abstract

While stochastic bilevel optimization provides a framework for nested learning problems, most existing methods assume that the data distributions at both levels remain fixed throughout the optimization process. This assumption can fail in performative settings, where the deployed decisions change the environment and thereby affect future data distributions. We study stochastic bilevel optimization for nonconvex performative risk when both the upper-level (UL) and lower-level (LL) distributions are decision-dependent and unknown. Unlike existing bilevel performative methods that primarily target performatively stable points, our goal is to directly optimize the performative risk and find its stationary point. We propose AdaBiO, which iteratively estimates the two unknown distribution maps using explored samples. We prove that AdaBiO converges to an -stationary point with computational complexity and sample complexity. Experiments on strategic credit classification demonstrate that AdaBiO achieves lower performative risk than both non-performative stocBiO and a bilevel performatively stable point baseline. Moreover, its performance approaches that of AdaBiO with known distribution maps.

Primary area:
optimization
Keywords:
Bilevel Optimization, Performative Risk

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_qZnNOpenReview ↗
Rating
3(+2)
Confidence
3
Informativeness
2(+1)
Presentation
2
Soundness
3(+1)
Read review
Paper summary

This paper considers performative bilevel optimization problems where the inner distribution depends on the outer variable and the outer distribution depends on the inner variable. The authors assume these distributions evolve linearly with respect to these variables and propose AdaBiO, an algorithm that jointly solves the problem, leveraging approximate implicit differentiation, and learns the linear map describing the distributions' evolution. They provide a complexity result of O(ϵ−2)\mathcal{O}(\epsilon^{-2}). A numerical illustration with the Give Me Some Credit dataset is provided.

Critical strengths
  • S1: Unlike prior bilevel performative work, which targets performatively stable points, the paper directly targets stationary points of the performative risk, which is novel in the bilevel setting to my knowledge.
Critical weaknesses
  • W1 (Motivation and novelty): While performative learning and bilevel optimization are each well motivated, the specific problem (1a-b) is not. Why does D\mathcal{D} depend only on xx, and C\mathcal{C} only on y∗(x)y^*(x)? Which practical situation does this model? The experiment does not clarify this either. Moreover, under Assumption 1 the problem reduces to a classical bilevel problem with F(x,y)=Eξ0[f(x,y,ξ0+A(c)y)]F(x, y) = \mathbb{E}_{\xi^0}[f(x, y, \xi^0 + A^{(c)}y)] and G(x,y)=Eζ0[g(x,y,ζ0+A(d)x)]G(x, y) = \mathbb{E}_{\zeta^0}[g(x, y, \zeta^0 + A^{(d)}x)]. AdaBiO is then stocBiO on (F,G)(F, G) with A(c),A(d)A^{(c)}, A^{(d)} replaced by least-squares estimates, as in [1].

  • W2 (The guarantees implicitly require bounded iterates): Assumption 4 requires ∇ξf\nabla_\xi f and ∇ζy2g\nabla^2_{\zeta y} g to be bounded uniformly over all parameters and samples. This does not hold as soon as the data interact multiplicatively with trainable parameters (linear models, GLMs, or any network whose first layer is linear in the input), since ∇ξf\nabla_\xi f then scales with the parameter norm. Moreover, the final sample complexity depends on max⁡0≤r<R∥xr∥2\max_{0\leq r< R}\lVert x_r\rVert^2 and max⁡0≤r<R∥yr,K∥2\max_{0\leq r< R}\lVert y_{r,K}\rVert^2. A complexity bound should not depend on the iterates of the algorithm. Note that [1] avoids both issues by restricting the parameters to a ball.

[1] John P. Miller, Juan C. Perdomo, and Tijana Zrnic. Outside the echo chamber: Optimizing the performative risk. ICML 2021

Questions for authors
  • Q1: Is there a concrete example for which the proposed formulation makes sense?
  • Q2: Under Assumption 1, the problem can be rewritten as a standard bilevel problem with fixed distributions (see W1). Beyond combining stocBiO with the estimation procedure of [1], what are the specific technical challenges of this setting?

[1] John P. Miller, Juan C. Perdomo, and Tijana Zrnic. Outside the echo chamber: Optimizing the performative risk. ICML 2021

4 comments

We thank the reviewer for the careful reading and important questions. We have uploaded a revised manuscript, with changes highlighted in blue. We address the two weaknesses and related questions below.

1. Motivation and a concrete example (W1 and Q1).

Our formulation follows the bilevel performative learning framework introduced by [2]. As discussed in [2], meta-learning provides a natural motivation for this problem: the UL model learns a shared initialization, while the LL model adapts it to individual tasks. When model deployment changes the data distributions, performative effects can arise at both levels.

Consider financial markets as a practical example. A financial institution may develop a shared investment model xx that is used across different trading desks. Deploying this model influences their initial trading decisions and the resulting market data, such as transaction prices and trading volumes. The data collected for adapting the model to a particular trading desk therefore depend on xx, giving the LL distribution D(x)\mathcal{D}(x). Based on these data, the LL problem learns an adapted trading model y⋆(x)y^{\star}(x). When this adapted model is deployed, its trading decisions can further affect market prices, liquidity, and transaction costs. Consequently, the data used to evaluate its performance follow the UL distribution C(y⋆(x))\mathcal{C}(y^{\star}(x)).

Thus, the two distribution dependencies correspond to different stages of model deployment: the shared model affects the data used for LL adaptation, while the adapted model affects the data used for UL evaluation. This explains the structure of Problem (1).

Furthermore, following [2], we have added a meta-strategic classification experiment in Section 5, Fig. 3 of the revised manuscript. This experiment considers the same type of coupled decision-dependent distributions and provides additional empirical support for the proposed framework.

2. Technical challenges beyond standard bilevel optimization (W1 and Q2).

We agree with the reviewer that if both distribution matrices are known, the location-family model can be rewritten as a stochastic bilevel problem over fixed base distributions. However, when A(d)A^{(d)} and A(c)A^{(c)} are unknown, the required transformed gradients cannot be evaluated directly: the performative hypergradient contains distributional derivatives involving both matrices, Eqs. (4)–(5).

Our contribution is to estimate both maps online while optimizing the bilevel problem and establish convergence with their estimation errors. The LL map error affects both the LL updates and the tracking of y⋆(xr)y^{\star}(x_r); errors from both maps affect the hypergradient. These errors are coupled with stochastic gradient noise and the Neumann inverse-Hessian approximation. Proposition 1 bounds online map-estimation errors, Lemma 1 controls their effect on the performative hypergradient, and Lemma 2 controls LL solution tracking. Theorem 1 then establishes convergence to a stationary point of the performative risk, rather than the performatively stable point studied in [2]. Thus, the key contribution is the error analysis and convergence guarantee with two unknown coupled maps, not simply applying stocBiO with known matrices.

3. Boundedness and sample complexity (W2).

Bounded parameter domains are common in performative prediction, including [1,3]. Similarly, we can impose ∥x∥≤Rx\|x\|\leq R_x and ∥y∥≤Ry\|y\|\leq R_y to bound parameter-dependent gradients, with suitable conditions on the data. Our analysis considers unconstrained optimization under Assumptions 1–4, and a constrained extension would use projected updates and a modified convergence analysis.

Theorem 1 also covers bounded iterates: if ∥xr∥≤Rx\|x_r\|\leq R_x and ∥yr,K∥≤Ry\|y_{r,K}\|\leq R_y uniformly, with bounds independent of ϵ\epsilon, the additional sample complexity for each distribution map becomes O~(LΦϵ−1)\widetilde O(L_\Phi\epsilon^{-1}). Thus, the iterate dependence is absorbed into constants.

We also added experiments beyond our theoretical assumptions. Appendix B.3.5 (Figs. 9–10) tests nonlinear shifts beyond the linear location-family model; Appendix B.3.7 (Fig. 12) tests a trainable ReLU MLP, which violates global smoothness and does not guarantee bounded gradients. AdaBiO remains effective in both settings, supporting its robustness beyond our theoretical assumptions.

We hope these explanations address your concerns. If you find that our response resolves your concerns, we would kindly ask you to reconsider your rating. We welcome further questions and would be happy to clarify them.

[1] Miller et al., "Outside the Echo Chamber: Optimizing the Performative Risk," ICML, 2021.

[2] Lu, "Bilevel Optimization with Coupled Decision-Dependent Distributions," ICML, 2023.

[3] Yan et al., "Zero-Regret Performative Prediction Under Inequality Constraints," NeurIPS, 2023.

Additional clarification on W2.

We would like to further clarify that, instead of imposing bounded feasible sets and introducing projection, we can directly adopt a bounded-iterate assumption, i.e., ∥xr∥≤Rx\|x_r\|\le R_x and ∥yr,k∥≤Ry\|y_{r,k}\|\le R_y for all iterations, with constants independent of ϵ\epsilon. Such an assumption is common in stochastic nonconvex optimization, as explicitly noted by Na and Mahoney [4, Assumption 4.1]. Under this additional assumption and our existing regularity conditions, Theorem 1 directly yields O~(ϵ−1)\widetilde O(\epsilon^{-1}) additional sample complexity for each distribution map, without modifying the algorithm or its convergence proof.

We hope this clarification can resolve your concerns.

[4] Na and Mahoney, "Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming," JMLR, 2025.

I thank the authors for their response, which addresses my concerns about the assumptions and the motivation. Given their answer and the additional experimental work to address the other reviewers’ concerns, I have updated my score.

We sincerely thank you for your kindness and thoughtful reconsideration. Your constructive feedback has greatly helped improve our work.

Reviewer_qQvjOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper studies stochastic bilevel optimization in which the data distributions at both levels depend on the decisions and are unknown. The authors propose AdaBiO, which estimates the distribution maps online and incorporates them into the bilevel hypergradient. They establish convergence guarantees for finding a stationary point of the nonconvex performative risk and evaluate the method on a strategic credit classification task.

Critical strengths
  1. The paper addresses an interesting and relatively unexplored problem: directly finding stationary points of bilevel performative risk rather than performatively stable points. The proposed algorithm provides useful theoretical guarantees, including O(ϵ−2)O(\epsilon^{-2}) stochastic computational complexity and an additional O~(ϵ−1)\widetilde{O}(\epsilon^{-1}) sample complexity for distribution-map estimation under the stated conditions.
  2. The theoretical analysis is detailed and well structured. The derivation of the performative hypergradient and the convergence analysis appear sound, and I did not identify any clear mathematical errors under the stated assumptions.
  3. The experimental results are promising. AdaBiO achieves lower performative losses than the non-oracle baselines in fewer outer iterations and performs comparably to AdaBiO-true, which has access to the true distribution maps.
Critical weaknesses
  1. My main concern is that the experiments are limited to a single strategic credit classification task with linear location-family distribution shifts. Evaluating AdaBiO on other bilevel performative tasks, such as the meta-strategic learning setting in [1], would strengthen the empirical evaluation. Testing nonlinear or misspecified distribution shifts would also help assess the robustness of the method beyond its theoretical assumptions.
  2. The comparisons could be more informative in terms of sample budgets. Bi-SGD uses only one lower-level update per outer iteration, whereas AdaBiO uses 100. Although runtime comparisons are provided, results based on total sample usage or stochastic oracle calls would be useful.
  3. Despite the nonconvex bilevel setting, the experiments only optimize 16-dimensional linear classifiers on top of a frozen encoder. Evaluating more complex trainable models would provide stronger empirical support.
  4. The paper lacks detailed ablation studies. In particular, it would be useful to examine the individual UL and LL correction terms, sensitivity to the number of lower-level updates KK, and variants in which only one distribution map is estimated.
  5. A few additional points require clarification. The O(ϵ−1)O(\epsilon^{-1}) sample complexity stated in the abstract refers only to distribution-map estimation. Furthermore, the equality ζ(2)−ζ(1)=A(d)xexp\zeta^{(2)}-\zeta^{(1)}=A^{(d)}x^{exp} on page 3 omits the noise difference between independent samples, although this is handled correctly in the appendix. Finally, the experimental setup does not appear to satisfy all the theoretical assumptions. For example, the quadratic regularizer in the UL objective leads to an unbounded gradient with respect to xx, contrary to Assumption 4.

[1] S. Lu. "Bilevel Optimization with Coupled Decision-Dependent Distributions." International Conference on Machine Learning (ICML), 2023.

Questions for authors
  1. Could the authors evaluate AdaBiO on another bilevel performative task, such as the meta-strategic learning setting in Lu (2023)? Could they also test its robustness under nonlinear or misspecified distribution shifts?
  2. Could the authors report comparisons based on total sample usage or stochastic oracle calls, particularly given the different lower-level update budgets?
  3. Have the authors considered evaluating AdaBiO with more complex trainable models rather than a frozen encoder and linear classifiers?
  4. Could the authors provide ablation studies examining the individual UL and LL correction terms, the number of lower-level updates, and the estimation of each distribution map separately?
5 comments

We thank the reviewer for the detailed comments. We have uploaded a revised manuscript with additional experiments. The changes are highlighted in blue. We respond below.

1. Additional task and nonlinear distribution shifts (Weakness 1 and Q1).

We added meta-strategic classification in Section 5, Fig. 3, following the bilevel performative learning task in [1]. We construct five Amazon Reviews classification tasks and compare all four methods with 100 LL updates per outer iteration. AdaBiO achieves small stationarity gaps and better meta-training and meta-testing losses and accuracies than the baselines, with results close to AdaBiO-true.

We also test nonlinear distribution shifts in Appendix B.3.5, Figs. 9–10 by adding quadratic terms to both distribution maps:

ζ=ζ(0)+A(d)x+B(d)(x⊙x)\zeta=\zeta^{(0)}+A^{(d)}x+B^{(d)}(x\odot x) and ξ=ξ(0)+A(c)y+B(c)(y⊙y)\xi=\xi^{(0)}+A^{(c)}y+B^{(c)}(y\odot y).

We consider weak and strong quadratic settings, with the spectral norms of the quadratic matrices set to 0.5 and 4 times those of the corresponding linear matrices. AdaBiO continues to estimate linear maps, so its model is misspecified. Under weak nonlinearity, its results remain close to the nonlinear oracle AdaBiO-true. Under strong nonlinearity, a larger gap appears, but AdaBiO still achieves lower losses and stationarity gaps than stocBiO and Bi-SGD. These tests are beyond our theoretical assumptions.

2. Sample usage and stochastic oracle calls (Weakness 2 and Q2).

We updated the main GMSC comparisons so that all methods use K=100K=100 LL updates in Section 4, Figs. 1–2. We further added Appendix B.3.6, Fig. 11, which compares all four methods under both K=1K=1 and K=100K=100. We plot training and test losses against cumulative samples and sample-weighted derivative-oracle calls. Total samples also include distribution-map exploration. Under comparable budgets, AdaBiO achieves lower losses than stocBiO and Bi-SGD and performs close to AdaBiO-true. With K=1K=1, more UL iterations can be performed within the same budget.

3. More complex trainable model (Weakness 3 and Q3).

In Appendix B.3.7, Fig. 12, we replace the frozen encoder with a fully trainable MLP and jointly optimize its parameters and the classifier, giving 896 trainable UL parameters instead of 16. The LL problem remains strongly convex. AdaBiO maintains small stationarity gaps and low training and test losses, with performance close to AdaBiO-true and Bi-SGD.

4. Ablation studies (Weakness 4 and Q4).

We added three ablation studies in Appendix B.3.8, Figs. 13–15:

  • Fig. 13: UL correction only, LL correction only, and no correction. The UL correction has a larger effect in our GMSC setting.
  • Fig. 14: K∈{1,10,50,100}K\in\{1,10,50,100\}. Final losses and stationarity gaps are similar across these settings.
  • Fig. 15: Estimate only the UL map or only the LL map, while using the true matrix for the other. Both variants and full AdaBiO perform close to AdaBiO-true.

5. Sample complexity, noise difference, and assumptions (Weakness 5).

We corrected two points in the revised manuscript. First, the Abstract now states clearly that the O(ϵ−1)O(\epsilon^{-1}) additional sample complexity is for the distribution-map estimation, not the total training cost. Second, Section 2.1 (page 3) now includes the base-noise difference in ζ(2)−ζ(1)\zeta^{(2)}-\zeta^{(1)}, consistently with the appendix.

Regarding Assumption 4, our current theoretical analysis considers unconstrained bilevel optimization. The bounded-gradient issue raised by the reviewer can be addressed by restricting the UL and LL variables to bounded feasible sets, as commonly considered in related performative prediction studies [2,3]. Specifically, we can impose ∣x∣≤Rx|x|\leq R_x and ∣y∣≤Ry|y|\leq R_y and introduce projection steps to keep the iterates within these sets. Under suitable regularity conditions on the data-dependent derivatives, this ensures that parameter-dependent gradient terms, including λxx\lambda_x x from the quadratic regularizer, are uniformly bounded. Moreover, the trajectory-dependent terms in Theorem 1 become bounded constants, giving O~(ϵ−1)\widetilde O(\epsilon^{-1}) additional sample complexity for distribution-map estimation. Thus, the bounded-domain formulation provides a standard way to address this issue. Our present analysis focuses on the unconstrained setting, while a constrained extension would require corresponding projected updates and a projected-stationarity analysis.

We hope these revisions address your concerns. If you find that our response and additional results resolve your concerns, we would kindly ask you to reconsider your rating. We welcome any further questions or concerns and would be happy to clarify them.

[1] S. Lu. "Bilevel Optimization with Coupled Decision-Dependent Distributions." ICML, 2023.

[2] W. Yan et al. "Zero-regret performative prediction under inequality constraints." NeurIPS, 2023.

[3] J. Miller et al. "Outside the echo chamber: Optimizing the performative risk." ICML 2021.

Reviewer_qQvjOpenReview ↗

Follow-up on Remaining Theoretical Concerns

Thank you for the detailed rebuttal and the substantial additional experiments. I appreciate the authors' efforts to address my comments. My original concerns have been satisfactorily resolved, particularly regarding the experimental comparisons, sample budgets, and ablation studies.

However, after reading the other reviewers' comments and the corresponding author responses, I have two remaining concerns that I would appreciate further clarification on.

1. Bounded gradients, bounded iterates, and sample complexity.

As noted by another reviewer, Assumption 4 requires uniformly bounded gradients, while the quadratic regularizer in the experimental UL objective yields ∇xf=λxx\nabla_x f=\lambda_x x, which is unbounded over the unconstrained domain.

The rebuttal suggests restricting xx and yy to bounded feasible sets and introducing projected updates. However, as the authors acknowledge, this would require modifying the algorithm and establishing a corresponding projected-stationarity analysis.

Moreover, the additional distribution-map estimation complexity depends on quantities such as max⁡r<R∥xr∥2\max_{r<R}\|x_r\|^2 and max⁡r<R∥yr,K∥2\max_{r<R}\|y_{r,K}\|^2. To obtain the claimed O~(ε−1)\widetilde O(\varepsilon^{-1}) dependence with constants independent of ε\varepsilon, these quantities need to be controlled appropriately.

Could the authors clarify whether the existing unconstrained assumptions and analysis imply such bounds, or whether additional assumptions are necessary? In particular, can the stated sample-complexity guarantee be established without relying on unproven boundedness of the iterates?

2. Novelty and the benefit of online distribution-map estimation.

I also find the observation about the reduction to standard stochastic bilevel optimization under known location-family matrices important. I understand that estimating both unknown matrices and controlling the resulting errors is a meaningful contribution.

However, the new offline-versus-online comparison in Figure 6 shows nearly identical performance under fixed distribution maps, which is precisely the setting covered by the theoretical analysis. The advantage of online estimation becomes apparent in Figure 7, where the distribution maps change over time, but this setting is outside the current theoretical framework.

Could the authors clarify what specific advantage the online estimation procedure offers over estimating the fixed matrices before optimization, under comparable total exploration budgets and within the assumptions of the paper? Is the primary contribution the joint estimation-and-optimization convergence analysis rather than an efficiency improvement over a two-stage approach?

Overall, the rebuttal has significantly improved my assessment of the paper, and my original concerns have been addressed. These remaining questions arise from considering the other reviewers' observations. If the authors can satisfactorily clarify these points, I would be happy to increase my score.

We sincerely thank the reviewer for the positive feedback and further questions.

1. Boundedness and sample complexity.

We agree that Assumptions 1–4 do not guarantee uniformly bounded iterates, so an additional assumption is needed for the simplified sample complexity. As noted by Na and Mahoney [4, Assumption 4.1], bounded iterates are commonly assumed in stochastic nonlinear nonconvex optimization.

Following this literature, we can assume ∥xr∥≤Rx\|x_r\|\le R_x and ∥yr,k∥≤Ry\|y_{r,k}\|\le R_y for all iterations, where RxR_x and RyR_y are independent of ϵ\epsilon. Under this additional assumption and the required regularity conditions, Theorem 1 directly yields O~(ϵ−1)\widetilde O(\epsilon^{-1}) additional sample complexity for each distribution map. Thus, no projection or modification of the original convergence analysis is needed to obtain this conditional result.

2. Benefits of online distribution-map estimation.

We agree that our main theoretical contribution is the joint estimation-and-optimization convergence analysis, rather than improved sample efficiency over offline estimation under fixed distribution maps. As Fig. 6 shows, both methods achieve similar performance with equal exploration budgets.

However, offline estimation requires collecting all exploration samples before model optimization begins, whereas online estimation allows the model to be updated while data are progressively collected. This is particularly useful when data arrive over time and optimization must proceed without waiting for the full exploration dataset.

We hope these clarifications resolve your remaining concerns.

[4] Na and Mahoney, "Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming," JMLR, 2025.

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

This paper studies stochastic bilevel performative-risk minimization, where the lower-level data distribution depends on the upper-level decision and the upper-level distribution depends on the lower-level optimal response. Unlike approaches targeting performatively stable points, the paper aims to find a stationary point of the resulting nonconvex performative objective. Under linear location-family distribution maps and a strongly convex lower-level objective, the authors derive a hypergradient containing distributional derivative terms at both levels. The proposed AdaBiO algorithm combines cumulative online least-squares estimation of the unknown response matrices, warm-started lower-level SGD, and a stochastic Neumann approximation of the inverse-Hessian-vector product. The analysis controls distribution-estimation, lower-level tracking, and hypergradient errors, yielding an expected squared-gradient stationarity guarantee with O(ϵ−2)\mathcal{O}(\epsilon^{-2}) dependence in the computational oracle counts. Additional map-estimation observations have a trajectory-dependent O~(ϵ−1)\widetilde{\mathcal{O}}(\epsilon^{-1}). Experiments on credit classification with simulated linear feature responses compare AdaBiO against stocBiO, Bi-SGD, and a true-map variant.

Critical strengths

• This paper targets a meaningful problem that a fixed point of retraining under the current distributions need not be stationary for the risk that accounts for deployment-induced distribution changes. Equations (4)-(5) incorporate both the effect of the lower-level distribution on the optimal response and the effect of that response on the upper-level evaluation distribution. This gives a coherent optimization objective and an implementable hypergradient under the stated structural assumptions. • Their analysis does more than assume access to accurate distribution derivatives. It accounts for the dependence between the optimization trajectory and the learned response matrices through trajectory-weighted moment bounds, and combines these errors with lower-level tracking and stochastic Neumann approximation. Reusing cumulative map estimates is also a sensible way to avoid restarting identification at every iteration. The comparison with AdaBiO-true provides useful empirical evidence that estimation error need not prevent effective optimization in the tested setting.

Critical weaknesses

The empirical evaluation does not sufficiently isolate the new components or establish that the reported stationarity metric measures the theoretical target. Under known location matrices, the problem can be reparameterized as a fixed-base-distribution stochastic bilevel problem. Consequently, learning the unknown maps and incorporating the resulting distributional derivatives are central to the added contribution. However, the experiments do not directly isolate these components. AdaBiO uses 100 lower-level updates per outer iteration, whereas Bi-SGD uses one. A matched-update ablation would provide more direct support for the interpretation in Section 4. A comparison against estimating the fixed response matrices before optimization would also help establish the value of the online scheme. Moreover, Figure 1(a) does not specify how the stationarity gap is computed, including whether the lower-level response is independently solved to sufficient accuracy and whether the true performative hypergradient is evaluated. I think this distinction matters because a small estimated update at yr,Ky_{r,K} does not necessarily imply a small ∇Φ(xr)\nabla \Phi(x_r). The lack of reported independent repetitions or uncertainty estimates further limits how strongly the displayed curves support the empirical conclusions.

Questions for authors

• How is the stationarity gap in Figure 1(a) computed? Is it the norm or squared norm of the true performative hypergradient, is y∗(xr)y^*(x_{r}) independently approximated to a specified tolerance, and are the true response matrices used for this evaluation? • Do the gains in Section 4 persist when the methods use matched lower-level update budgets, with the distributional derivative terms being the principal difference? Additionally, since the matrices A(d)A^{(d)} and A(c)A^{(c)} are fixed throughout optimization, is there evidence comparing cumulative online estimation with estimating the fixed response matrices before optimization under a matched exploration budget? For example, using the same total number of samples, one could estimate both matrices A(d)A^{(d)} and A(c)A^{(c)} before optimization and then keep them fixed during the subsequent bilevel updates. This comparison would help clarify the specific advantage of estimating the distribution map online rather than beforehand.

3 comments

We thank the reviewer for the constructive comments on our work. We have conducted additional experiments and uploaded a revised manuscript. All changes are highlighted in blue in the revised manuscript. We address the concerns as follows.

1. Matched LL updates and distributional correction terms (Weakness 1 and Q2).

We agree that matching the number of LL updates is important for a fair comparison. We have updated the main experiments so that stocBiO, Bi-SGD, AdaBiO, and AdaBiO-true all use K=100K=100 LL updates per outer iteration. The updated results are presented in Section 4, Figs. 1–2, with settings in Appendix B.2. AdaBiO continues to achieve lower training and test losses than the baselines under matched LL update budgets.

We also added a study of the distributional derivative terms in Appendix B.3.8, Fig. 13. We compare AdaBiO with variants using only the UL correction, only the LL correction, or neither correction, while estimating both distribution maps. AdaBiO and the UL-correction-only variant achieve similar performance, whereas the other two variants have larger stationarity gaps and higher losses. Thus, the UL correction term has a larger effect in this experiment.

In Fig. 15, we further compare variants that estimate only one distribution map while using the true matrix for the other. Estimating both maps online yields results close to those obtained using the true matrices.

2. Stationarity gap evaluation and independent runs (Weakness 2 and Q1).

In the original experiments, we evaluated the stationarity gap using the stochastic LL iterate yr,Ky_{r,K}. We have revised the evaluation to use an independently computed LL optimum y∗(xr)y^*(x_r). For each xrx_r, we solve the empirical LL problem using full-batch damped Newton's method with at most 30 iterations and a gradient residual tolerance of 10−610^{-6}. We then evaluate the squared norm of the performative hypergradient, ∥∇Φ(xr)∥2\|\nabla\Phi(x_r)\|^2, using the true distribution matrices.

The updated results appear in Section 4, Fig. 1(a), and the evaluation details are in Appendix B.2. Appendix B.3.4, Fig. 8 directly compares evaluation at y∗(xr)y^*(x_r) and yr,Ky_{r,K}. We also report mean curves with shaded standard deviations over ten independent runs.

3. Online versus offline distribution map estimation (Weakness 1 and Q2).

We added this comparison in Appendix B.3.3, Figs. 6–7. AdaBiO estimates both maps during optimization, whereas AdaBiO-offline estimates them before optimization and keeps them fixed. Both methods use the same total exploration budget for each map.

As shown in Fig. 6, the methods perform nearly identically when the matrices are fixed. This is expected, since both can estimate the matrices accurately with the same sample budget. Online estimation does not require a separate estimation stage before optimization.

We also test a changing environment: both matrices are replaced at outer iteration 200, with their spectral norms unchanged. Fig. 7 shows that AdaBiO adapts and achieves a smaller stationarity gap and lower losses than AdaBiO-offline, whose estimates remain fixed. This experiment is beyond our theoretical assumptions.

We hope these revisions address your concerns. If you find that our response and the new results resolve your concerns, we would kindly ask you to reconsider your rating. We welcome any further questions or concerns and would be happy to clarify them.

Dear Reviewer DY1q,

We sincerely thank you for your constructive comments. As the rebuttal period is approaching its end, we would be grateful if you could review our response and revised manuscript.

To address your concerns, we have conducted additional experiments with matched LL updates, improved the stationarity gap evaluation using independently computed LL optima, and added online-versus-offline distribution-map estimation comparisons. All revisions are highlighted in blue.

We hope these revisions address your concerns and would greatly appreciate your feedback and reconsideration of our work. Thank you for your time and consideration.

Dear Reviewer DY1q,

We apologize for this additional follow-up, as the rebuttal period is nearing its end. We have carefully addressed your concerns, and all revisions are highlighted in blue in the updated manuscript. We would be very grateful if you could review these revisions and reconsider your assessment. Thank you again for your valuable time.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.