Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis

## Abstract

Abstract Bilevel optimization has recently attracted considerable attention due to its abundant applications in machine learning problems. However, existing methods rely on prior knowledge of problem parameters to determine stepsizes, resulting in significant effort in tuning stepsizes when these parameters are unknown. In this paper, we propose two novel tuning-free algorithms, D-TFBO and S-TFBO. D-TFBO employs a double-loop structure with stepsizes adaptively adjusted by the "inverse of cumulative gradient norms" strategy. S-TFBO features a simpler fully single-loop structure that updates three variables simultaneously with a theory-motivated joint design of adaptive stepsizes for all variables. We provide a comprehensive convergence analysis for both algorithms and show that D-TFBO and S-TFBO respectively require 𝒪 ​ ( 1 ϵ ) 𝒪 1 italic-ϵ \mathcal{O}(\frac{1}{\epsilon}) and 𝒪 ​ ( 1 ϵ ​ log 4 ⁡ ( 1 ϵ ) ) 𝒪 1 italic-ϵ superscript 4 1 italic-ϵ \mathcal{O}(\frac{1}{\epsilon}\log^{4}(\frac{1}{\epsilon})) iterations to find an ϵ italic-ϵ \epsilon -accurate stationary point, (nearly) matching their well-tuned counterparts using the information of problem parameters. Experiments on various problems show that our methods achieve performance comparable to existing well-tuned approaches, while being more robust to the selection of initial stepsizes.
To the best of our knowledge, our methods are the first to completely eliminate the need for stepsize tuning, while achieving theoretical guarantees.

## 1 Introduction

Bilevel optimization has gained considerable attention recently due to its widespread use in various machine learning applications, such as meta-learning [, , ], hyperparameter optimization [, ], reinforcement learning [, ], robotics [], communication [] and federated learning [].
In this paper, we study a standard bilevel optimization problem that takes the following mathematical formulation:

$$ $\displaystyle\min_{x\in\mathbb{R}^{d_{x}}}\Phi(x):=f\big{(}x,y^{*}(x)\big{)}$ $\displaystyle\;\;\mbox{s.t.}\;y^{*}(x)=\arg\min_{y\in\mathbb{R}^{d_{y}}}g(x,y),$ (1) $$

where $f$ and $g$ are jointly continuously differentiable outer (upper-level) and inner (lower-level) functions.
In this paper, we focus on the nonconvex-strongly-convex setting, where the lower-level function $g$ is strongly convex w.r.t. $y$ and the outer function $\Phi(x)$ is possibly nonconvex.

Recent years have witnessed the rapid development of bilevel optimization algorithms, which can be categorized into approximate implicit differentiation (AID) [, ] based, iterative differentiation (ITD) [, ] based, and value-function based [, ] approaches.
However, these methods often require substantial effort to tune a couple of hyperparameters like stepsizes, which typically depend on unknown problem parameters (such as Lipschitzness parameters, strong convexity parameters, and optimal function values). This emphasizes the importance of adaptive and tuning-free methods in bilevel optimization.
In this paper, an algorithm is considered tuning-free if it does not need to know the problem parameters in advance but can still achieve almost the same convergence rate guarantee as its well-tuned counterpart using this information.
Despite several recent efforts to reduce dependence on problem-specific parameters [, ], developing a fully tuning-free bilevel optimization algorithm remains an open challenge. For instance, [] utilizes Polyak’s stepsizes to automate both inner and outer updates but still requires information such as gradient Lipschitzness parameters and optimal lower-level function values. Similarly, [] introduces an "on-the-fly" accumulation strategy for (hyper)gradient norms, which removes the reliance on inner and outer gradient Lipschitzness parameters but still depends on the strong convexity parameter for the inner AdaNGD-type updates.

This paper aims to close this gap by introducing two novel fully tuning-free bilevel optimization algorithms named D-TFBO and S-TFBO (where D and S represent double- and single-loop approaches), along with a comprehensive convergence analysis demonstrating their competitive performance compared to existing well-tuned approaches (which tune their hyperparameters like stepsizes based on the problem parameters). Our key contributions are outlined below.

- $\bullet$
Our algorithms are inspired by the "inverse of cumulative gradient norms" strategy introduced by [, ], adapting the stepsizes based on accumulated (hyper)gradient norms. D-TFBO utilizes two optimization sub-loops: one for solving the inner problem and another for addressing a linear system (LS), which approximates the Hessian-inverse-vector product of each hypergradient.
Unlike previous approaches, D-TFBO introduces cold-start adaptive stepsizes that accumulate gradients exclusively within the sub-loops. This method establishes a tighter lower bound on stepsizes, improving gradient complexity. In contrast, S-TFBO adopts a single-loop structure, where all variables are updated simultaneously in each iteration. Rather than applying the "inverse of cumulative gradient norms" uniformly to all updates, our error analysis motivates a joint design of adaptive stepsizes for $y$, $v$, and $x$, which correspond to solving the inner problem, LS, and outer problem, respectively. For instance, the stepsize for $v$ is coupled with that for $y$, while the stepsize for $x$ depends on both $y$ and $v$.
- $\bullet$
Compared to the well-tuned AID methods in [], our D-TFBO method achieves the same $\mathcal{O}(\frac{1}{T})$ convergence rate. Similarly, our S-TFBO method attains an $\widetilde{\mathcal{O}}(\frac{1}{T})$ convergence rate, matching that of well-tuned counterparts, up to polylogarithmic factors.
The complexity analysis shows that D-TFBO and S-TFBO require $\mathcal{O}(\frac{1}{\epsilon^{2}})$ and $\widetilde{\mathcal{O}}(\frac{1}{\epsilon})$ gradient computations, respectively, to reach an $\epsilon$-accurate stationary point. This comparison differs from the observation in well-tuned bilevel optimization, where double-loop approaches generally achieve lower gradient complexity than single-loop methods []. This is because the inner tuning-free solver requires $\mathcal{O}(\frac{1}{\epsilon})$ more iterations than well-tuned methods to achieve $\epsilon$-level accuracy.
- $\bullet$
The theoretical analysis is inspired by the two-stage framework in [, ], where the stages describe the relationship between the stepsizes and certain constants that depend on the problem parameters.
However, exploring this technical framework in bilevel problems is far more challenging because the stages for analyzing each stepsize interact with those for other stepsizes, resulting in intertwined multi-stage dynamics across different variables. For instance, the error analysis for the updates on $v$ must account for the accumulated gradient norms from the updates on $y$. This motivates us to couple the stepsize for $v$ with the adaptive stepsize for $y$ to prevent the propagation of accumulated errors. In addition, our analysis requires establishing precise upper and lower bounds for all stepsizes to ensure convergence results that match those achieved under well-tuned stepsizes.
- $\bullet$
We validate the effectiveness of our methods through experiments on regularization selection, data hyper-cleaning, and coreset selection for continual learning. The results show that our methods perform comparably to existing well-tuned methods. More importantly, our methods demonstrate greater robustness to different initial stepsizes, due to the tuning-free design.

## 2 Related Work

Bilevel Optimization.
Bilevel optimization, initially introduced by [], has been extensively studied for decades. Early works [, ] approached the bilevel problem from a constrained optimization perspective. More recently, gradient-based methods have gained significant attention for their efficiency and effectiveness. Among these, Approximate Implicit Differentiation (AID) methods [, , , ] leverage the implicit derivation of the hypergradient by approximating it through the solution of a linear system.
In contrast, Iterative Differentiation (ITD) methods [, ] estimate the hypergradient using automatic differentiation, employing either forward or reverse mode. Recently, a range of stochastic bilevel methods have been developed and analyzed, using techniques such as Neumann series [, ], recursive momentum [, ], and variance reduction [].
Another class of methods formulates the lower-level problem as a value-function-based constraint [, ], enabling the solution of bilevel problems without the need for second-order gradients. A more detailed discussion of related work can be found in the Appendix.

Adaptive and Tuning-free Algorithms.
Adaptive gradient descent has achieved remarkable success and is widely studied and applied in modern machine learning. Early adaptive algorithms trace back to line search methods, such as backtracking [], and Polyak’s stepsize [], both of which have inspired numerous recent variants [, , , , , , ]. To reduce the computational cost of line search and avoid the reliance on an unknown optimal function value, the Barzilai-Borwein stepsize [, , ] was introduced, drawing inspiration from quasi-Newton schemes.
Normalized gradient descent [, , ] preserves the direction of the gradient while ignoring its magnitude, removing the need for prior knowledge about the function. [] and [] pioneered AdaGrad, an adaptive gradient-based method, which proved efficient in solving online convex optimization problems. AdaGrad rapidly evolved for deep learning applications, giving rise to numerous methods, including popular variants like Adam [, , , ], RMSprop [], and Adadelta [].
Specifically, normalized versions of AdaGrad, such as AdaNGDk [], AcceleGrad [], and AdaGrad-Norm [, ], introduced adaptive stepsizes that require no problem-specific parameters, making them tuning-free approaches. Recent work by [] further established lower bounds for minimizing the deterministic gradient $l_{1}$-norm. Additional methods, such as Lipschitzness parameter approximation [] and restart techniques [], have also been explored.
A more comprehensive discussion refers to [].

Adaptive and Tuning-free Bilevel Algorithms.
Instead of focusing on single-level problems, [] extended Adam to bilevel optimization algorithms. [] introduced adaptive stepsizes for bilevel problems, based on Polyak’s stepsize and line search techniques. Most recently, [] proposed a novel framework that applies adaptive normalized gradient descent to the strongly convex inner problem and AdaGrad-Norm to the nonconvex outer problem, allowing the algorithm to update adaptively with fewer problem-specific parameters.

## 3 Algorithm

### 3.1 Standard Bilevel Optimization

A key challenge in bilevel optimization is calculating the hypergradient $\nabla\Phi(x)$, which, according to the implicit function theorem, is given by:

$$ $\displaystyle\nabla\Phi(x)=\nabla_{x}f\big{(}x,y^{*}(x)\big{)}-\nabla_{x}\nabla_{y}g\big{(}x,y^{*}(x)\big{)}\big{[}\nabla_{y}\nabla_{y}g\big{(}x,y^{*}(x)\big{)}\big{]}^{-1}\nabla_{y}f\big{(}x,y^{*}(x)\big{)},$ $$

when $g$ is twice differentiable, $\nabla_{y}g$ is
continuously differentiable and the Hessian $\nabla_{y}\nabla_{y}g\big{(}x,y^{*}(x)\big{)}$ is invertible.
In practice, $y^{*}(x)$ is not directly accessible, and one often use an iterative algorithm to obtain an estimate $\hat{y}$ instead.
Since computing the Hessian inverse is prohibitively expensive, a more efficient way is to approximate the Hessian-inverse-vector product in the above hypergradient $\nabla\Phi(x)$ by solving the following linear system:

$$ $\displaystyle\min_{v}R(x,\hat{y},v)=\frac{1}{2}v^{T}\nabla_{y}\nabla_{y}g(x,\hat{y})v-v^{T}\nabla_{y}f(x,\hat{y}).$ (2) $$

