acceptodds
Under review as a conference paper at ICLR 2027

ZOBA: An Efficient Single-loop Zeroth-order Bilevel Optimization Algorithm

Abstract

Bilevel optimization problems consist of minimizing a value function whose evaluation depends on the solution of an inner optimization problem. These problems are typically tackled using first-order methods that require computing the gradient of the value function (the \it hypergradient). In several practical settings, however, first-order information is unavailable, rendering these methods inapplicable. Finite-difference methods provide an alternative by approximating hypergradients using function evaluations along a set of directions. However, such surrogates are notoriously expensive, and most finite-difference bilevel approaches rely on two-loop algorithms that are poorly parallelizable. Recently, several works have proposed single-loop finite-difference methods enabling parallelization. However, to ensure stability, these methods require a large number of function evaluations per iteration, limiting their applicability in high-dimensional settings with limited evaluation budget. In this work, we propose ZOBA, an efficient finite-difference single-loop algorithm for bilevel optimization. Our method leverages hypergradient approximations based on delayed information and function values reusage to enable parallelization while limiting the per-iteration cost. We analyze the proposed algorithm and establish convergence rates in the non-convex setting, achieving a complexity of , where and denote the dimensions of the inner and outer variables, respectively and is the accuracy. This improves upon prior approaches based on Hessian approximation. We further introduce and analyze HF-ZOBA, a Hessian-free variant that yields optimal complexity. Finally, we corroborate our findings with numerical experiments on synthetic functions and a real-world black-box task in adversarial machine learning. Our results show that our methods achieve accuracy comparable to state-of-the-art techniques while requiring significantly less computation time.

Primary area:
optimization
Keywords:
zeroth-order optimization, black-box optimization, stochastic bilevel optimization, finite-difference method

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_EUjcOpenReview ↗
Rating
3
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes two single-loop finite-difference algorithms, ZOBA and HF-ZOBA, for bilevel optimization, leveraging function-value reuse and delayed information to reduce per-iteration computational costs and enable parallelization. Theoretical analyses and numerical experiments show that ZOBA achieves a complexity of O(p(d+p)2ε−2)O(p(d+p)^2\varepsilon^{-2}), while HF-ZOBA attains optimal complexity; both methods achieve accuracy comparable to state-of-the-art techniques with significantly less computation time.

Critical strengths

1.The paper addresses an important computational challenge in zeroth-order bilevel optimization, namely the high function-evaluation cost of hypergradient approximation, particularly in high-dimensional settings.

2.The paper introduces a computationally motivated single-loop design that uses delayed information to enable parallel updates and reuse function evaluations across gradient and Hessian approximations, reducing the per-iteration oracle cost at the expense of additional approximation error, which is accounted for in the convergence analysis.

3.This paper is well-written and theoretical solid.

Critical weaknesses

1.Although the use of delayed information and function-value reuse is correctly reflected in the proposed algorithm, the novelty and significance of this design remain unclear. In particular, it would be useful to clarify whether the reduction in function evaluations fundamentally relies on delayed updates or whether similar reuse could be achieved without introducing this delay.

2.Although Table 1 reports both the per-iteration function-evaluation costs and the theoretical oracle complexities, the claimed computational advantage of ZOBA and HF-ZOBA is not fully established by these comparisons. In particular, the methods are compared in terms of per-iteration function evaluations under a special parameter setting, but these counts do not necessarily reflect the total oracle cost required to achieve the same accuracy.

3.The parameter search spaces appear to contain some inconsistencies. In particular, the candidate values for ℓ1,ℓ2\ell_1,\ell_2 are given as 1,10,50,100{1,10,50,100} in one description, whereas Table 3 includes 2525 as an additional candidate. Similarly, the candidate momentum values for ZOSOGD differ between the main description and Table 3. These discrepancies should be resolved.

Questions for authors
  1. Theorem 3.4 imposes conditions on the stepsizes and smoothing parameter, but the role of the batch sizes b1,ℓ1,b2,ℓ2b_1,\ell_1,b_2,\ell_2 in establishing the convergence rate is not sufficiently clear. Could the authors clarify how these batch sizes should be chosen to ensure the stated bound and explain how their choices affect the convergence rate and the overall function evaluation complexity?

  2. In Corollary 3.5 (II), the parameter conditions appear to be inconsistent. Specifically, α1,α2∈(1/2,1)\alpha_1,\alpha_2\in(1/2,1) implies 2α2>1>α12\alpha_2>1>\alpha_1, which contradicts the requirement α1≥2α2\alpha_1\ge 2\alpha_2. Could the authors correct these conditions and clarify the intended parameter regime under which the claimed asymptotic convergence holds? In particular, it would be helpful to explain how the corrected parameter choices ensure that the normalized cumulative error vanishes and αK→0\alpha_K\to0.

  3. In Corollary 3.5 (III), the relationship between the prescribed batch sizes, the quantities D1D_1 and D2D_2, and the claimed oracle complexity is not entirely clear. Could the authors provide an explicit derivation showing how the prescribed batch sizes guarantee αK≤ε\alpha_K\leq\varepsilon and lead to the stated function-evaluation complexity? It would also be helpful to clarify whether the batch-size conditions constrain the individual parameters or their products.

  4. The authors state that the hyperparameters are selected through grid search, with the batch sizes b1,b2b_1,b_2 and the numbers of random directions ℓ1,ℓ2\ell_1,\ell_2 for ZOBA and HF-ZOBA chosen from specified candidate sets. However, the selected values for each method and experimental setting are not reported. Since these parameters can substantially affect both convergence behavior and function-evaluation costs, reporting the selected configurations is important for reproducibility and for interpreting the results.

4 comments
AuthorsOpenReview ↗

Rebuttal (Part 1/3)

We thank the reviewer for the constructive feedback and for the positive assessment of the paper’s computational motivation, single-loop design, writing quality, and theoretical analysis. We address the concerns and questions below.

