acceptodds
Under review as a conference paper at ICLR 2027

Fully First-Order Methods for Contextual Stochastic Bilevel Optimization

10 views

Abstract

Contextual stochastic bilevel optimization (CSBO) is a new paradigm for decision making under uncertainty. It generalizes stochastic bilevel optimization (SBO) by integrating contextual information in the lower-level optimization problem and thus offers a stronger modeling capability. Nevertheless, owing to its semi-infinite nature, CSBO is extremely challenging from a computational perspective, hindering its real-world applications. Indeed, many algorithms designed for SBO are not applicable to CSBO. In this paper, we propose a double-loop fully first-order algorithm for solving CSBO and prove that both expected sample and gradient complexities of the algorithm are . To tackle the increasing number of inner-loop iterations, we further develop an accelerated version of our algorithm using the random truncated multilevel Monte Carlo technique and an adaptive stepsize for empirical stabilization. The accelerated algorithm enjoys the improved expected complexities of . These sample and gradient complexity orders match those of the corresponding Hessian-based algorithms for CSBO, while our algorithms use only first-order derivatives of . Numerical experiments on meta-learning and a contextual electricity pricing problem demonstrate the superiority of the proposed algorithms over existing Hessian-based and reduction-based algorithms in terms of both speed and solution quality.

Primary area:
optimization
Keywords:
Stochastic Bilevel Optimization, Contextual Optimization, First-Order Optimization, Nonconvex Optimization, Multilevel Monte Carlo

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_4gX2OpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers contextual stochastic bilevel optimization (CSBO) problems, which are bilevel problems where the inner problem depends on a context ξ\xi. The authors adapt the penalty-based fully first-order approach to that regime. At each outer iteration, two inner loops are run, one on the inner problem and one on the inner problem perturbed by the outer function with weight 1/λ1/\lambda, and their outputs are combined into a first-order estimate of the gradient of the bilevel objective with a bias in O(1/λ)\mathcal{O}(1/\lambda). They propose a vanilla algorithm with increasing λ\lambda provably reaching a complexity of O~(ϵ−6)\tilde{\mathcal{O}}(\epsilon^{-6}). They also propose a variant that decreases the complexity to O~(ϵ−4)\tilde{\mathcal{O}}(\epsilon^{-4}) by leveraging the random truncated multilevel Monte Carlo technique, along with a level-dependent stepsize to stabilize it in practice. Experiments on meta-learning and contextual electricity pricing are provided.

Critical strengths
  • S1: This paper proposes the first fully first-order method to solve CSBO problems that handles general context distributions.

  • S2: The authors show a complexity in O~(ϵ−4)\tilde{\mathcal{O}}(\epsilon^{-4}) matching the complexities of the AID-based methods of [1]. The theoretical analysis is sound. Even though the proposed algorithms are an adaptation of the methods of [1] with the penalty-based estimator of [2], the analysis of this combination is not straightforward. The authors handle the variance amplification caused by the penalty parameter λ\lambda growing with the RT-MLMC level by directly controlling the coupled displacement of the two inner loops (Lemma A.9).

[1] Yifan Hu, Jie Wang, Yao Xie, Andreas Krause, and Daniel Kuhn. Contextual Stochastic Bilevel Optimization. NeurIPS 2023

[2] Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert Nowak. A Fully First-Order Method for Stochastic Bilevel Optimization. ICML 2023

Critical weaknesses

None

Questions for authors
  • Q1: How does the final complexity depend on the inner condition number?
2 comments
AuthorsOpenReview ↗

Author Response to Reviewer 4gX2: Condition Number Dependence

We sincerely thank the reviewer for appreciating our work and for carefully examining how Lemma A.9 addresses the variance amplification caused by combining the penalty construction with RT-MLMC.

Question 1. How does complexity depend on the inner condition number?

Algorithm 2 matches the O~(ϵ−4)\widetilde{\mathcal O}(\epsilon^{-4}) expected sample and gradient complexity of Hessian-based CSBO methods using only first-order evaluations, for general context distributions. Let κg=ℓg,1/μg\kappa_g=\ell_{g,1}/\mu_g, with ℓg,1\ell_{g,1} and the remaining problem constants and damping parameters held fixed as μg\mu_g varies. Proposition A.1 in the new Appendix A.11 establishes the following sufficient bound:

