Pith. sign in

REVIEW 3 major objections 6 minor 70 references

First proof that bilevel needs κ_y^2 ε^{-2} oracle calls.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

NC-SC bilevel optimization provably needs Ω(κ_y^2 ε^-2) first-order oracle calls in the worst case, beating the minimax lower bound; a faster O~(κ_y^{7/2} ε^-2) fully first-order method is also given.

T0 review reviewed 2026-08-03 challenge →

load-bearing objection Fresh and possibly important lower-bound construction for bilevel optimization, but the main proof's zero-chain invariant is not established, so the headline result is not yet credible. the 3 major comments →

arxiv 2511.22331 v3 pith:K62BZML6 submitted 2025-11-27 math.OC cs.AIcs.LG

On the Condition Number Dependency in Bilevel Optimization

Lesi Chen , Jingzhao Zhang This is my paper
classification math.OC cs.AIcs.LG MSC 90C2690C3068Q17
keywords bilevel optimizationoracle complexitylower boundcondition numbernonconvex-strongly-convexzero-chainfirst-order methodsstationary point
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper aims to establish that nonconvex-strongly-convex (NC-SC) bilevel optimization is provably harder than the closely related NC-SC minimax optimization, when hardness is measured by dependence on the lower-level condition number κ_y. It constructs quadratic hard instances with a chain-like structure and proves that any deterministic first-order or Hessian-vector-product method needs Ω(κ_y^2 L_1 Δ ε^{-2}) oracle calls to find an ε-stationary point of the hyper-objective. Combined with an improved upper bound of O~(κ_y^{7/2} L_1 Δ ε^{-2}) achieved by running accelerated gradient descent on the lower level, this is the first proof of a genuine condition-number gap between bilevel and minimax problems. The lower bounds extend to second-order smooth, arbitrarily smooth, convex-strongly-convex, and stochastic settings, each showing a larger κ_y dependence than the corresponding minimax bound.

Core claim

On its own terms, the paper claims that the condition number of the lower-level problem enters bilevel complexity through two distinct mechanisms: the cost of approximating the lower-level solution y*(x), and the smoothness constant of the hyper-objective F(x), which inherits a factor of κ_y from the implicit function theorem. The hard instance couples these two sources by moving the auxiliary variable z into the lower level, designing g so that y*(x) = K^2 x and the lower-level sub-chain forces every step in x to traverse K intermediate y-coordinates, and tuning f so that the resulting hyper-objective is exactly a standard nonconvex zero-chain evaluated at a rescaled argument K^{3/2} x. The

What carries the argument

The load-bearing object is a bilevel zero-chain built on a quadratic, strongly-convex lower-level function. Its two components are the sub-chain whose inverse Hessian has entries of order K, forcing any algorithm to walk through the K coordinates of y to transmit information from x_i to x_{i+1}, and the coupling chosen so that after solving the lower level the hyper-objective reduces to the standard NC zero-chain evaluated at K^{3/2} x. The K^{3/2} rescaling, which comes from the lower-level solution z*(x) = K^2 x interacting with the upper-level cross-terms, is what doubles the κ_y exponent with respect to the minimax instance.

Load-bearing premise

The lower bound assumes an adversarial rotation of the hard instance that keeps the zero-chain structure: a deterministic algorithm cannot activate a new coordinate of x until it has walked through the full K-length chain of y coordinates, and it cannot use the gradients of g to jump ahead in that chain.

What would settle it