In the following, we respond to their concerns and questions.

Weakness 1 The use of delayed information is essential to fully exploit function-value reuse in our algorithms. Without this delay, the gradient and Hessian approximations would need to be constructed at different points, preventing us from reusing most of the function evaluations. To illustrate this, consider a non-delayed variant of ZOBA, in which the updates would take the following form: zk+1=zk−ρ∇^zG(zk,xk),z_{k + 1} = z_k - \rho \hat{\nabla}_z G(z_k, x_k),

vk+1=vk−ρ(∇^zz2G(zk+1,xk)vk+∇^zF(zk+1,xk))v_{k + 1} = v_k - \rho (\hat\nabla^2_{zz} G(z_{k +1}, x_k) v_k + \hat\nabla_z F(z_{k + 1}, x_k) ) and xk+1=xk−γ(∇^xz2G(zk+1,xk)vk+1+∇^xF(zk+1,xk))x_{k + 1} = x_k - \gamma (\hat\nabla^2_{xz} G(z_{k +1}, x_k) v_{k+1} + \hat\nabla_x F(z_{k + 1}, x_k) ) In this case, the Hessian approximation would have to be constructed from scratch. In particular, the function evaluations used to compute ∇^zG(zk,xk)\hat\nabla_zG(z_k,x_k), namely, g(zk±hwk(i,j),xk,ξi,k)g(z_k \pm h w_k^{(i,j)}, x_k, \xi_{i,k}), could not be reused, since the Hessian approximation would instead require evaluations at g(zk+1±hwk(i,j),xk,ξi,k)g(z_{k +1} \pm h w_k^{(i,j)}, x_k, \xi_{i,k}). Without delayed information, the remaining opportunities for function-value reuse would be the common unperturbed evaluations of ff (shared by ∇^zF(zk+1,xk)\hat\nabla_{z} F(z_{k+1},x_k) and ∇^xF(zk+1,xk)\hat\nabla_xF(z_{k+1},x_k)), as well as the common unperturbed evaluations of gg shared by the two Hessian-block approximations, yielding a total saving of b1+b2b_1+b_2 function evaluations. However, these savings are considerably smaller than those enabled by our delayed-update design. In particular, the latter additionally allows us to reuse the evaluations employed in constructing the inner-gradient approximation when approximating the inner Hessian block, thereby avoiding an additional 2b1ℓ12b_1\ell_1 function evaluations. Consequently, the total number of saved function evaluations due to reuse in ZOBA is 2b1ℓ1+b1+b22b_1\ell_1+b_1+b_2. The advantage is even more pronounced in HF-ZOBA. With delayed information, the finite-difference approximation of the Hessian-vector product (denoted by HzzkH_{zz}^k) reuses the gradient approximations already computed for the inner update. Without delay, these approximations would have to be recomputed at the updated point. Moreover, delayed information allows the three sequences to be updated in parallel. Without it, the updates would have to be computed sequentially because the update of vk+1v_{k+1} depends on zk+1z_{k+1}, while the update of xk+1x_{k+1} depends on both zk+1z_{k+1} and vk+1v_{k+1}. Therefore, the delay is not merely an implementation choice: it is what enables the additional function-value reuse exploited by our algorithms and the parallel updates. Of course this introduce additional errors that are accounted in the analysis.

Weakness 3 and Question 4. We thank the reviewer for pointing out these inconsistencies. We have corrected them and now report the hyperparameter values selected by grid search for each method and experimental setting in the Experimental Details appendix.

Question 2 We thank the reviewer for spotting this out! The corrected exponent conditions in Corollary 3.5(II) are α1∈(1/2,1)\alpha_1\in(1/2,1), α2∈(1/3,1/2)\alpha_2\in(1/3,1/2), α1≥2α2\alpha_1\geq 2\alpha_2, and α3>1\alpha_3>1. We clarify why these conditions ensure the claimed convergence. First, the condition α1≥2α2\alpha_1\geq 2\alpha_2 guarantees the stepsize requirement in Theorem 3.4, namely γk=O(ϕˉzρk2)\gamma_k=O(\bar\phi_z\rho_k^2). Second, under these exponent conditions, the error terms in the proof of Corollary 3.5(II) (Appendix D) are summable. Recall that γk=γ(k+1)−α1\gamma_k=\gamma(k+1)^{-\alpha_1}, ρk=ρ(k+1)−α2\rho_k=\rho(k+1)^{-\alpha_2}, and hk=h(k+1)−α3h_k=h(k+1)^{-\alpha_3}. In particular, the error terms appearing in the convergence bound are of the following orders: γkhk2\gamma_kh_k^2, ρkhk2\rho_kh_k^2, ρk3\rho_k^3, ρk3hk2\rho_k^3h_k^2, γk2\gamma_k^2, and γk2hk2\gamma_k^2h_k^2. The stated exponent conditions ensure that all these terms are summable. Consequently, their cumulative contribution remains bounded and vanishes when normalized by ∑k=0Kγk\sum_{k=0}^{K}\gamma_k. Moreover, since α1<1\alpha_1<1, we have ∑k=0Kγk→∞\sum_{k=0}^{K}\gamma_k\to\infty as K→∞K\to\infty, so the normalized initialization term also vanishes. It follows from the convergence bound that αK→0\alpha_K\to0. Therefore, the proof of Corollary 3.5(II) remains unchanged apart from correcting the exponent conditions. We have corrected the conditions in both the statement and proof in the revised manuscript (see updated manuscript).

AuthorsOpenReview ↗

Rebuttal (Part 2/3)

Question 1 and 3

