解决非凸下层双层优化需要二阶平稳性

# To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationarity
Source: [https://arxiv.org/html/2609.30501](https://arxiv.org/html/2609.30501)
Zhiyao Zhang, Menglu Yu, Alvaro VelasquezAffiliation:The Ohio State UniversityAffiliation:MetaAffiliation:University of Colorado BoulderEmail:[zhang\.15178@osu\.edu](mailto:)Nathaniel D\. Bastian, Jia LiuAffiliation:The Ohio State UniversityAffiliation:Johns Hopkins UniversityEmail:[liu@ece\.osu\.edu](mailto:)

###### Abstract

Although bilevel optimization \(BLO\) has emerged as a powerful framework for addressing many complex and nested machine learning problems in recent years, most existing studies are confined to the lower\-level strongly convex \(LLSC\) or lower\-level generally convex \(LLGC\) settings \(i\.e\., the lower\-level objective function is assumed to be, at least, convex\)\. While the LLSC/LLGC assumptions render more tractable algorithmic design and theoretical analysis, they are too rigid to encompass many machine learning problems in practice\. The limitations of LLSC/LLGC assumptions in BLO motivate us to investigate solving the BLO problem in the general lower\-level nonconvex \(LLNC\) settings, which remains in its infancy\. In the literature on LLNC\-BLO, most of the existing works either require additional structures in the lower\-level objective function for tractable theoretical analysis, or adopt the first\-order stationarity reformulation as a lower\-level surrogate problem, which is inherited from the LLSC/LLGC settings but could lose their effectiveness in the LLNC setting\. To bridge this gap, in this work, we propose to reformulate the nonconvex lower\-level problem using asecond\-order stationarity\-based surrogate,the solution of which guarantees a local optimal solution at the lower level\. Based on this reformulation, we propose the𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~\(Perturbed gradient algorithm forbilevel problem\) and show that it overcomes the limitations of prior works by probing and escaping lower\-level saddle points\. We theoretically prove that𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~achieves a finite\-time convergence rate of𝒪⁡\(T−25\)\\mathcal\{O\}\(T^\{\-\\frac\{2\}\{5\}\}\), whereTTdenotes iterations\. To our knowledge, this work is the first to establish the finite\-time convergence rate guarantee for achieving lower\-level second\-order stationary solutions in general LLNC\-BLO\. Our experiments on both a large language model\-based data curation task and a meta\-learning task also show that𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~outperforms state\-of\-the\-art methods\.

## 1Introduction

In recent years, bilevel optimization \(BLO\)\([Bracken and McGill, 1973](https://arxiv.org/html/2609.30501#bib.bib10);[Liu et al\., 2021](https://arxiv.org/html/2609.30501#bib.bib12);[Zhang et al\., 2024](https://arxiv.org/html/2609.30501#bib.bib11)\)has received significant attention in the machine learning community due to the rise of a wide range of complex and nested machine learning problems, such as reinforcement learning\([Hong et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib13);[Kudo et al\., 2026](https://arxiv.org/html/2609.30501#bib.bib14)\), meta\-learning\([Franceschi et al\., 2018](https://arxiv.org/html/2609.30501#bib.bib15);[Ji et al\., 2021](https://arxiv.org/html/2609.30501#bib.bib9)\), adversarial training\([Zhang et al\., 2022b](https://arxiv.org/html/2609.30501#bib.bib16)\), large language model \(LLM\) fine\-tuning\([Shen et al\., 2024a](https://arxiv.org/html/2609.30501#bib.bib17)\), to name just a few\. In general, a BLO problem can be formulated as follows:

BLO:minx∈ℝp,y∈ℝq⁡f⁡\(x,y\)subject to\\displaystyle\\mathrm\{BLO:\}\\,\\,\\min\_\{x\\in\\mathbb\{R\}^\{p\},y\\in\\mathbb\{R\}^\{q\}\}f\(x,y\)\\hskip 30\.00005pt\\text\{subject to \}y∈𝒮⁡\(x\):=arg​miny⁡g​\(x,y\),\\displaystyle y\\in\\mathcal\{S\}\(x\):=\\argmin\_\{y\}g\(x,y\),\\vskip\-5\.0pt\(1\)wheref⁡\(x,y\)f\(x,y\)andg⁡\(x,y\)g\(x,y\)are the upper\- and lower\-level objective functions, respectively\. Clearly, the challenge of solving a BLO problem stems from the nested structure, i\.e\., part of the decision variablesyyin the upper\-level objectivef⁡\(x,y\)f\(x,y\)is obtained from the set of optimizersS⁡\(x\)S\(x\)given an upper\-level variablex∈ℝpx\\in\\mathbb\{R\}^\{p\}\. To address this challenge and for tractable algorithmic design and analysis, most existing works in the BLO literature have relied on therestrictivelower\-level strong convexity \(LLSC\) assumption, i\.e\.,g⁡\(x,⋅\)g\(x,\\cdot\)isstrongly convexwith respect to \(w\.r\.t\.\)yyfor any givenx∈ℝpx\\in\\mathbb\{R\}^\{p\}\([Ghadimi and Wang, 2018](https://arxiv.org/html/2609.30501#bib.bib18);[Ji et al\., 2021](https://arxiv.org/html/2609.30501#bib.bib9);[Yang et al\., 2021](https://arxiv.org/html/2609.30501#bib.bib19);[Dagréou et al\., 2022](https://arxiv.org/html/2609.30501#bib.bib20)\), thereby ensuring a singleton solution set for the lower\-level problem and well\-defined upper\-level hypergradient through the implicit function theorem\. To address the limitation of the stringent LLSC assumption, a recent line of works in the BLO literature relaxes LLSC to lower\-level general convexity \(LLGC\), i\.e\.,g⁡\(x,⋅\)g\(x,\\cdot\)isconvexw\.r\.t\.yy\([Cao et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib22);[Jiang et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib23);[Liu et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib21)\)\. Unfortunately, LLGC remains highly restrictive, since most modern learning models are based on deep neural networks, which are highlynonconvexand violate the LLGC assumption\.

To date, research on bilevel optimization \(BLO\) problems with nonconvex lower levels \(LLNC\) remains in its infancy, and existing results are limited\. To the best of our knowledge, early attempts to address LLNC\-BLO\([Kwon et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib24);[Shen and Chen, 2023](https://arxiv.org/html/2609.30501#bib.bib6);[Xiao et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib5);[Chen et al\., 2024](https://arxiv.org/html/2609.30501#bib.bib27);[Liu et al\., 2024](https://arxiv.org/html/2609.30501#bib.bib8);[Jiang et al\., 2025a](https://arxiv.org/html/2609.30501#bib.bib26);[Jiang et al\., 2025b](https://arxiv.org/html/2609.30501#bib.bib25);[Ma et al\., 2026](https://arxiv.org/html/2609.30501#bib.bib7)\)have achieved only partial success and exhibit various limitations\. One key reason for this stagnation is that, under LLNC, finding an optimal solutiony∗​\(x\)y^\{\*\}\(x\)to the lower\-level problem is already intractable in general \(typically NP\-hard\)\. This difficulty is further compounded by the potential non\-uniqueness ofy∗​\(x\)y^\{\*\}\(x\)and the challenge of establishing well\-defined upper\-level hypergradients given ay∗​\(x\)y^\{\*\}\(x\)\. Consequently, the aforementioned works either impose specific structural assumptions or consider relaxations of the LLNC\-BLO problem\. For example, some existing works\([Kwon et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib24);[Jiang et al\., 2025a](https://arxiv.org/html/2609.30501#bib.bib26);[Jiang et al\., 2025b](https://arxiv.org/html/2609.30501#bib.bib25)\)assume bounded domains for the variables \(eitherxx,yy, or both\), which limits their practical applicability\. Other works relax the LLNC\-BLO formulation by replacing the lower\-level optimality conditiony∈arg⁡miny⁡g⁡\(x,y\)y\\in\\arg\\min\_\{y\}g\(x,y\)with the first\-order stationarity condition, i\.e\., seekingyy\-solutions that satisfy∇yg​\(x,y\)=0\\nabla\_\{y\}g\(x,y\)=0\. Although some studies further assume that the lower\-level objectiveg⁡\(x,y\)g\(x,y\)satisfies the Polyak–Łojasiewicz \(PL\) condition\([Shen and Chen, 2023](https://arxiv.org/html/2609.30501#bib.bib6);[Xiao et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib5);[Liu et al\., 2024](https://arxiv.org/html/2609.30501#bib.bib8);[Ma et al\., 2026](https://arxiv.org/html/2609.30501#bib.bib7)\), thereby ensuring that any first\-order stationary point \(FOSP\) is globally optimal\. However, the PL condition is restrictive, since nonconvex problems may generally exhibit flat regions, saddle points, or suboptimal local minima, under which the PL condition fails to hold\.

In this work, we argue that algorithmic designs using the FOSP relaxation as a surrogate for the lower\-level problem could be easily trapped in undesirable saddle points of the lower\-level objective \(i\.e\., points that are FOSP but not local minima\), thereby yielding poor solutions to the overall LLNC\-BLO problem\. For example, consider the simple LLNC\-BLO problem in Fig\.[1](https://arxiv.org/html/2609.30501#S1.F1)wherex,y∈ℝx,y\\in\\mathbb\{R\},f⁡\(x,y\)=\(x−2\)2\+y2f\(x,y\)=\(x\-2\)^\{2\}\+y^\{2\},g⁡\(x,y\)=14​y4−12​x​y2g\(x,y\)=\\frac\{1\}\{4\}y^\{4\}\-\\frac\{1\}\{2\}xy^\{2\}\. It can be readily verified that the PL condition fails to hold even for this simple example\. Consequently, sequences generated by existing algorithms based on the FOSP surrogate converge only tosaddle pointsofg⁡\(x,⋅\)g\(x,\\cdot\)\(cf\. Fig\.[1\(a\)](https://arxiv.org/html/2609.30501#S1.F1.sf1)\), leading to solutions that are significantly suboptimal compared to the true optimum \(cf\. Fig\.[1\(b\)](https://arxiv.org/html/2609.30501#S1.F1.sf2)\)\.

\(a\)Converging trajectories\.\(b\)Convergence gaps in \(a\)\.
Figure 1:Example:x,y∈ℝx,y\\in\\mathbb\{R\},f⁡\(x,y\)=\(x−2\)2\+y2f\(x,y\)=\(x\-2\)^\{2\}\+y^\{2\},g⁡\(x,y\)=14​y4−12​x​y2g\(x,y\)=\\frac\{1\}\{4\}y^\{4\}\-\\frac\{1\}\{2\}xy^\{2\}\. Fig\.[1\(a\)](https://arxiv.org/html/2609.30501#S1.F1.sf1)shows the contour plot off⁡\(x,y\)f\(x,y\)along with converging trajectories with initial points\(0,2\)\(0,2\)and\(3,0\)\(3,0\), and Fig\.[1\(b\)](https://arxiv.org/html/2609.30501#S1.F1.sf2)plots\|f⁡\(xt,yt\)−f∗\|\|f\(x\_\{t\},y\_\{t\}\)\-f^\{\*\}\|vs\. iterationtt, illustrating how far the convergent sequences are from solving the LLNC\-BLO problem\. Our𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~\(Alg\.[1](https://arxiv.org/html/2609.30501#algorithm1)\) is theonlymethod thatescapes the saddle pointandfinds true solutions, compared to existing baselines methods: PBGD\([Shen and Chen, 2023](https://arxiv.org/html/2609.30501#bib.bib6)\), GALET\([Xiao et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib5)\), MEHA\([Liu et al\., 2024](https://arxiv.org/html/2609.30501#bib.bib8)\), and SUN\-DSBO\-SE\([Ma et al\., 2026](https://arxiv.org/html/2609.30501#bib.bib7)\)\.To address the limitations of FOSP\-based lower\-level surrogates, in this paper, we propose usingsecond\-order stationarityas a surrogate for LLNC\-BLO problems\. Mathematically, second\-order stationarity requires not only∇yg​\(x,y\)=0\\nabla\_\{y\}g\(x,y\)=0, but also that the Hessian with respect toyyis positive semidefinite \(PSD\), i\.e\.,λmin​\(∇y​y2g​\(x,y\)\)≥0\\lambda\_\{\\min\}\(\\nabla\_\{yy\}^\{2\}g\(x,y\)\)\\geq 0\. Our rationale for adopting this second\-order\-stationarity\-based lower\-level surrogate \(SOS\-LLS\) is that a PSD Hessian enforceslocal convexityin the lower\-level problem, thereby ruling out undesirable saddle points and guaranteeing at least local optimality with respect toyy\. As a concrete example, Fig\.[1](https://arxiv.org/html/2609.30501#S1.F1)shows that our𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~method, based on SOS\-LLS, successfully recovers true optimal solutions to the LLNC\-BLO problem\.

Table 1:Comparison of𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~\(Alg\.[1](https://arxiv.org/html/2609.30501#algorithm1)\) with state\-of\-the\-art LLNC\-BLO methods\.†\\dagger: BLO Setting states the assumptions on the lower level of the LLNC\-BLO\.‡\\ddagger: Surrogate Problem refers to the relaxed surrogate of the lower level of the LLNC\-BLO problem\. Moreau envelope\-based surrogates reduce to first\-order stationarity under smoothness conditions\([Ma et al\., 2026](https://arxiv.org/html/2609.30501#bib.bib7)\)\.Despite the significant advantage of avoiding undesirable saddle points, solving LLNC\-BLO problems through the SOS\-LLS reformulation remains largely underexplored, and both algorithm design and analysis are highly nontrivial\. This is primarily due to two fundamental challenges:\(i\)the SOS\-LLS reformulation leads to a constrained problem that is inherently non\-smooth, posing difficulties for algorithmic design; and\(ii\)under the LLNC setting, the upper\-level hypergradient is ill\-defined, leaving no natural metric to quantify the upper\-level stationarity gap\. In this paper, we address these challenges through the following key contributions:

- •Theoretical Foundations:For the first time in the literature, we propose to incorporate second\-order stationarity as the lower\-level surrogate for LLNC\-BLO problems, which allows to avoid undesirable saddle point solutions at the lower level without assuming the overly restrictive PL condition \(cf\.[Table1](https://arxiv.org/html/2609.30501#S1.T1)\)\. Building on the SOS\-LLS reformulation, we introduce a new augmented convergence metric that leverages second\-order stationarity to induce local curvature\. By progressively shrinking the augmentation parameter, the proposed metric recovers solutions to the original LLNC\-BLO problem, thereby providing a principled foundation for both algorithm design and analysis\.
- •Algorithmic Design and Analysis:Based on the proposed SOS\-LLS reformulation, we propose𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~\(Perturbed gradient algorithm forbilevel problem\), a new algorithm that efficiently probes and guarantees escaping saddle points in the lower level of LLNC\-BLO problems\. Theoretically, we show that𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~achieves a finite\-time convergence rate of𝒪⁡\(T−25\)\\mathcal\{O\}\(T^\{\-\\frac\{2\}\{5\}\}\)at the upper level while guaranteeing local optimality at the lower level for solving LLNC\-BLO problems, whereTTdenotes iteration counts\.
- •Empirical Validation:We validate the effectiveness of our𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~method through a dataset curation task for LLM fine\-tuning and a meta\-learning task, both of which can be formulated as a BLO problem\. Our experimental results demonstrate that𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~outperforms existing baselines\. We further conduct ablation studies to further reveal the significance of the key components in our proposed𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~method\.

## 2Related Work

In this section, we provide an overview on two related lines of research: \(i\) bilevel optimization \(BLO\), with a focus on methods that address BLO problems in the LLNC settings; and \(ii\) mechanisms for escaping saddle points in single\-level nonconvex optimization theory for machine learning\.

1\) Bilevel Optimization \(BLO\):The study of BLO traces its roots back to as early as[Bracken and McGill \(1973\)](https://arxiv.org/html/2609.30501#bib.bib10);[Ye and Zhu \(1995\)](https://arxiv.org/html/2609.30501#bib.bib35)\. In recent years, BLO has received significant attention within the machine learning community, primarily driven by the growing necessity of solving nested\-structured optimization problems in modern machine learning applications\. As mentioned earlier, most existing works in the BLO literature are based on the restrictive LLSC condition\([Franceschi et al\., 2018](https://arxiv.org/html/2609.30501#bib.bib15);[Ghadimi and Wang, 2018](https://arxiv.org/html/2609.30501#bib.bib18);[Shaban et al\., 2019](https://arxiv.org/html/2609.30501#bib.bib37);[Arbel and Mairal, 2021](https://arxiv.org/html/2609.30501#bib.bib36);[Ji et al\., 2021](https://arxiv.org/html/2609.30501#bib.bib9);[Yang et al\., 2021](https://arxiv.org/html/2609.30501#bib.bib19);[Dagréou et al\., 2022](https://arxiv.org/html/2609.30501#bib.bib20)\), which significantly limits the practical applicability of the BLO framework\. Due to the limitations of LLSC, researchers have recently started to relax the LLSC assumption to the LLGC assumption\([Cao et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib22);[Chen et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib39);[Jiang et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib23);[Liu et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib21);[Shen et al\., 2024b](https://arxiv.org/html/2609.30501#bib.bib38)\)\. However, the convexity requirement in LLGC still excludes a wide range of practical scenarios\. The widening gap between the demand for solving general BLO problems in the LLNC setting and the limited theoretical understanding of this BLO setting motivates the studies of LLNC\-BLO\. However, this area remains in its infancy, and existing works either impose strong structural assumptions or consider FOSP\-based relaxations of the LLNC\-BLO problem\([Kwon et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib24);[Shen and Chen, 2023](https://arxiv.org/html/2609.30501#bib.bib6);[Xiao et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib5);[Chen et al\., 2024](https://arxiv.org/html/2609.30501#bib.bib27);[Liu et al\., 2024](https://arxiv.org/html/2609.30501#bib.bib8);[Jiang et al\., 2025a](https://arxiv.org/html/2609.30501#bib.bib26);[Jiang et al\., 2025b](https://arxiv.org/html/2609.30501#bib.bib25);[Ma et al\., 2026](https://arxiv.org/html/2609.30501#bib.bib7)\)\. As shown in the illustrative example in[Figure1](https://arxiv.org/html/2609.30501#S1.F1)and[Table1](https://arxiv.org/html/2609.30501#S1.T1), these methods fail to distinguish local minima from saddle points at the lower level, leading to solutions that are significantly suboptimal compared to the true optimum of the original LLNC\-BLO problems\.

2\) Escaping Saddle Points in Single\-Level Nonconvex Optimization:It is well\-known that in the absence of convexity, traditional single\-level optimization becomes significantly more challenging: finding a global optimum is NP\-hard in general\([Murty et al\., 1987](https://arxiv.org/html/2609.30501#bib.bib40)\)\. In fact, even finding a local minimum solution in nonconvex optimization is highly nontrivial\. One of the primary challenges stems from the ubiquity of saddle points, particularly in the landscape of high\-dimensional objective functions\([Dauphin et al\., 2014](https://arxiv.org/html/2609.30501#bib.bib28)\), which is the typical regime where modern machine learning tasks reside\. Although second\-order methods naturally tackle this issue by actively probing and escaping saddle points, their dimension\-dependent convergence rates preclude them from practical large\-scale applications\. In the machine learning literature, the question of how to escape saddle points in nonconvex optimization was first systematically studied in[Ge et al\. \(2015\)](https://arxiv.org/html/2609.30501#bib.bib1)\. However, the convergence rate established in[Ge et al\. \(2015\)](https://arxiv.org/html/2609.30501#bib.bib1)scales polynomially with the dimension\. Inspired by this breakthrough, a significant amount of research effort has been dedicated to designing algorithms that reduce the dimension dependence to scale at a polylog fashion\([Agarwal et al\., 2017](https://arxiv.org/html/2609.30501#bib.bib41);[Jin et al\., 2017](https://arxiv.org/html/2609.30501#bib.bib2);[Allen\-Zhu and Li, 2018](https://arxiv.org/html/2609.30501#bib.bib42);[Fang et al\., 2018](https://arxiv.org/html/2609.30501#bib.bib45);[Jin et al\., 2018](https://arxiv.org/html/2609.30501#bib.bib3);[Liu et al\., 2018](https://arxiv.org/html/2609.30501#bib.bib44);[Jin et al\., 2021](https://arxiv.org/html/2609.30501#bib.bib43);[Zhang and Li, 2021](https://arxiv.org/html/2609.30501#bib.bib4)\)\. Another closely related line of research focuses on zeroth\-order methods for escaping saddle points\([Vlatakis\-Gkaragkounis et al\., 2019](https://arxiv.org/html/2609.30501#bib.bib46);[Zhang et al\., 2022a](https://arxiv.org/html/2609.30501#bib.bib47);[Zhang and Gu, 2022](https://arxiv.org/html/2609.30501#bib.bib49);[Ren et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib48)\)\. To our knowledge, the only works that incorporated saddle point escaping techniques in the BLO framework are[Huang et al\. \(2025\)](https://arxiv.org/html/2609.30501#bib.bib34);[Chen et al\. \(2025\)](https://arxiv.org/html/2609.30501#bib.bib50)\. However, these studies are limited to the LLSC\-based setting and only considered escaping saddle points at the upper level, which arefundamentally different fromandmuch simpler thanour setting, where we investigate saddle point escaping at the lower level for the LLNC setting\.

## 3The Second\-Order Stationarity\-Based Lower\-Level Surrogate

In this section, we present the second\-order stationarity\-based lower\-level surrogate reformulation for the LLNC\-BLO problem\. We begin by introducing several standard smoothness conditions that are needed to formally define second\-order stationary points:

###### Assumption 1\(Smoothness of the Upper\- and Lower\-Level Objective Functions\)\.

The upper\- and lower\-level objective functionsffandggare twice differentiable, and there exist positive constantsν,ℓ,ρ\\nu,\\ell,\\rho, such that for anyz=\(x,y\)z=\(x,y\)andz′=\(x′,y′\)z^\{\\prime\}=\(x^\{\\prime\},y^\{\\prime\}\), it holds that:

\|f⁡\(z\)−f⁡\(z′\)\|≤ν​‖z−z′‖,‖∇f​\(z\)−∇f​\(z′\)‖≤ℓ​‖z−z′‖,\\displaystyle\|f\(z\)\-f\(z^\{\\prime\}\)\|\\leq\\nu\\\|z\-z^\{\\prime\}\\\|,\\,\\,\\,\\,\\,\\,\\\|\\nabla f\(z\)\-\\nabla f\(z^\{\\prime\}\)\\\|\\leq\\ell\\\|z\-z^\{\\prime\}\\\|,‖∇g​\(z\)−∇g​\(z′\)‖≤ℓ​‖z−z′‖,‖∇2g​\(z\)−∇2g​\(z′\)‖≤ρ​‖z−z′‖,\\displaystyle\\\|\\nabla g\(z\)\-\\nabla g\(z^\{\\prime\}\)\\\|\\leq\\ell\\\|z\-z^\{\\prime\}\\\|,\\,\\,\\,\\,\\,\\,\\\|\\nabla^\{2\}g\(z\)\-\\nabla^\{2\}g\(z^\{\\prime\}\)\\\|\\leq\\rho\\\|z\-z^\{\\prime\}\\\|,where∥⋅∥\\\|\\cdot\\\|denotes Euclidean and spectral norm for vectors and matrices hereafter, respectively\.

We note that the smoothness assumptions above are not only widely adopted in the BLO literature\([Ghadimi and Wang, 2018](https://arxiv.org/html/2609.30501#bib.bib18);[Ji et al\., 2021](https://arxiv.org/html/2609.30501#bib.bib9);[Yang et al\., 2021](https://arxiv.org/html/2609.30501#bib.bib19);[Xiao et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib5)\), but they have also been numerically observed and verified in large\-scale modern machine learning models, such as LLMs\([Castin et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib56);[Malladi et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib55);[Li et al\., 2024](https://arxiv.org/html/2609.30501#bib.bib57)\)\.

Equipped with these smoothness properties, we now formally define stationary points, local minima, and saddle points for the lower\-level of the LLNC\-BLO problem\.

###### Definition 1\(First\- and Second\-Order Stationary Point\)\.

Suppose[Assumption1](https://arxiv.org/html/2609.30501#Thmassumption1)holds, and letλmin​\(⋅\)\\lambda\_\{\\min\}\(\\cdot\)denote the minimal eigenvalue of a matrix\. For any givenx∈ℝpx\\in\\mathbb\{R\}^\{p\}and any positiveϵ\\epsilon,

- 1\.yyis a first\-order stationary point \(FOSP\) if∇yg​\(x,y\)=0\\nabla\_\{y\}g\(x,y\)=0\. It is anϵ\\epsilon\-FOSP if‖∇yg​\(x,y\)‖≤ϵ\\\|\\nabla\_\{y\}g\(x,y\)\\\|\\leq\\epsilon\.
- 2\.yyis a second\-order stationary point \(SOSP\) if∇yg​\(x,y\)=0\\nabla\_\{y\}g\(x,y\)=0andλmin​\(∇y​y2g​\(x,y\)\)≥0\\lambda\_\{\\min\}\(\\nabla^\{2\}\_\{yy\}g\(x,y\)\)\\geq 0\. It is anϵ\\epsilon\-SOSP if‖∇yg​\(x,y\)‖≤ϵ\\\|\\nabla\_\{y\}g\(x,y\)\\\|\\leq\\epsilonandλmin​\(∇y​y2g​\(x,y\)\)≥−ρ​ϵ\\lambda\_\{\\min\}\(\\nabla^\{2\}\_\{yy\}g\(x,y\)\)\\geq\-\\sqrt\{\\rho\\epsilon\}\.

We note that the definition ofϵ\\epsilon\-second\-order stationary point here has also been adopted in the literature\([Nesterov and Polyak, 2006](https://arxiv.org/html/2609.30501#bib.bib30);[Jin et al\., 2017](https://arxiv.org/html/2609.30501#bib.bib2);[Jin et al\., 2018](https://arxiv.org/html/2609.30501#bib.bib3);[Zhang and Li, 2021](https://arxiv.org/html/2609.30501#bib.bib4)\)\.

###### Definition 2\(Local Minimum and Saddle Point\)\.

Suppose thatggis differentiable\. For any givenx∈ℝpx\\in\\mathbb\{R\}^\{p\},yyis a local minimum if∇yg​\(x,y\)=0\\nabla\_\{y\}g\(x,y\)=0and there existsδ\>0\\delta\>0such thatg⁡\(x,y\)≤g⁡\(x,y′\)g\(x,y\)\\leq g\(x,y^\{\\prime\}\)for ally′∈𝔹y​\(δ\)y^\{\\prime\}\\in\\mathbb\{B\}\_\{y\}\(\\delta\), where𝔹y​\(δ\)\\mathbb\{B\}\_\{y\}\(\\delta\)denotes an open ball of radiusδ\\deltacentered atyy\. In contrast,yyis a saddle point if∇yg​\(x,y\)=0\\nabla\_\{y\}g\(x,y\)=0and it is not a local minimum\.

When all saddle points are strict, i\.e\.,λmin​\(∇y​y2g​\(x,y\)\)<0\\lambda\_\{\\min\}\(\\nabla^\{2\}\_\{yy\}g\(x,y\)\)<0holds for all saddle points, attaining a second\-order stationary point is equivalent to reaching a local minimum\. In fact, this “strict” property has been extensively verified and documented for saddle points across various nonconvex landscapes \(e\.g\., tensor decomposition or low\-rank matrix recovery, see, e\.g\.,\([Ge et al\., 2015](https://arxiv.org/html/2609.30501#bib.bib1);[Bhojanapalli et al\., 2016](https://arxiv.org/html/2609.30501#bib.bib31);[Ge et al\., 2016](https://arxiv.org/html/2609.30501#bib.bib32);[Jin et al\., 2017](https://arxiv.org/html/2609.30501#bib.bib2);[Sun et al\., 2018](https://arxiv.org/html/2609.30501#bib.bib29)\), and see Appendix[D](https://arxiv.org/html/2609.30501#A4)for more discussions\.\)111While finding an SOSP does not theoretically preclude convergence to non\-strict saddle points that could occur in highly overparameterized deep learning landscapes, it remains strictly far more advantageous than relying on FOSP\. SOSP guarantees the evasion of all strict saddle points, including local maxima, by explicitly exploiting directions of negative curvature\. Furthermore, because escaping non\-strict saddle points generally requires computationally intractable higher\-order derivatives, targeting an SOSP represents the strongest practically verifiable optimality condition\. Empirically, the non\-strict saddles satisfying SOSP conditions in deep networks often lie on flat manifolds that yield highly desirable generalization properties\.\.

Given the NP\-hardness of finding global optima for general nonconvex objective functions, it is standard practice to target local optimal solutions instead \(i\.e\., points that satisfy the necessary conditions for global optimality\)\. However, as previously noted, simply relaxing the lower\-level optimality constraint to merely finding an FOSP\([Shen and Chen, 2023](https://arxiv.org/html/2609.30501#bib.bib6);[Xiao et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib5);[Liu et al\., 2024](https://arxiv.org/html/2609.30501#bib.bib8);[Ma et al\., 2026](https://arxiv.org/html/2609.30501#bib.bib7)\)is problematic, as it introduces the risk of converging to undesirable saddle points\. Fortunately, under the strict saddle assumption, identifying an SOSP yields local minima\. Thus, we propose to reformulate the LLNC\-BLO problem with the following SOSP\-based surrogate:

minx∈ℝp,y∈ℝq⁡f⁡\(x,y\),subject to​∇yg​\(x,y\)=0,λmin​\(∇y​y2g​\(x,y\)\)≥0\.\\min\_\{x\\in\\mathbb\{R\}^\{p\},y\\in\\mathbb\{R\}^\{q\}\}f\(x,y\),\\hskip 20\.00003pt\\text\{subject to \}\\nabla\_\{y\}g\(x,y\)=0,\\,\\,\\,\\lambda\_\{\\min\}\(\\nabla^\{2\}\_\{yy\}g\(x,y\)\)\\geq 0\.\(2\)

## 4The Proposed𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~Algorithm

Based on the SOSP\-based lower\-level surrogate for LLNC\-BLO problems, in this section, we will investigate how to design an efficient algorithm for solving in Eq\.[2](https://arxiv.org/html/2609.30501#S3.E2)\. We start with defining an appropriate metric to measure the convergence error in designing algorithms for solving Eq\.[2](https://arxiv.org/html/2609.30501#S3.E2)\.

Suppose that\(x~,y~\)\(\\tilde\{x\},\\tilde\{y\}\)is anϵ′\\epsilon^\{\\prime\}\-SOSP forg⁡\(x~,⋅\)g\(\\tilde\{x\},\\cdot\)for some positiveϵ′\\epsilon^\{\\prime\}\. According to[Definition1](https://arxiv.org/html/2609.30501#Thmdefinition1), we have that∇y​y2​g​\(x~,y~\)\+\(ρ​ϵ′\+σ\)​Iq\\nabla\_\{yy\}^\{2\}g\(\\tilde\{x\},\\tilde\{y\}\)\+\(\\sqrt\{\\rho\\epsilon^\{\\prime\}\}\+\\sigma\)I\_\{q\}is positive definite for any arbitrarily small positive valueσ\>0\\sigma\>0\(which can be adaptively selected according toϵ′\\epsilon^\{\\prime\}\)\. It then follows that the augmented objective functiong⁡\(x~,y\)\+μ2​‖y−y~‖2g\(\\tilde\{x\},y\)\+\\frac\{\\mu\}\{2\}\\\|y\-\\tilde\{y\}\\\|^\{2\}is locallyσ2\\frac\{\\sigma\}\{2\}\-strongly convex within a sufficiently small neighborhood ofy~\\tilde\{y\}, where the parameterμ≜μ⁡\(ϵ′,σ\):=ρ​ϵ′\+σ\\mu\\triangleq\\mu\(\\epsilon^\{\\prime\},\\sigma\):=\\sqrt\{\\rho\\epsilon^\{\\prime\}\}\+\\sigma\. By leveraging this local quadratic curvature, we can define the followingμ\\mu\-augmented implicit functionwith a small positive radiusr′=σρr^\{\\prime\}=\\frac\{\\sigma\}\{\\rho\}:

Φμ​\(x~\):=f⁡\(x~,yμ∗​\(x~\)\),where​yμ∗​\(x~\):=arg​miny∈𝔹y~​\(r′\)⁡\{g⁡\(x~,y\)\+μ2​‖y−y~‖2\},\\displaystyle\\Phi\_\{\\mu\}\(\\tilde\{x\}\):=f\(\\tilde\{x\},y\_\{\\mu\}^\{\*\}\(\\tilde\{x\}\)\),\\,\\,\\,\\text\{where \}y\_\{\\mu\}^\{\*\}\(\\tilde\{x\}\):=\\argmin\_\{y\\in\\mathbb\{B\}\_\{\\tilde\{y\}\}\(r^\{\\prime\}\)\}\\\{g\(\\tilde\{x\},y\)\+\\frac\{\\mu\}\{2\}\\\|y\-\\tilde\{y\}\\\|^\{2\}\\\},where the existence and uniqueness ofyμ∗​\(x~\)y\_\{\\mu\}^\{\*\}\(\\tilde\{x\}\)can be guaranteed by the local strong convexity\. Indeed, the introduction ofμ\\mu\-regularization restores a locally strongly convex curvature, thereby enabling the use of existing techniques from the LLSC\-BLO setting, such as hypergradient\-based methods\([Ghadimi and Wang, 2018](https://arxiv.org/html/2609.30501#bib.bib18);[Grazzi et al\., 2020](https://arxiv.org/html/2609.30501#bib.bib33);[Ji et al\., 2021](https://arxiv.org/html/2609.30501#bib.bib9);[Huang et al\., 2025](https://arxiv.org/html/2609.30501#bib.bib34)\)\. Consequently, following from the Implicit Function Theorem \(IFT\), the gradient ofΦμ​\(x~\)\\Phi\_\{\\mu\}\(\\tilde\{x\}\), referred to as theμ\\mu\-augmented hypergradient in this paper, can be computed as:

∇Φμ​\(x~\)\\displaystyle\\nabla\\Phi\_\{\\mu\}\(\\tilde\{x\}\)=∇xf​\(x~,yμ∗​\(x~\)\)\+d​yμ∗​\(x~\)d​x​∇yf​\(x~,yμ∗​\(x~\)\)\\displaystyle=\\nabla\_\{x\}f\(\\tilde\{x\},y\_\{\\mu\}^\{\*\}\(\\tilde\{x\}\)\)\+\\frac\{dy\_\{\\mu\}^\{\*\}\(\\tilde\{x\}\)\}\{dx\}\\nabla\_\{y\}f\(\\tilde\{x\},y\_\{\\mu\}^\{\*\}\(\\tilde\{x\}\)\)=∇xf​\(x~,yμ∗​\(x~\)\)−∇x​y2g​\(x~,yμ∗​\(x~\)\)​\[∇y​y2g​\(x~,yμ∗​\(x~\)\)\+μ​Iq\]−1​∇yf​\(x~,yμ∗​\(x~\)\)\.\\displaystyle=\\nabla\_\{x\}f\(\\tilde\{x\},y\_\{\\mu\}^\{\*\}\(\\tilde\{x\}\)\)\-\\nabla\_\{xy\}^\{2\}g\(\\tilde\{x\},y\_\{\\mu\}^\{\*\}\(\\tilde\{x\}\)\)\\left\[\\nabla\_\{yy\}^\{2\}g\(\\tilde\{x\},y\_\{\\mu\}^\{\*\}\(\\tilde\{x\}\)\)\+\\mu I\_\{q\}\\right\]^\{\-1\}\\nabla\_\{y\}f\(\\tilde\{x\},y\_\{\\mu\}^\{\*\}\(\\tilde\{x\}\)\)\.
Theμ\\mu\-augmented hypergradient naturally gives rise to the following convergence metric:

###### Definition 3\(μ\\mu\-Augmented Hypergradient\-Based Convergence Metric\)\.

Supposeyyis anϵ′\\epsilon^\{\\prime\}\-SOSP for a givenxx\(as defined in Def\.[1](https://arxiv.org/html/2609.30501#Thmdefinition1)\) and all saddle points are strict\. For any positiveϵ,μ=ρ​ϵ′\+σ\\epsilon,\\mu=\\sqrt\{\\rho\\epsilon^\{\\prime\}\}\+\\sigma,\(x,y\)\(x,y\)is said to be an\(ϵ,μ\)\(\\epsilon,\\mu\)\-stationary solution to Eq\.[2](https://arxiv.org/html/2609.30501#S3.E2)if it satisfies:Π⁡\(x,y\):=‖∇Φμ​\(x\)‖2\+ϵ′≤ϵ\\Pi\(x,y\):=\\\|\\nabla\\Phi\_\{\\mu\}\(x\)\\\|^\{2\}\+\\epsilon^\{\\prime\}\\leq\\epsilon\.

With the formal definition of this convergence metric and the SOSP\-based lower\-level surrogate for the LLNC\-BLO problem, the following key question naturally arises:

Question: Is theμ\\mu\-augmented hypergradient a good estimation of the “steepest descent update direction” of the original LLNC\-BLO problem in terms ofxx? More importantly, how to control theμ\\mu\-parameter in the SOSP\-based surrogate in order to ensure that we still converge to a good solution to the original LLNC\-BLO problem with a lower\-level local optimality guarantee?

Although this question is challenging to answer in the highly complex LLNC setting, one may obtain some high\-level qualitative understanding by measuring the “bias” of theμ\\mu\-augmented hypergradient when a hypergradient is well\-defined \(note that in LLNC\-BLO, a hypergradient could be ill\-posed if the Hessian of the lower\-level problem is rank\-deficient\)\. More specifically, note that if the sequence generated by an algorithm is able to escape strict saddle points, it typically reaches a local minimum, where the lower\-level objective function usually exhibits sufficient local curvature in a bounded local neighborhood, so that its landscape can be bounded from below by a quadratic function\. Consider a scenario in which∇y​y2g​\(x~,yμ∗​\(x~\)\)⪰μ0​Iq\\nabla\_\{yy\}^\{2\}g\(\\tilde\{x\},y\_\{\\mu\}^\{\*\}\(\\tilde\{x\}\)\)\\succeq\\mu\_\{0\}I\_\{q\}holds for someμ0\>0\\mu\_\{0\}\>0, so that a hypergradient is well\-defined\. Due to the fact thatA−1−B−1=A−1​\(B−A\)​B−1A^\{\-1\}\-B^\{\-1\}=A^\{\-1\}\(B\-A\)B^\{\-1\}, we can bound the discrepancy between theμ\\mu\-augmented hypergradient and the true hypergradient as follows:

‖∇Φμ​\(x~\)−∇Φ0​\(x~\)‖\\displaystyle\\\|\\nabla\\Phi\_\{\\mu\}\(\\tilde\{x\}\)\-\\nabla\\Phi\_\{0\}\(\\tilde\{x\}\)\\\|=‖∇x​y2g​\(\[∇y​y2g\]−1​\(μ​Iq\)​\[∇y​y2g\+μ​Iq\]−1\)​∇yf‖\\displaystyle=\\left\\\|\\nabla\_\{xy\}^\{2\}g\\left\(\\left\[\\nabla\_\{yy\}^\{2\}g\\right\]^\{\-1\}\(\\mu I\_\{q\}\)\\left\[\\nabla\_\{yy\}^\{2\}g\+\\mu I\_\{q\}\\right\]^\{\-1\}\\right\)\\nabla\_\{y\}f\\right\\\|≤‖∇x​y2g‖⋅‖\[∇y​y2g\]−1‖⋅μ⋅‖\[∇y​y2g\+μ​Iq\]−1‖⋅‖∇yf‖\\displaystyle\\leq\\\|\\nabla\_\{xy\}^\{2\}g\\\|\\cdot\\left\\\|\\left\[\\nabla\_\{yy\}^\{2\}g\\right\]^\{\-1\}\\right\\\|\\cdot\\mu\\cdot\\left\\\|\\left\[\\nabla\_\{yy\}^\{2\}g\+\\mu I\_\{q\}\\right\]^\{\-1\}\\right\\\|\\cdot\\\|\\nabla\_\{y\}f\\\|≤\(a\)​ℓ⋅1μ0⋅μ⋅1μ0\+μ⋅ν≤ℓ​νμ02​\(ρ​ϵ′\+σ\)=𝒪⁡\(ϵ′\+σ\),\\displaystyle\\overset\{\(a\)\}\{\\leq\}\\ell\\cdot\\frac\{1\}\{\\mu\_\{0\}\}\\cdot\\mu\\cdot\\frac\{1\}\{\\mu\_\{0\}\+\\mu\}\\cdot\\nu\\leq\\frac\{\\ell\\nu\}\{\\mu\_\{0\}^\{2\}\}\(\\sqrt\{\\rho\\epsilon^\{\\prime\}\}\+\\sigma\)=\\mathcal\{O\}\(\\sqrt\{\\epsilon^\{\\prime\}\}\+\\sigma\),where\(a\)\(a\)follows from[Assumption1](https://arxiv.org/html/2609.30501#Thmassumption1)\. This shows that theμ\\mu\-augmented hypergradient incurs an approximation bias that scales at most linearly with both the square root of the SOSP violationϵ′\\sqrt\{\\epsilon^\{\\prime\}\}and the augmentation parameterσ\\sigma\. To mitigate the impact of such “bias”, we can adaptively shrink bothϵt\\epsilon\_\{t\}andσt\\sigma\_\{t\}in the design of our algorithm to progressively refine the lower\-level solutions\. Specifically, by using a dynamic sequence\{μt=ρ​ϵt\+σt\}t\\\{\\mu\_\{t\}=\\sqrt\{\\rho\\epsilon\_\{t\}\}\+\\sigma\_\{t\}\\\}\_\{t\}that approaches0\+0^\{\+\}ast→∞t\\to\\infty, the “bias” can be gradually eliminated to induce convergence to a solution with vanishing bias to the original LLNC\-BLO problem\. Based on this intuition, we propose𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~\(Perturbed gradient algorithm forbilevel problem\), which is summarized in Algorithms[1](https://arxiv.org/html/2609.30501#algorithm1)and[2](https://arxiv.org/html/2609.30501#algorithm2)\. In what follows, we will first describe the basic idea and the key steps of𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}\. The theoretical convergence analysis of𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~will be provided in[Section5](https://arxiv.org/html/2609.30501#S5)\.

Algorithm 1The overall𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~algorithmic framework\.Input:Iteration

T,Kt,NtT,K\_\{t\},N\_\{t\}, initial points

x0,y0,v0x\_\{0\},y\_\{0\},v\_\{0\}, step\-sizes

αt,βt\\alpha\_\{t\},\\beta\_\{t\}, aggregation parameters

μt\\mu\_\{t\}, and PGD parameters

rt,ϱt,ΔG,t,ΔK,tr\_\{t\},\\varrho\_\{t\},\\Delta\_\{G,t\},\\Delta\_\{K,t\}, where

t∈\{0,…,T−1\}t\\in\\\{0,\\dotsc,T\-1\\\}
1for*t=0,…,T−1t=0,\\dots,T\-1*do

2Update

yt\+1←PGD​\(Kt,xt,yt,βt,rt,ϱt,ΔG,t,ΔK,t\)y\_\{t\+1\}\\leftarrow\\text\{PGD\}\\big\(K\_\{t\},x\_\{t\},y\_\{t\},\\beta\_\{t\},r\_\{t\},\\varrho\_\{t\},\\Delta\_\{G,t\},\\Delta\_\{K,t\}\\big\)
3Solve

\(∇y​y2g​\(xt,yt\+1\)\+μt​Iq\)​v=∇yf​\(xt,yt\+1\)\\big\(\\nabla\_\{yy\}^\{2\}g\(x\_\{t\},y\_\{t\+1\}\)\+\\mu\_\{t\}I\_\{q\}\\big\)v=\\nabla\_\{y\}f\(x\_\{t\},y\_\{t\+1\}\)from

vtv\_\{t\}by

NtN\_\{t\}\-step Conjugate Gradient with a warm start to get

vt\+1v\_\{t\+1\}
4Update

xt\+1←xt−αt​∇^​Φμt​\(xt\)x\_\{t\+1\}\\leftarrow x\_\{t\}\\\!\-\\\!\\alpha\_\{t\}\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\), where

∇^​Φμt​\(xt\)=∇xf​\(xt,yt\+1\)−∇x​y2g​\(xt,yt\+1\)​vt\+1\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)=\\nabla\_\{x\}f\(x\_\{t\},y\_\{t\+1\}\)\\\!\-\\\!\\nabla\_\{xy\}^\{2\}g\(x\_\{t\},y\_\{t\+1\}\)v\_\{t\+1\}
5return

\(xT,yT\)\(x\_\{T\},y\_\{T\}\)

Algorithm 2The perturbed gradient descent subroutine PGD\(K,x,y0,β,r,ϱ,ΔG,ΔKK,x,y^\{0\},\\beta,r,\\varrho,\\Delta\_\{G\},\\Delta\_\{K\}\)\.τ←−ΔK−1\\tau\\leftarrow\-\\Delta\_\{K\}\-1

1for*k=0,…,K−1k=0,\\dots,K\-1*do

2if*‖∇yg​\(x,yk\)‖≤ϱ\\\|\\nabla\_\{y\}g\(x,y^\{k\}\)\\\|\\leq\\varrhoandk−τ\>ΔKk\-\\tau\>\\Delta\_\{K\}*then

3

y~←yk,τ←k\\tilde\{y\}\\leftarrow y^\{k\},\\,\\,\\,\\,\\,\\,\\tau\\leftarrow k//Store anchor point & Update timestamp

4

ξ∼Unif​\(𝔹𝟎​\(r\)\),yk←yk\+ξ\\xi\\sim\\text\{Unif\}\(\\mathbb\{B\}\_\{\\bf\{0\}\}\(r\)\),\\,\\,\\,\\,\\,\\,y^\{k\}\\leftarrow y^\{k\}\+\\xi//Inject uniform noise

5if*k−τ=ΔKk\-\\tau=\\Delta\_\{K\}andg⁡\(x,yk\)−g⁡\(x,y~\)\>−ΔGg\(x,y^\{k\}\)\-g\(x,\\tilde\{y\}\)\>\-\\Delta\_\{G\}*then

6return

y~\\tilde\{y\}//Return confirmed SOSP

7

yk\+1←yk−β​∇yg​\(x,yk\)y^\{k\+1\}\\leftarrow y^\{k\}\-\\beta\\nabla\_\{y\}g\(x,y^\{k\}\)

1\) Basic Idea:𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~employs a double\-loop framework, where the inner loop is dedicated to finding anϵt\\epsilon\_\{t\}\-SOSP of the lower\-level objectiveg⁡\(xt,⋅\)g\(x\_\{t\},\\cdot\)for a given upper\-level variablextx\_\{t\}in steptt, while the outer loop utilizes this approximation to construct aμt\\mu\_\{t\}\-augmented hypergradient, which guides the update of the upper\-level variablextx\_\{t\}towards the minimum ofΦμt​\(⋅\)\\Phi\_\{\\mu\_\{t\}\}\(\\cdot\)with a shrinkingμt\\mu\_\{t\}\.

2\) SOSP Approximation via PGD \(Inner\-Loop\):The inner\-loop \(Algorithm[2](https://arxiv.org/html/2609.30501#algorithm2)\) employs Perturbed Gradient Descent \(PGD,[Jin et al\. \(2017\)](https://arxiv.org/html/2609.30501#bib.bib2)\) to identify SOSP approximations\. In order to escape saddle points, PGD monitors the gradient: if‖∇yg​\(x,yk\)‖≤ϱ\\\|\\nabla\_\{y\}g\(x,y^\{k\}\)\\\|\\leq\\varrho, it injects a uniform noiseξ∼Unif​\(𝔹𝟎​\(r\)\)\\xi\\sim\\text\{Unif\}\(\\mathbb\{B\}\_\{\\bf\{0\}\}\(r\)\)for a more aggressive exploration, whererrdenotes the radius of a ball and will be selected later\. After several steps, the algorithm confirms that the iterate has reached an approximate SOSP if the function value has an insufficient reduction \(i\.e\.,g⁡\(x,yk\)−g⁡\(x,y~\)\>−ΔGg\(x,y^\{k\}\)\-g\(x,\\tilde\{y\}\)\>\-\\Delta\_\{G\}\)\. Finally, the inner\-loop returns the identifiedϵt\\epsilon\_\{t\}\-SOSP to the outer\-loop at each outer iterationttby adaptively and properly selecting parameters \(Kt,ϱt,ΔG,t,ΔK,tK\_\{t\},\\varrho\_\{t\},\\Delta\_\{G,t\},\\Delta\_\{K,t\}\)\.

3\)μt\\mu\_\{t\}\-Hypergradient Estimation and Update \(Outer\-Loop\):Building upon the lower\-level solutionyt\+1y\_\{t\+1\}identified by the inner\-loop, the outer\-loop \(𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~, Algorithm[1](https://arxiv.org/html/2609.30501#algorithm1)\) proceeds to update the upper\-level variable\. In theμt\\mu\_\{t\}\-augmented hypergradient, the primary computational bottleneck lies in estimating the Hessian inverse\[∇y​y2​g​\(xt,yt\+1\)\+μt​Iq\]−1\[\\nabla\_\{yy\}^\{2\}g\(x\_\{t\},y\_\{t\+1\}\)\+\\mu\_\{t\}I\_\{q\}\]^\{\-1\}\. We address this by employing the Conjugate Gradient \(CG\) method\([Grazzi et al\., 2020](https://arxiv.org/html/2609.30501#bib.bib33);[Ji et al\., 2021](https://arxiv.org/html/2609.30501#bib.bib9)\), an inversion\-free approach that only queries Hessian\-vector products\. This allows𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~to efficiently compute the adjoint variablevt\+1v\_\{t\+1\}withinNtN\_\{t\}iterations at every time slottt\. Furthermore, we equip theNtN\_\{t\}\-step CG with a warm start mechanism \(conducting CG in thett\-round beginning from the last outputvtv\_\{t\}\), which significantly accelerates convergence to reach a faster rate\. Finally, using the estimatedμt\\mu\_\{t\}\-augmented hypergradient∇^​Φμt​\(xt\)\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\), we perform a gradient descent step to update upper\-level variable toxt\+1x\_\{t\+1\}\. As will be mentioned in the next section, to ensure the convergence to a good solution of the original LLNC\-BLO problem, we dynamically increase and decrease the parametersKtK\_\{t\}andσt\\sigma\_\{t\}, respectively, to shrinkμt=ρ​ϵt\+σt\\mu\_\{t\}=\\sqrt\{\\rho\\epsilon\_\{t\}\}\+\\sigma\_\{t\}toward00at an appropriate rate\.

## 5Finite\-Time Convergence Analysis of𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~

In this section, we will conduct theoretical convergence analysis of our proposed𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~algorithm\. Toward this end, we first restate the iteration complexity performance guarantee of the PGD method\([Jin et al\., 2017](https://arxiv.org/html/2609.30501#bib.bib2)\), which is adapted in the context of LLNC\-BLO in Algorithm[2](https://arxiv.org/html/2609.30501#algorithm2)\.

###### Lemma 1\(Iteration Complexity of PGD\)\.

Under[Assumption1](https://arxiv.org/html/2609.30501#Thmassumption1), with hyperparameter choices in Appendix[B](https://arxiv.org/html/2609.30501#A2), for anyδ′∈\(0,1\),ϵt≤ℓ2/ρ,Δg,t≥g⁡\(xt,yt\)−infyg⁡\(xt,y\)\\delta^\{\\prime\}\\in\(0,1\),\\epsilon\_\{t\}\\leq\\ell^\{2\}/\\rho,\\Delta\_\{g,t\}\\geq g\(x\_\{t\},y\_\{t\}\)\-\\inf\_\{y\}g\(x\_\{t\},y\), with probability at least1−δ′1\-\\delta^\{\\prime\},[Algorithm2](https://arxiv.org/html/2609.30501#algorithm2)outputs anϵt\\epsilon\_\{t\}\-SOSP with iterations no more thanKt=𝒪⁡\(ℓ​Δg,tϵt2​log4⁡\(q​ℓ​Δg,tϵt2​δ′\)\)K\_\{t\}=\\mathcal\{O\}\\big\(\\frac\{\\ell\\Delta\_\{g,t\}\}\{\\epsilon\_\{t\}^\{2\}\}\\log^\{4\}\\big\(\\frac\{q\\ell\\Delta\_\{g,t\}\}\{\\epsilon\_\{t\}^\{2\}\\delta^\{\\prime\}\}\\big\)\\big\)\.

We note that, besides PGD, several algorithms have been proposed to escape saddle points while maintaining nearly dimension\-free convergence rates\([Jin et al\., 2018](https://arxiv.org/html/2609.30501#bib.bib3);[Jin et al\., 2021](https://arxiv.org/html/2609.30501#bib.bib43);[Zhang and Li, 2021](https://arxiv.org/html/2609.30501#bib.bib4)\)\. While these approaches offer improvements in iteration complexity to some degree \(fromϵt−2\\epsilon\_\{t\}^\{\-2\}toϵt−1\.75\\epsilon\_\{t\}^\{\-1\.75\}at most\), they typically introduce additional algorithmic modules, such as Negative Curvature Finding \(NCF\) and Nesterov\-style acceleration, which significantly complicate the implementation of the inner\-loop algorithm\. Moreover, rather than offering a “last\-iteration” convergence guarantee, these accelerated methods only guarantee an approximate SOSP being visited at some point within the trajectory\. This renders them ill\-suited for algorithm designs for LLNC\-BLO, which requires a terminal SOSP estimate\. We are now ready to state the main convergence result for𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~\.

###### Theorem 1\.

By selectingKt=Θ~​\(\(t\+1\)85\)K\_\{t\}=\\widetilde\{\\Theta\}\\big\(\(t\+1\)^\{\\frac\{8\}\{5\}\}\\big\),σt=Θ⁡\(\(t\+1\)−p\)\\sigma\_\{t\}=\\Theta\\big\(\(t\+1\)^\{\-p\}\\big\)andαt=Θ⁡\(\(t\+1\)−q\)\\alpha\_\{t\}=\\Theta\\big\(\(t\+1\)^\{\-q\}\\big\)withp∈\(0,13\),3​p≤q<1p\\in\(0,\\frac\{1\}\{3\}\),3p\\leq q<1, for anyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta, the sequence\{xt,yt\}t\\\{x\_\{t\},y\_\{t\}\\\}\_\{t\}generated by[Algorithm1](https://arxiv.org/html/2609.30501#algorithm1)satisfies the following convergence guarantee:minT2≤t≤T⁡Π⁡\(xt,yt\)=𝒪⁡\(1T1−q\+1T2​p\+1T45\)\\min\_\{\\frac\{T\}\{2\}\\leq t\\leq T\}\\Pi\(x\_\{t\},y\_\{t\}\)=\\mathcal\{O\}\(\\frac\{1\}\{T^\{1\-q\}\}\+\\frac\{1\}\{T^\{2p\}\}\+\\frac\{1\}\{T^\{\\frac\{4\}\{5\}\}\}\)\. By selecting\(p,q\)=\(15,35\)\(p,q\)=\(\\frac\{1\}\{5\},\\frac\{3\}\{5\}\), we haveminT2≤t≤T⁡Π⁡\(xt,yt\)=𝒪⁡\(T−25\)\\min\_\{\\frac\{T\}\{2\}\\leq t\\leq T\}\\Pi\(x\_\{t\},y\_\{t\}\)=\\mathcal\{O\}\\big\(T^\{\-\\frac\{2\}\{5\}\}\\big\)\.

Proof Sketch\.Our convergence analysis is organized in three key steps \(proof details of[Theorem1](https://arxiv.org/html/2609.30501#Thmtheorem1)are relegated to Appendix[B](https://arxiv.org/html/2609.30501#A2)due to limited space\):

- •Step 1\) Bounding the Variable Drifts:We first control the tracking errors of the lower\-level variableyyand the adjoint multipliervv\. A major challenge here is decomposing and bounding several intertwined gaps: the inner\-iteration solver error \(i\.e\., takingyyfor example hereafter,‖yt\+1−yμt∗​\(xt\)‖\\\|y\_\{t\+1\}\-y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|\), and the parameter\-induced shift across varyingμ\\mu\(i\.e\.,‖yμt\+1∗​\(xt\)−yμt∗​\(xt\)‖\\\|y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|\)\.
- •Step 2\) Controlling the Augmented Implicit Function Shift:Next, we analyze the dynamics ofΦμt\+1​\(xt\+1\)−Φμt​\(xt\)\\Phi\_\{\\mu\_\{t\+1\}\}\(x\_\{t\+1\}\)\-\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\), which is challenging due to simultaneous updates in both the variablexxand the parameterμ\\mu\. We decompose this shift into two components: \(i\) the contribution from the dynamics ofxx, which can be controlled using the smoothness of the augmented implicit function and, consequently, the descent lemma; and \(ii\) the contribution induced by the drift inμ\\mu, which can be converted to the drift inyythat has already been controlled in the previous step\.
- •Step 3\) Lyapunov Analysis and Telescoping:Finally, building upon the aforementioned results, we construct a dynamic Lyapunov function to decouple the descent ofΦμt\\Phi\_\{\\mu\_\{t\}\}from the tracking errors\. By using a telescoping sum, we show that all error terms are bounded by the sum of a constant and a convergent series, thereby establishing the finite\-time convergence rate\.∎

Three remarks on[Theorem1](https://arxiv.org/html/2609.30501#Thmtheorem1)are in order:First, to our knowledge, this work is thefirstthat incorporates second\-order stationarity as a surrogate for LLNC\-BLO and propose an algorithm with a finite\-time convergence rate of𝒪⁡\(T−25\)\\mathcal\{O\}\\big\(T^\{\-\\frac\{2\}\{5\}\}\\big\)with lower\-level SOSP guarantee\. While existing LLNC\-BLO methods\([Shen and Chen, 2023](https://arxiv.org/html/2609.30501#bib.bib6);[Xiao et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib5);[Liu et al\., 2024](https://arxiv.org/html/2609.30501#bib.bib8);[Ma et al\., 2026](https://arxiv.org/html/2609.30501#bib.bib7)\)also provided finite\-time convergence analysis, a direct comparison with them is difficult due to the fact that most of these works assume the PL condition, which is not needed in this work\.Second, there is a trade\-off in choosingσt=σ0​\(t\+1\)−p\\sigma\_\{t\}=\\sigma\_\{0\}\(t\+1\)^\{\-p\}: a largerpp\-value yields faster convergence rate𝒪⁡\(T−2​p\)\\mathcal\{O\}\(T^\{\-2p\}\)in[Theorem1](https://arxiv.org/html/2609.30501#Thmtheorem1)\. However, the conditionq≥3​pq\\geq 3pimplies a small learning rateαt=α0​\(t\+1\)−q\\alpha\_\{t\}=\\alpha\_\{0\}\(t\+1\)^\{\-q\}\. Also, the smoothness coefficient ofΦμt\\Phi\_\{\\mu\_\{t\}\}scales asLt=Θ⁡\(σt−3\)L\_\{t\}=\\Theta\(\\sigma\_\{t\}^\{\-3\}\), implying thatαt=Θ⁡\(Lt−1\)=Θ⁡\(\(t\+1\)−3​p\)\\alpha\_\{t\}=\\Theta\(L\_\{t\}^\{\-1\}\)=\\Theta\(\(t\+1\)^\{\-3p\}\)whenq=3​pq=3pis required for a fast convergence, which in turn necessitates a relatively smallpp\. To balance these two directions, we choose\(p,q\)=\(15,35\)\(p,q\)=\(\\frac\{1\}\{5\},\\frac\{3\}\{5\}\)to achieve the most efficient convergence rate𝒪⁡\(T−25\)\\mathcal\{O\}\\big\(T^\{\-\\frac\{2\}\{5\}\}\\big\)\.Third, instead of using a fixed number of inner\-loop iterationsKK,𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~gradually increasesKtK\_\{t\}over time, leading to atwo\-timescalealgorithmic design\. Specifically, we introduce aμ\\mu\-augmentation to allow a well\-defined hypergradient in LLNC\-BLO\. This term introduces an error that can be controlled by gradually letting\{μt\}→0\\\{\\mu\_\{t\}\\\}\\to 0\. Hence,KtK\_\{t\}needs to be increasing rather than fixed to decrease the inner\-loop errorϵt\\epsilon\_\{t\}and thusμt\\mu\_\{t\}, leading to this two\-timescale design\.

## 6Experimental Results

\(a\)Loss vs Iteration\.\(b\)Loss vs Running time\.
Figure 2:Baseline comparison\.In this section, we will validate the efficacy of our𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~method by using a data curation task for LLM finetuning\. Specifically, we first curate a high quality dataset from multiple datasets of unknown qualities, which is then used to fine\-tune an LLM to mitigate toxicity, reduce verbosity, and improve coherence\. This data curation task can be formulated as an LLNC\-BLO problem\([Shen et al\., 2024a](https://arxiv.org/html/2609.30501#bib.bib17);[Pan et al\., 2025](https://arxiv.org/html/2609.30501#bib.bib51)\), where the lower level aims to determine the mixing proportion of each dataset, and the upper level further fine\-tunes the model as a validation process:

minx,y∑i=1n0ℒ\(ry⁡\(x\)\(pi\),ri\),s\.t\.y\(x\)∈arg​miny∑j=1𝒟SoftMaxx\(j\)∑i=1njℒ\(ry\(pi\),ri\),\\displaystyle\\min\_\{x,y\}\\sum\\nolimits\_\{i=1\}^\{n\_\{0\}\}\\mathcal\{L\}\\big\(r\_\{y\(x\)\}\(p\_\{i\}\),r\_\{i\}\\big\),\\,\\,\\,\\,\\,\\,\\text\{s\.t\. \}y\(x\)\\in\\argmin\_\{y\}\\sum\\nolimits\_\{j=1\}^\{\\mathcal\{D\}\}\\text\{SoftMax\}\_\{x\}\(j\)\\sum\\nolimits\_\{i=1\}^\{n\_\{j\}\}\\mathcal\{L\}\\big\(r\_\{y\}\(p\_\{i\}\),r\_\{i\}\\big\),wherexxis the weight vector for training datasets,yyrepresents the LLM parameters,\(p,r\)\(p,r\)denotes a prompt\-response pair,ℒ\\mathcal\{L\}is the loss,SoftMaxx​\(j\)=exp⁡\(xj\)/∑j′exp⁡\(xj′\)\\text\{SoftMax\}\_\{x\}\(j\)=\\exp\(x\_\{j\}\)/\\sum\_\{j^\{\\prime\}\}\\exp\(x\_\{j^\{\\prime\}\}\), index00stands for validation set, and1,…,𝒟1,\\dotsc,\\mathcal\{D\}are training indices\. Clearly, the lower\-level problem is nonconvex\. We conduct experiments on the HelpSteer\([Wang et al\., 2024](https://arxiv.org/html/2609.30501#bib.bib52)\)dataset, which incorporates data of varying quality\. We employ Llama\-3\.2\-3B\-Instruct\([Meta, 2024](https://arxiv.org/html/2609.30501#bib.bib53)\)as the base model\. More implementation details are relegated to Appendix[A](https://arxiv.org/html/2609.30501#A1)due to space limitation\.

1\) Baseline Comparison:We compare our𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~method against state\-of\-the\-art LLNC\-BLO baselines: PBGD\([Shen and Chen, 2023](https://arxiv.org/html/2609.30501#bib.bib6)\), GALET\([Xiao et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib5)\), MEHA\([Liu et al\., 2024](https://arxiv.org/html/2609.30501#bib.bib8)\), and SUN\-DSBO\-SE\([Ma et al\., 2026](https://arxiv.org/html/2609.30501#bib.bib7)\)\.[Figure2](https://arxiv.org/html/2609.30501#S6.F2)illustrates the upper\-level loss along with the standard error bars over55trials, which shows that PBGD and GALET fail to converge on this data curation task\. As detailed in Appendix[A](https://arxiv.org/html/2609.30501#A1), PBGD performs well at the lower level\. However, its oversimplified FOSP\-based surrogate could not avoid being trapped at undesirable saddle points at the lower level, leading to weak performance at the upper level\. In contrast, MEHA, SUN\-DSBO\-SE, and𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~converge to much better solutions at upper level\. Although the theoretical convergence rates of these methods are not directly comparable due to different metrics,𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~outperforms all baselines in terms of wall\-clock running time, demonstrating its efficiency\.

\(a\)Lower\-level loss withKK\.\(b\)Upper\-level loss withKK\.\(c\)Lower\-level loss withμ\\mu\.\(d\)Upper\-level loss withμ\\mu\.
Figure 3:Hyperparameter investigation\.2\) Hyper\-parameter Experimentation and Ablation Study:In this experiment, we study how the selections of hyperparametersKKandμ\\muimpact the performance of𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}, as shown in Fig\.[3](https://arxiv.org/html/2609.30501#S6.F3)\. For simplicity, we fixKKandμ\\mufor each experiment\. As shown in[Figures3\(a\)](https://arxiv.org/html/2609.30501#S6.F3.sf1)and[3\(b\)](https://arxiv.org/html/2609.30501#S6.F3.sf2), increasing the inner\-loop PGD iterations,KK, yields a significant improvement in the upper\-level loss\. This aligns with our theoretical insights: a smallKKrestricts PGD’s ability to probe and escape saddle points\. Consequently, the lower\-level problem stagnates at a suboptimal position, which in turn leads to unsatisfactory upper\-level performance\. In contrast, whenKKis sufficiently large,𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~reliably finds a lower\-level SOSP, yielding substantial overall performance improvements\.[Figures3\(c\)](https://arxiv.org/html/2609.30501#S6.F3.sf3)and[3\(d\)](https://arxiv.org/html/2609.30501#S6.F3.sf4)show the influence of the augmentation parameterμ\\mu, both of which show that the largerμ\\mufacilitates a slightly lower loss value\. Also,[Figure3\(d\)](https://arxiv.org/html/2609.30501#S6.F3.sf4)shows that the trajectory fluctuates dramatically whenμ\\muis insufficient to restore the Hessian positive definiteness\. This highlights the important tradeoff and provides a guidance in selectingμ\\mu\.

\(a\)Lower\-level loss\.\(b\)Upper\-level loss\.
Figure 4:Ablation Study\.We also conduct the following ablation study by replacing the PGD method in Algorithm[2](https://arxiv.org/html/2609.30501#algorithm2)with the vanilla gradient descent method, keeping all other components of𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~unchanged\. As shown in[Figure4](https://arxiv.org/html/2609.30501#S6.F4), without saddle points escaping,𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~is easily trapped in solutions seemingly better at the lower level but are suboptimal at the upper level, highlighting the importance of our SOSP\-based lower\-level surrogate and the efficacy of our proposed𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~\. Due to space limitation, we provide further numerical details and a meta\-learning experiment in Appendix[A](https://arxiv.org/html/2609.30501#A1)\.

## 7Conclusion

In this paper, we investigated bilevel optimization with non\-convex lower levels\. We showed that existing first\-order stationarity\-based surrogates often fail to escape lower\-level saddle points\. To address this challenge, we proposed a second\-order stationarity\-based surrogate, based on which we developed a new algorithm called𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~and established its finite\-time convergence rate\. We conducted experiments on dataset curation tasks for LLM finetuning to validate our𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~algorithm\. We note that the focus of this work is on deterministic LLNC\-BLO problems\. Future directions include extending our framework into stochastic LLNC\-BLO problems\.

## References

- N\. Agarwal, Z\. Allen\-Zhu, B\. Bullins, E\. Hazan, and T\. MaFinding approximate local minima faster than gradient descent\.InProceedings of the 49th annual ACM SIGACT symposium on theory of computing,pp\. 1195–1199\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p3.1)\.
- Allen\-Zhu and Li \(2018\)Z\. Allen\-Zhu and Y\. LiNeon2: finding local minima via first\-order oracles\.Advances in Neural Information Processing Systems31\.Cited by:[Appendix D](https://arxiv.org/html/2609.30501#A4.p3.1),[§2](https://arxiv.org/html/2609.30501#S2.p3.1)\.
- Arbel and Mairal \(2021\)M\. Arbel and J\. MairalAmortized implicit differentiation for stochastic bilevel optimization\.arXiv preprint arXiv:2111\.14580\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p2.1)\.
- Bhojanapalliet al\.\(2016\)S\. Bhojanapalli, B\. Neyshabur, and N\. SrebroGlobal optimality of local search for low rank matrix recovery\.Advances in Neural Information Processing Systems29\.Cited by:[§3](https://arxiv.org/html/2609.30501#S3.p5.1)\.
- Bracken and McGill \(1973\)J\. Bracken and J\. T\. McGillMathematical programs with optimization problems in the constraints\.Operations research21\(1\),pp\. 37–44\.Cited by:[§1](https://arxiv.org/html/2609.30501#S1.p1.2),[§2](https://arxiv.org/html/2609.30501#S2.p2.1)\.
- Caoet al\.\(2023\)J\. Cao, R\. Jiang, N\. Abolfazli, E\. Yazdandoost Hamedani, and A\. MokhtariProjection\-free methods for stochastic simple bilevel optimization with convex lower\-level problem\.Advances in Neural Information Processing Systems36,pp\. 6105–6131\.Cited by:[§1](https://arxiv.org/html/2609.30501#S1.p1.3),[§2](https://arxiv.org/html/2609.30501#S2.p2.1)\.
- Castinet al\.\(2023\)V\. Castin, P\. Ablin, and G\. PeyréHow smooth is attention?\.arXiv preprint arXiv:2312\.14820\.Cited by:[§3](https://arxiv.org/html/2609.30501#S3.p2.1)\.
- Chenet al\.\(2025\)L\. Chen, Y\. Ma, and J\. ZhangNear\-optimal nonconvex\-strongly\-convex bilevel optimization with fully first\-order oracles\.Journal of Machine Learning Research26\(109\),pp\. 1–56\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p3.1)\.
- Chenet al\.\(2023\)L\. Chen, J\. Xu, and J\. ZhangBilevel optimization without lower\-level strong convexity from the hyper\-objective perspective\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p2.1)\.
- Chenet al\.\(2024\)L\. Chen, J\. Xu, and J\. ZhangOn finding small hyper\-gradients in bilevel optimization: hardness results and improved analysis\.InThe Thirty Seventh Annual Conference on Learning Theory,pp\. 947–980\.Cited by:[§1](https://arxiv.org/html/2609.30501#S1.p2.1),[§2](https://arxiv.org/html/2609.30501#S2.p2.1)\.
- Dagréouet al\.\(2022\)M\. Dagréou, P\. Ablin, S\. Vaiter, and T\. MoreauA framework for bilevel optimization that enables stochastic and global variance reduction algorithms\.Advances in Neural Information Processing Systems35,pp\. 26698–26710\.Cited by:[§1](https://arxiv.org/html/2609.30501#S1.p1.3),[§2](https://arxiv.org/html/2609.30501#S2.p2.1)\.
- Dauphinet al\.\(2014\)Y\. N\. Dauphin, R\. Pascanu, C\. Gulcehre, K\. Cho, S\. Ganguli, and Y\. BengioIdentifying and attacking the saddle point problem in high\-dimensional non\-convex optimization\.Advances in neural information processing systems27\.Cited by:[Appendix D](https://arxiv.org/html/2609.30501#A4.p3.1),[§2](https://arxiv.org/html/2609.30501#S2.p3.1)\.
- Fanget al\.\(2018\)C\. Fang, C\. J\. Li, Z\. Lin, and T\. ZhangSpider: near\-optimal non\-convex optimization via stochastic path\-integrated differential estimator\.Advances in neural information processing systems31\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p3.1)\.
- Franceschiet al\.\(2018\)L\. Franceschi, P\. Frasconi, S\. Salzo, R\. Grazzi, and M\. PontilBilevel programming for hyperparameter optimization and meta\-learning\.InInternational conference on machine learning,pp\. 1568–1577\.Cited by:[§A\.1](https://arxiv.org/html/2609.30501#A1.SS1.p1.1),[§1](https://arxiv.org/html/2609.30501#S1.p1.2),[§2](https://arxiv.org/html/2609.30501#S2.p2.1)\.
- Geet al\.\(2015\)R\. Ge, F\. Huang, C\. Jin, and Y\. YuanEscaping from saddle points—online stochastic gradient for tensor decomposition\.InConference on learning theory,pp\. 797–842\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p3.1),[§3](https://arxiv.org/html/2609.30501#S3.p5.1)\.
- Geet al\.\(2016\)R\. Ge, J\. D\. Lee, and T\. MaMatrix completion has no spurious local minimum\.Advances in neural information processing systems29\.Cited by:[§3](https://arxiv.org/html/2609.30501#S3.p5.1)\.
- Ghadimi and Wang \(2018\)S\. Ghadimi and M\. WangApproximation methods for bilevel programming\.arXiv preprint arXiv:1802\.02246\.Cited by:[§1](https://arxiv.org/html/2609.30501#S1.p1.3),[§2](https://arxiv.org/html/2609.30501#S2.p2.1),[§3](https://arxiv.org/html/2609.30501#S3.p2.1),[§4](https://arxiv.org/html/2609.30501#S4.p2.2)\.
- Grazziet al\.\(2020\)R\. Grazzi, L\. Franceschi, M\. Pontil, and S\. SalzoOn the iteration complexity of hypergradient computation\.InInternational Conference on Machine Learning,pp\. 3748–3758\.Cited by:[Appendix B](https://arxiv.org/html/2609.30501#A2.p6.1.1.1),[§4](https://arxiv.org/html/2609.30501#S4.p2.2),[§4](https://arxiv.org/html/2609.30501#S4.p9.1)\.
- Honget al\.\(2023\)M\. Hong, H\. Wai, Z\. Wang, and Z\. YangA two\-timescale stochastic algorithm framework for bilevel optimization: complexity analysis and application to actor\-critic\.SIAM Journal on Optimization33\(1\),pp\. 147–180\.Cited by:[§1](https://arxiv.org/html/2609.30501#S1.p1.2)\.
- Huet al\.\(2023\)Y\. Hu, J\. Wang, Y\. Xie, A\. Krause, and D\. KuhnContextual stochastic bilevel optimization\.Advances in Neural Information Processing Systems36,pp\. 78412–78434\.Cited by:[§A\.1](https://arxiv.org/html/2609.30501#A1.SS1.p1.1)\.
- Huanget al\.\(2025\)M\. Huang, X\. Chen, K\. Ji, S\. Ma, and L\. LaiEfficiently escaping saddle points in bilevel optimization\.Journal of machine learning research26\(1\),pp\. 1–61\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p3.1),[§4](https://arxiv.org/html/2609.30501#S4.p2.2)\.
- Jiet al\.\(2021\)K\. Ji, J\. Yang, and Y\. LiangBilevel optimization: convergence analysis and enhanced design\.InInternational conference on machine learning,pp\. 4882–4892\.Cited by:[§A\.1](https://arxiv.org/html/2609.30501#A1.SS1.p1.1),[§1](https://arxiv.org/html/2609.30501#S1.p1.2),[§1](https://arxiv.org/html/2609.30501#S1.p1.3),[§2](https://arxiv.org/html/2609.30501#S2.p2.1),[§3](https://arxiv.org/html/2609.30501#S3.p2.1),[§4](https://arxiv.org/html/2609.30501#S4.p2.2),[§4](https://arxiv.org/html/2609.30501#S4.p9.1)\.
- Jianget al\.\(2023\)R\. Jiang, N\. Abolfazli, A\. Mokhtari, and E\. Y\. HamedaniA conditional gradient\-based method for simple bilevel optimization with convex lower\-level problem\.InInternational Conference on Artificial Intelligence and Statistics,pp\. 10305–10323\.Cited by:[§1](https://arxiv.org/html/2609.30501#S1.p1.3),[§2](https://arxiv.org/html/2609.30501#S2.p2.1)\.
- Jianget al\.\(2025a\)X\. Jiang, J\. Li, J\. Bi, M\. Hong, and S\. ZhangA correspondence\-driven approach for bilevel decision\-making with nonconvex lower\-level problems\.arXiv preprint arXiv:2509\.01148\.Cited by:[§1](https://arxiv.org/html/2609.30501#S1.p2.1),[§2](https://arxiv.org/html/2609.30501#S2.p2.1)\.
- Jianget al\.\(2025b\)X\. Jiang, I\. Tsaknakis, P\. Khanduri, and M\. HongA discretization approach for bilevel optimization with low\-dimensional and non\-convex lower\-level\.arXiv preprint arXiv:2505\.10830\.Cited by:[§1](https://arxiv.org/html/2609.30501#S1.p2.1),[§2](https://arxiv.org/html/2609.30501#S2.p2.1)\.
- Jinet al\.\(2017\)C\. Jin, R\. Ge, P\. Netrapalli, S\. M\. Kakade, and M\. I\. JordanHow to escape saddle points efficiently\.InInternational conference on machine learning,pp\. 1724–1732\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p3.1),[§3](https://arxiv.org/html/2609.30501#S3.p4.1),[§3](https://arxiv.org/html/2609.30501#S3.p5.1),[§4](https://arxiv.org/html/2609.30501#S4.p8.1),[§5](https://arxiv.org/html/2609.30501#S5.p1.1)\.
- Jinet al\.\(2021\)C\. Jin, P\. Netrapalli, R\. Ge, S\. M\. Kakade, and M\. I\. JordanOn nonconvex optimization for machine learning: gradients, stochasticity, and saddle points\.Journal of the ACM \(JACM\)68\(2\),pp\. 1–29\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p3.1),[§5](https://arxiv.org/html/2609.30501#S5.p2.1)\.
- Jinet al\.\(2018\)C\. Jin, P\. Netrapalli, and M\. I\. JordanAccelerated gradient descent escapes saddle points faster than gradient descent\.InConference on learning theory,pp\. 1042–1085\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p3.1),[§3](https://arxiv.org/html/2609.30501#S3.p4.1),[§5](https://arxiv.org/html/2609.30501#S5.p2.1)\.
- Kudoet al\.\(2026\)M\. Kudo, T\. Tanabe, A\. Wachi, and Y\. AkimotoSample\-efficient hypergradient estimation for decentralized bi\-level reinforcement learning\.arXiv preprint arXiv:2603\.14867\.Cited by:[§1](https://arxiv.org/html/2609.30501#S1.p1.2)\.
- Kwonet al\.\(2023\)J\. Kwon, D\. Kwon, S\. Wright, and R\. NowakOn penalty methods for nonconvex bilevel optimization and first\-order stochastic approximation\.arXiv preprint arXiv:2309\.01753\.Cited by:[§1](https://arxiv.org/html/2609.30501#S1.p2.1),[§2](https://arxiv.org/html/2609.30501#S2.p2.1)\.
- Liet al\.\(2024\)J\. Li, S\. Zeng, H\. Wai, C\. Li, A\. Garcia, and M\. HongGetting more juice out of the sft data: reward learning from human demonstration improves sft for llm alignment\.Advances in Neural Information Processing Systems37,pp\. 124292–124318\.Cited by:[§3](https://arxiv.org/html/2609.30501#S3.p2.1)\.
- Liuet al\.\(2018\)M\. Liu, Z\. Li, X\. Wang, J\. Yi, and T\. YangAdaptive negative curvature descent with applications in non\-convex optimization\.Advances in Neural Information Processing Systems31\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p3.1)\.
- Liuet al\.\(2021\)R\. Liu, J\. Gao, J\. Zhang, D\. Meng, and Z\. LinInvestigating bi\-level optimization for learning and vision from a unified perspective: a survey and beyond\.IEEE Transactions on Pattern Analysis and Machine Intelligence44\(12\),pp\. 10045–10067\.Cited by:[§1](https://arxiv.org/html/2609.30501#S1.p1.2)\.
- Liuet al\.\(2023\)R\. Liu, Y\. Liu, W\. Yao, S\. Zeng, and J\. ZhangAveraged method of multipliers for bi\-level optimization without lower\-level strong convexity\.InInternational Conference on Machine Learning,pp\. 21839–21866\.Cited by:[§1](https://arxiv.org/html/2609.30501#S1.p1.3),[§2](https://arxiv.org/html/2609.30501#S2.p2.1)\.
- Liuet al\.\(2024\)R\. Liu, Z\. Liu, W\. Yao, S\. Zeng, and J\. ZhangMoreau envelope for nonconvex bi\-level optimization: a single\-loop and hessian\-free solution strategy\.arXiv preprint arXiv:2405\.09927\.Cited by:[Appendix C](https://arxiv.org/html/2609.30501#A3.p1.2),[Figure 1](https://arxiv.org/html/2609.30501#S1.F1),[Figure 1](https://arxiv.org/html/2609.30501#S1.F1.7),[§1](https://arxiv.org/html/2609.30501#S1.p2.1),[§2](https://arxiv.org/html/2609.30501#S2.p2.1),[§3](https://arxiv.org/html/2609.30501#S3.p6.1),[§5](https://arxiv.org/html/2609.30501#S5.p4.1),[§6](https://arxiv.org/html/2609.30501#S6.p2.1)\.
- Maet al\.\(2026\)Y\. Ma, X\. Wang, W\. Yao, and J\. ZhangSUN\-dsbo: a structured unified framework for nonconvex decentralized stochastic bilevel optimization\.arXiv preprint arXiv:2601\.22682\.Cited by:[Appendix C](https://arxiv.org/html/2609.30501#A3.p1.2),[Figure 1](https://arxiv.org/html/2609.30501#S1.F1),[Figure 1](https://arxiv.org/html/2609.30501#S1.F1.7),[Table 1](https://arxiv.org/html/2609.30501#S1.T1),[Table 1](https://arxiv.org/html/2609.30501#S1.T1.4),[§1](https://arxiv.org/html/2609.30501#S1.p2.1),[§2](https://arxiv.org/html/2609.30501#S2.p2.1),[§3](https://arxiv.org/html/2609.30501#S3.p6.1),[§5](https://arxiv.org/html/2609.30501#S5.p4.1),[§6](https://arxiv.org/html/2609.30501#S6.p2.1)\.
- Malladiet al\.\(2023\)S\. Malladi, T\. Gao, E\. Nichani, A\. Damian, J\. D\. Lee, D\. Chen, and S\. AroraFine\-tuning language models with just forward passes\.Advances in Neural Information Processing Systems36,pp\. 53038–53075\.Cited by:[§3](https://arxiv.org/html/2609.30501#S3.p2.1)\.
- Meta \(2024\)MetaMeta\-llama/llama\-3\.2\-3b\-instruct\.External Links:[Link](https://huggingface.co/meta-llama/Llama-3.2-3B-Instruct)Cited by:[§A\.2](https://arxiv.org/html/2609.30501#A1.SS2.p1.1),[§6](https://arxiv.org/html/2609.30501#S6.p1.2)\.
- Murtyet al\.\(1987\)K\. G\. Murty S\. N\. Kabadiet al\.Some np\-complete problems in quadratic and nonlinear programming\.Mathematical programming39\(2\),pp\. 117–129\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p3.1)\.
- Nesterov and Polyak \(2006\)Y\. Nesterov and B\. T\. PolyakCubic regularization of newton method and its global performance\.Mathematical programming108\(1\),pp\. 177–205\.Cited by:[§3](https://arxiv.org/html/2609.30501#S3.p4.1)\.
- Panet al\.\(2025\)R\. Pan, D\. Zhang, H\. Zhang, X\. Pan, M\. Xu, J\. Zhang, R\. Pi, X\. Wang, and T\. ZhangScalebio: scalable bilevel optimization for llm data reweighting\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 31959–31982\.Cited by:[§6](https://arxiv.org/html/2609.30501#S6.p1.1)\.
- Qinet al\.\(2025\)Z\. Qin, Z\. Liu, S\. Lu, Y\. Liang, and J\. LiuDUET: decentralized bilevel optimization without lower\-level strong convexity\.InThe Thirteenth International Conference on Learning Representations,Cited by:[§A\.1](https://arxiv.org/html/2609.30501#A1.SS1.p1.1)\.
- Renet al\.\(2023\)Z\. Ren, Y\. Tang, and N\. LiEscaping saddle points in zeroth\-order optimization: the power of two\-point estimators\.InInternational Conference on Machine Learning,pp\. 28914–28975\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p3.1)\.
- Shabanet al\.\(2019\)A\. Shaban, C\. Cheng, N\. Hatch, and B\. BootsTruncated back\-propagation for bilevel optimization\.InThe 22nd international conference on artificial intelligence and statistics,pp\. 1723–1732\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p2.1)\.
- Shenet al\.\(2024a\)H\. Shen, P\. Chen, P\. Das, and T\. ChenSeal: safety\-enhanced aligned llm fine\-tuning via bilevel data selection\.arXiv preprint arXiv:2410\.07471\.Cited by:[§1](https://arxiv.org/html/2609.30501#S1.p1.2),[§6](https://arxiv.org/html/2609.30501#S6.p1.1)\.
- Shen and Chen \(2023\)H\. Shen and T\. ChenOn penalty\-based bilevel gradient descent method\.InInternational conference on machine learning,pp\. 30992–31015\.Cited by:[Appendix C](https://arxiv.org/html/2609.30501#A3.p1.2),[Figure 1](https://arxiv.org/html/2609.30501#S1.F1),[Figure 1](https://arxiv.org/html/2609.30501#S1.F1.7),[§1](https://arxiv.org/html/2609.30501#S1.p2.1),[§2](https://arxiv.org/html/2609.30501#S2.p2.1),[§3](https://arxiv.org/html/2609.30501#S3.p6.1),[§5](https://arxiv.org/html/2609.30501#S5.p4.1),[§6](https://arxiv.org/html/2609.30501#S6.p2.1)\.
- Shenet al\.\(2024b\)H\. Shen, S\. Paternain, G\. Liu, R\. Kompella, and T\. ChenA method for bilevel optimization with convex lower\-level problem\.InICASSP 2024\-2024 IEEE International Conference on Acoustics, Speech and Signal Processing \(ICASSP\),pp\. 9426–9430\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p2.1)\.
- Sunet al\.\(2018\)J\. Sun, Q\. Qu, and J\. WrightA geometric analysis of phase retrieval\.Foundations of Computational Mathematics18\(5\),pp\. 1131–1198\.Cited by:[§3](https://arxiv.org/html/2609.30501#S3.p5.1)\.
- Vlatakis\-Gkaragkouniset al\.\(2019\)E\. Vlatakis\-Gkaragkounis, L\. Flokas, and G\. PiliourasEfficiently avoiding saddle points with zero order methods: no gradients required\.Advances in neural information processing systems32\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p3.1)\.
- Wanget al\.\(2024\)Z\. Wang, Y\. Dong, J\. Zeng, V\. Adams, M\. N\. Sreedhar, D\. Egert, O\. Delalleau, J\. Scowcroft, N\. Kant, A\. Swope,et al\.Helpsteer: multi\-attribute helpfulness dataset for steerlm\.InProceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies \(Volume 1: Long Papers\),pp\. 3371–3384\.Cited by:[§A\.2](https://arxiv.org/html/2609.30501#A1.SS2.p1.1),[§6](https://arxiv.org/html/2609.30501#S6.p1.2)\.
- Xiaoet al\.\(2023\)Q\. Xiao, S\. Lu, and T\. ChenA generalized alternating method for bilevel learning under the polyak\-\{\\\{\\\\backslashl\}\\\}ojasiewicz condition\.arXiv preprint arXiv:2306\.02422\.Cited by:[Appendix C](https://arxiv.org/html/2609.30501#A3.p1.2),[Figure 1](https://arxiv.org/html/2609.30501#S1.F1),[Figure 1](https://arxiv.org/html/2609.30501#S1.F1.7),[§1](https://arxiv.org/html/2609.30501#S1.p2.1),[§2](https://arxiv.org/html/2609.30501#S2.p2.1),[§3](https://arxiv.org/html/2609.30501#S3.p2.1),[§3](https://arxiv.org/html/2609.30501#S3.p6.1),[§5](https://arxiv.org/html/2609.30501#S5.p4.1),[§6](https://arxiv.org/html/2609.30501#S6.p2.1)\.
- Yanget al\.\(2021\)J\. Yang, K\. Ji, and Y\. LiangProvably faster algorithms for bilevel optimization\.Advances in Neural Information Processing Systems34,pp\. 13670–13682\.Cited by:[§1](https://arxiv.org/html/2609.30501#S1.p1.3),[§2](https://arxiv.org/html/2609.30501#S2.p2.1),[§3](https://arxiv.org/html/2609.30501#S3.p2.1)\.
- Ye and Zhu \(1995\)J\. J\. Ye and D\. ZhuOptimality conditions for bilevel programming problems\.Optimization33\(1\),pp\. 9–27\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p2.1)\.
- Zhang and Li \(2021\)C\. Zhang and T\. LiEscape saddle points by a simple gradient\-descent based algorithm\.Advances in Neural Information Processing Systems34,pp\. 8545–8556\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p3.1),[§3](https://arxiv.org/html/2609.30501#S3.p4.1),[§5](https://arxiv.org/html/2609.30501#S5.p2.1)\.
- Zhang and Gu \(2022\)H\. Zhang and B\. GuFaster gradient\-free methods for escaping saddle points\.InThe Eleventh International Conference on Learning Representations,Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p3.1)\.
- Zhanget al\.\(2022a\)H\. Zhang, H\. Xiong, and B\. GuZeroth\-order negative curvature finding: escaping saddle points without gradients\.Advances in Neural Information Processing Systems35,pp\. 38332–38344\.Cited by:[§2](https://arxiv.org/html/2609.30501#S2.p3.1)\.
- Zhanget al\.\(2024\)Y\. Zhang, P\. Khanduri, I\. Tsaknakis, Y\. Yao, M\. Hong, and S\. LiuAn introduction to bilevel optimization: foundations and applications in signal processing and machine learning\.IEEE Signal Processing Magazine41\(1\),pp\. 38–59\.Cited by:[§1](https://arxiv.org/html/2609.30501#S1.p1.2)\.
- Zhanget al\.\(2022b\)Y\. Zhang, G\. Zhang, P\. Khanduri, M\. Hong, S\. Chang, and S\. LiuRevisiting and advancing fast adversarial training through the lens of bi\-level optimization\.InInternational Conference on Machine Learning,pp\. 26693–26712\.Cited by:[§1](https://arxiv.org/html/2609.30501#S1.p1.2)\.

## Appendix

## Appendix AAdditional Numerical Results

### A\.1Meta\-Learning Experiments

Meta\-learning seeks to improve model generalization and is naturally formulated as a BLO problem\([Franceschi et al\., 2018](https://arxiv.org/html/2609.30501#bib.bib15);[Ji et al\., 2021](https://arxiv.org/html/2609.30501#bib.bib9);[Hu et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib58);[Qin et al\., 2025](https://arxiv.org/html/2609.30501#bib.bib54)\)\. Specifically, the lower level implements task\-specific adaptation on the training data, while the upper level enhances the representation utility to ensure generalization ability of the model\.

We train a multi\-layer perceptron \(MLP, corresponding toxx\) with depth22, width512512and ReLU activation, along with an additional256256\-dimensional linear layer \(corresponding toyy\) on MNIST dataset\. In particular, we construct 5 MNIST heterogeneous training datasets, each containing80%80\\%of a selected pair of digits \(e\.g\.,\(0,1\)\(0,1\)\) and20%20\\%of other digit pairs\. The validation set are constructed from the MNIST test split, using the same ratio of five digit\-pair tasks\. The formal formulation is given as follows:

min⁡∑s∈𝒟0x,y⁡ℒ⁡\(\(x∘y\)​\(s\),l⁡\(s\)\)\\displaystyle\\min\_\{x,y\}\\sum\_\{s\\in\\mathcal\{D\}\_\{0\}\}\\mathcal\{L\}\\big\(\(x\\circ y\)\(s\),l\(s\)\\big\)subject toy∈𝒮\(x\):=arg​miny∑j=15∑s∈𝒟jℒ\(\(x∘y\)\(s\),l\(s\)\),\\displaystyle y\\in\\mathcal\{S\}\(x\):=\\argmin\_\{y\}\\sum\_\{j=1\}^\{5\}\\sum\_\{s\\in\\mathcal\{D\}\_\{j\}\}\\mathcal\{L\}\\big\(\(x\\circ y\)\(s\),l\(s\)\\big\),wheressdenotes the digit sample,l⁡\(s\)l\(s\)denotes its label,x∘y⁡\(s\)x\\circ y\(s\)denotes the model output,ℒ\\mathcal\{L\}denotes the cross\-entropy loss function, and𝒟j,j∈\{0,…,5\}\\mathcal\{D\}\_\{j\},j\\in\\\{0,\\dotsc,5\\\}are the datasets\. Since the loss function is convex, andyycorresponds to a linear layer, the lower\-level problem is convex \(but not strongly convex\) w\.r\.t\.yy\. We consider this meta\-learning task to demonstrate the capability of𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~in the LLGC setting\.

As shown in[Figure5](https://arxiv.org/html/2609.30501#A1.F5), all baselines and our𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~converge at both upper and lower levels\. All baseline methods succeed in this meta\-learning task because the FOSP\-based relaxed surrogate aligns exactly with the original BLO problem in this LLGC environment, preventing them from getting trapped at saddle points \(In fact, no saddle points exist due to the convexity\)\.𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}, on the other hand, still achieves the fastest convergence, demonstrating both its validity in the LLGC setting and its consistent efficiency\.

\(a\)Lower\-level loss\.\(b\)Upper\-level loss\.
Figure 5:Baseline comparison in meta\-learning task\.
### A\.2Implementation Details and Additional Results on Data Curation Task

In the data curation task, we fine\-tune an LLM, Llama\-3\.2\-3B\-Instruct\([Meta, 2024](https://arxiv.org/html/2609.30501#bib.bib53)\)model, on the HelpSteer\([Wang et al\., 2024](https://arxiv.org/html/2609.30501#bib.bib52)\)dataset, which naturally contains prompts with responses of varying quality\. During training, corresponding to the lower\-level problem in our formulation, the LLM learns to distinguish between two datasets and is expected to assign higher weights to the one with higher response quality\. During validation, corresponding to the upper\-level problem, the performance of the fine\-tuned LLM is evaluated on high\-quality prompt\-response data\. Specifically, the datasets are constructed as follows: for each response data in HelpSteer, we compute its average score, and include the corresponding prompt\-response pair in the high\-quality set ifs≥2\.5s\\geq 2\.5, or in the low\-quality set ifs≤2s\\leq 2\(the only validation set merely include high\-quality validation data\)\. Llama\-3\.2\-3B\-Instruct is trained using LoRA technique withrank=8\\text\{rank\}=8, and all data curation experiments are conducted on a cluster of 2 NVIDIA H200 GPUs \(approximately 140GB each\) using PyTorch’s DistributedDataParallel\.

The hyperparameter selection is detailed as follows\. The batch size is set to3232\. For a fair comparison, we fix the total number of iterations toT=20,000T=20,000, which implies: \(i\) for single\-loop methods, the algorithm runs for20,00020,000rounds; and \(ii\) for double\-loop methods, the product of inner\-loop steps and outer\-loop steps equals20,00020,000\. Additionally, we simplify our method by using fixed values forKK,NN, andμ\\muto ensure fairness in the comparison\. Accordingly, we uniformly select100100iterations to report\. The learning rates for all algorithms are set to10−510^\{\-5\}\. For𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}, we setT=100T=100,K=200K=200,μ=0\.1\\mu=0\.1\. We setΔK=10\\Delta\_\{K\}=10, and other PGD parameters are set to10−210^\{\-2\}as our default setup\. For these baselines, the detailed setups are specified as follows\. For MEHA, we examined additional learning rateη∈\{0\.1,2\.0\}\\eta\\in\\\{0\.1,2\.0\\\}and penalty coefficientc∈\{0\.1,1,2,5,10\}c\\in\\\{0\.1,1,2,5,10\\\}\. For SUN\-DSBO\-SE, we examined proximal parameterγ∈\{0\.01,0\.05,0\.1\}\\gamma\\in\\\{0\.01,0\.05,0\.1\\\}and penalty parameterμ0∈\{0\.01,0\.1,1,10\}\\mu\_\{0\}\\in\\\{0\.01,0\.1,1,10\\\}\. For PBGD, we examined the penalty coefficient in\{0\.1,1,10\}\\\{0\.1,1,10\\\}\. For GALET, we also tested larger inner\-loop step counts\(10,20\)\(10,20\), but these configurations resulted in numerical errors; we therefore used the best stable configuration with both inner\-loop counts set to55\. The reported baseline performances correspond to the best\-performing configurations among those tested rather than unfavorable or arbitrarily selected settings\. Each experiment is repeated55times, and the corresponding standard error bars are shown in all figures\. We also apply an exponential moving average \(EMA\) to enhance visibility\.

The lower\-level performances of all methods are shown in[Figure6](https://arxiv.org/html/2609.30501#A1.F6)\. As noted earlier, GALET finds some seemingly favorable solutions for the lower\-level problem \(Its loss values also decrease from around88, and the seemingly immediate convergence observed in the figure is due to the use of EMA\)\. Nevertheless, when considered alongside[Figure2](https://arxiv.org/html/2609.30501#S6.F2), it is clear that these solutions are actually suboptimal in general\. In stark contrast, MEHA, SUN\-DSBO\-SE, and our𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~not only converge during training, but also performs consistently well in the validation process\. Among them, our𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~is the most efficient method, achieving convergence in the shortest running time\.

\(a\)Loss vs Iteration\.\(b\)Loss vs Running time\.
Figure 6:Baseline \(lower\-level\) comparison\.

## Appendix BProof of Main Result

###### Theorem 2\(Formally restated[Theorem1](https://arxiv.org/html/2609.30501#Thmtheorem1)\)\.

By selecting parameters as follows:

σt=Θ⁡\(\(t\+1\)−p\),ϵt=σt4ρ,μt=ρ​ϵt\+σt,αt=Θ⁡\(\(t\+1\)−q\),βt=Θ⁡\(1ℓ\),\\displaystyle\\sigma\_\{t\}=\\Theta\\left\(\(t\+1\)^\{\-p\}\\right\),\\,\\,\\,\\,\\,\\,\\epsilon\_\{t\}=\\frac\{\\sigma\_\{t\}^\{4\}\}\{\\rho\},\\,\\,\\,\\,\\,\\,\\mu\_\{t\}=\\sqrt\{\\rho\\epsilon\_\{t\}\}\+\\sigma\_\{t\},\\,\\,\\,\\,\\,\\,\\alpha\_\{t\}=\\Theta\\left\(\(t\+1\)^\{\-q\}\\right\),\\,\\,\\,\\,\\,\\,\\beta\_\{t\}=\\Theta\\left\(\\frac\{1\}\{\\ell\}\\right\),Nt=Θ~​\(\(t\+1\)p2\),Kt=Θ~​\(\(t\+1\)8​p\),\\displaystyle N\_\{t\}=\\widetilde\{\\Theta\}\(\(t\+1\)^\{\\frac\{p\}\{2\}\}\),\\,\\,\\,\\,\\,\\,K\_\{t\}=\\widetilde\{\\Theta\}\(\(t\+1\)^\{8p\}\),δ′∈\(0,1T\),Δg,t≥g⁡\(xt,yt\)−infyg⁡\(xt,y\),χt=3​max​\{log⁡\(q​ℓ​Δg,tϵt2​δ′\),4\},\\displaystyle\\delta^\{\\prime\}\\in\(0,\\frac\{1\}\{T\}\),\\,\\,\\,\\,\\,\\,\\Delta\_\{g,t\}\\geq g\(x\_\{t\},y\_\{t\}\)\-\\inf\_\{y\}g\(x\_\{t\},y\),\\,\\,\\,\\,\\,\\,\\chi\_\{t\}=3\\max\\left\\\{\\log\\left\(\\frac\{q\\ell\\Delta\_\{g,t\}\}\{\\epsilon\_\{t\}^\{2\}\\delta^\{\\prime\}\}\\right\),4\\right\\\},rt=Θ⁡\(ϵtℓ​χt2\),ϱt=Θ⁡\(ϵtχt2\),ΔG,t=Θ⁡\(ϵt1\.5χt3​ρ0\.5\),ΔK,t=Θ⁡\(ℓ​χtρ0\.5​ϵt0\.5\),\\displaystyle r\_\{t\}=\\Theta\\left\(\\frac\{\\epsilon\_\{t\}\}\{\\ell\\chi\_\{t\}^\{2\}\}\\right\),\\,\\,\\,\\,\\,\\,\\varrho\_\{t\}=\\Theta\\left\(\\frac\{\\epsilon\_\{t\}\}\{\\chi\_\{t\}^\{2\}\}\\right\),\\,\\,\\,\\,\\,\\,\\Delta\_\{G,t\}=\\Theta\\left\(\\frac\{\\epsilon\_\{t\}^\{1\.5\}\}\{\\chi\_\{t\}^\{3\}\\rho^\{0\.5\}\}\\right\),\\,\\,\\,\\,\\,\\,\\Delta\_\{K,t\}=\\Theta\\left\(\\frac\{\\ell\\chi\_\{t\}\}\{\\rho^\{0\.5\}\\epsilon\_\{t\}^\{0\.5\}\}\\right\),for anyδ=T​δ′∈\(0,1\)\\delta=T\\delta^\{\\prime\}\\in\(0,1\),p∈\(0,13\)p\\in\(0,\\frac\{1\}\{3\}\),3​p≤q<13p\\leq q<1, the sequence\{xt,yt\}t\\\{x\_\{t\},y\_\{t\}\\\}\_\{t\}generated by[Algorithm1](https://arxiv.org/html/2609.30501#algorithm1)satisfies the following convergence guarantee w\.p\.1−δ1\-\\delta:

minT2≤t≤T⁡Π⁡\(xt,yt\)=𝒪⁡\(1T1−q\+1T2​p\+1T45\)\.\\displaystyle\\min\_\{\\frac\{T\}\{2\}\\leq t\\leq T\}\\Pi\(x\_\{t\},y\_\{t\}\)=\\mathcal\{O\}\\left\(\\frac\{1\}\{T^\{1\-q\}\}\+\\frac\{1\}\{T^\{2p\}\}\+\\frac\{1\}\{T^\{\\frac\{4\}\{5\}\}\}\\right\)\.When selectingp=15p=\\frac\{1\}\{5\}andq=35q=\\frac\{3\}\{5\}, we haveminT2≤t≤T⁡Π⁡\(xt,yt\)=𝒪⁡\(T−25\)\\min\_\{\\frac\{T\}\{2\}\\leq t\\leq T\}\\Pi\(x\_\{t\},y\_\{t\}\)=\\mathcal\{O\}\\left\(T^\{\-\\frac\{2\}\{5\}\}\\right\)\.

###### Proof\.

We prove this result with several sub\-steps\.

Part𝒜\\mathcal\{A\}\.We first control‖vμt\+1∗​\(xt\)−vμt∗​\(xt\)‖\\\|v\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\-v\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|\. To begin with, we define:

vμ∗​\(xt\):=−\[∇y​y2g​\(xt,yμ∗​\(xt\)\)\+μ​Iq\]−1​∇yf​\(xt,yμ∗​\(xt\)\),v\_\{\\mu\}^\{\*\}\(x\_\{t\}\):=\-\\left\[\\nabla\_\{yy\}^\{2\}g\(x\_\{t\},y\_\{\\mu\}^\{\*\}\(x\_\{t\}\)\)\+\\mu I\_\{q\}\\right\]^\{\-1\}\\nabla\_\{y\}f\(x\_\{t\},y\_\{\\mu\}^\{\*\}\(x\_\{t\}\)\),For any fixedt≥0t\\geq 0, letHμ=∇y​y2g​\(xt,yμ∗​\(xt\)\)\+μ​IqH\_\{\\mu\}=\\nabla\_\{yy\}^\{2\}g\(x\_\{t\},y\_\{\\mu\}^\{\*\}\(x\_\{t\}\)\)\+\\mu I\_\{q\}andwμ=∇yf​\(xt,yμ∗​\(xt\)\)w\_\{\\mu\}=\\nabla\_\{y\}f\(x\_\{t\},y\_\{\\mu\}^\{\*\}\(x\_\{t\}\)\)\. Then, we have:

‖vμt\+1∗​\(xt\)−vμt∗​\(xt\)‖\\displaystyle\\\|v\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\-v\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|=‖Hμt\+1−1​wμt\+1−Hμt−1​wμt‖\\displaystyle=\\\|H\_\{\\mu\_\{t\+1\}\}^\{\-1\}w\_\{\\mu\_\{t\+1\}\}\-H\_\{\\mu\_\{t\}\}^\{\-1\}w\_\{\\mu\_\{t\}\}\\\|\(3\)≤‖Hμt\+1−1​\(wμt\+1−wμt\)‖\+‖\(Hμt\+1−1−Hμt−1\)​wμt‖\\displaystyle\\leq\\\|H\_\{\\mu\_\{t\+1\}\}^\{\-1\}\(w\_\{\\mu\_\{t\+1\}\}\-w\_\{\\mu\_\{t\}\}\)\\\|\+\\\|\(H\_\{\\mu\_\{t\+1\}\}^\{\-1\}\-H\_\{\\mu\_\{t\}\}^\{\-1\}\)w\_\{\\mu\_\{t\}\}\\\|≤♭​ℓσt\+1​‖yμt\+1∗​\(xt\)−yμt∗​\(xt\)‖\+‖Hμt\+1−1‖⋅‖Hμt−Hμt\+1‖⋅‖Hμt−1‖⋅ν,\\displaystyle\\overset\{\\flat\}\{\\leq\}\\frac\{\\ell\}\{\\sigma\_\{t\+1\}\}\\\|y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|\+\\\|H\_\{\\mu\_\{t\+1\}\}^\{\-1\}\\\|\\cdot\\\|H\_\{\\mu\_\{t\}\}\-H\_\{\\mu\_\{t\+1\}\}\\\|\\cdot\\\|H\_\{\\mu\_\{t\}\}^\{\-1\}\\\|\\cdot\\nu,where♭\\flatis due to[Assumption1](https://arxiv.org/html/2609.30501#Thmassumption1)andA−1−B−1=A−1​\(B−A\)​B−1A^\{\-1\}\-B^\{\-1\}=A^\{\-1\}\(B\-A\)B^\{\-1\}\. For the second term, we have:

‖Hμt−Hμt\+1‖≤ρ​‖yμt∗​\(xt\)−yμt\+1∗​\(xt\)‖\+\|μt−μt\+1\|\.\\\|H\_\{\\mu\_\{t\}\}\-H\_\{\\mu\_\{t\+1\}\}\\\|\\leq\\rho\\\|y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\\\|\+\|\\mu\_\{t\}\-\\mu\_\{t\+1\}\|\.
Thus, to tackle[Equation3](https://arxiv.org/html/2609.30501#A2.E3), we need to control the gap‖yμt∗​\(xt\)−yμt\+1∗​\(xt\)‖\\\|y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\\\|\. To this end, we first define the following supporting function for any fixedtt:

hμ​\(y\)=g⁡\(xt,y\)\+μ2​‖y−yt\+1‖2\.h\_\{\\mu\}\(y\)=g\(x\_\{t\},y\)\+\\frac\{\\mu\}\{2\}\\\|y\-y\_\{t\+1\}\\\|^\{2\}\.Since our Alg\.[2](https://arxiv.org/html/2609.30501#algorithm2)ensures that w\.p\.1−δ′1\-\\delta^\{\\prime\},yt\+1y\_\{t\+1\}is anϵt\\epsilon\_\{t\}\-SOSP, we know that‖∇yg​\(xt,yt\+1\)‖≤ϵt\\\|\\nabla\_\{y\}g\(x\_\{t\},y\_\{t\+1\}\)\\\|\\leq\\epsilon\_\{t\}andλmin​\(∇y​y2g​\(xt,yt\+1\)\)≥−ρ​ϵt\\lambda\_\{\\min\}\(\\nabla\_\{yy\}^\{2\}g\(x\_\{t\},y\_\{t\+1\}\)\)\\geq\-\\sqrt\{\\rho\\epsilon\_\{t\}\}\. According to our parameter selection, we can getμt=Θ⁡\(σt\)\\mu\_\{t\}=\\Theta\(\\sigma\_\{t\}\)andρ​ϵt=σt2\\sqrt\{\\rho\\epsilon\_\{t\}\}=\\sigma\_\{t\}^\{2\}\. Accordingly, we have:

λmin​\(∇2hμt​\(yt\+1\)\)≥μt−ρ​ϵt=:=ιt,\\displaystyle\\lambda\_\{\\min\}\(\\nabla^\{2\}h\_\{\\mu\_\{t\}\}\(y\_\{t\+1\}\)\)\\geq\\mu\_\{t\}\-\\sqrt\{\\rho\\epsilon\_\{t\}\}=:=\\iota\_\{t\},λmin​\(∇2hμt\+1​\(yt\+1\)\)≥μt\+1−ρ​ϵt:=ι~t\+1\.\\displaystyle\\lambda\_\{\\min\}\(\\nabla^\{2\}h\_\{\\mu\_\{t\+1\}\}\(y\_\{t\+1\}\)\)\\geq\\mu\_\{t\+1\}\-\\sqrt\{\\rho\\epsilon\_\{t\}\}:=\\tilde\{\\iota\}\_\{t\+1\}\.Note thatσt=Θ⁡\(\(t\+1\)−p\)\\sigma\_\{t\}=\\Theta\(\(t\+1\)^\{\-p\}\)withp∈\(0,13\)p\\in\(0,\\frac\{1\}\{3\}\), we can easily getιt=Θ⁡\(σt\)\\iota\_\{t\}=\\Theta\(\\sigma\_\{t\}\)andι~t\+1=Θ⁡\(σt\)\\tilde\{\\iota\}\_\{t\+1\}=\\Theta\(\\sigma\_\{t\}\)\. Therefore, within a sufficiently small ballℬyt\+1​\(ιt2​ρ\)\\mathcal\{B\}\_\{y\_\{t\+1\}\}\(\\frac\{\\iota\_\{t\}\}\{2\\rho\}\), we haveλmin​\(∇2hμt​\(y\)\)≥ιt2\\lambda\_\{\\min\}\(\\nabla^\{2\}h\_\{\\mu\_\{t\}\}\(y\)\)\\geq\\frac\{\\iota\_\{t\}\}\{2\}\. Thus, noting that∇hμt​\(yμt∗​\(xt\)\)=0\\nabla h\_\{\\mu\_\{t\}\}\(y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\)=0, we can obtain:

‖yμt∗​\(xt\)−yt\+1‖≤2ιt​‖∇hμt​\(yt\+1\)‖=2ιt​‖∇yg​\(xt,yt\+1\)‖≤2​ϵtιt=2​σt4/ριt,\\displaystyle\\\|y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{t\+1\}\\\|\\leq\\frac\{2\}\{\\iota\_\{t\}\}\\\|\\nabla h\_\{\\mu\_\{t\}\}\(y\_\{t\+1\}\)\\\|=\\frac\{2\}\{\\iota\_\{t\}\}\\\|\\nabla\_\{y\}g\(x\_\{t\},y\_\{t\+1\}\)\\\|\\leq\\frac\{2\\epsilon\_\{t\}\}\{\\iota\_\{t\}\}=\\frac\{2\\sigma\_\{t\}^\{4\}/\\rho\}\{\\iota\_\{t\}\},⟹\\displaystyle\\implies‖yμt∗​\(xt\)−yt\+1‖=𝒪⁡\(σt3\)\.\\displaystyle\\\|y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{t\+1\}\\\|=\\mathcal\{O\}\(\\sigma\_\{t\}^\{3\}\)\.
Similarly, within a small ball centered atyt\+1y\_\{t\+1\},hμt\+1h\_\{\\mu\_\{t\+1\}\}remainsι~t\+12\\frac\{\\tilde\{\\iota\}\_\{t\+1\}\}\{2\}\-strong convex, which implies:

ι~t\+12​‖yμt\+1∗​\(xt\)−yμt∗​\(xt\)‖2\\displaystyle\\frac\{\\tilde\{\\iota\}\_\{t\+1\}\}\{2\}\\\|y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|^\{2\}≤⟨∇hμt\+1​\(yμt∗​\(xt\)\)−∇hμt\+1​\(yμt\+1∗​\(xt\)\),yμt∗​\(xt\)−yμt\+1∗​\(xt\)⟩\\displaystyle\\leq\\langle\\nabla h\_\{\\mu\_\{t\+1\}\}\(y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\)\-\\nabla h\_\{\\mu\_\{t\+1\}\}\(y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\),y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\\rangle=†​⟨∇yg​\(xt,yμt∗​\(xt\)\)\+μt\+1​\(yμt∗​\(xt\)−yt\+1\),yμt∗​\(xt\)−yμt\+1∗​\(xt\)⟩\\displaystyle\\overset\{\\dagger\}\{=\}\\langle\\nabla\_\{y\}g\(x\_\{t\},y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\)\+\\mu\_\{t\+1\}\(y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{t\+1\}\),y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\\rangle=‡​⟨\(μt\+1−μt\)​\(yμt∗​\(xt\)−yt\+1\),yμt∗​\(xt\)−yμt\+1∗​\(xt\)⟩\\displaystyle\\overset\{\\ddagger\}\{=\}\\langle\(\\mu\_\{t\+1\}\-\\mu\_\{t\}\)\(y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{t\+1\}\),y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\\rangle≤♭​\|μt\+1−μt\|⋅‖yμt∗​\(xt\)−yt\+1‖⋅‖yμt\+1∗​\(xt\)−yμt∗​\(xt\)‖,\\displaystyle\\overset\{\\flat\}\{\\leq\}\|\\mu\_\{t\+1\}\-\\mu\_\{t\}\|\\cdot\\\|y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{t\+1\}\\\|\\cdot\\\|y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|,where†\\daggeris becauseyμt\+1∗​\(xt\)y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)minimizeshμt\+1h\_\{\\mu\_\{t\+1\}\},‡\\ddaggeris due to∇yg​\(xt,yμt∗​\(xt\)\)\+μt​\(yμt∗​\(xt\)−yt\+1\)=0\\nabla\_\{y\}g\(x\_\{t\},y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\)\+\\mu\_\{t\}\(y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{t\+1\}\)=0, and♭\\flatis induced by the Cauchy\-Schwarz inequality\. Thus, we have:

‖yμt\+1∗​\(xt\)−yμt∗​\(xt\)‖≤2​\|μt\+1−μt\|ι~t\+1​‖yμt∗​\(xt\)−yt\+1‖\.\\\|y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|\\leq\\frac\{2\|\\mu\_\{t\+1\}\-\\mu\_\{t\}\|\}\{\\tilde\{\\iota\}\_\{t\+1\}\}\\\|y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{t\+1\}\\\|\.Substituting the bound‖yμt∗​\(xt\)−yt\+1‖=𝒪⁡\(σt3\)\\\|y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{t\+1\}\\\|=\\mathcal\{O\}\(\\sigma\_\{t\}^\{3\}\)and applying the rigorous lower boundι~t\+1=Θ⁡\(σt\)\\tilde\{\\iota\}\_\{t\+1\}=\\Theta\(\\sigma\_\{t\}\), we can get:

‖yμt\+1∗​\(xt\)−yμt∗​\(xt\)‖=𝒪⁡\(σt2\)​\|μt−μt\+1\|\.\\\|y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|=\\mathcal\{O\}\(\\sigma\_\{t\}^\{2\}\)\|\\mu\_\{t\}\-\\mu\_\{t\+1\}\|\.
We then substitute the above results into[Equation3](https://arxiv.org/html/2609.30501#A2.E3)to get:

‖vμt\+1∗​\(xt\)−vμt∗​\(xt\)‖≤ℓσt\+1​‖yμt\+1∗​\(xt\)−yμt∗​\(xt\)‖\+‖Hμt\+1−1‖⋅‖Ht−Ht\+1‖⋅‖Hμt−1‖⋅ν\\displaystyle\\\|v\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\-v\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|\\leq\\frac\{\\ell\}\{\\sigma\_\{t\+1\}\}\\\|y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\\\!\-\\\!y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|\+\\\|H\_\{\\mu\_\{t\+1\}\}^\{\-1\}\\\|\\cdot\\\|H\_\{t\}\-H\_\{t\+1\}\\\|\\cdot\\\|H\_\{\\mu\_\{t\}\}^\{\-1\}\\\|\\cdot\\nu⟹\\displaystyle\\implies‖vμt\+1∗​\(xt\)−vμt∗​\(xt\)‖=\(ℓσt\+1\+ν​ρσt​σt\+1\)​𝒪​\(σt2\)​\|μt−μt\+1\|\+νσt​σt\+1​\|μt−μt\+1\|\.\\displaystyle\\\|v\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\-v\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|=\\left\(\\frac\{\\ell\}\{\\sigma\_\{t\+1\}\}\+\\frac\{\\nu\\rho\}\{\\sigma\_\{t\}\\sigma\_\{t\+1\}\}\\right\)\\mathcal\{O\}\(\\sigma\_\{t\}^\{2\}\)\|\\mu\_\{t\}\-\\mu\_\{t\+1\}\|\+\\frac\{\\nu\}\{\\sigma\_\{t\}\\sigma\_\{t\+1\}\}\|\\mu\_\{t\}\-\\mu\_\{t\+1\}\|\.This indicates:

‖vμt\+1∗​\(xt\)−vμt∗​\(xt\)‖\\displaystyle\\\|v\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\-v\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|=𝒪⁡\(1σt​σt\+1​\|μt−μt\+1\|\)=𝒪⁡\(\(t\+1\)−p−1\(t\+1\)−p​\(t\+2\)−p\)\\displaystyle=\\mathcal\{O\}\\left\(\\frac\{1\}\{\\sigma\_\{t\}\\sigma\_\{t\+1\}\}\|\\mu\_\{t\}\-\\mu\_\{t\+1\}\|\\right\)=\\mathcal\{O\}\\left\(\\frac\{\(t\+1\)^\{\-p\-1\}\}\{\(t\+1\)^\{\-p\}\(t\+2\)^\{\-p\}\}\\right\)=𝒪⁡\(\(t\+1\)−p−1\(t\+1\)−2​p​2−p\)=𝒪⁡\(\(t\+1\)p−1\)\.\\displaystyle=\\mathcal\{O\}\\left\(\\frac\{\(t\+1\)^\{\-p\-1\}\}\{\(t\+1\)^\{\-2p\}2^\{\-p\}\}\\right\)=\\mathcal\{O\}\\big\(\(t\+1\)^\{p\-1\}\\big\)\.
Partℬ\\mathcal\{B\}\.We then consider the error introduced by the Conjugate Gradient step\. Recall thatvμt∗​\(xt\)=\[∇y​y2g​\(xt,yμt∗​\(xt\)\)\+μt​Iq\]−1​∇yf​\(xt,yμt∗​\(xt\)\)v\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)=\[\\nabla\_\{yy\}^\{2\}g\(x\_\{t\},y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\)\+\\mu\_\{t\}I\_\{q\}\]^\{\-1\}\\nabla\_\{y\}f\(x\_\{t\},y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\), and we now defineEt:=‖vt−vμt−1∗​\(xt−1\)‖2E\_\{t\}:=\\\|v\_\{t\}\-v\_\{\\mu\_\{t\-1\}\}^\{\*\}\(x\_\{t\-1\}\)\\\|^\{2\}\. Note that Conjugate Gradient actually solves a linear systemHt​v=btH\_\{t\}v=b\_\{t\}, whereHt=∇y​y2​g​\(xt,yt\+1\)\+μt​IqH\_\{t\}=\\nabla\_\{yy\}^\{2\}g\(x\_\{t\},y\_\{t\+1\}\)\+\\mu\_\{t\}I\_\{q\}andbt=∇yf​\(xt,yt\+1\)b\_\{t\}=\\nabla\_\{y\}f\(x\_\{t\},y\_\{t\+1\}\)at each steptt\. We correspondingly denote the exact solution to this linear system asvt∘=Ht−1​btv\_\{t\}^\{\\circ\}=H\_\{t\}^\{\-1\}b\_\{t\}\. According to[Grazzi et al\. \(2020\)](https://arxiv.org/html/2609.30501#bib.bib33), by selectingNt=Θ~​\(\(t\+1\)p\)N\_\{t\}=\\widetilde\{\\Theta\}\(\\sqrt\{\(t\+1\)^\{p\}\}\), we can obtain:

‖vt\+1−vt∘‖≤2​\(t\+1\)p2​\(\(t\+1\)p2−1\(t\+1\)p2\+1\)Nt​‖vt−vt∘‖,⟹‖vt\+1−vt∘‖≤12​‖vt−vt∘‖\.\\displaystyle\\\|v\_\{t\+1\}\-v\_\{t\}^\{\\circ\}\\\|\\leq 2\(t\+1\)^\{\\frac\{p\}\{2\}\}\\left\(\\frac\{\(t\+1\)^\{\\frac\{p\}\{2\}\}\-1\}\{\(t\+1\)^\{\\frac\{p\}\{2\}\}\+1\}\\right\)^\{N\_\{t\}\}\\\|v\_\{t\}\-v\_\{t\}^\{\\circ\}\\\|,\\,\\,\\,\\implies\\,\\,\\,\\\|v\_\{t\+1\}\-v\_\{t\}^\{\\circ\}\\\|\\leq\\frac\{1\}\{\\sqrt\{2\}\}\\\|v\_\{t\}\-v\_\{t\}^\{\\circ\}\\\|\.Therefore, we have:

Et\+1=‖vt\+1−vμt∗​\(xt\)‖≤‖vt\+1−vt∘‖\+‖vt∘−vμt∗​\(xt\)‖\.\\displaystyle\\sqrt\{E\_\{t\+1\}\}=\\\|v\_\{t\+1\}\-v\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|\\leq\\\|v\_\{t\+1\}\-v\_\{t\}^\{\\circ\}\\\|\+\\\|v\_\{t\}^\{\\circ\}\-v\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|\.Thus, we need to bound‖vt−vt∘‖\\\|v\_\{t\}\-v\_\{t\}^\{\\circ\}\\\|, which can be controlled by:

‖vt−vt∘‖≤Et\+‖vμt−1∗​\(xt−1\)−vμt−1∗​\(xt\)‖⏟1\+‖vμt−1∗​\(xt\)−vμt∗​\(xt\)‖⏟2\+‖vμt∗​\(xt\)−vt∘‖⏟3\.\\displaystyle\\\|v\_\{t\}\-v\_\{t\}^\{\\circ\}\\\|\\leq\\sqrt\{E\_\{t\}\}\+\\underbrace\{\\\|v\_\{\\mu\_\{t\-1\}\}^\{\*\}\(x\_\{t\-1\}\)\-v\_\{\\mu\_\{t\-1\}\}^\{\*\}\(x\_\{t\}\)\\\|\}\_\{\\mathchoice\{\\raisebox\{\-2\.0pt\}\{\\makebox\[8\.51111pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\displaystyle 1$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[8\.51111pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\textstyle 1$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[7\.15778pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\scriptstyle 1$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[6\.25555pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\scriptscriptstyle 1$\}\}\}\}\}\}\+\\underbrace\{\\\|v\_\{\\mu\_\{t\-1\}\}^\{\*\}\(x\_\{t\}\)\-v\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|\}\_\{\\mathchoice\{\\raisebox\{\-2\.0pt\}\{\\makebox\[8\.51111pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\displaystyle 2$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[8\.51111pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\textstyle 2$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[7\.15778pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\scriptstyle 2$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[6\.25555pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\scriptscriptstyle 2$\}\}\}\}\}\}\+\\underbrace\{\\\|v\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\-v\_\{t\}^\{\\circ\}\\\|\}\_\{\\mathchoice\{\\raisebox\{\-2\.0pt\}\{\\makebox\[8\.51111pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\displaystyle 3$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[8\.51111pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\textstyle 3$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[7\.15778pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\scriptstyle 3$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[6\.25555pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\scriptscriptstyle 3$\}\}\}\}\}\}\.We now control each of these terms\. For1, we first note that:

‖vμ∗​\(x\)−vμ∗​\(x′\)‖\\displaystyle\\\|v\_\{\\mu\}^\{\*\}\(x\)\-v\_\{\\mu\}^\{\*\}\(x^\{\\prime\}\)\\\|≤\\displaystyle\\leq‖\[∇y​y2g​\(x,yμ∗​\(x\)\)\+μ​Iq\]−1​\(∇yf​\(x,yμ∗​\(x\)\)−∇yf​\(x′,yμ∗​\(x′\)\)\)‖\\displaystyle\\left\\\|\\left\[\\nabla\_\{yy\}^\{2\}g\(x,y\_\{\\mu\}^\{\*\}\(x\)\)\+\\mu I\_\{q\}\\right\]^\{\-1\}\\big\(\\nabla\_\{y\}f\(x,y\_\{\\mu\}^\{\*\}\(x\)\)\-\\nabla\_\{y\}f\(x^\{\\prime\},y\_\{\\mu\}^\{\*\}\(x^\{\\prime\}\)\)\\big\)\\right\\\|\+‖\(\[∇y​y2g​\(x,yμ∗​\(x\)\)\+μ​Iq\]−1−\[∇y​y2g​\(x′,yμ∗​\(x′\)\)\+μ​Iq\]−1\)​∇yf​\(x′,yμ∗​\(x′\)\)‖\\displaystyle\+\\left\\\|\\left\(\\left\[\\nabla\_\{yy\}^\{2\}g\(x,y\_\{\\mu\}^\{\*\}\(x\)\)\+\\mu I\_\{q\}\\right\]^\{\-1\}\-\\left\[\\nabla\_\{yy\}^\{2\}g\(x^\{\\prime\},y\_\{\\mu\}^\{\*\}\(x^\{\\prime\}\)\)\+\\mu I\_\{q\}\\right\]^\{\-1\}\\right\)\\nabla\_\{y\}f\(x^\{\\prime\},y\_\{\\mu\}^\{\*\}\(x^\{\\prime\}\)\)\\right\\\|≤\\displaystyle\\leq\(ℓσ\+ν​ρσ2\)​\(1\+ℓσ\)​‖x−x′‖=Θ⁡\(σ−3\)​‖x−x′‖,\\displaystyle\\left\(\\frac\{\\ell\}\{\\sigma\}\+\\frac\{\\nu\\rho\}\{\\sigma^\{2\}\}\\right\)\\left\(1\+\\frac\{\\ell\}\{\\sigma\}\\right\)\\\|x\-x^\{\\prime\}\\\|=\\Theta\(\\sigma^\{\-3\}\)\\\|x\-x^\{\\prime\}\\\|,meaning that its Lipschitz continuity coefficient is in the order ofΘ⁡\(σ−3\)\\Theta\(\\sigma^\{\-3\}\)\. Therefore, we have:

1≤Θ⁡\(σt−3\)​αt−1​‖∇^​Φμt−1​\(xt−1\)‖⟹1=𝒪⁡\(\(t\+1\)3​p−q\)​‖∇^​Φμt−1​\(xt−1\)‖\.\\displaystyle\\leq\\Theta\(\\sigma\_\{t\}^\{\-3\}\)\\alpha\_\{t\-1\}\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\-1\}\}\(x\_\{t\-1\}\)\\\|\\,\\,\\,\\implies\\,\\,\\,\\mathchoice\{\\raisebox\{\-2\.0pt\}\{\\makebox\[10\.44444pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\displaystyle 1$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[10\.44444pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\textstyle 1$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[8\.51111pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\scriptstyle 1$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[7\.40283pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\oval\(0\.0,0\.0\)\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\scriptscriptstyle 1$\}\}\}\}\}=\\mathcal\{O\}\\big\(\(t\+1\)^\{3p\-q\}\\big\)\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\-1\}\}\(x\_\{t\-1\}\)\\\|\.For2, we can follow Part𝒜\\mathcal\{A\}to get2=𝒪⁡\(\(t\+1\)p−1\)\\mathchoice\{\\raisebox\{\-2\.0pt\}\{\\makebox\[10\.44444pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\displaystyle 2$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[10\.44444pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\textstyle 2$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[8\.51111pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\scriptstyle 2$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[7\.40283pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\oval\(0\.0,0\.0\)\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\scriptscriptstyle 2$\}\}\}\}\}=\\mathcal\{O\}\(\(t\+1\)^\{p\-1\}\)\.

For3, we have:

3≤‖\[∇y​y2g​\(xt,yμt∗​\(xt\)\)\+μt​Iq\]−1​\(∇yf​\(xt,yμt∗​\(xt\)\)−∇yf​\(xt,yt\+1\)\)‖\\displaystyle\\leq\\left\\\|\\left\[\\nabla\_\{yy\}^\{2\}g\(x\_\{t\},y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\)\+\\mu\_\{t\}I\_\{q\}\\right\]^\{\-1\}\\big\(\\nabla\_\{y\}f\(x\_\{t\},y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\)\-\\nabla\_\{y\}f\(x\_\{t\},y\_\{t\+1\}\)\\big\)\\right\\\|\+‖\(\[∇y​y2g​\(xt,yμt∗​\(xt\)\)\+μt​Iq\]−1−Ht−1\)​∇yf​\(xt,yt\+1\)‖,\\displaystyle\\,\\,\\,\\,\\,\\,\+\\left\\\|\\left\(\\left\[\\nabla\_\{yy\}^\{2\}g\(x\_\{t\},y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\)\+\\mu\_\{t\}I\_\{q\}\\right\]^\{\-1\}\-H\_\{t\}^\{\-1\}\\right\)\\nabla\_\{y\}f\(x\_\{t\},y\_\{t\+1\}\)\\right\\\|,⟹3\\displaystyle\\implies\\mathchoice\{\\raisebox\{\-2\.0pt\}\{\\makebox\[10\.44444pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\displaystyle 3$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[10\.44444pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\textstyle 3$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[8\.51111pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\circle\{0\.0\}\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\scriptstyle 3$\}\}\}\}\}\{\\raisebox\{\-2\.0pt\}\{\\makebox\[7\.40283pt\]\{\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(0\.0,0\.0\)\{\\oval\(0\.0,0\.0\)\}\}\\pic@makebox@\{\\makebox\}\{\}\(0\.0,0\.0\)\{\\put\(\-0\.5,0\.0\)\{$\\scriptscriptstyle 3$\}\}\}\}\}=ℓσt​𝒪​\(σt3\)\+ν​ρσt2​𝒪​\(σt3\)=𝒪⁡\(\(t\+1\)−p\)\.\\displaystyle=\\frac\{\\ell\}\{\\sigma\_\{t\}\}\\mathcal\{O\}\(\\sigma\_\{t\}^\{3\}\)\+\\frac\{\\nu\\rho\}\{\\sigma\_\{t\}^\{2\}\}\\mathcal\{O\}\(\\sigma\_\{t\}^\{3\}\)=\\mathcal\{O\}\\big\(\(t\+1\)^\{\-p\}\\big\)\.
Substituting them back, we can get:

‖vt−vt∘‖=Et\+𝒪⁡\(\(t\+1\)3​p−q\)​‖∇^​Φμt−1​\(xt−1\)‖\+𝒪⁡\(\(t\+1\)−p\),\\displaystyle\\\|v\_\{t\}\-v\_\{t\}^\{\\circ\}\\\|=\\sqrt\{E\_\{t\}\}\+\\mathcal\{O\}\\big\(\(t\+1\)^\{3p\-q\}\\big\)\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\-1\}\}\(x\_\{t\-1\}\)\\\|\+\\mathcal\{O\}\\big\(\(t\+1\)^\{\-p\}\\big\),⟹\\displaystyle\\impliesEt\+1=12​Et\+𝒪⁡\(\(t\+1\)3​p−q\)​‖∇^​Φμt−1​\(xt−1\)‖\+𝒪⁡\(\(t\+1\)−p\)\.\\displaystyle\\sqrt\{E\_\{t\+1\}\}=\\frac\{1\}\{\\sqrt\{2\}\}\\sqrt\{E\_\{t\}\}\+\\mathcal\{O\}\\big\(\(t\+1\)^\{3p\-q\}\\big\)\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\-1\}\}\(x\_\{t\-1\}\)\\\|\+\\mathcal\{O\}\\big\(\(t\+1\)^\{\-p\}\\big\)\.According to the Young’s inequality with constant1/21/2, we have:

Et\+1\\displaystyle E\_\{t\+1\}=\(1\+12\)​\(12​Et\)2\+\(1\+2\)​\(𝒪⁡\(\(t\+1\)3​p−q\)​‖∇^​Φμt−1​\(xt−1\)‖\+𝒪⁡\(\(t\+1\)−p\)\)2\\displaystyle=\\left\(1\+\\frac\{1\}\{2\}\\right\)\\left\(\\frac\{1\}\{\\sqrt\{2\}\}\\sqrt\{E\_\{t\}\}\\right\)^\{2\}\+\(1\+2\)\\left\(\\mathcal\{O\}\\big\(\(t\+1\)^\{3p\-q\}\\big\)\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\-1\}\}\(x\_\{t\-1\}\)\\\|\+\\mathcal\{O\}\\big\(\(t\+1\)^\{\-p\}\\big\)\\right\)^\{2\}=34​Et\+𝒪⁡\(\(t\+1\)6​p−2​q\)​‖∇^​Φμt−1​\(xt−1\)‖2\+𝒪⁡\(\(t\+1\)−2​p\)\.\\displaystyle=\\frac\{3\}\{4\}E\_\{t\}\+\\mathcal\{O\}\\big\(\(t\+1\)^\{6p\-2q\}\\big\)\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\-1\}\}\(x\_\{t\-1\}\)\\\|^\{2\}\+\\mathcal\{O\}\\big\(\(t\+1\)^\{\-2p\}\\big\)\.
Part𝒞\\mathcal\{C\}\.In this part, we control the shiftΦμt\+1​\(xt\+1\)−Φμt​\(xt\)\\Phi\_\{\\mu\_\{t\+1\}\}\(x\_\{t\+1\}\)\-\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\. We first compute the smoothness coefficient ofΦμ\\Phi\_\{\\mu\}as follows\. According to[Assumption1](https://arxiv.org/html/2609.30501#Thmassumption1), for anyx,x′x,x^\{\\prime\}we have:

‖∇Φμ​\(x\)−∇Φμ​\(x′\)‖\\displaystyle\\\|\\nabla\\Phi\_\{\\mu\}\(x\)\-\\nabla\\Phi\_\{\\mu\}\(x^\{\\prime\}\)\\\|≤\\displaystyle\\leq‖∇xf​\(x,yμ∗​\(x\)\)−∇xf​\(x′,yμ∗​\(x′\)\)‖\\displaystyle\\\|\\nabla\_\{x\}f\(x,y\_\{\\mu\}^\{\*\}\(x\)\)\-\\nabla\_\{x\}f\(x^\{\\prime\},y\_\{\\mu\}^\{\*\}\(x^\{\\prime\}\)\)\\\|\+‖\(∇x​y2g​\(x,yμ∗​\(x\)\)−∇x​y2g​\(x′,yμ∗​\(x′\)\)\)​vμ∗​\(x\)‖\+‖∇x​y2g​\(x′,yμ∗​\(x′\)\)​\(vμ∗​\(x\)−vμ∗​\(x′\)\)‖\\displaystyle\+\\left\\\|\\big\(\\nabla\_\{xy\}^\{2\}g\(x,y\_\{\\mu\}^\{\*\}\(x\)\)\-\\nabla\_\{xy\}^\{2\}g\(x^\{\\prime\},y\_\{\\mu\}^\{\*\}\(x^\{\\prime\}\)\)\\big\)v\_\{\\mu\}^\{\*\}\(x\)\\right\\\|\+\\left\\\|\\nabla\_\{xy\}^\{2\}g\(x^\{\\prime\},y\_\{\\mu\}^\{\*\}\(x^\{\\prime\}\)\)\\big\(v\_\{\\mu\}^\{\*\}\(x\)\-v\_\{\\mu\}^\{\*\}\(x^\{\\prime\}\)\\big\)\\right\\\|≤\\displaystyle\\leq\(ℓ\+‖vμ∗​\(x\)‖⋅ρ\)​\(‖x−x′‖\+‖yμ∗​\(x\)−yμ∗​\(x′\)‖\)\+ℓ​‖vμ∗​\(x\)−vμ∗​\(x′\)‖\\displaystyle\\big\(\\ell\+\\\|v\_\{\\mu\}^\{\*\}\(x\)\\\|\\cdot\\rho\\big\)\\big\(\\\|x\-x^\{\\prime\}\\\|\+\\\|y\_\{\\mu\}^\{\*\}\(x\)\-y\_\{\\mu\}^\{\*\}\(x^\{\\prime\}\)\\\|\\big\)\+\\ell\\\|v\_\{\\mu\}^\{\*\}\(x\)\-v\_\{\\mu\}^\{\*\}\(x^\{\\prime\}\)\\\|≤\\displaystyle\\leq\(ℓ\+νσ⋅ρ\)​\(‖x−x′‖\+‖yμ∗​\(x\)−yμ∗​\(x′\)‖\)\\displaystyle\\left\(\\ell\+\\frac\{\\nu\}\{\\sigma\}\\cdot\\rho\\right\)\\big\(\\\|x\-x^\{\\prime\}\\\|\+\\\|y\_\{\\mu\}^\{\*\}\(x\)\-y\_\{\\mu\}^\{\*\}\(x^\{\\prime\}\)\\\|\\big\)\+ℓ⁡‖\[∇y​y2g​\(x,yμ∗​\(x\)\)\+μ​Iq\]−1​\(∇yf​\(x,yμ∗​\(x\)\)−∇yf​\(x′,yμ∗​\(x′\)\)\)‖\\displaystyle\+\\ell\\left\\\|\\left\[\\nabla\_\{yy\}^\{2\}g\(x,y\_\{\\mu\}^\{\*\}\(x\)\)\+\\mu I\_\{q\}\\right\]^\{\-1\}\\big\(\\nabla\_\{y\}f\(x,y\_\{\\mu\}^\{\*\}\(x\)\)\-\\nabla\_\{y\}f\(x^\{\\prime\},y\_\{\\mu\}^\{\*\}\(x^\{\\prime\}\)\)\\big\)\\right\\\|\+ℓ⁡‖\(\[∇y​y2g​\(x,yμ∗​\(x\)\)\+μ​Iq\]−1−\[∇y​y2g​\(x′,yμ∗​\(x′\)\)\+μ​Iq\]−1\)​∇yf​\(x′,yμ∗​\(x′\)\)‖\\displaystyle\+\\ell\\left\\\|\\left\(\\left\[\\nabla\_\{yy\}^\{2\}g\(x,y\_\{\\mu\}^\{\*\}\(x\)\)\+\\mu I\_\{q\}\\right\]^\{\-1\}\-\\left\[\\nabla\_\{yy\}^\{2\}g\(x^\{\\prime\},y\_\{\\mu\}^\{\*\}\(x^\{\\prime\}\)\)\+\\mu I\_\{q\}\\right\]^\{\-1\}\\right\)\\nabla\_\{y\}f\(x^\{\\prime\},y\_\{\\mu\}^\{\*\}\(x^\{\\prime\}\)\)\\right\\\|≤\\displaystyle\\leq\(ℓ\+ν​ρσ\+ℓ2σ\+ν​ℓ​ρσ2\)​\(‖x−x′‖\+ℓσ​‖x−x′‖\)\\displaystyle\\left\(\\ell\+\\frac\{\\nu\\rho\}\{\\sigma\}\+\\frac\{\\ell^\{2\}\}\{\\sigma\}\+\\frac\{\\nu\\ell\\rho\}\{\\sigma^\{2\}\}\\right\)\\left\(\\\|x\-x^\{\\prime\}\\\|\+\\frac\{\\ell\}\{\\sigma\}\\\|x\-x^\{\\prime\}\\\|\\right\)≤\\displaystyle\\leq\(ℓ\+ν​ρσ\+ℓ2σ\+ν​ℓ​ρσ2\)​\(1\+ℓσ\)​‖x−x′‖≜Lμ​‖x−x′‖\.\\displaystyle\\left\(\\ell\+\\frac\{\\nu\\rho\}\{\\sigma\}\+\\frac\{\\ell^\{2\}\}\{\\sigma\}\+\\frac\{\\nu\\ell\\rho\}\{\\sigma^\{2\}\}\\right\)\\left\(1\+\\frac\{\\ell\}\{\\sigma\}\\right\)\\\|x\-x^\{\\prime\}\\\|\\triangleq L\_\{\\mu\}\\\|x\-x^\{\\prime\}\\\|\.We denoteLt:=LμtL\_\{t\}:=L\_\{\\mu\_\{t\}\}\. Given theLt\+1L\_\{t\+1\}\-smoothness ofΦμt\+1\\Phi\_\{\\mu\_\{t\+1\}\}withLt\+1=Θ⁡\(\(t\+1\)3​p\)L\_\{t\+1\}=\\Theta\(\(t\+1\)^\{3p\}\), and applying the update rulext\+1=xt−αt​∇^​Φμt​\(xt\)x\_\{t\+1\}=x\_\{t\}\-\\alpha\_\{t\}\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)withq≥3​pq\\geq 3p, the descent lemma yields:

Φμt\+1​\(xt\+1\)−Φμt\+1​\(xt\)\\displaystyle\\Phi\_\{\\mu\_\{t\+1\}\}\(x\_\{t\+1\}\)\-\\Phi\_\{\\mu\_\{t\+1\}\}\(x\_\{t\}\)≤\\displaystyle\\leq⟨∇Φμt\+1​\(xt\),xt\+1−xt⟩\+Lt\+12​‖xt\+1−xt‖2\\displaystyle\\langle\\nabla\\Phi\_\{\\mu\_\{t\+1\}\}\(x\_\{t\}\),x\_\{t\+1\}\-x\_\{t\}\\rangle\+\\frac\{L\_\{t\+1\}\}\{2\}\\\|x\_\{t\+1\}\-x\_\{t\}\\\|^\{2\}=\\displaystyle=−αt​⟨∇Φμt\+1​\(xt\),∇^​Φμt​\(xt\)⟩\+Lt\+1​αt22​‖∇^​Φμt​\(xt\)‖2\\displaystyle\-\\alpha\_\{t\}\\langle\\nabla\\Phi\_\{\\mu\_\{t\+1\}\}\(x\_\{t\}\),\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\rangle\+\\frac\{L\_\{t\+1\}\\alpha\_\{t\}^\{2\}\}\{2\}\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|^\{2\}≤\\displaystyle\\leq−αt2​‖∇Φμt​\(xt\)‖2−αt4​‖∇^​Φμt​\(xt\)‖2\+αt2​‖∇Φμt\+1​\(xt\)−∇^​Φμt​\(xt\)‖2,\\displaystyle\-\\frac\{\\alpha\_\{t\}\}\{2\}\\\|\\nabla\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|^\{2\}\-\\frac\{\\alpha\_\{t\}\}\{4\}\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|^\{2\}\+\\frac\{\\alpha\_\{t\}\}\{2\}\\\|\\nabla\\Phi\_\{\\mu\_\{t\+1\}\}\(x\_\{t\}\)\-\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|^\{2\},where in the last inequality, we use the fact that‖a−b‖2=‖a‖2\+‖b‖2−2​⟨a,b⟩\\\|a\-b\\\|^\{2\}=\\\|a\\\|^\{2\}\+\\\|b\\\|^\{2\}\-2\\langle a,b\\rangle\. For the last term, we can control it by:

‖∇Φμt\+1​\(xt\)−∇^​Φμt​\(xt\)‖≤\\displaystyle\\\|\\nabla\\Phi\_\{\\mu\_\{t\+1\}\}\(x\_\{t\}\)\-\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|\\leq‖∇xf​\(xt,yμt\+1∗​\(xt\)\)−∇xf​\(xt,yt\+1\)‖⏟Term A\\displaystyle\\underbrace\{\\\|\\nabla\_\{x\}f\(x\_\{t\},y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\)\-\\nabla\_\{x\}f\(x\_\{t\},y\_\{t\+1\}\)\\\|\}\_\{\\text\{Term A\}\}\+‖∇x​y2g​\(xt,yμt\+1∗​\(xt\)\)​vμt\+1∗​\(xt\)−∇x​y2g​\(xt,yt\+1\)​vt\+1‖⏟Term B\.\\displaystyle\+\\underbrace\{\\\|\\nabla\_\{xy\}^\{2\}g\(x\_\{t\},y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\)v\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\-\\nabla\_\{xy\}^\{2\}g\(x\_\{t\},y\_\{t\+1\}\)v\_\{t\+1\}\\\|\}\_\{\\text\{Term B\}\}\.Then, we have:

Term A≤ℓ​‖yμt\+1∗​\(xt\)−yt\+1‖=𝒪⁡\(‖yμt\+1∗​\(xt\)−yμt∗​\(xt\)‖\+‖yμt∗​\(xt\)−yt\+1‖\),\\displaystyle\\leq\\ell\\\|y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{t\+1\}\\\|=\\mathcal\{O\}\\big\(\\\|y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|\+\\\|y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{t\+1\}\\\|\\big\),⟹Term A\\displaystyle\\implies\\text\{Term A\}=𝒪⁡\(t−3​p−1\)\+𝒪⁡\(t−3​p\)=𝒪⁡\(t−3​p\)\.\\displaystyle=\\mathcal\{O\}\(t^\{\-3p\-1\}\)\+\\mathcal\{O\}\(t^\{\-3p\}\)=\\mathcal\{O\}\(t^\{\-3p\}\)\.Besides, we have:

Term B≤ρ​‖yμt\+1∗​\(xt\)−yt\+1‖⋅‖vμt\+1∗​\(xt\)‖\+ℓ⁡\(‖vμt\+1∗​\(xt\)−vμt∗​\(xt\)‖\+Et\+1\),\\displaystyle\\leq\\rho\\\|y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{t\+1\}\\\|\\cdot\\\|v\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\\\|\+\\ell\(\\\|v\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\-v\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|\+\\sqrt\{E\_\{t\+1\}\}\),⟹Term B\\displaystyle\\implies\\text\{Term B\}=𝒪⁡\(t−3​p⋅tp\)\+𝒪⁡\(tp−1\)\+𝒪⁡\(Et\+1\)=𝒪⁡\(t−2​p\+tp−1\+Et\+1\)\.\\displaystyle=\\mathcal\{O\}\(t^\{\-3p\}\\cdot t^\{p\}\)\+\\mathcal\{O\}\(t^\{p\-1\}\)\+\\mathcal\{O\}\(\\sqrt\{E\_\{t\+1\}\}\)=\\mathcal\{O\}\(t^\{\-2p\}\+t^\{p\-1\}\+\\sqrt\{E\_\{t\+1\}\}\)\.Thus, we combine them to get:

‖∇Φμt\+1​\(xt\)−∇^​Φμt​\(xt\)‖2=𝒪⁡\(t−4​p\+t2​p−2\+Et\+1\)\.\\\|\\nabla\\Phi\_\{\\mu\_\{t\+1\}\}\(x\_\{t\}\)\-\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|^\{2\}=\\mathcal\{O\}\(t^\{\-4p\}\+t^\{2p\-2\}\+E\_\{t\+1\}\)\.
Also, we consider the the gap\|Φμt\+1​\(xt\)−Φμt​\(xt\)\|\|\\Phi\_\{\\mu\_\{t\+1\}\}\(x\_\{t\}\)\-\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\|\. According to[Assumption1](https://arxiv.org/html/2609.30501#Thmassumption1), we have:

\|Φμt\+1​\(xt\)−Φμt​\(xt\)\|\\displaystyle\|\\Phi\_\{\\mu\_\{t\+1\}\}\(x\_\{t\}\)\-\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\|=\|f⁡\(xt,yμt\+1∗​\(xt\)\)−f⁡\(xt,yμt∗​\(xt\)\)\|≤ν​‖yμt\+1∗​\(xt\)−yμt∗​\(xt\)‖,\\displaystyle=\|f\(x\_\{t\},y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\)\-f\(x\_\{t\},y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\)\|\\leq\\nu\\\|y\_\{\\mu\_\{t\+1\}\}^\{\*\}\(x\_\{t\}\)\-y\_\{\\mu\_\{t\}\}^\{\*\}\(x\_\{t\}\)\\\|,⟹\|Φμt\+1​\(xt\)−Φμt​\(xt\)\|\\displaystyle\\implies\|\\Phi\_\{\\mu\_\{t\+1\}\}\(x\_\{t\}\)\-\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\|=♭​𝒪​\(σt2\)​\|μt−μt\+1\|=𝒪⁡\(\(t\+1\)−3​p−1\),\\displaystyle\\overset\{\\flat\}\{=\}\\mathcal\{O\}\(\\sigma\_\{t\}^\{2\}\)\|\\mu\_\{t\}\-\\mu\_\{t\+1\}\|=\\mathcal\{O\}\\big\(\(t\+1\)^\{\-3p\-1\}\\big\),where♭\\flatcan be implied by Part𝒜\\mathcal\{A\}\.

We can introduce positive constantsC1,C1′C\_\{1\},C\_\{1\}^\{\\prime\}to construct the following result:

Φμt\+1​\(xt\+1\)−Φμt​\(xt\)\\displaystyle\\Phi\_\{\\mu\_\{t\+1\}\}\(x\_\{t\+1\}\)\-\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)=\\displaystyle=\[Φμt\+1​\(xt\+1\)−Φμt\+1​\(xt\)\]\+\[Φμt\+1​\(xt\)−Φμt​\(xt\)\]\\displaystyle\[\\Phi\_\{\\mu\_\{t\+1\}\}\(x\_\{t\+1\}\)\-\\Phi\_\{\\mu\_\{t\+1\}\}\(x\_\{t\}\)\]\+\[\\Phi\_\{\\mu\_\{t\+1\}\}\(x\_\{t\}\)\-\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\]≤\\displaystyle\\leq−αt2​‖∇Φμt​\(xt\)‖2−αt4​‖∇^​Φμt​\(xt\)‖2\+C1​αt​Et\+1\+C1′​\(αt​t−4​p\+αt​t2​p−2\+t−3​p−1\)\.\\displaystyle\-\\frac\{\\alpha\_\{t\}\}\{2\}\\\|\\nabla\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|^\{2\}\-\\frac\{\\alpha\_\{t\}\}\{4\}\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|^\{2\}\+C\_\{1\}\\alpha\_\{t\}E\_\{t\+1\}\+C\_\{1\}^\{\\prime\}\\big\(\\alpha\_\{t\}t^\{\-4p\}\+\\alpha\_\{t\}t^\{2p\-2\}\+t^\{\-3p\-1\}\\big\)\.
Part𝒟\\mathcal\{D\}\.Recall Partℬ\\mathcal\{B\}, with positive constantsC2,C2′C\_\{2\},C\_\{2\}^\{\\prime\}, we have:

Et\+1≤34​Et\+C2​t6​p−2​q​‖∇^​Φμt−1​\(xt−1\)‖2\+C2′​t−2​p\.E\_\{t\+1\}\\leq\\frac\{3\}\{4\}E\_\{t\}\+C\_\{2\}t^\{6p\-2q\}\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\-1\}\}\(x\_\{t\-1\}\)\\\|^\{2\}\+C\_\{2\}^\{\\prime\}t^\{\-2p\}\.
We construct the following Lyapunov function:

Vt=Φμt​\(xt\)\+M​αt​Et,V\_\{t\}=\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\+M\\alpha\_\{t\}E\_\{t\},whereM=3​C1M=3C\_\{1\}\. Then, we have:

Vt\+1−Vt\\displaystyle V\_\{t\+1\}\-V\_\{t\}=Φμt\+1​\(xt\+1\)−Φμt​\(xt\)\+M⁡\(αt\+1​Et\+1−αt​Et\)\\displaystyle=\\Phi\_\{\\mu\_\{t\+1\}\}\(x\_\{t\+1\}\)\-\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\+M\(\\alpha\_\{t\+1\}E\_\{t\+1\}\-\\alpha\_\{t\}E\_\{t\}\)≤−αt2​‖∇Φμt​\(xt\)‖2−αt4​‖∇^​Φμt​\(xt\)‖2\+C1′​\(αt​t−4​p\+αt​t2​p−2\+t−3​p−1\)\\displaystyle\\leq\-\\frac\{\\alpha\_\{t\}\}\{2\}\\\|\\nabla\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|^\{2\}\-\\frac\{\\alpha\_\{t\}\}\{4\}\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|^\{2\}\+C\_\{1\}^\{\\prime\}\\big\(\\alpha\_\{t\}t^\{\-4p\}\+\\alpha\_\{t\}t^\{2p\-2\}\+t^\{\-3p\-1\}\\big\)\+\(C1​αt\+M​αt\+1\)​Et\+1−M​αt​Et\\displaystyle\\,\\,\\,\\,\\,\\,\+\(C\_\{1\}\\alpha\_\{t\}\+M\\alpha\_\{t\+1\}\)E\_\{t\+1\}\-M\\alpha\_\{t\}E\_\{t\}≤−αt2​‖∇Φμt​\(xt\)‖2−αt4​‖∇^​Φμt​\(xt\)‖2\+C1′​\(αt​t−4​p\+αt​t2​p−2\+t−3​p−1\)\\displaystyle\\leq\-\\frac\{\\alpha\_\{t\}\}\{2\}\\\|\\nabla\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|^\{2\}\-\\frac\{\\alpha\_\{t\}\}\{4\}\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|^\{2\}\+C\_\{1\}^\{\\prime\}\\big\(\\alpha\_\{t\}t^\{\-4p\}\+\\alpha\_\{t\}t^\{2p\-2\}\+t^\{\-3p\-1\}\\big\)\+\(C1​αt\+M​αt\+1\)​\(34​Et\+C2​t6​p−2​q​‖∇^​Φμt−1​\(xt−1\)‖2\+C2′​t−2​p\)−M​αt​Et\\displaystyle\\,\\,\\,\\,\\,\\,\+\(C\_\{1\}\\alpha\_\{t\}\+M\\alpha\_\{t\+1\}\)\\left\(\\frac\{3\}\{4\}E\_\{t\}\+C\_\{2\}t^\{6p\-2q\}\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\-1\}\}\(x\_\{t\-1\}\)\\\|^\{2\}\+C\_\{2\}^\{\\prime\}t^\{\-2p\}\\right\)\-M\\alpha\_\{t\}E\_\{t\}≤♭−αt2​‖∇Φμt​\(xt\)‖2−αt4​‖∇^​Φμt​\(xt\)‖2\+4​C1​C2​αt​t6​p−2​q⏟ηt​‖∇^​Φμt−1​\(xt−1\)‖2\\displaystyle\\overset\{\\flat\}\{\\leq\}\-\\frac\{\\alpha\_\{t\}\}\{2\}\\\|\\nabla\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|^\{2\}\-\\frac\{\\alpha\_\{t\}\}\{4\}\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|^\{2\}\+\\underbrace\{4C\_\{1\}C\_\{2\}\\alpha\_\{t\}t^\{6p\-2q\}\}\_\{\\eta\_\{t\}\}\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\-1\}\}\(x\_\{t\-1\}\)\\\|^\{2\}\+C1′′​\(t−4​p−q\+t2​p−2−q\+t−2​p−q\+t−3​p−1\)⏟Rt,\\displaystyle\\,\\,\\,\\,\\,\\,\+\\underbrace\{C\_\{1\}^\{\\prime\\prime\}\\big\(t^\{\-4p\-q\}\+t^\{2p\-2\-q\}\+t^\{\-2p\-q\}\+t^\{\-3p\-1\}\\big\)\}\_\{R\_\{t\}\},where♭\\flatis due toM=3​C1M=3C\_\{1\}andαt≥αt\+1\\alpha\_\{t\}\\geq\\alpha\_\{t\+1\}, andC1′′C\_\{1\}^\{\\prime\\prime\}is another constant\. Whenq≥3​pq\\geq 3p, we can select properαt\\alpha\_\{t\}to ensureηt\+1≤18​αt\\eta\_\{t\+1\}\\leq\\frac\{1\}\{8\}\\alpha\_\{t\}, and denoteT0=⌈T2⌉T\_\{0\}=\\lceil\\frac\{T\}\{2\}\\rceil\. Then, we can get:

∑t=T0Tαt2​‖∇Φμt​\(xt\)‖2\\displaystyle\\sum\_\{t=T\_\{0\}\}^\{T\}\\frac\{\\alpha\_\{t\}\}\{2\}\\\|\\nabla\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|^\{2\}≤∑t=T0Tαt2​‖∇Φμt​\(xt\)‖2−∑t=T0Tαt8​‖∇^​Φμt​\(xt\)‖2\+η1​‖∇^​ΦμT0​\(x0\)‖2\\displaystyle\\leq\\sum\_\{t=T\_\{0\}\}^\{T\}\\frac\{\\alpha\_\{t\}\}\{2\}\\\|\\nabla\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|^\{2\}\-\\sum\_\{t=T\_\{0\}\}^\{T\}\\frac\{\\alpha\_\{t\}\}\{8\}\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|^\{2\}\+\\eta\_\{1\}\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{T\_\{0\}\}\}\(x\_\{0\}\)\\\|^\{2\}≤VT0−VT\+1\+η1​‖∇^​ΦμT0​\(x0\)‖2\+∑t=T0TRt\.\\displaystyle\\leq V\_\{T\_\{0\}\}\-V\_\{T\+1\}\+\\eta\_\{1\}\\\|\\widehat\{\\nabla\}\\Phi\_\{\\mu\_\{T\_\{0\}\}\}\(x\_\{0\}\)\\\|^\{2\}\+\\sum\_\{t=T\_\{0\}\}^\{T\}R\_\{t\}\.
Noting thatVT\+1V\_\{T\+1\}is bounded below byinfΦ\\inf\\Phi, the constant terms can be bounded by𝒪⁡\(1\)\\mathcal\{O\}\(1\)\. For the residual sum∑t=T0TRt\\sum\_\{t=T\_\{0\}\}^\{T\}R\_\{t\}, the dominant term is𝒪⁡\(t−q−2​p\)\\mathcal\{O\}\(t^\{\-q\-2p\}\)\. Integrating this term yields∑t=T0TRt=𝒪⁡\(T1−q−2​p\)\\sum\_\{t=T\_\{0\}\}^\{T\}R\_\{t\}=\\mathcal\{O\}\(T^\{1\-q\-2p\}\)\. Dividing both sides by∑t=T0Tαt=Θ⁡\(T1−q\)\\sum\_\{t=T\_\{0\}\}^\{T\}\\alpha\_\{t\}=\\Theta\(T^\{1\-q\}\), we finally get:

min1≤t≤T⁡‖∇Φμt​\(xt\)‖2\\displaystyle\\min\_\{1\\leq t\\leq T\}\\\|\\nabla\\Phi\_\{\\mu\_\{t\}\}\(x\_\{t\}\)\\\|^\{2\}=𝒪⁡\(1\)\+𝒪⁡\(T1−q−2​p\)Θ⁡\(T1−q\)=𝒪⁡\(1T1−q\+1T2​p\)\.\\displaystyle=\\frac\{\\mathcal\{O\}\(1\)\+\\mathcal\{O\}\(T^\{1\-q\-2p\}\)\}\{\\Theta\(T^\{1\-q\}\)\}=\\mathcal\{O\}\\left\(\\frac\{1\}\{T^\{1\-q\}\}\+\\frac\{1\}\{T^\{2p\}\}\\right\)\.When selectingp=1/5p=1/5andq=3/5q=3/5, and notingminT0≤t≤T⁡ϵt=𝒪⁡\(T−45\)\\min\_\{T\_\{0\}\\leq t\\leq T\}\\epsilon\_\{t\}=\\mathcal\{O\}\(T^\{\-\\frac\{4\}\{5\}\}\)the convergence rate isminT0≤t≤T⁡Π⁡\(xt,yt\)=𝒪⁡\(T−25\)\\min\_\{T\_\{0\}\\leq t\\leq T\}\\Pi\(x\_\{t\},y\_\{t\}\)=\\mathcal\{O\}\(T^\{\-\\frac\{2\}\{5\}\}\)\. ∎

Given[Theorem1](https://arxiv.org/html/2609.30501#Thmtheorem1), we can immediately obtain the following result:

###### Corollary 1\.

Whenever the lower\-level local minimum satisfies the local curvature condition∇y​y2​g​\(x,y\)⪰μ0​Iq\\nabla\_\{yy\}^\{2\}g\(x,y\)\\succeq\\mu\_\{0\}I\_\{q\}for someμ0\>0\\mu\_\{0\}\>0, the bias bound yields‖∇Φμ​\(x\)−∇Φ0​\(x\)‖=𝒪⁡\(μ\)\\\|\\nabla\\Phi\_\{\\mu\}\(x\)\-\\nabla\\Phi\_\{0\}\(x\)\\\|=\\mathcal\{O\}\(\\mu\)\. Combining this bound with the parameter selection in[Theorem1](https://arxiv.org/html/2609.30501#Thmtheorem1)gives:

min⌈T/2⌉≤t≤T∥∇Φ0\(xt\)∥2=𝒪\(T−2/5\)\.\\min\_\{\\lceil T/2\\rceil\\leq t\\leq T\}\\\|\\nabla\\Phi\_\{0\}\(x\_\{t\}\)\\\|^\{2\}=\\mathcal\{O\}\(T^\{\-2/5\}\)\.

## Appendix CDetails of Illustrative Example

To intuitively show the rationale of our SOSP\-based relaxed surrogate, we consider the following concrete example withx,y∈ℝx,y\\in\\mathbb\{R\}:

minx∈ℝp,y∈ℝq⁡f⁡\(x,y\)=\(x−2\)2\+y2\\displaystyle\\min\_\{x\\in\\mathbb\{R\}^\{p\},y\\in\\mathbb\{R\}^\{q\}\}f\(x,y\)=\(x\-2\)^\{2\}\+y^\{2\}subject toy∈𝒮⁡\(x\):=arg​miny⁡g​\(x,y\)=14​y4−12​xy2\.\\displaystyle\\,\\,y\\in\\mathcal\{S\}\(x\):=\\argmin\_\{y\}g\(x,y\)=\\frac\{1\}\{4\}y^\{4\}\-\\frac\{1\}\{2\}xy^\{2\}\.As mentioned earlier, to tackle this nonconvex lower\-level BLO problem, existing works instead solve a surrogate lower\-level problem by finding a first\-order stationary point, i\.e\., a point where∇yg​\(x,y\)=0\\nabla\_\{y\}g\(x,y\)=0, or by solving its equivalent formulations under certain other assumptions\([Xiao et al\., 2023](https://arxiv.org/html/2609.30501#bib.bib5);[Shen and Chen, 2023](https://arxiv.org/html/2609.30501#bib.bib6);[Liu et al\., 2024](https://arxiv.org/html/2609.30501#bib.bib8);[Ma et al\., 2026](https://arxiv.org/html/2609.30501#bib.bib7)\)\.

Specifically, the required derivatives are:

∇yg​\(x,y\)=y3−x​y=y⁡\(y2−x\),∇y​y2g​\(x,y\)=3​y2−x\.\\displaystyle\\nabla\_\{y\}g\(x,y\)=y^\{3\}\-xy=y\(y^\{2\}\-x\),\\,\\,\\,\\,\\,\\,\\nabla\_\{yy\}^\{2\}g\(x,y\)=3y^\{2\}\-x\.Setting the gradient to00, we obtain the following FOSP set:

\{\(x,0\),\(x′,x′\),\(x′,−x′\):∀x∈ℝ,x′≥0\}\.\\displaystyle\\\{\(x,0\),\(x^\{\\prime\},\\sqrt\{x^\{\\prime\}\}\),\(x^\{\\prime\},\-\\sqrt\{x^\{\\prime\}\}\):\\forall x\\in\\mathbb\{R\},x^\{\\prime\}\\geq 0\\\}\.When substituting∇yg​\(x,y\)=0\\nabla\_\{y\}g\(x,y\)=0into the upper\-level problem, we obtain the following solutions:\(x∗,y∗\)∈\{\(2,0\),\(1\.5,1\.5\),\(1\.5,−1\.5\)\}\(x^\{\*\},y^\{\*\}\)\\in\\\{\(2,0\),\(1\.5,\\sqrt\{1\.5\}\),\(1\.5,\-\\sqrt\{1\.5\}\)\\\}, where\(2,0\)\(2,0\)is a saddle point ofg⁡\(x,⋅\)g\(x,\\cdot\), and the other two serve as the true solutions\. As shown in[Figure1](https://arxiv.org/html/2609.30501#S1.F1), these aforementioned methods can be entirely drawn toward the saddle point, failing to solve the original BLO problem\. In contrast, our𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~escapes the saddle point and finds the optimal solution\.

## Appendix DScope and Implications of SOSP Guarantees

While we established a finite\-time convergence rate of𝒪⁡\(T−25\)\\mathcal\{O\}\(T^\{\-\\frac\{2\}\{5\}\}\)for𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~in[Section5](https://arxiv.org/html/2609.30501#S5), it remains important to clarify the class of solutions to which the method converges\. In this section, we discuss our SOSP\-based solutions in detail\.

The theoretical guarantee is to achieve some SOSP solution\.Our theoretical results guarantee that𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~reaches alower\-level SOSPand thereby avoids strict saddle points\. However, they donotguarantee the selection of the “best” solution among multiple lower\-level local minima\. Although the objective values of any given collection of local minima can be compared directly, guaranteeing the selection of the best solution among all local minima is equivalent to finding a global minimum of the lower\-level problem, which is computationally intractable for general nonconvex problems \(NP\-hard\)\. Therefore, without additional structural assumptions, the effects of different lower\-level local solutions on the upper\-level problem cannot be characterized in general\.

An SOSP provides a strictly stronger stationarity guarantee than an FOSP\.The lower\-level guarantee that𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~reaches an SOSP doesnotrely on the strict\-saddle property\. Rather, this property is used only to conclude that an SOSP corresponds to a lower\-level local minimum\. Even when strictness does not hold, an SOSP still excludes any stationary point that admits a direction of negative curvature and therefore provides astrictly strongerstationarity guarantee than an FOSP\. This advantage is also well documented in the literature\([Dauphin et al\., 2014](https://arxiv.org/html/2609.30501#bib.bib28);[Allen\-Zhu and Li, 2018](https://arxiv.org/html/2609.30501#bib.bib42)\)\. This distinction is particularly important in BLO: as shown in[Figure1](https://arxiv.org/html/2609.30501#S1.F1), FOSP\-based methods can become trapped at lower\-level saddle points and consequently converge to incorrect upper\-level solutions, whereas𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~escapes these saddle points and finds the correct solution\.

Empirical evidence shows the prevalence of strict saddles in practice\.We conducted an experiment using the same LLM\-based setting as in[AppendixA](https://arxiv.org/html/2609.30501#A1)\. Specifically, we identified all the saddle points encountered along each trajectory and computed the minimum eigenvalue of the lower\-level Hessian at each of them\. As shown in[Table2](https://arxiv.org/html/2609.30501#A4.T2), across five repeated trials, all6161encountered saddle points exhibited a negative minimum eigenvalue, providing empirical evidence that the saddles encountered in these runs are strict\. This implies that most saddle points are strict in practice, demonstrating the applicability of our theories\.

Table 2:Numerical classification of the perturbation\-triggered lower\-level stationary\-point candidates encountered along five𝖯𝖱𝖮𝖡𝖤\\mathsf\{PROBE\}~trajectories\.Undeterminedrefers to candidates that could not be classified conclusively because of numerical instability\.