acceptodds
Under review as a conference paper at ICLR 2027

Optimal Stochastic Bilevel Optimization with First-Order Oracles

Abstract

We study nonconvex–strongly-convex bilevel optimization under a stochastic first-order oracle. We introduce MRT-FD, a single-loop first-order method that simultaneously tracks the outer variable, the lower-level solution, and the auxiliary response arising from implicit differentiation of the hyperobjective. MRT-FD performs one update of each variable per iteration and approximates the second-order derivative actions using order- finite differences. For any fixed finite smoothness order in the lower variable, MRT-FD finds an -stationary point using stochastic gradient queries. We also prove a matching oracle lower bound. The lower-bound construction starts from a hard stochastic nonconvex chain under a stronger oracle and lifts it to a bilevel problem through a sinusoidal coupling with a scalar lower-level variable. Consequently, the dependence on is optimal for every fixed finite , closing the upper–lower complexity gap in this stochastic first-order oracle setting.

Primary area:
optimization
Keywords:
bilevel optimization, single-loop, first-order method

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_B8EJOpenReview ↗
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 Ω(ϵ−4−2/p)\Omega(\epsilon^{-4-2/p}) lower bound for fixed finite pp.

Critical strengths

I find the main theoretical direction valuable. This paper resolves an important problem in the theory of bilevel optimization.

Critical weaknesses
  1. For p=1p=1, recent work has already studied both single-loop first-order methods [1,2] and ϵ−6\epsilon^{-6} lower bounds [3]. Extending higher-order finite differences to general p seems expected.

  2. The paper hides all condition-number dependence. This is essential for comparing stochastic NC-SC bilevel methods: recent lower bounds have strong κy\kappa_y-dependence. The authors should state explicit dependence on κ\kappa for both upper and lower bounds. Without explicit κy\kappa_y-dependence, it is difficult to assess whether the results in this paper are genuinely competitive with existing ones.

  3. 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.

  4. 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 κy\kappa_y-dependences in the upper and lower bounds?

4 comments
AuthorsOpenReview ↗

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=1p=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\nabla_y g(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)y^\star(x) and the response z⋆(x)z^\star(x) solving Hz⋆(x)=∇yfH z^\star(x)=\nabla_y f. 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-pp finite differences only to gradients of gg to estimate the actions HzHz and JzJz. Hence, higher-order smoothness is required only for gg, whereas finite-difference extensions based on the penalty value ℓν(x)=min⁡yg(x,y)+νf(x,y)\ell_\nu(x)=\min_y\\{g(x,y)+\nu f(x,y)\\} involve both ff and gg 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=1p=1 and improves the condition-number dependence. Our lower bound addresses a different question: the optimal accuracy dependence for every fixed finite smoothness order pp 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=1d_y=1, whereas the lower-level dimension in Gu--Wu--Yang grows with 1/ϵ1/\epsilon. Therefore the additional ϵ−2\epsilon^{-2} difficulty at p=1p=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 δ\delta and extends naturally to every finite pp. We do not claim condition-number optimality, but we do establish the matching ϵ−4−2/p\epsilon^{-4-2/p} hierarchy in this oracle model.

AuthorsOpenReview ↗

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 κ=max⁡ℓf,ℓg,ρ1,Lp/μ.\kappa=\max\\{\ell_f,\ell_g,\rho_1,L_p\\}/\mu. With the analysis and parameter choices stated in the paper, and with the initial-gap factor displayed separately, the upper bound is O!(Δ0,κ14+7/p,ϵ−4−2/p).O\\!\left(\Delta_0\\,\kappa^{14+7/p}\\,\epsilon^{-4-2/p}\right). 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 O!(κ8+4/pϵ−4−2/p+κ10ϵ−4).O\\!\left(\kappa^{8+4/p}\epsilon^{-4-2/p}+\kappa^{10}\epsilon^{-4}\right). For comparison, F2SAF^2SA-pp obtains O~p(κ9+2/pϵ−4−2/p)\widetilde O_p(\kappa^{9+2/p}\epsilon^{-4-2/p}) under a different, stronger smoothness accounting. At p=2p=2, our refined polynomial dependence is κ10ϵ−5\kappa^{10}\epsilon^{-5}, matching the polynomial order while removing the logarithmic factor; for p>2p>2, the leading term has a smaller κ\kappa exponent. This comparison should be read together with the assumptions: their condition number includes Lipschitz constants for every order q≤pq\le p and their higher-order smoothness is imposed on both ff and gg, whereas ours uses only LpL_p and imposes the order-pp condition only on gg.