The bound of Theorem 3.4 holds for any positive integers b1,ℓ1,b2,ℓ2b_1,\ell_1,b_2,\ell_2. No specific choice, and in particular no dimension-dependent scaling of the batch sizes or numbers of directions, is needed to establish it. The batch sizes and numbers of directions enter the analysis in several ways: they determine the constants of the error terms Cˉk\bar C_k in the bound (see Appendices E.1 and E.3), the accuracy of the gradient and Hessian surrogates (Lemmas D.9 and D.10) and the admissible ranges of the stepsizes and of the smoothing parameter (see conditions of Theorems 3.4 and 3.6). In particular from the bounds in the manuscript we can observe that larger batch sizes and more directions give more accurate and more stable estimators, and they enlarge the admissible stepsizes. Since the rate contains many error terms, to illustrate how these parameters affect the rate, consider Setting (I) of Corollary 3.5 and show only the dependence on dimensions and batch sizes. The proof gives

αK ≲ Rinitγ(K+1)+O(p(d+p)2b1ℓ1+d+pb2ℓ2)γ+O((p+6)2pb1ℓ1+pb2ℓ2+pℓ1b1)ρ3γ+Ch2.\alpha_K\ \lesssim\ \frac{R_{\rm init}}{\gamma(K+1)}+\mathcal O( \frac{p(d + p)^2}{b_1 \ell_1} + \frac{d + p}{b_2 \ell_2}) \gamma+\mathcal O( \frac{(p + 6)^2p}{b_1 \ell_1} + \frac{p}{b_2 \ell_2} + \frac{p}{\ell_1 b_1}) \frac{\rho^3}{\gamma}+Ch^2 .

The terms depending on hh are collected in CC, since their contribution can be made negligible by choosing hh sufficiently small. The batch sizes and numbers of directions control the remaining error terms: larger b1ℓ1b_1\ell_1 and b2ℓ2b_2\ell_2 reduce them, and larger b1ℓ1b_1\ell_1 also allows larger stepsizes. While larger batches reduce the error terms, they also increase the per-iteration cost b1(4ℓ1+1)+b2(2ℓ2+1)b_1(4\ell_1+1)+b_2(2\ell_2+1) and thus to obtain good complexity (number of evaluations needed to reach αK≤ε\alpha_K\le\varepsilon) a good balance is needed. Corollary 3.5 (III) gives a choice of the parameters and batch sizes that balances these two effects. Regarding the derivation of complexity, we first clarify that D1D_1 and D2D_2 are shorthand quantities introduced to simplify the statement. As shown in the proof (Appendix E.2), the constants of the error terms satisfy

C5,1=O(p(d+p)2b1ℓ1+db2ℓ2)=O(D1),C6,1=O(p3b1ℓ1+pb2ℓ2)=O(D2).C_{5,1}=\mathcal O\left(\frac{p(d+p)^2}{b_1\ell_1}+\frac{d}{b_2\ell_2}\right)=\mathcal O(D_1),\qquad C_{6,1}=\mathcal O\left(\frac{p^3}{b_1\ell_1}+\frac{p}{b_2\ell_2}\right)=\mathcal O(D_2).

Under the parameters of Corollary 3.5, the bound reads

αK≤Rinitγ(K+1)+C3μGφˉzρ3+C6,1ρ2γ+C5,1γ+C(γ,ρ)h2,\alpha_K\le \frac{R_{init}}{\gamma(K+1)}+\frac{C_3\mu_G\bar\varphi_z\rho^3+C_{6,1}\rho^2}{\gamma}+C_{5,1}\gamma+C(\gamma,\rho)h^2,

where RinitR_{init} is the initialization. We choose γ\gamma to minimize the terms that do not depend on hh. The bound thus becomes

αK≤2C5,1(RinitK+1+C3μGφˉzρ3+C6,1ρ2)+C(γ,ρ)h2.\alpha_K\le 2\sqrt{C_{5,1}\Big(\frac{R_{init}}{K+1}+C_3\mu_G\bar\varphi_z\rho^3+C_{6,1}\rho^2\Big)}+C(\gamma,\rho)h^2 .

Choosing h=ε/(2C(γ,ρ))h=\sqrt{\varepsilon/(2C(\gamma,\rho))} makes the last term at most ε/2\varepsilon/2. Since C(γ,ρ)C(\gamma,\rho) depends on D1D_1 and D2D_2, this gives h=O(ε (1+D1/D2)−1/2)h=\mathcal O\big(\sqrt{\varepsilon}\,(1+\sqrt{D_1/D_2})^{-1/2}\big), as in the corollary. We then choose

ρ=ε64 C5,1C6,1=O(ε (D1D2)−1/2),φˉz=C6,1C3μGρ,\rho=\frac{\varepsilon}{\sqrt{64\,C_{5,1}C_{6,1}}}=\mathcal O\big(\varepsilon\,(D_1D_2)^{-1/2}\big),\qquad \bar\varphi_z=\frac{C_{6,1}}{C_3\mu_G\rho},

so that C3μGφˉzρ3+C6,1ρ2=2C6,1ρ2=ε2/(32C5,1)C_3\mu_G\bar\varphi_z\rho^3+C_{6,1}\rho^2=2C_{6,1}\rho^2=\varepsilon^2/(32C_{5,1}). Thus, we have

RinitK+1≤ε216C5,1−ε232C5,1=ε232C5,1,\frac{R_{init}}{K+1}\le\frac{\varepsilon^2}{16C_{5,1}}-\frac{\varepsilon^2}{32C_{5,1}}=\frac{\varepsilon^2}{32C_{5,1}},

that is,

K+1≥ 32C5,1Rinitε−2=O(D1Rinitε−2).K+1 \ge\ 32 C_{5,1} R_{init}\varepsilon^{-2}=\mathcal O\big(D_1R_{init} \varepsilon^{-2}\big).

Under this condition, αK≤ε\alpha_K\le\varepsilon. The total number of function evaluations is the number of iterations times the per-iteration cost, which is at most 5(b1ℓ1+b2ℓ2)5(b_1\ell_1+b_2\ell_2). Note that the cost and the error constants D1,D2D_1,D_2 depend on the batch sizes and numbers of directions only through the products b1ℓ1b_1\ell_1 and b2ℓ2b_2\ell_2. Hence the batch-size conditions in Corollary 3.5 (III) constrain these products, not the individual parameters.