Similarly, an iterative algorithm is usually deployed to obtain an approximate solution $\hat{v}$ of the problem in [eq. 2](#S3.E2).
Given the approximates $\hat{y}$ and $\hat{v}$, the variable $x$ is then updated with a hypergradient estimate given by

$$ $\displaystyle\bar{\nabla}f(x,\hat{y},\hat{v})=\nabla_{x}f(x,\hat{y})-\nabla_{x}\nabla_{y}g(x,\hat{y})\hat{v}.$ (3) $$

Standard bilevel optimization approaches select the stepsizes for updating $y$, $v$, and $x$ based on problem-specific parameters, such as Lipschitzness and strong convexity parameters [, , ]. However, these parameters are often difficult to obtain or approximate in practice, leading to significant tuning efforts. This challenge motivates the development of adaptive bilevel optimization algorithms that require less to no tuning.

### 3.2 Existing Adaptive Bilevel Optimization Methods

Among the existing adaptive bilevel methods, the most closely related to this work are [] and []. [] utilizes Polyak’s stepsizes and a line search to automate the stepsizes for both inner and outer updates. [] applies AdaNGD [] to solve the inner problem and updates $x$ using the inverse of cumulative hypergradient norms, where the hypergradient norms are approximated via gradient mapping [] with Fenchel coupling [].

However, these methods are not entirely tuning-free. For instance, the initialization of Polyak’s stepsizes in [] depends on Lipschitzness parameters, strong convexity parameters, and the optimal lower-level function values. While the line search approach in [] bypasses the need for problem-specific parameters, it lacks theoretical convergence guarantees. Similarly, [] requires the strong convexity parameter for the inner AdaNGD updates.

Figure: Algorithm 1 Double-loop Tuning-Free Bilevel Optimizer (D-TFBO)

### 3.3 Double-Loop Tuning-Free Bilevel Optimization- D-TFBO

As shown in [Algorithm 1](#alg1), our D-TFBO method follows a double-loop structure, where two sub-loops of iterations are used to solve the lower-level and linear system problems. In the first sub-loop,
we employ the idea of "inverse of cumulative gradient norm" to design the adaptive updates as

$$ $\displaystyle y_{t}^{p+1}\leftarrow y_{t}^{p}-\frac{1}{\beta_{p+1}}\nabla_{y}g(x_{t},y_{t}^{p}),\quad\text{with}\ \ \beta_{p+1}^{2}=\beta_{p}^{2}+\|\nabla_{y}g(x_{t},y_{t}^{p})\|^{2}.$ $$

It can be seen from [Algorithm 1](#alg1) that our D-TFBO algorithm employs a stopping criterion based on the gradient norm: $\|\nabla_{y}g(x_{t},y_{t}^{p})\|^{2}\leq\epsilon_{y}$, where $\epsilon_{y}$ (defaulted to $1/T$ for convergence analysis) is independent of problem parameters. The rationale behind this design is that if the stopping criterion is not met (i.e., $\|\nabla_{y}g(x_{t},y_{t}^{p})\|^{2}>\epsilon_{y}$), the accumulation $\beta_{p}$ of gradient norms continues to increase. This increase causes the stepsize $\frac{1}{\beta_{p}}$ to decrease to a value at which a descent in the optimality gap is guaranteed. A similar stopping criterion applies to the updates of $v_{t}^{q}$ when solving the linear system.

Notably, both sub-loops utilize warm-start variable values but reset the stepsizes at each iteration (cold-start stepsizes). The warm-start variables ensure that the initial point is reasonably close to the optimal solution, while the cold-start scheme guarantees stepsizes to achieve stronger lower bounds. Finally, the update of $x_{t}$ is based on the accumulation of hypergradient estimates $\bar{\nabla}f(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}})$.

###### Remark 1 (Extension to a tunable version with problem-parameter-free tuning coefficients.) .

Although [Algorithm 1](#alg1) is designed as a tuning-free method, a tunable version with the flexibility to preset hyperparameters can still achieve the same convergence rate and gradient complexity.
The stepsizes for $\{x,y,v\}$ can be set as $\{\eta_{x}/\alpha_{t},\eta_{y}/\beta_{p},\eta_{v}/\gamma_{q}\}$ and the sub-loops stopping criteria can be set to $\{c_{y}/T,c_{v}/T\}$, where $\{\eta_{x},\eta_{y},\eta_{v},c_{y},c_{v}\}$ are configurable hyperparameters that are independent of the problem parameters such as strong-convexity and Lipschitzness parameters.

Figure: Algorithm 2 Single-loop Tuning-Free Bilevel Optimizer (S-TFBO)

###### Remark 1 (Extension to a tunable version with problem-parameter-free tuning coefficients.) .

### 3.4 Single-Loop Tuning-Free Bilevel Optimization- S-TFBO

The two sub-loops in D-TFBO may complicate the implementation, and increase the number of iterations to meet the stopping criterion.
In this section, we propose a much simpler fully single-loop tuning-free bilevel optimization method named S-TFBO, as described in [Algorithm 2](#alg2).

The design of stepsizes in [Algorithm 2](#alg2) follows a similar idea in [Algorithm 1](#alg1).
In each iteration $t$,
we update $\alpha_{t}$, $\beta_{t}$, $\gamma_{t}$ as accumulations of gradient norms of $\bar{\nabla}f$, $\nabla_{y}g$, and $\nabla_{v}R$ from the previous $t-1$ iterations.
We then update variables $y_{t}$, $v_{t}$ and $x_{t}$ simultaneously with adaptive stepsizes $\big{\{}\frac{1}{\beta_{t}},\frac{1}{\max\{\beta_{t},\gamma_{t}\}},\frac{1}{\alpha_{t}{\max\{\beta_{t},\gamma_{t}\}}}\big{\}}$.
However, the stepsizes for $v$ and $x$ are not straightforward and require careful designs guided by our theoretical analysis, as elaborated below.

Design of stepsize for $\bm{v_{t}}$.
Instead of simply using $\frac{1}{\gamma_{t}}$, we introduce $\frac{1}{\varphi_{t}}:=\frac{1}{\max\{\beta_{t},\gamma_{t}\}}$ as the stepsize.
This adjustment is necessary because $\nabla_{v}R(x_{t},y_{t},v_{t})$ involves the approximation error $\|y_{t}-y^{*}(x_{t})\|^{2}$.
Since this error is proportional to $\|\nabla_{y}g(x_{t},y_{t})\|^{2}$, using $\frac{1}{\beta_{t}}$ helps control this error and prevents it from exploding after accumulation, as validated in our theoretical analysis later.

Design of stepsize for $\bm{x_{t}}$.
Similarly, we use $\frac{1}{\alpha_{t}\varphi_{t}}$ as the stepsize for updating $x_{t}$, where the coupled factor
$\frac{1}{\varphi_{t}}$ is introduced to mitigate the approximation errors from the $y_{t}$ and $v_{t}$ updates, leading to a more stable convergence.

###### Remark 2 (Extension to a tunable version with problem-parameter-free tuning coefficients.) .

Similarly to [Remark 1](#Thmremark1), [Algorithm 2](#alg2) can extend to a tunable version with the same convergence rate and gradient complexity.
The stepsizes for $\{x,y,v\}$ can be set as $\{\eta_{x}/\alpha_{t}\varphi_{t},\eta_{y}/\beta_{t},\eta_{v}/\varphi_{t}\}$, where $\{\eta_{x},\eta_{y},\eta_{v}\}$ are configurable hyperparameters that are independent of the problem parameters.

###### Remark 2 (Extension to a tunable version with problem-parameter-free tuning coefficients.) .

## 4 Theoretical Analysis

### 4.1 Technical Challenges

Compared to existing single-level tuning-free approaches, fully tuning-free bilevel optimization poses unique challenges that have not been addressed well.

- •
Compared to single-level problems, bilevel problems involve interdependent variable updates, resulting in more complex and interconnected stepsize designs.
- •
The stages for analyzing each stepsize interact with those of other stepsizes, leading to intertwined multi-stage dynamics across various variables.
- •
The optimization error of each variable can accumulate (hyper)gradient norms from previous iterations due to the adaptive stepsize designs, complicating the error analysis.

In [Section 4.2](#S4.SS2), we introduce the standard definitions and assumptions. Next, in [Section 4.3](#S4.SS3) and [4.4](#S4.SS4), we provide a detailed convergence analysis, explaining how we address the above challenges.

### 4.2 Assumptions and Definitions

We make the following definitions and assumptions for outer- and inner-objective functions, as also adopted by [, , ].

###### Definition 1 .

A mapping $f$ is $L$-Lipschitz continuous if $\|f(x_{1})-f(x_{2})\|\leq L\|x_{1}-x_{2}\|$ for $\forall x_{1},x_{2}$.

Since the outer objective function $\Phi(x)$ is non-convex, we aim to find an $\epsilon$-accurate stationary point, as defined below.

###### Definition 2 .

An output $\bar{x}$ of an algorithm is the $\epsilon$-accurate stationary point of the objective function $\Phi(x)$ if $\|\nabla\Phi(\bar{x})\|^{2}\leq\epsilon$, where $\epsilon\in(0,1)$.

###### Assumption 1 .

Functions $f(x,y)$ and $g(x,y)$ are twice continuously differentiable and $g(x,y)$ is $\mu$ strongly convex w.r.t. $y$, for $x\in\mathbb{R}^{d_{x}}$, $y\in\mathbb{R}^{d_{y}}$.

The following assumption imposes the Lipschitz continuity on the outer and inner functions and their derivatives.

###### Assumption 2 .

Function $f(x,y)$ is $L_{f,0}$-Lipschitz continuous; the gradients $\nabla f(x,y)$ and $\nabla g(x,y)$ are $L_{f,1}$ and $L_{g,1}$-Lipschitz continuous, respectively; the second-order gradients $\nabla_{x}\nabla_{y}g(x,y)$ and $\nabla_{y}\nabla_{y}g(x,y)$ are $L_{g,2}$-Lipschitz continuous.

Rather than directly using the Lipschitz continuity parameters as bounds on gradients-which can cause dimensional inconsistencies during logarithmic operations-we offer the following remark:

###### Remark 3 .

Assumption [2](#Thmassumption2) indicates that there exist constants $C_{f_{x}}$, $C_{f_{y}}$, $C_{g_{xy}}$ and $C_{g_{yy}}$ such that
$\|\nabla_{x}f(x,y)\|\leq C_{f_{x}}$,
$\|\nabla_{y}f(x,y)\|\leq C_{f_{y}}$, $\|\nabla_{x}\nabla_{y}g(x,y)\|\leq C_{g_{xy}}$ and $\|\nabla_{y}\nabla_{y}g(x,y)\|\leq C_{g_{yy}}$.

###### Assumption 3 .

There exists $m\in\mathbb{R}$ such that $\inf_{x}\Phi(x)\geq m$.

Next, we present the main convergence theorems for [Algorithm 1](#alg1) and [Algorithm 2](#alg2), along with key propositions that provide insights into these theorems. A proof sketch is provided in [Appendix C](#A3).

###### Definition 1 .

###### Definition 2 .

###### Assumption 1 .

###### Assumption 2 .

###### Remark 3 .

###### Assumption 3 .

### 4.3 Convergence and Complexity Analysis for Algorithm 1

Firstly, we explain the two-stage framework used in our analysis.

###### Proposition 1 .

Suppose the iteration rounds to update $\{x,y,v\}$ are $\{T_{1},T_{2},T_{3}\}$ and $\{\alpha_{t},\beta_{t},\gamma_{t}\}$ are generated by [Algorithm 1](#alg1) or [2](#alg2). For any $C_{\alpha}\geq\alpha_{0}$, $C_{\beta}\geq\beta_{0}$, $C_{\gamma}\geq\gamma_{0}$, we have

- (a)
either $\alpha_{t}\leq C_{\alpha}$ for any $t\leq T_{1}$, or $\exists k_{1}\leq T_{1}$ such that $\alpha_{k_{1}}\leq C_{\alpha}$, $\alpha_{k_{1}+1}>C_{\alpha}$;
- (b)
either $\beta_{t}\leq C_{\beta}$ for any $t\leq T_{2}$, or $\exists k_{2}\leq T_{2}$ such that $\beta_{k_{2}}\leq C_{\beta}$, $\beta_{k_{2}+1}>C_{\beta}$;
- (c)
either $\gamma_{t}\leq C_{\gamma}$ for any $t\leq T_{3}$, or $\exists k_{3}\leq T_{3}$ such that $\gamma_{k_{3}}\leq C_{\gamma}$, $\gamma_{k_{3}+1}>C_{\gamma}$.

The analysis for each stepsize is divided into two cases. Let us take (a) as an illustration example.
Case 1: the accumulation $\alpha_{t}$ of gradient norms is bounded by a constant $C_{\alpha}$ before the end of the iteration. In this case, the average gradient norm square can be bound as $\frac{C_{\alpha}^{2}}{T_{1}}$, which decreases with $T_{1}$.
Case 2: the accumulation $\alpha_{T_{1}}$ exceeds $C_{\alpha}$, and hence $\alpha_{t}$ experiences two stages: in stage 1, $\alpha_{t}\leq C_{\alpha}$, and in stage 2, $\alpha_{t}>C_{\alpha}$. The error analysis for stage 1 is similar to that of case 1. In stage 2, the stepsizes are small enough to show the gradient norm decreases via a descent lemma.

###### Proposition 2 .

Recall that for $t_{th}$ iteration, the sub-loops in [Algorithm 1](#alg1) aim to find $y_{t}^{P_{t}}$ and $v_{t}^{Q_{t}}$ such that $\|\nabla_{y}g(x_{t},y_{t}^{P_{t}})\|^{2}\leq\epsilon_{y}$ and $\|\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}})\|^{2}\leq\epsilon_{v}$.
Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2), we have

$$ $\left\{\begin{aligned} &P_{t}\leq\frac{\log(C_{\beta}^{2}/\beta_{0}^{2})}{\log(1+\epsilon_{y}/C_{\beta}^{2})}+\frac{\beta_{\text{max}}}{\mu}\log\big{(}\frac{L_{g,1}^{2}(\beta_{\text{max}}-C_{\beta})}{\epsilon_{y}}\big{)},\\ &Q_{t}\leq\frac{\log(C_{\gamma}^{2}/\gamma_{0}^{2})}{\log(1+\epsilon_{v}/C_{\gamma}^{2})}+\frac{\gamma_{\text{max}}}{\mu}\log\big{(}\frac{C_{g_{yy}}^{2}(\gamma_{\text{max}}-C_{\gamma})}{\epsilon_{v}}\big{)},\end{aligned}\right.$ $$

where $\{C_{\beta},C_{\gamma}\}$, $\beta_{\text{max}}$, $\gamma_{\text{max}}$ are denied in [eq. 5](#A5.E5), [eq. 22](#A5.E22), [eq. 29](#A5.E29) in the Appendix, respectively.

[Proposition 2](#Thmproposition2) provides upper bounds on $P_{t}$ and $Q_{t}$, which correspond to the total numbers of iterations of the two sub-loops. This result is the same as that of the standard AdaGrad-Norm in the strongly convex setting [].
For the sub-loop for $y$,
in Case 1 above, the loop terminates within ${\log(C_{\beta}^{2}/\beta_{0}^{2})}/{\log(1+\epsilon_{y}/C_{\beta}^{2})}$ steps; and in Case 2, it takes at most
${\log(C_{\beta}^{2}/\beta_{0}^{2})}/{\log(1+\epsilon_{y}/C_{\beta}^{2})}$ steps for stage 1 and it takes at most $\frac{\beta_{\text{max}}}{\mu}\log({L_{g,1}^{2}(\beta_{\text{max}}-C_{\beta})}/{\epsilon_{y}})$ steps for stage 2.
For $\epsilon_{y}$ small enough, it can be seen that $P_{t}$ takes an order of $1/\epsilon_{y}$, which is typically larger than those obtained with well-tuned stepsizes.
Based on this proposition, we can derive the following convergence results.

###### Theorem 1 .

Suppose Assumptions [1](#Thmassumption1),[2](#Thmassumption2),[3](#Thmassumption3) are satisfied.
By setting $\epsilon_{y}=1/T$ and $\epsilon_{v}=1/T$,
the iterates generated by [Algorithm 1](#alg1) satisfy

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla\Phi(x_{t})\|^{2}\leq\frac{c_{1}(C_{\alpha}+2c_{1})}{T}=\mathcal{O}\Big{(}\frac{1}{T}\Big{)},$ $$

where $C_{\alpha}$ and $c_{1}$ are constants defined in [eq. 5](#A5.E5) and [eq. 37](#A5.E37), respectively.

###### Corollary 1 .

Under the same setting [Theorem 1](#Thmtheorem1), to achieve an $\epsilon$-accurate stationary point, [Algorithm 1](#alg1) needs $T=\mathcal{O}(1/\epsilon)$, $\{P_{t},Q_{t}\}=\mathcal{O}(1/\epsilon)$,
and the gradient complexity (i.e., the number of gradient evaluations) is ${\rm Gc}(\epsilon)=\mathcal{O}(1/\epsilon^{2})$.

[Theorem 1](#Thmtheorem1) shows that the convergence rate of [Algorithm 1](#alg1) matches that of the standard double-loop bilevel algorithms [, ].
According to [Proposition 2](#Thmproposition2), the sub-loops for updating $y$ and $v$ require $\mathcal{O}(1/\epsilon_{y})$ iterations to ensure an $\epsilon_{y}$-level approximation accuracy, which is worse than the $\mathcal{O}(1)$ results achieved by well-tuned bilevel optimization methods. This is because more iterations are needed to ensure high accuracy in both sub-loops, due to the lack of information about the Lipschitzness parameters and strong convexity parameters. Consequently, the gradient complexity of our D-TFBO method is worse than those of well-tuned double-loop methods by an order of $1/\epsilon$.

###### Proposition 1 .

###### Proposition 2 .

###### Theorem 1 .

###### Corollary 1 .

### 4.4 Convergence and Complexity Analysis for Algorithm 2

Differently from D-TFBO that uses sub-loops to achieve high-accurate $y$ and $v$ iterates, the main challenge for analyzing S-TFBO lies in dealing with the accumulated approximations errors for updating all variables over iterations. In the following propositions, we will show how we upper-bound such cumulative approximation errors and lower-bound the adaptive stepsizes.

First, we present a descent result for the objective function $\Phi(\cdot)$.

###### Proposition 3 .

Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2), for Algorithm [2](#alg2), suppose the total iteration number is $T$.
No matter $k_{1}$ in [Proposition 1](#Thmproposition1) exists or not, we always have

$$ $\displaystyle\Phi(x_{t+1})-\Phi(x_{t})\leq$ $\displaystyle-\frac{1}{2\alpha_{t+1}\varphi_{t+1}}\|\nabla\Phi(x_{t})\|^{2}-\frac{1}{2\alpha_{t+1}\varphi_{t+1}}\Big{(}1-\frac{L_{\Phi}}{\alpha_{t+1}\varphi_{t+1}}\Big{)}\|\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2}$ $\displaystyle+\frac{\bar{L}^{2}}{2\mu^{2}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\frac{\big{\|}\nabla_{y}g(x_{t},y_{t})\big{\|}^{2}}{\alpha_{t+1}\varphi_{t+1}}+\frac{\bar{L}^{2}}{\mu^{2}}\frac{\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\alpha_{t+1}\varphi_{t+1}}.$ $$

If in addition, $k_{1}$ in [Proposition 1](#Thmproposition1) exists, then for $t\geq k_{1}$, we further have

$$ $\displaystyle\Phi(x_{t+1})-\Phi(x_{t})\leq$ $\displaystyle-\frac{1}{2\alpha_{t+1}\varphi_{t+1}}\|\nabla\Phi(x_{t})\|^{2}-\frac{1}{4\alpha_{t+1}\varphi_{t+1}}\|\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2}$ $\displaystyle+\frac{\bar{L}^{2}}{2\mu^{2}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\frac{\big{\|}\nabla_{y}g(x_{t},y_{t})\big{\|}^{2}}{\alpha_{t+1}\varphi_{t+1}}+\frac{\bar{L}^{2}}{\mu^{2}}\frac{\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\alpha_{t+1}\varphi_{t+1}},$ $$

where $\bar{L}:=\max\big{\{}2({C_{f_{y}}^{2}L_{g,2}^{2}}/{\mu^{2}}+L_{f,1}^{2})^{\frac{1}{2}},\sqrt{2}C_{g_{yy}}\big{\}}$.

It can be seen from [Proposition 1](#Thmproposition1) that
we derive two distinct forms of descent results for the objective function based on the relationship between $\alpha_{t+1}$ and $C_{\alpha}$ (whose form is specified in [section F.1](#A6.Ex73) in the appendix). Their key difference is that the second inequality is tighter for the case $t\geq k_{1}$ by eliminating a term of $\frac{L_{\Phi}}{2\alpha_{t+1}^{2}\varphi_{t+1}^{2}}\|\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2}$.
Both upper bounds consist of two parts: (i) the approximation errors $\mathcal{O}(\|\nabla_{y}g(x_{t},y_{t})\|^{2}+\|\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2})/(\alpha_{t+1}\varphi_{t+1})$ induced by the updates on $y$ and $v$; (ii) the descent term $-\|\nabla\Phi(x_{t})\|^{2}/(\alpha_{t+1}\varphi_{t+1})$. It can be seen that there exists a trade-off:
a smaller $\alpha_{t}\varphi_{t}$ leads to a more notable descent, but larger approximation errors. However, due to the lack of information about the problem parameters, the value of $\alpha_{t}\varphi_{t}$ remains unknown, making it infeasible to determine the optimal trade-off. Instead, we adjust this trade-off based on an overall bound on the descent and approximation errors, derived by telescoping all descent inequalities.

Next, we investigate the upper bounds on the summations of the positive error terms in [Proposition 3](#Thmproposition3).

###### Proposition 4 .

Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2), for any $0\leq k_{0}<t$, for the positive error terms in [Proposition 3](#Thmproposition3), we have the upper bounds in terms of logarithmic functions as

$$ $\displaystyle\sum_{k=k_{0}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}\leq a_{2}\log(t+1)+b_{2},\ \ \sum_{k=k_{0}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}\leq a_{3}\log(t+1)+b_{3},$ $$

where $a_{2}$, $b_{2}$, $a_{3}$, $b_{3}$ are defined in [lemma 16](#A6.Ex269) in the Appendix.

###### Proposition 5 .

Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2), [3](#Thmassumption3), suppose the total iteration rounds is $T$. For any case in [Proposition 1](#Thmproposition1), we have the upper-bound of $\varphi_{t}$ and $\alpha_{t}$ in [Algorithm 2](#alg2) as

$$ $\displaystyle\varphi_{t}\leq a_{1}\log(t)+b_{1},\ \ \alpha_{t}\leq$ $\displaystyle C_{\alpha}+\big{(}a_{4}\log(t)+b_{4}+{4}(\Phi(x_{0})-\inf_{x}\Phi(x))\big{)}\varphi_{t},$ $$

where $a_{1}$, $b_{1}$ are defined in [eq. 65](#A6.E65) and $a_{4}$, $b_{4}$ are defined in [lemma 17](#A6.Ex296) in the Appendix.

[Proposition 4](#Thmproposition4) provides the upper bounds on the accumulated positive error terms in [Proposition 3](#Thmproposition3), and [Proposition 5](#Thmproposition5) shows that the cumulative gradient norms for all variables increase only logarithmically.
By rearranging the terms
and taking the average, we have the upper bound for the average squared hypergradient norm $\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla\Phi(x_{t})\|^{2}$, establishing the final convergence rate of [Algorithm 2](#alg2), as shown in the following theorem and corollary.

###### Theorem 2 .

Suppose Assumptions [1](#Thmassumption1),[2](#Thmassumption2),[3](#Thmassumption3) are satisfied. The iterates generated by [Algorithm 2](#alg2) satisfy

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T}$ $\displaystyle\|\nabla\Phi(x_{t})\|^{2}\leq\frac{1}{2T}\Big{[}\Big{(}a_{4}\log(T)+b_{4}+4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}\Big{)}^{2}\big{(}a_{1}\log(T)+b_{1}\big{)}^{2}$ $\displaystyle\quad\quad+C_{\alpha}\Big{(}a_{4}\log(T)+b_{4}+4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}\Big{)}\big{(}a_{1}\log(T)+b_{1}\big{)}\Big{]}=\mathcal{O}\Big{(}\frac{\log^{4}(T)}{T}\Big{)},$ $$

where $\{C_{\alpha}$, $a_{1}$, $b_{1}$, $a_{4}$, $b_{4}\}=\mathcal{O}(1)$ are defined in [section F.1](#A6.Ex73), [eq. 65](#A6.E65), [lemma 17](#A6.Ex296) in the Appendix.

###### Corollary 2 .

Under the same setting [Theorem 2](#Thmtheorem2), to achieve an $\epsilon$-accurate stationary point, [Algorithm 2](#alg2) needs $T=\mathcal{O}\big{(}\frac{1}{\epsilon}\log^{4}(\frac{1}{\epsilon})\big{)}$ and the gradient complexity is ${\rm Gc}(\epsilon)=\mathcal{O}\big{(}\frac{1}{\epsilon}\log^{4}(\frac{1}{\epsilon})\big{)}$.

[Theorem 2](#Thmtheorem2) shows that the proposed [Algorithm 2](#alg2) achieves a convergence rate of $\mathcal{O}({\log^{4}(T)}/{T})$ and a gradient complexity of $\mathcal{O}\big{(}\frac{1}{\epsilon}\log^{4}(\frac{1}{\epsilon})\big{)}$, both of which nearly match the results in  [] of the standard well-tuned bilevel optimization methods up to polylogarithmic factors.

###### Remark 4 .

Note that the difference of $\frac{1}{\epsilon}$ in gradient complexity between double-loop and single-loop methods has not been observed in previous works on well-tuned bilevel optimization.
This difference stems from the design of the sub-loops. In previous double-loop works, carefully selected stepsizes are used to ensure that the iterates of each sub-loop converge linearly, up to an approximation error caused by the shift in $x$. However, due to the precise control of stepsizes, tuning-free approaches can only guarantee a sub-linear convergence for each sub-loop (as shown in [Proposition 2](#Thmproposition2)).

###### Proposition 3 .

###### Proposition 4 .

###### Proposition 5 .

###### Theorem 2 .

###### Corollary 2 .

###### Remark 4 .

## 5 Experiments

In this section, we evaluate the effectiveness of our proposed algorithm on practical applications including regularization selection, data hyper-cleaning [], and coreset selection for continual learning []. Our implementation is based on the benchmark provided in [] and [], respectively. Please refer to [Appendix B](#A2) for more details about practical implementation, experiment configurations, and additional plots.

### 5.1 Regularization Selection

The selection of regularization can be framed as a bilevel optimization problem, where the inner objective focuses on optimizing the model parameters $\theta$ on the training set $\mathcal{S}_{T}=\{(d_{i}^{train},y_{i}^{train})\}_{1\leq i\leq n}$, while the outer objective aims to determine the best regularization term $\lambda$ on the validation set $\mathcal{S}_{V}=\{(d_{j}^{val},y_{j}^{val})\}_{1\leq j\leq m}$. Denote the model parameters by $\theta\in\mathbb{R}^{p}$ and regularization term by $\lambda\in\mathbb{R}^{p}$, then the outer and inner problems can be formulated as

$$ $\displaystyle f(\theta,\lambda)=\frac{1}{m}\sum_{j=1}^{m}l\big{(}(d_{j}^{val},y_{j}^{val}),\theta\big{)};\quad g(\theta,\lambda)=\frac{1}{n}\sum_{i=1}^{n}l\big{(}(d_{i}^{train},y_{i}^{train}),\theta\big{)}+\mathcal{R}(\theta,\lambda),$ $$

where the loss $l((d_{i},y_{i}),\theta)=\log(1+\exp(-y_{i}d_{i}^{\top}\theta)$, and $\mathcal{R}(\theta,\lambda)=\frac{1}{2}\sum_{k=1}^{p}\exp(\lambda_{k})\theta_{k}^{2}$ represents the regularization, where each element $\theta_{k}$ is regularized with strength $\exp(\lambda_{k})$. We compare our proposed algorithm with benchmark bilevel algorithms including AmIGO [], BSA [], FSLA [], MRBO [], SOBA [], StocBiO [], SUSTAIN [], TTSA [], VRBO [] on the Covtype dataset. More details are provided in [Appendix B](#A2).

Figure: (a) Covtype
Refer to caption: /html/2410.05140/assets/x1.png

As shown in [Figure 1(a)](#S5.F1.sf1), our D-TFBO achieves the fastest convergence rate, while S-TFBO converges slightly more slowly but remains comparable to other well-tuned methods.

### 5.2 Data Hyper-Cleaning

The training set $\mathcal{S}_{T}=\{(d_{i}^{train},y_{i}^{train})\}_{1\leq i\leq n}$ have been corrupted in this scenario, where the label of a data sample could be replaced by a random label with a certain probability $p$. It is important to note that we do not have prior knowledge about which data samples have been corrupted. The objective is to develop a model that can effectively fit the corrupted training set while performing well on the clean validation set $\mathcal{S}_{V}=\{(d_{j}^{val},y_{j}^{val})\}_{1\leq j\leq m}$. We conduct experiments on the MNIST dataset, where we aim to learn a set of weights $\lambda$, one for each training sample, in addition to the model parameters $\theta$. Hence, the outer and inner problems are

$$ $\displaystyle f(\theta,\lambda)=\frac{1}{m}\sum_{j=1}^{m}l\big{(}(d_{j}^{val},y_{j}^{val}),\theta\big{)};\quad g(\theta,\lambda)=\frac{1}{n}\sum_{i=1}^{n}\sigma(\lambda_{i})l\big{(}(d_{i}^{train},y_{i}^{train}),\theta\big{)}+C\|\theta\|^{2},$ $$

where $\sigma(\cdot)$ is sigmoid function, $C$ is a regularization constant, and loss function $l((d_{i},y_{i}),\theta)=1/(1+\exp(-y_{i}d_{i}^{\top}\theta))$. Ideally, we would like the weights to be 0 for the corrupted sample and 1 for the clean sample. More details can be found in [Appendix B](#A2). We compare the performance with other bilevel optimization methods including AmIGO [], BSA [], FSLA [], MRBO [], SOBA [], StocBiO [], SUSTAIN [], VRBO []. The results presented in [Figure 1(b)](#S5.F1.sf2) demonstrate that our algorithms achieve a convergence rate comparable to other baselines.

### 5.3 Coreset Selection for Continual Learning

Coreset selection aims to improve training efficiency by selecting a subset of the most informative data samples, which can be used as an approximation of the entire dataset. Thus, the model that minimizes the loss on the coreset can also minimize the loss on the entire dataset. Following the design in [], we apply the proposed algorithms to coreset selection for continual learning.
The inner problem learns model parameters $\theta$, and the outer problem determines the distribution $\lambda$ ($0\leq\lambda_{(i)}\leq 1$ and $\|\lambda\|_{1}=1$) over the entire dataset

$$ $\displaystyle f(\theta,\lambda)=\sum_{i=1}^{n}l_{i}(\theta)+C\mathcal{R}(\lambda);\quad g(\theta,\lambda)=\sum_{i=1}^{n}\lambda_{(i)}l_{i}(\theta),$ $$

where $n$ is the sample size, $C$ is a constant, $\lambda_{(i)}$ is the $i$-th entry. $\mathcal{R}(\lambda)=-\sum_{i=1}^{K}\mathbb{E}(\lambda+\delta z)_{[i]}$ denotes the smoothed top-$K$ regularizer, where $\delta$ is a constant and $z\sim\mathcal{N}(0,1)$, $\lambda_{[i]}$ is the $i$-th largest component. The regularizer encourages the distribution to have $K$ non-zero entries, corresponding to the size of the selected coreset. Following [], we use the Split CIFAR100 dataset and conduct experiments in the balanced and imbalanced scenarios. We compare the proposed algorithms with various methods, including $k$-means features [], $k$-means embedding [], Uniform Sampling, iCaRL [], Grad Matching [], GCR [], Greedy Coreset [], PBCS [], and BCSR [], with the last three being bilevel optimization-based methods. We evaluate the performance using the average accuracy and forgetting measure across all tasks after learning task $T$. The former is defined as $A_{T}=\frac{1}{T}\sum_{i=1}^{T}a_{T,i}$, where $a_{T,i}$ is the test accuracy of the $i$-th task after learning task $T$. The latter is defined as $FGT_{T}=\frac{1}{T}\sum_{i=1}^{T}[\max_{j\in 1,\cdots,T-1}(a_{j,i}-a_{T,i})]$. The results are shown in [Table 1](#S5.T1). Each experiment is repeated three times and the average is reported. It can be observed that our D-TFBO achieves the best $FGT_{T}$ under the balanced setting and the second-best performance under the imbalanced setting.

**Table 1: Results on Split CIFAR100. The best and second best results are in bold and underlined.**
| Method | Balanced | Imbalanced |  |  |
| --- | --- | --- | --- | --- |
| $A_{T}$ | $FGT_{T}$ | $A_{T}$ | $FGT_{T}$ |  |
| $k$-means features | 57.82$\pm$0.69 | 0.070$\pm$0.003 | 45.44$\pm$0.76 | 0.037$\pm$0.002 |
| $k$-means embedding | 59.77$\pm$0.24 | 0.061$\pm$0.001 | 43.91$\pm$0.15 | 0.044$\pm$0.001 |
| Uniform Sampling | 58.99$\pm$0.54 | 0.074$\pm$0.004 | 44.73$\pm$0.11 | 0.033$\pm$0.007 |
| iCaRL | 60.74$\pm$0.09 | 0.044$\pm$0.026 | 44.25$\pm$2.04 | 0.042$\pm$0.019 |
| Grad Matching | 59.17$\pm$0.38 | 0.067$\pm$0.003 | 45.44$\pm$0.64 | 0.038$\pm$0.001 |
| GCR | 58.73$\pm$0.43 | 0.073$\pm$0.013 | 44.48$\pm$0.05 | 0.035$\pm$0.005 |
| Greedy Coreset | 59.39$\pm$0.16 | 0.066$\pm$0.017 | 43.80$\pm$0.01 | 0.039$\pm$0.007 |
| PBCS | 55.64$\pm$2.26 | 0.062$\pm$0.001 | 39.87$\pm$1.12 | 0.076$\pm$0.011 |
| BCSR | 61.60$\pm$0.14 | 0.051$\pm$0.015 | 47.30$\pm$0.57 | 0.022$\pm$0.005 |
| S-TFBO | 58.90$\pm$0.75 | 0.046$\pm$0.009 | 45.78$\pm$0.70 | 0.036$\pm$0.005 |
| D-TFBO | 59.54$\pm$0.45 | 0.041$\pm$0.005 | 46.68$\pm$0.72 | 0.029$\pm$0.002 |

**Table 2: Experiment results of sensitivity analysis on Split CIFAR100. The initial values refer to the constant learning rates in BCSR or $\alpha_{0}$,$\beta_{0}$,$\gamma_{0}$ in S-TFBO and D-TFBO.**
| Method | $initial=2$ | $initial=4$ | $initial=6$ | $initial=8$ | Relative Average Change |
| --- | --- | --- | --- | --- | --- |
| BCSR | 59.42 | 56.25 | 58.75 | 57.55 | 5.8$\%$ |
| S-TFBO | 58.85 | 58.55 | 58.69 | 58.47 | 0.4$\%$ |
| D-TFBO | 59.71 | 59.62 | 59.11 | 59.08 | 0.3$\%$ |

Sensitivity analysis w.r.t. different initial learning rates. The tuning-free design provides another benefit. The proposed algorithms demonstrate more robustness compared to the []. We conduct a simple sensitivity analysis under the balanced setting, regarding the learning rates in the inner and outer loops. Specifically, we set the initial learning rates in [] and $\alpha_{0}$, $\beta_{0}$, $\gamma_{0}$ in S-TFBO and D-TFBO for the inner and outer loops to $\{2,4,6,8\}$, where the original values are set to 5. We run one experiment for each learning rate. Further, we compare the changes in average accuracy $A_{T}$. We also compute the average and report the relative change compared to the results presented in [Table 1](#S5.T1).
The code is available at [https://github.com/OptMN-Lab/tfbo](https://github.com/OptMN-Lab/tfbo).

## 6 Conclusion

We introduce two fully tuning-free bilevel optimization algorithms, D-TFBO and S-TFBO. Both methods adaptively update stepsizes without requiring prior knowledge of problem parameters, while achieving convergence rates comparable to their well-tuned counterparts. The experimental results show that our tuning-free design performs comparably to existing well-tuned methods and is more robust to initial stepsizes. We anticipate that the proposed algorithms and the developed analysis can be extended to the stochastic setting,
and the proposed algorithms may be applied to other applications such
as meta-learning, few-shot learning, and fair machine learning.

## Appendix A Supplementary Related Work on Bilevel Optimization

Initially introduced by [], bilevel optimization has been extensively studied for decades. Early works [, , , ] solved the bilevel problem from a constrained optimization perspective. More recently, gradient-based bilevel methods have gained significant attention for their efficiency and effectiveness in addressing machine learning problems. Among them, approaches based on Approximate Implicit Differentiation (AID) [, , , , , , , ] exploit the implicit derivation of the hypergradient, approximating it by solving a linear system.

On the other hand, approaches based on Iterative Differentiation (ITD) [, , , , ] estimate the hypergradient by employing automatic differentiation, utilizing either forward or reverse mode.

A series of stochastic bilevel approaches has been developed and analyzed recently, utilizing Neumann series [, , ], recursive momentum [, , ], and variance reduction [, ], etc. For the lower-level problem with multiple solutions, several approaches were proposed based on upper- and lower-level gradient aggregation [, , ], barrier types of regularization [, ], penalty-based formulations [], primal-dual techniques [], and dynamic system-based methods []. Another class of approaches formulated the lower-level problem as a value-function-based constraint [, ] to solve bilevel problems without second-order gradients.

## Appendix B Specifications of Experiments

### B.1 Practical Implementation

For regularization selection and data hyper-cleaning, we use the benchmark provided in []. For coreset selection, we use the codebase from []. We implement D-TFBO using “for loops” as an approximation, since the magnitude of $\|\nabla_{v}R(x,y,v)\|$ in [Algorithm 1](#alg1) varies across different experiments. Specifically, the number of loops for updating $y$ and $v$ in regularization selection and data hyper-cleaning are both set to 10, while the numbers of loops for updating $y$ and $v$ in coreset selection are 5 and 3, respectively.

Figure: (a) Covtype
Refer to caption: /html/2410.05140/assets/x3.png

### B.2 Configuration

We adopt the default configuration for regularization selection and data hyper-cleaning. The batch size is 64. The maximum iterations are 2048 and 512, respectively. The data corruption ratio in hyper-cleaning is 0.1. For coreset selection, we also use the default configuration except for the leaning rates, due to the tuning-free design. The $\alpha_{0}$, $\beta_{0}$, and $\gamma_{0}$ values are set to 5.

### B.3 Additional Results

For regularization and data hyper-cleaning, we also present the loss curves regarding running time in [Figure 2](#A2.F2). Our methods exhibit a faster running time than other baselines on the Covtype dataset.

## Appendix C Proof Sketch

The proofs of Propositions [1](#Thmproposition1), [2](#Thmproposition2), [3](#Thmproposition3), [4](#Thmproposition4) and [5](#Thmproposition5) can be found in [Lemma 4](#Thmlemma4), [9](#Thmlemma9), [11](#Thmlemma11), [15](#Thmlemma15),[17](#Thmlemma17), respectively. In this section, we present a high level proof sketch that outlines the convergence and gradient complexity analysis of [Algorithm 1](#alg1) and [Algorithm 2](#alg2), emphasizing the key challenges and our technical innovations.

Proof sketch of [Algorithm 1](#alg1):

Step 1: We first discuss the two-stage framework in our problem in [Lemma 4](#Thmlemma4) and we develop two forms of descent lemma of the objective function in [Lemma 7](#Thmlemma7) based on the two stages of $\alpha_{t}$ in [Lemma 4](#Thmlemma4).

Step 2: We developed upper bounds of $\alpha_{t}$ under the two stages in [Lemma 4](#Thmlemma4).

Step 3: We provide the maximum iteration numbers for the sub-loops approximating $y^{*}(x_{t})$ and $v^{*}(x_{t})$.

Step 4: Combining the results in Step 1 and Step 2, we telescope and take the average of the inequalities in the descent lemma of the objective function, then we obtain the convergence rate.

Step 5: Combining the maximum iteration numbers in Step 3 and convergence rate in Step 4, we obtain the gradient computation complexity to find $\epsilon$-stationary point.
Then the proof is complete.

Proof sketch of [Algorithm 2](#alg2):

Step 1: We first discuss the two-stage framework in our problem in [Lemma 4](#Thmlemma4) and we develop two forms of descent lemma of the objective function in [Lemma 11](#Thmlemma11) based on the two stages of $\alpha_{t}$ in [Lemma 4](#Thmlemma4).

Step 2: We develop a rough upper bound of two important components in the descent lemma in [Lemma 11](#Thmlemma11):
$\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ and $\sum_{k=k_{3}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}$, where $k_{2}$ and $k_{3}$ represents the second stage in [Lemma 4](#Thmlemma4).

Step 3: Following the results in Step 2 and the upper bound of $v_{t}$ in [Lemma 10](#Thmlemma10),
we obtain a two-way relationship between $\varphi_{t+1}$ and
$\sum_{k=0}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$, which further indicates the logarithmic upper bounds of both terms in [Lemma 15](#Thmlemma15) and [Lemma 16](#Thmlemma16), respectively.

Step 4: Incorporating the results from Step 3 into the rough bounds from Step 2, we can also obtain the logarithmic upper bounds of $\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ and $\sum_{k=k_{3}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}$ in [Lemma 16](#Thmlemma16).

Step 5: We rearrange the terms in [Lemma 11](#Thmlemma11) and
incorporate in the results in Step 4, we obtain two forms of the upper bound of $\alpha_{t}$ in [Lemma 17](#Thmlemma17).

Step 6:
Combining the results in Steps 3, 4, 5, we telescope and take the average of the inequalities in the descent lemma of the objective function, then we obtain the convergence rate.

Step 7: Without sub-loops, via the convergence rate in Step 6,
we can directly obtain the gradient computation complexity to find $\epsilon$-stationary point.
Then the proof is complete.

## Appendix D Proofs of Preliminary Lemmas

###### Lemma 1 ( [ 84 ] Lemma 3.2) .

For any non-negative $a_{1},...,a_{T}$, and $a_{1}\geq 1$, we have

$$ $\displaystyle\sum_{l=1}^{T}\frac{a_{l}}{\sum_{i=1}^{l}a_{i}}\leq\log\Bigg{(}\sum_{l=1}^{T}a_{l}\Bigg{)}+1.$ (4) $$

###### Lemma 2 .

Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2), we have basic properties as follows:

- (a)
$\Phi(x)$ is $L_{\Phi}$-smooth w.r.t $x$, where $L_{\Phi}:=\Big{(}L_{f,1}+\frac{L_{g,2}C_{f_{y}}}{\mu}\Big{)}\Big{(}1+\frac{C_{g_{xy}}}{\mu}\Big{)}^{2}$;
- (b)
$y^{*}(x)$ is $L_{y}$-Lipschitz continuous w.r.t. $x$, where $L_{y}:=\frac{C_{g_{xy}}}{\mu}$;
- (c)
the gradient estimator $\bar{\nabla}f(x,y,v)$ is $(L_{g,2}\|v\|+L_{f,1})$ -Lipschitz continuous w.r.t. $(x,y)$, and $L_{g,1}$-Lipschitz continuous w.r.t. $v$;
- (d)
$\bar{\nabla}f(x,y,v)$ can be bounded as $\|\bar{\nabla}f(x,y,v)\|\leq C_{g_{xy}}\|v\|+C_{f_{x}}$.

###### Proof.

The proof of (a) and (b) can refer to []. For (c), under Assumption [2](#Thmassumption2), we have

$$ $\displaystyle\|\bar{\nabla}f(x_{1},y_{1},v)-\bar{\nabla}f(x_{2},y_{2},v)\|\leq$ $\displaystyle\|\nabla_{x}\nabla_{y}g(x_{1},y_{1})-\nabla_{x}\nabla_{y}g(x_{2},y_{2})\|\cdot\|v\|$ $\displaystyle+\|\nabla_{x}f(x_{1},y_{1})-\nabla_{x}f(x_{2},y_{2})\|$ $\displaystyle\leq$ $\displaystyle(L_{g,2}\|v\|+L_{f,1})(\|x_{1}-x_{2}\|+\|y_{1}-y_{2}\|)$ $\displaystyle\|\bar{\nabla}f(x,y,v_{1})-\bar{\nabla}f(x,y,v_{2})\|\leq$ $\displaystyle\|\nabla_{x}\nabla_{y}g(x,y)\|\cdot\|v_{1}-v_{2}\|\leq L_{g,1}\|v_{1}-v_{2}\|.$ $$

By Assumption [2](#Thmassumption2) and Remark [3](#Thmremark3), we can easily prove (d) as

$$ $\displaystyle\|\bar{\nabla}f(x,y,v)\|\leq\|\nabla_{x}\nabla_{y}g(x,y)\|\cdot\|v\|+\|\nabla_{x}f(x,y)\|\leq C_{g_{xy}}\|v\|+C_{f_{x}}.$ $$

Then the proof is complete.
∎

###### Lemma 3 .

Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2), we have basic properties of linear system function $R$ in [eq. 2](#S3.E2) as follows:

- (a)
$R(x,y,v)$ is $\mu$-strongly convex and $C_{g_{yy}}$-smooth w.r.t. $v$;
- (b)
$\nabla_{v}R(x,y,v)$ is $(L_{g,2}\|v\|+L_{f,1})$-Lipschitz continuous w.r.t. $(x,y)$;
- (c)
$\nabla_{v}R(x,y,v)$ can be bounded as $\|\nabla_{v}R(x,y,v)\|\leq C_{g_{yy}}\|v\|+C_{f_{y}}$;
- (d)
$v^{*}(x)$ in [eq. 2](#S3.E2) can be bounded as $\|v^{*}(x)\|\leq\frac{C_{f_{y}}}{\mu}$, and $\hat{v}^{*}(x,y):=\operatorname*{arg\,min}_{v}R(x,y,v)$ can also be bounded as $\|\hat{v}^{*}(x,y)\|\leq\frac{C_{f_{y}}}{\mu}$;
- (e)
$v^{*}(x)$ is $L_{v}$-Lipschitz continuous w.r.t. $x$ and $\hat{v}^{*}(x,y)$ is $\bar{L}_{v}$-Lipschitz continuous w.r.t. $y$,
where $L_{v}:=\Big{(}\frac{L_{f,1}}{\mu}+\frac{C_{f_{y}}L_{g,2}}{\mu^{2}}\Big{)}(1+L_{y})$ and $\bar{L}_{v}:=\frac{L_{f,1}}{\mu}+\frac{C_{f_{y}}L_{g,2}}{\mu^{2}}$.

###### Proof.

First of all, since $\nabla_{v}\nabla_{v}R(x,y,v)=\nabla_{y}\nabla_{y}g(x,y)$, we know $\mu I\preceq\nabla_{y}\nabla_{y}g(x,y)$. Thus, according to Assumptions[1](#Thmassumption1),[2](#Thmassumption2), we have

$$ $\displaystyle\|\nabla_{v}\nabla_{v}R(x,y,v_{1})-\nabla_{v}\nabla_{v}R(x,y,v_{2})\|\leq\|\nabla_{y}\nabla_{y}g(x,y)\|\|v_{1}-v_{2}\|\leq C_{g_{yy}}\|v_{1}-v_{2}\|.$ $$

Then (a) is proved.
Next, by using Lipschitz continuity in Assumption [2](#Thmassumption2), we have

$$ $\displaystyle\|\nabla_{v}R(x_{1},y_{1},v)-\nabla_{v}R(x_{2},y_{2},v)\|\leq$ $\displaystyle\|\nabla_{y}\nabla_{y}g(x_{1},y_{1})-\nabla_{y}\nabla_{y}g(x_{2},y_{2})\|\cdot\|v\|$ $\displaystyle+\|\nabla_{y}f(x_{1},y_{1})-\nabla_{y}f(x_{2},y_{2})\|$ $\displaystyle\leq$ $\displaystyle(L_{g,2}\|v\|+L_{f,1})(\|x_{1}-x_{2}\|+\|y_{1}-y_{2}\|).$ $$

Then (b) is proved. By Assumption [2](#Thmassumption2), we can easily prove (c) as

$$ $\displaystyle\|\nabla_{v}R(x,y,v)\|\leq\|\nabla_{y}\nabla_{y}g(x,y)\|\cdot\|v\|+\|\nabla_{y}f(x,y)\|\leq C_{g_{yy}}\|v\|+C_{f_{y}}.$ $$

Next, for $\hat{v}^{*}(x,y)$, we have

$$ $\displaystyle\nabla_{v}R\big{(}x,y,\hat{v}^{*}(x,y)\big{)}=\nabla_{y}\nabla_{y}g(x,y)\hat{v}^{*}(x,y)-\nabla_{y}f(x,y)=0,$ $$

which indicates that

$$ $\displaystyle\left\lVert\hat{v}^{*}(x,y)\right\rVert=$ $\displaystyle\big{\|}\big{[}\nabla_{y}\nabla_{y}g(x,y)\big{]}^{-1}\nabla_{y}f(x,y)\big{\|}\leq\big{\|}\big{[}\nabla_{y}\nabla_{y}g(x,y)\big{]}^{-1}\big{\|}\cdot\|\nabla_{y}f(x,y))\|\leq\frac{C_{f_{y}}}{\mu}.$ $$

Since $v^{*}(x)$ is a special case as $v^{*}(x)=\hat{v}^{*}(x,y^{*}(x))$, (d) is proved.
The proof of the first part of (e) can refer to Lemma 4 in [];
for the second part, we have

$$ $\displaystyle\|\hat{v}^{*}$ $\displaystyle(x,y_{1})-\hat{v}^{*}(x,y_{2})\|$ $\displaystyle=$ $\displaystyle\big{\|}[\nabla_{y}\nabla_{y}g(x,y_{1})]^{-1}\nabla_{y}f(x,y_{1})-[\nabla_{y}\nabla_{y}g(x,y_{2})]^{-1}\nabla_{y}f(x,y_{2})\big{\|}$ $\displaystyle\leq$ $\displaystyle\big{\|}[\nabla_{y}\nabla_{y}g(x,y_{1})]^{-1}\big{(}\nabla_{y}f(x,y_{1})-\nabla_{y}f(x,y_{2})\big{)}\big{\|}$ $\displaystyle+\big{\|}\big{(}[\nabla_{y}\nabla_{y}g(x,y_{1})]^{-1}-[\nabla_{y}\nabla_{y}g(x,y_{2})]^{-1}\big{)}\nabla_{y}f(x,y_{2})\big{\|}$ $\displaystyle\leq$ $\displaystyle\frac{L_{f,1}}{\mu}\|y_{1}-y_{2}\|+C_{f_{y}}\big{\|}\big{(}[\nabla_{y}\nabla_{y}g(x,y_{1})]^{-1}\big{(}\nabla_{y}\nabla_{y}g(x,y_{2})-\nabla_{y}\nabla_{y}g(x,y_{1})\big{)}[\nabla_{y}\nabla_{y}g(x,y_{2})]^{-1}\big{)}\big{\|}$ $\displaystyle\leq$ $\displaystyle\bigg{(}\frac{L_{f,1}}{\mu}+\frac{C_{f_{y}}L_{g,2}}{\mu^{2}}\bigg{)}\|y_{1}-y_{2}\|.$ $$

Thus, the second part of (e) is proved and the proof of [Lemma 3](#Thmlemma3) is complete.
∎

###### Lemma 4 .

Suppose the iteration rounds to update $\{x,y,v\}$ are $\{T_{1},T_{2},T_{3}\}$ and $\{\alpha_{t},\beta_{t},\gamma_{t}\}$ are generated by [Algorithm 1](#alg1) or [2](#alg2). For any $C_{\alpha}\geq\alpha_{0}$, $C_{\beta}\geq\beta_{0}$, $C_{\gamma}\geq\gamma_{0}$, we have

- (a)
either $\alpha_{t}\leq C_{\alpha}$ for any $t\leq T_{1}$, or $\exists k_{1}\leq T_{1}$ such that $\alpha_{k_{1}}\leq C_{\alpha}$, $\alpha_{k_{1}+1}>C_{\alpha}$;
- (b)
either $\beta_{t}\leq C_{\beta}$ for any $t\leq T_{2}$, or $\exists k_{2}\leq T_{2}$ such that $\beta_{k_{2}}\leq C_{\beta}$, $\beta_{k_{2}+1}>C_{\beta}$;
- (c)
either $\gamma_{t}\leq C_{\gamma}$ for any $t\leq T_{3}$, or $\exists k_{3}\leq T_{3}$ such that $\gamma_{k_{3}}\leq C_{\gamma}$, $\gamma_{k_{3}+1}>C_{\gamma}$.

###### Proof.

The proof resembles the Lemma 4.1 in []. Here we only prove part (a), and the other two are similar.
Note that if $\alpha_{T_{1}}>C_{\alpha}$, then there must exist $k_{1}\leq T_{1}$ such that $\alpha_{k_{1}}\leq C_{\alpha}$, $\alpha_{k_{1}+1}>C_{\alpha}$, because $C_{\alpha}\geq\alpha_{0}$ and the sequence $\{\alpha_{k}\}$ is monotonically increasing. Otherwise, we have $\alpha_{t}\leq\alpha_{T_{1}}\leq C_{\alpha}$ for any $t\leq T_{1}$.
This completes the proof of part (a).
∎

###### Lemma 1 ( [ 84 ] Lemma 3.2) .

###### Lemma 2 .

###### Proof.

###### Lemma 3 .

###### Proof.

###### Lemma 4 .

###### Proof.

## Appendix E Proof of Theorem 1

We define some notation for convenience before proving [Theorem 1](#Thmtheorem1).

### E.1 Notation

Here, we define the following constants as thresholds for parameters $\beta_{p}$, $\gamma_{q}$, $\alpha_{t}$ in [Algorithm 1](#alg1) as

$$ $\displaystyle C_{\alpha}:=\max\big{\{}2L_{\Phi},\alpha_{0}\big{\}},\quad C_{\beta}:=\max\big{\{}L_{g,1},\beta_{0}\big{\}},\quad C_{\gamma}:=\max\big{\{}C_{g_{yy}},\gamma_{0}\big{\}}.$ (5) $$

### E.2 Proofs of Preliminary Lemmas

###### Lemma 5 .

Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2), for any $t\geq 0$ in [Algorithm 1](#alg1), we have

$$ $\displaystyle\|y_{t}^{P_{t}}-y^{*}(x_{t})\|^{2}\leq\frac{\epsilon_{y}}{\mu^{2}},\quad\big{\|}v_{t}^{Q_{t}}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}\leq\frac{\epsilon_{v}}{\mu^{2}},$ $$

where $\epsilon_{y}$ and $\epsilon_{v}$ are sub-loop stopping criteria in [Algorithm 1](#alg1).

###### Proof.

For the $k_{th}$ iteration, according to the stop criteria of the sub-loops, we have

$$ $\displaystyle\|\nabla_{y}g(x_{t},y_{t}^{P_{t}})\|^{2}\leq\epsilon_{y},\quad\|\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}})\|^{2}\leq\epsilon_{v}.$ $$

By using Assumptions [1](#Thmassumption1),[2](#Thmassumption2), we have

$$ $\displaystyle\|y_{t}^{P_{t}}-y^{*}(x_{t})\|^{2}\leq\frac{1}{\mu^{2}}\big{\|}\nabla_{y}g(x_{t},y_{t}^{P_{t}})-\nabla_{y}g\big{(}x_{t},y^{*}(x_{t})\big{)}\big{\|}^{2}\leq\frac{\epsilon_{y}}{\mu^{2}},$ $\displaystyle\big{\|}v_{t}^{Q_{t}}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}\leq\frac{1}{\mu^{2}}\big{\|}\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}})-\nabla_{v}R\big{(}x_{t},y_{t}^{P_{t}},\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{)}\big{\|}^{2}\leq\frac{\epsilon_{v}}{\mu^{2}},$ $$

since $\|\nabla_{y}g(x_{t},y^{*}(x_{t}))\|^{2}=0$ and $\big{\|}\nabla_{v}R\big{(}x_{t},y_{t}^{P_{t}},\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{)}\big{\|}^{2}=0$.
Thus, the proof is complete.
∎

###### Lemma 6 .

Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2), for any $t\geq 0$ in Algorithm [1](#alg1), we have $\|\bar{\nabla}f(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}})\|^{2}\leq C_{f}^{2}$, where $C_{f}:=\Big{(}\frac{2C_{g_{xy}}^{2}\epsilon_{v}}{\mu^{2}}+\frac{4C_{g_{xy}}^{2}C_{f_{y}}^{2}}{\mu^{2}}+4C_{f_{y}}^{2}\Big{)}^{\frac{1}{2}}$.

###### Proof.

For the $k_{th}$ iteration, we have

$$ $\displaystyle\|\bar{\nabla}f($ $\displaystyle x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}})\|^{2}$ $\displaystyle\leq$ $\displaystyle 2\big{\|}\bar{\nabla}f(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}})-\bar{\nabla}f\big{(}x_{t},y_{t}^{P_{t}},\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{)}\big{\|}^{2}+2\big{\|}\bar{\nabla}f\big{(}x_{t},y_{t}^{P_{t}},\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{)}\big{\|}^{2}$ $\displaystyle=$ $\displaystyle 2\big{\|}\nabla_{x}\nabla_{y}g(x_{t},y_{t}^{P_{t}})\big{(}v_{t}^{Q_{t}}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{)}\big{\|}^{2}+2\|\nabla_{x}\nabla_{y}g(x_{t},y_{t}^{P_{t}})\hat{v}^{*}(x_{t},y_{t}^{P_{t}})-\nabla_{y}f(x_{t},y_{t}^{P_{t}})\|^{2}$ $\displaystyle\leq$ $\displaystyle 2\big{\|}\nabla_{x}\nabla_{y}g(x_{t},y_{t}^{P_{t}})\big{\|}^{2}\cdot\|v_{t}^{Q_{t}}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\|^{2}+2\|\nabla_{x}\nabla_{y}g(x_{t},y_{t}^{P_{t}})\hat{v}^{*}(x_{t},y_{t}^{P_{t}})-\nabla_{y}f(x_{t},y_{t}^{P_{t}})\|^{2}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\frac{2C_{g_{xy}}^{2}\epsilon_{v}}{\mu^{2}}+\frac{4C_{g_{xy}}^{2}C_{f_{y}}^{2}}{\mu^{2}}+4C_{f_{y}}^{2},$ $$

where (a) uses Assumption [1](#Thmassumption1), [Remark 3](#Thmremark3), [Lemma 3](#Thmlemma3) and [Lemma 5](#Thmlemma5). Then, the proof is complete.
∎

###### Lemma 5 .

###### Proof.

###### Lemma 6 .

###### Proof.

### E.3 Descent in Objective Function

###### Lemma 7 .

Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2), for Algorithm [1](#alg1), suppose the total iteration number is $T$.
No matter $k_{1}$ in [Lemma 4](#Thmlemma4) exists or not, we always have

$$ $\displaystyle\Phi(x_{t+1})\leq$ $\displaystyle\Phi(x_{t})-\frac{1}{2\alpha_{t+1}}\|\nabla\Phi(x_{t})\|^{2}-\frac{1}{2\alpha_{t+1}}\Big{(}1-\frac{L_{\Phi}}{2\alpha_{t+1}}\Big{)}\|\bar{\nabla}f(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}})\|^{2}+\frac{\epsilon^{\prime}}{2\alpha_{t+1}}.$ (6) $$

If in addition, $k_{1}$ in [Lemma 4](#Thmlemma4) exists, then for $t\geq k_{1}$, we further have

$$ $\displaystyle\Phi(x_{t+1})\leq$ $\displaystyle\Phi(x_{t})-\frac{1}{2\alpha_{t+1}}\|\nabla\Phi(x_{t})\|^{2}-\frac{1}{4\alpha_{t+1}}\|\bar{\nabla}f(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}})\|^{2}+\frac{\epsilon^{\prime}}{2\alpha_{t+1}},$ (7) $$

where
$\epsilon^{\prime}:=\frac{\bar{L}^{2}}{\mu^{2}}(\epsilon_{y}+\epsilon_{v})$ and $\bar{L}:=\max\big{\{}2\big{(}\frac{C_{f_{y}}^{2}L_{g,2}^{2}}{\mu^{2}}+L_{f,1}^{2}+C_{g_{yy}}^{2}\bar{L}_{v}^{2}\big{)}^{\frac{1}{2}},\sqrt{2}C_{g_{yy}}\big{\}}$.

###### Proof.

From [Lemma 2](#Thmlemma2), we have $\Phi(x)$ is $L_{\Phi}$-smooth. So we can apply the descent lemma to $\Phi$ as

$$ $\displaystyle\Phi(x_{t+1})\leq$ $\displaystyle\Phi(x_{t})+\langle\nabla\Phi(x_{t}),x_{t+1}-x_{t}\rangle+\frac{L_{\Phi}}{2}\|x_{t+1}-x_{t}\|^{2}$ $\displaystyle=$ $\displaystyle\Phi(x_{t})-\frac{1}{\alpha_{t+1}}\big{\langle}\nabla\Phi(x_{t}),\bar{\nabla}f\big{(}x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}}\big{)}\big{\rangle}+\frac{L_{\Phi}}{2\alpha_{t+1}^{2}}\big{\|}\bar{\nabla}f\big{(}x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}}\big{)}\big{\|}^{2}$ $\displaystyle=$ $\displaystyle\Phi(x_{t})-\frac{1}{2\alpha_{t+1}}\|\nabla\Phi(x)\|^{2}-\frac{1}{2\alpha_{t+1}}\big{\|}\bar{\nabla}f\big{(}x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}}\big{)}\big{\|}^{2}$ $\displaystyle+\frac{1}{2\alpha_{t+1}}\big{\|}\nabla\Phi(x_{t})-\bar{\nabla}f\big{(}x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}}\big{)}\big{\|}^{2}+\frac{L_{\Phi}}{2\alpha_{t+1}^{2}}\big{\|}\bar{\nabla}f\big{(}x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}}\big{)}\big{\|}^{2},$ (8) $$

where the approximation error

$$ $\displaystyle\big{\|}\nabla$ $\displaystyle\Phi(x_{t})-\bar{\nabla}f\big{(}x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}}\big{)}\big{\|}^{2}$ $\displaystyle=$ $\displaystyle\big{\|}\bar{\nabla}f\big{(}x_{t},y^{*}(x_{t}),v^{*}(x_{t})\big{)}-\bar{\nabla}f\big{(}x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}}\big{)}\big{\|}^{2}$ $\displaystyle\leq$ $\displaystyle 2\big{\|}\bar{\nabla}f\big{(}x_{t},y^{*}(x_{t}),v^{*}(x_{t})\big{)}-\bar{\nabla}f\big{(}x_{t},y_{t}^{P_{t}},v^{*}(x_{t})\big{)}\big{\|}^{2}$ $\displaystyle+2\big{\|}\bar{\nabla}f\big{(}x_{t},y_{t}^{P_{t}},v^{*}(x_{t})\big{)}-\bar{\nabla}f\big{(}x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}}\big{)}\big{\|}^{2}$ $\displaystyle\leq$ $\displaystyle 4\big{\|}\nabla_{y}\nabla_{y}g(x_{t},y^{*}(x_{t}))v^{*}(x_{t})-\nabla_{y}\nabla_{y}g\big{(}x_{t},y_{t}^{P_{t}}\big{)}v^{*}(x_{t})\big{\|}^{2}$ $\displaystyle+4\big{\|}\nabla_{y}f\big{(}x_{t},y^{*}(x_{t})\big{)}-\nabla_{y}f(x_{t},y_{t}^{P_{t}})\big{\|}^{2}+2\big{\|}\nabla_{y}\nabla_{y}g(x_{t},y_{t}^{P_{t}})\big{(}v^{*}(x_{t})-v_{t}^{Q_{t}}\big{)}\big{\|}^{2}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle 4\Big{(}\frac{C_{f_{y}}^{2}L_{g,2}^{2}}{\mu^{2}}+L_{f,1}^{2}\Big{)}\|y_{t}^{P_{t}}-y^{*}(x_{t})\|^{2}+2C_{g_{yy}}^{2}\|v_{t}^{Q_{t}}-v^{*}(x_{t})\|^{2}$ $\displaystyle\leq$ $\displaystyle{4\Big{(}\frac{C_{f_{y}}^{2}L_{g,2}^{2}}{\mu^{2}}+L_{f,1}^{2}\Big{)}\|y_{t}^{P_{t}}-y^{*}(x_{t})\|^{2}+4C_{g_{yy}}^{2}\|v_{t}^{Q_{t}}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\|^{2}+4C_{g_{yy}}^{2}\|\hat{v}^{*}(x_{t},y_{t}^{P_{t}})-v^{*}(x_{t})\|^{2}}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle{4\bigg{(}\frac{C_{f_{y}}^{2}L_{g,2}^{2}}{\mu^{2}}+L_{f,1}^{2}+C_{g_{yy}}^{2}\bar{L}_{v}^{2}\bigg{)}\|y_{t}^{P_{t}}-y^{*}(x_{t})\|^{2}+4C_{g_{yy}}^{2}\|v_{t}^{Q_{t}}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\|^{2}}$ $\displaystyle\leq$ $\displaystyle\bar{L}^{2}\big{(}\|y_{t}^{P_{t}}-y^{*}(x_{t})\|^{2}+\|v_{t}^{Q_{t}}-\hat{v}^{*}(x_{t},y^{*}(x_{t}))\|^{2}\big{)},$ (9) $$

where (a) uses Assumption [2](#Thmassumption2), [Remark 3](#Thmremark3) and [Lemma 3](#Thmlemma3);
(b) uses $v^{*}(x_{t})=\hat{v}^{*}\big{(}x_{t},y^{*}(x_{t})\big{)}$ and [Lemma 3](#Thmlemma3).
By using [Lemma 5](#Thmlemma5), we have

$$ $\displaystyle\big{\|}\nabla\Phi$ $\displaystyle(x_{t})-\bar{\nabla}f\big{(}x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}}\big{)}\big{\|}^{2}\leq\frac{\bar{L}^{2}}{\mu^{2}}(\epsilon_{y}+\epsilon_{v})=:\epsilon^{\prime}.$ (10) $$

By plugging [eq. 10](#A5.E10) into [section E.3](#A5.Ex44), we obtain ([6](#A5.E6)).

Now if in addition, $k_{1}$ in [Lemma 4](#Thmlemma4) exists, then for $t\geq k_{1}$, we have $\alpha_{t+1}>C_{\alpha}\geq 2L_{\Phi}$. From ([6](#A5.E6)) we can immediately obtain ([7](#A5.E7)).
Thus, the proof is complete.
∎

###### Lemma 7 .

###### Proof.

### E.4 The bound of α t subscript 𝛼 𝑡 \alpha_{t}

###### Lemma 8 .

Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2), [3](#Thmassumption3), suppose the number of total iteration rounds in [Algorithm 1](#alg1) is $T$.
If there exists $k_{1}\leq T$ described in [Lemma 4](#Thmlemma4), we have

$$ $\left\{\begin{aligned} \alpha_{t}\leq&C_{\alpha},\quad&t\leq k_{1};\\ \alpha_{t}\leq&C_{\alpha}+2c_{0}+\frac{2t\epsilon^{\prime}}{\alpha_{0}},\quad&t\geq k_{1},\end{aligned}\right.$ $$

where we define

$$ $\displaystyle c_{0}:=2\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{L_{\Phi}C_{\alpha}^{2}}{2\alpha_{0}^{2}}.$ (11) $$

When such $k_{1}$ does not exist, we have $\alpha_{t}\leq C_{\alpha}$ for any $t\leq T$.

###### Proof.

According to [Lemma 4](#Thmlemma4), the proof can be split into the following three cases.

Case 1: if $\alpha_{T}\leq C_{\alpha}$, for any $t<T$, we have the upper bound of $\alpha_{t+1}$ as $\alpha_{t+1}\leq C_{\alpha}$.

Case 2: if $\alpha_{T}>C_{\alpha}$, there exists $k_{1}\leq T$ described in [Lemma 4](#Thmlemma4).
Then we have the upper bound of $\alpha_{t+1}$ as $\alpha_{t+1}\leq C_{\alpha}$ for any $t<k_{1}$.

Case 3: in the remaining proof, we only consider and explore the case $k_{1}\leq t\leq T$ when $\alpha_{T}>C_{\alpha}$.

From [Lemma 7](#Thmlemma7), for $k\geq k_{1}$, we have

$$ $\displaystyle\Phi(x_{k+1})\leq$ $\displaystyle\Phi(x_{k})-\frac{1}{2\alpha_{k+1}}\|\nabla\Phi(x_{k})\|^{2}-\frac{1}{4\alpha_{k+1}}\|\bar{\nabla}f(x_{k},y_{k}^{P_{k}},v_{k}^{Q_{k}})\|^{2}+\frac{\epsilon^{\prime}}{2\alpha_{k+1}},$ $$

which indicates that

$$ $\displaystyle\frac{\|\bar{\nabla}f(x_{k},y_{k}^{P_{k}},v_{k}^{Q_{k}})\|^{2}}{\alpha_{k+1}}\leq 4\big{(}\Phi(x_{k})-\Phi(x_{k+1})\big{)}+\frac{2\epsilon^{\prime}}{\alpha_{k+1}}.$ $$

By taking summation over $k=k_{1},\ldots,t$, we have

$$ $\displaystyle\sum_{k=k_{1}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k}^{P_{k}},v_{k}^{Q_{k}})\|^{2}}{\alpha_{k+1}}\leq$ $\displaystyle 4\sum_{k={k_{1}}}^{t}\big{(}\Phi(x_{k})-\Phi(x_{k+1})\big{)}+\sum_{k={k_{1}}}^{t}\frac{2\epsilon^{\prime}}{\alpha_{k+1}}$ $\displaystyle=$ $\displaystyle 4\big{(}\Phi(x_{k_{1}})-\Phi(x_{t+1})\big{)}+\sum_{k={k_{1}}}^{t}\frac{2\epsilon^{\prime}}{\alpha_{k+1}}.$ (12) $$

For $\Phi(x_{k_{1}})$, by telescoping ([6](#A5.E6)), we get

$$ $\displaystyle\Phi(x_{k_{1}})\leq$ $\displaystyle\Phi(x_{0})+\sum_{k=0}^{k_{1}-1}\frac{L_{\Phi}}{4\alpha_{k+1}^{2}}\|\bar{\nabla}f(x_{k},y_{k}^{P_{k}},v_{k}^{Q_{k}})\|^{2}+\sum_{k=0}^{k_{1}-1}\frac{\epsilon^{\prime}}{2\alpha_{k+1}}.$ (13) $$

Plugging [eq. 13](#A5.E13) into [section E.4](#A5.Ex59), we obtain

$$ $\displaystyle\sum_{k=k_{1}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k}^{P_{k}},v_{k}^{Q_{k}})\|^{2}}{\alpha_{k+1}}\leq$ $\displaystyle 4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\sum_{k=0}^{k_{1}-1}\frac{L_{\Phi}}{\alpha_{k+1}^{2}}\|\bar{\nabla}f(x_{k},y_{k}^{P_{k}},v_{k}^{Q_{k}})\|^{2}+\sum_{k=0}^{t}\frac{2\epsilon^{\prime}}{\alpha_{k+1}}$ $\displaystyle\leq$ $\displaystyle 4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{L_{\Phi}\sum_{k=0}^{k_{1}-1}\|\bar{\nabla}f(x_{k},y_{k}^{P_{k}},v_{k}^{Q_{k}})\|^{2}}{\alpha_{0}^{2}}+\sum_{k=0}^{t}\frac{2\epsilon^{\prime}}{\alpha_{k+1}}$ $\displaystyle\leq$ $\displaystyle 4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{L_{\Phi}\alpha_{k_{1}}^{2}}{\alpha_{0}^{2}}+\frac{2(t+1)\epsilon^{\prime}}{\alpha_{0}}$ $\displaystyle\leq$ $\displaystyle 4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{L_{\Phi}C_{\alpha}^{2}}{\alpha_{0}^{2}}+\frac{2(t+1)\epsilon^{\prime}}{\alpha_{0}}.$ (14) $$

Inspired by [] and using telescoping, we have

$$ $\displaystyle\alpha_{t+1}=$ $\displaystyle\alpha_{t}+\frac{\|\bar{\nabla}f(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}})\|^{2}}{\alpha_{t+1}+\alpha_{t}}$ $\displaystyle\leq$ $\displaystyle\alpha_{t}+\frac{\|\bar{\nabla}f(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}})\|^{2}}{\alpha_{t+1}}$ $\displaystyle\leq$ $\displaystyle\alpha_{k_{1}}+\sum_{k=k_{1}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k}^{P_{k}},v_{k}^{Q_{k}})\|^{2}}{\alpha_{k+1}}$ $\displaystyle\leq$ $\displaystyle C_{\alpha}+4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{L_{\Phi}C_{\alpha}^{2}}{\alpha_{0}^{2}}+\frac{2(t+1)\epsilon^{\prime}}{\alpha_{0}}.$ $$

Thus, the proof is complete.
∎

###### Lemma 8 .

###### Proof.

### E.5 Convergence Analysis of Sub-loops

###### Lemma 9 .

Recall that for the $t_{th}$ iteration, the sub-loops in [Algorithm 1](#alg1) aim to find $y_{t}^{P_{t}}$ and $v_{t}^{Q_{t}}$ such that $\|\nabla_{y}g(x_{t},y_{t}^{P_{t}})\|^{2}\leq\epsilon_{y}$ and $\|\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}})\|^{2}\leq\epsilon_{v}$.
Here we prove that

$$ $\displaystyle P_{t}\leq P^{\prime}:=\frac{\log(C_{\beta}^{2}/\beta_{0}^{2})}{\log(1+\epsilon_{y}/C_{\beta}^{2})}+\frac{\beta_{\text{max}}}{\mu}\log\big{(}\frac{L_{g,1}^{2}(\beta_{\text{max}}-C_{\beta})}{\epsilon_{y}}\big{)},$ (15a) $\displaystyle Q_{t}\leq Q^{\prime}:=\frac{\log(C_{\gamma}^{2}/\gamma_{0}^{2})}{\log(1+\epsilon_{v}/C_{\gamma}^{2})}+\frac{\gamma_{\text{max}}}{\mu}\log\big{(}\frac{C_{g_{yy}}^{2}(\gamma_{\text{max}}-C_{\gamma})}{\epsilon_{v}}\big{)},$ (15b) $$

where $\beta_{\text{max}}:=C_{\beta}+L_{g,1}\big{(}\frac{2\epsilon_{y}}{\mu^{2}}+\frac{2C_{g_{xy}}^{2}C_{f}^{2}}{\mu^{2}\alpha_{0}^{2}}+2\log(C_{\beta}/\beta_{0})+1\big{)}$ and $\gamma_{\text{max}}:=C_{\gamma}+C_{g_{yy}}\big{(}\frac{2\epsilon_{y}}{\mu^{2}}+\frac{8C_{f_{y}}^{2}}{\mu^{2}}+2\log(C_{\gamma}/\gamma_{0})+1\big{)}$.

###### Proof.

The proof is split into the following two parts.

Part I: maximum number for convergence of $g(x_{t},y_{t}^{P_{t}})$.

Inspired by [], we split the analysis into the following two cases.

Case 1: $k_{2}$ does not exist before we find $P_{t}$. This indicates $\beta_{P_{t}}<C_{\beta}$.
Referring to Lemma 2 in [], we have $P_{t}<\frac{\log(C_{\beta}^{2}/\beta_{0}^{2})}{\log(1+\epsilon_{y}/C_{\beta}^{2})}$ and therefore the desired upper bound for $P_{t}$ holds. This can be proved as follows. If $P_{t}\geq\frac{\log(C_{\beta}^{2}/\beta_{0}^{2})}{\log(1+\epsilon_{y}/C_{\beta}^{2})}$, we have the following result.

$$ $\displaystyle\beta_{P_{t}}^{2}=$ $\displaystyle\beta_{P_{t}-1}^{2}+\|\nabla_{y}g(x_{t},y_{t}^{P_{t}-1})\|^{2}$ $\displaystyle=$ $\displaystyle\beta_{P_{t}-1}^{2}\Big{(}1+\frac{\|\nabla_{y}g(x_{t},y_{t}^{P_{t}-1})\|^{2}}{\beta_{P_{t}-1}^{2}}\Big{)}$ $\displaystyle\geq$ $\displaystyle\beta_{0}^{2}\prod_{p=0}^{P_{t}-1}\Big{(}1+\frac{\|\nabla_{y}g(x_{t},y_{t}^{p})\|^{2}}{\beta_{p}^{2}}\Big{)}$ $\displaystyle\geq$ $\displaystyle\beta_{0}^{2}\Big{(}1+\frac{\epsilon_{y}}{C_{\beta}^{2}}\Big{)}^{P_{t}}\geq C_{\beta}^{2}.$ (16) $$

This contradicts $\beta_{P_{t}}<C_{\beta}$.

Case 2: $k_{2}$ exists and $P_{t}\geq k_{2}$. Here we have $\beta_{k_{2}}\leq C_{\beta}$ and $\beta_{k_{2}+1}>C_{\beta}$.

Firstly, we prove $k_{2}\leq\frac{\log(C_{\beta}^{2}/\beta_{0}^{2})}{\log(1+\epsilon_{y}/C_{\beta}^{2})}$.
Similar to Case 1, if $k_{2}>\frac{\log(C_{\beta}^{2}/\beta_{0}^{2})}{\log(1+\epsilon_{y}/C_{\beta}^{2})}$, following [section E.5](#A5.Ex1)by replacing $P_{t}$ with $k_{2}$, we have

$$ $\displaystyle\beta_{k_{2}}^{2}\geq\beta_{0}^{2}\Big{(}1+\frac{\epsilon_{y}}{C_{\beta}^{2}}\Big{)}^{k_{2}}>C_{\beta}^{2},$ $$

which contradicts $\beta_{k_{2}}\leq C_{\beta}$.

Secondly, referring to Lemma 3 in [], we have the bound of $\|y_{t}^{k_{2}}-y^{*}(x_{t})\|^{2}$ as

$$ $\displaystyle\|y_{t}^{k_{2}}$ $\displaystyle-y^{*}(x_{t})\|^{2}$ $\displaystyle=$ $\displaystyle\bigg{\|}y_{t}^{k_{2}-1}-\frac{\nabla_{y}g(x_{t},y_{t}^{k_{2}-1})}{\beta_{k_{2}}}-y^{*}(x_{t})\bigg{\|}^{2}$ $\displaystyle=$ $\displaystyle\|y_{t}^{k_{2}-1}-y^{*}(x_{t})\|^{2}+\bigg{\|}\frac{\nabla_{y}g(x_{t},y_{t}^{k_{2}})}{\beta_{k_{2}}}\bigg{\|}^{2}-2\bigg{\langle}y_{t}^{k_{2}-1}-y^{*}(x_{t}),\frac{\nabla_{y}g(x_{t},y_{t}^{k_{2}-1})}{\beta_{k_{2}}}\bigg{\rangle}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\|y_{t}^{k_{2}-1}-y^{*}(x_{t})\|^{2}+\bigg{\|}\frac{\nabla_{y}g(x_{t},y_{t}^{k_{2}-1})}{\beta_{k_{2}}}\bigg{\|}^{2}-\frac{2}{\beta_{k_{2}}L_{g,1}}\big{\|}\nabla_{y}g(x_{t},y_{t}^{k_{2}-1})-\nabla_{y}g\big{(}x_{t},y^{*}(x_{t})\big{)}\big{\|}^{2}$ $\displaystyle\leq$ $\displaystyle\|y_{t}^{k_{2}-1}-y^{*}(x_{t})\|^{2}+\frac{\|\nabla_{y}g(x_{t},y_{t}^{k_{2}-1})\|^{2}}{\beta_{k_{2}}^{2}}$ $\displaystyle\leq$ $\displaystyle\|y_{t}^{0}-y^{*}(x_{t})\|^{2}+\sum_{p=0}^{k_{2}-1}\frac{\|\nabla_{y}g(x_{t},y_{t}^{p})\|^{2}}{\beta_{p+1}^{2}}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\|y_{t-1}^{P_{t-1}}-y^{*}(x_{t})\|^{2}+\sum_{p=0}^{k_{2}-1}\frac{\|\nabla_{y}g(x_{t},y_{t}^{p})\|^{2}/\beta_{0}^{2}}{\sum_{k=0}^{p}\|\nabla_{y}g(x_{t},y_{t}^{k})\|^{2}/\beta_{0}^{2}}$ $\displaystyle\overset{(c)}{\leq}$ $\displaystyle 2\|y_{t-1}^{P_{t-1}}-y^{*}(x_{t-1})\|^{2}+2\|y^{*}(x_{t-1})-y^{*}(x_{t})\|^{2}+\log\bigg{(}\sum_{p=0}^{k_{2}-1}\frac{\|\nabla_{y}g(x_{t},y_{t}^{p})\|^{2}}{\beta_{0}^{2}}\bigg{)}+1$ $\displaystyle\overset{(d)}{\leq}$ $\displaystyle\frac{2\epsilon_{y}}{\mu^{2}}+\frac{2C_{g_{xy}}^{2}\|\bar{\nabla}f(x_{t-1},y_{t-1}^{P_{t-1}},v_{t-1}^{Q_{t-1}})\|^{2}}{\mu^{2}\alpha_{t}^{2}}+\log\bigg{(}\sum_{p=0}^{k_{2}-1}\frac{\|\nabla_{y}g(x_{t},y_{t}^{p})\|^{2}}{\beta_{0}^{2}}\bigg{)}+1$ $\displaystyle\overset{(e)}{\leq}$ $\displaystyle\frac{2\epsilon_{y}}{\mu^{2}}+\frac{2C_{g_{xy}}^{2}C_{f}^{2}}{\mu^{2}\alpha_{0}^{2}}+2\log(C_{\beta}/\beta_{0})+1,$ (17) $$

where (a) uses Assumptions [1](#Thmassumption1),[2](#Thmassumption2); (b) refers to the warm start of $y_{t}^{0}$;
(c) uses [Lemma 1](#Thmlemma1); (d) uses Lemmas [2](#Thmlemma2) and [5](#Thmlemma5); (e) follows from [Lemma 6](#Thmlemma6) and $\beta_{k_{2}}\leq C_{\beta}$.

Last, following [], for all $P>k_{2}$, we have the bound of $\|y_{t}^{P}-y^{*}(x_{t})\|^{2}$ as

$$ $\displaystyle\|y_{t}^{P}-y^{*}(x_{t})\|^{2}=$ $\displaystyle\|y_{t}^{P-1}-y^{*}(x_{t})\|^{2}+\frac{\|\nabla_{y}g(x_{t},y_{t}^{P-1})\|^{2}}{\beta_{P}^{2}}-\frac{2\big{\langle}y_{t}^{P-1}-y^{*}(x_{t}),\nabla_{y}g(x_{t},y_{t}^{P-1})\big{\rangle}}{\beta_{P}}$ $\displaystyle\leq$ $\displaystyle\|y_{t}^{P-1}-y^{*}(x_{t})\|^{2}-\frac{1}{\beta_{P}}\Big{(}2-\frac{L_{g,1}}{\beta_{P}}\Big{)}\big{\langle}y_{t}^{P-1}-y^{*}(x_{t}),\nabla_{y}g(x_{t},y_{t}^{P-1})\big{\rangle}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\|y_{t}^{P-1}-y^{*}(x_{t})\|^{2}-\frac{1}{\beta_{P}}\big{\langle}y_{t}^{P-1}-y^{*}(x_{t}),\nabla_{y}g(x_{t},y_{t}^{P-1})\big{\rangle}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\Big{(}1-\frac{\mu}{\beta_{P}}\Big{)}\|y_{t}^{P-1}-y^{*}(x_{t})\|^{2}$ $\displaystyle\overset{(c)}{\leq}$ $\displaystyle e^{-{\mu(P-k_{2})}/{\beta_{P}}}\|y_{t}^{k_{2}}-y^{*}(x_{t})\|^{2}$ $\displaystyle\overset{(d)}{\leq}$ $\displaystyle e^{-{\mu(P-k_{2})}/{\beta_{P}}}\bigg{(}\frac{2\epsilon_{y}}{\mu^{2}}+\frac{2C_{g_{xy}}^{2}C_{f}^{2}}{\mu^{2}\alpha_{0}^{2}}+2\log(C_{\beta}/\beta_{0})+1\bigg{)},$ (18) $$

where (a) uses $\beta_{P}\geq C_{\beta}\geq L_{g,1}$; (b) uses Assumption [1](#Thmassumption1); (c) follows from $\beta_{P}\geq C_{\beta}\geq L_{g,1}\geq\mu$ and $1-m\leq e^{-m}$ for $0<m<1$; (d) refers to [section E.5](#A5.Ex5). Inspired by Lemma 4 in [], we have the upper-bound of $\beta_{P}$ as

$$ $\displaystyle\beta_{P}=\beta_{P-1}+\frac{\|\nabla_{y}g(x_{t},y_{t}^{P-1})\|^{2}}{\beta_{P}+\beta_{P-1}}\leq\beta_{k_{2}}+\sum_{p=k_{2}}^{P-1}\frac{\|\nabla_{y}g(x_{t},y_{t}^{p})\|^{2}}{\beta_{p+1}}.$ (19) $$

To further bound the last term of the right-hand side of [eq. 19](#A5.E19), using Assumption [2](#Thmassumption2), we have the following result:

$$ $\displaystyle\|y_{t}^{P}$ $\displaystyle-y^{*}(x_{t})\|^{2}$ $\displaystyle=$ $\displaystyle\|y_{t}^{P-1}-y^{*}(x_{t})\|^{2}+\frac{\|\nabla_{y}g(x_{t},y_{t}^{P-1})\|^{2}}{\beta_{P}^{2}}-\frac{2\big{\langle}y_{t}^{P-1}-y^{*}(x_{t}),\nabla_{y}g(x_{t},y_{t}^{P-1})\big{\rangle}}{\beta_{P}}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\|y_{t}^{P-1}-y^{*}(x_{t})\|^{2}+\frac{\|\nabla_{y}g(x_{t},y_{t}^{P-1})\|^{2}}{\beta_{P}^{2}}-\frac{2\|\nabla_{y}g(x_{t},y_{t}^{P-1})-\nabla_{y}g(x_{t},y^{*}(x_{t}))\|^{2}}{\beta_{P}L_{g,1}}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\|y_{t}^{P-1}-y^{*}(x_{t})\|^{2}-\frac{\|\nabla_{y}g(x_{t},y_{t}^{P-1})\|^{2}}{\beta_{P}L_{g,1}}$ $\displaystyle{\leq}$ $\displaystyle\|y_{t}^{k_{2}}-y^{*}(x_{t})\|^{2}-\sum_{p=k_{2}}^{P-1}\frac{\|\nabla_{y}g(x_{t},y_{t}^{p})\|^{2}}{\beta_{p+1}L_{g,1}},$ (20) $$

where (a) uses Assumptions [1](#Thmassumption1),[2](#Thmassumption2); (b) refers to $\beta_{P}\geq C_{\beta}\geq L_{g,1}$. By rearranging [section E.5](#A5.Ex19) and using [section E.5](#A5.Ex5), we have

$$ $\displaystyle\sum_{p=k_{2}}^{P-1}\frac{\|\nabla_{y}g(x_{t},y_{t}^{p})\|^{2}}{\beta_{p+1}}\leq$ $\displaystyle L_{g,1}\big{(}\|y_{t}^{k_{2}}-y^{*}(x_{t})\|^{2}-\|y_{t}^{P}-y^{*}(x_{t})\|^{2}\big{)}$ $\displaystyle\leq$ $\displaystyle L_{g,1}\|y_{t}^{k_{2}}-y^{*}(x_{t})\|^{2}$ $\displaystyle\leq$ $\displaystyle L_{g,1}\bigg{(}\frac{2\epsilon_{y}}{\mu^{2}}+\frac{2C_{g_{xy}}^{2}C_{f}^{2}}{\mu^{2}\alpha_{0}^{2}}+2\log(C_{\beta}/\beta_{0})+1\bigg{)}.$ (21) $$

Plugging [section E.5](#A5.Ex23) into [eq. 19](#A5.E19), we obtain the upper-bound of $\beta_{P}$ as

$$ $\displaystyle\beta_{P}\leq C_{\beta}+L_{g,1}\bigg{(}\frac{2\epsilon_{y}}{\mu^{2}}+\frac{2C_{g_{xy}}^{2}C_{f}^{2}}{\mu^{2}\alpha_{0}^{2}}+2\log(C_{\beta}/\beta_{0})+1\bigg{)}=:\beta_{\text{max}}.$ (22) $$

Then, by plugging [eq. 22](#A5.E22) into [section E.5](#A5.Ex14),
we have the upper bound of $\|y_{t}^{P}-y^{*}(x_{t})\|^{2}$ as

$$ $\displaystyle\|y_{t}^{P}-y^{*}(x_{t})\|^{2}\leq e^{-{\mu(P-k_{2})}/{\beta_{\text{max}}}}\bigg{(}\frac{2\epsilon_{y}}{\mu^{2}}+\frac{2C_{g_{xy}}^{2}C_{f}^{2}}{\mu^{2}\alpha_{0}^{2}}+2\log(C_{\beta}/\beta_{0})+1\bigg{)}.$ (23) $$

Recall we have the upper bound $k_{2}\leq\frac{\log(C_{\beta}^{2}/\beta_{0}^{2})}{\log(1+\epsilon_{y}/C_{\beta}^{2})}$.
Note that $P^{\prime}$ defined in ([15a](#A5.E15.1)) satisfies

$$ $\displaystyle P^{\prime}\geq k_{2}+\frac{\beta_{\text{max}}}{\mu}\log\big{(}{L_{g,1}^{2}(\beta_{\text{max}}-C_{\beta})}/{\epsilon_{y}}\big{)}.$ $$

By replacing $P$ with $P^{\prime}$ in [eq. 23](#A5.E23),
we have

$$ $\displaystyle\|\nabla_{y}g(x_{t},y_{t}^{P^{\prime}})\|^{2}\leq L_{g,1}^{2}\|y_{t}^{P^{\prime}}-y^{*}(x_{t})\|^{2}\leq e^{-{\mu(P^{\prime}-k_{2})}/{\beta_{\text{max}}}}L_{g,1}^{2}(\beta_{\text{max}}-C_{\beta})\leq\epsilon_{y}.$ $$

Therefore, $P_{t}\leq P^{\prime}$ and this completes the proof of ([15a](#A5.E15.1)).

Part II: maximum number for convergence of $R(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}})$.

Similarly to Part I, we split the analysis into the following two cases.

Case 1: $k_{3}$ does not exist before we find $Q_{t}$. This indicates $\gamma_{Q_{t}}<C_{\gamma}$.
Then we have $Q_{t}<\frac{\log(C_{\gamma}^{2}/\gamma_{0}^{2})}{\log(1+\epsilon_{v}/C_{\gamma}^{2})}$.
Otherwise, if $Q_{t}\geq\frac{\log(C_{\gamma}^{2}/\gamma_{0}^{2})}{\log(1+\epsilon_{v}/C_{\gamma}^{2})}$, we have the following result.

$$ $\displaystyle\gamma_{Q_{t}}^{2}=$ $\displaystyle\gamma_{Q_{t}-1}^{2}+\|\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}-1})\|^{2}$ $\displaystyle=$ $\displaystyle\gamma_{Q_{t}-1}^{2}\Big{(}1+\frac{\|\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}-1})\|^{2}}{\gamma_{Q_{t}-1}^{2}}\Big{)}$ $\displaystyle\geq$ $\displaystyle\gamma_{0}^{2}\prod_{q=0}^{Q_{t}-1}\Big{(}1+\frac{\|\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}-1})\|^{2}}{\gamma_{Q_{t}-1}^{2}}\Big{)}$ $\displaystyle\geq$ $\displaystyle\gamma_{0}^{2}\Big{(}1+\frac{\epsilon_{v}}{C_{\gamma}^{2}}\Big{)}^{Q_{t}}\geq C_{\gamma}^{2}.$ $$

This contradicts $\gamma_{Q_{t}}<C_{\gamma}$.

Case 2: $k_{3}$ exists and $Q_{t}\geq k_{3}$. Here we have $\gamma_{k_{3}}\leq C_{\gamma}$ and $\gamma_{k_{3}+1}>C_{\gamma}$.

Firstly, we have $k_{3}\leq\frac{\log(C_{\gamma}^{2}/\gamma_{0}^{2})}{\log(1+\epsilon_{v}/C_{\gamma}^{2})}$.
Similar to Case 1, if $k_{3}>\frac{\log(C_{\gamma}^{2}/\gamma_{0}^{2})}{\log(1+\epsilon_{v}/C_{\gamma}^{2})}$, following [section E.5](#A5.Ex1), by replacing $Q_{t}$ with $k_{3}$, we have

$$ $\displaystyle\gamma_{k_{3}}^{2}\geq\gamma_{0}^{2}\Big{(}1+\frac{\epsilon_{v}}{C_{\gamma}^{2}}\Big{)}^{k_{3}}>C_{\gamma}^{2},$ $$

which contradicts $\gamma_{k_{3}}\leq C_{\gamma}$.

Secondly, referring to Lemma 3 in [], we have the bound of $\|v_{t}^{k_{3}}-v^{*}(x_{t})\|^{2}$ as following:

$$ $\displaystyle\big{\|}v_{t}^{k_{3}}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}=$ $\displaystyle\bigg{\|}v_{t}^{k_{3}-1}-\frac{\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{k_{3}-1})}{\gamma_{k_{3}}}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\bigg{\|}^{2}$ $\displaystyle=$ $\displaystyle\big{\|}v_{t}^{k_{3}-1}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}+\bigg{\|}\frac{\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{k_{3}-1})}{\gamma_{k_{3}}}\bigg{\|}^{2}$ $\displaystyle-\frac{2}{\gamma_{k_{3}}}\big{\langle}v_{t}^{k_{3}-1}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}}),\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{k_{3}-1})\big{\rangle}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\big{\|}v_{t}^{k_{3}-1}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}+\bigg{\|}\frac{\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{k_{3}-1})}{\gamma_{k_{3}}}\bigg{\|}^{2}$ $\displaystyle-\frac{2}{\gamma_{k_{3}}C_{g_{yy}}}\big{\|}\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{k_{3}-1})-\nabla_{v}R\big{(}x_{t},y_{t}^{P_{t}},\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{)}\big{\|}^{2}$ $\displaystyle\leq$ $\displaystyle\big{\|}v_{t}^{k_{3}-1}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}+\bigg{\|}\frac{\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{k_{3}-1})}{\gamma_{k_{3}}}\bigg{\|}^{2}$ $\displaystyle\leq$ $\displaystyle\big{\|}v_{t}^{0}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}+\sum_{q=0}^{k_{3}-1}\bigg{\|}\frac{\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{q})}{\gamma_{k_{3}}}\bigg{\|}^{2}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\big{\|}v_{t}^{0}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}+\sum_{q=0}^{k_{3}-1}\frac{\|\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{q})\|^{2}/\gamma_{0}^{2}}{\sum_{k=0}^{q}\|\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{k})\|^{2}/\gamma_{0}^{2}}$ $\displaystyle\overset{(c)}{\leq}$ $\displaystyle 2\big{\|}v_{t-1}^{P_{t-1}}-\hat{v}^{*}(x_{t-1},y_{t-1}^{P_{t-1}})\big{\|}^{2}+2\big{\|}\hat{v}^{*}(x_{t-1},y_{t-1}^{P_{t-1}})-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}$ $\displaystyle+\log\bigg{(}\sum_{q=0}^{k_{3}-1}\|\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{k})\|^{2}/\gamma_{0}^{2}\bigg{)}+1$ $\displaystyle\leq$ $\displaystyle 2\big{\|}v_{t-1}^{P_{t-1}}-\hat{v}^{*}(x_{t-1},y_{t-1}^{P_{t-1}})\big{\|}^{2}+4\big{\|}\hat{v}^{*}(x_{t-1},y_{t-1}^{P_{t-1}})\big{\|}^{2}+4\big{\|}\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}$ $\displaystyle+\log\bigg{(}\sum_{q=0}^{k_{3}-1}\|\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{k})\|^{2}/\gamma_{0}^{2}\bigg{)}+1$ $\displaystyle\overset{(d)}{\leq}$ $\displaystyle\frac{2\epsilon_{y}}{\mu^{2}}+\frac{8C_{f_{y}}^{2}}{\mu^{2}}+2\log(C_{\gamma}/\gamma_{0})+1,$ (24) $$

where (a) uses [Lemma 3](#Thmlemma3) and $\nabla_{v}R\big{(}x_{t},y_{t}^{P_{t}},\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{)}=0$;
(b) refers to the warm start of $v_{t}^{0}$;
(c) uses [Lemma 1](#Thmlemma1);
(d) follows from [Lemma 3](#Thmlemma3),[5](#Thmlemma5) and $\gamma_{k_{3}}\leq C_{\gamma}$.

Last, similar to Part I, for all $Q>k_{3}$, we explore the bound of $\|v_{t}^{Q}-v^{*}(x_{t})\|^{2}$ as

$$ $\displaystyle\big{\|}v_{t}^{Q}$ $\displaystyle-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}$ $\displaystyle=$ $\displaystyle\big{\|}v_{t}^{Q-1}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}+\frac{\|\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q-1})\|^{2}}{\gamma_{Q}^{2}}$ $\displaystyle-\frac{2\big{\langle}v_{t}^{Q-1}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}}),\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q-1})\big{\rangle}}{\gamma_{Q}}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\big{\|}v_{t}^{Q-1}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}-\frac{1}{\gamma_{Q}}\Big{(}2-\frac{C_{g_{yy}}}{\gamma_{Q}}\Big{)}\big{\langle}v_{t}^{Q-1}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}}),\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q-1})\big{\rangle}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\big{\|}v_{t}^{Q-1}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}-\frac{1}{\gamma_{Q}}\big{\langle}v_{t}^{Q-1}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}}),\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q-1})\big{\rangle}$ $\displaystyle\overset{(c)}{\leq}$ $\displaystyle\Big{(}1-\frac{\mu}{\gamma_{Q}}\Big{)}\big{\|}v_{t}^{Q-1}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}$ $\displaystyle\overset{(d)}{\leq}$ $\displaystyle e^{-{\mu(Q-k_{3})}/{\gamma_{Q}}}\big{\|}v_{t}^{k_{3}}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}$ $\displaystyle\overset{(e)}{\leq}$ $\displaystyle e^{-{\mu(Q-k_{3})}/{\gamma_{Q}}}\Big{(}\frac{2\epsilon_{y}}{\mu^{2}}+\frac{8C_{f_{y}}^{2}}{\mu^{2}}+2\log(C_{\gamma}/\gamma_{0})+1\Big{)},$ (25) $$