O(κg9ϵ−4[1+log⁡(κg/ϵ)]2).O\left(\kappa_g^9\epsilon^{-4}[1+\log(\kappa_g/\epsilon)]^2\right).

The improved condition-number dependence follows from a refined analysis of the coupled inner trajectories. By exploiting samplewise strong convexity and common-sample coupling, we obtain a uniform bound on their displacement. Combined with a two-regime analysis of the inner SGD error, this yields an O(κg6)O(\kappa_g^6) coefficient in the multilevel correction's second-moment bound. The analysis also controls the bias introduced by the level-dependent stepsize. Together with the O(κg3)O(\kappa_g^3) smoothness bound for the upper-level objective (Lemma A.4), these estimates lead to the stated κg9\kappa_g^9 dependence. The detailed proof is provided in Appendix A.11.

Recent lower bounds for non-contextual stochastic bilevel optimization give Ω(κy9/2ϵ−4)\Omega(\kappa_y^{9/2}\epsilon^{-4}) [1], Ω(κy8ϵ−6)\Omega(\kappa_y^8\epsilon^{-6}) [2], and Ω(κ10ϵ−6)\Omega(\kappa^{10}\epsilon^{-6}) [3], under their respective model assumptions.

The last two are concurrent preprints appearing around and after our submission. Note that their oracle and regularity assumptions differ from ours. Specifically, these two concurrent bounds use black-box stochastic gradients with a fresh sample per query. Our accelerated estimator uses sampled-function (white-box) access, evaluating the same conditional sample at multiple points under samplewise smoothness and strong convexity, with every gradient evaluation counted. Although CSBO includes non-contextual SBO as a special case, and context-dependent inner solutions may introduce additional difficulty, these black-box lower bounds do not apply to our algorithms.

Our algorithmic design and analysis prioritize achieving the accelerated rate O(ϵ−4)O(\epsilon^{-4}) that is optimal with respect to the accuracy ϵ\epsilon, in the sense that the exponent matches the SBO lower bound [4]. Deriving sharp lower bounds under our contextual and oracle assumptions and designing algorithms with optimal κg\kappa_g dependence remain open.

References

[1] L. Chen, K. Ji, and J. Zhang. On the Condition Number Dependency in Bilevel Optimization. arXiv:2511.22331v4, 2026.

[2] Z. Gu, Q. Wu, and J. Yang. An Ω(κy8ϵ−6)\Omega(\kappa_y^8\epsilon^{-6}) Lower Bound for Stochastic NC--SC Bilevel Optimization with First-order Oracles. arXiv:2609.21905, first posted 18 September 2026.

[3] H. Zhang et al. Closing the Accuracy Gap in Stochastic First-Order Bilevel Optimization. arXiv:2610.03633v2, first posted 2 October 2026.

[4] L. Chen, J. Li, E. M. Chayti, and J. Zhang. Faster Gradient Methods for Highly-smooth Stochastic Bilevel Optimization. ICLR, 2026. Paper.

[5] Y. Hu, J. Wang, Y. Xie, A. Krause, and D. Kuhn. Contextual Stochastic Bilevel Optimization. Advances in Neural Information Processing Systems (NeurIPS), vol. 36, pp. 78412--78434, 2023.

[6] J. Kwon, D. Kwon, and H. Lyu. On the Complexity of First-Order Methods in Stochastic Bilevel Optimization. ICML, PMLR 235, pp. 25784--25811, 2024. Paper.

Thanks for the clarification.

Reviewer_avvXOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes first-order methods for contextual stochastic bilevel optimization, using a penalty formulation to estimate hypergradients without second-order derivatives. An accelerated variant uses randomized truncated multilevel Monte Carlo to match the complexity order of existing Hessian-based methods, with experiments on meta-learning and contextual electricity pricing.

Critical strengths
  • The proposed methods outperform existing methods in the reported experiments.
  • The paper provides theoretical performance guarantees for the proposed methods.
Critical weaknesses
  • The approach builds on existing techniques, including the method of Kwon et al. (2023) and RT-MLMC, making the contribution appear incremental.
  • The experimental evaluation is limited to two applications, and some assumptions and evaluation choices may limit their practical relevance.
