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

Bilevel optimization models hierarchical decision-making problems with two nested levels, where an upper-level objective depends on the solution of a lower-level problem. Standard fully first-order methods for nonconvex-strongly-convex (NC-SC) bilevel optimization typically achieve their best complexity guarantees by relying on double-loop, penalty-based procedures with inner subproblem iterations. This paper asks whether a single-loop, fully first-order algorithm can match the best epsilon-dependence achieved by double-loop penalty methods without requiring nested loop loops or costly Hessian-vector products.

The authors propose SGHA (Smoothed Gradient Descent Ascent with Hessian Approximation) and its stochastic counterpart Stoc-SGHA. The approach starts by formulating the lower-level first-order optimality condition as an equality constraint, yielding an equivalent constrained problem. The authors then construct a regularized Lagrangian by introducing a quadratic regularizer, restricting dual variables to a bounded domain, and approximating Hessian-vector products via finite differences of gradients. This transforms the problem into a well-conditioned minimax surrogate that can be solved using Smoothed Gradient Descent Ascent in a single loop.

In the deterministic setting, SGHA finds an epsilon-stationary point with an oracle complexity of O(kappa_y^5 epsilon^-2). In the stochastic setting, under an additional stochastic smoothness assumption on the lower-level objective, Stoc-SGHA achieves an oracle complexity of O(kappa_y^11 epsilon^-4) in expectation and O(kappa_y^11 epsilon^-4 rho^-2) with high probability. These results match the optimal epsilon-dependence of existing lower bounds for fully first-order stochastic bilevel optimization while successfully eliminating the double-loop structure.