Take b1ℓ1≍p(d+p)2/cb_1\ell_1\asymp p(d+p)^2/c and b2ℓ2≍p(d+p)2/cb_2\ell_2\asymp p(d+p)^2/c. Then, the total complexity is therefore O(p(d+p)2 ε−2).\mathcal O\big(p(d+p)^2\,\varepsilon^{-2}\big).

AuthorsOpenReview ↗

Rebuttal (Part 3/3)

Weakness 2 Table 1 reports two distinct quantities: the theoretical oracle complexity and the number of function evaluations required per iteration.

The former characterizes the total number of function evaluations required by an algorithm to achieve an accuracy of ε\varepsilon. As shown in the table, ZOBA improves upon methods based on explicit Hessian approximation (ZMDSBA and ZDSBA), while HF-ZOBA achieves optimal oracle complexity, matching that of the other baselines.

The per-iteration evaluation cost provides a complementary measure of the flexibility of our algorithms. We emphasize that a lower per-iteration cost does not, by itself, imply a lower total oracle complexity. Rather, it indicates how flexibly the evaluation budget can be distributed across iterations. This flexibility is particularly valuable in settings with a limited evaluation budget: by adjusting their parameters, algorithms with lower per-iteration costs can perform more iterations within a fixed budget, potentially at the expense of estimator accuracy. In contrast, methods with less flexibility or high per-iteration costs due to unfavorable dimension dependence may become impractical under such constraints, even if they achieve optimal theoretical oracle complexity.

As shown in Table 1, ZOBA and HF-ZOBA offer greater flexibility in controlling the per-iteration cost through the choice of b1,ℓ1,b2,ℓ2b_1,\ell_1,b_2,\ell_2 than previous approaches. This practical advantage is also reflected in our experiments. For instance, the per-iteration cost of VRZSBO scales with the problem dimension. Under a limited evaluation budget, this can make large batch sizes impractical, even though larger batches generally improve estimator accuracy and may permit more favorable step-size choices. Indeed, although VRZSBO has the same theoretical oracle complexity as HF-ZOBA, its higher per-iteration cost makes it infeasible to run in our adversarial experiment with the available budget.

We have clarified the distinction between these two measures and the purpose of the per-iteration comparison in the revised manuscript (see new manuscript).

We thank the reviewer again for their time in reviewing our manuscript, their valuable feedback, and their positive evaluation. As the discussion phase is coming to an end, we would appreciate knowing whether our response has adequately addressed your concerns.

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

The paper studies bilevel optimization with access only to stochastic function values and proposes ZOBA and its Hessian-free variant, HF-ZOBA. The methods jointly track the outer variable, an inner solution, and an auxiliary linear-system solution. Their zeroth-order estimators are designed to reuse some function evaluations across updates. The paper reports total query complexities of O(p(d+p)2ε−2)O(p(d+p)^2 ε^{-2}) and O((d+p)ε−2)O((d+p)ε^{-2}), respectively, where d and p are the outer and inner dimensions and ε bounds the average expected squared hypergradient norm. Experiments compare query budgets and runtime on synthetic problems and MNIST adversarial tasks, with ablations on batch size, direction count, parallelization, and function-value reuse.

Critical strengths
  • A concrete and practically relevant efficiency objective. Zeroth-order bilevel updates can require many function evaluations. Jointly designing estimators to share query locations can directly reduce redundant calls, and the paper provides per-update query expressions that can be traced to the construction. This is a worthwhile algorithmic question, particularly when function evaluation is expensive.
  • A reasonably developed evaluation framework. The paper presents ZOBA and HF-ZOBA, discusses total query complexity, and reports queries and runtime separately. Several zeroth-order comparators and ablations address samples, directions, parallelization, and reuse. Supplementary code makes implementation details inspectable and provides a basis for evaluating the method after correction.
Critical weaknesses
  • The independent methodological increment and the efficiency claims are not sufficiently established. The three-variable single-loop structure has a clear antecedent in SOBA, while zeroth-order Hessian–vector approximations appear in the cited work of Peng and Nazari. Existing components do not preclude novelty, but the paper should identify which estimator design or analysis goes beyond applying shared-center caching to existing methods, and why that addition is necessary. A direct comparison with the closest approaches, under comparable implementation optimizations, would help substantiate the contribution (p. 2, lines 73–88; Appendix A; Table 1 on p. 19).

The efficiency discussion should distinguish constants, asymptotic orders, and total budgets. With direction counts fixed, the query formulas for HF-ZOBA and ZO-SOGD in Table 1 are both linear in batch size. The batch-scaling claim on p. 6, lines 270–275, should therefore be qualified as a constant-factor saving under the stated configurations. For a fixed per-update configuration, Q(ε)=qN(ε), where q counts queries per update and N(ε) counts updates to matched accuracy. Fewer samples or directions may reduce q while increasing estimation noise and N(ε). The paper does report total-complexity corollaries; the concern is not an absence of total-complexity analysis. Rather, the per-update comparison alone does not establish an advantage under finite budgets. Cumulative queries to matched accuracy should be compared using consistent accuracy definitions, actual call counts, and comparable tuning opportunities.

  • Unresolved validity issues affect both the theoretical guarantees and empirical comparisons. Corollaries 3.5(II) and 3.7(II) require α_1,α_2∈(1/2,1) and α_1≥2α_2 (p. 7, lines 339–342 and 369–372). Since 2α_2>1>α_1, this parameter set is empty: the stated diminishing-step-size regimes have no admissible instance. A corrected nonempty range and a valid example are needed. Reversing an inequality without rechecking the proof would not establish a valid replacement.