Our lower-bound theorem is an accuracy lower bound for each fixed finite pp and does not claim a condition-number-optimal lower bound. In particular, it gives Ω(ϵ−4−2/p)\Omega(\epsilon^{-4-2/p}) (and Ω(ϵ−6)\Omega(\epsilon^{-6}) at p=1p=1) with fixed problem constants. The Ω(κy8ϵ−6)\Omega(\kappa_y^8\epsilon^{-6}) result cited by the reviewer addresses the complementary condition-number axis; we therefore do not claim that our lower bound dominates it in κy\kappa_y.

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.

  1. 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.
  2. 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$.
  3. 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 ϵ\epsilon because, despite a long line of work on stochastic bilevel optimization, both ϵ−6\epsilon^{-6} and ϵ−4\epsilon^{-4} rates appear in the literature under different assumptions. The ϵ−4\epsilon^{-4} 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 ϵ\epsilon-dependence as single-level optimization. We show that the ϵ−6\epsilon^{-6} dependence is fundamental under the base smoothness and oracle assumptions, and that higher-order smoothness of the lower-level objective in yy alone reduces the complexity exponent towards 44.

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 uu can be hidden in the lower-level gradients while preserving its effect on the hypergradient.

Reviewer_F5w9OpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper consider a kind of nonconvex-strongly-convex bilevel optimization problem and proposes a single-loop first-order method by using order-p finite differences. Theoretically, the authors provide the convergence to ϵ\epsilon-stationary point and also the lower bound.

Critical strengths

Strengths:

  • The proposed algorithm is single-loop and does not depend on Hessian estimations
  • The paper provide the convergence gurangee without requiring the assumption on stochastic smoothness and additional order-pp smoothness condition on ff.
Critical weaknesses

Weaknesses:

  • The presentation is unclear, with inconsistent notation, missing definitions, and poor readability.

  • The convergence result in Theorem 1 does not appear to guarantee exact convergence to a stationary point.

  • The convergence analysis is not sufficiently sharp, and the dependence on the condition number is not characterized.

  • The paper provides no numerical experiments to validate the proposed method.

Questions for authors
  • Convergence guarantees: In Theorem 3.1, the proposed algorithm does not appear to converge exactly to a stationary point, since the last two terms in (18) do not vanish with KK. How are these two error terms controlled or made diminishing? Given above fact, it is unclear how the claimed complexity of O(ϵ−4−2/p)\mathcal{O}(\epsilon^{-4-2/p}) follows from (18).

  • Novelty. What are the main distinctions between this work and Chen et al. (2026b)? In particular, what are the key technical challenges in removing the additional order-(p) smoothness assumption on (f) compared with Chen et al. (2026b)?

  • Assumption. How can the assumptions required by the theoretical analysis be verified or justified in practical applications? In Assumption 2.1(iv), why is the condition on bounded Φ\Phi required?

  • Condition-number dependence: How does the sample complexity of the proposed algorithm depend on the condition number of the considered problem?

  • How does the proposed algorithm perform compared with existing methods in the numerical experiments?

3 comments
AuthorsOpenReview ↗

Response to Reviewer F5w9: assumptions, condition number, and experiments

We address the remaining questions about the assumptions, condition-number dependence, experiments, and presentation.

3. Assumptions and the lower-bounded hyperobjective

The condition inf⁡xΦ(x)>−∞\inf_x\Phi(x)>-\infty in Assumption 2.1(iv) is the standard lower-bounded-objective condition in nonconvex optimization. It makes the initial gap Φ(x0)−inf⁡xΦ(x)\Phi(x_0)-\inf_x\Phi(x) finite and gives a lower bound for the Lyapunov function used in the tracking proof. This is what allows the one-step descent inequalities to be telescoped; it is not an additional claim that every practical objective is globally bounded on all of Rdx\mathbb{R}^{d_x}.

