PaperlayerView exact revision on arXiv

Source-linked AI summary

SGHA: A Single-Loop Fully First-Order Algorithm for Nonconvex-Strongly-Convex Bilevel Optimization

Zhihao Gu, Qilong Wu, Junchi Yang

arXiv:2608.23211v1math.OCcs.LG

TL;DR

Finding ε-stationary points in NC-SC bilevel optimization using only first-order oracles is challenging because common gradient-substitution methods typically rely on the Hessian of g. SGHA and Stoc-SGHA adapt Smoothed GDA to this setting through a regularized Lagrangian reformulation, achieving optimal deterministic and best-known stochastic ε-dependence.

  • Problem

    Common gradient-substitution methods for NC-SC bilevel optimization typically rely on the Hessian of g, motivating first-order approaches.

    Source: §1 · p. 2

  • Method

    SGHA and Stoc-SGHA adapt Smoothed GDA to NC-SC bilevel optimization through a regularized Lagrangian reformulation and first-order Hessian–vector approximations.

    Source: §1 · p. 3, §8 · p. 19

  • Results

    SGHA achieves optimal ε-dependence in the deterministic setting, while Stoc-SGHA matches the best-known ε-dependence of existing nested-loop methods in the stochastic setting.

    Source: §8 · p. 19

  • Takeaways & Limitations

    Single-loop, fully first-order algorithms attain optimal deterministic and best-known stochastic ε-dependence for NC-SC bilevel optimization.

    Source: §8 · p. 19

    The algorithms’ dependence on κ_y and ¯κ_y remains worse than existing lower bounds and double-loop penalty methods.

    Source: §4.2 · p. 10, §8 · p. 19

Abstract

from arXiv · show

In this work, we study the oracle complexity of finding an $ε$-stationary point for nonconvex-strongly-convex (NC-SC) bilevel optimization using only first-order oracles. Existing methods achieving the best-known complexity guarantees typically rely on double-loop, penalty-based procedures. We propose a novel single-loop algorithm based on a constrained reformulation in which lower-level stationarity is imposed as a constraint. Specifically, we construct a regularized Lagrangian by introducing a quadratic regularizer and restricting the dual variable to a bounded domain, and then apply Smoothed Gradient Descent Ascent [Zhang et al., 2020], with Hessian-vector products approximated via finite differences of gradients. We refer to the resulting deterministic and stochastic algorithms as SGHA and Stoc-SGHA, respectively. In the deterministic setting, SGHA achieves an oracle complexity of $O(\barκ_y^{5}ε^{-2})$, where $\barκ_y$ denotes the relevant condition number. In the stochastic setting, Stoc-SGHA achieves an oracle complexity of $O\left(\barκ_y^{17}ε^{-6}ρ^{-3}\right)$ with probability at least $1-ρ$ for any $ρ\in(0,1)$, and an oracle complexity of $O\left(\barκ_y^{17}ε^{-6}\right)$ in expectation under an additional bounded-iterate assumption. Moreover, under an additional stochastic smoothness assumption imposed only on the lower-level objective, the stochastic oracle complexity of Stoc-SGHA improves to $O\left(\barκ_y^{11}ε^{-4}ρ^{-2}\right)$ with high probability and $O\left(\barκ_y^{11}ε^{-4}\right)$ in expectation, matching the $ε$-dependence of the lower bounds.

1 Introduction

Bilevel optimization models hierarchical decision-making [Colson et al., 2007]; this work studies smooth NC–SC problems, where strong convexity makes the lower-level solution unique and the hyperobjective smooth [Ghadimi and Wang, 2018, Hong et al., 2023, Ji et al., 2021].

Problem setting and motivation

Motivation and prior work

  • Prior penalty methods attain eO(ε^-2) deterministic and eO(ε^-6) stochastic complexity, but their guarantees rely on double loops and direct single-loop penalty methods do not retain the best ε-dependence.Removing the inner loops leaves simultaneous tracking errors and penalty-induced conditioning deterioration [Liu et al., 2022, Shen and Chen, 2023, Kwon et al., 2023b].Source: §1 · p. 2

