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

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(barkappay5ε-2), where barkappay denotes the relevant condition number. In the stochastic setting, Stoc-SGHA achieves an oracle complexity of Oleft(barkappay17ε-6ρ-3right) with probability at least 1-ρ for any ρ∈(0,1), and an oracle complexity of Oleft(barkappay17ε-6right) 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 Oleft(barkappay11ε-4ρ-2right) with high probability and Oleft(barkappay11ε-4right) in expectation, matching the ε-dependence of the lower bounds.