Questions for authors
  • In what scenarios does RT-MLMC acceleration provide a substantial practical benefit?
  • In the meta-learning experiment, how is the learned upper-level variable intended to be used? To demonstrate meta-learning performance, should it not be evaluated through adaptation to previously unseen tasks or datasets?
  • In the electricity pricing application, how realistic is it to assume access to gradients of the lower-level objective? Evaluation under more realistic information-access assumptions would strengthen the practical relevance of the results.
  • In conventional bilevel optimization, the upper-level design variables already serve as fixed parameters of the lower-level problem. Beyond addressing the loss of warm-start guarantees across contexts, what new technical contributions does this paper make in extending existing penalty-based first-order methods to CSBO?
3 comments
AuthorsOpenReview ↗

Author Response to Reviewer avvX: Novelty and Practical Relevance

We thank the reviewer for the questions about novelty and practical relevance. Lemma A.9 is the main technical contribution enabling the accelerated first-order guarantee. It resolves the penalty amplification created by combining the two constructions. We explain this contribution first, followed by the additional ablation and robustness experiments.

Weakness 1. What is new in combining the penalty construction with RT-MLMC?

First-order CSBO and multilevel variance control.

To understand the novelties, we first clarify the new difficulties in our setting. First, unlike the SBO setting of Kwon et al. (2024a), our lower-level minimizer y⋆(x;ξ)y^\star(x;\xi) changes with both xx and the sampled context. Consequently, their solution-tracking argument does not directly extend to general CSBO without additional control of inter-context variation. Second, unlike the Hessian-based CSBO method of Hu et al. (2023b), we use only first-order derivatives. This introduces a penalty parameter λn\lambda_n that grows with the multilevel resolution and amplifies inner approximation errors.

Specifically, with λn≍2n/2\lambda_n\asymp2^{n/2}, Tn=2nT_n=2^n, and pn≍2−np_n\asymp2^{-n}, separately bounding the two inner mean-square errors gives only λn2O(Tn−1)=O(1)\lambda_n^2\mathcal O(T_n^{-1})=\mathcal O(1). The resulting multilevel variance upper bound is ∑n=1Npn−1O(1)=O(2N)\sum_{n=1}^N p_n^{-1}\mathcal O(1)=\mathcal O(2^N), which is insufficient to establish acceleration. Thus, applying the RT-MLMC telescoping identity alone does not yield our result.

Our fixed-anchor analysis in Lemma A.9 instead exploits cancellation between the coupled inner errors. Writing Δλt=(zkt(λ)−zλ⋆)−(ykt−y0⋆)\Delta_\lambda^t=(z_k^t(\lambda)-z_\lambda^\star) -(y_k^t-y_0^\star), where zλ⋆z_\lambda^\star and y0⋆y_0^\star are the perturbed and unperturbed minimizers, we establish

E[∣Δλt∣2∣Hk]≤Cλ−4+Cλ−2t+1.\mathbb E[\\|\Delta_\lambda^t\\|^2\mid\mathcal H_k] \leq C\lambda^{-4}+\frac{C\lambda^{-2}}{t+1}.

The proof explicitly retains the remainder caused by the different minimizers, rather than assuming pure contraction of the error difference. Together with sensitivity analysis across penalty levels, this yields

E![∣Gk(n,λn)−Gk(n−1,λn−1)∣2∣Fk]=O(2−n);\mathbb E\\!\left[\\|G_k(n,\lambda_n)-G_k(n-1,\lambda_{n-1})\\|^2 \mid\mathcal F_k\right]=\mathcal O(2^{-n});

see Lemma A.14. The RT-MLMC estimator therefore has O(N)\mathcal O(N) variance and O(N)\mathcal O(N) expected inner cost. These estimates enable O~(ϵ−4)\widetilde{\mathcal O}(\epsilon^{-4}) expected sample and gradient complexity, matching the accuracy dependence of the Hessian-based CSBO method without second-order oracles.

Level-dependent stabilization and its analysis.

