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

arXiv:2608.23211v1 Announce Type: cross Abstract: In this work, we study the oracle complexity of finding an epsilon-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(ar{kappa}_y^{5}epsilon^{-2}), where ar{kappa}_y denotes the relevant condition number. In the stochastic setting, Stoc-SGHA achieves an oracle complexity of Oleft(ar{kappa}_y^{17}epsilon^{-6}rho^{-3}right) with probability at least 1-rho for any rhoin(0,1), and an oracle complexity of Oleft(ar{kappa}_y^{17}epsilon^{-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 Oleft(ar{kappa}_y^{11}epsilon^{-4}rho^{-2}right) with high probability and Oleft(ar{kappa}_y^{11}epsilon^{-4}right) in expectation, matching the epsilon-dependence of the lower bounds.

Source: arXiv cs.LG | 2026-08-25