SGHA: A Single-Loop Fully First-Order Algorithm for Nonconvex-Strongly-Convex Bilevel Optimization
2026-08-24 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study how hard it is to find an approximately stationary point in a specific kind of bilevel optimization problem where the lower-level problem is strongly convex but the overall problem is nonconvex. They propose new single-loop algorithms called SGHA and Stoc-SGHA that improve on existing double-loop methods by reformulating the problem with constraints and using a regularized Lagrangian approach. Their methods use approximated Hessian-vector products and achieve certain complexity guarantees in both deterministic and stochastic settings. Under some additional smoothness assumptions, their stochastic algorithm matches known lower bounds on complexity.
bilevel optimizationnonconvex optimizationstrong convexityoracle complexitystationary pointLagrangian relaxationSmoothed Gradient Descent Ascentstochastic optimizationHessian-vector productcomputational complexity
Authors
Zhihao Gu, Qilong Wu, Junchi Yang
Abstract
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(\barκ_y^{5}ε^{-2})$, where $\barκ_y$ denotes the relevant condition number. In the stochastic setting, Stoc-SGHA achieves an oracle complexity of $O\left(\barκ_y^{17}ε^{-6}ρ^{-3}\right)$ with probability at least $1-ρ$ for any $ρ\in(0,1)$, and an oracle complexity of $O\left(\barκ_y^{17}ε^{-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κ_y^{11}ε^{-4}ρ^{-2}\right)$ with high probability and $O\left(\barκ_y^{11}ε^{-4}\right)$ in expectation, matching the $ε$-dependence of the lower bounds.