where (a) uses [Lemma 3](#Thmlemma3);
(b) follows from $\gamma_{Q}>C_{\gamma}\geq C_{g_{yy}}$;
(c) uses $\nabla_{v}R\big{(}x_{t},y_{t}^{P_{t}},\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{)}=0$ and [Lemma 3](#Thmlemma3);
(d) follows from $\gamma_{Q}\geq C_{\gamma}\geq C_{g_{yy}}\geq\mu$ and $1-m\leq e^{-m}$ for $0<m<1$;
(e) uses [section E.5](#A5.Ex32).
Similar to [eq. 19](#A5.E19), we have the upper-bound of $\gamma_{Q}$ as

$$ $\displaystyle\gamma_{Q}=\gamma_{Q-1}+\frac{\|\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q-1})\|^{2}}{\gamma_{Q}+\gamma_{Q-1}}\leq\gamma_{k_{3}}+\sum_{q=k_{3}}^{Q-1}\frac{\|\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{q})\|^{2}}{\gamma_{q+1}}.$ (26) $$

To further bound the last term on the right-hand side of [eq. 26](#A5.E26), we can have the following result:

$$ $\displaystyle\big{\|}v_{t}^{Q}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}=$ $\displaystyle\big{\|}v_{t}^{Q-1}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}+\frac{\|\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q-1})\|^{2}}{\gamma_{Q}^{2}}$ $\displaystyle-\frac{2\big{\langle}v_{t}^{Q}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}}),\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q-1})\big{\rangle}}{\gamma_{Q}}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\big{\|}v_{t}^{Q-1}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}+\frac{\|\|\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q-1})\|^{2}}{\gamma_{Q}^{2}}$ $\displaystyle-\frac{2\big{\|}\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q-1})-\nabla_{v}R\big{(}x_{t},y_{t}^{P_{t}},\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{)}\big{\|}^{2}}{\gamma_{Q}C_{g_{yy}}}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\big{\|}v_{t}^{Q-1}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}-\frac{\big{\|}\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q-1})\big{\|}^{2}}{\gamma_{Q}C_{g_{yy}}}$ $\displaystyle\leq$ $\displaystyle\big{\|}v_{t}^{k_{3}}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}-\sum_{q=k_{3}}^{Q-1}\frac{\big{\|}\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{q})\big{\|}^{2}}{\gamma_{q+1}C_{g_{yy}}},$ (27) $$

