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.