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.

Optimization and Control (math.OC); Machine Learning (cs.LG)

arXiv:2608.23211 [math.OC]

(or arXiv:2608.23211v1 [math.OC] for this version)

https://doi.org/10.48550/arXiv.2608.23211 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.