where (a) uses [Lemma 3](#Thmlemma3); (b) refers to $\gamma_{Q}\geq C_{\gamma}\geq C_{g_{yy}}$. By rearranging [section E.5](#A5.Ex51a) and using [section E.5](#A5.Ex32), we have

$$ $\displaystyle\sum_{q=k_{3}}^{Q-1}\frac{\big{\|}\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{q})\big{\|}^{2}}{\gamma_{q+1}}\leq$ $\displaystyle C_{g_{yy}}\big{(}\big{\|}v_{t}^{k_{3}}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}-\big{\|}v_{t}^{Q}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}\big{)}$ $\displaystyle\leq$ $\displaystyle C_{g_{yy}}\bigg{(}\frac{2\epsilon_{y}}{\mu^{2}}+\frac{8C_{f_{y}}^{2}}{\mu^{2}}+2\log(C_{\gamma}/\gamma_{0})+1\bigg{)}.$ (28) $$

Plugging [eq. 23](#A5.E23) into [section E.5](#A5.Ex19), we obtain the upper-bound of $\gamma_{Q}$ as

$$ $\displaystyle\gamma_{Q}\leq C_{\gamma}+C_{g_{yy}}\bigg{(}\frac{2\epsilon_{y}}{\mu^{2}}+\frac{8C_{f_{y}}^{2}}{\mu^{2}}+2\log(C_{\gamma}/\gamma_{0})+1\bigg{)}=:\gamma_{\text{max}}.$ (29) $$

Then, we have the upper bound of $\|v_{t}^{Q}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\|^{2}$ as

$$ $\displaystyle\big{\|}v_{t}^{Q}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}\leq e^{-{\mu(Q_{t}-k_{3})}/{\gamma_{\text{max}}}}\bigg{(}\frac{2\epsilon_{y}}{\mu^{2}}+\frac{8C_{f_{y}}^{2}}{\mu^{2}}+2\log(C_{\gamma}/\gamma_{0})+1\bigg{)}.$ (30) $$