We additionally introduce a stepsize reduction for high sampled levels to damp occasional large inverse-probability-weighted updates. Since the stepsize and estimator depend on the same random level, the damped update no longer preserves the terminal-level expectation. Our analysis explicitly derives the expected weighted update and controls the additional threshold-level bias, retaining the O~(ϵ−4)\widetilde{\mathcal O}(\epsilon^{-4}) complexity guarantee, as established in the proof of our accelerated algorithm. This stabilizes the updates rather than changing the variance of the unscaled estimator. Our ablation studies, including nonadaptive controls with uniformly smaller stepsizes, support the benefit of level-dependent damping on the tested instance.

Weakness 2. How do the additional experiments address practical relevance?

The two applications are a learning problem and a model-based decision problem, and they lie on the two sides of the regime in which Algorithm 2 saves inner work; see Section B.4. To strengthen the practical evaluation, we added ablation analyses and clarified the model assumptions and information access. On the evaluation choices, we added in Section B.3 a stepsize comparison of all four methods under scaled outer and inner stepsizes, and a comparison of the two proposed algorithms under a scaled penalty and in two joint grids, one pairing the penalty multiplier with the outer stepsize multiplier and one with the inner stepsize multiplier; we also added an evaluation with a reduced calibration set for pricing in Section B.2.9 and a synthetic problem with a tunable lower-level condition number in Section B.4. Across the separate inner- and outer-stepsize sweeps in Section B.3.1, the ordering of the four methods remains unchanged. The additional penalty and joint-grid experiments further assess the robustness of the two proposed algorithms over the tested hyperparameter ranges. The meta-learning formulation satisfies the assumptions of our convergence analysis, and for pricing the model calibration, gradient access, and local noise bound are addressed in Question 3 and our response to MLYX.

AuthorsOpenReview ↗

Author Response to Reviewer avvX: Practical Acceleration and Generalization

Question 1. When does RT-MLMC acceleration provide a substantial practical benefit?

We added Section B.4 to the revised manuscript to analyze this question.

The benefit is determined by how much inner work an effective upper-level update needs. Algorithm 2 draws a random level, so deep solves are rare and the expected number of inner iterations grows with the number of levels rather than with the deepest one. It therefore saves time when the accuracy that the outer update needs requires many inner iterations, and saves nothing when a short solve already suffices. A short solve suffices when that accuracy is reached quickly, or when the outer descent tolerates a coarser estimate.

The two applications are the two regimes. On meta-learning the inner loop of Algorithm 1 grows long, so it repeatedly pays for deep solves and Algorithm 2 reduces the objective faster in wall-clock time. On pricing the tuned Algorithm 1 already makes most of its progress with short inner solves, so the multilevel construction has little to save and Algorithm 2 does not accelerate the run.

Section B.4 supports this reading in three ways. It measures the inner work actually executed in the two runs, which separates the regimes. It checks one-step progress at fixed states, where short inner solves still decrease the objective, so a few inner steps are genuinely sufficient on pricing. It adds a synthetic family whose exact upper objective is unchanged as the lower-level conditioning varies: the advantage of Algorithm 2 grows with the number of inner iterations that Algorithm 1 is prescribed, and a control that always uses the deepest level reaches the same objective with far more samples, so the saving comes from random level selection.

RT-MLMC is therefore beneficial when an effective upper-level update needs many inner iterations.

Question 2. How is the learned variable used on an unseen task?

The upper-level variable xx in Equation (7) is a shared regularization center. Given a learned x^\widehat x, a task adapts by solving its lower-level problem on its support data with x^\widehat x fixed,

\widehat y\approx\arg\min_y\left\\{\widehat\ell^{\mathrm{support}}(y)+\frac{\gamma}{2}\\|y-\widehat x\\|^2\right\\}.

Generalization to unseen tasks is not the focus of this paper; we therefore focus on how efficiently the methods solve the corresponding CSBO problem. Nevertheless, we add relevant experiments to test the generalization performance of the learned parameter xx; see Section B.1.5 for details. Specifically, we evaluated the saved iterates of all runs of the main experiment under two settings. The first setting uses three new 7-way tasks from 21 classes unseen in training, while the second setting considers held-out images of the three training tasks. For reference, the same adaptation is applied to x=0x=0, which is plain regularized training of each task, and to the random initial point.

In both settings, every learned parameter improves on the random point from which the algorithms start, but none is better than the zero center on held-out data. On new classes the four methods are indistinguishable. On held-out images of the training tasks our two methods have lower error than the two baselines, in the same order as the training objective, but remain far from the zero center. The gap is consistent with fitting the fixed upper-level data of the training tasks rather than learning a center that transfers to other data.

