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

• URL: http://arxiv.org/abs/2608.23211v1
• Date: Mon, 24 Aug 2026 13:00:40 GMT
• Title: SGHA: A Single-Loop Fully First-Order Algorithm for Nonconvex-Strongly-Convex Bilevel Optimization
• Abstract summary: We show that Stoc-SGHA achieves an oracle complexity of $Oleft(bar_y-4)$ with at least $1$ for any $in(1)$, and an complexity of $Oleft(bar_y-4)$ under an additional assumption.<n>In a deterministic setting, Stoc-SGHA achieves an oracle complexity of $Oleft(bar_y)$ with at least $1$ for any $in(1)$, and an complexity of $Oleft(bar_y)$ under
• Score: 9.118433290504035
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps [28.438129186461598]
  We study the oracle complexity of computing a point with small fixed-point residual $|T(x)-x| leq $, for a general norm $|cdot|$ and a self-map $T$ of a compact convex set.<n>We provide an algorithm that solves such instances for any norm with a weak Rademacher type $q > 1$, with high probability.
  arXiv  Detail & Related papers  (2026-09-08T23:09:39Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• First-Order Methods for Linearly Constrained Bilevel Optimization [38.19659447295665]
  We present first-order linearly constrained optimization methods for high-level Hessian computations.<n>For linear inequality constraints, we attain $(delta,epsilon)$-Goldstein stationarity in $widetildeO(ddelta-1 epsilon-3)$ gradient oracle calls.
  arXiv  Detail & Related papers  (2024-06-18T16:41:21Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation [13.813242559935732]
  We show first-order algorithms for solving Bilevel Optimization problems. In particular, we show a strong connection between the penalty function and the hyper-objective. We show an improved oracle-complexity of $O(epsilon-3)$ and $O(epsilon-5)$, respectively.
  arXiv  Detail & Related papers  (2023-09-04T18:25:43Z)
• Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
  We present a method for solving general non-strongly-concave bilevel optimization problems. Our results also improve upon the existing complexity for finding second-order stationary points in non-strongly-concave problems.
  arXiv  Detail & Related papers  (2023-06-30T20:36:44Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  We show that our algorithms converge without any prior knowledge on the parameters of the problem.<n>All three algorithms work without prior knowledge of the diameter of the feasible set, the Lipschitz constant or smoothness of the objective function.<n>We extend our framework to relative scale and demonstrate the efficiency and robustness of our methods on large-scale semidefinite programs.
  arXiv  Detail & Related papers  (2023-06-30T08:34:29Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  We introduce a new tool for BFG convex optimization (SCO): a Reweighted Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probability density. We develop algorithms achieving state-of-the-art complexities for SCO in parallel and private settings.
  arXiv  Detail & Related papers  (2023-01-01T18:51:29Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization [12.096252285460814]
  We propose a projection-free conditional gradient-type algorithm for composition optimization. We show that the number of oracles and the linear-minimization oracle required by the proposed algorithm, are of order $mathcalO_T(epsilon-2)$ and $mathcalO_T(epsilon-3)$ respectively.
  arXiv  Detail & Related papers  (2022-02-09T06:05:38Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  We find an algorithm which finds. epsilon$-approximate stationary point (with $|nabla F(x)|le epsilon$) using. $(epsilon,gamma)$surimate random random points. Our lower bounds here are novel even in the noiseless case.
  arXiv  Detail & Related papers  (2020-06-24T04:41:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.