cs.LGNov 6, 2026

Lower-Level Agnostic Bilevel Optimization

Authors: Peiwen Qiu, Prashant Khanduri, Jia Liu

Organizations: Dept. of ECE, The Ohio State University, Columbus, OH 43210 · Dept. of CS, Wayne State University, Detroit, MI 48202

Abstract

Bilevel optimization is a fundamental framework for machine learning problems, where an upper-level (UL) objective depends on the solution of a nested lower-level (LL) problem. Existing bilevel algorithms typically assume that the LL objective is available for evaluation, differentiation, or unrolling. However, this assumption can fail when the LL response is produced by a black-box solver, simulator, adversary, or learned predictor. In this paper, we study LL agnostic bilevel optimization, where the UL learner has access only to an approximate LL solution yˉ(x)\bar{\mathbf{y}}(\mathbf{x}) and cannot query the LL objective, its gradients, Hessian/Jacobian information, or the procedure that generates the LL response. We propose LeGo-BiO, a coordinate-wise pseudo-hypergradient method that estimates the missing Jacobian ∇xyˉ(x)\nabla _{\mathbf{x}}\bar{\mathbf{y}}(\mathbf{x}) using finite differences of yˉ(⋅)\bar{\mathbf{y}}(\cdot). For each UL coordinate, LeGo-BiO constructs a decision vector subject to 1-sparse updates, thereby isolating the corresponding Jacobian column needed in the UL gradient computation. This avoids the directional-projection limitation of full-parameter response differences and, unlike derivative-free/zeroth-order approximations of the entire UL gradient, preserves the available first-order gradient information with respect to the UL variables for more accurate UL gradient evaluation. We establish convergence guarantees for LeGo-BiO in both deterministic and stochastic settings under an LL error-bound/Polyak-Lojasiewicz-type condition, without requiring LL strong convexity. Our bounds yield an O(T−1)O(T^{-1}) rate in the deterministic setting and an O(T−1/2)O(T^{-1/2}) rate in the stochastic setting when the LL approximation error decreases geometrically. Experiments demonstrate competitive performance of LeGo-BiO despite being agnostic to the LL objective.

Figures & tables

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationarity

    Sep 24, 2026Zhiyao Zhang, Menglu Yu, Alvaro Velasquez +2Bilevel OptimizationSecond-Order Optimization

  2. BiMuon: A Geometry-Aware Stochastic Bilevel Optimization Approach

    Nov 6, 2026Zhen Qin, Zhiyao Zhang, Yingbin Liang +1Stochastic Bilevel OptimizationMatrix Optimization

  3. Select-then-differentiate: Solving Bilevel Optimization with Manifold Lower-level Solution Sets

    May 9, 2026Saeed Masiha, Zebang Shen, Negar Kiyavash +1Nonconvex OptimizationBilevel Optimization