The remaining assumptions are structural sufficient conditions for a worst-case theorem and can be checked analytically for common models. For example, strong convexity of the lower problem can be enforced by regularization; Lipschitz and fixed-order derivative bounds hold for standard softplus/logistic models with bounded features; and bounded-variance conditions follow from bounded data or an explicitly bounded oracle-noise model. The exact constants can be estimated from the model and data bounds. We will add these examples and explain the role of each assumption in the revised presentation.

4. Explicit condition-number dependence

For κ=max⁡ℓf,ℓg,ρ1,Lp/μ,\kappa=\max\\{\ell_f,\ell_g,\rho_1,L_p\\}/\mu, the current analysis and parameter choices give, with the initial-gap factor shown separately, O!(Δ0,κ14+7/p,ϵ−4−2/p).O\\!\left(\Delta_0\\,\kappa^{14+7/p}\\,\epsilon^{-4-2/p}\right). A sharper bookkeeping of the same algorithm keeps the lower-level-gradient variance and the finite-difference variance separate instead of replacing them by their maximum. Choosing the batch size and finite-difference radius accordingly gives O!(κ8+4/pϵ−4−2/p+κ10ϵ−4).O\\!\left(\kappa^{8+4/p}\epsilon^{-4-2/p}+\kappa^{10}\epsilon^{-4}\right). For comparison, F2SAF^2SA-pp obtains O~p(κ9+2/pϵ−4−2/p)\widetilde O_p(\kappa^{9+2/p}\epsilon^{-4-2/p}) under stronger smoothness accounting. At p=2p=2, our refined polynomial dependence is κ10ϵ−5\kappa^{10}\epsilon^{-5}, matching the polynomial order while removing the logarithmic factor; for p>2p>2, the leading term has a smaller κ\kappa exponent. The comparison depends on assumptions: their condition number includes Lipschitz constants for all orders q≤pq\le p and higher-order smoothness is imposed on both ff and gg, whereas ours uses only LpL_p and imposes the order-pp condition only on gg.

Our lower-bound theorem is an accuracy lower bound for each fixed finite pp with fixed problem constants. It gives Ω(ϵ−4−2/p)\Omega(\epsilon^{-4-2/p}), or Ω(ϵ−6)\Omega(\epsilon^{-6}) at p=1p=1, and does not claim condition-number optimality. The cited Ω(κy8ϵ−6)\Omega(\kappa_y^8\epsilon^{-6}) result addresses the complementary condition-number axis; we do not claim that our lower bound dominates it in κy\kappa_y.

5. Experiments and presentation

The submission is primarily theoretical, and the matching upper and lower bounds establish the worst-case accuracy dependence in the stated fresh-randomness oracle model. We agree that the lack of a numerical study is a useful evidence gap. We will add a controlled experiment on learning a regularization parameter for logistic regression, report both iteration counts and primitive-gradient query counts, and compare with representative first-order baselines. We will also add a compact notation table, place the accuracy-dependent parameter choices next to the convergence bound, and summarize the condition-number factors. These changes address the readability concern while leaving the theorem and its quantifiers unchanged.

AuthorsOpenReview ↗

Response to Reviewer F5w9: convergence and novelty

We thank the reviewer for raising the convergence concern and for asking us to clarify the distinction from Chen et al. (2026b). We address both points directly.

1. Theorem 3.1 and the last two terms in (18)

The bound in (18) is