Recall we have the upper bound $k_{3}\leq\frac{\log(C_{\gamma}^{2}/\gamma_{0}^{2})}{\log(1+\epsilon_{v}/C_{\gamma}^{2})}$.
Note that $Q^{\prime}$ defined in ([15b](#A5.E15.2)) satisfies

$$ $\displaystyle Q^{\prime}\geq k_{3}+\frac{\gamma_{\text{max}}}{\mu}\log\big{(}{C_{g_{yy}}^{2}(\gamma_{\text{max}}-C_{\gamma})}/{\epsilon_{v}}\big{)}.$ $$

By replacing $Q$ with $Q^{\prime}$ in [eq. 30](#A5.E30), we have

$$ $\displaystyle\|\nabla_{v}R(x_{t},y_{t}^{P_{t}},v_{t}^{Q^{\prime}})\|^{2}\leq C_{g_{yy}}^{2}\big{\|}v_{t}^{Q^{\prime}}-\hat{v}^{*}(x_{t},y_{t}^{P_{t}})\big{\|}^{2}\leq e^{-{\mu(Q^{\prime}-k_{3})}/{\gamma_{\text{max}}}}(\gamma_{\text{max}}-C_{\gamma})\leq\epsilon_{v}.$ $$

Therefore, $Q_{t}\leq Q^{\prime}$ and this completes the proof of ([15b](#A5.E15.2)).
Thus, the proof is complete.
∎

###### Lemma 9 .

###### Proof.

### E.6 Proof of Theorem 1

Here we suppose the total iteration round is $T$.
According to [Lemma 4](#Thmlemma4), the proof can be split into the following two cases.

Case 1: $k_{1}$ does not exist. Based on [Lemma 4](#Thmlemma4), we have $\alpha_{T}\leq C_{\alpha}$.
Then by [Lemma 7](#Thmlemma7) we have

$$ $\displaystyle\frac{\|\nabla\Phi(x_{t})\|^{2}}{\alpha_{t+1}}\leq 2\big{(}\Phi(x_{t})-\Phi(x_{t+1})\big{)}+\frac{L_{\Phi}}{2\alpha_{t+1}^{2}}\|\bar{\nabla}f(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}})\|^{2}+\frac{\epsilon^{\prime}}{\alpha_{t+1}},$ $$

where $\epsilon^{\prime}$ is defined in [Lemma 7](#Thmlemma7).
By taking the average, we have

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\frac{\|\nabla\Phi(x_{t})\|^{2}}{\alpha_{t+1}}\leq$ $\displaystyle\frac{2}{T}\big{(}\Phi(x_{0})-\Phi(x_{T})\big{)}+\frac{L_{\Phi}}{2\alpha_{0}^{2}}\frac{1}{T}\sum_{t=0}^{T-1}\big{\|}\bar{\nabla}f(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}})\big{\|}^{2}+\frac{1}{T}\sum_{t=0}^{T-1}\frac{\epsilon^{\prime}}{\alpha_{t+1}}$ $\displaystyle\leq$ $\displaystyle\frac{1}{T}\bigg{(}2\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{L_{\Phi}C_{\alpha}^{2}}{2\alpha_{0}^{2}}\bigg{)}+\frac{\epsilon^{\prime}}{\alpha_{0}}=\frac{c_{0}}{T}+\frac{\epsilon^{\prime}}{\alpha_{0}},$ (31) $$

where $c_{0}$ is defined by [eq. 11](#A5.E11) in [Lemma 8](#Thmlemma8).

Case 2: $k_{1}$ exists.
For $t<k_{1}$, according to [Lemma 7](#Thmlemma7), we still have

$$ $\displaystyle\frac{\|\nabla\Phi(x_{t})\|^{2}}{\alpha_{t+1}}\leq 2\big{(}\Phi(x_{t})-\Phi(x_{t+1})\big{)}+\frac{L_{\Phi}}{2\alpha_{t+1}^{2}}\|\bar{\nabla}f(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}})\|^{2}+\frac{\epsilon^{\prime}}{\alpha_{t+1}}.$ (32) $$

For $t\geq k_{1}$, we have $\alpha_{t}\geq C_{\alpha}$. Using [Lemma 7](#Thmlemma7), we have

$$ $\displaystyle\frac{\|\nabla\Phi(x_{t})\|^{2}}{\alpha_{t+1}}\leq 2\big{(}\Phi(x_{t})-\Phi(x_{t+1})\big{)}+\frac{\epsilon^{\prime}}{\alpha_{t+1}}.$ (33) $$

By merging [eq. 32](#A5.E32) and [eq. 33](#A5.E33), and taking an average from $t=0,...,T-1$, we have

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\frac{\|\nabla\Phi(x_{t})\|^{2}}{\alpha_{t+1}}=$ $\displaystyle\frac{1}{T}\sum_{t=0}^{k_{1}-1}\frac{\|\nabla\Phi(x_{t})\|^{2}}{\alpha_{t+1}}+\frac{1}{T}\sum_{t=k_{1}}^{T-1}\frac{\|\nabla\Phi(x_{t})\|^{2}}{\alpha_{t+1}}$ $\displaystyle\leq$ $\displaystyle\frac{2}{T}\big{(}\Phi(x_{0})-\Phi(x_{T})\big{)}+\frac{L_{\Phi}}{2\alpha_{0}^{2}}\frac{1}{T}\sum_{t=0}^{k_{1}-1}\big{\|}\bar{\nabla}f(x_{t},y_{t}^{P_{t}},v_{t}^{Q_{t}})\big{\|}^{2}+\frac{1}{T}\sum_{t=0}^{T-1}\frac{\epsilon^{\prime}}{\alpha_{t+1}}$ $\displaystyle\leq$ $\displaystyle\frac{1}{T}\bigg{(}2\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{L_{\Phi}C_{\alpha}^{2}}{2\alpha_{0}^{2}}\bigg{)}+\frac{\epsilon^{\prime}}{\alpha_{0}}=\frac{c_{0}}{T}+\frac{\epsilon^{\prime}}{\alpha_{0}},$ (34) $$

where $c_{0}$ is defined in [Lemma 8](#Thmlemma8). This result is the same as [section E.6](#A5.Ex60a). Thus, for both Case 1 and Case 2, we have

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\frac{\|\nabla\Phi(x_{t})\|^{2}}{\alpha_{T}}\leq\frac{1}{T}\sum_{t=0}^{T-1}\frac{\|\nabla\Phi(x_{t})\|^{2}}{\alpha_{t+1}}\leq\frac{1}{T}\bigg{(}2\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{L_{\Phi}C_{\alpha}^{2}}{2\alpha_{0}^{2}}\bigg{)}+\frac{\epsilon^{\prime}}{\alpha_{0}},$ $$

which indicates that

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla\Phi(x_{t})\|^{2}\leq$ $\displaystyle\bigg{[}\frac{1}{T}\Big{(}2\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{L_{\Phi}C_{\alpha}^{2}}{2\alpha_{0}^{2}}\Big{)}+\frac{\epsilon^{\prime}}{\alpha_{0}}\bigg{]}\alpha_{T}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\frac{1}{T}\bigg{[}\Big{(}2\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{L_{\Phi}C_{\alpha}^{2}}{2\alpha_{0}^{2}}\Big{)}+\frac{T\epsilon^{\prime}}{\alpha_{0}}\bigg{]}$ $\displaystyle\times\bigg{[}C_{\alpha}+4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{L_{\Phi}C_{\alpha}^{2}}{\alpha_{0}^{2}}+\frac{2T\epsilon^{\prime}}{\alpha_{0}}\bigg{]},$ (35) $$

where (a) uses [Lemma 8](#Thmlemma8).
To achieve the $\mathcal{O}(1/T)$ convergence rate, we need $\epsilon^{\prime}=\mathcal{O}({1}/{T})$ in [section E.6](#A5.Ex64a). This can be guaranteed by taking $\epsilon_{y}=1/T$ and $\epsilon_{v}=1/T$, which implies (see [Lemma 7](#Thmlemma7))

$$ $\displaystyle\epsilon^{\prime}=\frac{1}{T}\bigg{[}\Big{(}\frac{2}{\mu^{2}}\big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\big{)}+1\Big{)}L_{g,1}^{2}\bar{L}^{2}+\frac{2\bar{L}^{2}}{\mu^{2}}\bigg{]}.$ (36) $$

For symbol convenience, here we define

$$ $\displaystyle c_{1}:=c_{0}+\frac{1}{\alpha_{0}}\bigg{[}\Big{(}\frac{2}{\mu^{2}}\big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\big{)}+1\Big{)}L_{g,1}^{2}\bar{L}^{2}+\frac{2\bar{L}^{2}}{\mu^{2}}\bigg{]},$ (37) $$

where $c_{0}$ is defined in [eq. 11](#A5.E11).
Thus, we can obtain

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla\Phi(x_{t})\|^{2}\leq\frac{c_{1}(C_{\alpha}+2c_{1})}{T}=\mathcal{O}\Big{(}\frac{1}{T}\Big{)}.$ $$

Thus, [Theorem 1](#Thmtheorem1) is proved.

### E.7 Complexity Analysis of Algorithm 1 (Proof of Corollary 1 )

Recall in [Theorem 1](#Thmtheorem1), we take $\epsilon_{y}=1/T$, $\epsilon_{v}=1/T$, and we obtain

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla\Phi(x_{t})\|^{2}\leq\frac{c_{1}(C_{\alpha}+2c_{1})}{T}.$ $$

To achieve $\epsilon$-accurate stationary point, we need

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla\Phi(x_{t})\|^{2}\leq\frac{c_{1}(C_{\alpha}+2c_{1})}{T}\leq\epsilon\quad\mbox{ i.e., }\quad T=\mathcal{O}(1/\epsilon).$ (38) $$

Recall in [Lemma 9](#Thmlemma9), we have

$$ $\displaystyle P_{t}\leq$ $\displaystyle\frac{\log(C_{\beta}^{2}/\beta_{0}^{2})}{\log(1+\epsilon_{y}/C_{\beta}^{2})}+\frac{\beta_{\text{max}}}{\mu}\log\big{(}\frac{L_{g,1}^{2}(\beta_{\text{max}}-C_{\beta})}{\epsilon_{y}}\big{)}$ $\displaystyle\leq$ $\displaystyle\frac{\log(C_{\beta}^{2}/\beta_{0}^{2})}{\log(1+1/C_{\beta}^{2}T)}+\frac{\beta_{\text{max}}}{\mu}\log\big{(}\frac{TL_{g,1}^{2}(\beta_{\text{max}}-C_{\beta})}{1}\big{)}=\mathcal{O}\bigg{(}\frac{1}{\log(1+\epsilon)}+\log\Big{(}\frac{1}{\epsilon}\Big{)}\bigg{)}.$ $$

When $\epsilon$ is sufficiently small, we have

$$ $\displaystyle P_{t}=\mathcal{O}\bigg{(}\frac{1}{\log(1+\epsilon)}+\log\Big{(}\frac{1}{\epsilon}\Big{)}\bigg{)}=\mathcal{O}\bigg{(}\frac{1}{\epsilon}+\log\Big{(}\frac{1}{\epsilon}\Big{)}\bigg{)}=\mathcal{O}(1/\epsilon).$ (39) $$

Similarly, we have

$$ $\displaystyle Q_{t}=\mathcal{O}\bigg{(}\frac{1}{\log(1+\epsilon)}+\log\Big{(}\frac{1}{\epsilon}\Big{)}\bigg{)}=\mathcal{O}\bigg{(}\frac{1}{\epsilon}+\log\Big{(}\frac{1}{\epsilon}\Big{)}\bigg{)}=\mathcal{O}(1/\epsilon).$ (40) $$

We denote ${\rm Gc}(\epsilon)$ as the gradient complexity, then we have

$$ $\displaystyle{\rm Gc}(\epsilon)=T\cdot\max_{t}\{P_{t}+Q_{t}\}=\mathcal{O}(1/\epsilon^{2}).$ $$

Therefore [Corollary 1](#Thmcorollary1) is proved.

## Appendix F Proof of Theorem 2

We define some notation for convenience before proving [Theorem 2](#Thmtheorem2).

### F.1 Notation

Below, we define several preset constants for notational convenience at their first use.
We first define some Lipschitzness parameters for $\Phi(x)$ as

$$ $\displaystyle L_{\Phi}:=$ $\displaystyle\Big{(}L_{f,1}+\frac{L_{g,2}C_{f_{y}}}{\mu}\Big{)}\Big{(}1+\frac{C_{g_{xy}}}{\mu}\Big{)}^{2}$ $\displaystyle\bar{L}:=$ $\displaystyle\max\Big{\{}2\Big{(}\frac{C_{f_{y}}^{2}L_{g,2}^{2}}{\mu^{2}}+L_{f,1}^{2}\Big{)}^{\frac{1}{2}},\sqrt{2}C_{g_{yy}}\Big{\}}.$ $$

Next, we define the following constants as thresholds for parameters $\beta_{k}$, $\gamma_{k}$, $\alpha_{k}$ as

$$ $\displaystyle C_{\alpha}:=$ $\displaystyle\max\Big{\{}{\frac{2L_{\Phi}}{\varphi_{0}}},{\alpha_{0}}\Big{\}},$ $\displaystyle C_{\beta}:=$ $\displaystyle\max\Big{\{}\mu+L_{g,1},\frac{2\mu L_{g,1}}{\mu+L_{g,1}},{\beta_{0}},64a_{0}^{2},1\Big{\}},$ $\displaystyle C_{\gamma}:=$ $\displaystyle\max\Big{\{}2(\mu+C_{g_{yy}}),\frac{\mu C_{g_{yy}}}{\mu+C_{g_{yy}}},{\gamma_{0}},64a_{0}^{2},1,C_{g_{yy}}\Big{\}},$ $\displaystyle C_{\varphi}:=$ $\displaystyle C_{\beta}+C_{\gamma},$ (41) $$

where the constant $\alpha_{0}$ is defined as

$$ $\displaystyle a_{0}:=$ $\displaystyle\Big{(}\big{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\big{)}\big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\big{)}^{2}\frac{1}{\mu^{2}}+1\Big{)}\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}C_{\beta}}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})(\mu+L_{g,1})L_{y}^{2}}{\mu^{3}L_{g,1}\varphi_{0}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}\gamma_{0}}.$ $$

### F.2 A rough bound of v k subscript 𝑣 𝑘 v_{k}

###### Lemma 10 .

Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2), for any $t\geq 0$ in Algorithm [2](#alg2), we have $\|v_{t}\|\leq\frac{\sqrt{2}}{\mu}{\varphi_{t+1}}+\frac{\sqrt{2}C_{f_{y}}}{\mu}\sqrt{t}$.

###### Proof.

By strong convexity of $g$ in Assumption [1](#Thmassumption1), we have

$$ $\displaystyle\sum_{k=1}^{t}\mu^{2}\|v_{k}\|^{2}\leq$ $\displaystyle\sum_{k=1}^{t}\|\nabla_{y}\nabla_{y}g(x_{k},y_{k})v_{k}\|^{2}$ $\displaystyle\leq$ $\displaystyle\sum_{k=1}^{t}2\|\nabla_{y}\nabla_{y}g(x_{k},y_{k})v_{k}-\nabla_{y}f(x_{k},y_{k})\|^{2}+\sum_{k=1}^{t}2\|\nabla_{y}f(x_{k},y_{k})\|^{2}$ $\displaystyle=$ $\displaystyle\sum_{k=1}^{t}2\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}+\sum_{k=1}^{t}2\|\nabla_{y}f(x_{k},y_{k})\|^{2}$ $\displaystyle\leq$ $\displaystyle 2\gamma_{t+1}^{2}+2tC_{f_{y}}^{2},$ $$

which indicates that for any $t\geq 0$, $\|v_{t}\|$ can be bounded as

$$ $\displaystyle\|v_{t}\|\leq\frac{\big{(}2\gamma_{t+1}^{2}+2tC_{f_{y}}^{2}\big{)}^{\frac{1}{2}}}{\mu}\leq\frac{\big{(}2\varphi_{t+1}^{2}+2tC_{f_{y}}^{2}\big{)}^{\frac{1}{2}}}{\mu}\leq\frac{\sqrt{2}\big{(}{\varphi_{t+1}}+\sqrt{t}C_{f_{y}}\big{)}}{\mu}.$ (42) $$

Then the proof is complete.
∎

###### Lemma 10 .

###### Proof.

### F.3 Descent in Objective Function

###### Lemma 11 .

Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2), for Algorithm [2](#alg2), suppose the total iteration number is $T$.
No matter $k_{1}$ in [Lemma 4](#Thmlemma4) exists or not, we always have

$$ $\displaystyle\Phi(x_{t+1})\leq$ $\displaystyle\Phi(x_{t})-\frac{1}{2\alpha_{t+1}\varphi_{t+1}}\|\nabla\Phi(x_{t})\|^{2}-\frac{1}{2\alpha_{t+1}\varphi_{t+1}}\Big{(}1-\frac{L_{\Phi}}{\alpha_{t+1}\varphi_{t+1}}\Big{)}\|\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2}$ $\displaystyle+\frac{\bar{L}^{2}}{2\mu^{2}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\frac{\big{\|}\nabla_{y}g(x_{t},y_{t})\big{\|}^{2}}{\alpha_{t+1}\varphi_{t+1}}+\frac{\bar{L}^{2}}{\mu^{2}}\frac{\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})\big{\|}^{2}}{\alpha_{t+1}\varphi_{t+1}}.$ (43) $$

If in addition, $k_{1}$ in [Lemma 4](#Thmlemma4) exists, then for $t\geq k_{1}$, we further have

$$ $\displaystyle\Phi(x_{t+1})\leq$ $\displaystyle\Phi(x_{t})-\frac{1}{2\alpha_{t+1}\varphi_{t+1}}\|\nabla\Phi(x_{t})\|^{2}-\frac{1}{4\alpha_{t+1}\varphi_{t+1}}\|\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2}$ $\displaystyle+\frac{\bar{L}^{2}}{2\mu^{2}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\frac{\big{\|}\nabla_{y}g(x_{t},y_{t})\big{\|}^{2}}{\alpha_{t+1}\varphi_{t+1}}+\frac{\bar{L}^{2}}{\mu^{2}}\frac{\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})\big{\|}^{2}}{\alpha_{t+1}\varphi_{t+1}},$ (44) $$

where $\bar{L}:=\max\big{\{}2\big{(}\frac{C_{f_{y}}^{2}L_{g,2}^{2}}{\mu^{2}}+L_{f,1}^{2}\big{)}^{\frac{1}{2}},\sqrt{2}C_{g_{yy}}\big{\}}$.

###### Proof.

From [Lemma 2](#Thmlemma2), we have $\Phi(x)$ is $L_{\Phi}$-smooth. So we can apply the descent lemma to $\Phi$ as

$$ $\displaystyle\Phi(x_{t+1})\leq$ $\displaystyle\Phi(x_{t})+\langle\nabla\Phi(x_{t}),x_{t+1}-x_{t}\rangle+\frac{L_{\Phi}}{2}\|x_{t+1}-x_{t}\|^{2}$ $\displaystyle=$ $\displaystyle\Phi(x_{t})-\frac{1}{\alpha_{t+1}\varphi_{t+1}}\langle\nabla\Phi(x_{t}),\bar{\nabla}f(x_{t},y_{t},v_{t})\rangle+\frac{L_{\Phi}}{2\alpha_{t+1}^{2}\varphi_{t+1}^{2}}\|\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2}$ $\displaystyle=$ $\displaystyle\Phi(x_{t})-\frac{1}{2\alpha_{t+1}\varphi_{t+1}}\|\nabla\Phi(x)\|^{2}-\frac{1}{2\alpha_{t+1}\varphi_{t+1}}\|\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2}$ $\displaystyle+\frac{1}{2\alpha_{t+1}\varphi_{t+1}}\|\nabla\Phi(x_{t})-\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2}+\frac{L_{\Phi}}{2\alpha_{t+1}^{2}\varphi_{t+1}^{2}}\|\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2},$ (45) $$

and the approximation error

$$ $\displaystyle\|\nabla\Phi$ $\displaystyle(x_{t})-\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2}$ $\displaystyle=$ $\displaystyle\big{\|}\bar{\nabla}f\big{(}x_{t},y^{*}(x_{t}),v^{*}(x_{t})\big{)}-\bar{\nabla}f(x_{t},y_{t},v_{t})\big{\|}^{2}$ $\displaystyle\leq$ $\displaystyle 2\big{\|}\bar{\nabla}f\big{(}x_{t},y^{*}(x_{t}),v^{*}(x_{t})\big{)}-\bar{\nabla}f\big{(}x_{t},y_{t},v^{*}(x_{t})\big{)}\big{\|}^{2}+2\big{\|}\bar{\nabla}f\big{(}x_{t},y_{t},v^{*}(x_{t})\big{)}-\bar{\nabla}f(x_{t},y_{t},v_{t})\big{\|}^{2}$ $\displaystyle\leq$ $\displaystyle 4\big{\|}\nabla_{y}\nabla_{y}g\big{(}x_{t},y^{*}(x_{t})\big{)}v^{*}(x_{t})-\nabla_{y}\nabla_{y}g(x_{t},y_{t})v^{*}(x_{t})\big{\|}^{2}$ $\displaystyle+4\big{\|}\nabla_{y}f\big{(}x_{t},y^{*}(x_{t})\big{)}-\nabla_{y}f(x_{t},y_{t})\big{\|}^{2}+2\big{\|}\nabla_{y}\nabla_{y}g(x_{t},y_{t})\big{(}v^{*}(x_{t})-v_{t}\big{)}\big{\|}^{2}$ $\displaystyle\leq$ $\displaystyle 4\Big{(}\frac{C_{f_{y}}^{2}L_{g,2}^{2}}{\mu^{2}}+L_{f,1}^{2}\Big{)}\|y_{t}-y^{*}(x_{t})\|^{2}+2C_{g_{yy}}^{2}\|v_{t}-v^{*}(x_{t})\|^{2}$ $\displaystyle\leq$ $\displaystyle\bar{L}^{2}\big{(}\|y_{t}-y^{*}(x_{t})\|^{2}+\|v_{t}-v^{*}(x_{t})\|^{2}\big{)},$ (46) $$

where the third inequality used results from Lemma [3](#Thmlemma3).
By plugging [section F.3](#A6.Ex87) into [section F.3](#A6.Ex84), we have

$$ $\displaystyle\Phi(x_{t+1})\leq$ $\displaystyle\Phi(x_{t})-\frac{1}{2\alpha_{t+1}\varphi_{t+1}}\|\nabla\Phi(x_{t})\|^{2}-\frac{1}{2\alpha_{t+1}\varphi_{t+1}}\Big{(}1-\frac{L_{\Phi}}{\alpha_{t+1}\varphi_{t+1}}\Big{)}\|\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2}$ $\displaystyle+\frac{\bar{L}^{2}}{2\alpha_{t+1}\varphi_{t+1}}\big{(}\|y_{t}-y^{*}(x_{t})\|^{2}+\|v_{t}-v^{*}(x_{t})\|^{2}\big{)}.$ (47) $$

Note that $g(x,y)$ is $\mu$-strongly convex in $y$ and $R(x,y,v)$ is $\mu$-strongly convex in $v$.
So here we can bound the approximation gaps $\|y_{t}-y^{*}(x_{t})\|^{2}+\|v_{t}-v^{*}(x_{t})\|^{2}$ by $\|\nabla_{y}g(x_{t},y_{t})\|^{2}$ and $\|\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}$ as

$$ $\displaystyle\|y_{t}-$ $\displaystyle y^{*}(x_{t})\|^{2}+\|v_{t}-v^{*}(x_{t})\|^{2}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\frac{1}{\mu^{2}}\big{\|}\nabla_{y}g(x_{t},y_{t})-\nabla_{y}g\big{(}x_{t},y^{*}(x_{t})\big{)}\big{\|}^{2}+\frac{1}{\mu^{2}}\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})-\nabla_{v}R\big{(}x_{t},y_{t},v^{*}(x_{t})\big{)}\big{\|}^{2}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\frac{1}{\mu^{2}}\big{\|}\nabla_{y}g(x_{t},y_{t})\big{\|}^{2}+\frac{2}{\mu^{2}}\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}$ $\displaystyle+\frac{2}{\mu^{2}}\big{\|}\nabla_{v}R\big{(}x_{t},y_{t},v^{*}(x_{t})\big{)}-\nabla_{v}R\big{(}x_{t},y^{*}(x_{t}),v^{*}(x_{t})\big{)}\big{\|}^{2}$ $\displaystyle\overset{(c)}{\leq}$ $\displaystyle\frac{1}{\mu^{2}}\big{\|}\nabla_{y}g(x_{t},y_{t})\big{\|}^{2}+\frac{2}{\mu^{2}}\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}+\frac{2}{\mu^{2}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\|y_{t}-y^{*}(x_{t})\|^{2}$ $\displaystyle\overset{(d)}{\leq}$ $\displaystyle\bigg{[}\frac{1}{\mu^{2}}+\frac{2}{\mu^{4}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\big{\|}\nabla_{y}g(x_{t},y_{t})\big{\|}^{2}+\frac{2}{\mu^{2}}\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})\big{\|}^{2},$ (48) $$

where (a) and (d) use the strong convexity; (b) and (d) result from $\nabla_{y}g\big{(}x,y^{*}(x)\big{)}=0$ and $\nabla_{v}R\big{(}x,y^{*}(x),v^{*}(x)\big{)}=0$; (c) uses [Lemma 3](#Thmlemma3).
By plugging [section F.3](#A6.Ex94) into [section F.3](#A6.Ex93), we obtain [lemma 11](#A6.Ex82).

Now if in addition, $k_{1}$ in [Lemma 4](#Thmlemma4) exists, then for $t\geq k_{1}$, we have $\alpha_{t+1}>C_{\alpha}\geq 2L_{\Phi}/\varphi_{0}$. From ([11](#A6.Ex82)) we can immediately obtain ([11](#A6.Ex83)). Thus, the proof is complete.
∎

Note that to further explore the bounds of the right-hand side of [lemma 11](#A6.Ex82) and [lemma 11](#A6.Ex83) in the above lemma, we next show the (summed) bounds of $\frac{\|\nabla_{y}g(x_{t},y_{t})\|^{2}}{\beta_{t+1}}$ and $\frac{\|\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\varphi_{t+1}}$.

###### Lemma 12 .

Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2), for Algorithm [2](#alg2), suppose the total iteration rounds is $T$. If $k_{2}$ in [Lemma 4](#Thmlemma4) exists within $T$ iterations, for all integer $t\in[k_{2},T]$, we have

$$ $\displaystyle\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}\leq\frac{(\mu+L_{g,1})C_{\beta}^{2}}{\mu^{2}}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}\varphi_{0}}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}}\sum_{k=k_{2}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}\varphi_{k+1}}.$ $$

###### Proof.

For $k_{2}\leq t<T$, we have $\beta_{k_{2}}\leq C_{\beta}$ and $\beta_{t+1}>C_{\beta}$.
For any positive scalar $\bar{\lambda}_{t+1}$, using Young’s inequality, we have

$$ $\displaystyle\|y_{t+1}-y^{*}(x_{t+1})\|^{2}\leq(1+\bar{\lambda}_{t+1})\|y_{t+1}-y^{*}(x_{t})\|^{2}+\Big{(}1+\frac{1}{\bar{\lambda}_{t+1}}\Big{)}\|y^{*}(x_{t})-y^{*}(x_{t+1})\|^{2}.$ (49) $$

For the first term on the right hand side of [eq. 49](#A6.E49), we have

$$ $\displaystyle\|y_{t+1}$ $\displaystyle-y^{*}(x_{t})\|^{2}$ $\displaystyle=$ $\displaystyle\Big{\|}y_{t}-\frac{1}{\beta_{t+1}}\nabla_{y}g(x_{t},y_{t})-y^{*}(x_{t})\Big{\|}^{2}$ $\displaystyle=$ $\displaystyle\|y_{t}-y^{*}(x_{t})\|^{2}+\frac{1}{\beta_{t+1}^{2}}\|\nabla_{y}g(x_{t},y_{t})\|^{2}-\frac{2}{\beta_{t+1}}\big{\langle}y_{t}-y^{*}(x_{t}),\nabla_{y}g(x_{t},y_{t})\big{\rangle}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\bigg{(}1-\frac{2\mu L_{g,1}}{\beta_{t+1}(\mu+L_{g,1})}\bigg{)}\|y_{t}-y^{*}(x_{t})\|^{2}+\frac{1}{\beta_{t+1}}\bigg{(}\frac{1}{\beta_{t+1}}-\frac{2}{\mu+L_{g,1}}\bigg{)}\|\nabla_{y}g(x_{t},y_{t})\|^{2}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\bigg{(}1-\frac{2\mu L_{g,1}}{\beta_{t+1}(\mu+L_{g,1})}\bigg{)}\|y_{t}-y^{*}(x_{t})\|^{2}-\frac{1}{\beta_{t+1}(\mu+L_{g,1})}\|\nabla_{y}g(x_{t},y_{t})\|^{2},$ (50) $$

where (a) uses Lemma 3.11 in []; (b) follows from $\beta_{t+1}\geq C_{\beta}\geq\mu+L_{g,1}$.
By plugging [section F.3](#A6.Ex100) into [eq. 49](#A6.E49), we have

$$ $\displaystyle\|$ $\displaystyle y_{t+1}-y^{*}(x_{t+1})\|^{2}$ $\displaystyle\leq$ $\displaystyle(1+\bar{\lambda}_{t+1})\bigg{(}1-\frac{2\mu L_{g,1}}{\beta_{t+1}(\mu+L_{g,1})}\bigg{)}\|y_{t}-y^{*}(x_{t})\|^{2}-(1+\bar{\lambda}_{t+1})\frac{1}{\beta_{t+1}(\mu+L_{g,1})}\|\nabla_{y}g(x_{t},y_{t})\|^{2}$ $\displaystyle+\Big{(}1+\frac{1}{\bar{\lambda}_{t+1}}\Big{)}\|y^{*}(x_{t})-y^{*}(x_{t+1})\|^{2}.$ (51) $$

By rearranging the terms in [section F.3](#A6.Ex104), we have

$$ $\displaystyle(1+$ $\displaystyle\bar{\lambda}_{t+1})\frac{1}{\beta_{t+1}(\mu+L_{g,1})}\|\nabla_{y}g(x_{t},y_{t})\|^{2}$ $\displaystyle\leq$ $\displaystyle(1+\bar{\lambda}_{t+1})\bigg{(}1-\frac{2\mu L_{g,1}}{\beta_{t+1}(\mu+L_{g,1})}\bigg{)}\|y_{t}-y^{*}(x_{t})\|^{2}-\|y_{t+1}-y^{*}(x_{t+1})\|^{2}$ $\displaystyle+\Big{(}1+\frac{1}{\bar{\lambda}_{t+1}}\Big{)}\|y^{*}(x_{t})-y^{*}(x_{t+1})\|^{2}.$ $$

We take $\bar{\lambda}_{t+1}:=\frac{2\mu L_{g,1}}{\beta_{t+1}(\mu+L_{g,1})}$. Since $\beta_{t+1}>C_{\beta}\geq{\frac{2\mu L_{g,1}}{\mu+L_{g,1}}}$ in [section F.1](#A6.Ex73), we have $\bar{\lambda}_{t+1}\leq{1}$. Then we have

$$ $\displaystyle\frac{\|\nabla_{y}g(x_{t},y_{t})\|^{2}}{\beta_{t+1}}\leq$ $\displaystyle(1+\bar{\lambda}_{t+1})\frac{\|\nabla_{y}g(x_{t},y_{t})\|^{2}}{\beta_{t+1}}$ $\displaystyle\leq$ $\displaystyle{(\mu+L_{g,1})}\big{(}\|y_{t}-y^{*}(x_{t})\|^{2}-\|y_{t+1}-y^{*}(x_{t+1})\|^{2}\big{)}$ $\displaystyle+\frac{2(\mu+L_{g,1})}{\bar{\lambda}_{t+1}}\|y^{*}(x_{t})-y^{*}(x_{t+1})\|^{2}$ $\displaystyle=$ $\displaystyle{(\mu+L_{g,1})}\big{(}\|y_{t}-y^{*}(x_{t})\|^{2}-\|y_{t+1}-y^{*}(x_{t+1})\|^{2}\big{)}$ $\displaystyle+\frac{(\mu+L_{g,1})^{2}\beta_{t+1}}{\mu L_{g,1}}\|y^{*}(x_{t})-y^{*}(x_{t+1})\|^{2}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle{(\mu+L_{g,1})}\big{(}\|y_{t}-y^{*}(x_{t})\|^{2}-\|y_{t+1}-y^{*}(x_{t+1})\|^{2}\big{)}$ $\displaystyle+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}\beta_{t+1}}{\mu L_{g,1}}\|x_{t}-x_{t+1}\|^{2},$ $$

where (a) uses [Lemma 2](#Thmlemma2).
Summing the above inequality over $k=k_{2},\ldots,t$, we have

$$ $\displaystyle\sum_{k=k_{2}}^{t}$ $\displaystyle\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ $\displaystyle\leq$ $\displaystyle\sum_{k=k_{2}-1}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ $\displaystyle\leq$ $\displaystyle{(\mu+L_{g,1})}\|y_{{k_{2}-1}}-y^{*}(x_{{k_{2}-1}})\|^{2}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}}\sum_{k={k_{2}-1}}^{t}\beta_{k+1}\|x_{k}-x_{k+1}\|^{2}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\frac{\mu+L_{g,1}}{\mu^{2}}\big{\|}\nabla_{y}g(x_{{k_{2}-1}},y_{{k_{2}-1}})-\nabla_{y}g\big{(}x_{{k_{2}-1}},y^{*}(x_{{k_{2}-1}})\big{)}\big{\|}^{2}$ $\displaystyle+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}}\sum_{k={k_{2}-1}}^{t}\frac{\beta_{k+1}}{\alpha_{k+1}^{2}\varphi_{k+1}^{2}}\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}$ $\displaystyle\leq$ $\displaystyle\frac{\mu+L_{g,1}}{\mu^{2}}\|\nabla_{y}g(x_{{k_{2}-1}},y_{{k_{2}-1}})\|^{2}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}}\sum_{k={k_{2}-1}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}\varphi_{k+1}}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\frac{(\mu+L_{g,1}){C_{\beta}^{2}}}{\mu^{2}}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}}\sum_{k={k_{2}-1}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}\varphi_{k+1}}$ $\displaystyle\overset{(c)}{\leq}$ $\displaystyle\frac{(\mu+L_{g,1}){C_{\beta}^{2}}}{\mu^{2}}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}\varphi_{0}}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}}\sum_{k=k_{2}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}\varphi_{k+1}},$ (52) $$

where (a) uses Assumption [1](#Thmassumption1); (b) results from $\|\nabla_{y}g(x_{{k_{2}-1}},y_{{k_{2}-1}})\|^{2}\leq\beta_{k_{2}}^{2}\leq C_{\beta}^{2}$; (c) denotes $\varphi_{0}=\max\{\beta_{0},\gamma_{0}\}$.
Then, the proof is complete.
∎

###### Lemma 13 .

Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2), for Algorithm [2](#alg2), suppose the total iteration rounds is $T$. If $k_{3}$ in [Lemma 4](#Thmlemma4) exists within $T$ iterations, for all integer $t\in[k_{3},T)$, we have

$$ $\displaystyle\sum_{k=k_{3}}^{t}$ $\displaystyle\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}$ $\displaystyle\leq$ $\displaystyle\frac{4(\mu+C_{g_{yy}})C_{\beta}^{2}}{\mu^{4}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}+\frac{4(\mu+C_{g_{yy}})C_{\gamma}^{2}}{\mu^{2}}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})(\mu+L_{g,1})L_{y}^{2}}{\mu^{3}L_{g,1}\varphi_{0}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\sum_{k=k_{2}-1}^{k_{3}-2}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}C_{\gamma}}\sum_{k=k_{3}-1}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle+\bigg{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\frac{1}{\mu^{2}}\sum_{k=k_{3}-1}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}.$ $$