Theorem 3.6 also states a condition expressible as h_k≤Ch ̂_k, whereas its proof uses h_k≤Ch ̂_k ρ_k (p. 7, lines 356–357; p. 81, lines 4361–4367). Here C abbreviates the prefactor after aligning the identically named quantities. With this prefactor fixed and 0<ρ_k<1, the proof condition is strictly stronger. The additional step-size factor is used to absorb smoothing error into the contraction controlling auxiliary-variable tracking error. The displayed proof therefore does not cover all parameters allowed by the theorem statement. The conditions and affected corollaries need to be reconciled. These observations identify gaps in the written guarantees, not nonconvergence of the algorithms.

Empirically, the supplied ZOSOGD implementation constructs finite-difference queries with P_b2_p but reconstructs the Hessian–vector product using independently sampled P_b1_p (experiments/other_methods.py, lines 66–83 and 130–132). With the current state fixed, on a quadratic objective with independent zero-mean directions this term has zero expectation rather than the true matrix–vector product. In addition, the value–cost pairing in experiments/synthetic/utils.py, lines 34–41, combined with the interval replication in experiments/comp_with_other/plot_results.py, lines 72–84, can display an updated value before it is available. For example, a value requiring 100 queries may appear from query 1. Recording semantics also differ across runners. These findings concern the supplied code; they neither establish which version generated the paper's figures nor predict corrected rankings. Exact version provenance, raw logs, and corrected comparisons are needed to assess the efficiency claims.

Questions for authors
  • Methodological contribution. Relative to SOBA and the cited zeroth-order HVP methods, which specific estimator design or theoretical result constitutes the independent increment? Does the total-query advantage at matched accuracy remain when baselines receive available caching and comparable tuning? This would materially affect the novelty and significance assessment.
  • Diminishing-step-size guarantees. Please provide corrected, nonempty exponent ranges and one admissible numerical example for Corollaries 3.5(II) and 3.7(II), explaining how the step-size constraints and error-summability requirements are jointly satisfied.
  • HF theorem. Which smoothing condition is intended in Theorem 3.6: the main-text condition or the stronger condition used in its proof? Please reconcile them and explain any changes needed to the smoothing-parameter choices and conclusions of the existing corollaries.
  • Empirical conclusions. Which exact code revision generated the reported figures? After verifying that ZOSOGD's query and reconstruction directions match, using consistent cumulative call counts, and displaying each value only when it becomes available, do the main conclusions remain supported? Please provide before-and-after results and per-run logs.
6 comments
AuthorsOpenReview ↗

Rebuttal (Part 1/2)

Weakness 1 and Question 1

We thank the reviewer for the question. Our contribution goes beyond combining these components with shared-center caching. In particular, it lies in the estimator design and theoretical analysis. Below, we discuss the main differences with SOBA, ZO-SOGD [1], and VRZSBO [2].

Differences with SOBA. Although our algorithms share SOBA's single-loop structure, they are not obtained by simply replacing first-order information with surrogates. Indeed, a direct zeroth-order extension of SOBA would consist of applying Gaussian smoothing to the outer/inner objectives and using the hypergradient of the smoothed objectives as a surrogate. However, as shown in Lemmas D.7 and D.8, this approach introduces large approximation errors because the functions are always smoothed with respect to both variables. To avoid this, ZOBA employs different smoothings tailored to the individual hypergradient components (see Appendix D.2):

  • Gh,0(z,x)=Ew[G(z+hw,x)]G_{h,0}(z,x)=\mathbb E_w[G(z+hw,x)] to construct DzkD_z^k and ∇^z2G(z,x)\hat\nabla^2_z G(z,x).
  • Fh,0(z,x)=Ew[F(z+hw,x)]F_{h,0}(z,x)=\mathbb E_w[F(z+hw,x)] and F0,h(z,x)=Eu[F(z,x+hu)]F_{0,h}(z,x)=\mathbb E_u[F(z,x+hu)] to construct ∇^zF(z,x)\hat\nabla_z F(z,x) and ∇^xF(z,x)\hat\nabla_x F(z,x).
  • Gh,h(z,x)=Ew,u[G(z+hw,x+hu)]G_{h,h}(z,x)=\mathbb E_{w,u}[G(z+hw,x+hu)] to construct ∇^xz2G(z,x)\hat\nabla_{xz}^2 G(z,x).

Moreover, our analysis differs from SOBA's convergence analysis. In particular, SOBA relies on a uniform bound of the form E[∣Dxk∣2]≤C\mathbb E[|D_x^k|^2]\leq C. In our setting, this assumption cannot be directly adopted because DxkD_x^k is constructed from function evaluations. Instead, we prove the bound E[∥Dxk∥2]≤C1∣vk−v∗(xk)∣2+C2\mathbb E[\|D_x^k\|^2]\leq C_1|v_k-v^*(x_k)|^2+C_2. This dependence on the auxiliary-variable tracking error requires a modified analysis of tracking sequences, of value function decrease, of the Lyapunov and different stepsize conditions. Furthermore, SOBA bounds the tracking errors ∥zk−z∗(xk)∥2\|z_k-z^*(x_k)\|^2 and ∥vk−v∗(xk)∥2\|v_k-v^*(x_k)\|^2 by exploiting the smoothness of the solution mappings z∗(⋅)z^*(\cdot) and v∗(⋅)v^*(\cdot). This approach is insufficient for ZOBA and HF-ZOBA. We therefore adopt a different proof strategy based on the Lipschitz continuity of these mappings.

Furthermore, in HF-ZOBA, Hessian-vector products (HVPs) are approximated using first-order-to-zeroth-order finite differences, unlike in SOBA. Controlling the resulting approximation errors requires a different treatment of the tracking error and a modified value-function decrease analysis.

Differences with ZO-SOGD and VRZSBO. Our methods also differ from previous zeroth-order single-loop algorithms.

ZO-SOGD addresses online bilevel optimization (different setting) and establishes regret guarantees (different analysis), whereas our work considers the offline setting and establishes convergence guarantees, requiring a different analysis. Its updates also incorporate momentum terms, requiring additional function evaluations at different points and on different samples. Consequently, not all evaluations can be reused through caching. Moreover, its HVPs are approximated using central finite differences with different smoothing parameters and require evaluations at different iterates (e.g. eq. 27c of [1]). This further limits evaluation reuse, whereas our estimator design enables it.

