- 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 , 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 are given as in one description, whereas Table 3 includes 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
-
Theorem 3.4 imposes conditions on the stepsizes and smoothing parameter, but the role of the batch sizes 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?
-
In Corollary 3.5 (II), the parameter conditions appear to be inconsistent. Specifically, implies , which contradicts the requirement . 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 .
-
In Corollary 3.5 (III), the relationship between the prescribed batch sizes, the quantities and , and the claimed oracle complexity is not entirely clear. Could the authors provide an explicit derivation showing how the prescribed batch sizes guarantee 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.
-
The authors state that the hyperparameters are selected through grid search, with the batch sizes and the numbers of random directions 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
Rebuttal (Part 2/3)
Question 1 and 3
The bound of Theorem 3.4 holds for any positive integers . 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 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
The terms depending on are collected in , since their contribution can be made negligible by choosing sufficiently small. The batch sizes and numbers of directions control the remaining error terms: larger and reduce them, and larger also allows larger stepsizes. While larger batches reduce the error terms, they also increase the per-iteration cost and thus to obtain good complexity (number of evaluations needed to reach ) 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 and are shorthand quantities introduced to simplify the statement. As shown in the proof (Appendix E.2), the constants of the error terms satisfy
Under the parameters of Corollary 3.5, the bound reads
where is the initialization. We choose to minimize the terms that do not depend on . The bound thus becomes
Choosing makes the last term at most . Since depends on and , this gives , as in the corollary. We then choose
so that . Thus, we have
that is,
Under this condition, . The total number of function evaluations is the number of iterations times the per-iteration cost, which is at most . Note that the cost and the error constants depend on the batch sizes and numbers of directions only through the products and . Hence the batch-size conditions in Corollary 3.5 (III) constrain these products, not the individual parameters.
Take and . Then, the total complexity is therefore
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 . 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 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.
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),
vk+1=vk−ρ(∇^zz2G(zk+1,xk)vk+∇^zF(zk+1,xk)) and xk+1=xk−γ(∇^xz2G(zk+1,xk)vk+1+∇^xF(zk+1,xk)) In this case, the Hessian approximation would have to be constructed from scratch. In particular, the function evaluations used to compute ∇^zG(zk,xk), namely, g(zk±hwk(i,j),xk,ξi,k), could not be reused, since the Hessian approximation would instead require evaluations at g(zk+1±hwk(i,j),xk,ξi,k). Without delayed information, the remaining opportunities for function-value reuse would be the common unperturbed evaluations of f (shared by ∇^zF(zk+1,xk) and ∇^xF(zk+1,xk)), as well as the common unperturbed evaluations of g shared by the two Hessian-block approximations, yielding a total saving of b1+b2 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ℓ1 function evaluations. Consequently, the total number of saved function evaluations due to reuse in ZOBA is 2b1ℓ1+b1+b2. The advantage is even more pronounced in HF-ZOBA. With delayed information, the finite-difference approximation of the Hessian-vector product (denoted by Hzzk) 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+1 depends on zk+1, while the update of xk+1 depends on both zk+1 and vk+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), α2∈(1/3,1/2), α1≥2α2, and α3>1. We clarify why these conditions ensure the claimed convergence. First, the condition α1≥2α2 guarantees the stepsize requirement in Theorem 3.4, namely γk=O(ϕˉzρk2). 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, ρk=ρ(k+1)−α2, and hk=h(k+1)−α3. In particular, the error terms appearing in the convergence bound are of the following orders: γkhk2, ρkhk2, ρk3, ρk3hk2, γk2, and γk2hk2. 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. Moreover, since α1<1, we have ∑k=0Kγk→∞ as K→∞, so the normalized initialization term also vanishes. It follows from the convergence bound that αK→0. 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).