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

arXiv: https://arxiv.org/abs/2608.23211 · HTML: https://mlsanity.com/paper/2608.23211/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 53 references that are in the map.
- First posted on arXiv 24 Aug 2026.

## Builds on (most cited first, 7 of 7)

- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization](https://mlsanity.com/paper/1607.05447/) (2016)
- [Amortized Implicit Differentiation for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2111.14580/) (2021)
- [On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation](https://mlsanity.com/paper/2309.01753/) (2023)
- [Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-loop and Hessian-free Solution Strategy](https://mlsanity.com/paper/2405.09927/) (2024)
- [Inexact bilevel stochastic gradient methods for constrained and unconstrained lower-level problems](https://mlsanity.com/paper/2110.00604/) (2021)
- [On the Condition Number Dependency in Bilevel Optimization](https://mlsanity.com/paper/2511.22331/) (2025)

## Built on by (most cited first, 2 of 2)

- [Optimal Stochastic Bilevel Optimization with First-Order Oracles](https://mlsanity.com/paper/2610.01843/) (2026)
- [A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2610.07290/) (2026)

## Abstract (arXiv)

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.