\le C_\star\left(\frac{\Delta_0}{K}+\tau^{2p}+\frac{1}{m\tau^2}\right).$$ The three terms are, respectively, the optimization term, the order-$p$ finite-difference bias, and the sampling-variance term. **This is not the parameter regime used in Theorem 3.1.** The last two terms are error terms in an intermediate accuracy bound; they are not held fixed while $K$ tends to infinity. For each fixed $p$ and target accuracy $\epsilon$, Theorem 3.1 chooses the parameters in (17): $$\tau=\left(\frac{\epsilon^2}{3C_\star}\right)^{1/(2p)},\qquad m=\left\lceil\frac{3C_\star}{\epsilon^2\tau^2}\right\rceil,\qquad K=\left\lceil\frac{3C_\star(1+\Delta_0)}{\epsilon^2}\right\rceil.$$ With this accuracy-dependent choice, each of the three terms is at most $\epsilon^2/3$. Hence the returned point satisfies $\mathbb{E}\\|\nabla\Phi(x_R)\\|^2\le\epsilon^2$, and the oracle cost $(2p+5)mK$ is $O((1+\Delta_0)\epsilon^{-4-2/p})$ after suppressing problem-constant factors. If $\tau$ and $m$ are fixed and only $K$ increases, there is indeed an error floor; that observation is correct, but it is not the parameter regime or the conclusion of Theorem 3.1. We will place the parameter choice immediately next to the bound to make this quantifier explicit. **2. Novelty relative to Chen et al. (2026b)** We do not claim that the exponent $\epsilon^{-4-2/p}$ is new in isolation. The contribution is a different single-loop tracking route that obtains this rate under lighter assumptions and extends naturally to the highly smooth setting. Chen et al. introduce the perturbed value function $$\ell_\nu(x)=\min_y\\{g(x,y)+\nu f(x,y)\\}$$ and approximate the hypergradient by taking order-$p$ finite differences in $\nu$ of $\nabla_x\ell_\nu(x)$. Since both $f$ and $g$ enter $\ell_\nu$, their error control requires order-$p$ smoothness in $y$ for both functions. MRT--FD instead uses the implicit hypergradient directly. It tracks the moving lower solution $y^\star(x)$ and the response $z^\star(x)$ satisfying $H z^\star(x)=\nabla_y f$. The finite differences are applied only to gradients of $g$ to estimate the actions $Hz$ and $Jz$, so the additional order-$p$ smoothness is required only for $g$. Each iteration performs one update of $x$, $y$, and $z$; a joint moving-target Lyapunov argument controls their tracking errors without inner solves. This removes the logarithmic factor in the stated complexity and makes the higher-order extension natural. We will also add a compact notation table and a parameter-selection box to improve readability.

I thank the authors for their responses. After carefully considering the paper and their rebuttal, I have decided to maintain my original score.

Reviewer_r1CSOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

MRT-FD tracks the lower solution and an auxiliary linear-system solution in one loop, using finite differences of stochastic gradients instead of second-order products. For each fixed finite smoothness order p, the paper gives matching upper and lower query bounds of order epsilon^(-4-2/p) for expected squared hypergradient norm at most epsilon squared.

Critical strengths
  1. The main lower bound addresses a clear question that the existing upper rate alone does not answer: whether the smoothness-dependent exponent can be improved under the same first-order oracle assumptions (Theorem 4.3). Matching the epsilon exponent for every fixed finite p is the paper's most important contribution.
  2. The lower construction keeps the lower variable scalar while preserving strong convexity and the required smoothness constants. The sinusoidal coupling reduces the observable signal, yet keeps the hypergradient close to the hard nonconvex objective (Equations 25-28). This makes the source of the extra first-order difficulty clear.
  3. The argument explicitly handles the stronger comparison oracle's scalar and vector channels, arbitrary adaptive queries, and a final output that need not be a queried point (Lemmas B.11-B.13 and Corollary B.14). These are important details for transferring a lower bound beyond zero-respecting algorithms.
  4. The upper method has clear sampling and query accounting. Projection bounds the auxiliary vector, fresh batches avoid unsupported sample-reuse assumptions, and the analysis tracks both moving targets without requiring higher-order smoothness of the upper objective. The paper also explains its relation to existing linear-system tracking and finite-difference methods.
Critical weaknesses
  1. Optimality is specific to the fresh-randomness, bounded-variance oracle, and growing-dimensional worst-case class (an important scope limit, not a demonstrated error). The result does not establish the same barrier when a sample can be reused across points, samplewise derivatives are smooth, or the dimension is fixed. Add a compact comparison of oracle access, extra assumptions, and dimension requirements so readers do not interpret the title as covering all stochastic bilevel settings.
  2. The dependence on p and other problem constants is not summarized in a way that supports choosing the method's order (fixable presentation and scope issue). The theorem is optimal in epsilon for fixed p, but the stencil size and constants depend on p, while the construction's dimension also grows as accuracy increases. Give useful bounds or a small table for the stencil constants and total cost across p; increasing p toward infinity cannot be justified from the fixed-p epsilon exponent alone.
  3. The practical consequences of the single-loop design remain untested (fixable evidence limitation, not essential to the lower-bound result). The manuscript presents theory but no numerical study, and its accuracy rule uses growing batches, a shrinking difference radius, and parameter-dependent step sizes. A small controlled experiment should separate iteration count from gradient-query count, test finite-difference cancellation and noise, and compare against the stated first-order baselines before making practical efficiency claims.