Proposed approach

  • SGHA and Stoc-SGHA impose lower-level stationarity as an equality constraint and use a bounded, quadratically regularized multiplier with finite-difference Hessian-vector approximations.These modifications make the minimax surrogate suitable for Smoothed GDA while retaining a fully first-order method.Source: §1 · p. 3

Main complexity results

  • In the deterministic setting, SGHA finds an ε-stationary point of the NC–SC bilevel problem; in the stochastic setting, Stoc-SGHA has an expected-complexity guarantee under an additional bounded-iterate assumption.Source: §1 · p. 3
  • Under the lower-level stochastic smoothness condition in Assumption 3, Theorems 10 and 11 improve the bounds and match the lower bound in dependence on ϵ.The lower bound is for zero-respecting SFO algorithms on a bounded constrained nonconvex–quadratic problem.Source: §1 · pp. 3–4

2 Related Work

The related work reviews first-order methods for NC–SC bilevel optimization and NC–C minimax optimization, emphasizing their oracle requirements, complexity guarantees, and assumptions that distinguish them from this paper’s setting.

Bilevel Optimization with Hessian

Fully First-order Bilevel Optimization

  • Fully first-order penalty methods [Liu et al., 2022, Shen and Chen, 2023, Kwon et al., 2023b] are mostly double-loop; no known method improves their epsilon dependencies without additional assumptions.F2SA uses an increasing penalty, while fixing the penalty parameter improves deterministic and stochastic complexity guarantees [Chen et al., 2025a, Kwon et al., 2024, Chen et al., 2025b].Source: §2 · p. 5
  • An ε^-2 gap remains between the best-known stochastic upper bound and the Ω(ε^-4) lower bound; the latter under lower-level stochastic smoothness uses a y⋆-aware oracle [Kwon et al., 2024].That oracle additionally returns an estimate of the exact lower-level solution to a prescribed accuracy.Source: §2 · p. 5
  • FdeHBO is a closely related single-loop method using finite-difference Hessian-vector products, but its guarantees require variance reduction and stronger smoothness assumptions.F3SA [Kwon et al., 2023b] operates under similar stronger assumptions; these methods are omitted from Table 1.Source: §2 · p. 5

Minimax optimization

  • NC–C minimax methods reach eO(ε^-2.5) under f-stationarity or eO(ε^-3) under Moreau-envelope stationarity, while Smoothed GDA’s rates require conditions that do not directly apply here.Most cited rates assume a compact dual domain; the Smoothed GDA analyses require additional regularity or a Polyak–Łojasiewicz condition, and approximating the Lagrangian gradients requires Hessian-vector products.Source: §2 · pp. 5–6

3 Preliminaries and Technical Background

The section states the smoothness and strong-convexity assumptions for NC-SC bilevel optimization, then reformulates lower-level optimality as an equality constraint and relates Lagrangian stationarity to hyperobjective stationarity.

3.1 Basic Assumptions and Definitions

  • Assumption 1 requires lower-level strong convexity, smooth objectives, Lipschitz Hessians, and a finite lower bound on f.The paper defines κ_y and ¯κ_y as condition numbers and calls x ϵ-first-order stationary when ∥∇φ(x)∥ ≤ ϵ.Source: §3.1 · pp. 6–7

3.2 Equality–constrained Reformulation

  • The equality constraint ∇_y g(x, y) = 0 exactly characterizes the lower-level solution graph, preserving the original objective values and minimizers.Strong convexity makes the lower-level minimizer unique, and the reformulated constraint is regular under LICQ.Source: §3.2 · p. 7
  • The authors introduce a regularized Lagrangian and single-loop, fully first-order method, unlike prior KKT-system [Liu et al., 2023] or penalty approaches [Kim et al., 2020, Mehra and Hamm, 2021].Their method targets an approximate stationary point of L.Source: §3.2 · p. 7

3.3 From Lagrangian Stationarity to Bilevel Stationarity

  • Theorem 2 reduces analysis of hyperobjective F stationarity to analysis of Lagrangian L stationarity.The theorem is stated under Assumption 1.Source: §3.3 · pp. 7–8
  • Under Assumption 1, KKT multipliers λ* are bounded by a problem-dependent constant, motivating Lagrangian stationarity instead of penalizing the lower-level value gap as in [Kwon et al., 2023b].The boundedness claim concerns multiplier solutions satisfying the KKT conditions.Source: §3.3 · p. 8

