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

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(\bar{\kappa}_y^{5}\epsilon^{-2})$, where $\bar{\kappa}_y$ denotes the relevant condition number. In the stochastic setting, Stoc-SGHA achieves an oracle complexity of $O\left(\bar{\kappa}_y^{17}\epsilon^{-6}\rho^{-3}\right)$ with probability at least $1-\rho$ for any $\rho\in(0,1)$, and an oracle complexity of $O\left(\bar{\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 $O\left(\bar{\kappa}_y^{11}\epsilon^{-4}\rho^{-2}\right)$ with high probability and $O\left(\bar{\kappa}_y^{11}\epsilon^{-4}\right)$ in expectation, matching the $\epsilon$-dependence of the lower bounds.