Construct a deterministic first-order algorithm that, on the hard quadratic instance (with κ_y large), needs fewer than c κ_y^2 ε^{-2} oracle calls to reach ε-stationarity; or exhibit a rotated version of the instance on which the algorithm can set coordinate t+2 of x nonzero without ever querying a point with a nonzero y^{(t)} coordinate. Either would break the zero-chain argument behind Theorem 3.1.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Any first-order or HVP-based method that treats bilevel problems through the standard hyper-gradient formula must pay Ω(κ_y^2 L_1 Δ ε^{-2}) oracle calls on smooth NC-SC instances, so the previous O~(κ_y^4 ε^{-2}) upper bounds are improvable only up to a √κ_y gap.
  • The same construction yields Ω(κ_y^{25/14} ε^{-12/7}) for second-order smooth problems and Ω(κ_y^{17/10} ε^{-8/5}) for arbitrarily smooth problems, showing the κ_y gap persists at higher smoothness orders.
  • For convex-strongly-convex and strongly-convex-strongly-convex bilevel problems the lower bounds become Ω(κ_y^{5/4} √(L_1 D/ε)) and Ω~(κ_y^{5/4} √κ_x), improving the previous κ_y^{1/4}.
  • Stochastic NC-SC bilevel problems inherit a worse dependence, Ω(κ_y^4 σ^2 Δ ε^{-4}) in the noisy case, so the condition number gap is not an artifact of determinism.
  • Because the lower bound holds on lower-level quadratic problems, gradient oracles and HVP oracles are equivalent on the hard instance, so the bound applies to both oracle models.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • A natural next test is whether the κ_y^{7/2} upper bound can be pushed to κ_y^2 by a method that avoids fully solving the lower level at every outer iteration, e.g., by reusing past lower-level iterates; the two-source mechanism suggests the smoothness-of-F term is the harder obstacle.
  • The construction's reliance on z*(x) = K^2 x suggests that problems with a nearly linear lower-level best response may be the genuine worst case for bilevel methods; problems whose y*(x) has small Jacobian norm could be strictly easier.
  • If the lower bound is tight, then practical bilevel pipelines on ill-conditioned inner problems (e.g., meta-learning with deep inner loops) should expect a κ_y^2 bottleneck and should use accelerated inner solvers; the experiment on hyperparameter tuning supports this.
  • The randomized lower bound is proved only for first-order smooth stochastic settings; extending it to second-order smooth or to the (S)C-SC settings is a concrete open problem that would need a new zero-chain that is robust to random rotations.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper studies deterministic and stochastic first-order oracle complexity for nonconvex-strongly-convex (NC-SC) bilevel optimization. The main claim is that, for finding an epsilon-stationary point of the hyper-objective F(x), any deterministic first-order or HVP-based algorithm requires Omega(kappa_y^2 L1 Delta epsilon^{-2}) oracle calls (Theorem 3.1), and similar strengthened lower bounds are claimed for second-order smooth, convex-strongly-convex, strongly-convex-strongly-convex, and stochastic settings. On the upper-bound side, the paper proposes F2BA+ and AccF2BA+, which replace the inner-loop gradient descent of the earlier F2BA method with accelerated gradient descent, yielding O~(kappa_y^{7/2} epsilon^{-2}) and O~(kappa_y^{13/4} epsilon^{-7/4}) complexities. The paper argues this establishes the first provable condition-number gap between NC-SC bilevel and NC-SC minimax optimization. Appendices contain the lower-bound constructions and proofs.

Significance. If the lower-bound technique is valid, the paper makes a substantial contribution: it identifies a genuine separation between bilevel and minimax optimization in condition-number dependence, and it improves the best known fully first-order upper bounds by a sqrt(kappa_y) factor. The hard-instance construction is concrete and the claimed upper bounds follow from a clean acceleration of the inner solver. The paper also usefully collects applications with quadratic lower-level problems. However, the central lower-bound proof currently contains a nontrivial gap in the zero-chain invariant for the paired (f,g) oracle, and one lemma used to extend the bounds to HVP algorithms is algebraically incorrect as stated. These issues are likely fixable, but they are load-bearing and must be addressed before the main claims can be accepted.

