- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper gives a single-loop finite-difference method and a matching lower bound for fixed finite .
Critical strengths
I find the main theoretical direction valuable. This paper resolves an important problem in the theory of bilevel optimization.
Critical weaknesses
-
For , recent work has already studied both single-loop first-order methods [1,2] and lower bounds [3]. Extending higher-order finite differences to general p seems expected.
-
The paper hides all condition-number dependence. This is essential for comparing stochastic NC-SC bilevel methods: recent lower bounds have strong -dependence. The authors should state explicit dependence on for both upper and lower bounds. Without explicit -dependence, it is difficult to assess whether the results in this paper are genuinely competitive with existing ones.
-
The proofs in the appendix are also unnecessarily difficult to verify. It introduces excessive notation and very long statements, such as Lemma B.9, which obscure the main argument. It looks like they were generated by AI instead of humans. The proof should be simplified.
-
There are no experiments to support the theoretical results in the paper.
[1] Sgha: A single-loop fully first-order algorithm for nonconvex-strongly-convex bilevel optimization.
[2] A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization.
[3] An $\Omega (\kappa_y^ 8\epsilon^{-6}) $ Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles.
Questions for authors
What are the -dependences in the upper and lower bounds?
4 comments
Response to Reviewer B8EJ: condition number, appendix, and experiments
We thank the reviewer for asking us to make the condition-number dependence and the scope of the theoretical claims explicit. We also clarify how we will improve the appendix and address the absence of experiments.
3. Explicit condition-number dependence
The submission emphasized the accuracy dependence and suppressed problem-constant factors for readability. We do not claim condition-number optimality. Let With the analysis and parameter choices stated in the paper, and with the initial-gap factor displayed separately, the upper bound is A sharper bookkeeping of the same algorithm gives a more informative comparison. The current proof upper-bounds the lower-level-gradient variance and the finite-difference variance by their maximum. Retaining the two variances separately in the Lyapunov argument and choosing the batch size and finite-difference radius accordingly gives For comparison, - obtains under a different, stronger smoothness accounting. At , our refined polynomial dependence is , matching the polynomial order while removing the logarithmic factor; for , the leading term has a smaller exponent. This comparison should be read together with the assumptions: their condition number includes Lipschitz constants for every order and their higher-order smoothness is imposed on both and , whereas ours uses only and imposes the order- condition only on .
Our lower-bound theorem is an accuracy lower bound for each fixed finite and does not claim a condition-number-optimal lower bound. In particular, it gives (and at ) with fixed problem constants. The result cited by the reviewer addresses the complementary condition-number axis; we therefore do not claim that our lower bound dominates it in .
4. Appendix readability and experiments
We agree that Lemma B.9 is difficult to verify in isolation, but this is a presentation issue rather than a counterexample to the result. It is a conditional-symmetry lemma: when the prior and the observation are invariant under a symmetry, the posterior inherits that symmetry. We use it only in Lemma B.10 to show that unrevealed rotation directions remain hidden under adaptive queries. We will tailor Lemma B.9 to that application, move the general measure-theoretic material to a separate subsection, and add an appendix roadmap, a notation table, and a short explanation of each lemma's role before its proof. We focus on these concrete readability changes rather than the reviewer's wording about AI.
The paper is primarily theoretical: the matching upper and lower bounds establish the worst-case accuracy dependence for the stated oracle model. We agree that experiments would complement this result. We will add a small controlled experiment on learning a regularization parameter for logistic regression in the appendix, with query-count accounting and comparisons to representative baselines.
I thank the authors for their responses. It is good that the upper bound in this paper improves prior work. But my concerns are not fully addressed, since (1) I still think that the lack of condition-number dependence in the lower bound is a weakness (2) I am still unsatisfied with the poor readability of the current manuscript. I strongly recommend that the author revise the article further. Therefore, I will keep my score.
Thank you very much for your reply. We have revised the manuscript following your suggestions and now present explicit condition-number bounds alongside the original results. We hope these additions address your concerns and would be very grateful if you could reconsider your assessment of our contribution.
-
Upper bound. We added the following bound at the end of Section 3, with the proof in Section A.7:
\kappa^{10}\epsilon^{-4} +\kappa^{8+4/p}\epsilon^{-4-2/p} \right).$$ Compared with the previous analysis, we simply keep the two variance terms in Lemma A.7 separate, rather than replacing them with a common upper bound, and then work out the $\kappa$-dependence of the constants. -
Lower bound. Proposition 4.4 now gives
\min\left\\{ \kappa^{2+2/p}\epsilon^{-4-2/p}, \\;\kappa^2\epsilon^{-6} \right\\} \right),$$ with the proof in Section B.7. The first term determines the bound when $\epsilon$ is small. We add a deterministic convex term $q(y)$. When $\kappa=1$, we have $q(y)\equiv0$, and the construction reduces to the original hard instance. The proof follows the original argument, with additional bounds on the derivatives of $q$ and checking that the hyperobjective gradient remains close to that of $P$. -
Appendix readability. We added short explanations before the main technical lemmas and improved their presentation. We merged the former Lemmas B.9 and B.10 into one lemma. We also divided the proof of the former Lemma B.11, now B.10, into three steps.
We initially focused on because, despite a long line of work on stochastic bilevel optimization, both and rates appear in the literature under different assumptions. The rates in prior work require stronger conditions, such as stochastic averaged smoothness or assumptions on stochastic Hessians. This gap has left it unclear whether bilevel optimization can achieve the same -dependence as single-level optimization. We show that the dependence is fundamental under the base smoothness and oracle assumptions, and that higher-order smoothness of the lower-level objective in alone reduces the complexity exponent towards .
Our upper and lower bounds explain this dependence from both sides. The upper bound shows how higher-order smoothness improves finite-difference approximations of Hessian- and Jacobian-vector products. The lower bound shows how the term can be hidden in the lower-level gradients while preserving its effect on the hypergradient.
Response to Reviewer B8EJ: novelty and lower bound
We thank the reviewer for identifying the two comparison points. We clarify both the chronology and the technical scope of our claims.
1. Novelty beyond the known p=1 results
The chronology is relevant. SGHA [Gu--Wu--Yang] first appeared on arXiv on August 24, 2026. SICO [Chen--Yang--Hu--Yang] first appeared on arXiv on October 5, 2026, after the ICLR submission deadline. More importantly, MRT--FD follows a different algorithmic route.
SGHA and SICO express lower-level optimality as a constraint: SGHA uses a regularized Lagrangian for ∇yg(x,y)=0, while SICO penalizes the lower-level optimality gap. MRT--FD instead uses the implicit hypergradient formula directly and tracks both y⋆(x) and the response z⋆(x) solving Hz⋆(x)=∇yf. It is a single-loop method with one update per variable per iteration, and it does not require the almost-sure boundedness of the primal iterates used by SGHA.
The higher-order extension is also not a formal change of stencil. MRT--FD applies the order-p finite differences only to gradients of g to estimate the actions Hz and Jz. Hence, higher-order smoothness is required only for g, whereas finite-difference extensions based on the penalty value ℓν(x)=minyg(x,y)+νf(x,y) involve both f and g and require higher-order smoothness of both. Thus our single-loop method works under lighter assumptions and provides a natural extension to the highly smooth setting.
2. Lower bound and relation to Gu--Wu--Yang
Gu--Wu--Yang first presented their lower bound on arXiv on September 18, 2026. Their result focuses on p=1 and improves the condition-number dependence. Our lower bound addresses a different question: the optimal accuracy dependence for every fixed finite smoothness order p under the fresh-randomness first-order oracle.
Our hard instance uses the comparison oracle in (22) and connects the bilevel problem to the classical stochastic nonconvex chain. We only need the hypergradient to be sufficiently close to the hard chain gradient, as in (27), rather than making the bilevel hyperobjective exactly equal to the target chain. The lower-level variable in our construction is scalar, dy=1, whereas the lower-level dimension in Gu--Wu--Yang grows with 1/ϵ. Therefore the additional ϵ−2 difficulty at p=1 persists even with a one-dimensional lower-level problem; it is caused by the bilevel structure and oracle information, rather than by the lower-level dimension. Our sine coupling has a tunable parameter δ and extends naturally to every finite p. We do not claim condition-number optimality, but we do establish the matching ϵ−4−2/p hierarchy in this oracle model.