4 Deterministic NC–SC Bilevel Optimization

Section 4 introduces SGHA for deterministic NC–SC bilevel optimization, establishes its complexity guarantee, and sketches the analysis.

4.1 Algorithm

  • SGHA bounds and regularizes the dual variable, applies Smoothed GDA, and uses central finite differences to approximate Hessian-vector products with first-order oracles.The bounded domain contains all KKT multipliers, while quadratic regularization makes the dual maximization strongly concave.Source: §4.1 · pp. 8–9

4.2 Complexity Guarantees

  • SGHA is the first single-loop deterministic NC–SC method with optimal ε^-2 dependence; versus Chen et al. [2025a], it removes a logarithmic factor but has worse κ_y dependence.Source: §4.2 · p. 10

4.3 Analysis and Proof Sketch

  • A lower-bounded Lyapunov function’s one-step decrease controls stationarity and tracking residuals up to finite-difference error, linking them to Lagrangian stationarity and hypergradient convergence.Source: §4.3 · pp. 11–12

5 Stochastic NC–SC Bilevel Optimization

The section extends SGHA to stochastic first-order oracles through mini-batch gradient estimates and finite-difference Hessian-vector products. It gives high-probability and bounded-iterate expected guarantees, and discusses sharper stochastic complexity and remaining gaps.

5 Stochastic NC–SC Bilevel Optimization

  • Stoc-SGHA preserves SGHA’s single-loop structure, replacing exact gradients with mini-batch estimates and approximating Hessian-vector products by finite differences.The method uses separate mini-batches for gradients of f and finite-difference approximations involving g.Source: §5 · p. 12
  • Reusing the same sample in each central difference is essential for the sharper variance bound, while bounded-variance noise adds a variance term of order σ_L^2.That additional variance complicates direct combinations of existing minimax analyses with finite-difference approximations.Source: §5 · p. 13
  • For Algorithm 2, Markov’s inequality converts expected residual bounds into a high-probability bound, after which Lemma 7 is applied pathwise to yield a high-probability oracle-complexity guarantee.Source: §5 · p. 13
  • The cited discussion says an additional ε^-2 gap, plus a substantial condition-number gap, remains between best-known upper and lower bounds for stochastic NC–SC bilevel optimization; closing this gap remains open.Source: §5 · p. 15

6 Improved Complexities with Lower-Level Stochastic Smoothness

With stochastic smoothness imposed only on the lower-level objective, Stoc-SGHA achieves improved stochastic oracle complexity. Its epsilon-dependence is optimal, while its condition-number dependence remains above the lower bound.

6 Improved Complexities with Lower-Level Stochastic Smoothness

  • Using the same mini-batch sample for both central-difference gradient evaluations sharpens Hessian-vector variance control and prevents variance amplification by the finite-difference radius.This allows a batch size of order epsilon^-2.Source: §6 · p. 15
  • The stochastic first-order oracle complexity guarantee holds with probability at least 1−ρ; for Algorithm 2, an expectation guarantee additionally requires the bounded-iterate condition.Source: §6 · p. 16
  • The epsilon^-4 dependence is optimal, matching smooth nonconvex single-level optimization, while previously this rate required a noise-free lower-level gradient.The additional stochastic smoothness condition is imposed only on the lower-level objective and is stronger than the standard bounded-variance oracle model.Source: §6 · pp. 15–16
  • The algorithm's kappa_bar_y dependence remains worse than the lower bound, leaving the condition-number gap for single-loop fully first-order methods open.Source: §6 · p. 16

7 Numerical Experiments

Across learn-to-regularize logistic regression and MNIST data hyper-cleaning, SGHA achieves the strongest reported results among the compared methods. Experiments use a common evaluation protocol and report each method’s best stable performance.

7 Numerical Experiments

  • The experiments cover learn-to-regularize logistic regression and data hyper-cleaning, using a common protocol and each method’s best stable performance.The data-cleaning experiment evaluates learned weights by the average weight assigned to corrupted training examples, for which lower is better.Source: §7 · pp. 16–17, §7.2 · p. 19