###### Proof.

For $k_{3}\leq t<T$, we have $\gamma_{t+1}>C_{\gamma}$.
For any positive scalar $\hat{\lambda}_{t+1}$, using Young’s inequality, we have

$$ $\displaystyle\|v_{t+1}-v^{*}(x_{t+1})\|^{2}\leq(1+\hat{\lambda}_{t+1})\|v_{t+1}-v^{*}(x_{t})\|^{2}+\Big{(}1+\frac{1}{\hat{\lambda}_{t+1}}\Big{)}\|v^{*}(x_{t})-v^{*}(x_{t+1})\|^{2}.$ (53) $$

For the first term on the right hand side of [eq. 53](#A6.E53), we have

$$ $\displaystyle\|v_{t+1}$ $\displaystyle-v^{*}(x_{t})\|^{2}$ $\displaystyle=$ $\displaystyle\Big{\|}v_{t}-\frac{1}{\varphi_{t+1}}\nabla_{v}R(x_{t},y_{t},v_{t})-v^{*}(x_{t})\Big{\|}^{2}$ $\displaystyle=$ $\displaystyle\|v_{t}-v^{*}(x_{t})\|^{2}+\frac{1}{\varphi_{t+1}^{2}}\|\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}-\frac{2}{\varphi_{t+1}}\big{\langle}v_{t}-v^{*}(x_{t}),\nabla_{v}R(x_{t},y_{t},v_{t})\big{\rangle}.$ (54) $$

For the last term of the right-hand side of [section F.3](#A6.Ex128), we have

$$ $\displaystyle-\langle v_{t}$ $\displaystyle-v^{*}(x_{t}),\nabla_{v}R(x_{t},y_{t},v_{t})\big{\rangle}$ $\displaystyle=$ $\displaystyle-\langle v_{t}-v^{*}(x_{t}),\nabla_{v}R(x_{t},y_{t},v_{t})-\nabla_{v}R\big{(}x_{t},y_{t},v^{*}(x_{t})\big{)}\big{\rangle}$ $\displaystyle-\langle v_{t}-v^{*}(x_{t}),\nabla_{v}R\big{(}x_{t},y_{t},v^{*}(x_{t})\big{)}-\nabla_{v}R\big{(}x_{t},y^{*}(x_{t}),v^{*}(x_{t})\big{)}\big{\rangle}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle-\frac{1}{\mu+C_{g_{yy}}}\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})-\nabla_{v}R\big{(}x_{t},y_{t},v^{*}(x_{t})\big{)}\big{\|}^{2}-\frac{\mu C_{g_{yy}}}{\mu+C_{g_{yy}}}\|v_{t}-v^{*}(x_{t})\|^{2}$ $\displaystyle+\frac{\mu+C_{g_{yy}}}{2\mu C_{g_{yy}}}\big{\|}\nabla_{v}R\big{(}x_{t},y_{t},v^{*}(x_{t})\big{)}-\nabla_{v}R\big{(}x_{t},y^{*}(x_{t}),v^{*}(x_{t})\big{)}\big{\|}^{2}$ $\displaystyle+\frac{\mu C_{g_{yy}}}{2(\mu+C_{g_{yy}})}\|v_{t}-v^{*}(x_{t})\|^{2}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle-\frac{1}{2(\mu+C_{g_{yy}})}\|\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}+\frac{1}{\mu+C_{g_{yy}}}\|\nabla_{v}R\big{(}x_{t},y_{t},v^{*}(x_{t})\big{)}\|^{2}$ $\displaystyle+\frac{\mu+C_{g_{yy}}}{2\mu C_{g_{yy}}}\big{\|}\nabla_{v}R\big{(}x_{t},y_{t},v^{*}(x_{t})\big{)}-\nabla_{v}R\big{(}x_{t},y^{*}(x_{t}),v^{*}(x_{t})\big{)}\big{\|}^{2}$ $\displaystyle-\frac{\mu C_{g_{yy}}}{2(\mu+C_{g_{yy}})}\|v_{t}-v^{*}(x_{t})\|^{2}$ $\displaystyle\overset{(c)}{=}$ $\displaystyle-\frac{1}{2(\mu+C_{g_{yy}})}\|\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}-\frac{\mu C_{g_{yy}}}{2(\mu+C_{g_{yy}})}\|v_{t}-v^{*}(x_{t})\|^{2}$ $\displaystyle+\bigg{(}\frac{1}{\mu+C_{g_{yy}}}+\frac{\mu+C_{g_{yy}}}{2\mu C_{g_{yy}}}\bigg{)}\big{\|}\nabla_{v}R\big{(}x_{t},y_{t},v^{*}(x_{t})\big{)}-\nabla_{v}R\big{(}x_{t},y^{*}(x_{t}),v^{*}(x_{t})\big{)}\big{\|}^{2}$ $\displaystyle\overset{(d)}{\leq}$ $\displaystyle-\frac{1}{2(\mu+C_{g_{yy}})}\|\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}-\frac{\mu C_{g_{yy}}}{2(\mu+C_{g_{yy}})}\|v_{t}-v^{*}(x_{t})\|^{2}$ $\displaystyle+\bigg{(}\frac{1}{\mu+C_{g_{yy}}}+\frac{\mu+C_{g_{yy}}}{2\mu C_{g_{yy}}}\bigg{)}\big{(}L_{g,2}\|v^{*}(x_{t})\|+L_{f,1}\big{)}^{2}\|y_{t}-y^{*}(x_{t})\|^{2}$ $\displaystyle\overset{(e)}{\leq}$ $\displaystyle-\frac{1}{2(\mu+C_{g_{yy}})}\|\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}-\frac{\mu C_{g_{yy}}}{2(\mu+C_{g_{yy}})}\|v_{t}-v^{*}(x_{t})\|^{2}$ $\displaystyle+\bigg{(}\frac{1}{\mu+C_{g_{yy}}}+\frac{\mu+C_{g_{yy}}}{2\mu C_{g_{yy}}}\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\|y_{t}-y^{*}(x_{t})\|^{2},$ (55) $$

where
(a) follows from Lemma 3.11 in [];
(b) uses $-\|a-b\|^{2}\leq-\frac{1}{2}\|a\|^{2}+\|b\|^{2}$ since $\|a-b+b\|^{2}\leq 2\|a-b\|^{2}+2\|b\|^{2}$;
(c) uses $\nabla_{v}R\big{(}x_{t},y^{*}(x_{t}),v^{*}(x_{t})\big{)}=0$;
(d) and (e) follow from [Lemma 3](#Thmlemma3).
Plugging [section F.3](#A6.Ex130) into [section F.3](#A6.Ex128), we have

$$ $\displaystyle\|v_{t+1}$ $\displaystyle-v^{*}(x_{t})\|^{2}$ $\displaystyle\leq$ $\displaystyle\bigg{(}1-\frac{\mu C_{g_{yy}}}{(\mu+C_{g_{yy}})\varphi_{t+1}}\bigg{)}\|v_{t}-v^{*}(x_{t})\|^{2}+\frac{1}{\varphi_{t+1}}\bigg{(}\frac{1}{\varphi_{t+1}}-\frac{1}{\mu+C_{g_{yy}}}\bigg{)}\big{\|}\nabla_{v}R\big{(}x_{t},y_{t},v_{t}\big{)}\big{\|}^{2}$ $\displaystyle+\bigg{(}\frac{2}{\mu+C_{g_{yy}}}+\frac{\mu+C_{g_{yy}}}{\mu C_{g_{yy}}}\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\frac{1}{\varphi_{t+1}}\|y_{t}-y^{*}(x_{t})\|^{2}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\bigg{(}1-\frac{\mu C_{g_{yy}}}{(\mu+C_{g_{yy}})\varphi_{t+1}}\bigg{)}\|v_{t}-v^{*}(x_{t})\|^{2}-\frac{1}{2(\mu+C_{g_{yy}})\varphi_{t+1}}\big{\|}\nabla_{v}R\big{(}x_{t},y_{t},v_{t}\big{)}\big{\|}^{2}$ $\displaystyle+\bigg{(}\frac{2}{\mu+C_{g_{yy}}}+\frac{\mu+C_{g_{yy}}}{\mu C_{g_{yy}}}\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\frac{1}{\varphi_{t+1}}\|y_{t}-y^{*}(x_{t})\|^{2},$ (56) $$

where (a) follows from $\varphi_{t+1}\geq\gamma_{t+1}\geq C_{\gamma}\geq 2(\mu+C_{g_{yy}})$. Combining [section F.3](#A6.Ex144) with [eq. 53](#A6.E53), we have

$$ $\displaystyle\|v_{t+1}$ $\displaystyle-v^{*}(x_{t+1})\|^{2}$ $\displaystyle\leq$ $\displaystyle(1+\hat{\lambda}_{t+1})\bigg{(}1-\frac{\mu C_{g_{yy}}}{(\mu+C_{g_{yy}})\varphi_{t+1}}\bigg{)}\|v_{t}-v^{*}(x_{t})\|^{2}$ $\displaystyle-(1+\hat{\lambda}_{t+1})\frac{1}{2(\mu+C_{g_{yy}})\varphi_{t+1}}\big{\|}\nabla_{v}R\big{(}x_{t},y_{t},v_{t}\big{)}\big{\|}^{2}$ $\displaystyle+(1+\hat{\lambda}_{t+1})\bigg{(}\frac{2}{\mu+C_{g_{yy}}}+\frac{\mu+C_{g_{yy}}}{\mu C_{g_{yy}}}\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\frac{1}{\varphi_{t+1}}\|y_{t}-y^{*}(x_{t})\|^{2}$ $\displaystyle+\Big{(}1+\frac{1}{\hat{\lambda}_{t+1}}\Big{)}\|v^{*}(x_{t})-v^{*}(x_{t+1})\|^{2}.$ (57) $$

By rearranging the terms in [section F.3](#A6.Ex148), we have

$$ $\displaystyle(1+\hat{\lambda}_{t+1})$ $\displaystyle\frac{1}{2(\mu+C_{g_{yy}})\varphi_{t+1}}\big{\|}\nabla_{v}R\big{(}x_{t},y_{t},v_{t}\big{)}\big{\|}^{2}$ $\displaystyle\leq$ $\displaystyle(1+\hat{\lambda}_{t+1})\bigg{(}1-\frac{\mu C_{g_{yy}}}{(\mu+C_{g_{yy}})\varphi_{t+1}}\bigg{)}\|v_{t}-v^{*}(x_{t})\|^{2}-\|v_{t+1}-v^{*}(x_{t+1})\|^{2}$ $\displaystyle+(1+\hat{\lambda}_{t+1})\bigg{(}\frac{2}{\mu+C_{g_{yy}}}+\frac{\mu+C_{g_{yy}}}{\mu C_{g_{yy}}}\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\frac{1}{\varphi_{t+1}}\|y_{t}-y^{*}(x_{t})\|^{2}$ $\displaystyle+{\Big{(}1+\frac{1}{\hat{\lambda}_{t+1}}\Big{)}\|v^{*}(x_{t})-v^{*}(x_{t+1})\|^{2}}.$ (58) $$

We now take $\hat{\lambda}_{t+1}:=\frac{\mu C_{g_{yy}}}{(\mu+C_{g_{yy}})\varphi_{t+1}}$.
Since $\varphi_{t+1}\geq\gamma_{t+1}\geq C_{\gamma}\geq\frac{\mu C_{g_{yy}}}{\mu+C_{g_{yy}}}$ in [section F.1](#A6.Ex73), we have $\hat{\lambda}_{t+1}\leq{1}$.
Then we get

$$ $\displaystyle\frac{\|\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\varphi_{t+1}}<$ $\displaystyle(1+\hat{\lambda}_{t+1})\frac{\|\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\varphi_{t+1}}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle{2(\mu+C_{g_{yy}})}\big{(}\|v_{t}-v^{*}(x_{t})\|^{2}-\|v_{t+1}-v^{*}(x_{t+1})\|^{2}\big{)}$ $\displaystyle+4(\mu+C_{g_{yy}})\bigg{(}\frac{2}{\mu+C_{g_{yy}}}+\frac{\mu+C_{g_{yy}}}{\mu C_{g_{yy}}}\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\frac{\|y_{t}-y^{*}(x_{t})\|^{2}}{\varphi_{t+1}}$ $\displaystyle+2(\mu+C_{g_{yy}})\bigg{(}1+\frac{(\mu+C_{g_{yy}})\varphi_{t+1}}{\mu C_{g_{yy}}}\bigg{)}L_{v}^{2}\|x_{t}-x_{t+1}\|^{2}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle{2(\mu+C_{g_{yy}})}\big{(}\|v_{t}-v^{*}(x_{t})\|^{2}-\|v_{t+1}-v^{*}(x_{t+1})\|^{2}\big{)}$ $\displaystyle+\bigg{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\frac{\|y_{t}-y^{*}(x_{t})\|^{2}}{\varphi_{t+1}}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}\varphi_{t+1}}{\mu C_{g_{yy}}}\|x_{t}-x_{t+1}\|^{2},$ (59) $$

where
(a) multiplies both sides of [section F.3](#A6.Ex152) by $2(\mu+C_{g_{xy}})$ and uses $\hat{\lambda}_{t+1}\leq{1}$;
(b) uses $\varphi_{t+1}\geq\gamma_{t+1}\geq C_{\gamma}\geq\frac{\mu C_{g_{yy}}}{\mu+C_{g_{yy}}}$.
Take summation of [section F.3](#A6.Ex155) and we have

$$ $\displaystyle\sum_{k=k_{3}}^{t}$ $\displaystyle\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}$ $\displaystyle\leq$ $\displaystyle\sum_{k={k_{3}-1}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}$ $\displaystyle\leq$ $\displaystyle{2(\mu+C_{g_{yy}})}\|v_{{k_{3}-1}}-v^{*}(x_{{k_{3}-1}})\|^{2}+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}}\sum_{k={k_{3}-1}}^{t}\varphi_{k+1}\|x_{k}-x_{k+1}\|^{2}$ $\displaystyle+\bigg{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\sum_{k={k_{3}-1}}^{t}\frac{\|y_{k}-y^{*}(x_{k})\|^{2}}{\varphi_{k+1}}$ $\displaystyle\leq$ $\displaystyle{2(\mu+C_{g_{yy}})}\|v_{{k_{3}-1}}-v^{*}(x_{{k_{3}-1}})\|^{2}+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}}\sum_{k={k_{3}-1}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}\varphi_{k+1}}$ $\displaystyle+\bigg{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\sum_{k={k_{3}-1}}^{t}\frac{\|y_{k}-y^{*}(x_{k})\|^{2}}{\varphi_{k+1}}$ $\displaystyle\leq$ $\displaystyle{2(\mu+C_{g_{yy}})}\|v_{{k_{3}-1}}-v^{*}(x_{{k_{3}-1}})\|^{2}+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}}\sum_{k={k_{3}-1}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}\varphi_{k+1}}$ $\displaystyle+\bigg{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\sum_{k={k_{3}-1}}^{t}\frac{\|y_{k}-y^{*}(x_{k})\|^{2}}{\beta_{k+1}}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle{2(\mu+C_{g_{yy}})}\|v_{{k_{3}-1}}-v^{*}(x_{{k_{3}-1}})\|^{2}+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}}\sum_{k={k_{3}-1}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}\varphi_{k+1}}$ $\displaystyle+\bigg{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\frac{1}{\mu^{2}}\sum_{k={k_{3}-1}}^{t}\frac{\big{\|}\nabla_{y}g(x_{k},y_{k})-\nabla_{y}g\big{(}x_{k},y^{*}(x_{k})\big{)}\big{\|}^{2}}{\beta_{k+1}}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle{2(\mu+C_{g_{yy}})}\|v_{{k_{3}-1}}-v^{*}(x_{{k_{3}-1}})\|^{2}+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}}\sum_{k={k_{3}-1}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}\varphi_{k+1}}$ $\displaystyle+\bigg{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\frac{1}{\mu^{2}}\sum_{k={k_{3}-1}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ $\displaystyle\overset{(c)}{\leq}$ $\displaystyle\frac{2(\mu+C_{g_{yy}})}{\mu^{2}}\big{\|}\nabla_{v}R\big{(}x_{{k_{3}-1}},y_{{k_{3}-1}},v_{{k_{3}-1}}\big{)}-\nabla_{v}R\big{(}x_{{k_{3}-1}},y_{{k_{3}-1}},v^{*}(x_{{k_{3}-1}})\big{)}\big{\|}^{2}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}}\sum_{k={k_{3}-1}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}\varphi_{k+1}}$ $\displaystyle+\bigg{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\frac{1}{\mu^{2}}\sum_{k={k_{3}-1}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ $\displaystyle\overset{(d)}{\leq}$ $\displaystyle\frac{4(\mu+C_{g_{yy}})}{\mu^{2}}\big{\|}\nabla_{v}R\big{(}x_{{k_{3}-1}},y^{*}(x_{{k_{3}-1}}),v^{*}(x_{{k_{3}-1}})\big{)}-\nabla_{v}R\big{(}x_{{k_{3}-1}},y_{{k_{3}-1}},v^{*}(x_{{k_{3}-1}})\big{)}\big{\|}^{2}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})}{\mu^{2}}\big{\|}\nabla_{v}R(x_{{k_{3}-1}},y_{{k_{3}-1}},v_{{k_{3}-1}})-\nabla_{v}R\big{(}x_{{k_{3}-1}},y^{*}(x_{{k_{3}-1}}),v^{*}(x_{{k_{3}-1}})\big{)}\big{\|}^{2}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}}\sum_{k={k_{3}-1}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}\varphi_{k+1}}$ $\displaystyle+\bigg{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\frac{1}{\mu^{2}}\sum_{k={k_{3}-1}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ $\displaystyle\overset{(e)}{\leq}$ $\displaystyle\frac{4(\mu+C_{g_{yy}})}{\mu^{2}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}{\|y_{{k_{3}-1}}-y^{*}(x_{{k_{3}-1}})\|^{2}}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})}{\mu^{2}}\|\nabla_{v}R(x_{{k_{3}-1}},y_{{k_{3}-1}},v_{{k_{3}-1}})\|^{2}+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}}\sum_{k={k_{3}-1}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}\varphi_{k+1}}$ $\displaystyle+\bigg{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\frac{1}{\mu^{2}}\sum_{k={k_{3}-1}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}},$ (60) $$

where (a) uses Assumption [1](#Thmassumption1);
(b) results from $\nabla_{y}g\big{(}x,y^{*}(x)\big{)}=0$;
(c) uses the strong convexity in [Lemma 3](#Thmlemma3);
(d) uses $\nabla_{v}R\big{(}x,y^{*}(x),v^{*}(x)\big{)}=0$;
(e) follows from [Lemma 3](#Thmlemma3).

Our next step is bounding $\|y_{{k_{3}-1}}-y^{*}(x_{{k_{3}-1}})\|^{2}$ on the right hand side of [section F.3](#A6.Ex161) in two cases.
The first case is $\beta_{k_{3}}\leq C_{\beta}$. In this case,
by using strong convexity of $g$ and the definition of $\beta_{k_{3}}$,
we can easily have

$$ $\displaystyle\|y_{{k_{3}-1}}-y^{*}(x_{{k_{3}-1}})\|^{2}\leq$ $\displaystyle\frac{1}{\mu^{2}}\big{\|}\nabla_{y}g\big{(}x_{{k_{3}-1}},y_{{k_{3}-1}})-\nabla_{y}g(x_{{k_{3}-1}},y^{*}(x_{{k_{3}-1}})\big{)}\big{\|}^{2}$ $\displaystyle=$ $\displaystyle\frac{1}{\mu^{2}}\|\nabla_{y}g(x_{{k_{3}-1}},y_{{k_{3}-1}}))\|^{2}\leq\frac{\beta_{k_{3}}^{2}}{\mu^{2}}\leq\frac{C_{\beta}^{2}}{\mu^{2}}.$ (61) $$

The second case is $\beta_{k_{3}}>C_{\beta}$.
This indicates that $k_{2}$ exists and $k_{3}>k_{2}$ based on [Lemma 4](#Thmlemma4).
By plugging $\bar{\lambda}_{k_{3}-1}:=\frac{2\mu L_{g,1}}{\beta_{k_{3}-1}(\mu+L_{g,1})}$ into [section F.3](#A6.Ex104), and noting $\bar{\lambda}_{k_{3}-1}\leq 1$, we have

$$ $\displaystyle\|y_{{k_{3}-1}}-y^{*}(x_{{k_{3}-1}})\|^{2}\leq$ $\displaystyle\|y_{k_{3}-2}-y^{*}(x_{k_{3}-2})\|^{2}+\frac{(\mu+L_{g,1})\beta_{k_{3}-1}}{\mu L_{g,1}}\|y^{*}(x_{k_{3}-2})-y^{*}(x_{k_{3}-1})\|^{2}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\|y_{k_{3}-2}-y^{*}(x_{k_{3}-2})\|^{2}+\frac{(\mu+L_{g,1})L_{y}^{2}\beta_{k_{3}-1}}{\mu L_{g,1}}\|x_{k_{3}-2}-x_{k_{3}-1}\|^{2}$ $\displaystyle=$ $\displaystyle\|y_{k_{3}-2}-y^{*}(x_{k_{3}-2})\|^{2}+\frac{(\mu+L_{g,1})L_{y}^{2}\beta_{k_{3}-1}}{\mu L_{g,1}}\frac{\|\bar{\nabla}f(x_{k_{3}-2},y_{k_{3}-2},v_{k_{3}-2})\|^{2}}{\alpha_{k_{3}-1}^{2}\varphi_{k_{3}-1}^{2}}$ $\displaystyle\leq$ $\displaystyle\|y_{k_{3}-2}-y^{*}(x_{k_{3}-2})\|^{2}+\frac{(\mu+L_{g,1})L_{y}^{2}}{\mu L_{g,1}}\frac{\|\bar{\nabla}f(x_{k_{3}-2},y_{k_{3}-2},v_{k_{3}-2})\|^{2}}{\alpha_{k_{3}-1}^{2}\varphi_{k_{3}-1}}$ $\displaystyle\leq$ $\displaystyle\|y_{k_{3}-2}-y^{*}(x_{k_{3}-2})\|^{2}+\frac{(\mu+L_{g,1})L_{y}^{2}}{\mu L_{g,1}\varphi_{0}}\frac{\|\bar{\nabla}f(x_{k_{3}-2},y_{k_{3}-2},v_{k_{3}-2})\|^{2}}{\alpha_{k_{3}-1}^{2}}$ $\displaystyle\leq$ $\displaystyle\|y_{k_{2}-1}-y^{*}(x_{k_{2}-1})\|^{2}+\frac{(\mu+L_{g,1})L_{y}^{2}}{\mu L_{g,1}\varphi_{0}}\sum_{k=k_{2}-1}^{k_{3}-2}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\frac{C_{\beta}^{2}}{\mu^{2}}+\frac{(\mu+L_{g,1})L_{y}^{2}}{\mu L_{g,1}\varphi_{0}}\sum_{k=k_{2}-1}^{k_{3}-2}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}},$ (62) $$

where (a) uses [Lemma 2](#Thmlemma2); (b) uses [section F.3](#A6.Ex182) by replacing $k_{3}$ by $k_{2}$ since $\beta_{k_{2}}\leq C_{\beta}$ (see [Lemma 4](#Thmlemma4)).
By combining [section F.3](#A6.Ex182) and [section F.3](#A6.Ex183), we obtain a general upper bound of $\|y_{k_{3}-1}-y^{*}(x_{k_{3}-1})\|^{2}$ as

$$ $\displaystyle\|y_{k_{3}-1}-y^{*}(x_{k_{3}-1})\|^{2}\leq\frac{C_{\beta}^{2}}{\mu^{2}}+\frac{(\mu+L_{g,1})L_{y}^{2}}{\mu L_{g,1}\varphi_{0}}\sum_{k=k_{2}-1}^{k_{3}-2}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}},$ (63) $$

where we define $\sum_{k=m}^{n}l_{k}=0$ for any $m>n$ and non-negative sequence $\{l_{k}\}$.
By plugging [eq. 63](#A6.E63) into [section F.3](#A6.Ex161) and using $\|\nabla_{v}R(x_{{k_{3}-1}},y_{{k_{3}-1}},v_{{k_{3}-1}})\|^{2}\leq\gamma_{k_{3}}^{2}\leq C_{\gamma}^{2}$, we have

$$ $\displaystyle\sum_{k=k_{3}}^{t}$ $\displaystyle\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}$ $\displaystyle\leq$ $\displaystyle\frac{4(\mu+C_{g_{yy}})C_{\beta}^{2}}{\mu^{4}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}+\frac{4(\mu+C_{g_{yy}})C_{\gamma}^{2}}{\mu^{2}}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})(\mu+L_{g,1})L_{y}^{2}}{\mu^{3}L_{g,1}\varphi_{0}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\sum_{k=k_{2}-1}^{k_{3}-2}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}C_{\gamma}}\sum_{k=k_{3}-1}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle+\bigg{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\frac{1}{\mu^{2}}\sum_{k=k_{3}-1}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}.$ $$

Then, the proof is complete.
∎

Supported by [Lemma 12](#Thmlemma12) and [Lemma 13](#Thmlemma13), we derive upper bounds of $\beta_{t}$ and $\varphi_{t}$.

###### Lemma 14 .

Suppose the total iteration rounds of Algorithm [2](#alg2) is $T$. Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2),
if $k_{2}$ in [Lemma 4](#Thmlemma4) exists within $T$ iterations,
we have

$$ $\left\{\begin{aligned} \beta_{t+1}\leq&C_{\beta},&t<k_{2};\\ \beta_{t+1}\leq&\Big{(}C_{\beta}+\frac{(\mu+L_{g,1})C_{\beta}^{2}}{\mu^{2}}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}\varphi_{0}}\Big{)}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}C_{\beta}}\sum_{k=k_{2}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}},&t\geq k_{2}.\end{aligned}\right.$ $$

When such $k_{2}$ does not exist, $\beta_{t+1}\leq C_{\beta}$ holds for any $t<T$.

###### Proof.

According to [Lemma 4](#Thmlemma4), the proof can be split into the following three cases.

Case 1: $k_{2}$ does not exist: In this case, based on [Lemma 4](#Thmlemma4), we have $\beta_{T}\leq C_{\beta}$, and hence $\beta_{t+1}\leq C_{\beta}$ for any $t<T$ because $\beta_{t}$ is non-decreasing with $t$.

Case 2: $k_{2}$ exists and $t<k_{2}$: In this case, based on [Lemma 4](#Thmlemma4), we have $\beta_{t+1}\leq C_{\beta}$.

Case 3: $k_{2}$ exists and $t\geq k_{2}$: Inspired by [] and using telescoping, we have

$$ $\displaystyle\beta_{t+1}=$ $\displaystyle\beta_{t}+\frac{\|\nabla_{y}g(x_{t},y_{t})\|^{2}}{\beta_{t+1}+\beta_{t}}$ $\displaystyle\leq$ $\displaystyle\beta_{t}+\frac{\|\nabla_{y}g(x_{t},y_{t})\|^{2}}{\beta_{t+1}}$ $\displaystyle\leq$ $\displaystyle\beta_{{k_{2}}}+\sum_{k={k_{2}}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\bigg{(}C_{\beta}+\frac{(\mu+L_{g,1})C_{\beta}^{2}}{\mu^{2}}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}\varphi_{0}}\bigg{)}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}C_{\beta}}\sum_{k=k_{2}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}},$ (64) $$

where (a) uses [lemma 12](#Thmlemma12). Thus, the proof is complete.
∎

###### Lemma 15 .

Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2), suppose the total iteration rounds of Algorithm [2](#alg2) is $T$.
If at least one of $k_{2}$ and $k_{3}$ in [Lemma 4](#Thmlemma4) exists, we denote $k_{\text{min}}:=\min\{k_{2},k_{3}\}$.
Then we have the upper bound of $\varphi_{t}$ as

$$ $\left\{\begin{aligned} \varphi_{t}\leq&C_{\varphi},\quad&t\leq k_{\text{min}};\\ \varphi_{t}\leq&a_{1}\log(t)+b_{1},\quad&t>k_{\text{min}},\end{aligned}\right.$ $$

where $a_{1}$, $b_{1}$ are defined as

$$ $\displaystyle a_{1}:=6a_{0},\quad b_{1}:=4a_{0}\log\Big{(}1+\frac{C_{g_{xy}}\bar{b}+C_{f_{x}}+\alpha_{0}}{C_{g_{xy}}\bar{a}}\Big{)}+4a_{0}\log(C_{g_{xy}}\bar{a})+4a_{0}+2b_{0},$ (65) $$

in which we define constants

$$ $\displaystyle\bar{a}:=$ $\displaystyle\frac{\sqrt{2}}{\mu},\quad\bar{b}:=\frac{\sqrt{2}C_{f_{y}}}{\mu},$ $\displaystyle a_{0}:=$ $\displaystyle\bigg{(}\Big{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\Big{)}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\frac{1}{\mu^{2}}+1\bigg{)}\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}C_{\beta}}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})(\mu+L_{g,1})L_{y}^{2}}{\mu^{3}L_{g,1}\varphi_{0}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}\gamma_{0}},$ $\displaystyle b_{0}:=$ $\displaystyle C_{\beta}+C_{\gamma}+\frac{4(\mu+C_{g_{yy}})C_{\beta}^{2}}{\mu^{4}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}+\frac{4(\mu+C_{g_{yy}})C_{\gamma}^{2}}{\mu^{2}}$ $\displaystyle+\Big{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\Big{)}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\frac{1}{\mu^{2}}\Big{(}\frac{C_{\beta}^{2}}{\beta_{0}}-\beta_{0}\Big{)}$ $\displaystyle+\bigg{[}\Big{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\Big{)}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\frac{1}{\mu^{2}}+1\bigg{]}\bigg{(}\frac{(\mu+L_{g,1})C_{\beta}^{2}}{\mu^{2}}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}\varphi_{0}}\bigg{)}.$ (66) $$