VRZSBO employs coordinate-based estimators using all canonical basis vectors for gradient/HVP approximations, leading to a high per-iteration cost and making it unsuitable for our limited-budget setting. Its analysis also differs due to the variance reduction in the iterates.

Another difference concerns the treatment of approximation errors introduced by HVP approximations. ZO-SOGD and VRZSBO control these errors through projection steps onto a ball of a given radius. Our approach instead uses an adaptive smoothing parameter hˉk\bar h_k (see Theorem 3.6), without requiring additional projection steps to bound the iterates. This leads to a different analysis of approximation errors and iterate stability. We have included these observations in a new Appendix B.1 (see new manuscript).

Finally, we thank the reviewer for suggesting a fixed-accuracy experiment. We have included it in Appendix C.1 ("Comparison at matched accuracy", see new manuscript). Specifically, we compare the cumulative number of function evaluations and wall-clock time required to reach an accuracy threshold τ\tau. The results confirm that our total-query advantage persists at matched accuracy and show that our methods achieve a better balance in the number of evaluations while retaining an advantage in cumulative runtime. We thank the reviewer again for this helpful suggestion!

References

[1] Nazari et al. Stochastic regret guarantees for online zeroth- and first-order bilevel optimization.

[2] Peng et al. Provable faster zeroth-order method for bilevel optimization with optimal dependency on error and dimension.

AuthorsOpenReview ↗

Rebuttal (Part 2/2)

Weakness 2

We thank the reviewer for this comment. Our intention in the efficiency discussion was to highlight HF-ZOBA's flexibility in controlling its per-iteration evaluation cost, rather than claim an asymptotic improvement in batch-size scaling over ZO-SOGD. Indeed, with the number of directions fixed, both methods have per-iteration query costs that scale linearly with the batch size, so the difference is a constant-factor saving under the considered configurations.

Nevertheless, per-iteration evaluation cost is important, especially under limited evaluation budgets. It determines how many updates can be performed within a given budget and how flexibly an algorithm can allocate its evaluation resources. Compared with previous methods, ZOBA and HF-ZOBA offer greater flexibility by allowing the number of samples or directions per update to be adjusted. Our claim is therefore not that reducing per-iteration cost directly improves theoretical complexity, but that it provides greater flexibility under finite budgets. This has practical consequences. For instance, as illustrated by the adversarial experiment in Section 4, VRZSBO performs worse than the other approaches despite it achieves optimal theoretical complexity. This is due its dimension-dependent per-iteration cost that limits the number of updates under a fixed budget, preventing it from reaching the desired accuracy.

We have revised the efficiency discussion to clarify these distinctions. We also emphasized that theoretical complexity provides (asymptotically) total-query guarantees, whereas the per-iteration comparison characterizes the cost and flexibility of individual updates. Furthermore, we have added a synthetic experiment in the appendix comparing the cumulative function evaluations required to reach a common accuracy threshold (see our previous response to Weakness 1 and Question 1).

Weakness 3 and Question 2

We thank the reviewer for pointing this out. We have corrected the stepsize conditions. The correct conditions for point (II) of both Corollaries 3.5 and 3.7 are α1∈(1/2,1)\alpha_1\in(1/2,1), α2∈(1/3,1/2)\alpha_2\in(1/3,1/2), and α1≥2α2\alpha_1\geq 2\alpha_2. For Corollary 3.5, we additionally require α3>1\alpha_3>1. For Corollary 3.7(II), we require also α3≥α2+α4\alpha_3\geq\alpha_2+\alpha_4 and α4>1/2\alpha_4>1/2.

We clarify why these conditions ensure convergence. First, α1≥2α2\alpha_1\geq 2\alpha_2 guarantees the stepsize requirement in Theorems 3.4 and 3.6, namely γk=O(ϕˉzρk2)\gamma_k=O(\bar\phi_z\rho_k^2). Second, under these exponent conditions, the error terms in the proof of Corollary 3.5(II) (Appendix D) are summable. Recall that γk=γ(k+1)−α1\gamma_k=\gamma(k+1)^{-\alpha_1}, ρk=ρ(k+1)−α2\rho_k=\rho(k+1)^{-\alpha_2}, hk=h(k+1)−α3h_k=h(k+1)^{-\alpha_3}, and h^k=h^(k+1)−α4\hat h_k=\hat h(k+1)^{-\alpha_4}. The error terms in Theorem 3.4 are of orders γkhk2\gamma_k h_k^2, ρkhk2\rho_k h_k^2, ρk3\rho_k^3, ρk3hk2\rho_k^3 h_k^2, γk2\gamma_k^2, and γk2hk2\gamma_k^2 h_k^2. Those in Theorem 3.6 are of orders hk2ρk2h_k^2\rho_k^2, h^k2ρk2\hat h_k^2\rho_k^2, γkhk2\gamma_k h_k^2, h^k2γk\hat h_k^2\gamma_k, ρk3\rho_k^3, ρk3hk2\rho_k^3 h_k^2, γk2\gamma_k^2, hk2h^k2ρk2\frac{h_k^2}{\hat h_k^2}\rho_k^2, and hk2h^k2γk2\frac{h_k^2}{\hat h_k^2}\gamma_k^2. The stated exponent conditions ensure that all these terms are summable and the stepsize requirements hold with appropriate prefactors. Consequently, the existing convergence proofs remain valid under the corrected conditions. In the revised manuscript, we corrected such conditions. One example satisfying the conditions is α2=25\alpha_2=\frac{2}{5}, α1=45\alpha_1=\frac{4}{5}, α3=1110\alpha_3=\frac{11}{10} and, for Corollary 3.7, α4=35\alpha_4=\frac{3}{5}.

Weakness 4 and Question 3