7.1 Learn-to-Regularize Logistic Regression

  • SGHA achieves the lowest test loss and highest test accuracy on 20 Newsgroups, outperforming all compared methods.F2BSA is the strongest baseline. The experiment uses 20 classes and 101,631 TF-IDF features.Source: §7.1 · p. 17, Figure 1 · p. 18

7.2 Data Hyper-Cleaning on MNIST

  • Across corruption ratios, SGHA assigns substantially smaller weights to corrupted MNIST examples than competing methods, with its advantage growing as corruption increases.F2BSA is the best-performing baseline, but assigns noticeably larger weights to corrupted examples; tested corruption ratios were 0.5, 0.9, and 0.99.Source: §7.2 · pp. 18–19, Figure 2 · p. 19

8 Conclusions and Future Directions … B.4 Intermediate Lemmas for Lyapunov Function

SGHA and Stoc-SGHA are presented as single-loop, fully first-order methods with the stated ε-dependence guarantees, built from a regularized Lagrangian and finite-difference gradient approximations. The conclusion identifies condition-number dependence, stochastic lower bounds, and extending beyond strongly convex lower levels as open directions.

8 Conclusions and Future Directions

  • The algorithms achieve optimal ε-dependence deterministically and match the best-known stochastic ε-dependence, while open questions include improving condition-number dependence, identifying the stochastic lower bound, and extending beyond strongly convex lower levels.The cited Ω(κ_y^4.5 ε^-4) lower bound [Chen et al., 2025a] uses a deterministic upper-level objective and quadratic lower-level objective; the authors conjecture a tight complexity of Ω(poly(κ_y) ε^-6) without these special structures.Source: §8 · pp. 19–20

A.1 LICQ of NC-SC Bilevel Optimization

  • The lower-level constraint Jacobian has full row rank, establishing LICQ at every feasible point.Strong convexity in y makes ∇_yy g(x, y) nonsingular.Source: §A.1 · p. 23

A.2 Approximation of Hypergradient

  • The hypergradient-approximation proof derives a smoothness bound using smoothness of f, strong convexity of g, and transfer from the current y to y⋆(x).The final transfer step uses Lipschitz continuity of the approximate hypergradient with respect to y.Source: §A.2 · pp. 24–25

A.3 Boundedness of λ∗

  • The KKT multiplier λ∗ is bounded by a constant independent of the specific KKT point.The proof invokes KKT stationarity and strong convexity of g with respect to y.Source: §A.3 · p. 25

B.1 Lower Bound of the Lyapunov Function

  • The Lyapunov lower-bound argument defines V as K(w, ŵ, λ) − 2Ψ(ŵ, λ) + 2P(ŵ) and uses the bounded dual domain containing zero.The supplied proof rewrites V as a sum involving P, K − Ψ, and P − Ψ.Source: §B.1 · p. 26

B.2 Properties of Deterministic Finite Difference Approximation

  • The deterministic finite-difference approximation is stated to satisfy two properties, with the proof of the second following the same argument as the first.The supplied passage does not specify the properties’ bounds.Source: §B.2 · pp. 26–27

B.3 Preliminary Lemmas

  • When p_w > l_L,1, K is strongly convex in w and strongly concave in λ; the preliminary lemmas also bound changes in its minimizer as ŵ and λ vary.The stated curvatures are p_w − l_L,1 in w and p_λ in λ.Source: §B.3 · pp. 28, 30

B.4 Intermediate Lemmas for Lyapunov Function

  • The intermediate lemmas combine iterate-update inequalities and proximal descent into a Lyapunov-function proposition under specified step-size conditions.The excerpt includes a bound γ_w,k ≤ 1/[8(p_w + l_L,1)] and identifies the resulting Lyapunov function in Proposition 23.Source: §B.4 · pp. 31, 33, 34, 36

B.5 Oracle Complexity under Deterministic Setting … C.4 Oracle Complexity under Stochastic Setting

These sections close the deterministic stationarity proof and develop the stochastic analysis, using finite-difference bounds and Lyapunov estimates to derive an iteration-level result for Algorithm 2 under specified parameter choices.