AuthorsOpenReview ↗

Author Response to Reviewer avvX: Pricing Assumptions and Technical Contribution

Question 3. How realistic is gradient access in electricity pricing?

The pricing model is already built under realistic information access. In particular, none of its inputs is assumed to be observed directly, and every component is estimated from data by standard practice. The conditional baseline-load law is fitted on flat-rate households as in Section B.2.3, and the cluster-specific response potentials are identified by inverse optimization on the observed responses of the dynamic-tariff trial as in Section B.2.4. Once these are fitted, the lower-level gradient is explicit,

∇zhg(x,z;η,ξ)=∇Φr(h)(zh)+S(ηh)(px(ξ)−pref),\nabla_{z_h}g(x,z;\eta,\xi)=\nabla\Phi_{r(h)}(z_h)+S(\eta_h)\bigl(p_x(\xi)-p_{\rm ref}\bigr),

and stochastic gradients are obtained by sampling load scenarios.

More realistic information access is therefore not a variation of this experiment: the model is fitted from observed data, and reducing the assumed information would replace the problem rather than perturb it. What can be varied is the amount of data behind the fitted model, which we evaluated in Section B.2.9. We refit the response model, within the same family, on 50%, 25% and 10% of the calibration days, let every method optimize its tariff against the refitted model, and evaluate all tariffs under the model fitted on all days; one fixed subset is used per fraction. Algorithm 1 barely changes even with a tenth of the data, and Algorithm 2 behaves similarly down to a quarter. At a tenth, Algorithm 2 with the reported parameters fails, because the refitted model is much worse conditioned and the reported inner stepsize is then too large; rescaling the stepsize by the ratio of the two condition numbers removes the failure.

The tariffs are therefore insensitive to how much data the model is fitted on, provided the inner stepsize matches the curvature of the model actually being optimized.

Question 4. What technical contribution goes beyond the loss of warm starts?

Holding xx fixed during an inner solve is standard. The additional contribution is a coupled displacement estimate that remains valid for trajectories minimizing different objectives and is strong enough to control a growing penalty.

The distinction matters even for ordinary SBO. The proof of Lemma A.8 in Kwon et al. (2024a) invokes a pure-contraction step for this displacement. Our Appendix A.2 shows that the step can fail. For g(w)=w2/2g(w)=w^2/2, f(w)=1−cos⁡wf(w)=1-\cos w, and λ≥2\lambda\ge2, both exact minimizers are zero. Yet at u=−π/2u=-\pi/2 and v=u−1/λv=u-1/\lambda, the displacement is u−v=1/λu-v=1/\lambda while its drift is

λ−1f′(u)+g′(u)−g′(v)=0.\lambda^{-1}f'(u)+g'(u)-g'(v)=0.

Thus strong convexity alone supplies no strictly contractive drift at this pair.

Lemma A.9 centers each trajectory at its own conditional minimizer and studies

(z^t(\lambda)-y_{1/\lambda}^\star) -(y^t-y_0^\star).$$ The exact drift decomposition retains the remainder from the two distinct minimizers. Shared samples then preserve the cancellation needed to prove, uniformly over outer iterations and contexts, $$\mathbb E\\|\Delta_\lambda^t\\|^2 \le C\lambda^{-4}+\frac{C\lambda^{-2}}{t+1}.$$ At $t=2^n$ and $\lambda=\lambda_n\asymp2^{n/2}$, multiplying by $\lambda_n^2$ gives $O(2^{-n})$. Combining this estimate with the adjacent exact-minimizer directions yields Lemma A.14 and the accelerated complexity. The estimate holds for each fresh context even when its inner solution changes substantially. Appendix A.10 additionally controls the dependence between the sampled correction and its adaptive stepsize, preserving the $\widetilde{\mathcal O}(\epsilon^{-4})$ guarantee.
Reviewer_MLYXOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studied contextual stochastic bilevel optimization problems and proposed a fully first order approach for it. To further improve the convergence rate, the paper proposed an accelerated version using the random truncated multilevel Monte Carlo technique. The original version of algorithm has O(ϵ−6){\cal O}(\epsilon^{-6}) convergence rate, while the accelerated version enjoys O(ϵ−4){\cal O}(\epsilon^{-4}) convergence rate. Experimental results on contextual electricity pricing problem validate the effectiveness of the proposed methods.