major comments (3)
  1. [Section 2.2, Lemma 2.1 and Eq. (7)] The claimed algebraic identities are incorrect. For g(x,y) = (1/2)y^T H y + x^T J y + b^T y, we have H v = nabla_y g(x,v) - J^T x - b, not H v = nabla_y g(x,v) + nabla_y g(0,0). The correct identity involves an extra x-dependent term obtainable from nabla_x g(0,x). In addition, Definition 2.4 defines the first-order oracle as O_fo(x,y) = (nabla_x f(x,y), nabla_y f(x,y)), i.e. it returns only gradients of f, yet the proof of Lemma 2.1 uses gradients of g. As written, the lemma and the claimed equivalence A_hvp = A_fo do not follow. Since Theorem 3.1 and its extensions assert the same lower bounds for HVP-based algorithms, this needs a corrected simulation argument with the appropriate oracle definition and an accounting of the number of first-order calls per HVP query.
  2. [Appendix C, proof of Theorem 3.1, zero-chain invariant] The proof asserts that, because of the zero-chain structure of Eq. (8), the oracle response O(w_t) depends only on (u^0,...,u^t) once the vectors u^t_x, u^t_z, u^t_y are chosen orthogonal to the past iterates x_i, z_i, y_i respectively. This is not sufficient. The rotation conditions enforce only same-variable orthogonality: u^t_x is orthogonal to previous x_i, u^t_z to previous z_i, and u^t_y to previous y_i. They do not enforce cross-orthogonality such as u^s_x being orthogonal to z_t. But the gradient of the lower-level function has nabla_x g = -z and nabla_z g = z/K^2 - x, so a component of z_t along a not-yet-activated u^s_x would immediately appear in nabla_x g, and a component of x_t along u^s_z would appear in nabla_z g. The proof does not state or prove a joint invariant that rules this out, nor does it give a dimension count showing that the required cross-orthogonality constra
  3. [Abstract versus Theorem 3.1] There are serious numerical inconsistencies in the stated exponents. The abstract supplied for the manuscript states a first-order lower bound of Omega(kappa_y^{5/2} epsilon^{-2}), while the full-text abstract and Theorem 3.1 state Omega(kappa_y^2 epsilon^{-2}). The full-text abstract states a second-order lower bound of Omega(kappa_y^{13/4} epsilon^{-12/7}), while Theorem 3.1 (p=2) states Omega(kappa_y^{25/14} epsilon^{-12/7}); the preceding 'ABSTRACT' block states yet another value, Omega(kappa_y^{31/14} epsilon^{-12/7}). Similar discrepancies appear for the convex-strongly-convex lower bound (kappa_y^{5/4} in Theorem 3.2 versus kappa_y^{3/2} in the abstract block). The authors must align the abstract, introduction, tables, and theorems, and state which exponent is the actual result.
minor comments (6)
  1. [Lemma 3.2] The lemma lists only two numbered items, but its proof says 'Finally, item 3 immediately follows...'. Either an item is missing or the reference should be corrected.
  2. [Definition 4.1] The second-order stationary condition is written as nabla^2 F(x) >= -sqrt(rho_F) epsilon I_d. Dimensional analysis and the subsequent use in Lemma 4.6 suggest the intended condition is nabla^2 F(x) >= -sqrt(rho_F epsilon) I_d.
  3. [Theorem 4.2] The theorem statement says Algorithm 3 finds an 'epsilon-stationary point', but the supporting Lemma 4.6 guarantees an 'epsilon-second-order stationary point'. Please make the statements consistent.
  4. [Algorithm 3] Lines 9-10 of Algorithm 3 are garbled: the notation xi_t ~ B(r) is undefined, and the restart update 'x_{-1}=x_0=x_t + xi_t 1_{...}' is not a well-formed assignment. This needs to be cleaned up, preferably by matching the corresponding presentation in [14].
  5. [Definitions 2.4 and 2.7] Definition 2.4 as written returns only gradients of f, which is inconsistent with the algorithm class and with the proof of Lemma 2.1. Definition 2.7 states that the HVP algorithm follows 'protocol (5)', but it should refer to protocol (6).
  6. [Abstract] There is a typographical error 'Chen el al.' in the second line of the abstract; it should be 'Chen et al.'.

Circularity Check

0 steps flagged

No significant circularity: the lower and upper bounds follow from explicit hard-instance constructions and from standard/prior published lemmas used as black boxes, not from fitting or restating the target result.

full rationale

The paper's central claims are derived by constructing explicit hard instances and by applying standard oracle-complexity arguments, not by fitting parameters to the answer. The deterministic lower bound (Theorem 3.1) is built from the NC zero-chain (Definition 3.2), the lower-level sub-chain h_sc (Eq. 10), and the coupling h(z,y) (Eq. 9); Lemma 3.3 computes the hyper-objective exactly as K^3/2 * sum (x_i - x_{i+1})^2 (Eq. 12), and the argument then counts chain activations (Appendix C). No step assumes the claimed Omega(kappa_y^2 epsilon^{-2}) bound. The stochastic bound (Theorem 3.4) similarly sets z*(x) = kappa_y x so that F(x) equals a scaled known stochastic zero-chain, then chooses beta, T, p via Eqs. (38)-(40); this is parameter setting, not result renaming. The upper bound (Theorem 4.1) is a composition of the standard AGD guarantee (Lemma 4.2), a smoothness bound for F (Lemma 4.3), and the F2BA outer-loop lemma from the authors' earlier published work (Lemma 4.4). That cited lemma has stated assumptions independent of the target complexity and is used as a legitimate black box, so the self-citation is not circular. Likewise, Lemma B.1 (from [37]) is a matrix-entry bound used to choose a_K and b_K; it concerns an explicit matrix and does not state the target bound. The only caveat is a proof-verification concern in Appendix C: the combined-oracle zero-chain invariant is asserted ('from the zero-chain structure of Eq. (8)') without fully demonstrating the cross-orthogonality needed to rule out shortcuts; that is a completeness/correctness issue, not an instance of the derivation reducing to its own inputs.