Questions for authors

Please refer to the weaknesses.

1 comment
AuthorsOpenReview ↗

Response to Reviewer r1CS

We thank Reviewer r1CS for recognizing the value of the lower-bound direction and the single-loop method.

1. Scope of the lower bound

Our lower bound applies to the fresh-randomness oracle model and allows the dimension to grow with the target accuracy. We will add comparisons with other settings to the related-work discussion. We focus on this setting for two reasons.

(a) We aim to establish a lower bound for arbitrary adaptive randomized algorithms. For this algorithm class, lower bounds for single-level optimization in general fixed dimensions are not yet well understood. A partial answer for d=1d=1 is given by Chewi et al. (2023). We therefore focus on the high-dimensional setting. Interestingly, our bilevel hard instance uses a one-dimensional lower-level variable, dy=1d_y=1, showing that this complexity persists even when the lower-level problem is one-dimensional.

(b) We consider fresh randomness because, under stronger oracle assumptions, first-order bilevel algorithms already achieve O(ϵ−4)O(\epsilon^{-4}) complexity under lower-level averaged smoothness (Gu et al., 2026a) and O(ϵ−3)O(\epsilon^{-3}) complexity with variance reduction under per-sample smoothness at both levels (Yang et al., 2023), in the base case p=1p=1. These rates match the corresponding lower bounds for single-level nonconvex minimization. In the fresh-randomness setting, a long-standing complexity gap has remained, and our result shows that the complexity difference between single-level and bilevel optimization is fundamental.

2. Dependence on pp and stencil constants

The theorem is stated for fixed pp. Our stencil uses p+1p+1 nodes, and the per-iteration query count is (2p+5)m(2p+5)m, where mm is the batch size and is already included in the complexity bound. The pp-dependent constants ApA_p and CpC_p are bounded. Making the dependence on pp and the condition number κ=max⁡ℓf,ℓg,ρ1,Lp/μ\kappa=\max\\{\ell_f,\ell_g,\rho_1,L_p\\}/\mu explicit, the current analysis and parameter choices yield

O!(Δ0p,κ14+7/pϵ−4−2/p).O\\!\left(\Delta_0 p\\,\kappa^{14+7/p}\epsilon^{-4-2/p}\right).

For simplicity of presentation, the current analysis bounds the lower-level gradient variance and the finite-difference variance by their maximum in (65)--(67). By retaining the two variance bounds vv and vyv_y separately in the Lyapunov analysis and choosing the batch size and finite-difference radius accordingly, we obtain

O!(p,κ8+4/pϵ−4−2/p+p,κ10ϵ−4).O\\!\left(p\\,\kappa^{8+4/p}\epsilon^{-4-2/p}+p\\,\kappa^{10}\epsilon^{-4}\right).

When the smoothness order satisfies p≥qp\ge q, where

q=⌈2log⁡(1/ϵ)log⁡log⁡(1/ϵ)⌉,q=\left\lceil\frac{2\log(1/\epsilon)}{\log\log(1/\epsilon)}\right\rceil,

we can run our method with an order-qq stencil. Then the above complexity becomes

O!(ϵ−4log⁡2(1/ϵ)log⁡log⁡(1/ϵ))=O~(ϵ−4).O\\!\left(\frac{\epsilon^{-4}\log^2(1/\epsilon)}{\log\log(1/\epsilon)}\right)=\widetilde O(\epsilon^{-4}).

Thus, the stencil order can be capped at qq while attaining O~(ϵ−4)\widetilde O(\epsilon^{-4}) complexity, independently of further increases in pp.

We will add this discussion to the paper, together with a table reporting the number of stencil nodes and the values of ApA_p and CpC_p for representative pp.

3. Experiments

The paper is primarily theoretical. Our matching upper and lower bounds establish the optimal dependence of the worst-case oracle complexity on ϵ\epsilon for this problem class. We agree that experiments would complement this result by showing how the algorithm performs in practice. Given the space constraints in the main text, we will include experiments on learning regularization parameters for logistic regression in the appendix.

Chewi, Sinho, Sébastien Bubeck, and Adil Salim. On the complexity of finding stationary points of smooth functions in one dimension. ALT, 2023.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.