We thank the reviewer for pointing this out. The correct condition is hk≤μG4(μG+2)CˉLϕˉvh^kρkh_k \leq \frac{\mu_G}{4 \sqrt{(\mu_G + 2) \bar{C}_L}} \sqrt{\bar{\phi}_v} \hat h_k \rho_k.

This correction does not require changes to the proof of the main theorem or affect the convergence results of the existing corollaries. The only adjustment concerns the smoothing-parameter choice in Corollary 3.7(III), where we now select h=μG4(μG+2)C~Lϕˉvh^2ρh = \frac{\mu_G}{4 \sqrt{(\mu_G + 2) \widetilde{C}_L}}\sqrt{\bar{\phi}_v}\hat{h}^2\rho. Since h^<1\hat{h}<1, the corrected condition is satisfied. The proof derivation and final result remain unchanged. We have corrected the condition and added further details in the revised manuscript.

Weakness 5 and Question 4

We thank the reviewer for pointing this out. We realized that the code initially included in the supplementary material was outdated. The figures reported in the paper were generated using an updated implementation that already incorporated the corrections identified by the reviewer. We have updated the supplementary material and added the result traces for the experiments reported in the main text.

We thank the reviewer again for taking the time to review our work and provide valuable feedback. Since the discussion period is nearing its end, we would be grateful if you could let us know whether our rebuttal has sufficiently addressed their concerns.

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

This paper proposes ZOBA, a single-loop zeroth-order bilevel optimization algorithm that leverages delayed information and function evaluation reuse to reduce computational costs. It also introduces HF-ZOBA, a Hessian-free variant to avoid explicit Hessian estimation. Convergence guarantees are established for nonconvex bilevel optimization with strongly convex lower-level objectives. Experiments demonstrate improved computational efficiency over existing baseline methods.

Critical strengths
  1. The proposed single-loop framework enables parallel computation and reduces function evaluations through information reuse.
  2. The theoretical analysis provides convergence guarantees, with HF-ZOBA achieving optimal complexity.
  3. Extensive comparisons with existing zeroth-order bilevel methods demonstrate promising computational efficiency.
Critical weaknesses
  1. The diminishing-stepsize conditions in Corollaries 3.5(II) and 3.7(II) are inconsistent: α1,α2∈(1/2,1)\alpha_1,\alpha_2\in(1/2,1) and α1≥2α2\alpha_1\geq 2\alpha_2 cannot hold simultaneously.
  2. The optimal complexity guarantee for HF-ZOBA needs clarification. The choice γ=c^γρ\gamma=\hat c_\gamma\rho in Corollary 3.7(III) appears inconsistent with the stepsize requirement γk=O(ϕˉzρk2)\gamma_k=O(\bar\phi_z\rho_k^2) in Theorem 3.6 unless additional parameter dependencies are specified.
  3. The theoretical assumptions are restrictive and do not directly cover several experiments. For example, the synthetic problem uses a quadratic outer objective that is not globally Lipschitz, while the adversarial attack involves nonsmooth and nonconvex objectives.
  4. The practical evaluation remains relatively limited, particularly regarding larger real-world black-box learning tasks.
  5. The paper contains lengthy blocks of text with insufficient paragraph breaks, making it difficult to read and follow. Better paragraph organization would improve readability.
Questions for authors
  1. How does the parameter selection in Corollary 3.7(III) satisfy the conditions of Theorem 3.6? Does resolving this affect the claimed optimal complexity?
  2. In the adversarial attack experiments, why are hyperparameters selected based on classification accuracy rather than the outer distortion objective? Could the authors compare distortion at matched attack success rates?
  3. How does the computational advantage change when parallel computing resources are limited?
3 comments
AuthorsOpenReview ↗

Rebuttal (Part 1/2)

We thank the reviewer for their useful feedback and comments. We particularly appreciate the recognition of our theoretical contributions, including the convergence guarantees established for our methods and the optimal complexity achieved by HF-ZOBA. We also thank the reviewer's positive remarks on our extensive comparisons with existing zeroth-order bilevel optimization methods, which demonstrate the promising computational efficiency of our approaches. In the following, we respond to their concerns.

Weaknesses 1-2 and Question 1. We thank the reviewer for pointing out this. We have corrected them in the revised manuscript. The correct conditions for point (II) for Corollary 3.5 are α1∈(1/2,1)\alpha_1\in(1/2,1), α2∈(1/3,1/2)\alpha_2\in(1/3,1/2), α1≥2α2\alpha_1\geq 2\alpha_2, α3>1\alpha_3 > 1 and for Corollary 3.7 are α1∈(1/2,1)\alpha_1\in(1/2,1), α2∈(1/3,1/2)\alpha_2\in(1/3,1/2), α3≥α2+α4\alpha_3\geq\alpha_2+\alpha_4 and α4>1/2\alpha_4>1/2. Note that these choices still allow us to establish convergence, since all error terms remain summable. In particular, recall that γk=γ(k+1)−α1\gamma_k=\gamma(k+1)^{-\alpha_1}, ρk=ρ(k+1)−α2\rho_k=\rho(k+1)^{-\alpha_2}, hk=h(k+1)−α3h_k=h(k+1)^{-\alpha_3} and h^k=h^(k+1)−α4\hat h_k=\hat h(k+1)^{-\alpha_4}. Note that the error terms appearing in the convergence bound of Theorem 3.4 are of order γkhk2\gamma_k h_k^2, ρkhk2\rho_k h_k^2, ρk3\rho_k^3, ρk3hk2\rho_k^3 h_k^2, γk2\gamma_k^2, and γk2hk2\gamma_k^2 h_k^2, and for Theorem 3.6, the terms are of order hk2ρk2h_k^2\rho_k^2, h^k2ρk2\hat h_k^2\rho_k^2, γkhk2\gamma_k h_k^2, h^k2γk\hat h_k^2\gamma_k, ρk3\rho_k^3, ρk3hk2\rho_k^3 h_k^2, γk2\gamma_k^2, hk2h^k2ρk2\frac{h_k^2}{\hat h_k^2}\rho_k^2, and hk2h^k2γk2\frac{h_k^2}{\hat h_k^2}\gamma_k^2. Consequently, the existing proof arguments remain valid under these corrected parameter conditions. Regarding point (III), the above corrections do not affect it. In particular, the choice γ=c^γρ\gamma=\hat{c}_\gamma\rho is compatible with the stepsize requirement γk=O(ϕˉzρk2)\gamma_k=O(\bar\phi_z\rho_k^2) in Theorem 3.6 by choosing ϕˉz=O(1/ρ)\bar\phi_z=O(1/\rho), as indicated in the proofs. This choice is admissible because ρ\rho is constant in point (III). In the rebuttal manuscript, we have corrected these and clarified the parameter choices.