Critical strengths

The proposed methods are fully first order and achieved the best known rate in contextual stochastic bilevel optimization. To achieve this goal, the author proposed several novel designs, including adaptive stepsize and the proof techniques.

Critical weaknesses

The main weakness is that it is unclear how informative and useful the theory in this paper is in practice. For the electricity-pricing problem, Algorithm 2 which has theoretically faster convergence rate seems to converge slower in the experiment. Moreover, it is not clear whether the electricity pricing problem satisfies the assumptions made in this paper, e.g. the bound gradient noise assumption.

It would be good if the author can highlight some ablations in the main paper, as the algorithm's performance are highly depending on the stepwise they choose. To make a fair comparison, it is crucial to show the robustness of the algorithm under different stepsize, penalty constant and other hyperparameters, and compare with other baselines.

Questions for authors

How sensitive is the algorithm's performance to the penalty constant?

2 comments
AuthorsOpenReview ↗

Author Response to Reviewer MLYX: Practical Acceleration and Pricing Assumptions

We thank the reviewer for recognizing the fully first-order construction and the proof techniques. We have clarified how the practical benefit of RT-MLMC depends on the inner-solve cost and presented additional robustness results in the revised manuscript.

Weakness 1. Practical acceleration and the pricing assumptions

We agree that Algorithm 2 reaches the plateau more slowly than Algorithm 1 on the electricity-pricing instance. This observation is indeed closely related to the fact that this instance needs a small number of total inner iterations to reach the plateau. Specifically, we tuned CTC_T for Algorithm 1 to a small value 0.002, so TkT_k of Algorithm 1 starts at 11 and remains in the low tens during the early phase. Although the inner solves in this phase are inaccurate, the resulting upper-level updates are still effective enough that the objective reaches F≤2.09F\le 2.09 within the first 100 outer iterations on average.

In contrast, Algorithm 2 has no comparable cheap phase: each multilevel update constructs several base estimators, so its per-update cost is already high from the first update, and the level distribution can also place a deep level early. Consequently, Algorithm 1 reaches the target with about 2.0×1042.0\times10^{4} cumulative gradient calls in a mean time of 0.414 s, against 9.1×1049.1\times10^{4} calls in 1.565 s for Algorithm 2. Both Algorithms 1 and 2 are also faster than the Hessian-based method on this problem.

The underlying reason is that a small CTC_T suffices under either of two conditions: the lower-level problem is easy enough that a few inner steps already give a hypergradient estimate accurate enough for the outer update, or the upper-level descent tolerates the remaining error in the hypergradient estimate at the target accuracy. Here the relevant error is the error of the full direction used to update xx, not the distance between the inner iterate and the exact lower-level solution. These conditions explain why short inner solves can be sufficient on pricing, while the meta-learning setting uses much longer inner loops and Algorithm 2 enjoys the advantage.

Algorithm 2 is therefore faster when producing a hypergradient accurate enough for the outer update requires many inner iterations, so that avoiding deep solves pays for the multilevel overhead; the meta-learning experiment is in this regime. We have added two studies that correspond to the two conditions to support this claim; see Section B.4 for details.

Assumption 2.2 holds uniformly under zero initialization, with b=G2/(2μg)b=G^2/(2\mu_g). The regularity and conditional-noise bounds associated with Assumption 2.1 are established on a region containing the relevant inner iterates and auxiliary points; see Section B.2.5.

Write the lower-level objective as g(x,w;η,ξ)=Φ(w)+b(x,η,ξ)⊤wg(x,w;\eta,\xi)=\Phi(w)+b(x,\eta,\xi)^\top w, where x∈Rdxx\in\mathbb{R}^{d_x} is the tariff policy; w∈Rdyw\in\mathbb{R}^{d_y} is the vector of household load adjustments; ξ\xi is the context; η\eta is the scenario; the vector b(x,η,ξ)∈Rdyb(x,\eta,\xi)\in\mathbb{R}^{d_y} collects the household price responses.