When such $k_{2}$ and $k_{3}$ do not exist, we have $\varphi_{t}\leq C_{\varphi}$ for all $t\leq T$.

###### Proof.

To begin with,
we first show the following result as the first two lines of [section F.3](#A6.Ex195):
since $\beta_{t}$ and $\gamma_{t}$ are positive and increasing monotonically with $t$, we can easily have

$$ $\displaystyle 0\leq$ $\displaystyle\min\{\beta_{t+1}^{2},\gamma_{t+1}^{2}\}-\min\{\beta_{t}^{2},\gamma_{t}^{2}\}$ $\displaystyle=$ $\displaystyle\big{(}\beta_{t+1}^{2}+\gamma_{t+1}^{2}-\max\{\beta_{t+1}^{2},\gamma_{t+1}^{2}\}\big{)}-\big{(}\beta_{t}^{2}+\gamma_{t}^{2}-\max\{\beta_{t}^{2},\gamma_{t}^{2}\}\big{)}$ $\displaystyle\overset{(a)}{=}$ $\displaystyle(\beta_{t+1}^{2}+\gamma_{t+1}^{2})-(\beta_{t}^{2}+\gamma_{t}^{2})-(\varphi_{t+1}^{2}-\varphi_{t}^{2}),$ $$

where (a) uses the definition $\varphi_{t}:=\max\{\beta_{t},\gamma_{t}\}$.
Similar to [section F.3](#A6.Ex195), we have

$$ $\displaystyle\varphi_{t+1}^{2}-\varphi_{t}^{2}\leq$ $\displaystyle(\beta_{t+1}^{2}-\beta_{t}^{2})+(\gamma_{t+1}^{2}-\gamma_{t}^{2})=\|\nabla_{y}g(x_{t},y_{t})\|^{2}+\|\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2},$ $$

which indicates that

$$ $\displaystyle\varphi_{t+1}\leq$ $\displaystyle\varphi_{t}+\frac{\|\nabla_{y}g(x_{t},y_{t})\|^{2}}{\varphi_{t+1}+\varphi_{t}}+\frac{\|\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\varphi_{t+1}+\varphi_{t}}$ $\displaystyle\leq$ $\displaystyle\varphi_{t}+\frac{\|\nabla_{y}g(x_{t},y_{t})\|^{2}}{\beta_{t+1}+\beta_{t}}+\frac{\|\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\varphi_{t+1}}$ $\displaystyle\leq$ $\displaystyle\varphi_{t}+\frac{\|\nabla_{y}g(x_{t},y_{t})\|^{2}}{\beta_{t+1}}+\frac{\|\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\varphi_{t+1}}.$ (67) $$

Note that, to simplify the proof,
we define $\sum_{k=m}^{n}l_{k}=0$ for any $m>n$ and non-negative sequence $\{l_{k}\}$.
According to the definitions of $\bm{k_{2}}$ and $\bm{k_{3}}$ in [Lemma 4](#Thmlemma4), the proof can be split into the following four cases.

Case 1: neither $k_{2}$ nor $k_{3}$ exists:
for any $t\in(0,T)$, we can easily have $\varphi_{t}=\max\{\beta_{t},\gamma_{t}\}\leq\max\{C_{\beta},C_{\gamma}\}\leq C_{\varphi}$.

Case 2: $k_{2}$ exists but $k_{3}$ does not:
by using the third line of [section F.3](#A6.Ex195),
for any $t\in(0,T)$, we have

$$ $\displaystyle\varphi_{t+1}\leq\beta_{t+1}+\gamma_{t+1}\leq C_{\beta}+\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}+C_{\gamma},$ (68) $$

where we take $\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}=0$ for any $t<k_{2}$.

Case 3: $k_{3}$ exists but $k_{2}$ does not:
from the second line of [section F.3](#A6.Ex208), for any $t\in(0,T)$, we have

$$ $\displaystyle\varphi_{t+1}\overset{(a)}{\leq}$ $\displaystyle\varphi_{t}+\frac{\|\nabla_{y}g(x_{t},y_{t})\|^{2}}{\beta_{t+1}+\beta_{t}}+\frac{\|\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\varphi_{t+1}}$ $\displaystyle\leq$ $\displaystyle\varphi_{k_{3}}+\sum_{k=k_{3}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}+\beta_{k}}+\sum_{k=k_{3}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}$ $\displaystyle\leq$ $\displaystyle\beta_{k_{3}}+\gamma_{k_{3}}+\sum_{k=k_{3}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}+\beta_{k}}+\sum_{k=k_{3}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}$ $\displaystyle\overset{(b)}{=}$ $\displaystyle\beta_{t+1}+\gamma_{k_{3}}+\sum_{k=k_{3}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}$ $\displaystyle\leq$ $\displaystyle\beta_{t+1}+C_{\gamma}+\sum_{k=k_{3}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}$ $\displaystyle\leq$ $\displaystyle C_{\beta}+C_{\gamma}+\sum_{k=k_{3}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}},$ (69) $$

where (a) uses the second line of [section F.3](#A6.Ex208); and we take $\sum_{k=k_{3}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}=0$ for any $t<k_{3}$; (b) uses the first line of [section F.3](#A6.Ex195).

Case 4: both $k_{2}$ and $k_{3}$ exist: from the third line of [section F.3](#A6.Ex210), for any $t\in(0,T)$, we have

$$ $\displaystyle\varphi_{t+1}\leq$ $\displaystyle\beta_{k_{3}}+\gamma_{k_{3}}+\sum_{k=k_{3}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}+\sum_{k=k_{3}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\beta_{k_{2}}+\sum_{k=k_{2}}^{k_{3}-1}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}+C_{\gamma}+\sum_{k=k_{3}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}+\sum_{k=k_{3}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}$ $\displaystyle=$ $\displaystyle C_{\beta}+C_{\gamma}+\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}+\sum_{k=k_{3}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}},$ (70) $$

where (a) uses the third line of [section F.3](#A6.Ex195);
and we take $\sum_{k=k_{2}}^{k_{3}-1}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}=0$ when $k_{2}\geq k_{3}$, and $\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}=0$ for any $t<k_{2}$ and $\sum_{k=k_{3}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\gamma_{k+1}}=0$ for any $t<k_{3}$. It is easy to see that the upper bound of $\varphi_{t+1}$ in [section F.3](#A6.Ex215) is the largest among all cases. Thus, in the remaining proof, we only explore the upper bound of $\varphi_{t}$ in Case 4.

To further explore the bound of $\varphi_{t}$, we need to use some auxiliary results and bounds. So we split them into three parts as follows.

Part I: an auxiliary bound of $\sum\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$.

To further explore Case 4, we begin with a common term $\sum_{k=k_{0}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ for any $k_{0}\leq t$. Recall in [Lemma 10](#Thmlemma10), we have

$$ $\displaystyle\|v_{k}\|\leq\frac{\sqrt{2}}{\mu}{\varphi_{k+1}}+\frac{\sqrt{2}C_{f_{y}}}{\mu}\sqrt{k}=:\bar{a}{\varphi_{k+1}}+\bar{b}\sqrt{k},$ $$

where $\bar{a}$ and $\bar{b}$ refer to [lemma 15](#A6.Ex199).
According to [Lemma 1](#Thmlemma1), since $\alpha_{0}\geq 1$, for any integer $t>0$, we have

$$ $\displaystyle\sum_{k=k_{0}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}\leq$ $\displaystyle\sum_{k=0}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle\leq$ $\displaystyle\log\bigg{(}\sum_{k=0}^{t}\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}+\alpha_{0}^{2}\bigg{)}+1$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\log\bigg{(}\sum_{k=0}^{t}\big{(}C_{g_{xy}}\bar{a}{\varphi_{k+1}}+C_{g_{xy}}\bar{b}\sqrt{k}+C_{f_{x}}\big{)}^{2}+\alpha_{0}^{2}\bigg{)}+1$ $\displaystyle\leq$ $\displaystyle\log\bigg{(}\Big{(}\sum_{k=0}^{t}C_{g_{xy}}\bar{a}{\varphi_{k+1}}+C_{g_{xy}}\bar{b}\sqrt{k}+C_{f_{x}}+\alpha_{0}\Big{)}^{2}\bigg{)}+1$ $\displaystyle=$ $\displaystyle 2\log\bigg{(}\sum_{k=0}^{t}C_{g_{xy}}\bar{a}{\varphi_{k+1}}+C_{g_{xy}}\bar{b}\sqrt{k}+C_{f_{x}}+\alpha_{0}\bigg{)}+1$ $\displaystyle\leq$ $\displaystyle 2\log\bigg{(}(t+1)(C_{g_{xy}}\bar{a}{\varphi_{t+1}}+C_{g_{xy}}\bar{b}\sqrt{t}+C_{f_{x}}+\alpha_{0})\bigg{)}+1$ $\displaystyle=$ $\displaystyle 2\log(t+1)+2\log\big{(}C_{g_{xy}}\bar{a}{\varphi_{t+1}}+C_{g_{xy}}\bar{b}\sqrt{t}+C_{f_{x}}+\alpha_{0}\big{)}+1$ $\displaystyle\leq$ $\displaystyle 2\log(t+1)+2\log\big{(}(C_{g_{xy}}\bar{a}{\varphi_{t+1}}+C_{g_{xy}}\bar{b}+C_{f_{x}}+\alpha_{0})\sqrt{t}\big{)}+1$ $\displaystyle\leq$ $\displaystyle 3\log(t+1)+2\log(C_{g_{xy}}\bar{a}{\varphi_{t+1}}+C_{g_{xy}}\bar{b}+C_{f_{x}}+\alpha_{0})+1,$ (71) $$

where (a) follows from [Remark 3](#Thmremark3) and [Lemma 10](#Thmlemma10). Therefore, we obtain the upper bound of $\sum_{k=k_{0}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ for any $k_{0}\leq t$ in [section F.3](#A6.Ex218). Part I is completed.

Part II: a more general bound of $\sum\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$.

In [Lemma 12](#Thmlemma12), we show the bound of $\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ when $k_{2}$ exists. In Part II, we further provide a rough bound of $\sum_{k=\tilde{k}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ for any potential $\tilde{k}\leq T$.
Firstly, if $\tilde{k}\geq k_{2}$, it is easy to have

$$ $\displaystyle\sum_{k=\tilde{k}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}\leq\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}};$ $$

secondly, if $\tilde{k}<k_{2}$, we have

$$ $\displaystyle\sum_{k=\tilde{k}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}\leq$ $\displaystyle\sum_{k=\tilde{k}}^{k_{2}-1}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}+\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ $\displaystyle\leq$ $\displaystyle\frac{\sum_{k=\tilde{k}}^{k_{2}-1}\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{0}}+\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ $\displaystyle\leq$ $\displaystyle\frac{\beta_{k_{2}}^{2}-\beta_{\tilde{k}}^{2}}{\beta_{0}}+\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ $\displaystyle\leq$ $\displaystyle\frac{C_{\beta}^{2}-\beta_{0}^{2}}{\beta_{0}}+\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ $\displaystyle=$ $\displaystyle\frac{C_{\beta}^{2}}{\beta_{0}}-\beta_{0}+\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}.$ $$

Combining these two situations, since $C_{\beta}\geq\beta_{0}$, for any $\tilde{k}\leq t$, we have

$$ $\displaystyle\sum_{k=\tilde{k}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}\leq$ $\displaystyle\frac{C_{\beta}^{2}}{\beta_{0}}-\beta_{0}+\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\frac{C_{\beta}^{2}}{\beta_{0}}-\beta_{0}+\frac{(\mu+L_{g,1})C_{\beta}^{2}}{\mu^{2}}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}\varphi_{0}}$ $\displaystyle+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}}\sum_{k=k_{2}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}\varphi_{k+1}},$ (72) $$

where (a) uses [Lemma 12](#Thmlemma12). Thus, Part II is completed.

Part III: the bound of $\varphi_{t}$ in Case 4.

Here, we explore the upper bound of $\varphi_{t}$ in Case 4.
Recalling [section F.3](#A6.Ex215), we have

$$ $\displaystyle\varphi_{t+1}\leq$ $\displaystyle C_{\beta}+C_{\gamma}+\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}+\sum_{k=k_{3}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}=C_{\beta}+C_{\gamma}=C_{\varphi},$ $$

for $t\leq k_{\text{min}}:=\min\{k_{2},k_{3}\}$. For $t>k_{\text{min}}$, we have

$$ $\displaystyle\varphi_{t+1}\leq$ $\displaystyle C_{\beta}+C_{\gamma}+\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}+\sum_{k=k_{3}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle C_{\beta}+C_{\gamma}+\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})C_{\beta}^{2}}{\mu^{4}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}+\frac{4(\mu+C_{g_{yy}})C_{\gamma}^{2}}{\mu^{2}}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})(\mu+L_{g,1})L_{y}^{2}}{\mu^{3}L_{g,1}\varphi_{0}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\sum_{k=k_{2}-1}^{k_{3}-2}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}C_{\gamma}}\sum_{k=k_{3}-1}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle+\bigg{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\frac{1}{\mu^{2}}\sum_{k=k_{3}-1}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\bigg{[}\Big{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\Big{)}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\frac{1}{\mu^{2}}+1\bigg{]}\sum_{k=k_{2}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ $\displaystyle+C_{\beta}+C_{\gamma}+\frac{4(\mu+C_{g_{yy}})C_{\beta}^{2}}{\mu^{4}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}+\frac{4(\mu+C_{g_{yy}})C_{\gamma}^{2}}{\mu^{2}}$ $\displaystyle+\Big{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\Big{)}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\frac{1}{\mu^{2}}\Big{(}\frac{C_{\beta}^{2}}{\beta_{0}}-\beta_{0}\Big{)}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})(\mu+L_{g,1})L_{y}^{2}}{\mu^{3}L_{g,1}\varphi_{0}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\sum_{k=k_{2}-1}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}C_{\gamma}}\sum_{k=k_{3}-1}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle\overset{(c)}{\leq}$ $\displaystyle\bigg{(}\Big{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\Big{)}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\frac{1}{\mu^{2}}+1\bigg{)}\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}}\sum_{k=k_{2}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}\varphi_{k+1}}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})(\mu+L_{g,1})L_{y}^{2}}{\mu^{3}L_{g,1}\varphi_{0}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\sum_{k=k_{2}-1}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}C_{\gamma}}\sum_{k=k_{3}-1}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle+C_{\beta}+C_{\gamma}+\frac{4(\mu+C_{g_{yy}})C_{\beta}^{2}}{\mu^{4}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}+\frac{4(\mu+C_{g_{yy}})C_{\gamma}^{2}}{\mu^{2}}$ $\displaystyle+\Big{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\Big{)}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\frac{1}{\mu^{2}}\Big{(}\frac{C_{\beta}^{2}}{\beta_{0}}-\beta_{0}\Big{)}$ $\displaystyle+\bigg{[}\Big{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\Big{)}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\frac{1}{\mu^{2}}+1\bigg{]}\bigg{(}\frac{(\mu+L_{g,1})C_{\beta}^{2}}{\mu^{2}}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}\varphi_{0}}\bigg{)}$ $\displaystyle\leq$ $\displaystyle\bigg{[}\bigg{(}\Big{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\Big{)}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\frac{1}{\mu^{2}}+1\bigg{)}\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}C_{\beta}}$ $\displaystyle\quad+\frac{4(\mu+C_{g_{yy}})(\mu+L_{g,1})L_{y}^{2}}{\mu^{3}L_{g,1}\varphi_{0}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\bigg{]}\sum_{k=k_{2}-1}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}\gamma_{0}}\sum_{k=k_{3}-1}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle+C_{\beta}+C_{\gamma}+\frac{4(\mu+C_{g_{yy}})C_{\beta}^{2}}{\mu^{4}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}+\frac{4(\mu+C_{g_{yy}})C_{\gamma}^{2}}{\mu^{2}}$ $\displaystyle+\Big{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\Big{)}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\frac{1}{\mu^{2}}\Big{(}\frac{C_{\beta}^{2}}{\beta_{0}}-\beta_{0}\Big{)}$ $\displaystyle+\bigg{[}\Big{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\Big{)}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\frac{1}{\mu^{2}}+1\bigg{]}\bigg{(}\frac{(\mu+L_{g,1})C_{\beta}^{2}}{\mu^{2}}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}\varphi_{0}}\bigg{)}$ $\displaystyle\overset{(d)}{=:}$ $\displaystyle a_{0}\sum_{k=\min\{k_{2}-1,k_{3}-1\}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}+b_{0}$ $\displaystyle\leq$ $\displaystyle a_{0}\sum_{k=\min\{k_{2},k_{3}\}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}+a_{0}+b_{0}$ $\displaystyle\overset{(e)}{\leq}$ $\displaystyle a_{0}\bigg{[}3\log(t+1)+2\log\bigg{(}{\varphi_{t+1}}+\frac{C_{g_{xy}}\bar{b}+C_{f_{x}}+\alpha_{0}}{C_{g_{xy}}\bar{a}}\bigg{)}+2\log(C_{g_{xy}}\bar{a})+1\bigg{]}+a_{0}+b_{0},$ (73) $$

where (a) uses [Lemma 13](#Thmlemma13);
(b) uses the first line in [section F.3](#A6.Ex232) by replacing $\tilde{k}$ with $k_{3}-1$;
(c) results from [section F.3](#A6.Ex116);
(d) refers to [lemma 15](#A6.Ex199);
(e) uses [section F.3](#A6.Ex218).
Since $\min\{k_{2},k_{3}\}\leq T$,
we have $\varphi_{t+1}\geq\min\{C_{\beta},C_{\gamma}\}\geq\max\{64a_{0}^{2},1\}$, which indicate that

(i) if $8a_{0}\leq 1$, we have

$$ $\displaystyle 4a_{0}\log(\varphi_{t+1})\leq\frac{\log(\varphi_{t+1})}{2}\leq\frac{\varphi_{t+1}}{2}\leq\varphi_{t+1};$ $$

(ii) if $8a_{0}>1$, we have

$$ $\displaystyle\varphi_{t+1}-4a_{0}\log(\varphi_{t+1})=\varphi_{t+1}-8a_{0}\log(\sqrt{\varphi_{t+1}})\geq 8a_{0}\big{(}\sqrt{\varphi_{t+1}}-\log(\sqrt{\varphi_{t+1}})\big{)}\geq 0.$ $$

Combining (i) and (ii), we have $4a_{0}\log(\varphi_{t+1})\leq\varphi_{t+1}$. Then we obtain

$$ $\displaystyle\varphi_{t+1}\leq$ $\displaystyle a_{0}\bigg{[}3\log(t+1)+2\log\bigg{(}{\varphi_{t+1}}+\frac{C_{g_{xy}}\bar{b}+C_{f_{x}}+\alpha_{0}}{C_{g_{xy}}\bar{a}}\bigg{)}+2\log(C_{g_{xy}}\bar{a})+1\bigg{]}+a_{0}+b_{0}$ $\displaystyle\leq$ $\displaystyle a_{0}\bigg{[}3\log(t+1)+2\log({\varphi_{t+1}})+2\log\bigg{(}1+\frac{C_{g_{xy}}\bar{b}+C_{f_{x}}+\alpha_{0}}{C_{g_{xy}}\bar{a}}\bigg{)}+2\log(C_{g_{xy}}\bar{a})+1\bigg{]}+a_{0}+b_{0}$ $\displaystyle\leq$ $\displaystyle\frac{1}{2}\varphi_{t+1}+a_{0}\bigg{[}3\log(t+1)+2\log\bigg{(}1+\frac{C_{g_{xy}}\bar{b}+C_{f_{x}}+\alpha_{0}}{C_{g_{xy}}\bar{a}}\bigg{)}+2\log(C_{g_{xy}}\bar{a})+1\bigg{]}+a_{0}+b_{0},$ $$

which indicates that

$$ $\displaystyle\varphi_{t+1}\leq$ $\displaystyle 6a_{0}\log(t+1)+4a_{0}\log\Big{(}1+\frac{C_{g_{xy}}\bar{b}+C_{f_{x}}+\alpha_{0}}{C_{g_{xy}}\bar{a}}\Big{)}+4a_{0}\log(C_{g_{xy}}\bar{a})+4a_{0}+2b_{0}$ $\displaystyle\overset{(a)}{=:}$ $\displaystyle a_{1}\log(t+1)+b_{1},$ (74) $$

where (a) refers to [eq. 65](#A6.E65).
Thus, Part III is completed and the proof of this lemma is completed.
∎

###### Lemma 16 .

Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2), for any integer $k_{0}\in[0,t)$, we have the upper bounds in terms of logarithmic functions as

$$ $\displaystyle\sum_{k=k_{0}}^{t}$ $\displaystyle\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}\leq 5\log(t+1)+c_{2},$ $\displaystyle\sum_{k=k_{0}}^{t}$ $\displaystyle\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}\leq a_{2}\log(t+1)+b_{2},$ $\displaystyle\sum_{k=k_{0}}^{t}$ $\displaystyle\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}\leq a_{3}\log(t+1)+b_{3},$ $$

where referring to [eq. 65](#A6.E65), [lemma 15](#A6.Ex199),
$c_{2}$, $a_{2}$, $b_{2}$, $a_{3}$, $b_{3}$ are defined as

$$ $\displaystyle c_{2}:=$ $\displaystyle 2\log\big{(}C_{g_{xy}}\bar{a}a_{1}+C_{g_{xy}}\bar{a}b_{1}+C_{g_{xy}}\bar{b}+C_{f_{x}}+\alpha_{0}\big{)}+1,$ $\displaystyle a_{2}:=$ $\displaystyle\frac{5(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}C_{\beta}},\quad b_{2}:=\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}C_{\beta}}c_{2}+\Big{(}\frac{C_{\beta}^{2}}{\beta_{0}}-\beta_{0}+\frac{(\mu+L_{g,1})C_{\beta}^{2}}{\mu^{2}}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}\varphi_{0}}\Big{)},$ $\displaystyle a_{3}:=$ $\displaystyle\frac{20(\mu+C_{g_{yy}})(\mu+L_{g,1})L_{y}^{2}}{\mu^{3}L_{g,1}\varphi_{0}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}+\frac{20(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}C_{\gamma}}$ $\displaystyle+\big{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\big{)}\big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\big{)}^{2}\frac{a_{2}}{\mu^{2}},$ $\displaystyle b_{3}:=$ $\displaystyle\frac{C_{\gamma}^{2}}{\gamma_{0}}-\gamma_{0}+\frac{4(\mu+C_{g_{yy}})C_{\beta}^{2}}{\mu^{4}}\big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\big{)}^{2}+\frac{4(\mu+C_{g_{yy}})C_{\gamma}^{2}}{\mu^{2}}$ $\displaystyle+\bigg{(}\frac{4(\mu+C_{g_{yy}})(\mu+L_{g,1})L_{y}^{2}}{\mu^{3}L_{g,1}\varphi_{0}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}C_{\gamma}}\bigg{)}c_{2}$ $\displaystyle+\big{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\big{)}\big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\big{)}^{2}\frac{b_{2}}{\mu^{2}}.$ (75) $$

###### Proof.

Based on the logarithmic-function form bound in [Lemma 15](#Thmlemma15), we can further have the logarithmic-function form bounds of the components in [Lemma 11](#Thmlemma11) as the following 3 parts.

Part I: the bound of $\sum\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ in terms of logarithmic function.

Firstly, we bound $\sum_{k=k_{0}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ for arbitrary $k_{0}<t$.
Back to [section F.3](#A6.Ex218), by plugging in [section F.3](#A6.Ex265), we have

$$ $\displaystyle\sum_{k=k_{0}}^{t}$ $\displaystyle\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle\leq$ $\displaystyle 3\log(t+1)+2\log(C_{g_{xy}}\bar{a}\varphi_{t+1}+C_{g_{xy}}\bar{b}+C_{f_{x}}+\alpha_{0})+1$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle 3\log(t+1)+2\log\big{(}C_{g_{xy}}\bar{a}a_{1}\log(t+1)+C_{g_{xy}}\bar{a}b_{1}+C_{g_{xy}}\bar{b}+C_{f_{x}}+\alpha_{0}\big{)}+1$ $\displaystyle\leq$ $\displaystyle 3\log(t+1)+2\log\big{(}C_{g_{xy}}\bar{a}a_{1}(t+1)+C_{g_{xy}}\bar{a}b_{1}+C_{g_{xy}}\bar{b}+C_{f_{x}}+\alpha_{0}\big{)}+1$ $\displaystyle\leq$ $\displaystyle 3\log(t+1)+2\log\big{(}(C_{g_{xy}}\bar{a}a_{1}+C_{g_{xy}}\bar{a}b_{1}+C_{g_{xy}}\bar{b}+C_{f_{x}}+\alpha_{0})(t+1)\big{)}+1$ $\displaystyle\leq$ $\displaystyle 5\log(t+1)+2\log\big{(}C_{g_{xy}}\bar{a}a_{1}+C_{g_{xy}}\bar{a}b_{1}+C_{g_{xy}}\bar{b}+C_{f_{x}}+\alpha_{0}\big{)}+1$ $\displaystyle\overset{(b)}{=:}$ $\displaystyle 5\log(t+1)+c_{2},$ (76) $$

where (a) results from [section F.3](#A6.Ex265); (b) refers to [lemma 16](#A6.Ex269).

Part II: the bound of $\sum\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ in terms of logarithmic function.

Secondly, we bound $\sum_{k=k_{0}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$.
We split this part into two cases using [Lemma 4](#Thmlemma4).

Case 1: If $\beta_{t+1}\leq C_{\beta}$, we have

$$ $\displaystyle\sum_{k=k_{0}}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}\leq\frac{\sum_{k=k_{0}}^{t}\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{0}}\leq\frac{\beta_{t+1}^{2}-\beta_{k_{0}}^{2}}{\beta_{0}}\leq\frac{C_{\beta}^{2}-\beta_{0}^{2}}{\beta_{0}}=\frac{C_{\beta}^{2}}{\beta_{0}}-\beta_{0}\leq b_{2}.$ $$

Case 2: If $\beta_{t+1}>C_{\beta}$, we have $k_{2}\leq t$, where $k_{2}$ refers to [Lemma 4](#Thmlemma4). Then we can use [section F.3](#A6.Ex232), which indicates

$$ $\displaystyle\sum_{k=k_{0}}^{t}$ $\displaystyle\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ $\displaystyle\leq$ $\displaystyle\bigg{(}\frac{C_{\beta}^{2}}{\beta_{0}}-\beta_{0}+\frac{(\mu+L_{g,1})C_{\beta}^{2}}{\mu^{2}}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}\varphi_{0}}\bigg{)}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}C_{\beta}}\sum_{k=k_{2}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle\leq$ $\displaystyle\frac{5(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}C_{\beta}}\log(t+1)+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}C_{\beta}}c_{2}+\bigg{(}\frac{C_{\beta}^{2}}{\beta_{0}}-\beta_{0}+\frac{(\mu+L_{g,1})C_{\beta}^{2}}{\mu^{2}}+\frac{(\mu+L_{g,1})^{2}L_{y}^{2}}{\mu L_{g,1}\varphi_{0}}\bigg{)}$ $\displaystyle\overset{(a)}{=:}$ $\displaystyle a_{2}\log(t+1)+b_{2},$ (77) $$

where the second inequality uses ([F.3](#A6.Ex275)), and (a) refers to [lemma 16](#A6.Ex269).
Since the upper bound of Case 2 is larger, we take [section F.3](#A6.Ex282) as our final result.

Part III: the bound of $\sum\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}$ in terms of logarithmic function.

Last, we bound $\sum_{k=k_{0}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}$.
We split this part into two cases using [Lemma 4](#Thmlemma4).

Case 1: If $\gamma_{t+1}\leq C_{\gamma}$, we have

$$ $\displaystyle\sum_{k=k_{0}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}\leq\frac{\sum_{k=k_{0}}^{t}\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{0}}\leq\frac{C_{\gamma}^{2}-\gamma_{0}^{2}}{\gamma_{0}}\leq\frac{C_{\gamma}^{2}}{\gamma_{0}}-\gamma_{0}\leq b_{3}.$ $$

Case 2: If $\gamma_{t+1}>C_{\gamma}$, we have $k_{3}\leq t$, where $k_{3}$ refers to [Lemma 4](#Thmlemma4).

$$ $\displaystyle\sum_{k=k_{0}}^{t}$ $\displaystyle\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\sum_{k=k_{0}}^{k_{3}-1}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}+\sum_{k=k_{3}}^{t}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\frac{C_{\gamma}^{2}}{\gamma_{0}}-\gamma_{0}+\frac{4(\mu+C_{g_{yy}})C_{\beta}^{2}}{\mu^{4}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}+\frac{4(\mu+C_{g_{yy}})C_{\gamma}^{2}}{\mu^{2}}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})(\mu+L_{g,1})L_{y}^{2}}{\mu^{3}L_{g,1}\varphi_{0}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\sum_{k=k_{2}-1}^{k_{3}-2}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}C_{\gamma}}\sum_{k=k_{3}-1}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}^{2}}$ $\displaystyle+\bigg{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\frac{1}{\mu^{2}}\sum_{k=k_{3}-1}^{t}\frac{\|\nabla_{y}g(x_{k},y_{k})\|^{2}}{\beta_{k+1}}$ $\displaystyle\overset{(c)}{\leq}$ $\displaystyle\frac{C_{\gamma}^{2}}{\gamma_{0}}-\gamma_{0}+\frac{4(\mu+C_{g_{yy}})C_{\beta}^{2}}{\mu^{4}}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}+\frac{4(\mu+C_{g_{yy}})C_{\gamma}^{2}}{\mu^{2}}$ $\displaystyle+\bigg{(}\frac{4(\mu+C_{g_{yy}})(\mu+L_{g,1})L_{y}^{2}}{\mu^{3}L_{g,1}\varphi_{0}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}+\frac{4(\mu+C_{g_{yy}})^{2}L_{v}^{2}}{\mu C_{g_{yy}}C_{\gamma}}\bigg{)}\big{(}5\log(t+1)+c_{2}\big{)}$ $\displaystyle+\bigg{(}\frac{4(\mu+C_{g_{yy}})^{2}}{\mu C_{g_{yy}}}+8\bigg{)}\bigg{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\bigg{)}^{2}\frac{1}{\mu^{2}}\big{(}a_{2}\log(t+1)+b_{2}\big{)}$ $\displaystyle\overset{(d)}{=:}$ $\displaystyle a_{3}\log(t+1)+b_{3},$ (78) $$