B.5 Oracle Complexity under Deterministic Setting

  • The deterministic proof selects an iterate with bounded primal and dual residuals and establishes that its associated x is ε-stationary.The proof then substitutes its ε-dependent tolerance into the iteration bound.Source: §B.5 · pp. 47–48

C.1 Filtration

  • The stochastic proof defines filtrations before sampling and after each update, with fresh mini-batches used at each iteration.These definitions organize the stochastic analysis around the sampling and update steps.Source: §C.1 · p. 48

C.2 Properties of Stochastic Finite Difference Approximation

  • The stochastic analysis bounds the finite-difference approximation by combining bias and variance estimates, and derives bounds for updates under stochastic gradient assumptions.The cited update bounds include iterate changes and an expectation bound.Source: §C.2 · pp. 50–52

C.3 Intermediate Lemmas for Lyapunov Function under Stochastic Setting

  • The stochastic Lyapunov analysis imposes step-size and regularization conditions, then establishes intermediate Lyapunov estimates for the updates.The stated conditions include γw,k ≤ 1/[8(pw+lL,1)] and pw = 2lL,1.Source: §C.3 · pp. 52, 54, 56
  • The C.3 proof takes total expectation and substitutes an inequality into the descent relation to complete the Lyapunov argument.The supplied passages contain intermediate proof steps rather than the resulting inequality.Source: §C.3 · pp. 59, 61

C.4 Oracle Complexity under Stochastic Setting

  • The C.4 proof applies a deterministic lemma pathwise conditional on (ŵ_k, λ_k), then squares the estimate and takes expectation.The passages show this sequence of steps but do not expose the resulting bound.Source: §C.4 · p. 61
  • Under prescribed choices of τ, batch size B, and iteration count K, some index k in {0, …, K − 1} satisfies the stated bound.The same conclusion holds for smaller τ² and integer B and K no smaller than their displayed lower bounds; the bound for B is evaluated at the selected τ.Source: §C.4 · p. 63

C.5 Oracle Complexity of Stoc-SGHA in High Probability

The high-probability analysis establishes Stoc-SGHA’s oracle complexity and transfers a high-probability closeness event into a stationarity guarantee through pathwise application of Lemma 7.

C.5 Oracle Complexity of Stoc-SGHA in High Probability

  • The proof chooses parameters to meet Lemma 31’s condition, then applies Lemma 7 pathwise using the high-probability event.The proof notes that conditions verified in Theorem 4’s proof hold with δ in place of ϵ_L.Source: §C.5 · p. 65
  • With probability at least 1−ρ, the selected iterate satisfies three stated closeness bounds involving δ and κ̄_y.These bound the distances between w_k⋆ and w+(ŵ_k⋆, λ_k⋆), λ+(ŵ_k⋆) and λ_k⋆, and w_k⋆ and ŵ_k⋆.Source: §D.5 · p. 76

C.6 Oracle Complexity of Stoc-SGHA in Expectation … D.3 Intermediate Lemmas for Lyapunov Function

The expectation analysis gives Stoc-SGHA an O(κ_y^17 ε^-6) oracle complexity under a bounded-iterate assumption. With lower-level stochastic smoothness, the paper reports improved stochastic rates and develops supporting finite-difference and Lyapunov analyses.

C.6 Oracle Complexity of Stoc-SGHA in Expectation

  • On bounded iterates, Lemma 32 establishes finite gradient bounds and a bounded true bilevel hypergradient under its assumptions.The argument uses smoothness and compactness to establish finiteness of the relevant constants.Source: §C.6 · pp. 66–67
  • The expected-stationarity bridge converts the algorithm’s bounds into a true bilevel hypergradient bound under the stated assumptions and bounded-iterate condition.Lemma 33 assumes a bounded dual domain with Cλ > lf,0/µg and sets pw = 2lL,1.Source: §C.6 · pp. 67, 70
  • O(κ_y^17 ε^-6) is the expected oracle complexity of Stoc-SGHA under an additional bounded-iterate assumption.The proof concludes by bounding the total oracle complexity while treating remaining problem-dependent constants as fixed.Source: §C.6 · pp. 67, 70