Weaknesses 3-4. We agree with the reviewer that the theoretical assumptions are restrictive. We note, however, that this limitation is shared by the existing state-of-the-art literature, which adopts the same or even more restrictive settings (see, e.g., [1, 2, 3, 4]). We want to specify that the primary goal of our work was not to develop an algorithm under weaker theoretical assumptions but rather to study the cost problem of zeroth-order bilevel optimization algorithms with the goal of designing an efficient method by incorporating additional approximations while retaining optimal theoretical complexity. Regarding the experiments, our intention was to compare our approaches with SOTA methods in empirical scenarios where theoretical assumptions are not satisfied. This is important for understanding the theory–practice gap and identifying directions for further theoretical development. Indeed also previous works performed experiments that go beyond their assumptions exactly with this purpose. In particular, our results of showing that it is possible to build efficient zeroth-order bilevel algorithm can motivate future studies with the goal for instance of relaxing assumptions or applying these methods in large-scale black-box learning settings where efficiency is relevant and where usage of previous methods have not been explored exactly for the cost problem. For these reason such points are important direction for future research.

In revised manuscript, we clarified this in Limitation appendix and, following reviewer's suggestion, we included an additional synthetic experiment on a target objective that satisfies the theoretical assumptions in Appendix C3 (see new manuscript).

Weakness 5. We thank the reviewer for pointing this out. In the revised version, we restructured the paragraphs, making use of the additional page space to make equations more visible and split long passages whenever possible.

References

[1] Aghasi and Ghadimi. Fully zeroth-order bilevel programming via gaussian smoothing.

[2] Aghasi et al. Optimal zeroth-order bilevel optimization.

[3] Peng et al. Provable faster zeroth-order method for bilevel optimization with optimal dependency on error and dimension.

[4] Nazari et al. Stochastic regret guarantees for online zeroth- and first-order bilevel optimization.

AuthorsOpenReview ↗

Rebuttal (Part 2/2)

Question 2. Because in our universal adversarial attack experiments the final goal is to maximize the fraction of misclassified samples, while the distortion is explicitly controlled by the outer optimization objective. Moreover, as can be observed from the experimental results, the distortion does not increase substantially from its initial value for every considered methods and all methods achieve similar value for the distortion. This indicates that the approaches successfully control the distortion while improving the attack success rate.

Following the reviewer's suggestion, we compared the distortion achieved by the different methods to achieve different shared attack success rates. In particular, we compared the distortion, number of evaluations, and wall-clock time needed to reach each accuracy threshold within the budget (since our setting is the limited budget setting) for each method. We observed that all methods achieve similar distortion at each threshold. At high accuracy levels, the two-loop methods seem to reach them with slightly lower distortion. This is because ZOBA and HF-ZOBA make more progress in the first few iterations and thus jump to lower classification accuracy levels (i.e. higher success rate), which explains why their distortion stays constant across several thresholds. As the accuracy requested decreases, the differences in distortion between methods vanish. Regarding the number of evaluations required, we observed that ZOBA needs much more evaluations than other approaches because the construction of reliable Hessian estimates are costly in high dimension. HF-ZOBA, instead which avoids explicit Hessian estimation, needs a number of evaluations comparable to the best baseline ZMDSBA, which avoid the hessian cost by performing many inner-loop iterations. However looking at the wall-clock time we observe that HF-ZOBA is significantly faster than other methods thanks to parallelization and function value reuse, whereas ZMDSBA due to the two-loop structure, is poorly parallelizable. Overall, the results show that all method achieve comparable distortion level while in terms of evaluation cost, HF-ZOBA offers a better compromise between wall-clock time and number of evaluations. We found the result very interesting and we thank the reviewer for suggesting this comparison. We included the plot and further details in the main section of the revised manuscript (see Section 4 of new manuscript).

Question 3. We explored the limit setting of absence of parallelization in appendix (Figure 6). In this setting, we observe that our methods achieve runtime performance comparable to that of competing approaches, with the exception of ZDSBA, which requires more time. This behavior is expected, since the total number of function evaluations is the same across all methods. ZDSBA incurs additional computational overhead because it requires many inner iterations to compensate for the lack of multiple directions in gradient estimation. Opt-ZMDSBA and ZMDSBA partially mitigate this limitation by allowing larger batch sizes for estimating the Hessian cross-block and the gradient of the outer objective with respect to the second variable, thereby reducing the number of inner iterations. Despite incorporating additional approximations, our methods maintain comparable runtime costs in the sequential setting thanks to function-value reuse. Without this reuse, a larger number of function evaluations would be required (Figure 7). In contrast, other single-loop algorithms, as observed in Section 4, exhibit worse performance even in parallel setting due to their cost scaling. Thus, overall, our methods achieve lower wall-clock time in parallel settings while maintaining runtime performance comparable to competing two-loop methods in the fully sequential setting (with the exception of ZDSBA).

We would like to thank the reviewer again for their time and effort in reviewing our manuscript and for their useful feedback. As the discussion phase is coming to an end, we would appreciate knowing whether our response has adequately addressed their concerns.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.