where (a) allows $\sum_{k=k_{0}}^{k_{3}-1}\frac{\|\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}=0$ when $k_{0}\geq k_{3}$; (b) uses $C_{\gamma}\geq\gamma_{0}$ and [Lemma 13](#Thmlemma13); (c) follows from [section F.3](#A6.Ex275) and [section F.3](#A6.Ex282);
(d) refers to [lemma 16](#A6.Ex269). Since the upper bound of Case 2 is larger, we take [section F.3](#A6.Ex286) as our final result.

Thus, the proof is complete.
∎

Next, we show the upper bound of $\alpha_{t}$.

###### Lemma 17 (The upper bound of $\alpha_{t}$ ) .

Under Assumptions [1](#Thmassumption1), [2](#Thmassumption2), [3](#Thmassumption3), suppose the number of total iteration rounds in [Algorithm 2](#alg2) is $T$.
If there exists $k_{1}\leq T$ described in [Lemma 4](#Thmlemma4), we have

$$ $\left\{\begin{aligned} \alpha_{t}\leq&C_{\alpha},\quad&t\leq k_{1};\\ \alpha_{t}\leq&C_{\alpha}+\Big{(}a_{4}\log(t)+b_{4}+{4}\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}\Big{)}\varphi_{t},\quad&t\geq k_{1},\end{aligned}\right.$ $$

where $a_{4}$, $b_{4}$ are defined as

$$ $\displaystyle a_{4}:=$ $\displaystyle\frac{2\bar{L}^{2}a_{2}}{\mu^{2}C_{\alpha}}\Big{[}1+\frac{2}{\mu^{2}}\big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\big{)}^{2}\Big{]}+\frac{4\bar{L}^{2}a_{3}}{\mu^{2}C_{\alpha}}$ $\displaystyle b_{4}:=$ $\displaystyle\frac{2\bar{L}^{2}b_{2}}{\mu^{2}C_{\alpha}}\Big{[}1+\frac{2}{\mu^{2}}\big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\big{)}^{2}\Big{]}+\frac{4\bar{L}^{2}b_{3}}{\mu^{2}C_{\alpha}}+\frac{2L_{\Phi}}{\varphi_{0}^{2}}\frac{C_{\alpha}^{2}}{\alpha_{0}^{2}},$ (79) $$

and the upper bound of $\varphi_{t}:=\max\{\beta_{t},\gamma_{t}\}$ refers to [Lemma 15](#Thmlemma15).
When such $k_{1}$ does not exist, we have $\alpha_{t}\leq C_{\alpha}$ for any $t\leq T$.

###### Proof.

According to [Lemma 4](#Thmlemma4), the proof can be split into the following three cases.

Case 1: if $\alpha_{T}\leq C_{\alpha}$, for any $t<T$, we have the upper bound of $\alpha_{t+1}$ as $\alpha_{t+1}\leq C_{\alpha}$.

Case 2: if $\alpha_{T}>C_{\alpha}$, there exists $k_{1}\leq T$ described in [Lemma 4](#Thmlemma4).
Then we have the upper bound of $\alpha_{t+1}$ as $\alpha_{t+1}\leq C_{\alpha}$ for any $t<k_{1}$.

Case 3: in the remaining proof, we only consider and explore the case $k_{1}\leq t\leq T$ when $\alpha_{T}>C_{\alpha}$.

From [Lemma 11](#Thmlemma11), for $k\geq k_{1}$, we have

$$ $\displaystyle\Phi(x_{k+1})\leq$ $\displaystyle\Phi(x_{k})-\frac{1}{2\alpha_{k+1}\varphi_{k+1}}\|\nabla\Phi(x_{k})\|^{2}-\frac{1}{4\alpha_{k+1}\varphi_{k+1}}\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}$ $\displaystyle+\frac{\bar{L}^{2}}{2\mu^{2}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\frac{\big{\|}\nabla_{y}g(x_{k},y_{k})\big{\|}^{2}}{\alpha_{k+1}\varphi_{k+1}}+\frac{\bar{L}^{2}}{\mu^{2}}\frac{\big{\|}\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}\varphi_{k+1}},$ $$

which indicates that

$$ $\displaystyle\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}\varphi_{k+1}}\leq 4\big{(}\Phi(x_{k})-\Phi(x_{k+1})\big{)}$ $\displaystyle\quad\quad\quad\quad\quad+\frac{2\bar{L}^{2}}{\mu^{2}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\frac{\big{\|}\nabla_{y}g(x_{k},y_{k})\big{\|}^{2}}{\alpha_{k+1}\varphi_{k+1}}+\frac{4\bar{L}^{2}}{\mu^{2}}\frac{\big{\|}\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}\varphi_{k+1}}.$ $$

By taking summation, we have

$$ $\displaystyle\sum_{k=k_{1}}^{t}$ $\displaystyle\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}\varphi_{k+1}}$ $\displaystyle\leq$ $\displaystyle 4\big{(}\Phi(x_{k_{1}})-\inf_{x}\Phi(x)\big{)}+\frac{2\bar{L}^{2}}{\mu^{2}C_{\alpha}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\sum_{k=k_{1}}^{t}\frac{\big{\|}\nabla_{y}g(x_{k},y_{k})\big{\|}^{2}}{\varphi_{k+1}}$ $\displaystyle+\frac{4\bar{L}^{2}}{\mu^{2}C_{\alpha}}\sum_{k=k_{1}}^{t}\frac{\big{\|}\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}.$ (80) $$

For $\Phi(x_{k_{1}})$, by telescoping [lemma 11](#A6.Ex82) in [Lemma 11](#Thmlemma11), we get

$$ $\displaystyle\Phi(x_{k_{1}})\leq$ $\displaystyle\Phi(x_{0})+\frac{L_{\Phi}}{2}\sum_{k=0}^{k_{1}-1}\frac{\|\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2}}{\alpha_{t+1}^{2}\varphi_{t+1}^{2}}$ $\displaystyle+\frac{\bar{L}^{2}}{2\mu^{2}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\sum_{k=0}^{k_{1}-1}\frac{\big{\|}\nabla_{y}g(x_{t},y_{t})\big{\|}^{2}}{\alpha_{t+1}\varphi_{t+1}}$ $\displaystyle+\frac{\bar{L}^{2}}{\mu^{2}}\sum_{k=0}^{k_{1}-1}\frac{\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\alpha_{t+1}\varphi_{t+1}}.$ (81) $$

By plugging [section F.3](#A6.Ex303) into [section F.3](#A6.Ex301), we have

$$ $\displaystyle\sum_{k=k_{1}}^{t}$ $\displaystyle\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}\varphi_{k+1}}$ $\displaystyle\leq$ $\displaystyle 4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{2\bar{L}^{2}}{\mu^{2}C_{\alpha}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\sum_{k=0}^{t}\frac{\big{\|}\nabla_{y}g(x_{k},y_{k})\big{\|}^{2}}{\varphi_{k+1}}$ $\displaystyle+\frac{4\bar{L}^{2}}{\mu^{2}C_{\alpha}}\sum_{k=0}^{t}\frac{\big{\|}\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}+\frac{2L_{\Phi}}{\varphi_{0}^{2}}\frac{C_{\alpha}^{2}}{\alpha_{0}^{2}}$ $\displaystyle\leq$ $\displaystyle 4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{2\bar{L}^{2}}{\mu^{2}C_{\alpha}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\sum_{k=0}^{t}\frac{\big{\|}\nabla_{y}g(x_{k},y_{k})\big{\|}^{2}}{\beta_{k+1}}$ $\displaystyle+\frac{4\bar{L}^{2}}{\mu^{2}C_{\alpha}}\sum_{k=0}^{t}\frac{\big{\|}\nabla_{v}R(x_{k},y_{k},v_{k})\|^{2}}{\varphi_{k+1}}+\frac{2L_{\Phi}}{\varphi_{0}^{2}}\frac{C_{\alpha}^{2}}{\alpha_{0}^{2}}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle 4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{2\bar{L}^{2}}{\mu^{2}C_{\alpha}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\big{(}a_{2}\log(t+1)+b_{2}\big{)}$ $\displaystyle+\frac{4\bar{L}^{2}}{\mu^{2}C_{\alpha}}\big{(}a_{3}\log(t+1)+b_{3}\big{)}+\frac{2L_{\Phi}}{\varphi_{0}^{2}}\frac{C_{\alpha}^{2}}{\alpha_{0}^{2}}$ $\displaystyle\overset{(b)}{=:}$ $\displaystyle a_{4}\log(t+1)+b_{4}+4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)},$ (82) $$

where
(a) plugs in [section F.3](#A6.Ex282) and [section F.3](#A6.Ex286); (b) refers to [lemma 17](#A6.Ex296).
This immediately implies

$$ $\displaystyle\sum_{k=k_{1}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}}\leq\Big{(}a_{4}\log(t+1)+b_{4}+4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}\Big{)}\varphi_{t+1}.$ (83) $$

Similarly, we can have the upper bound of $\alpha_{t+1}$ as

$$ $\displaystyle\alpha_{t+1}\leq$ $\displaystyle\alpha_{k_{1}}+\sum_{k=k_{1}}^{t}\frac{\|\bar{\nabla}f(x_{k},y_{k},v_{k})\|^{2}}{\alpha_{k+1}}$ $\displaystyle\leq$ $\displaystyle C_{\alpha}+\Big{(}a_{4}\log(t+1)+b_{4}+4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}\Big{)}\varphi_{t+1}.$ (84) $$

Then the upper bound of $\alpha_{t+1}$ is proved.
∎

###### Lemma 11 .

###### Proof.

###### Lemma 12 .

###### Proof.

###### Lemma 13 .

###### Proof.

###### Lemma 14 .

###### Proof.

###### Lemma 15 .

###### Proof.

###### Lemma 16 .

###### Proof.

###### Lemma 17 (The upper bound of α t subscript 𝛼 𝑡 \alpha_{t} ) .

###### Proof.

### F.4 Proof of Theorem 2

Here we still assume the total iteration rounds of Algorithm [2](#alg2) is $T$.
According to [Lemma 4](#Thmlemma4), the proof can be split into the following two cases.

Case 1: If $\alpha_{T}\leq C_{\alpha}$, then by [Lemma 11](#Thmlemma11) and [Lemma 17](#Thmlemma17), we have

$$ $\displaystyle\frac{\|\nabla\Phi(x_{t})\|^{2}}{\alpha_{t+1}\varphi_{t+1}}\leq$ $\displaystyle 2\big{(}\Phi(x_{t})-\Phi(x_{t+1})\big{)}+\frac{L_{\Phi}}{\alpha_{t+1}^{2}\varphi_{t+1}^{2}}\|\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2}$ $\displaystyle+\frac{\bar{L}^{2}}{\mu^{2}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\frac{\big{\|}\nabla_{y}g(x_{t},y_{t})\big{\|}^{2}}{\alpha_{t+1}\varphi_{t+1}}+\frac{2\bar{L}^{2}}{\mu^{2}}\frac{\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\alpha_{t+1}\varphi_{t+1}},$ $$

By taking the average, we have

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\frac{\|\nabla\Phi(x_{t})\|^{2}}{\alpha_{t+1}\varphi_{t+1}}\leq$ $\displaystyle\frac{2}{T}\big{(}\Phi(x_{0})-\Phi(x_{T})\big{)}+\frac{L_{\Phi}}{\alpha_{0}^{2}\varphi_{0}^{2}}\frac{1}{T}\sum_{t=0}^{T-1}\|\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2}$ $\displaystyle+\frac{\bar{L}^{2}}{\mu^{2}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\frac{1}{T}\sum_{t=0}^{T-1}\frac{\big{\|}\nabla_{y}g(x_{t},y_{t})\big{\|}^{2}}{\alpha_{t+1}\varphi_{t+1}}$ $\displaystyle+\frac{2\bar{L}^{2}}{\mu^{2}}\frac{1}{T}\sum_{t=0}^{T-1}\frac{\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\alpha_{t+1}\varphi_{t+1}}$ $\displaystyle\leq$ $\displaystyle\frac{2}{T}\big{(}\Phi(x_{0})-\Phi(x_{T})\big{)}+\frac{L_{\Phi}C_{\alpha}^{2}}{T\alpha_{0}^{2}\varphi_{0}^{2}}$ $\displaystyle+\frac{\bar{L}^{2}}{\mu^{2}\alpha_{0}T}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\sum_{t=0}^{T-1}\frac{\big{\|}\nabla_{y}g(x_{t},y_{t})\big{\|}^{2}}{\beta_{t+1}}$ $\displaystyle+\frac{2\bar{L}^{2}}{\mu^{2}\alpha_{0}T}\sum_{t=0}^{T-1}\frac{\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\varphi_{t+1}}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\frac{2}{T}\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{L_{\Phi}C_{\alpha}^{2}}{T\alpha_{0}^{2}\varphi_{0}^{2}}$ $\displaystyle+\frac{\bar{L}^{2}}{\mu^{2}\alpha_{0}T}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\big{(}a_{2}\log(T)+b_{2}\big{)}$ $\displaystyle+\frac{2\bar{L}^{2}}{\mu^{2}\alpha_{0}T}\big{(}a_{3}\log(T)+b_{3}\big{)}$ $\displaystyle=$ $\displaystyle\frac{1}{2T}\Big{(}a_{4}\log(T)+b_{4}+4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}\Big{)},$ (85) $$

where (a) uses [Lemma 16](#Thmlemma16) with $k_{0}=0$.

Case 2:
If $\alpha_{T}>C_{\alpha}$, by [Lemma 4](#Thmlemma4),
there exists $k_{1}\leq T_{0}$ such that $\alpha_{k_{1}}\leq C_{\alpha}$, $\alpha_{k_{1}+1}>C_{\alpha}$.

Then for $t<k_{1}$ when $\alpha_{T}>C_{\alpha}$, from [Lemma 11](#Thmlemma11), we have

$$ $\displaystyle\frac{\|\nabla\Phi(x_{t})\|^{2}}{\alpha_{t+1}\varphi_{t+1}}\leq$ $\displaystyle 2\big{(}\Phi(x_{t})-\Phi(x_{t+1})\big{)}+\frac{L_{\Phi}}{\alpha_{t+1}^{2}\varphi_{t+1}^{2}}\|\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2}$ $\displaystyle+\frac{\bar{L}^{2}}{\mu^{2}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\frac{\big{\|}\nabla_{y}g(x_{t},y_{t})\big{\|}^{2}}{\alpha_{t+1}\varphi_{t+1}}+\frac{2\bar{L}^{2}}{\mu^{2}}\frac{\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\alpha_{t+1}\varphi_{t+1}}.$ $$

For $t\geq k_{1}$ when $\alpha_{T}>C_{\alpha}$, from [Lemma 11](#Thmlemma11), we have

$$ $\displaystyle\frac{\|\nabla\Phi(x_{t})\|^{2}}{\alpha_{t+1}\varphi_{t+1}}\leq$ $\displaystyle 2\big{(}\Phi(x_{t})-\Phi(x_{t+1})\big{)}$ $\displaystyle+\frac{\bar{L}^{2}}{\mu^{2}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\frac{\big{\|}\nabla_{y}g(x_{t},y_{t})\big{\|}^{2}}{\alpha_{t+1}\varphi_{t+1}}+\frac{2\bar{L}^{2}}{\mu^{2}}\frac{\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\alpha_{t+1}\varphi_{t+1}}.$ $$

By taking the average, we can merge $t<k_{1}$ and $t\geq k_{1}$ as

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\frac{\|\nabla\Phi(x_{t})\|^{2}}{\alpha_{t+1}\varphi_{t+1}}=$ $\displaystyle\frac{1}{T}\sum_{t=0}^{k_{1}-1}\frac{\|\nabla\Phi(x_{t})\|^{2}}{\alpha_{t+1}\varphi_{t+1}}+\frac{1}{T}\sum_{t=k_{1}}^{T-1}\frac{\|\nabla\Phi(x_{t})\|^{2}}{\alpha_{t+1}\varphi_{t+1}}$ $\displaystyle\leq$ $\displaystyle\frac{2}{T}\big{(}\Phi(x_{0})-\Phi(x_{k_{1}})\big{)}+\frac{L_{\Phi}}{\alpha_{0}^{2}\varphi_{0}^{2}}\frac{1}{T}\sum_{t=0}^{k_{1}-1}\|\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2}$ $\displaystyle+\frac{\bar{L}^{2}}{\mu^{2}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\frac{1}{T}\sum_{t=0}^{k_{1}-1}\frac{\big{\|}\nabla_{y}g(x_{t},y_{t})\big{\|}^{2}}{\alpha_{t+1}\varphi_{t+1}}$ $\displaystyle+\frac{2\bar{L}^{2}}{\mu^{2}}\frac{1}{T}\sum_{t=0}^{k_{1}-1}\frac{\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\alpha_{t+1}\varphi_{t+1}}$ $\displaystyle+\frac{2}{T}\big{(}\Phi(x_{k_{1}})-\Phi(x_{T})\big{)}$ $\displaystyle+\frac{\bar{L}^{2}}{\mu^{2}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\frac{1}{T}\sum_{t={k_{1}}}^{T-1}\frac{\big{\|}\nabla_{y}g(x_{t},y_{t})\big{\|}^{2}}{\alpha_{t+1}\varphi_{t+1}}$ $\displaystyle+\frac{2\bar{L}^{2}}{\mu^{2}}\frac{1}{T}\sum_{t={k_{1}}}^{T-1}\frac{\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\alpha_{t+1}\varphi_{t+1}}$ $\displaystyle\leq$ $\displaystyle\frac{2}{T}\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{L_{\Phi}}{\alpha_{0}^{2}\varphi_{0}^{2}}\frac{1}{T}\sum_{t=0}^{k_{1}-1}\|\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2}$ $\displaystyle+\frac{\bar{L}^{2}}{\mu^{2}}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\frac{1}{T}\sum_{t=0}^{T-1}\frac{\big{\|}\nabla_{y}g(x_{t},y_{t})\big{\|}^{2}}{\alpha_{t+1}\varphi_{t+1}}$ $\displaystyle+\frac{2\bar{L}^{2}}{\mu^{2}}\frac{1}{T}\sum_{t=0}^{T-1}\frac{\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\alpha_{t+1}\varphi_{t+1}}$ $\displaystyle\leq$ $\displaystyle\frac{2}{T}\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{L_{\Phi}}{\alpha_{0}^{2}\varphi_{0}^{2}}\frac{1}{T}\sum_{t=0}^{k_{1}-1}\|\bar{\nabla}f(x_{t},y_{t},v_{t})\|^{2}$ $\displaystyle+\frac{\bar{L}^{2}}{\mu^{2}\alpha_{0}T}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\sum_{t=0}^{T-1}\frac{\big{\|}\nabla_{y}g(x_{t},y_{t})\big{\|}^{2}}{\varphi_{t+1}}$ $\displaystyle+\frac{2\bar{L}^{2}}{\mu^{2}\alpha_{0}T}\sum_{t=0}^{T-1}\frac{\big{\|}\nabla_{v}R(x_{t},y_{t},v_{t})\|^{2}}{\varphi_{t+1}}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\frac{2}{T}\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}+\frac{L_{\Phi}C_{\alpha}^{2}}{T\alpha_{0}^{2}\varphi_{0}^{2}}$ $\displaystyle+\frac{\bar{L}^{2}}{\mu^{2}\alpha_{0}T}\bigg{[}1+\frac{2}{\mu^{2}}\Big{(}\frac{L_{g,2}C_{f_{y}}}{\mu}+L_{f,1}\Big{)}^{2}\bigg{]}\big{(}a_{2}\log(T)+b_{2}\big{)}$ $\displaystyle+\frac{2\bar{L}^{2}}{\mu^{2}\alpha_{0}T}\big{(}a_{3}\log(T)+b_{3}\big{)}$ $\displaystyle=$ $\displaystyle\frac{1}{2T}\Big{(}a_{4}\log(T)+b_{4}+4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}\Big{)},$ (86) $$

where (a) uses [Lemma 16](#Thmlemma16) by plugging in $k_{0}=0$.

Note that Case 1 and Case 2 indicate the same result.
Thus, we have

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla\Phi(x_{t})\|^{2}\leq$ $\displaystyle\frac{1}{2T}\Big{(}a_{4}\log(T)+b_{4}+4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}\Big{)}\alpha_{T}\varphi_{T}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\frac{1}{2T}\Big{[}\Big{(}a_{4}\log(T)+b_{4}+4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}\Big{)}^{2}\varphi_{T}^{2}$ $\displaystyle\quad\quad+C_{\alpha}\Big{(}a_{4}\log(T)+b_{4}+4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}\Big{)}\varphi_{T}\Big{]}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\frac{1}{2T}\Big{[}\Big{(}a_{4}\log(T)+b_{4}+4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}\Big{)}^{2}\big{(}a_{1}\log(T)+b_{1}\big{)}^{2}$ $\displaystyle\quad\quad+C_{\alpha}\Big{(}a_{4}\log(T)+b_{4}+4\big{(}\Phi(x_{0})-\inf_{x}\Phi(x)\big{)}\Big{)}\big{(}a_{1}\log(T)+b_{1}\big{)}\Big{]}$ $\displaystyle=$ $\displaystyle\mathcal{O}\bigg{(}\frac{\log^{4}(T)}{T}\bigg{)}.$ $$

where (a) follows from [Lemma 17](#Thmlemma17);
(b) results from [Lemma 15](#Thmlemma15).
Thus, the proof is finished.

### F.5 Complexity Analysis of Algorithm 2 (Proof of Corollary 2 )

Recall in [Theorem 2](#Thmtheorem2), we know that there exist a constant $M$ such that

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla\Phi(x_{t})\|^{2}\leq\frac{M\log^{4}(T)}{T}.$ $$

When we set the iteration number $T=\frac{MN}{\epsilon}\log^{4}(\frac{M}{\epsilon})$ and assume the constant $N=12^{4}$, we have

$$ $\displaystyle\frac{M\log^{4}(T)}{T}=$ $\displaystyle\frac{M\log^{4}(\frac{MN}{\epsilon}\log^{4}(\frac{M}{\epsilon}))}{\frac{MN}{\epsilon}\log^{4}(\frac{M}{\epsilon})}$ $\displaystyle\leq$ $\displaystyle\frac{[\log(N)+\log(\frac{M}{\epsilon})+4\log(\log(\frac{M}{\epsilon}))]^{4}}{N\log^{4}(\frac{M}{\epsilon})}\cdot\epsilon$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\bigg{(}\frac{\log(N)+2\log(\frac{M}{\epsilon})}{N^{\frac{1}{4}}\log(\frac{M}{\epsilon})}\bigg{)}^{4}\cdot\epsilon\overset{(b)}{\leq}\epsilon,$ $$

where (a) follows from the inequality $\log(\log(\frac{M}{\epsilon}))\leq\frac{1}{4}\log(\frac{M}{\epsilon})$ for sufficiently small $\epsilon$; (b) holds because $\log(N)+2\log(\frac{M}{\epsilon})\leq N^{\frac{1}{4}}\log(\frac{M}{\epsilon})$ for $N=12^{4}$ and $\epsilon$ is sufficiently small.
Thus, to achieve $\epsilon$-accurate stationary point, we require $T=\frac{MN}{\epsilon}\log^{4}(\frac{M}{\epsilon})=\mathcal{O}\big{(}\frac{1}{\epsilon}\log^{4}(\frac{1}{\epsilon})\big{)}$, and the gradient complexity is given by ${\rm Gc}(\epsilon)=\Omega(T)=\mathcal{O}\big{(}\frac{1}{\epsilon}\log^{4}(\frac{1}{\epsilon})\big{)}$.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: This paper proposes two versions of tuning-free bilevel algorithms. It appears that the single-loop algorithm offers better gradient complexity, while the double-loop algorithm demonstrates superior empirical performance. Could the authors comment on the reasons for this discrepancy—such as whether it stems from a less tight convergence rate for the double-loop method or something else? Additionally, guidance on when to choose the double-loop versus single-loop version would be helpful for practioner.
soundness: 3
strengths: Parameter tuning is challenging in bilevel optimization, as bilevel problems typically involve more hyperparameters than single-level learning. This paper presents two versions of tuning-free methods with both theoretical guarantees and experimental validation, making it a valuable contribution to the bilevel optimization community. 

Theoretical guarantees for the proposed methods are solid, and the numerical performance demonstrates a clear advantage, showcasing the effectiveness of these approaches.
summary: This paper has proposed two tuning-free algorithms for stochastic bilevel optimization, D-TFBO and S-TFBO, which eliminates the need for stepsize tuning that depends on problem-specific parameters. D-TFBO follows a double-loop structure, while S-TFBO utilizes a fully single-loop approach with a joint design of adaptive stepsizes. Convergence rates for both methods are established, and numerical results on data hyper-cleaning, regularization selection, and coreset selection validate the effectiveness of the proposed algorithms.
weaknesses: This paper addresses only deterministic bilevel optimization, leaving it unclear whether the proposed technique is robust in stochastic settings.

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. How would the methods extend to more general bilevel problems?
2. Could you update citations from arXiv preprints to published versions where available?
3. How does the performance of these tuning-free methods compare directly to well-tuned bilevel optimization algorithms in terms of convergence rate?
soundness: 3
strengths: The paper provides a detailed convergence analysis for the algorithms.
summary: The paper introduces tuning-free bilevel optimization algorithms to eliminate the need for prior knowledge of problem-specific parameters. Theoretical convergence is derived for methods and experiments are provided.
weaknesses: While I understand the importance of addressing tuning-free bilevel optimization, the main technical novelty of this work is unclear.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. I do not understand the proposed observations in Remarks 1 and 2. The authors could discuss these observations in greater depth, such as by providing more detailed explanations in the main theorems and experiments.

2. I would like to know whether the proposed algorithm can work without the prior knowledge of the total number of iterations $T$ (cf. Weakness 1).

3. I would like to observe the progression of the loss function over time in the experimental results.

4. For other questions, please see the weaknesses above.
soundness: 3
strengths: 1. The paper is well-written and is easy to read.

2. This paper introduce two tuning-free algorithms, D-TFBO and S-TFBO to solve bilevel problems, which eliminate the need for stepsize tuning while achieving theoretical guarantees.

3. The complexity bounds of the proposed method (nearly) match their well-tuned counterparts using the information of problem parameters.
summary: In this paper, the authors introduce two tuning-free algorithms, D-TFBO and S-TFBO to solve bilevel problems. D-TFBO employs a double-loop structure with stepsizes adaptively adjusted by the "inverse of cumulative gradient norms'' strategy. S-TFBO features a simpler fully singleloop structure that updates three variables simultaneously with a theory-motivated joint design of adaptive stepsizes for all variables. The authors demonstrate that D-TFBO and S-TFBO respectively require $\mathcal{O}(1/\epsilon)$ and $\mathcal{O}(1/\epsilon \log^4 (1/\epsilon))$ iterations to reach an $\epsilon$-accurate stationary point. The methods are the first to eliminate the need for stepsize tuning while achieving theoretical guarantees.
weaknesses: 1. My primary concern is the update mode of the proposed algorithms. Many tuning-free algorithms do not require prior knowledge of the total number of iterations $T$ (e.g., [1]). However, this is not a significant drawback for me, as addressing bilevel problems with tuning-free algorithms in this context seems to be new.

2. The literature review should comprehensively compare the complexity results and the corresponding problem settings with other methods in a table.

[1] Marumo, Naoki, and Akiko Takeda. "Parameter-free accelerated gradient descent for nonconvex minimization." SIAM Journal on Optimization 34.2 (2024): 2093-2120.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Non.
soundness: 3
strengths: 1.This paper combines the parameter free methodology with BLO, which is a good direction to explore.

2.The convergence rates achieved by proposed methods are nearly optimal.
summary: This paper studies parameter-free algorithms for solving BLO, where the lower level problem is strongly convex and the upper level problem can be nonconvex. The authors propose two tuning-free algorithms that achieve the nearly same rate of the state of the art without knowing the parameter. The stationarity measure is the standard hyper gradient norm. Numerical experiments are conducted to show the effectiveness of the proposed methods.
weaknesses: 1. Under the strong convexity of the lower level problem, the BLO is similar to single level problems. This is due to the fact that there is a unique solution $y^*(x)$ for the lower-level problem given an arbitrary upper-level variable $x$, and then the BLO is reduced to the single level problem $\min_{x}\phi(x)=f(x,y^*(x))$. Even further, the gradient of $\phi$ can be computed, as presented in Sec. 3.1 of this paper. Given this, the authors should point out the novelty of the techniques used in this paper compared with single-level parameter-free methods.

2. Second-order information is needed for each iteration, which is computationally expensive. The authors may discuss how to approximate the used hessian matrix or a furture direction to develop methods that are both tuning-free and hessian-free.

Meta-review: This paper studies a practically important problem on bilevel optimization with adaptive tuning of stepsizes, which will reduce significant efforts in tuning stepsizes when some of the problem parameters are unknown. The paper proposes two novel tuning-free algorithms, where one employs a double-loop structure with stepsizes and the other features a fully single-loop structure. All the reviewers are active researchers in the field, and have achieved consensus on the acceptance of this paper. I also read the paper and believe that the paper will add value to the bilevel optimization community.

Decision: Accept (Poster)