The convex response function Φ\Phi satisfies μI⪯∇2Φ(w)⪯LyI\mu I\preceq\nabla^2\Phi(w)\preceq L_yI, so gg is μ\mu-strongly convex and LyL_y-smooth in ww, where μ\mu and LyL_y are the strong-convexity and smoothness constants of Φ\Phi. Since contexts, scenarios, and tariffs are bounded, b(x,η,ξ)b(x,\eta,\xi) and its derivatives in xx are bounded. Separately, the explicit construction of the upper-level loss f(x,w;η,ξ)f(x,w;\eta,\xi) yields bounded gradients and Hessians, and the upper-level objective FF is bounded below.

Conditioned on ξ\xi (so the expectation is over η∣ξ\eta\mid\xi), the noise of the full gradient has two blocks: (A−E[A∣ξ])w(A-\mathbb{E}[A\mid\xi])w in the xx-component and b−E[b∣ξ]b-\mathbb{E}[b\mid\xi] in the ww-component, where A=(Dxb)⊤A=(D_xb)^\top is the transpose of the Jacobian of bb with respect to xx.

Since bb and DxbD_xb are bounded and ∥w∥≤r\lVert w\rVert\le r on the region, both blocks have bounded conditional variance, so the noise bound in Assumption 2.1(iv) holds on this region. Thus, the conditional gradient-noise bound associated with Assumption 2.1(iv) holds uniformly on the relevant bounded region.

The new Lemma B.1 in Section B.2.5 shows that all inner iterates and all lower-level minimizers stay in a bounded ball BRB_R, uniformly over outer iterations, contexts and MLMC levels, where the radius RR depends only on the problem constants. This holds with zero initialization and the stepsizes and penalties used in the algorithms, which satisfy β0≤2/μ\beta_0\le 2/\mu and βt≤1/(Ly+μ/2)\beta_t\le 1/(L_y+\mu/2) for t≥1t\ge 1; Section B.2.6 checks these conditions.

AuthorsOpenReview ↗

Author Response to Reviewer MLYX: Ablations and Robustness

We thank the reviewer for this suggestion, and we have added the corresponding sensitivity analyses to the revised manuscript; see Section B.3.

Weakness 2. Ablations and robustness of the comparison

Specifically, beyond the adaptive-stepsize ablation already in Section B.1.4, we have added separate sensitivity analyses of the outer and inner stepsizes for all four methods, the penalty parameter for the two proposed algorithms on both applications, two joint grids combining the penalty with either the outer or inner stepsize, and the inner-iteration budget of Algorithm 1 and the truncation level of Algorithm 2 on meta-learning.

Penalty sensitivity (Section B.3.2).

We multiply the penalty parameter of both proposed algorithms by a constant factor and consider two scenarios.

In the first scenario, the outer and inner iteration counts are those of the main experiments, so only the penalty entering the updates changes. The curves for the different factors lie almost on top of each other for both algorithms on both problems, suggesting that the penalty value by itself has little influence within the tested range.

In the second scenario, the inner iteration count of Algorithm 1 follows the scaled penalty as prescribed by its schedule, and the number of outer iterations is recalibrated to match the wall-clock time of the main experiments. The inner work of Algorithm 2 does not depend on the penalty, so its outer iteration count remains essentially unchanged.

The second scenario reveals a difference between the two algorithms. Algorithm 2 is insensitive to penalty scaling on both problems. Algorithm 1 is sensitive on meta-learning: a larger penalty increases its inner-loop budget quadratically, so far fewer outer iterations fit into the same time budget, and its performance degrades substantially. On electricity pricing, both algorithms stay close to their performance in the main experiment, and the effect is much smaller than on meta-learning.

These results distinguish the direct influence of the penalty parameter from its effect on computational cost. The cost of Algorithm 1 is tied to the penalty through its number of inner iterations, whereas the inner-loop cost of Algorithm 2 is not. This provides a practical illustration of the computational difference between the two algorithms. The relative ordering of the two proposed algorithms remains unchanged in the two tested penalty scenarios.

Taken together, these ablations provide additional evidence for the robustness of the comparisons. The ordering of the four methods remains unchanged across the separate stepsize sweeps in Section B.3.1. Algorithm 2 is also relatively insensitive to the tested penalty multipliers, while the inner-budget and truncation-level experiments on meta-learning preserve its advantage over Algorithm 1.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.