Axiom & Free-Parameter Ledger

5 free parameters · 4 axioms · 0 invented entities

No data-fitting parameters appear. The listed quantities are proof constants for the hard instances. The paper's lower bounds are not circular, but they lean on several prior lemmas, two of which are self-authored.

free parameters (5)
  • a_K, b_K = a_K=(1/K)(1-B11/B1K), b_K=K/B1K
    Chosen in Lemma 3.3 to make the lower-level-induced H(x) equal K^3/2 Σ(x_i-x_{i+1})^2; not empirical, but hand-tuned proof constants.
  • K (inner chain length) = sqrt(L1/(\barℓ1 μ_y))
    Sets the lower-level condition number and ensures K≥10; chosen to balance strong convexity and smoothness.
  • β (rescaling) = 4\barℓ1 ε/(K^{3/2}ν^{3/4} L1)
    Scaling of the rotated hard instance so the hyper-gradient norm stays above ε for t≤n'.
  • T (chain length) = largest integer with F(0)-inf F ≤ Δ
    Maximizes number of activations subject to the initial suboptimality constraint.
  • ν, r = ν=r=1 (p=1); ν=... for p=2; ν=β^2 L_* for p≥3
    Regularizer parameters chosen to match the required order of smoothness.
axioms (4)
  • standard math Zero-chain lower-bound framework (Carmon et al. [11,12])
    Used to translate chain length into oracle lower bounds; assumed without reproof in Appendix C.
  • standard math Lemma B.1: inverse of I_K/K^2 + A_K has entries B_{1,i} between 0.1K and 20K
    Imported from Li et al. [37, Lemma 7]; determines |a_K|≤20, |b_K|≤10 in Lemma 3.3.
  • domain assumption F2BA outer-loop guarantee (Chen et al. [14, Theorem 4.1])
    Used as black box for Lemma 4.4 to convert inner-solver accuracy and Lipschitz constants into outer complexity; self-cited prior result.
  • standard math Stochastic zero-chain properties (Arjevani et al. [7, Lemma 6,7])
    Used in Theorem 3.4 to guarantee large gradients for any randomized algorithm querying the stochastic oracle.

reviewed 2026-08-03 · how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Condition Number Dependency in Bilevel Optimization." pith.science (2026). https://pith.science/paper/K62BZML6

@misc{pith2026251122331,
  author       = {Pith},
  title        = {Pith review of: On the Condition Number Dependency in Bilevel Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/K62BZML6}},
  note         = {Machine review of arXiv:2511.22331}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Bilevel optimization minimizes an objective function, defined by an upper-level problem whose feasible region is the solution of a lower-level problem. We study the oracle complexity of finding an $\epsilon$-stationary point with first-order methods when the upper-level problem is nonconvex, and the lower-level problem is strongly convex. Recent works (Ji et al., ICML 2021; Arbel and Mairal, ICLR 2022; Chen et al., JMLR 2025) achieve a $\tilde{\mathcal{O}}(\bar \kappa_y^4 \epsilon^{-2})$ upper bound that is near-optimal in $\epsilon$, which can be reduced to $\tilde{\mathcal{O}}(\bar \kappa_y^{7/2} \epsilon^{-2})$ by a naive application of Nesterov acceleration in the inner loop, where $\bar \kappa_y$ is the global condition number. However, the optimal dependency on the condition number is unknown. In this work, we establish a new $\Omega(\kappa_y^{5/2} \epsilon^{-2})$ lower bound, where $\kappa_y < \bar \kappa_y$ is the lower-level condition number that is of the same order as $\bar \kappa_y$ when the smoothness constants are $\mathcal{O}(1)$. Our lower bound establishes the first provable gap in terms of condition number dependency between bilevel problems and minimax problems in this setup. Our lower bounds can be extended to various settings, including high-order smooth functions, stochastic oracles, and convex hyper-objectives: (1) For second-order and arbitrarily smooth problems, we show lower bounds of $\Omega({\kappa_y^{31/14}} \epsilon^{-12/7})$ and $\Omega(\kappa_y^{21/10} \epsilon^{-8/5})$, respectively. (2) For convex-strongly-convex problems, we improve the previously best lower bound (Ji and Liang, JMLR 2022) from $\Omega(\kappa_y /\sqrt{\epsilon})$ to $\Omega(\kappa_y^{3/2} / \sqrt{\epsilon})$. (3) For smooth stochastic problems, we also show a lower bound of $\Omega(\kappa_y^4 \epsilon^{-4})$.