D.1 Properties of Stochastic Finite Difference Approximation with Stochastic Smoothness of g

  • Using the same sample at both perturbed points yields finite-difference estimates whose squared bias and variance add, for both the stated bounds (31) and (32).The deterministic central-difference bias is combined with centered sampling error.Source: §D.1 · pp. 70–71

D Improved Complexities with Lower-Level Stochastic Smoothness

  • The analysis states that, because the sampling error is centered, squared bias and variance add, and the same calculation applied to the y-component yields (31) and (32).Source: §D.1 · p. 71

D.2 Preliminary Lemmas

  • Lemma 35 supplies a preliminary result under Assumptions 1–3 and Algorithm 2; its proof follows the proof of Lemma 26.Source: §D.2 · p. 71

D.3 Intermediate Lemmas for Lyapunov Function

  • The Lyapunov analysis gives intermediate lemmas and a proposition; Lemma 36 requires γw,k ≤ 1/[8(pw + lL,1)], while Lemma 37 sets pw = 2lL,1.Proposition 38 defines the Lyapunov function; the supplied passage does not show its resulting bound.Source: §D.3 · pp. 71–72

D.4 Oracle Complexity under Stochastic Setting with Stochastic Smoothness of g

Under stochastic smoothness of g, Stoc-SGHA improves the stochastic oracle complexity to O(κ̄_y^11 ε^-4 ρ^-2) with high probability and O(κ̄_y^11 ε^-4) in expectation. The section establishes this guarantee through parameter choices for Algorithm 2.

D.4 Oracle Complexity under Stochastic Setting with Stochastic Smoothness of g

  • The guarantee follows by choosing the averaging parameter, batch size, and iteration count for Algorithm 2.The section specifies these choices in its stochastic-smoothness analysis.Source: §D.4 · pp. 73–74
  • The conclusion also holds for a no-larger τ^2 and batch size B and iteration count K no smaller than their displayed values, yielding a guaranteed index k.The index lies in {0, …, K − 1}.Source: §D.4 · p. 74

D.5 Oracle Complexity of Stoc-SGHA in High Probability with Stochastic Smoothness of g · D.6 Oracle Complexity of Stoc-SGHA in Expectation with Stochastic Smoothness of g

With stochastic smoothness of g, Stoc-SGHA has improved oracle complexity in both high-probability and expectation guarantees. The proofs use parameter choices and bounds tailored to each guarantee.

D.5 Oracle Complexity of Stoc-SGHA in High Probability with Stochastic Smoothness of g

  • The high-probability proof sets ε_L using ε√ρ and sets L_0 = 8L̄κ̄_y.These parameter choices are used to verify the conditions needed for the proof.Source: §D.5 · p. 75
  • The proof applies Lemma 7 pathwise and derives its final guarantee on the same high-probability event.The cited passages describe the pathwise application and subsequent result, but do not expose the guarantee’s full formula.Source: §D.5 · p. 77
  • By Markov’s inequality and a union bound, with probability at least 1−ρ, the simultaneous bounds are ∥wk⋆−w+(ˆwk⋆, λk⋆)∥≤δ, ∥λ+(ˆwk⋆)−λk⋆∥≤κ̄_yδ, and ∥wk⋆−ˆwk⋆∥≤κ̄_yδ.Source: §D.5 · p. 76

D.6 Oracle Complexity of Stoc-SGHA in Expectation with Stochastic Smoothness of g

  • The expectation proof uses ε_L defined in terms of ε, G, L̄, and κ̄_y, with L_0 = 8L̄κ̄_y.It verifies the conditions of Lemma 40 as in the high-probability proof, then applies Lemma 33 for the hypergradient conclusion.Source: §D.6 · pp. 77–78
  • The expectation proof obtains an index k⋆ among the first K iterates before applying Lemma 33.The cited passages do not expose the full inequality defining the index’s guarantee.Source: §D.6 · p. 78
  • O(κ̄_y^11 ε^-4) is the expected stochastic oracle complexity under stochastic smoothness of g.The proof uses a problem-dependent constant G chosen to bound the constants Gw/κ̄_y and Gλ, as well as 1.Source: §D.6 · pp. 77–78

Related papers

Loading 2608.23211v1…