Figures

Figures reproduced from arXiv: 2511.22331 by Jingzhao Zhang, Lesi Chen.

Figure 1
Figure 1. Figure 1: (a) The construction for NC-SC minimax lower bound [ [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Performances of different algorithms when learning the optimal regularization. [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

70 extracted references · 3 linked inside Pith

  1. [1]

    Lower bounds for higher-order convex optimization

    Naman Agarwal and Elad Hazan. Lower bounds for higher-order convex optimization. InCOLT, pages 774–792. PMLR, 2018

    2018

  2. [2]

    Fully zeroth-order bilevel programming via gaussian smoothing

    Alireza Aghasi and Saeed Ghadimi. Fully zeroth-order bilevel programming via gaussian smoothing. Journal of Optimization Theory and Applications, 205(2):31, 2025

    2025

  3. [3]

    Optimal zeroth-order bilevel optimization.arXiv preprint arXiv:2510.03646, 2025

    Alireza Aghasi, Jeongyeol Kwon, and Saeed Ghadimi. Optimal zeroth-order bilevel optimization.arXiv preprint arXiv:2510.03646, 2025

    arXiv 2025

  4. [4]

    Amortized implicit differentiation for stochastic bilevel optimization

    Michael Arbel and Julien Mairal. Amortized implicit differentiation for stochastic bilevel optimization. InICLR, 2022

    2022

  5. [5]

    Oracle complexity of second-order methods for smooth convex optimization.Mathematical Programming, 178(1):327–360, 2019

    Yossi Arjevani, Ohad Shamir, and Ron Shiff. Oracle complexity of second-order methods for smooth convex optimization.Mathematical Programming, 178(1):327–360, 2019

    2019

  6. [6]

    Duchi, Dylan J

    Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Ayush Sekhari, and Karthik Sridharan. Second-order information in non-convex stochastic optimization: Power and limitations. InCOLT, 2020

    2020

  7. [7]

    Duchi, Dylan J

    Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization.Mathematical Programming, 199(1):165–214, 2023

    2023

  8. [8]

    Stability and generalization of bilevel programming in hyperparameter optimization

    Fan Bao, Guoqiang Wu, Chongxuan Li, Jun Zhu, and Bo Zhang. Stability and generalization of bilevel programming in hyperparameter optimization. InNeurIPS, 2021

    2021

  9. [9]

    Stackelberg games for adversarial prediction problems

    Michael Brückner and Tobias Scheffer. Stackelberg games for adversarial prediction problems. In SIGKDD, 2011

    2011

  10. [10]

    convex until proven guilty

    Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. “convex until proven guilty”: Dimension- free acceleration of gradient descent on non-convex functions. InICML, 2017. 19

    2017

  11. [11]

    Duchi, Oliver Hinder, and Aaron Sidford

    Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i.Mathematical Programming, 184(1):71–120, 2020

    2020

  12. [12]

    Duchi, Oliver Hinder, and Aaron Sidford

    Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points II: first-order methods.Mathematical Programming, 185(1):315–355, 2021

    2021

  13. [13]

    On finding small hyper-gradients in bilevel optimization: Hardness results and improved analysis

    Lesi Chen, Jing Xu, and Jingzhao Zhang. On finding small hyper-gradients in bilevel optimization: Hardness results and improved analysis. InCOLT, 2024

    2024

  14. [14]

    Near-optimalnonconvex-strongly-convexbileveloptimization with fully first-order oracles.JMLR, 2025

    LesiChen, YaohuaMa, andJingzhaoZhang. Near-optimalnonconvex-strongly-convexbileveloptimization with fully first-order oracles.JMLR, 2025

    2025

  15. [15]

    SPABA: A single-loop and probabilistic stochastic bilevel algorithm achieving optimal sample complexity

    Tianshu Chu, Dachuan Xu, Wei Yao, and Jin Zhang. SPABA: A single-loop and probabilistic stochastic bilevel algorithm achieving optimal sample complexity. InICML, 2024

    2024

  16. [16]

    A framework for bilevel optimization that enables stochastic and global variance reduction algorithms

    Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. InNeurIPS, 2022

    2022

  17. [17]

    A lower bound and a near-optimal algorithm for bilevel empirical risk minimization

    Mathieu Dagréou, Thomas Moreau, Samuel Vaiter, and Pierre Ablin. A lower bound and a near-optimal algorithm for bilevel empirical risk minimization. InAISTATS, 2024

    2024

  18. [18]

    Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator

    Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. InNeurIPS, 2018

    2018

  19. [19]

    Bilevel programming for hyperparameter optimization and meta-learning

    Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. InICML, 2018

    2018

  20. [20]

    Escaping from saddle points—online stochastic gradient for tensor decomposition

    Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points—online stochastic gradient for tensor decomposition. InCOLT, 2015

    2015

  21. [21]

    Approximation methods for bilevel programming.arXiv preprint arXiv:1802.02246, 2018

    Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming.arXiv preprint arXiv:1802.02246, 2018

    Pith/arXiv arXiv 2018

  22. [22]

    Generative adversarial networks.Communications of the ACM, 63(11): 139–144, 2020

    Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks.Communications of the ACM, 63(11): 139–144, 2020

    2020

  23. [23]

    On the iteration complexity of hypergradient computation

    Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complexity of hypergradient computation. InICML, 2020

    2020

  24. [24]

    Lower complexity bounds of finite-sum optimization problems: The results and construction.JMLR, 25(2):1–86, 2024

    Yuze Han, Guangzeng Xie, and Zhihua Zhang. Lower complexity bounds of finite-sum optimization problems: The results and construction.JMLR, 25(2):1–86, 2024

    2024

  25. [25]

    A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic.SIAM Journal on Optimization, 33(1):147–180, 2023

    Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic.SIAM Journal on Optimization, 33(1):147–180, 2023

    2023

  26. [26]

    Efficiently escaping saddle points in bilevel optimization.JMLR, 26(1):1–61, 2025

    Minhui Huang, Xuxing Chen, Kaiyi Ji, Shiqian Ma, and Lifeng Lai. Efficiently escaping saddle points in bilevel optimization.JMLR, 26(1):1–61, 2025

    2025

  27. [27]

    Lower bounds and accelerated algorithms for bilevel optimization.JMLR, 24(22):1–56, 2022

    Kaiyi Ji and Yingbin Liang. Lower bounds and accelerated algorithms for bilevel optimization.JMLR, 24(22):1–56, 2022

    2022

  28. [28]

    Bilevel optimization: Convergence analysis and enhanced design

    Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. InICML, 2021

    2021

  29. [29]

    Beyond value functions: Single-loop bilevel optimization under flatness conditions

    Liuyuan Jiang, Quan Xiao, Lisha Chen, and Tianyi Chen. Beyond value functions: Single-loop bilevel optimization under flatness conditions. InNeurIPS, 2025

    2025

  30. [30]

    Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. InCOLT, 2018. 20

    2018

  31. [31]

    A near-optimal algorithm for stochastic bilevel optimization via double-momentum

    Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. InNeurIPS, 2021

    2021

  32. [32]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2016

    2016

  33. [33]

    Actor-critic algorithms.NeurIPS, 12, 1999

    Vijay Konda and John Tsitsiklis. Actor-critic algorithms.NeurIPS, 12, 1999

    1999

  34. [34]

    Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D. Nowak. A fully first-order method for stochastic bilevel optimization. InICML, 2023

    2023

  35. [35]

    On the complexity of first-order methods in stochastic bilevel optimization

    Jeongyeol Kwon, Dohyun Kwon, and Hanbaek Lyu. On the complexity of first-order methods in stochastic bilevel optimization. InICML, 2024

    2024

  36. [36]

    Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D. Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. InICLR, 2024

    2024

  37. [37]

    Complexity lower bounds for nonconvex- strongly-concave min-max optimization

    Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadbabaie. Complexity lower bounds for nonconvex- strongly-concave min-max optimization. InNeurIPS, 2021

    2021

  38. [38]

    Restarted nonconvex accelerated gradient descent: No more polylogarithmic factor in the in theO(ϵ−7/4)complexity.JMLR, 2023

    Huan Li and Zhouchen Lin. Restarted nonconvex accelerated gradient descent: No more polylogarithmic factor in the in theO(ϵ−7/4)complexity.JMLR, 2023

    2023

  39. [39]

    PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization

    Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. InICML, 2021

    2021

  40. [40]

    Tianyi Lin, Chi Jin, and Michael I. Jordan. Near-optimal algorithms for minimax optimization. In COLT, 2020

    2020

  41. [41]

    Bome! bilevel optimization made easy: A simple first-order approach

    Bo Liu, Mao Ye, Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made easy: A simple first-order approach. InNeurIPS, 2022

    2022

  42. [42]

    A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton

    Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. InICML, 2020

    2020

  43. [43]

    A value-function-based interior-point method for non-convex bi-level optimization

    Risheng Liu, Xuan Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A value-function-based interior-point method for non-convex bi-level optimization. InICML, 2021

    2021

  44. [44]

    Towards gradient-based bilevel optimization with non-convex followers and beyond

    Risheng Liu, Yaohua Liu, Shangzhi Zeng, and Jin Zhang. Towards gradient-based bilevel optimization with non-convex followers and beyond. InNeurIPS, 2021

    2021

  45. [45]

    First-order penalty methods for bilevel optimization.SIAM Journal on Optimization, 34(2):1937–1969, 2024

    Zhaosong Lu and Sanyou Mei. First-order penalty methods for bilevel optimization.SIAM Journal on Optimization, 34(2):1937–1969, 2024

    1937

  46. [46]

    Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions

    Matthew Mackay, Paul Vicol, Jonathan Lorraine, David Duvenaud, and Roger Grosse. Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions. InICLR, 2019

    2019

  47. [47]

    Arkadi Nemirovski. Prox-method with rate of convergence O(1/t)for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems.SIAM Journal on Optimization, 15(1):229–251, 2004

    2004

  48. [48]

    Problem complexity and method efficiency in optimization

    Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983

    1983

  49. [49]

    A method for solving the convex programming problem with convergence rateO(1/k2)

    Yurii Nesterov. A method for solving the convex programming problem with convergence rateO(1/k2). InDokl akad nauk Sssr, volume 269, page 543, 1983

    1983

  50. [50]

    Cubic regularization of newton method and its global performance

    Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical programming, 108(1):177–205, 2006. 21

    2006

  51. [51]

    Lectures on convex optimization

    Yurii Nesterov et al. Lectures on convex optimization. 137, 2018

    2018

  52. [52]

    Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems.Mathematical Programming, 185(1):1–35, 2021

    Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems.Mathematical Programming, 185(1):1–35, 2021

    2021

  53. [53]

    ScaleBiO: Scalable bilevel optimization for llm data reweighting.arXiv preprint arXiv:2406.19976, 2024

    Rui Pan, Jipeng Zhang, Xingyuan Pan, Renjie Pi, Xiaoyu Wang, and Tong Zhang. ScaleBiO: Scalable bilevel optimization for llm data reweighting.arXiv preprint arXiv:2406.19976, 2024

    Pith/arXiv arXiv 2024

  54. [54]

    Kakade, and Sergey Levine

    Aravind Rajeswaran, Chelsea Finn, Sham M. Kakade, and Sergey Levine. Meta-learning with implicit gradients. InNeurIPS, volume 32, 2019

    2019

  55. [55]

    On penalty-based bilevel gradient descent method

    Han Shen and Tianyi Chen. On penalty-based bilevel gradient descent method. InICML, 2023

    2023

  56. [56]

    Communication networks: An optimization, control and stochastic networks perspective

    Rayadurgam Srikant and Lei Ying. Communication networks: An optimization, control and stochastic networks perspective. 2014

    2014

  57. [57]

    Marktform und gleichgewicht

    Heinrich von Stackelberg. Marktform und gleichgewicht. 1934

    1934

  58. [58]

    Efficient first order method for saddle point problems with higher order smoothness.SIAM Journal on Optimization, 34(4):3342–3370, 2024

    Nuozhou Wang, Junyu Zhang, and Shuzhong Zhang. Efficient first order method for saddle point problems with higher order smoothness.SIAM Journal on Optimization, 34(4):3342–3370, 2024

    2024

  59. [59]

    Accelerating inexact hypergradient descent for bilevel optimization.arXiv preprint arXiv:2307.00126, 2023

    Haikuo Yang, Luo Luo, Chris Junchi Li, and Michael I Jordan. Accelerating inexact hypergradient descent for bilevel optimization.arXiv preprint arXiv:2307.00126, 2023

    Pith/arXiv arXiv 2023

  60. [60]

    Provably faster algorithms for bilevel optimization

    Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. In NeurIPS, 2021

    2021

  61. [61]

    AchievingO(ϵ−1.5)complexity in hessian/jacobian-free stochastic bilevel optimization

    Yifan Yang, Peiyao Xiao, and Kaiyi Ji. AchievingO(ϵ−1.5)complexity in hessian/jacobian-free stochastic bilevel optimization. InNeurIPS, 2023

    2023

  62. [62]

    Graph neural networks inspired by classical iterative algorithms

    Yongyi Yang, Tang Liu, Yangkun Wang, Jinjing Zhou, Quan Gan, Zhewei Wei, Zheng Zhang, Zengfeng Huang, and David Wipf. Graph neural networks inspired by classical iterative algorithms. InICML, 2021

    2021

  63. [63]

    Fast two-time-scale stochastic gradient method with applications in reinforcement learning

    Sihan Zeng and Thinh Doan. Fast two-time-scale stochastic gradient method with applications in reinforcement learning. InCOLT, 2024

    2024

  64. [64]

    A two-time-scale stochastic optimization framework with applications in control and reinforcement learning.SIAM Journal on Optimization, 34(1):946–976, 2024

    Sihan Zeng, Thinh Doan, and Justin Romberg. A two-time-scale stochastic optimization framework with applications in control and reinforcement learning.SIAM Journal on Optimization, 34(1):946–976, 2024

    2024

  65. [65]

    On lower iteration complexity bounds for the convex concave saddle point problems.Mathematical Programming, 194(1):901–935, 2022

    Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the convex concave saddle point problems.Mathematical Programming, 194(1):901–935, 2022

    2022

  66. [66]

    The complexity of nonconvex- strongly-concave minimax optimization

    Siqi Zhang, Junchi Yang, Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of nonconvex- strongly-concave minimax optimization. InUAI, 2021. 22 A Examples with Lower-Level Quadratics This section provides a collection of (S)C-SC and NC-SC bilevel optimization applications in which the lower-level function is quadratic. A.1 Convex-Strongly-Conv...

    2021

  67. [67]

    Attheinitialization w0 = (x0,z 0,y 0) = (0, 0, 0), we know from the zero-chain structure of Eq

    Pick( u0 x,u 0 z,u 0 y)asthreearbitraryunitvectorsin R2n. Attheinitialization w0 = (x0,z 0,y 0) = (0, 0, 0), we know from the zero-chain structure of Eq. (8) that the oracle responseO(w0)only depends on (u0 x,u 0 z,u 0 y), which is already fixed. Since the algorithm is deterministic, we know the next query w1 = (x1,y 1,z 1)is also fixed

  68. [68]

    For anyt = 1,· · ·, n, we repeat the following process: We computewt = (xt,z t,y t)from the algorithm, and picku t x,u t z andu t y as the unit vectors satisfying ⟨ut x,u i x⟩=⟨u t z,u i z⟩=⟨u t y,u i y⟩= 0,∀i= 1,· · ·, t−1; and⟨u t x,x i⟩=⟨u t z,z i⟩=⟨u t y,y i⟩= 0,∀i= 1,· · ·, t; We know such vectorsut x,u t z,andu t y always exist in the spaceR2n since...

  69. [69]

    Next, we ensure thatf has L2-Lipschitz continuous Hessians by setting ν= β ¯ℓ1L2 L1ℓ2 .(27) Combining with the setting ofβin Eq

    The case p = 2.We let r = 1, then the conditionνr 3−p ≤ 1still holds if ν≤ 1, which means both f and g have L1-Lipschitz continuous gradients. Next, we ensure thatf has L2-Lipschitz continuous Hessians by setting ν= β ¯ℓ1L2 L1ℓ2 .(27) Combining with the setting ofβin Eq. (24), we can solve that ν= 4ϵ/K 3/2 4/7 ¯ℓ1/L1 8/7 (L2/ℓ2)4/7 , β= 4ϵ/K 3/2 4/7 ¯ℓ1/L...

  70. [70]

    The case p≥ 3.Let r = p 1/ν then the conditionνr 3−p ≤ 1still holds if ν≤ 1, which means bothf and g have L1-Lipschitz continuous gradients. Forq = 2,· · ·, p, the qth-order derivative ofg is zero and the qth-order derivatives off is( L1/¯ℓ1)β1−qν(q−1)/2ℓq-Lipschitz continuous, whereℓq is the numerical constant defined in Lemma 3.1. Hence, we can ensure t...

This paper was first reviewed by deepseek-v4-flash on August 3, 2026.