# Efficient Gradient Approximation Method for Constrained Bilevel Optimization

Siyuan Xu1, Minghui Zhu1 Corresponding author.

###### Abstract

Bilevel optimization has been developed for many machine learning tasks with
large-scale and high-dimensional data. This paper considers a constrained
bilevel optimization problem, where the lower-level optimization problem is
convex with equality and inequality constraints and the upper-level
optimization problem is non-convex. The overall objective function is non-
convex and non-differentiable. To solve the problem, we develop a gradient-
based approach, called gradient approximation method, which determines the
descent direction by computing several representative gradients of the
objective function inside a neighborhood of the current estimate. We show that
the algorithm asymptotically converges to the set of Clarke stationary points,
and demonstrate the efficacy of the algorithm by the experiments on
hyperparameter optimization and meta-learning.

##  1 Introduction

A general constrained bilevel optimization problem is formulated as follows:

$\displaystyle\min_{x\in\mathbb{R}^{d_{x}}}\ \Phi(x)=f\left(x,y^{*}(x)\right)$
$\displaystyle\text{ s.t. }\ r\left(x,y^{*}(x)\right)\leq 0;\
s\left(x,y^{*}(x)\right)=0;$ (1) $\displaystyle
y^{*}(x)=\underset{y\in\mathbb{R}^{d_{y}}}{\arg\min}\\{g(x,y):p\left(x,y\right)\leq
0;q\left(x,y\right)=0\\}.$

The bilevel optimization minimizes the overall objective function $\Phi(x)$
with respect to (w.r.t.) $x$, where $y^{*}(x)$ is the optimal solution of the
lower-level optimization problem and parametric in the upper-level decision
variable $x$. In this paper, we assume that $y^{*}(x)$ is unique for any
$x\in\mathbb{R}^{d_{x}}$.

Existing methods to solve problem (1) can be categorized into two classes:
single-level reduction methods (Bard and Falk 1982; Bard and Moore 1990; Shi,
Lu, and Zhang 2005) and descent methods (Savard and Gauvin 1994; Dempe 1998).
Single-level reduction methods use the KKT conditions to replace the lower-
level optimization problem when it is convex. Then, they reformulate the
bilevel optimization problem (1) as a single-level constrained optimization
problem. Descent methods aim to find descent directions in which the new point
is feasible and meanwhile reduces the objective function. Paper (Savard and
Gauvin 1994) computes a descent direction of the objective function by solving
a quadratic program. Paper (Dempe 1998) applies the gradient of the objective
function computed in (Kolstad and Lasdon 1990; Fiacco and McCormick 1970) to
compute a generalized Clarke Jacobian, and uses a bundle method (Schramm and
Zowe 1992) for the optimization. When applied to machine learning, bilevel
optimization faces additional challenges as the dimensions of decision
variables in the upper-level and lower-level problems are high (Liu et al.
2021a).

Gradient-based methods have been shown to be effective in handling large-scale
and high-dimensional data in a variety of machine learning tasks (Bottou and
Bousquet 2008). They have been extended to solve the bilevel optimization
problem where there is no constraint in the lower-level optimization. The
methods can be categorized into the approximate implicit differentiation (AID)
based approaches (Pedregosa 2016; Gould et al. 2016; Ghadimi and Wang 2018;
Grazzi et al. 2020) and the iterative differentiation (ITD) approaches (Grazzi
et al. 2020; Franceschi et al. 2017, 2018; Shaban et al. 2019; Ji, Yang, and
Liang 2021). The AID based approaches evaluate the gradients of $y^{*}(x)$ and
$\Phi(x)$ based on implicit differentiation (Bengio 2000). The ITD based
approaches treat the iterative optimization steps in the lower-level
optimization as a dynamical system, impose $y^{*}(x)$ as its stationary point,
and compute $\nabla y^{*}(x)$ at each iterative step. The gradient-based
algorithms have been applied to solve several machine learning tasks,
including meta-learning (Franceschi et al. 2018; Rajeswaran et al. 2019; Ji et
al. 2020), hyperparameter optimization (Pedregosa 2016; Franceschi et al.
2017, 2018), reinforcement learning (Hong et al. 2020; Konda and Tsitsiklis
2000), and network architecture search (Liu, Simonyan, and Yang 2018). The
above methods are limited to unconstrained bilevel optimization and require
the objective function to be differentiable. They cannot be directly applied
when constraints are present in the lower-level optimization, as the objective
function is non-differentiable.

Contributions.  In this paper, we consider a special case of problem (1) where
the upper-level constraints $r$ and $s$ are not included. In general, the
objective function $\Phi$ is nonconvex and non-differentiable, even if the
upper-level and lower-level problems are convex and functions $f$, $g$, $p$,
$q$ are differentiable (Hansen, Jaumard, and Savard 1992; Liu et al. 2021a).
Most methods for this bilevel optimization problem are highly complicated and
computationally expensive, especially when the dimension of the problem is
large (Liu et al. 2021a; Dempe and Franke 2016). Addressing the challenge, we
determine the descent direction by computing several gradients which can
represent the gradients of the objective function of all points in a ball, and
develop a computationally efficient algorithm with convergence guarantee for
the constrained bilevel optimization problem. The overall contributions are
summarized as follows. (i) Firstly, we derive the conditions under which the
lower-level optimal solution $y^{*}(x)$ is continuously differentiable or
directional differentiable. In addition, we provide analytical expressions for
the gradient of $y^{*}(x)$ when it is continuously differentiable and the
directional derivative of $y^{*}(x)$ when it is directional differentiable.
(ii) Secondly, we propose the gradient approximation method, which applies the
Clarke subdifferential approximation of the non-convex and non-differentiable
objective function $\Phi$ to the line search method. In particular, a set of
derivatives is used to approximate the gradients or directional derivatives on
all points in a neighborhood of the current estimate. Then, the Clarke
subdifferential is approximated by the derivatives, and the approximate Clarke
subdifferential is employed as the descent direction for line search. (iii) It
is shown that, the Clarke subdifferential approximation errors are small, the
line search is always feasible, and the algorithm asymptotically converges to
the set of Clarke stationary points. (iv) We empirically verify the efficacy
of the proposed algorithm by conducting experiments on hyperparameter
optimization and meta-learning.

Related Works.  Differentiation of the optimal solution of a constrained
optimization problem has been studied for a long time. Sensitivity analysis of
constrained optimization (Fiacco 1983; Fiacco and Ishizuka 1990; Fiacco and
McCormick 1970) shows the optimal solution $y^{*}(x)$ of a convex optimization
problem is directional differentiable but may not differentiable at all
points. It implies that the objective function $\Phi(x)$ in problem (1) may
not be differentiable. Based on the implicit differentiation of the KKT
conditions, the papers also compute $\nabla y^{*}(x)$ when $y^{*}$ is
differentiable at $x$. Optnet (Amos, Xu, and Kolter 2017; Amos and Kolter
2017; Agrawal et al. 2019) applies the gradient computation to the constrained
bilevel optimization, where a deep neural network is included in the upper-
level optimization problem. In particular, the optimal solution $y^{*}(x)$
serves as a layer in the deep neural network and $\nabla y^{*}(x)$ is used as
the backpropagation gradients to optimize the neural network parameters.
However, all the above methods do not explicitly consider the non-
differentiability of $y^{*}(x)$ and $\Phi(x)$, and cannot guarantee
convergence. Recently, papers (Liu et al. 2021b; Sow et al. 2022) consider
that the lower-level optimization problem has simple constraints, such that
projection onto the constraint set can be easily computed, and require that
the constraint set is bounded. In this paper, we consider inequality and
equality constraints, which are more general than those in (Liu et al. 2021b;
Sow et al. 2022).

Notations.  Denote $a>b$ for vectors $a,b\in\mathbb{R}^{n}$, when
$a_{i}>b_{i}$ for all $1\leq i\leq n$. Notations $a\geq b$, $a=b$, $a\leq b$,
and $a<b$ are defined in an analogous way. Denote the $l_{2}$ norm of vectors
by $\|\cdot\|$. The directional derivative of a function $f$ at $x$ on the
direction $d$ with $\|d\|=1$ is defined as
$\nabla_{d}f({x})\triangleq\lim_{h\rightarrow 0^{+}}\frac{f(x+hd)-f(x)}{h}$. A
ball centered at $x$ with radius $\epsilon$ is denoted as
$\mathcal{B}(x,\epsilon)$. The complementary set of a set $S$ is denoted as
$S^{C}$. The distance between the point $x$ and the set $S$ is defined as
$d(x,S)\triangleq\inf\\{\|x-a\|\mid a\in S\\}$. The convex hull of $S$ is
denoted by $\operatorname{conv}S$. For set $S$ and function $f$, we define the
image set $f(S)\triangleq\\{f(x)\mid x\in S\\}$. For a finite positive integer
set $I$ and a vector function $p$, we denote the subvector function
$p_{I}\triangleq[p_{k_{1}},\cdots,p_{k_{j}},\cdots]^{\top}$ where $k_{j}\in
I$.

##  2 Problem Statement

Consider the constrained bilevel optimization problem:

$\displaystyle\min_{x\in\mathbb{R}^{d_{x}}}\ \Phi(x)=f\left(x,y^{*}(x)\right)$
(2) $\displaystyle\text{s.t.
}y^{*}(x)=\underset{y\in\mathbb{R}^{d_{y}}}{\arg\min}\\{g(x,y):p\left(x,y\right)\leq
0;q\left(x,y\right)=0\\},$

where $f,g:\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{y}}\rightarrow\mathbb{R}$;
$p:\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{y}}\rightarrow\mathbb{R}^{m}$;
$q:\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{y}}\rightarrow\mathbb{R}^{n}$. Given
$x\in\mathbb{R}^{d_{x}}$, we denote the lower-level optimization problem in
(2) as $P(x)$. The feasible set of $P(x)$ is defined as
$K\left(x\right)\triangleq\\{y\in\mathbb{R}^{d_{y}}:p\left(x,y\right)\leq
0,q\left(x,y\right)=0\\}$. Suppose the following assumptions hold.

######  Assumption 1.

The functions $f$, $g$, $p$ and $q$ are twice continuously differentiable.

######  Assumption 2.

For all ${x}\in\mathbb{R}^{d_{x}}$, the function $g(x,y)$ is $\mu$-strongly-
convex w.r.t. $y$; $p_{j}(x,y)$ is convex w.r.t. $y$ for each $j$;
$q_{i}(x,y)$ is affine w.r.t. $y$ for each $i$.

Note that the upper-level objective function $f(x,y)$ and the overall
objective function $\Phi(x)$ are non-convex. The lower-level problem $P(x)$ is
convex and its Lagrangian is $\mathcal{L}(y,\lambda,\nu,x)\triangleq
g(x,y)+\lambda^{\top}p(x,y)+\nu^{\top}q(x,y)$, where $(\lambda,\nu)$ are
Lagrange multipliers and $\lambda\geq 0$.

######  Definition 1.

Suppose that the KKT conditions hold at ${y}$ for $P(x)$ with the Lagrangian
multipliers ${\lambda}$ and ${\nu}$. The set of active inequality constraints
at ${y}$ for $P(x)$ is defined as: $J(x,{y})\triangleq\\{j:1\leq j\leq m,\
p_{j}(x,{y})=0\\}$. An inequality constraint is called inactive if it is not
included in $J(x,{y})$ and the set of inactive constraints is denoted as
$J(x,y)^{C}$. The set of strictly active inequality constraints at ${y}$ is
defined as: $J^{+}(x,{y},{\lambda})\triangleq\\{j:j\in J\left(x,{y}\right),\
{\lambda}_{j}>0\\}$. The set of non-strictly active inequality constraints at
${y}$ is defined as: $J^{0}(x,{y},{\lambda})\triangleq J(x,{y})\setminus
J^{+}(x,{y},{\lambda})$. Notice that ${\lambda}_{j}\geq 0$ for $j\in J(x,{y})$
and ${\lambda}_{j}=0$ for $j\in J^{0}(x,{y},{\lambda})$.

######  Definition 2.

The Linear Independence Constraint Qualification (LICQ) holds at ${y}$ for
$P(x)$ if the vectors $\left\\{\nabla_{y}p_{j}\left(x,{y}\right),j\in
J\left(x,{y}\right);\nabla_{y}q_{i}\left(x,{y}\right),1\leq i\leq n\right\\}$
are linearly independent.

######  Assumption 3.

Suppose that for all ${x}\in\mathbb{R}^{d_{x}}$, the solution $y^{*}(x)$
exists for $P\left(x\right)$, and the LICQ holds at $y^{*}(x)$ for $P(x)$.

##  3 Differentiability and Gradient of $y^{*}(x)$

In this section, we provide sufficient conditions under which the lower-level
optimal solution $y^{*}(x)$ is continuously differentiable or directional
differentiable. We compute the gradient of $y^{*}(x)$ when it is continuously
differentiable and the directional derivative of $y^{*}(x)$ when it is
directional differentiable. Moreover, we give a necessary condition that
$y^{*}(x)$ is not differentiable and illustrate it by a numerical example.

In problem (2), if the upper-level objective function $f$ and the solution of
lower-level problem $y^{*}$ are continuously differentiable, so is $\Phi$, and
by the gradient computation of composite functions, we have

$\nabla\Phi(x)=\nabla_{x}f(x,y^{*}(x))+\nabla
y^{*}(x)^{\top}\nabla_{y}f(x,y^{*}(x)).$ (3)

It is shown in (Domke 2012) that, when $p$ and $q$ are absent, $y^{*}$ and
$\Phi$ are differentiable under certain assumptions. The differentiability of
$y^{*}$ and $\Phi$ is used by the AID based approaches in (Pedregosa 2016;
Gould et al. 2016; Ghadimi and Wang 2018; Grazzi et al. 2020; Domke 2012) to
approximate $\nabla y^{*}$ and minimize $\Phi$ by gradient descent. However,
it is not the case as the lower-level problem (2) is constrained.

Theorem 1 states the conditions under which $y^{*}(x)$ is directional
differentiable.

######  Theorem 1.

Suppose Assumptions 1, 2, 3 hold. The following properties hold for any $x$.

  * (i)

The global minimum $y^{*}(x)$ of $P\left(x\right)$ exists and is unique. The
KKT conditions hold at $y^{*}(x)$ with unique Lagrangian multipliers
$\lambda(x)$ and $\nu(x)$.

  * (ii)

The vector function
$z(x)\triangleq[y^{*}(x)^{\top},\lambda(x)^{\top},\nu(x)^{\top}]^{\top}$ is
continuous and locally Lipschitz. The directional derivative of $z(x)$ on any
direction exists.

As shown in part (i) of Theorem 1, $y^{*}(x)$, ${\lambda}(x)$ and ${\nu}(x)$
are uniquely determined by $x$. So we simplify the notations of Definition 1
in the rest of this paper: $J(x,y^{*}(x))$ is denoted as $J(x)$,
$J^{+}(x,y^{*}(x),{\lambda}(x))$ is denoted as $J^{+}(x)$, and
$J^{0}(x,y^{*}(x),\lambda(x))$ is denoted as $J^{0}(x)$. In part (ii), the
computation of the directional derivative of $z(x)$ is given in Theorem 6 in
Appendix C.

######  Definition 3.

Suppose that the KKT conditions hold at ${y}$ for $P(x)$ with the Lagrangian
multipliers ${\lambda}$ and ${\nu}$. The Strict Complementarity Slackness
Condition (SCSC) holds at ${y}$ w.r.t. ${\lambda}$ for $P(x)$, if
${\lambda}_{j}>0$ for all ${j}\in J(x,{y})$.

######  Remark 1.

The KKT conditions include the Complementarity Slackness Condition (CSC). The
SCSC is stronger than the CSC, which only requires that ${\lambda}_{j}\geq 0$
for all ${j}\in J(x,{y})$.

Theorem 2 states the conditions under which $y^{*}(x)$ is continuously
differentiable and derives $\nabla y^{*}(x)$.

######  Theorem 2.

Suppose Assumptions 1, 2, 3 hold. If the SCSC holds at $y^{*}(x)$ w.r.t.
$\lambda(x)$, then $z(x)$ is continuously differentiable at $x$ and the
gradient is computed as

$\left[\nabla_{x}y^{*}(x)^{\top},\nabla_{x}\lambda_{J(x)}^{\top}(x),\nabla_{x}\nu(x)^{\top}\right]^{\top}=-M_{+}^{-1}(x)N_{+}(x)$
(4)

and $\nabla_{x}\lambda_{{J(x)}^{C}}(x)=0$, where $M_{+}(x)\triangleq$

$\left[\begin{array}[]{ccccccc}\nabla_{y}^{2}\mathcal{L}&\nabla_{y}p_{J^{+}(x)}^{\top}&\nabla_{y}q^{\top}\\\
\nabla_{y}p_{J^{+}(x)}&0&0\\\
\nabla_{y}q&0&0\end{array}\right](x,y^{*}(x),\lambda(x),\nu(x))$

is nonsingular and $N_{+}(x)\triangleq$

$[\nabla_{xy}^{2}\mathcal{L}^{\top},\nabla_{x}p_{J^{+}(x)}^{\top},\nabla_{x}q^{\top}]^{\top}(x,y^{*}(x),\lambda(x),\nu(x)).$

Theorem 2 shows that, if $z(x)$ is not continuously differentiable, then the
SCSC does not hold at $y^{*}(x)$ w.r.t. $\lambda(x)$. Definition 3 implies
that the SCSC holds at ${y}$ w.r.t. ${\lambda}$ for $P(x)$ if and only if
$J^{0}(x)=\emptyset$. It concludes that if $y^{*}(x)$ is not continuously
differentiable at $x$, $J^{0}(x)\neq\emptyset$, i.e., the non-
differentiability of $y^{*}(x)$ occurs at points with non-strictly active
constraints. Example 1 illustrates such claim.

######  Example 1.

Consider a bilevel optimization problem $\Phi(x)=y^{*}(x)$ and the lower-level
problem $P(x)$: $y^{*}(x)={\arg\min}_{y}\\{(y-x^{2})^{2}:p_{1}(x,y)=-x-y\leq
0\\}$, where $x$, $y\in\mathbb{R}$. The analytical solution of
$z(x)=[y^{*}(x),\lambda(x)]$ is given by: $y^{*}(x)=x^{2}$, $\lambda(x)=0$
when $x\in(-\infty,-1]\cup[0,+\infty)$; $y^{*}(x)=-x$, $\lambda(x)=-2x(1+x)$
when $x\in[-1,0]$. Correspondingly, when $x\in(-1,0)$, $J(x)=\\{1\\}$,
$J^{+}(x)=\\{1\\}$, $J^{0}(x)=\emptyset$; when
$x\in(-\infty,-1)\cup(0,+\infty)$, $J(x)=\emptyset$, $J^{+}(x)=\emptyset$,
$J^{0}(x)=\emptyset$; when $x\in\\{-1,0\\}$, $J(x)=\\{1\\}$,
$J^{+}(x)=\emptyset$, $J^{0}(x)=\\{1\\}$. As shown in Fig. 1, $y^{*}(x)$ is
continuously differentiable everywhere except when $J^{0}(x)\neq\emptyset$.

Figure 1: Occurrence of non-differentiability.

The computation of the gradient of $z(x)$ in (4) is derived from the implicit
differentiation of the KKT conditions of problem $P(x)$, which is also used in
(Fiacco and Ishizuka 1990; Amos and Kolter 2017; Agrawal et al. 2019).
Compared with these papers, Theorem 2 directly determines
$\nabla_{x}\lambda_{{J(x)}^{C}}(x)=0$ and excludes $\lambda_{{J(x)}^{C}}(x)$
from the computation of the inverse matrix in (4), when $z(x)$ is continuously
differentiable. Theorem 6 in Appendix C derives the directional derivative of
$z(x)$ when it is not differentiable.

Consider a special case where the lower-level optimization problem $P(x)$ is
unconstrained. Since the SCSC is not needed anymore, the assumptions in
Theorem 2 reduce to that $g$ is twice continuously differentiable and $g(x,y)$
is $\mu$-strongly-convex w.r.t. $y$ for ${x}\in\mathbb{R}^{d_{x}}$. By Theorem
2, the optimal solution $y^{*}(x)$ is continuously differentiable, the matrix
$\nabla_{y}^{2}g({x},{y})$ is non-singular, and the gradient is computed as
$\nabla y^{*}(x)=-[\nabla_{y}^{2}g({x},{y})]^{-1}\nabla_{xy}^{2}g({x},{y})$.
These results are well-known and widely used in unconstrained bilevel
optimization analysis and applications (Pedregosa 2016; Franceschi et al.
2017, 2018; Ji, Yang, and Liang 2021).

##  4 The Gradient Approximation Method

In this section, we develop the gradient approximation method to efficiently
solve problem (2), whose objective function is non-differentiable and non-
convex. First, we define the Clarke subdifferential (Section 4.1) and
efficiently approximate the Clarke subdifferential of the objective function
$\Phi(x)$ (Section 4.2). Next, we propose the gradient approximation
algorithm, provide its convergence guarantee (Section 4.3), and present its
implementation details (Section 4.4).

###  4.1 Clarke Subdifferential of $\Phi$

As shown in Section 2 and also shown in (Dempe and Franke 2016; Liu et al.
2021a), the objective function $\Phi\left(x\right)$ of problem (2) is usually
non-differentiable and non-convex. To deal with the non-smoothness and non-
convexity, we introduce Clarke subdifferential and Clarke stationary point.

######  Definition 4 (Clarke subdifferential and Clarke stationary point
(Clarke 1975)).

For a locally Lipschitz function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$, the
Clarke subdifferential of $f$ at $x$ is defined by the convex hull of the
limits of gradients of $f$ on sequences converging to $x$, i.e.,
$\bar{\partial}f(x)\triangleq\operatorname{conv}\left\\{\lim_{j\rightarrow\infty}\nabla
f\left(y^{j}\right):\left\\{y^{j}\right\\}\rightarrow x\right.$ where $f$ is
differentiable at $y^{j}$ for all $\left.j\in\mathbb{N}\right\\}$. The Clarke
$\epsilon\text{-subdifferential}$ of $f$ at $x$ is defined by
$\bar{\partial}_{\epsilon}f(x)\triangleq\operatorname{conv}\\{\bar{\partial}f(x^{\prime}):x^{\prime}\in\mathcal{B}(x,\epsilon)\\}$.
A point $x$ is Clarke stationary for $f$ if $0\in\bar{\partial}f(x)$.

If $y^{*}$ is differentiable at $x$, we have
$\bar{\partial}y^{*}(x)=\left\\{\nabla y^{*}(x)\right\\}$ and
$\bar{\partial}\Phi(x)=\\{\nabla_{x}f(x,y^{*}(x))+\nabla
y^{*}(x)^{\top}\nabla_{y}f(x,y^{*}(x))\\}$; otherwise,
$\bar{\partial}\Phi(x)=\\{\nabla_{x}f(x,y^{*}(x))+w^{\top}\nabla_{y}f(x,y^{*}(x)):w\in\bar{\partial}y^{*}(x)\\}$.
Take the functions shown in Example 1 and Fig. 1 as an example,
$\bar{\partial}_{\epsilon}\Phi(-1)=\bar{\partial}_{\epsilon}y^{*}(-1)=\operatorname{conv}\\{[-2-2\epsilon,-2]\cup\\{-1\\}\\}=[-2-2\epsilon,-1]$,
and
$\bar{\partial}_{\epsilon}\Phi(0)=\bar{\partial}_{\epsilon}y^{*}(0)=\operatorname{conv}\\{[0,2\epsilon]\cup\\{-1\\}\\}=[-1,2\epsilon]$.

###  4.2 Clarke Subdifferential Approximation

Gradient-based methods have been applied to convex and non-convex optimization
problems (Hardt, Recht, and Singer 2016; Nemirovski et al. 2009). The
convergence requires that the objective function is differentiable. If there
exist points where the objective function is not differentiable, the
probability for the algorithms to visit these points is non-zero and the
gradients at these points are not defined (Bagirov et al. 2020). Moreover,
oscillation may occur even if the objective function is differentiable at all
visited points (Bagirov, Karmitsa, and Mäkelä 2014).

To handle the non-differentiability, the gradient sampling method (Burke,
Lewis, and Overton 2005; Kiwiel 2007; Bagirov et al. 2020) uses gradients in a
neighborhood of the current estimate to approximate the Clarke subdifferential
and determine the descent direction. Specifically, the method samples a set of
points inside the neighborhood $\mathcal{B}(x^{0},\epsilon)$, select the
points where the objective function is differentiable, and then compute the
convex hull of the gradients on the sampled points.

However, in problem (2), the point sampling is highly computationally
expensive. For each sampled point $x^{j}$, to check the differentiability of
$\Phi$, we need to solve the lower-level optimization $P(x^{j})$ to obtain
$y^{*}(x^{j})$, $\lambda(x^{j})$ and $\nu(x^{j})$, and check the SCSC.
Moreover, after the points are sampled, the gradient on each point is computed
by (4). As the dimension $d_{x}$ increases, the sampling number increases to
ensure the accuracy of the approximation. More specifically, as shown in
(Kiwiel 2007), the algorithm is convergent if the sampling number is large
than $d_{x}+1$. The above procedure is executed in each optimization
iteration.

Addressing the computational challenge, we approximate the Clarke
$\epsilon\text{-subdifferential}$ by a small number of gradients, which can
represent the gradients on all points in the neighborhood. The following
propositions distinguish two cases: $\Phi$ is continuously differentiable on
$\mathcal{B}(x^{0},\epsilon)$ (Proposition 1) and it is not (Proposition 2).

######  Proposition 1.

Suppose Assumptions 1, 2, 3 hold. Consider $x^{0}\in R^{d_{x}}$. There is
sufficiently small $\epsilon>0$ such that, if the SCSC holds at $y^{*}(x)$
w.r.t. $\lambda(x)$ for any $x\in\mathcal{B}(x^{0},\epsilon)$, then
$\nabla\Phi(x^{0})\in\bar{\partial}_{\epsilon}\Phi(x^{0})$ and

$|\|\nabla\Phi(x^{0})\|-d(0,\bar{\partial}_{\epsilon}\Phi(x^{0}))|<o(\epsilon).$

Proposition 1 shows that the gradient $\nabla\Phi$ at a single point $x^{0}$
can be used to approximate the Clarke $\epsilon\text{-subdifferential}$
$\bar{\partial}_{\epsilon}\Phi(x^{0})$ and the approximation error is in the
order of $\epsilon$. Recall that the gradient $\nabla\Phi(x^{0})$ can be
computed by (3) and (4). Fig. 4 illustrates the approximation on the problem
in Example 1. The SCSC holds at $y^{*}(x)$ and $\Phi(x)$ is continuously
differentiable on $\mathcal{B}(x^{0},\epsilon)$, then
$\bar{\partial}_{\epsilon}\Phi(x^{0})=[2x^{0}-2\epsilon,2x^{0}+2\epsilon]$ can
be approximated by $\nabla\Phi(x^{0})=2x^{0}$, and the approximation error is
$2\epsilon$. The approximations of $\bar{\partial}_{\epsilon}\Phi(x^{1})$ and
$\bar{\partial}_{\epsilon}\Phi(x^{2})$ can be done in an analogous way.

Figure 2: The SCSC holds on $\mathcal{B}(x^{0},\epsilon)$

Figure 3: Subsets inside $\mathcal{B}(x^{0},\epsilon)$

Figure 4: Approximate $\bar{\partial}_{\epsilon}y^{*}(x^{0})$

Consider $\Phi(x)$ is not continuously differentiable at some points in
$\mathcal{B}(x^{0},\epsilon)$. Define the set $I^{\epsilon}(x^{0})$ which
contains all $j$ such that there exist $x^{\prime}$,
$x^{\prime\prime}\in\mathcal{B}(x^{0},\epsilon)$ with $j\in
J^{+}(x^{\prime})^{C}\text{ and }j\in J^{+}(x^{\prime\prime})$. Define the set
$I_{+}^{\epsilon}(x^{0})$ which contains all $j$ such that $j\in J^{+}(x)$ for
any $x\in\mathcal{B}(x^{0},\epsilon)$. If $I^{\epsilon}(x^{0})$ is not empty,
there exists a point $x\in\mathcal{B}(x^{0},\epsilon)$ such that the SCSC does
not hold at $y^{*}(x)$. The power set of $I^{\epsilon}(x^{0})$ partitions
$\mathcal{B}(x^{0},\epsilon)$ into a number of subsets, where $\Phi(x)$ and
$y^{*}(x)$ are continuously differentiable in each subset. An illustration on
the problem in Example 1 is shown in Fig. 4. The point $x^{\prime}=-1$ belongs
to $(x^{0}-\epsilon,x^{0}+\epsilon)$ and the SCSC does not hold at
$y^{*}(x^{\prime})$. Notice that $I^{\epsilon}_{+}(x^{0})=\emptyset$ and
$I^{\epsilon}(x^{0})=\\{1\\}$. Then, $I^{\epsilon}(x^{0})=\\{1\\}$ has the
power set $\\{S_{(1)},S_{(2)}\\}$ with $S_{(1)}=\emptyset$ and
$S_{(2)}=\\{1\\}$. Then, $\mathcal{B}(x^{0},\epsilon)$ is partitioned to two
subsets: the subset where the constraint $p_{1}$ is inactive (blue side in the
ball) which corresponds to $S_{(1)}$, and the subset where the constraint
$p_{1}$ is strictly active (red side in the ball) which corresponds to
$S_{(2)}$. Their boundary is the point $x^{\prime}$ where the constraint
$p_{1}$ is non-strictly active. It can be seen that $y^{*}(x)$ is continuously
differentiable on each subset and the gradient variations are small inside the
subset when $\epsilon$ is small. In contrast, the gradient variations between
two subsets are large. Inspired by Proposition 1, we compute a representative
gradient to approximate $\nabla y^{*}(x)$ inside each subset of
$\mathcal{B}(x^{0},\epsilon)$.

Now we proceed to generalize the above idea. Recall that $\nabla\Phi(x)$ is
computed by (3) and $f$ is twice continuously differentiable. Define

$\displaystyle
G(x^{0},\epsilon)\triangleq\\{\nabla_{x}f\left(x^{0},y^{*}\left(x^{0}\right)\right)+{w}^{S}(x^{0})^{\top}$
(5)
$\displaystyle\nabla_{y}f\left(x^{0},y^{*}\left(x^{0}\right)\right):S\subseteq
I^{\epsilon}(x^{0})\\},$

where ${w}^{S}(x^{0})$ is obtained by extracting the first $d_{x}$ rows from
matrix
$-M^{S}_{\epsilon}(x^{0},y^{*}(x^{0}))^{-1}N^{S}_{\epsilon}(x^{0},y^{*}(x^{0}))$,
with

$M^{S}_{\epsilon}\triangleq\left[\begin{array}[]{ccccccc}\nabla_{y}^{2}\mathcal{L}&\nabla_{y}p_{I^{\epsilon}_{+}(x^{0})}^{\top}&\nabla_{y}q^{\top}&\nabla_{y}p^{\top}_{S}\\\
\nabla_{y}p_{I^{\epsilon}_{+}(x^{0})}&0&0&0\\\ \nabla_{y}q&0&0&0\\\
\nabla_{y}p_{S}&0&0&0\end{array}\right],$

and
$N^{S}_{\epsilon}\triangleq\left[\nabla_{xy}^{2}\mathcal{L}^{\top},\nabla_{x}p_{I^{\epsilon}_{+}(x^{0})}^{\top},\nabla_{x}q^{\top},\nabla_{x}p_{S}^{\top}\right]^{\top}$.
Here, $S$ is a subset of $I^{\epsilon}(x^{0})$, and $w^{S}(x^{0})$ is the
representative gradient to approximate $\nabla y^{*}(x)$ inside the subset of
$\mathcal{B}(x^{0},\epsilon)$ which corresponds $S$. Proposition 2 shows that
the Clarke $\epsilon\text{-subdifferential}$
$\bar{\partial}_{\epsilon}y^{*}(x^{0})$ can be approximated by representative
gradient set $G(x^{0},\epsilon)$, and the approximation error is in the order
of $\epsilon$.

######  Proposition 2.

Suppose Assumptions 1, 2, 3 hold. Consider $x^{0}\in\mathbb{R}^{d_{x}}$, and
assume there exists a sufficiently small $\epsilon>0$ such that, there exists
$x\in\mathcal{B}(x^{0},\epsilon)$ such that $y^{*}(x)$ is not continuously
differentiable at $x$. Then, the following inequality holds for any
$z\in\mathbb{R}^{d_{x}}$,

$|d(z,\operatorname{conv}G(x^{0},\epsilon))-d(z,\bar{\partial}_{\epsilon}\Phi(x^{0}))|<o(\epsilon).$

The computation of the representative gradient $w^{S}(x^{0})$ of Example 1 is
demonstrated in Fig. 4. Since $x^{0}$ is near the boundary of two subsets,
Proposition 2 employs $w^{S_{(1)}}(x^{0})=\nabla y^{*}(x^{0})$ to approximate
the gradients of the subset with the inactive constraint (blue side), and
$w^{S_{(2)}}(x^{0})=\nabla\tilde{y}^{*}(x^{0})$ to approximate the gradients
in the subset with the strictly active constraint (red side). The twice-
differentiable function $\tilde{y}^{*}(x)$ is an extension of $y^{*}(x)$
(refer to the definition of $x^{I}(\cdot)$ in (12.8) of (Dempe 1998)). The
gradients $\nabla{y}^{*}(x^{0})$ and $\nabla\tilde{y}^{*}(x^{0})$ are computed
in the matrices $-{M^{S_{(1)}}_{\epsilon}}^{-1}N^{S_{(1)}}_{\epsilon}$ and
$-{M^{S_{(2)}}_{\epsilon}}^{-1}N^{S_{(2)}}_{\epsilon}$, respectively. Then,
the representative gradients $w^{S_{(1)}}(x^{0})$ and $w^{S_{(2)}}(x^{0})$ are
used to approximate $\bar{\partial}_{\epsilon}y^{*}(x^{0})$. Then, we can
compute $G(x^{0},\epsilon)=\\{2x^{0},-1\\}$ and
$\bar{\partial}_{\epsilon}\Phi(x^{0})=[2x^{0}-2\epsilon,-1]$ with
$-1\in[x^{0}-\epsilon,x^{0}+\epsilon]$. The approximation error
$|d(z,\operatorname{conv}G(x^{0},\epsilon))-d(z,\bar{\partial}_{\epsilon}\Phi(x^{0}))|$
is smaller than or equal to $2\epsilon$ for any $z$.

Algorithm 1 Gradient Approximation Method

0: Initial point $x^{0}$; Initial approximation radius
$\epsilon_{0}\in(0,\infty)$; Initial stationarity target
$\nu_{0}\in(0,\infty)$; Line search parameters
$(\beta,\gamma)\in(0,1)\times(0,1)$; Termination tolerances
$\left(\epsilon_{\mathrm{opt}};\nu_{\mathrm{opt}}\right)\in[0,\infty)\times[0,\infty)$;
Discount factors
$\left(\theta_{\epsilon},\theta_{\nu}\right)\in(0,1)\times(0,1)$.

1: for $k\in\mathbb{N}$ do

2: Solve the lower-level optimization problem $P(x^{k})$ and obtain
$y^{*}(x^{k})$, $\lambda(x^{k})$, and $\nu(x^{k})$

3: Check the differentiability of $y^{*}$ on
$\mathcal{B}\left(x^{k},\epsilon_{k}\right)$ by (6) and (7)

4: if $y^{*}$ is continuously differentiable on
$\mathcal{B}\left(x^{k},\epsilon_{k}\right)$ then

5: Compute $g^{k}=\nabla\Phi(x^{k})$ by (3)

6: else

7: Compute $G(x^{k},\epsilon_{k})$ by (5)

8:
$\bar{\partial}_{\epsilon_{k}}\Phi(x^{k})=\operatorname{conv}G(x^{k},\epsilon_{k})$

9: Compute
$g^{k}=\min\\{\|g\|:g\in\operatorname{conv}G(x^{k},\epsilon_{k})\\}$

10: end if

11: if $\left\|g^{k}\right\|\leq\nu_{\mathrm{opt}}$ and
$\epsilon_{k}\leq\epsilon_{\mathrm{opt}}$ then

12: Output: $x^{k}$ and terminate

13: end if

14: if $\left\|g^{k}\right\|\leq\nu_{k}$ then

15: $\nu_{k+1}\leftarrow\theta_{\nu}\nu_{k}$,
$\epsilon_{k+1}\leftarrow\theta_{\epsilon}\epsilon_{k}$, and $t_{k}\leftarrow
0$

16: else

17: Compute $t_{k}$ by the line search:
$t_{k}=\max\\{t\in\\{\gamma,\gamma^{2},\ldots\\}:\Phi(x^{k}-tg^{k})<\Phi(x^{k})-\beta
t\|g^{k}\|^{2}\\}$

18: $\nu_{k+1}\leftarrow\nu_{k}$ and $\epsilon_{k+1}\leftarrow\epsilon_{k}$

19: end if

20: $x^{k+1}\leftarrow x^{k}-t_{k}g^{k}$

21: end for

###  4.3 The Gradient Approximation Algorithm

Our proposed gradient approximation algorithm, summarized in Algorithm 1, is a
line search algorithm. It uses the approximation of the Clarke subdifferential
as the descent direction for line search. In iteration $k$, we firstly solve
the lower-level optimization problem $P(x^{k})$ and obtain $y^{*}(x^{k})$,
$\lambda(x^{k})$ and $\nu(x^{k})$. To reduce the computation complexity, the
solution in iteration $k$ serves as the initial point to solve $P(x^{k+1})$ in
iteration $k+1$. Secondly, we check the differentiability of $y^{*}$ on
$\mathcal{B}\left(x^{k},\epsilon_{k}\right)$ and its implementation details
are shown in Section 4.4. If $y^{*}$ is continuously differentiable on
$\mathcal{B}\left(x^{k},\epsilon_{k}\right)$, we use $\nabla\Phi(x^{k})$ to
approximate $\bar{\partial}_{\epsilon}\Phi(x^{k})$ which corresponds to
Proposition 1. Otherwise, $G(x^{k},\epsilon_{k})$ is used which corresponds to
Proposition 2. The details of computing $G(x^{k},\epsilon_{k})$ are shown in
(5) and Section 4.4. Thirdly, the line search direction $g^{k}$ is determined
by a vector which has the smallest norm over all vectors in the convex hull of
$G(x^{k},\epsilon_{k})$. During the optimization steps, as the iteration
number $k$ increases, the approximation radius $\epsilon_{k}$ decreases.
According to Propositions 1 and 2, the approximation error of the Clarke
subdifferential is diminishing. We next characterize the convergence of
Algorithm 1.

######  Theorem 3.

Suppose Assumptions 1, 2, 3 hold and $\Phi(x)$ is lower bounded on
$\mathbb{R}^{d_{x}}$. Let $\\{x^{k}\\}$ be the sequence generated by Algorithm
1 with $\nu_{\mathrm{opt}}=\epsilon_{\mathrm{opt}}=0$. Then,

  * (i)

For each $k$, the line search in line 17 has a solution $t_{k}$.

  * (ii)

$\lim_{k\rightarrow\infty}\nu_{k}=0$,
$\lim_{k\rightarrow\infty}\epsilon_{k}=0$.

  * (iii)

$\liminf_{k\rightarrow\infty}d(0,\bar{\partial}\Phi(x^{k}))=0$.

  * (iv)

Every limit point of $\\{x^{k}\\}$ is Clarke stationary for $\Phi$.

If the objective function $\Phi$ is non-convex but smooth, property (iii)
reduces to $\liminf_{k\rightarrow\infty}\|\nabla\Phi(x^{k})\|=0$, which is a
widely used convergence criterion for smooth and non-convex optimization
(Nesterov 1998; Jin et al. 2021). A sufficient condition for the existence of
limit point of $\\{x^{k}\\}$ is that the sequence is bounded.

###  4.4 Implementation Details

#### Check differentiability of $y^{*}$ on
$\mathcal{B}\left(x^{0},\epsilon_{0}\right)$

We propose Proposition 3 to check differentiability of $y^{*}$ on
$\mathcal{B}\left(x^{0},\epsilon_{0}\right)$, which is required by line 3 of
Algorithm 1.

######  Proposition 3.

Consider $x^{0}\in\mathbb{R}^{d_{x}}$ and $\epsilon>0$. Suppose Assumptions 1,
2, 3 hold. Then, Lipschitz constants of functions $\Phi(x)$, $\lambda_{j}(x)$
and $p_{j}(x,y^{*}(x))$ on $\mathcal{B}(x^{0},\epsilon)$ exist and are denoted
by $l_{\Phi}(x^{0},\epsilon)$, $l_{\lambda_{j}}(x^{0},\epsilon)$ and
$l_{p_{j}}(x^{0},\epsilon)$, respectively. Further, suppose the SCSC holds at
$y^{*}(x^{0})$ w.r.t. $\lambda(x^{0})$. If there exists $\epsilon_{1}>0$ such
that

$\displaystyle\lambda_{j}(x^{0})>l_{\lambda_{j}}(x^{0},\epsilon_{1})\epsilon_{1}\
\text{ for all }j\in J(x^{0}),$ (6) $\displaystyle
p_{j}(x^{0},y^{*}(x^{0}))<-l_{p_{j}}(x^{0},\epsilon_{1})\epsilon_{1}\ \text{
for all }j\not\in J(x^{0}),$

then $y^{*}$ is continuously differentiable on
$\mathcal{B}(x^{0},\epsilon_{1})$.

Proposition 3 shows that, $y^{*}$ is continuously differentiable on a
neighborhood of $x^{0}$, if for any $j$, either (i) $\lambda_{j}$ is larger
than zero with non-trivial amount when the constraint
$p_{j}(x^{0},y^{*}(x^{0}))$ is active; or (ii) the satisfaction of
$p_{j}(x^{0},y^{*}(x^{0}))$ is non-trivial when it is inactive. For case (i),
$\lambda_{j}(x)>0$ and the constraint is strictly active for all
$x\in\mathcal{B}(x^{0},\epsilon)$; for case (ii), $p_{j}(x,y^{*}(x))<0$ and
the constraint is inactive for all $x\in\mathcal{B}(x^{0},\epsilon)$. As a
illustration on the problem in Example 1 shown in Fig. 4, $y^{*}$ is
continuously differentiable on $\mathcal{B}(x^{0},\epsilon)$,
$\mathcal{B}(x^{1},\epsilon)$ and $\mathcal{B}(x^{2},\epsilon)$, and the
constraint is inactive or strictly active in each ball.

We evaluate the differentiability of $y^{*}(x)$ and $\Phi(x)$ on
$\mathcal{B}(x^{0},\epsilon)$ by Proposition 3. In particular, we
approximatively regard that $y^{*}$ and $\Phi$ is continuously differentiable
on $\mathcal{B}(x^{0},\epsilon)$ if (6) is satisfied; otherwise, there exists
$x\in\mathcal{B}(x^{0},\epsilon)$ such that $y^{*}$ and $\Phi$ is not
continuously differentiable at $x$. The Lipschitz constants
$l_{\lambda_{j}}(x^{0},\epsilon)$ and $l_{p_{j}}(x^{0},\epsilon)$ are computed
as

$\displaystyle
l_{\lambda_{j}}(x^{0},\epsilon)=\|\nabla\lambda_{j}(x^{0})\|+\delta,$ (7)
$\displaystyle
l_{p_{j}}(x^{0},\epsilon)=\|\nabla_{x}p_{j}(x^{0},y^{*}(x^{0}))+$
$\displaystyle\quad\quad\quad\nabla
y^{*}(x^{0})^{\top}\nabla_{y}p_{j}(x^{0},y^{*}(x^{0}))\|+\delta,$

where $\delta$ is a small parameter, and $\nabla_{x}p_{j}(x^{0},y^{*}(x^{0}))$
and $\nabla\lambda_{j}(x^{0})$ are given in (4). Here, for a function $f$, we
approximate its Lipschitz constant on $\mathcal{B}(x^{0},\epsilon)$, which is
defined as $l_{f}(x^{0},\epsilon)\triangleq\sup_{x}\\{\|\nabla
f(x)\|:x\in\mathcal{B}(x^{0},\epsilon)\\}$, as
$l_{f}(x^{0},\epsilon)\approx\|\nabla f(x^{0})\|+\delta$. As $\epsilon$
decreases, $f$ in $\mathcal{B}(x^{0},\epsilon)$ is approximating to an affine
function, and then the approximation error of $l_{f}(x^{0},\epsilon)$
decreases.

#### Computation of $G(x^{0},\epsilon)$

To compute $G(x^{0},\epsilon)$ in line 7 of Algorithm 1, we need to compute
the sets $I_{+}^{\epsilon}(x^{0})$ and $I^{\epsilon}(x^{0})$ defined in
Proposition 2. Similar to the idea in Proposition 3, we evaluate
$I_{+}^{\epsilon}(x^{0})$ and $I^{\epsilon}(x^{0})$ as

$\displaystyle I_{+}^{\epsilon}(x^{0})=\left\\{j\in
J(x^{0}):\lambda_{j}(x^{0})>l_{\lambda_{j}}(x^{0},\epsilon)\epsilon\right\\},$
$\displaystyle I^{\epsilon}_{-}(x^{0})=\left\\{j\not\in
J(x^{0}):\right.\left.p_{j}(x^{0},y^{*}(x^{0}))<-l_{p_{j}}(x^{0},\epsilon)\epsilon\right\\},$
$\displaystyle I^{\epsilon}(x^{0})=\left\\{j:j\not\in
I^{\epsilon}_{+}(x^{0})\cup I^{\epsilon}_{-}(x^{0})\right\\}.$ (8)

Recall that the KKT conditions hold at $y^{*}(x^{0})$ for problem $P(x^{0})$,
then for any $x\in\mathcal{B}(x^{0},\epsilon)$, $p_{j}(x,y^{*}(x))=0$ for
$j\in I_{+}^{\epsilon}(x^{0})$ and $\lambda_{j}(x)=0$ for $j\in
I_{-}^{\epsilon}(x^{0})$. Here, we also use $l_{\lambda_{j}}$ and $l_{p_{j}}$
given in (7) as the Lipschitz constants. When $y^{*}$ and $\lambda$ are not
differentiable at $x^{0}$, we sample a point $x^{\prime}$ near $x^{0}$ such
that $y^{*}$ and $\lambda$ are differentiable at $x^{\prime}$, then replace
$\nabla\lambda(x^{0})$ and $\nabla y^{*}(x^{0})$ in (7) by
$\nabla\lambda(x^{\prime})$ and $\nabla y^{*}(x^{\prime})$.

##  5 Experiments

###  5.1 Hyperparameter Optimization

Hyperparameter optimization has been widely studied (Pedregosa 2016;
Franceschi et al. 2017; Ji, Yang, and Liang 2021). However, existing methods
cannot handle hyperparameter optimization of constrained learning problems,
such as the supported vector machine (SVM) classification (Cortes and Vapnik
1995), constrained reinforcement learning (Achiam et al. 2017; Chen, Dong, and
Wang 2021; Xu, Liang, and Lan 2021). We apply the proposed algorithm to
hyperparameter optimization of constrained learning.

|
---|---
|
Figure 5:  Loss and accuracy v.s. running time in hyperparameter optimization
of linear and kernelized SVM

#### Hyperparameter Optimization of SVM

We optimize the hyperparameter in the SVM optimization, i.e., the penalty
terms of the separation violations. We conduct the experiment on linear SVM
and kernelized SVM on the dataset of diabetes in (Dua and Graff 2017). It is
the first time to solve hyperparameter optimization for SVM. We provide
details of the problem formulation and the implementation setting in Appendix
B.1. As shown in Fig. 5, the loss is nearly convergent for both linear and
kernelized SVM, and the final test accuracy is much better than that of
randomly selected hyperparameters, which is the initial point of the
optimization.

#### Data Hyper-Cleaning

Data hyper-cleaning (Franceschi et al. 2017; Shaban et al. 2019) is to train a
classifier in a setting where the labels of training data are corrupted with a
probability $p$ (i.e., the corruption rate). We formulate the problem as a
hyperparameter optimization of SVM and conduct experiments on a breast cancer
dataset provided in (Dua and Graff 2017). The problem formulation and the
implementation setting are provided in Appendix B.1. We compare our gradient
approximation method with directly gradient descent used in (Amos and Kolter
2017; Lee et al. 2019). It is shown in Fig. 6 that, our method converges
faster than the benchmark method in terms of the loss and accuracy in both the
training and test stages. Moreover, both the two methods achieve the test
accuracy $96.2\%$ using the corrupt data ($p=0.4$). The accuracy is comparable
to the test accuracy $96.5\%$ of an SVM model where the data is not corrupted.

|
---|---
Figure 6: Comparison of gradient descent (GD) and gradient approximation method (GAM) in data hyper-cleaning with the corruption rate $p=0.4$. Left: training and test losses of GD and GAM v.s. running time; right: training and test accuracy of GD and GAM with $p=0.4$ and training and test accuracy with $p=0$ v.s. running time.  |
---|---
|
Figure 7:  Comparison of MetaOptNet and gradient approximation method (GAM).
For each dataset, left: training loss v.s. running time; right: test accuracy
v.s. running time.

###  5.2 Meta-Learning

Meta-learning approaches for few-shot learning have been formulated as bilevel
optimization problems in (Rajeswaran et al. 2019; Lee et al. 2019; Ji, Yang,
and Liang 2021). In particular, the problem in MetaOptNet (Lee et al. 2019)
has the form of problem (2) with the lower-level constraints. However, its
optimization does not explicitly consider the non-differentiability of the
objective function and cannot guarantee convergence. In the experiment, we
compare our algorithm with the optimization in MetaOptNet on datasets CIFAR-FS
(Bertinetto et al. 2018) and FC100 (Oreshkin, Rodríguez López, and Lacoste
2018), which are widely used for few-shot learning. Appendix B.2 provides
details of the problem formulation and the experiment setting.

Fig. 7 compares our gradient approximation method and the direct gradient
descent in MetaOptNet (Lee et al. 2019). The two algorithms share all training
configurations, including the network structure, the learning rate in each
epoch and the batch size. For both CIFAR-FS and FC100 datasets, our method
converges faster than the optimization in MetaOptNet in terms of the training
loss and test accuracy, and achieves a higher final test accuracy. Note that
the only difference between the two algorithms in this experiment is the
computation of the descent direction. The result shows the Clarke
subdifferential approximation in our algorithm works better than the gradient
as the descent direction. This is consistent with Proposition 2, where a set
of representative gradients instead one gradient is more suitable to
approximate the Clarke subdifferential. More comparison results with other
meta-learning approaches are given in Appendix B.2.

##  6 Conclusion

We develop a gradient approximation method for the bilevel optimization where
the lower-level optimization problem is convex with equality and inequality
constraints and the upper-level optimization is non-convex. The proposed
method efficiently approximates the Clarke Subdifferential of the non-smooth
objective function, and theoretically guarantees convergence. Our experiments
validate our theoretical analysis and demonstrate the superior effectiveness
of the algorithm.

##  7 Acknowledgements

This work was partially supported by NSF awards ECCS 1846706 and ECCS 2140175.

## References

  * Achiam et al. (2017) Achiam, J.; Held, D.; Tamar, A.; and Abbeel, P. 2017.  Constrained policy optimization.  In _International Conference on Machine Learning_ , 22–31. PMLR.
  * Agrawal et al. (2019) Agrawal, A.; Amos, B.; Barratt, S.; Boyd, S.; Diamond, S.; and Kolter, J. Z. 2019\.  Differentiable convex optimization layers.  _Advances in Neural Information Processing Systems_ , 9562–9674.
  * Amos and Kolter (2017) Amos, B.; and Kolter, J. Z. 2017.  Optnet: Differentiable optimization as a layer in neural networks.  In _International Conference on Machine Learning_ , 136–145. PMLR.
  * Amos, Xu, and Kolter (2017) Amos, B.; Xu, L.; and Kolter, J. Z. 2017.  Input convex neural networks.  In _International Conference on Machine Learning_ , 146–155. PMLR.
  * Bagirov, Karmitsa, and Mäkelä (2014) Bagirov, A.; Karmitsa, N.; and Mäkelä, M. M. 2014.  _Introduction to nonsmooth optimization: theory, practice and software_ , volume 12.  Springer.
  * Bagirov et al. (2020) Bagirov, A. M.; Gaudioso, M.; Karmitsa, N.; Mäkelä, M. M.; and Taheri, S. 2020.  Gradient sampling methods for nonsmooth optimization.  In _Numerical Nonsmooth Optimization: State of the Art Algorithms_. Springer.
  * Bard and Moore (1990) Bard, J.; and Moore, J. 1990.  A branch and bound algorithm for the bilevel programming problem.  _SIAM Journal on Scientific and Statistical Computing_ , 11.
  * Bard and Falk (1982) Bard, J. F.; and Falk, J. E. 1982.  An explicit solution to the multi-level programming problem.  _Computers and Operations Research_ , 9(1): 77–100.
  * Bengio (2000) Bengio, Y. 2000.  Gradient-based optimization of hyperparameters.  _Neural computation_ , 12(8): 1889–1900.
  * Bertinetto et al. (2018) Bertinetto, L.; Henriques, J. F.; Torr, P. H.; and Vedaldi, A. 2018.  Meta-learning with differentiable closed-form solvers.  _arXiv preprint arXiv:1805.08136_.
  * Bottou and Bousquet (2008) Bottou, L.; and Bousquet, O. 2008.  The tradeoffs of large scale learning.  _Advances in Neural Information Processing Systems_ , 161–168.
  * Burke, Lewis, and Overton (2005) Burke, J. V.; Lewis, A. S.; and Overton, M. L. 2005.  A robust gradient sampling algorithm for nonsmooth, nonconvex optimization.  _SIAM Journal on Optimization_ , 15(3): 751–779.
  * Chen, Dong, and Wang (2021) Chen, Y.; Dong, J.; and Wang, Z. 2021.  A primal-dual approach to constrained markov decision processes.  _arXiv preprint arXiv:2101.10895_.
  * Clarke (1975) Clarke, F. H. 1975.  Generalized gradients and applications.  _Transactions of the American Mathematical Society_ , 205: 247–262.
  * Cortes and Vapnik (1995) Cortes, C.; and Vapnik, V. 1995.  Support-vector networks.  _Machine learning_ , 20(3): 273–297.
  * Dempe (1998) Dempe, S. 1998.  An implicit function approach to bilevel programming problems.  In _Multilevel Optimization: Algorithms and Applications_ , 273–294. Springer.
  * Dempe and Franke (2016) Dempe, S.; and Franke, S. 2016.  On the solution of convex bilevel optimization problems.  _Computational Optimization and Applications_ , 63(3): 685–703.
  * Domke (2012) Domke, J. 2012.  Generic methods for optimization-based modeling.  In _Artificial Intelligence and Statistics_ , 318–326. PMLR.
  * Dua and Graff (2017) Dua, D.; and Graff, C. 2017.  UCI Machine Learning Repository.
  * Fiacco (1983) Fiacco, A. V. 1983.  _Introduction to sensitivity and stability analysis in nonlinear programming_.  Academic press.
  * Fiacco and Ishizuka (1990) Fiacco, A. V.; and Ishizuka, Y. 1990.  Sensitivity and stability analysis for nonlinear programming.  _Annals of Operations Research_ , 27(1): 215–235.
  * Fiacco and McCormick (1970) Fiacco, A. V.; and McCormick, G. P. 1970.  Nonlinear programming: sequential unconstrained minimization techniques.  _SIAM Review_ , 12(4): 593–594.
  * Finn, Abbeel, and Levine (2017) Finn, C.; Abbeel, P.; and Levine, S. 2017.  Model-agnostic meta-learning for fast adaptation of deep networks.  In _International Conference on Machine Learning_ , 1126–1135. PMLR.
  * Franceschi et al. (2017) Franceschi, L.; Donini, M.; Frasconi, P.; and Pontil, M. 2017.  Forward and reverse gradient-based hyperparameter optimization.  In _International Conference on Machine Learning_ , 1165–1173. PMLR.
  * Franceschi et al. (2018) Franceschi, L.; Frasconi, P.; Salzo, S.; Grazzi, R.; and Pontil, M. 2018.  Bilevel programming for hyperparameter optimization and meta-learning.  In _International Conference on Machine Learning_ , 1568–1577. PMLR.
  * Ghadimi and Wang (2018) Ghadimi, S.; and Wang, M. 2018.  Approximation methods for bilevel programming.  _arXiv preprint arXiv:1802.02246_.
  * Giorgi and Zuccotti (2018) Giorgi, G.; and Zuccotti, C. 2018.  A tutorial on sensitivity and stability in nonlinear programming and variational inequalities under differentiability assumptions.  Technical report, DEM Working Paper Series.
  * Gould et al. (2016) Gould, S.; Fernando, B.; Cherian, A.; Anderson, P.; Cruz, R. S.; and Guo, E. 2016\.  On differentiating parameterized argmin and argmax problems with application to bi-level optimization.  _arXiv preprint arXiv:1607.05447_.
  * Grazzi et al. (2020) Grazzi, R.; Franceschi, L.; Pontil, M.; and Salzo, S. 2020.  On the iteration complexity of hypergradient computation.  In _International Conference on Machine Learning_ , 3748–3758. PMLR.
  * Hansen, Jaumard, and Savard (1992) Hansen, P.; Jaumard, B.; and Savard, G. 1992.  New branch-and-bound rules for linear bilevel programming.  _SIAM Journal on Scientific Computing_ , 13(5): 1194–1217.
  * Hardt, Recht, and Singer (2016) Hardt, M.; Recht, B.; and Singer, Y. 2016.  Train faster, generalize better: Stability of stochastic gradient descent.  In _International Conference on Machine Learning_ , 1225–1234. PMLR.
  * Hestenes and Stiefel (1952) Hestenes, M. R.; and Stiefel, E. 1952.  Methods of conjugate gradients for solving.  _Journal of research of the National Bureau of Standards_ , 49(6): 409.
  * Hofmann, Schölkopf, and Smola (2008) Hofmann, T.; Schölkopf, B.; and Smola, A. J. 2008.  Kernel methods in machine learning.  _The Annals of Statistics_ , 36(3): 1171 – 1220.
  * Hong et al. (2020) Hong, M.; Wai, H.-T.; Wang, Z.; and Yang, Z. 2020.  A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic.  _arXiv preprint arXiv:2007.05170_.
  * Ji et al. (2020) Ji, K.; Lee, J. D.; Liang, Y.; and Poor, H. V. 2020.  Convergence of meta-learning with task-specific adaptation over partial parameters.  _Advances in Neural Information Processing Systems_ , 11490–11500.
  * Ji, Yang, and Liang (2021) Ji, K.; Yang, J.; and Liang, Y. 2021.  Bilevel optimization: Convergence analysis and enhanced design.  In _International Conference on Machine Learning_ , 4882–4892. PMLR.
  * Jin et al. (2021) Jin, C.; Netrapalli, P.; Ge, R.; Kakade, S. M.; and Jordan, M. I. 2021.  On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points.  _Journal of the ACM_ , 68(2): 1–29.
  * Kiwiel (2007) Kiwiel, K. C. 2007.  Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization.  _SIAM Journal on Optimization_ , 18(2): 379–388.
  * Kojima (1980) Kojima, M. 1980.  Strongly stable stationary solutions in nonlinear programs.  In _Analysis and computation of fixed points_ , 93–138. Elsevier.
  * Kolstad and Lasdon (1990) Kolstad, C. D.; and Lasdon, L. S. 1990.  Derivative evaluation and computational experience with large bilevel mathematical programs.  _Journal of optimization theory and applications_ , 65(3): 485–499.
  * Konda and Tsitsiklis (2000) Konda, V. R.; and Tsitsiklis, J. N. 2000.  Actor-critic algorithms.  In _Advances in Neural Information Processing Systems_ , 1008–1014.
  * Kyparisis (1985) Kyparisis, J. 1985.  On uniqueness of Kuhn-Tucker multipliers in nonlinear programming.  _Mathematical Programming_ , 32(2): 242–246.
  * Lee et al. (2019) Lee, K.; Maji, S.; Ravichandran, A.; and Soatto, S. 2019.  Meta-learning with differentiable convex optimization.  In _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 10649–10657.
  * Liu, Simonyan, and Yang (2018) Liu, H.; Simonyan, K.; and Yang, Y. 2018.  DARTS: Differentiable architecture search.  In _International Conference on Learning Representations_.
  * Liu et al. (2021a) Liu, R.; Gao, J.; Zhang, J.; Meng, D.; and Lin, Z. 2021a.  Investigating bi-Level optimization for learning and vision from a unified perspective: A survey and beyond.  _IEEE Transactions on Pattern Analysis & Machine Intelligence_.
  * Liu et al. (2021b) Liu, R.; Liu, Y.; Zeng, S.; and Zhang, J. 2021b.  Towards gradient-based bilevel optimization with non-convex followers and beyond.  _Advances in Neural Information Processing Systems_ , 34: 8662–8675.
  * Lorraine, Vicol, and Duvenaud (2020) Lorraine, J.; Vicol, P.; and Duvenaud, D. 2020.  Optimizing millions of hyperparameters by implicit differentiation.  In _International Conference on Artificial Intelligence and Statistics_ , 1540–1552. PMLR.
  * Malanowski (1985) Malanowski, K. 1985.  Differentiability with respect to parameters of solutions to convex programming problems.  _Mathematical Programming_ , 33(3): 352–361.
  * Nemirovski et al. (2009) Nemirovski, A.; Juditsky, A.; Lan, G.; and Shapiro, A. 2009.  Robust stochastic approximation approach to stochastic programming.  _SIAM Journal on optimization_ , 19(4): 1574–1609.
  * Nesterov (1998) Nesterov, Y. 1998.  Introductory lectures on convex programming.
  * Oreshkin, Rodríguez López, and Lacoste (2018) Oreshkin, B.; Rodríguez López, P.; and Lacoste, A. 2018.  Tadam: Task dependent adaptive metric for improved few-shot learning.  _Advances in Neural Information Processing Systems_ , 719–729.
  * Pedregosa (2016) Pedregosa, F. 2016.  Hyperparameter optimization with approximate gradient.  In _International Conference on Machine Learning_ , 737–746. PMLR.
  * Rajeswaran et al. (2019) Rajeswaran, A.; Finn, C.; Kakade, S. M.; and Levine, S. 2019.  Meta-learning with implicit gradients.  In _Advances in Neural Information Processing Systems_ , 113–124.
  * Ralph and Dempe (1995) Ralph, D.; and Dempe, S. 1995.  Directional derivatives of the solution of a parametric nonlinear program.  _Mathematical programming_ , 70(1): 159–172.
  * Savard and Gauvin (1994) Savard, G.; and Gauvin, J. 1994.  The steepest descent direction for the nonlinear bilevel programming problem.  _Operations Research Letters_ , 15(5): 265–272.
  * Schramm and Zowe (1992) Schramm, H.; and Zowe, J. 1992.  A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results.  _SIAM journal on optimization_ , 2(1): 121–152.
  * Shaban et al. (2019) Shaban, A.; Cheng, C.-A.; Hatch, N.; and Boots, B. 2019.  Truncated back-propagation for bilevel optimization.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , 1723–1732. PMLR.
  * Shi, Lu, and Zhang (2005) Shi, C.; Lu, J.; and Zhang, G. 2005.  An extended Kuhn-Tucker approach for linear bilevel programming.  _Applied Mathematics and Computation_ , 162(1): 51–63.
  * Snell, Swersky, and Zemel (2017) Snell, J.; Swersky, K.; and Zemel, R. 2017.  Prototypical networks for few-shot learning.  _Advances in Neural Information Processing Systems_ , 4080–4090.
  * Sow et al. (2022) Sow, D.; Ji, K.; Guan, Z.; and Liang, Y. 2022.  A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima.  _arXiv preprint arXiv:2203.01123_.
  * Sung et al. (2018) Sung, F.; Yang, Y.; Zhang, L.; Xiang, T.; Torr, P. H.; and Hospedales, T. M. 2018\.  Learning to compare: Relation network for few-shot learning.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 1199–1208.
  * Xu, Liang, and Lan (2021) Xu, T.; Liang, Y.; and Lan, G. 2021.  Crpo: A new approach for safe reinforcement learning with convergence guarantee.  In _International Conference on Machine Learning_ , 11480–11491. PMLR.

Supplementary Materials

##  Appendix A Implementation Supplement

###  A.1 Computation of gradient matrices

In lines 5 and 7 of Algorithm 1, we need to compute the gradient matrices
$\nabla\Phi(x^{k})$ and the set of gradients $G(x^{k},\epsilon_{k})$. Notice
that both $-M_{+}^{-1}(x)N_{+}(x)$ in the computation of $\nabla\Phi(x^{k})$
in (4) and
$-M^{S}_{\epsilon}(x^{0},y^{*}(x^{0}))^{-1}N^{S}_{\epsilon}(x^{0},y^{*}(x^{0}))$
in the computation of $G(x^{0},\epsilon)$ in (5) have a form of

$-\left[\begin{array}[]{ccccccc}\nabla_{y}^{2}\mathcal{L}&\nabla_{y}r^{\top}\\\
\nabla_{y}r&0\end{array}\right]^{-1}\left[\begin{array}[]{c}\nabla_{xy}^{2}\mathcal{L}\\\
\nabla_{x}r\end{array}\right],$ (9)

where $\nabla_{y}^{2}\mathcal{L}^{-1}$ is positive definite at
$(y^{*}(x),\lambda(x),\nu(x),x)$ for any $x$ (shown in the proof (ii) of
Theorem 6 in Appendix). We can compute (9) as follows. First, as
$\nabla_{y}^{2}\mathcal{L}^{-1}$ is positive definite, we can use the
conjugate gradient (CG) method (Hestenes and Stiefel 1952) to compute
$A=\nabla_{y}^{2}\mathcal{L}^{-1}\nabla_{xy}^{2}\mathcal{L}$ and
$B=\nabla_{y}^{2}\mathcal{L}^{-1}\nabla_{y}{r}^{\top}$. Second, (9) can be
written as

$\left[\begin{array}[]{c}-A+B(\nabla_{y}{r}B)^{-1}(\nabla_{y}{r}A-\nabla_{x}r)\\\
-(\nabla_{y}{r}B)^{-1}(\nabla_{y}{r}A-\nabla_{x}r)\end{array}\right].$ (10)

Let the number of strictly active constraints be $m^{+}$ and the number of
non-strictly active constraints be $m^{-}$ in $P(x)$, and $n$ is the number of
equality constraints. Then, $r(x,y)$ is a vector function with at most
$n+m^{+}+m^{-}$ dimensions. The dimension of $\nabla_{y}^{2}\mathcal{L}$ is
$d_{y}$. In machine learning applications, $d_{x}$ is usually large and
$n+m^{+}+m^{-}$ is relatively small. It is shown in (Ji, Yang, and Liang 2021)
that the computation of $A$ and $B$ in the first step is achievable, and thus
so is the computation of (10).

Paper (Amos and Kolter 2017) provides a highly efficient solver to compute the
gradient of the solution of a quadratic program, which exploits fast GPU-based
batch solves within a primal-dual interior point method. The tool can also be
used to compute $-M_{+}^{-1}(x)N_{+}(x)$ and
$-M^{S}_{\epsilon}(x^{0},y^{*}(x^{0}))^{-1}N^{S}_{\epsilon}(x^{0},y^{*}(x^{0}))$
in Algorithm 1, when the lower-level optimization problem is a quadratic
program.

###  A.2 Satisfaction of Assumptions

Here are two reminders of Assumption 3.

######  Remark 2.

A sufficient condition of Assumption 3 which is easier to check is that, the
solution $y^{*}(x)$ exists for $P\left(x\right)$ and the LICQ holds at $y$ for
$P(x)$ for all ${x}\in\mathbb{R}^{d_{x}}$ and $y\in\mathbb{R}^{d_{y}}$.

######  Remark 3.

The equality constraint cannot be replaced by two inequality constraints,
i.e., $p=0$ is replaced by $p\leq 0$ and $-p\leq 0$. Otherwise, the LICQ is
violated.

Note that all optimization problems in the experiments of this paper satisfy
Assumptions 1, 2, 3. The details are shown in Appendix B.

##  Appendix B Experimental Supplement

All experiments are executed on a computer with a 4.10 GHz Intel Core i5 CPU
and an RTX 3080 GPU.

###  B.1 Hyperparameter Optimization

In a machine learning problem, given a hyperparameter $\Lambda$, the learner
is to minimize the training error and the optimal parameter is denoted as
$w^{*}(\Lambda)$. Hyperparameter optimization is to search for the best
hyperparameter $\Lambda^{*}$ for the learning problem, which can be formulated
as a bilevel optimization problem. In particular, it is to minimize the
validation error of the learner’s parameter $w^{*}(\Lambda)$ in the upper-
level optimization, where $w^{*}(\Lambda)$ is the minimizer of training error
in the lower-level optimization under the hyperparameter $\Lambda$.

Hyperparameter optimization has been widely studied in (Pedregosa 2016;
Franceschi et al. 2017, 2018; Lorraine, Vicol, and Duvenaud 2020; Ji, Yang,
and Liang 2021). However, these methods cannot handle with hyperparameter
optimization of constrained learning problems, such as the supported vector
machine (SVM) classification (Cortes and Vapnik 1995), safe reinforcement
learning (Achiam et al. 2017; Chen, Dong, and Wang 2021; Xu, Liang, and Lan
2021). We apply the proposed algorithm to hyperparameter optimization of
constrained learning problem, which is formulated as

$\displaystyle\min_{\Lambda}\
\Phi(\Lambda)=\mathcal{L}_{\mathcal{D}_{\text{val
}}}(w^{*})=\frac{1}{\left|\mathcal{D}_{\text{val
}}\right|}\sum_{z\in\mathcal{D}_{\text{val }}}\mathcal{L}\left(w^{*};z\right)$
$\displaystyle\text{ s.t.
}w^{*}=\underset{w}{\arg\min}\\{\mathcal{F}_{\mathcal{D}_{\text{tr
}}}(\Lambda,w):p\left(\Lambda,w\right)\leq 0;q\left(\Lambda,w\right)=0\\},$

where $\mathcal{D}_{\text{val }}$ and $\mathcal{D}_{\text{tr }}$ are
validation and training data, $\mathcal{L}_{\mathcal{D}_{\text{val }}}$ is the
loss function of model parameter $\omega$ on data $\mathcal{D}_{\text{val }}$.
The lower-level optimization is the training of model parameter $w$, where
$\mathcal{F}_{\mathcal{D}_{\text{val }}}$ is the training objective on
$\mathcal{D}_{\text{tr }}$ and $p$, $q$ are the constraints.

#### Hyperparameter Optimization of SVM

The optimization problem for SVM is:

$\displaystyle(w^{*},b^{*},{\xi}^{*})=$ $\displaystyle\arg\min_{w,b,\xi}\
\frac{1}{2}\|w\|^{2}+\frac{1}{2}\sum_{i=1}^{N}{e^{c_{i}}}\xi_{i}^{2}$ (11)
$\displaystyle\text{ s.t. }\ l_{i}\left(w^{\top}\phi(z_{i})+b\right)\geq
1-\xi_{i},\ i=1,2,\ldots N,$

Here, $z_{i}$ is the data point and $y_{i}$ is the label, and
$(z_{i};l_{i})\in\mathcal{D}_{\text{tr }}$ for all $1\leq i\leq N$. and
$(z_{i};y_{i})\in\mathcal{D}_{\text{tr }}$ for all $1\leq i\leq N$. The vector
function $\phi(z_{i})$ is the high dimension feature for point $z_{i}$. The
kernel function is defined as
$K\left(z_{i},z_{j}\right)=\phi\left(z_{i}\right)^{T}\phi\left(z_{j}\right)$.
The hyperparameter optimization of SVM is formulated as

$\min_{c}\ \Phi(c)=\mathcal{L}_{\mathcal{D}_{\text{val }}}(w^{*},b^{*}),$ (12)

where $w^{*},b^{*}$ are given in (11) and the optimized hyperparameter is
$c=[c_{1},\dots,c_{N}]$. To satisfy Assumption 2, we set the objective
function of (11) as
$\frac{1}{2}\|w\|^{2}+\frac{1}{2}\sum_{i=1}^{N}{e^{c_{i}}}\xi_{i}^{2}+\frac{1}{2}\mu
b^{2}$ where $\mu$ is a small positive number. Then, the objective function is
strongly-convex w.r.t $(w,b,\xi)$. It is easy to justify the LICQ in
Assumption 3 is satisfied.

The upper-level objective function is defined as
$\mathcal{L}_{\mathcal{D}_{\text{val
}}}(w^{*},b^{*})=\frac{1}{\left|\mathcal{D}_{\text{val
}}\right|}\sum_{(z,l)\in\mathcal{D}_{\text{val
}}}\mathcal{L}\left(w^{*},b^{*};z,l\right)$, where
$\mathcal{L}(w^{*},b^{*};\mathcal{D}_{\text{val }})$ is defined as
$\mathcal{L}\left(w^{*},b^{*};z,l\right)=\sigma((\frac{-l(z^{\top}{w^{*}}+b)}{\|w^{*}\|})$
and $\sigma(x)=\frac{1-e^{-x}}{1+e^{-x}}$. Here,
$\frac{l(z^{\top}{w^{*}}+b)}{\|w^{*}\|}$ is the signed distance between point
$z$ and the decision plane $z^{\top}{w^{*}}+b=0$, where
$\frac{l(z^{\top}{w^{*}}+b)}{\|w^{*}\|}>0$ when the prediction is correct and
$\frac{l(z^{\top}{w^{*}}+b)}{\|w^{*}\|}<0$ when the prediction is incorrect.
Thus, $\mathcal{L}_{\mathcal{D}_{\text{val }}}(w^{*},b^{*})$ is a
differentiable surrogate function of the validation accuracy.

When the feature function $\phi$ is not tractable, the hyperparameter $c$ of
(11) can not be directly optimized. For example, in kernelized SVM (Hofmann,
Schölkopf, and Smola 2008), under most kernel functions, e.g., Gaussian kernel
and polynomial kernel $\phi$ are unknown or very complex. Then, it is hard to
compute $\nabla w^{*}(c)$ by Theorem 2. Therefore, in kernelized SVM, we solve
the dual problem of (11):

$\displaystyle\min_{\alpha}$
$\displaystyle\frac{1}{2}\alpha^{\top}(Q+C^{-1})\alpha-\sum_{i=1}^{n}\alpha_{i}$
(13) s.t. $\displaystyle\ \sum_{i=1}^{n}\alpha_{i}y_{i}=0$
$\displaystyle\alpha_{i}\geq 0,\ i=1,2,\ldots N,$

where $Q$ is an $n$ by $n$ positive semi-definite matrix with $Q_{ij}\equiv
y_{i}y_{j}K\left(z_{i},z_{j}\right)$, and
$C=\operatorname{diag}\left(e^{c_{1}},\ldots,e^{c_{n}}\right)$. Since the
strong duality holds for problem (11), we have

$w^{*}=\sum_{i=1}^{n}\alpha_{i}^{*}y_{i}\phi\left(z_{i}\right)$

and

$b^{*}=y_{i}(1-e^{-c_{i}}\alpha_{i})-\sum_{j=1}^{n}\alpha_{j}^{*}y_{j}\phi\left(z_{j}\right)^{\top}\phi\left(z_{i}\right)=y_{i}(1-e^{-c_{i}}\alpha_{i})-\sum_{j=1}^{n}\alpha_{j}^{*}y_{j}K\left(z_{j},z_{i}\right)$

for any support vector $z_{i}$ with $\alpha_{i}^{*}>0$. Following the kernel
method, the computation of $\phi$ is not required for both processes of model
training and prediction. The prediction of $z^{new}$ is

$\operatorname{sign}\\{{w^{*}}^{\top}\phi(z^{new})+b^{*}\\}=\operatorname{sign}\\{\sum_{i=1}^{n}\alpha_{i}^{*}y_{i}K\left(z_{i},z_{new}\right)+b^{*}\\}.$

Assumption 2 is satisfied, since the objective function
$\frac{1}{2}\alpha^{\top}(Q+C^{-1})\alpha-\sum_{i=1}^{n}\alpha_{i}$ where $Q$
is a positive semi-definite matrix and
$C^{-1}=\operatorname{diag}\left(e^{-c_{1}},\ldots,e^{-c_{n}}\right)$ is
positive definite, then the objective function is strongly-convex. Since there
exists $i$ such that $\alpha_{i}^{*}>0$, then it is easy to justify the LICQ
in Assumption 3 is satisfied.

In the experiment, we consider hyperparameter optimization of the linear SVM
model and the kernelized SVM model. Linear SVM:  The feature function is
$\phi(x)=x$. Both lower-level problems (11) and (13) works for hyperparameter
optimization of Linear SVM. Here, we solve the bilevel problem (11).
kernelized SVM:  We apply the polynomial kernel, i.e.,
$K(z,z^{\prime})=\phi(z)^{T}\phi(z^{\prime})=(\gamma
z^{\top}z^{\prime}+r)^{d}$, where $\gamma=1$ and $d=3$. We test our algorithm
on a diabetes dataset in (Dua and Graff 2017). For Algorithm 1, we set
$\gamma=0.3$, $\epsilon_{0}=0.3$, $\beta=0.5$ and fix the total iteration
number as 60.

#### Data Hyper-Cleaning

We formulate the data hyper-cleaning as the hyperparameter optimization of
SVM, where the upper-level optimization problem is shown in (12) and the
lower-level optimization problem is shown in (11). After the optimization of
the hyperparameter $c$, the penalty term $e^{c_{i}}$ which corresponds to the
corruption data $(z_{i},y_{i})$ will be close to $0$. Thus, the corruption
data $(z_{i},y_{i})$ is detected and almost does no affect training and the
prediction of the classifier model. We conduct experiments on a dataset of
breast cancer provided in (Dua and Graff 2017). For Algorithm 1, we set
$\gamma=0.3$, $\epsilon_{0}=0.3$, $\beta=0.5$ and fix the total iteration
number as 30.

###  B.2 Meta-learning

Meta-learning for few-shot learning is to learn a shared prior parameter
across a distribution of tasks, such that a simple learning step with few-shot
data based on the prior leads to a good adaptation to the task in the
distribution. In particular, the training task $\mathcal{T}_{i}$ is sampled
from distribution $P_{\mathcal{T}}$. Each task $\mathcal{T}_{i}$ is
characterized by its training data $\mathcal{D}_{i}^{tr}$ and test data
$\mathcal{D}_{i}^{test}$. The goal of meta-learning is to find a good
parameter ${\phi}$ and a base learner $\mathcal{A}$, such that the task-
specific parameter $w^{i}=\mathcal{A}({\phi},\mathcal{D}_{i}^{tr})$ has a
small test loss $\mathcal{L}(w^{i},\phi,\mathcal{D}_{i}^{test})$.

The training of meta-learning can be formulated as a constrained bilevel
optimization problem (Lee et al. 2019). The upper-level optimization is to
extract features from the input data. The multi-class SVM served as the base
learner $\mathcal{A}$ in the lower-level optimization to classify the data on
its extracted features. In particular, the feature extraction model
$f_{{\phi}}$ maps from the image $x_{n}$ to its features denoted as
$f_{{\phi}}(x_{n})$. The multi-class SVM in the lower-level optimization is a
constrained optimization problem:

$\displaystyle w^{i}=\mathcal{A}\left(\mathcal{D}_{i}^{\text{tr
}};{\phi}\right)=\underset{\\{{w}_{k}\\},\\{\xi_{n}\\}}{\arg\min}\frac{1}{2}\sum_{k}\left\|{w}_{k}\right\|_{2}^{2}+C\sum_{n}\xi_{n}$
(14) $\displaystyle\text{s.t. }{w}_{y_{n}}\cdot
f_{{\phi}}\left({x}_{n}\right)-{w}_{k}\cdot f_{{\phi}}\left({x}_{n}\right)\geq
1-\delta_{y_{n},k}-\xi_{n},\forall n,k$

where $\mathcal{D}^{{tr}}_{i}=\left\\{\left({x}_{n},y_{n}\right)\right\\}$
with image ${x}_{n}$ and its label $y_{n}$, $C$ is the regularization
parameter and $\delta_{\cdot,\cdot}$ is the Kronecker delta function. Here,
$k$ is the index of feature $f_{{\phi}}(x_{n})$, and $n$ is the index of the
data. The upper-level optimization is

$\min_{\phi}\sum_{\mathcal{T}_{i}\in
P_{\mathcal{T}}}\mathcal{L}\left(w^{i},\phi,\mathcal{D}^{{test}}_{i}\right).$
(15)

where

$\mathcal{L}\left(w^{i},\phi,\mathcal{D}^{{test}}_{i}\right)=\sum_{({x},y)\in\mathcal{D}^{{test}}}\left[-\gamma{w}_{y}^{i}\cdot
f_{\phi}({x})+\log\sum_{k}\exp\left(\gamma{w}_{k}^{i}\cdot
f_{\phi}({x})\right)\right]$

and $w^{i}$ is given in (14). Here,
$\mathcal{L}\left(w^{i},\phi,\mathcal{D}^{{test}}_{i}\right)$ is the negative
log-likelihood loss under the feature extraction parameter ${{\phi}}$ and the
SVM parameter ${w}^{i}$ optimized in lower-level optimization (14). Then, the
upper-level optimization (15) to find the best feature extraction parameter
${{\phi}}$.

Following the experiment setting in MetaOptNet (Lee et al. 2019), we use a
ResNet-12 network as the feature extraction mapping $f_{{\phi}}()$. Since the
line search in Algorithm 1 is not convenient for the meta-learning problem, we
compute the descent direction in 1 and use the SGD method with Nesterov
momentum of 0.9 and weight decay of 0.0005 to solve the problem. Each mini-
batch consists of 8 episodes. The model was meta-trained for 30 epochs, with
each epoch consisting of 1000 episodes. The learning rate was initially set to
0.1, and then changed to 0.006, 0.0012 at epochs 10, 20 and 25, respectively.
We use the configurations for both our method and the method in MetaOptNet
(Lee et al. 2019).

The comparison to previous work on CIFAR-FS and FC100 in the aspect of
prediction accuracy is shown in Table 1. It is shown that the final test
accuracy of our optimization algorithm is slightly better than that of
MetaOptNet-SVM (Lee et al. 2019).

Table 1: Comparison to prior work on CIFAR-FS and FC100. Average few-shot classification accuracies (%) with 95% confidence intervals on CIFAR-FS and FC100. $\ast$CIFAR-FS results from (Bertinetto et al. 2018). FC100 result from $\dagger$(Oreshkin, Rodríguez López, and Lacoste 2018) and ${\ddagger}$(Ji, Yang, and Liang 2021). All models are trained on the original training data of CIFAR-FS and FC100 in (Lee et al. 2019), and validation data are not included. |  | CIFAR-FS 5-way |  | FC100 5-way
---|---|---|---|---
model |  | 1-shot | 5-shot |  | 1-shot | 5-shot
MAML$\ast$${\ddagger}$ (Finn, Abbeel, and Levine 2017) |  | 58.9 $\pm$ 1.9 |  71.5 $\pm$ 1.0 |  | - |  47.2
Prototypical Networks$\ast$$\dagger$ (Snell, Swersky, and Zemel 2017) |  | 55.5 $\pm$ 0.7 |  72.0 $\pm$ 0.6 |  | 35.3 $\pm$ 0.6 |  48.6 $\pm$ 0.6
Relation Networks$\ast$ (Sung et al. 2018) |  | 55.0 $\pm$ 1.0 |  69.3 $\pm$ 0.8 |  | - |  -
R2D2 (Bertinetto et al. 2018) |  | 65.3 $\pm$ 0.2 |  79.4 $\pm$ 0.1 |  | - |  -
TADAM (Oreshkin, Rodríguez López, and Lacoste 2018) |  | - |  - |  | 40.1 $\pm$ 0.4 |  56.1 $\pm$ 0.4
ProtoNets (Snell, Swersky, and Zemel 2017) |  | 72.2 $\pm$ 0.7 |  83.5 $\pm$ 0.5 |  | 37.5 $\pm$ 0.6 |  52.5 $\pm$ 0.6
MetaOptNet-RR (Lee et al. 2019) |  | 72.6 $\pm$ 0.7 |  84.3 $\pm$ 0.5 |  | 40.5 $\pm$ 0.6 |  55.3 $\pm$ 0.6
MetaOptNet-SVM (Lee et al. 2019) |  | 72.0 $\pm$ 0.7 |  84.2 $\pm$ 0.5 |  | 41.1 $\pm$ 0.6 |  55.5 $\pm$ 0.6
MetaOptNet-SVM-GAE (ours) |  | 72.2 $\pm$ 0.7 |  84.6 $\pm$ 0.6 |  | 41.9 $\pm$ 0.6 |  56.4 $\pm$ 0.8

##  Appendix C Proof and Analysis

Firstly, we clarify notations used in this section. All notations used in this
section are the same as in the main body of the paper, except $J(x)$,
$J^{+}(x)$ and $J^{0}(x)$ in Section 3. In Section 3, we simplify notations in
(1) and denote $J(x,y^{*}(x))$ as $J(x)$, $J^{+}(x,y^{*}(x),{\lambda}(x))$ as
$J^{+}(x)$, and $J^{0}(x,y^{*}(x),\lambda(x))$ as $J^{0}(x)$, because the
optimal solution $y^{*}(x)$ and the Lagrangian multipliers ${\lambda}$ and
${\nu}$ are uniquely determined by $x$.

This section keeps all definitions in Definition 1, and simplify
$J^{+}(x,y,{\lambda})$ as $J^{+}(x,y)$, and $J^{0}(x,y,\lambda)$ as
$J^{0}(x,y)$, where the KKT conditions hold at $y$ for $P(x)$. We can do this
because Lagrangian multipliers $\lambda$ and $\mu$ are unique and determined
by $x$ and $y$ when the KKT conditions hold at $y$ for $P(x)$ and the LICQ
holds (Assumption 3) (Kyparisis 1985).

###  C.1 Proof of Theorems 1 and 2

We first list Definition 5, Theorems 4 and 5, which are shown in (Fiacco 1983;
Giorgi and Zuccotti 2018; Kojima 1980), then introduce Lemmas 1, 2 and 3.
Finally, we prove Theorem 6, which is the full version of the combination of
Theorems 1 and 2.

######  Definition 5.

Suppose that the KKT conditions hold at $\hat{y}$ for $P(x)$ with the
Lagrangian multipliers $\hat{\lambda}$ and $\hat{\nu}$, the Strong Second
Order Sufficient Conditions (SSOSC) hold at $\hat{y}$ if

$z^{\top}\nabla_{y}^{2}\mathcal{L}\left(\hat{y},\hat{\lambda},\hat{\nu},x\right)z>0$

for all $z\neq 0,z\in Z\left(\hat{y},x\right)$, where $\mathcal{L}$ is the
Lagrangian associated with $P(x)$, and $Z\left(\hat{y},x\right)$ is defined by

$Z\left(\hat{y},x\right)\triangleq\\{z\in\mathbb{R}^{d_{y}}:\nabla_{y}p_{j}\left(x,\hat{y}\right)z=0,\
\hat{\lambda}_{j}>0;\nabla_{y}q_{i}\left(x,\hat{y}\right)z=0,\ 1\leq i\leq
n\\}.$

######  Theorem 4 ((Fiacco 1983; Giorgi and Zuccotti 2018)).

Consider the problem $P\left(x^{0}\right)$. Suppose that Assumption 1 holds.
Suppose that $y^{0}\in K\left(x^{0}\right)$ and the KKT conditions hold at
$y^{0}$ with the Lagrangian multipliers $\lambda^{0},{\nu}^{0}$. Moreover,
suppose that the LICQ holds at $y^{0}$, the SCSC holds at $y^{0}$ w.r.t.
$\lambda^{0}$, and the SSOSC hold at $y^{0}$, with
$\left(\lambda^{0},{\nu}^{0}\right)$. Then,

  * (i)

$y^{0}$ is a locally unique local minimum of $P\left(x^{0}\right)$, i.e.,
there exists $\delta>0$ such that, for all $y\in\mathcal{B}(y^{0},\delta)$,
$y^{0}$ is the unique local minimum of $P\left(x^{0}\right)$. The associated
Lagrangian multipliers $\lambda^{0}$ and ${\nu}^{0}$ are unique.

  * (ii)

There exists $\epsilon>0$ such that, there exists a unique continuously
differentiable vector function

$z(x)\triangleq[y(x)^{\top},\lambda(x)^{\top},\nu(x)^{\top}]^{\top},$

which is defined on $\mathcal{B}(x^{0},\epsilon)$, and $y(x)$ is a locally
unique local minimum of $P(x)$. The KKT conditions hold at $y(x)$ with unique
associated Lagrangian multipliers $\lambda(x)$ and $\nu(x)$.

  * (iii)

The LICQ and the SCSC hold at $y(x)$ for $P(x)$ for all
$x\in\mathcal{B}(x^{0},\epsilon)$.

  * (iv)

The gradient of $z(x)$ is given as

$\left[\begin{array}[]{c}\nabla_{x}y(x^{0})\\\ \nabla_{x}\lambda(x^{0})\\\
\nabla_{x}\nu(x^{0})\end{array}\right]=-M(x^{0},y^{0},\lambda^{0},{\nu}^{0})^{-1}N(x^{0},y^{0},\lambda^{0},{\nu}^{0}),$

where

$M\triangleq\left[\begin{array}[]{ccccccc}\nabla_{y}^{2}\mathcal{L}&\left(\nabla_{y}p_{1}\right)^{\top}&\cdots&\left(\nabla_{y}p_{m}\right)^{\top}&\left(\nabla_{y}q\right)^{\top}\\\
\lambda_{1}\nabla_{y}p_{1}&p_{1}&\cdots&0&0\\\
\vdots&\vdots&\ddots&0&\vdots\\\
\lambda_{m}\nabla_{y}p_{m}&0&\cdots&p_{m}&0\\\
\nabla_{y}q&0&0&0&0\end{array}\right]$

with $M(x^{0},y^{0})$ being nonsingular and

$N\triangleq\left[\nabla_{xy}^{2}\mathcal{L}^{\top},\lambda_{1}\left(\nabla_{x}p_{1}\right)^{\top},\cdots,\lambda_{m}\left(\nabla_{x}p_{m}\right)^{\top},\nabla_{x}q^{\top}\right]^{\top}.$

######  Remark 4.

If the lower-level optimization problem $P(x^{0})$ is unconstrained, the
requirements in Theorem 4 reduce to that
$\nabla_{y}^{2}g\left({y}^{0},x^{0}\right)$ is positive definite.

######  Theorem 5 ((Giorgi and Zuccotti 2018; Kojima 1980)).

Suppose that all requirements except the SCSC in Theorem 4 are satisfied at
$(y^{0},\lambda^{0},{\nu}^{0})$ for $P\left(x^{0}\right)$. Then,

  * (i)

$y^{0}$ is a locally unique local minimum of $P\left(x^{0}\right)$. The
associated Lagrangian multipliers $\lambda^{0}$ and ${\nu}^{0}$ are unique.

  * (ii)

There exists $\epsilon>0$ such that, there exists a unique Lipschitz
continuous and once directional differentiable vector function

$z(x)\triangleq[y(x)^{\top},\lambda(x)^{\top},\nu(x)^{\top}]^{\top},$

which is defined on $\mathcal{B}(x^{0},\epsilon)$, and $y(x)$ is the locally
unique local minimum of $P(x)$ with unique associated Lagrangian multipliers
$\lambda(x)$ and $\nu(x)$.

  * (iii)

The LICQ hold at $y(x)$ for $P(x)$ for all $x\in\mathcal{B}(x^{0},\epsilon)$.

######  Lemma 1.

Suppose that all requirements except the SCSC in Theorem 4 hold at
$(y^{0},\lambda^{0},{\nu}^{0})$ for $P\left(x^{0}\right)$ (All requirements in
Theorem 5 are satisfied). Let $y(x)$ be the locally unique local minimum of
$P(x)$ shown in Theorem 5. Then,

  * (i)

There exists $\beta>0$, such that for all $x\in\mathcal{B}(x^{0},\beta)$,
$p_{j}\left(x,y(x)\right)<0$ for all $j\not\in J(x^{0},y^{0})$.

  * (ii)

There exists $\xi>0$ and $\delta>0$, such that for all
$x^{\prime}\in\mathcal{B}(x^{0},\xi)$ and
$y^{\prime}\in\mathcal{B}(y(x^{\prime}),\delta)$,
$p_{j}\left(x^{\prime},y^{\prime}\right)<0$ for all $j\not\in J(x^{0},y^{0})$.

###### Proof.

(i) For any $j\not\in J(x^{0},y^{0})$, we have
$p_{j}\left(x^{0},y^{0}\right)<0$. Then, there exists $\epsilon_{1}>0$ such
that $p_{j}\left(x^{0},y^{0}\right)\leq-\epsilon_{1}$. Since the function
$p_{j}$ is continuous at $(x^{0},y^{0})$ and $y$ is continuous at $x^{0}$, we
have that $p_{j}(x,y(x))$ is continuous at $x^{0}$. Then, there exists
$\beta_{1}>0$ such that, for all $x\in\mathcal{B}(x^{0},\beta_{1})$, we have
$|p_{j}\left(x,y(x)\right)-p_{j}\left(x^{0},y^{0}\right)|\leq\frac{1}{2}\epsilon_{1}$,
and then $p_{j}\left(x,y(x)\right)\leq-\frac{1}{2}\epsilon_{1}$. By selecting
the smallest $\beta_{1}$ over all $j\not\in J(x^{0},y^{0})$ as $\beta$, (i) is
shown.

(ii) Since $p_{j}$ is continuous at $(x^{0},y^{0})$, there exists
$\delta_{1}>0$ such that, for all
$(x^{\prime},y^{\prime})\in\mathcal{B}((x^{0},y^{0}),\delta_{1})$,
$|p_{j}\left(x^{\prime},y^{\prime}\right)-p_{j}\left(x^{0},y^{0}\right)|\leq\frac{1}{2}\epsilon_{1}$.
Since $y(x)$ is continuous at $x^{0}$, there exists $\xi_{1}>0$, for all
$x\in\mathcal{B}(x^{0},\xi_{1})$, $\|y(x)-y(x^{0})\|<\delta_{1}/4$. Let
$\xi_{2}=\min\\{\delta_{1}/4,\xi_{1}\\}$. Then, for all
$x^{\prime}\in\mathcal{B}(x^{0},\xi_{2})$ and
$y^{\prime}\in\mathcal{B}(y(x^{\prime}),\delta_{1}/2)$,
$\|(x^{\prime},y^{\prime})-(x_{0},y_{0})\|<\delta_{1}$. Then
$|p_{j}\left(x^{\prime},y^{\prime}\right)-p_{j}\left(x^{0},y^{0}\right)|\leq\frac{1}{2}\epsilon_{1}$,
and $p_{j}\left(x^{\prime},y^{\prime}\right)\leq-\frac{1}{2}\epsilon_{1}$.

By selecting the smallest $\xi_{2}$ over all $j\not\in J(x^{0},y^{0})$ as
$\xi$ and selecting the smallest $\delta_{1}/2$ over all $j\not\in
J(x^{0},y^{0})$ as $\delta$, we have that, for all
$x^{\prime}\in\mathcal{B}(x^{0},\xi)$, we can find $\delta>0$ such that, when
${||y^{\prime}-y(x)||}\leq\delta$,
$p_{j}\left(x,y^{\prime}\right)\leq-\frac{1}{2}\epsilon_{1}$ for all $j\not\in
J(x^{0},y^{0})$. ∎

######  Remark 5.

Lemma 1 shows that the inactive constraints at $(x^{0},y^{0})$ are still
inactive near $(x^{0},y^{0})$.

######  Lemma 2.

Suppose that all requirements in Theorem 4 hold at
$(y^{0},\lambda^{0},{\nu}^{0})$ for $P\left(x^{0}\right)$. Define problem
$\hat{P}\left(x\right)$ as:

$\displaystyle\underset{y}{\arg\min}$ $\displaystyle\ g(x,y):$ s.t.
$\displaystyle p_{j}\left(x,y\right)\leq 0,j\in J(x^{0},y^{0}),$
$\displaystyle q\left(x,y\right)=0.$

Then, the following properties hold:

  * (i)

All requirements and all conclusions in Theorem 4 hold at
$(y^{0},{\lambda}^{0},{\nu}^{0})$ for ${P}\left(x^{0}\right)$, and also hold
at $(y^{0},{\lambda}^{0}_{J(x^{0},y^{0})},{\nu}^{0})$ for
$\hat{P}\left(x^{0}\right)$.

Let
${z}(x)\triangleq[{y}(x)^{\top},{\lambda}(x)^{\top},{\nu}(x)^{\top}]^{\top}$
be the unique continuously differentiable vector function in a neighborhood of
$x^{0}$, such that $y(x)$ is a locally unique local minimum of $P(x)$ with
unique associated Lagrangian multipliers $\lambda(x)$ and $\nu(x)$. Let
$\hat{z}(x)\triangleq[\hat{y}(x)^{\top},\hat{\lambda}(x)^{\top},\hat{\nu}(x)^{\top}]^{\top}$
be the unique continuously differentiable vector function in a neighborhood of
$x^{0}$, such that $\hat{y}(x)$ is a locally unique local minimum of
$\hat{P}(x)$ with unique associated Lagrangian multipliers $\hat{\lambda}(x)$
and $\hat{\nu}(x)$.

  * (ii)

We have

$\displaystyle\nabla_{x}y(x^{0})=\nabla_{x}\hat{y}(x^{0}),$
$\displaystyle\nabla_{x}{\nu}(x^{0})=\nabla_{x}\hat{\nu}(x^{0}),$
$\displaystyle\nabla_{x}\lambda_{j}(x^{0})=\nabla_{x}\hat{\lambda}_{j}(x^{0})\text{
when }j\in J(x^{0},y^{0}),$ $\displaystyle\nabla_{x}\lambda_{j}(x^{0})=0\text{
when }j\not\in J(x^{0},y^{0}).$

###### Proof.

(i) Problem $\hat{P}\left(x^{0}\right)$ holds a same objective function and
same equality constraints as problem $P\left(x^{0}\right)$. The inequality
constraints of $P\left(x^{0}\right)$ are those of $P\left(x^{0}\right)$
removing the inactive constraint. The LICQ, the SCSC, the SSOSC and the KKT
conditions hold at $(y^{0},{\lambda}^{0},{\nu}^{0})$ for
${P}\left(x^{0}\right)$. Then, it is easy to justify that the LICQ, the SCSC
hold at $(y^{0},{\lambda}^{0}_{J(x^{0},y^{0})},{\nu}^{0})$ for
$\hat{P}\left(x^{0}\right)$. By the KKT conditions at
$(y^{0},{\lambda}^{0},{\nu}^{0})$ for ${P}\left(x^{0}\right)$, we have
$\lambda_{j}=0$ for $j\not\in J(x^{0},y^{0})$, i.e.,
$p_{j}\left(x^{0},y^{0}\right)<0$. Then, the SSOSC and the KKT conditions hold
at $(y^{0},{\lambda}^{0}_{J(x^{0},y^{0})},{\nu}^{0})$ for
$\hat{P}\left(x^{0}\right)$. By Theorem 4, (i) holds. Then $y^{0}$ is a
locally unique local minimum of $\hat{P}\left(x^{0}\right)$, and there exists
$\hat{z}(x)=[\hat{y}(x)^{\top},\hat{\lambda}(x)^{\top},\hat{\nu}(x)^{\top}]^{\top}$
being the unique continuously differentiable vector function in a neighborhood
of $x^{0}$, such that $\hat{y}(x)$ is a locally unique local minimum of
$\hat{P}(x)$ with unique Lagrangian multipliers $\hat{\lambda}(x)$ and
$\hat{\nu}(x)$.

(ii) All conclusions in Theorem 4 hold at $(y^{0},{\lambda}^{0},{\nu}^{0})$
for ${P}\left(x^{0}\right)$, then there exists
${z}(x)=[{y}(x)^{\top},{\lambda}(x)^{\top},{\nu}(x)^{\top}]^{\top}$ be the
unique continuously differentiable vector function in a neighborhood of
$x^{0}$, such that $y(x)$ is a locally unique local minimum of $P(x)$ with
unique Lagrangian multipliers $\lambda(x)$ and $\nu(x)$. Next, we will show
that, in a neighborhood of $x^{0}$,

$\displaystyle y(x)=\hat{y}(x),$ $\displaystyle{\nu}(x)=\hat{\nu}(x),$
$\displaystyle\lambda_{j}(x)=\hat{\lambda}_{j}(x)\text{ when }j\in
J(x^{0},y^{0}),$ $\displaystyle\lambda_{j}(x)=0\text{ when }j\not\in
J(x^{0},y^{0}).$

Since $y(x)$ is a locally unique local minimum of $P(x)$, then there exists
$\beta_{3}>0$, for any ${||x-x^{0}||}\leq\beta_{3}$, $y(x)$ is a local minimum
of $P\left(x\right)$, i.e., there exists $\delta_{3}>0$ such that
$g(x,y(x))\leq g(x,y^{\prime})$, when ${||y^{\prime}-y(x)||}\leq\delta_{3}$,
$p\left(x,y^{\prime}\right)\leq 0$, and $q\left(x,y^{\prime}\right)=0$. Let
$\beta_{2}$ be the $\xi$ and $\delta_{3}$ be the $\delta$ shown in Lemma 1.
Let $\beta_{4}=\min{\\{\beta_{2},\beta_{3}\\}}$ and
$\delta_{4}=\min{\\{\delta_{2},\delta_{3}\\}}$. Then, for all
${||x-x^{0}||}\leq\beta_{4}$, we have $\delta_{4}$, such that the following
two statements are satisfied:

  * (a)

$g(x,y(x))\leq g(x,y^{\prime})$ when ${||y^{\prime}-y(x)||}\leq\delta_{4}$,
$p\left(x,y^{\prime}\right)\leq 0$, and $q\left(x,y^{\prime}\right)=0$.

  * (b)

$p_{j}\left(x,y^{\prime}\right)\leq-\frac{1}{2}\epsilon_{1}<0$ for all
$j\not\in J(x^{0},y^{0})$ when ${||y^{\prime}-y(x)||}\leq\delta_{4}$.

The statement (b) show that set
$\\{y^{\prime}:{||y^{\prime}-y(x)||}\leq\delta_{4}\\}\subset$
$\\{y^{\prime}:p_{j}\left(x,y^{\prime}\right)\leq-\frac{1}{2}\epsilon_{1}<0\text{
for all }j\not\in J(x^{0},y^{0})\\}$. Then, $g(x,y(x))\leq g(x,y^{\prime})$
when ${||y^{\prime}-y(x)||}\leq\delta_{4}$, $q\left(x,y^{\prime}\right)=0$,
and $p\left(x,y^{\prime}\right)\leq 0$, $j\in J(x^{0},y^{0})$. This means
$y(x)$ is a local minimum of $\hat{P}\left(x\right)$ for all
${||x-x^{0}||}\leq\beta_{4}$.

For ${||x-x^{0}||}\leq\beta_{4}$, $y(x)$ is a locally unique local minimum of
${P}\left(x\right)$. Assume that $y(x)$ is not a locally unique local minimum
of $\hat{P}\left(x\right)$, i.e., for any $\phi>0$, there exists
${||y^{\prime}(\phi)-y(x)||}\leq\phi$ such that $y^{\prime}$ is a local
minimum of $\hat{P}\left(x\right)$. We can set $0<\phi<\delta_{4}$, then
$p_{j}(x,y^{\prime}(\phi))<0$ for all $j\not\in J(x^{0},y^{0})$. Then for any
$\phi$, $y^{\prime}(\phi)$ is a local minimum of ${P}\left(x\right)$, which
contradicts that $y(x)$ is a locally unique local minimum of
${P}\left(x\right)$. Thus, $y(x)$ is a locally unique local minimum of
$\hat{P}\left(x\right)$. Let
$z_{1}(x)\triangleq[{y}(x)^{\top},{\lambda}^{\prime}(x)^{\top},{\nu}(x)^{\top}]^{\top}$
defined on $\\{x:{||x-x^{0}||}\leq\beta_{4}\\}$, where
${\lambda}^{\prime}(x)^{\top}$ is a vector function which contains all
$\lambda_{j}(x)$ when $j\in J(x^{0},y^{0})$. Then $z_{1}(x)$ is a continuously
differentiable vector function, and it is easy to justify that the KKT
conditions hold at $y(x)$ with Lagrangian multipliers $\lambda^{\prime}(x)$
and $\nu(x)$ for $\hat{P}(x)$.

Since
$\hat{z}(x)=[\hat{y}(x)^{\top},\hat{\lambda}(x)^{\top},\hat{\nu}(x)^{\top}]^{\top}$
is the unique continuously differentiable vector function in a neighborhood of
$x^{0}$, such that $\hat{y}(x)$ is a locally unique local minimum of
$\hat{P}(x)$. Then for ${||x-x^{0}||}\leq\beta_{4}$, we have
$\hat{z}(x)=z_{1}(x)$ and

$\displaystyle y(x)=\hat{y}(x),$ $\displaystyle{\nu}(x)=\hat{\nu}(x),$
$\displaystyle\lambda_{j}(x)=\hat{\lambda}_{j}(x)\text{ when }j\in
J(x^{0},y^{0}).$

Since $p_{j}\left(x,y(x)\right)<0$ when $j\not\in J(x^{0},y^{0})$, then
$\lambda_{j}(x)=0$ by the KKT conditions. Then,

$\displaystyle\nabla_{x}y(x^{0})=\nabla_{x}\hat{y}(x^{0}),$
$\displaystyle\nabla_{x}{\nu}(x^{0})=\nabla_{x}\hat{\nu}(x^{0}),$
$\displaystyle\nabla_{x}\lambda_{j}(x^{0})=\nabla_{x}\hat{\lambda}_{j}(x^{0})\text{
when }j\in J(x^{0},y^{0}),$ $\displaystyle\nabla_{x}\lambda_{j}(x^{0})=0\text{
when }j\not\in J(x^{0},y^{0}).$

∎

Note that the SCSC holds at $\hat{y}$ w.r.t. $\hat{\lambda}$ for $P(x)$ is
equivalent to $J^{0}(x,\hat{y})=\emptyset$, then
$J\left(x,\hat{y}\right)=J^{+}\left(x,\hat{y}\right)$. We define the matrix
functions

$M_{+}(x^{0},y^{0})\triangleq\left[\begin{array}[]{ccccccc}\nabla_{y}^{2}\mathcal{L}&\nabla_{y}p_{J^{+}(x^{0},y^{0})}^{\top}&\nabla_{y}q^{\top}\\\
\nabla_{y}p_{J^{+}(x^{0},y^{0})}&0&0\\\
\nabla_{y}q&0&0\end{array}\right](x^{0},y^{0},\lambda^{0},{\nu}^{0}),$

and

$N_{+}(x^{0},y^{0})\triangleq[\nabla_{xy}^{2}\mathcal{L}^{\top},\nabla_{x}p_{J^{+}(x^{0},y^{0})}^{\top},\nabla_{x}q^{\top}]^{\top}(x^{0},y^{0},\lambda^{0},{\nu}^{0}).$

Compute the gradient of $\hat{z}(x)$ as shown in Theorem 4. Since
$\lambda_{j}>0$ for all $j\in J^{+}(x^{0},y^{0})$, we can cancel all
$\lambda_{j}$ in $M$ and $N$. Then we can get

$\left[\begin{array}[]{c}\nabla_{x}\hat{y}(x^{0})\\\
\nabla_{x}\hat{\lambda}(x^{0})\\\ \nabla_{x}\hat{\nu}(x^{0})\\\
\end{array}\right]=-{M}_{+}^{-1}(x^{0},y^{0}){N}_{+}(x^{0},y^{0}).$

By Lemma 2, the gradient of ${z}(x)$ is computed as:

$\begin{array}[]{c}\left[\begin{array}[]{c}\nabla_{x}y(x^{0})\\\
\nabla_{x}\lambda_{J(x^{0},y^{0})}(x^{0})\\\
\nabla_{x}\nu(x^{0})\end{array}\right]=-M_{+}(x^{0},y^{0})^{-1}N_{+}(x^{0},y^{0}),\\\
\nabla_{x}\lambda_{{J(x^{0},y^{0})}^{C}}(x^{0})=0.\end{array}$ (16)

######  Lemma 3.

Suppose that all requirements except the SCSC in Theorem 4 are satisfied at
$(y^{0},\lambda^{0},{\nu}^{0})$ for $P\left(x^{0}\right)$. Then,

  * (i)

$y^{0}$ is a locally unique local minimum of $P\left(x^{0}\right)$.

  * (ii)

There exists $\epsilon>0$ such that, there exists a unique Lipschitz
continuous vector function

$z(x)\triangleq[y(x)^{\top},\lambda(x)^{\top},\nu(x)^{\top}]^{\top},$

which is defined on $\mathcal{B}(x^{0},\epsilon)$, and $y(x)$ is the locally
unique local minimum of $P(x)$ with unique associated Lagrangian multipliers
$\lambda(x)$ and $\nu(x)$.

For a direction $d\in\mathbb{R}^{d_{x}}$, define $J^{0}_{+}(x^{0},y^{0},d)$ as
set which contains all $j\in J^{0}(x^{0},y^{0})$ such that, there exists
${\epsilon}_{0}>0$, for any $0<{\epsilon}<{\epsilon}_{0}$,
$p_{j}(x^{0}+\epsilon d,y(x^{0}+\epsilon d))=0$ and
$\lambda_{j}(x^{0}+\epsilon d)>0$. Denote $J^{0}_{-}(x^{0},y^{0},d)\triangleq
J^{0}(x^{0},y^{0})\setminus J^{0}_{+}(x^{0},y^{0},d)$,

$M_{D}(x^{0},y^{0},d)\triangleq\left[\begin{array}[]{ccccccc}\nabla_{y}^{2}\mathcal{L}&\nabla_{y}p_{J^{+}(x^{0},y^{0})}^{\top}&\nabla_{y}q^{\top}&\nabla_{y}p^{\top}_{J^{0}_{+}(x^{0},y^{0},d)}\\\
\nabla_{y}p_{J^{+}(x^{0},y^{0})}&0&0&0\\\ \nabla_{y}q&0&0&0\\\
\nabla_{y}p_{J^{0}_{+}(x^{0},y^{0},d)}&0&0&0\end{array}\right](x^{0},y^{0},\lambda^{0},{\nu}^{0})$
(17)

and

$N_{D}(x^{0},y^{0},d)\triangleq\left[\nabla_{xy}^{2}\mathcal{L}^{\top},\nabla_{x}p_{J^{+}(x^{0},y^{0})}^{\top},\nabla_{x}q^{\top},\nabla_{x}p_{J^{0}_{+}(x^{0},y^{0},d)}^{\top}\right]^{\top}(x^{0},y^{0},\lambda^{0},{\nu}^{0}).$
(18)

  * (iii)

The directional derivative of $z(x)$ at $x^{0}$ on any direction
$d\in\mathbb{R}^{d_{x}}$ with $\|d\|=1$ exists and given by

$\begin{array}[]{c}\left[\begin{array}[]{c}\nabla_{d}{y}(x^{0})\\\
\nabla_{d}\lambda_{J^{+}(x^{0},y^{0})}(x^{0})\\\ \nabla_{d}{\nu}(x^{0})\\\
\nabla_{d}{\lambda}_{J_{+}^{0}(x^{0},y^{0},d)}(x^{0})\\\
\end{array}\right]=-M_{D}^{-1}(x^{0},y^{0},d)N_{D}(x^{0},y^{0},d)d,\\\
\nabla_{d}{\lambda}_{J_{-}^{0}(x^{0},y^{0},d)}(x^{0})=0,\\\
\nabla_{d}{\lambda}_{J(x^{0},y^{0})^{C}}(x^{0})=0,\end{array}$ (19)

where $M_{D}(x^{0},y^{0},d)$ is nonsingular.

###### Proof.

When the SCSC holds at $y^{0}$ w.r.t. $\lambda^{0}$, then we have
$J(x^{0},y^{0})=J^{+}(x^{0},y^{0})$. This theorem is equivalent to Lemma 2.
When the SCSC is not satisfied, $J^{0}(x^{0},y^{0})\neq\emptyset$.

(i) By part (i) of Theorem 5, the LICQ, the SSOSC and the KKT conditions hold
at $(y^{0},{\lambda}^{0},{\nu}^{0})$ for ${P}\left(x^{0}\right)$, (i) holds.

(ii) By part (ii) of Theorem 5, the LICQ, the SSOSC and the KKT conditions
hold at $(y^{0},{\lambda}^{0},{\nu}^{0})$ for ${P}\left(x^{0}\right)$, (ii)
holds and the directional derivative of $z(x)$ at $x^{0}$ on any direction
exists.

(iii) By (ii), the vector function
$z(x)\triangleq[y(x)^{\top},\lambda(x)^{\top},\nu(x)^{\top}]^{\top}$ defined
on $\mathcal{B}(x^{0},\epsilon)$ is the local solution of $P(x)$. By (iii) of
Theorem 5 the LICQ hold at $y(x)$ for $P(x)$ for all
$x\in\mathcal{B}(x^{0},\epsilon)$. Then, according to Theorem 3 in (Giorgi and
Zuccotti 2018),
$z(x)\triangleq[y(x)^{\top},\lambda(x)^{\top},\nu(x)^{\top}]^{\top}$ satisfies
the KKT conditions for problem $P(x)$ for any
$x\in\mathcal{B}(x^{0},\epsilon)$, and $\lambda(x),\nu(x)$ are unique
Lagrangian multipliers. The directional derivative of $z(x)$ at $x^{0}$ on any
direction exists.

(a) Consier $j\not\in J(x^{0},y^{0})$. From part (ii) of Lemma 1, we have
that, in a small neighborhood of $(x^{0},y^{0})$, $p_{j}\left(x,y\right)<0$
for all $j\not\in J(x^{0},y^{0})$, i.e., the inactive constraints at
$(x^{0},y^{0})$ are still inactive in a neighborhood of $(x^{0},y^{0})$. Then,
for $j\not\in J(x^{0},y^{0})$, there exists $\beta_{0}$ such that
$p_{j}(x^{0}+\beta d,y(x^{0}+\beta d))<0$ and $\lambda_{j}(x^{0}+\beta d)=0$
for all $\beta<\beta_{0}$. Then,
$\nabla_{d}{\lambda}_{J(x^{0},y^{0})^{C}}(x^{0})=0$.

(b) Consider $j\in J^{0}_{-}\left(x^{0},y^{0},d\right)$, i.e., there does not
exist ${\beta}_{0}>0$, for any ${\beta}<{\beta}_{0}$, $p_{j}(x^{0}+\beta
d,y(x^{0}+\beta d))=0$ and $\lambda_{j}(x^{0}+\beta d)>0$. There are two
possible cases for the direction $d$. The first case is that, there exists
${\beta}_{0}>0$, for any ${\beta}<{\beta}_{0}$, $p_{j}(x^{0}+\beta
d,y(x^{0}+\beta d))\leq 0$ and $\lambda_{j}(x^{0}+\beta d)=0$. The second case
is that, for any ${\beta}_{0}>0$, we can always find
${\beta},\beta_{1}<{\beta}_{0}$ such that, $p_{j}(x^{0}+\beta d,y(x^{0}+\beta
d))=0$, $\lambda_{j}(x^{0}+\beta d)>0$, and $p_{j}(x^{0}+\beta d,y(x^{0}+\beta
d))\leq 0$, $\lambda_{j}(x^{0}+\beta d)=0$. For the first case, we have
$\nabla_{d}{\lambda}_{J_{-}^{0}(x^{0},y^{0},d)}(x^{0})=0$. For the second
case, since the directional derivative of $y(x)$ and $\lambda(x)$ at $x^{0}$
on the direction exists, we have $\nabla_{\beta}p_{j}(x^{0}+\beta
d,y(x^{0}+\beta d))=0$ and
$\nabla_{d}{\lambda}_{J_{-}^{0}(x^{0},y^{0},d)}(x^{0})=0$. Thus, for $j\in
J^{0}_{-}\left(x^{0},y^{0},d\right)$,
$\nabla_{d}{\lambda}_{J_{-}^{0}(x^{0},y^{0},d)}(x^{0})=0$.

(c) Consider $j\in J^{+}(x^{0},y^{0})$, we have $\lambda^{0}_{j}>0$. When
$\beta$ is sufficiently small, we have $p_{j}(x^{0}+\beta d,y(x^{0}+\beta
d))=0$ and $\lambda_{j}(x^{0}+\beta d)>0$.

(d) Consider $j\in J^{0}_{+}\left(x^{0},y^{0},d\right)$, $p_{j}(x^{0}+\beta
d,y(x^{0}+\beta d))=0$ and $\lambda_{j}(x^{0}+\beta d)>0$.

(e) Consider the KKT conditions at $z(x)$, we have

$\left\\{\begin{array}[]{l}\nabla_{y}\mathcal{L}(y(x),\lambda(x),\nu(x),x)=0\\\
\lambda_{j}(x)p_{j}(y(x),x)=0,\ j=1,\ldots,m\\\ q_{j}(y(x),x)=0,\
j=1,\ldots,n\end{array}\right.$

for any $x\in\mathcal{B}(x^{0},\epsilon)$. Then, for any sufficiently small
$\beta<\epsilon$, we have

$\left\\{\begin{array}[]{l}\nabla_{y}\mathcal{L}(y(x^{0}),\lambda(x^{0}),\nu(x^{0}),x^{0})=0\\\
\lambda_{j}(x^{0})p_{j}(y(x^{0}),x^{0})=0,\ j=1,\ldots,m\\\
q_{j}(y(x^{0}),x^{0})=0,\ j=1,\ldots,n\end{array}\right.\text{ and
}\left\\{\begin{array}[]{l}\nabla_{y}\mathcal{L}(y(x^{0}+\beta
d),\lambda(x^{0}+\beta d),\nu(x^{0}+\beta d),x^{0}+\beta d)=0\\\
\lambda_{j}(x^{0}+\beta d)p_{j}(y(x^{0}+\beta d),x^{0}+\beta d)=0,\
j=1,\ldots,m\\\ q_{j}(y(x^{0}+\beta d),x^{0}+\beta d)=0,\
j=1,\ldots,n.\end{array}\right.$

Then, we have

$\left.\frac{\partial\nabla_{y}\mathcal{L}\left(y\left(x^{0}+\beta
d\right),\lambda\left(x^{0}+\beta d\right),\nu\left(x^{0}+\beta
d\right),x^{0}+\beta d\right)}{\partial\beta}\right|_{\beta=0}=0,$
$\left.\frac{\partial\lambda_{i}(x^{0}+\beta d)p_{j}(y(x^{0}+\beta
d),x^{0}+\beta d)}{\partial\beta}\right|_{\beta=0}=0,\ j=1,\ldots,m,$
$\left.\frac{\partial q_{j}(y(x^{0}+\beta d),x^{0}+\beta
d)}{\partial\beta}\right|_{\beta=0}=0,\ j=1,\ldots,n.$

Then, we get

$\left[\begin{array}[]{ccccc}\nabla_{y}^{2}\mathcal{L}&\left(\nabla_{y}p_{1}\right)^{\top}&\cdots&\left(\nabla_{y}p_{m}\right)^{\top}&\left(\nabla_{y}q\right)^{\top}\\\
\lambda_{1}\nabla_{y}p_{1}&p_{1}&\cdots&0&0\\\
\vdots&\vdots&\ddots&0&\vdots\\\
\lambda_{m}\nabla_{y}p_{m}&0&\cdots&p_{m}&0\\\
\nabla_{y}q&0&0&0&0\end{array}\right]\left[\begin{array}[]{c}\nabla_{d}y\\\
\nabla_{d}\lambda_{1}\\\ \vdots\\\ \nabla_{d}\lambda_{m}\\\
\nabla_{d}\nu\end{array}\right]+\left[\begin{array}[]{c}\nabla_{xy}^{2}\mathcal{L}\\\
\lambda_{1}\nabla_{x}p_{1}\\\ \vdots\\\ \lambda_{m}\nabla_{x}p_{m}\\\
\nabla_{x}q\end{array}\right]d=0.$

From (a)(b), we have $\nabla_{d}{\lambda}_{J(x^{0},y^{0})^{C}}(x^{0})=0$ and
$\nabla_{d}{\lambda}_{J_{-}^{0}(x^{0},y^{0},d)}(x^{0})=0$. Then, the equation
is reduced to

$\displaystyle\left[\begin{array}[]{ccccc}\nabla_{y}^{2}\mathcal{L}&\nabla_{y}p_{J^{+}(x^{0},y^{0})}^{\top}&\nabla_{y}p_{J^{0}_{+}(x^{0},y^{0},d)}^{\top}&\nabla_{y}q^{\top}\\\
\lambda_{J^{+}(x^{0},y^{0})}\nabla_{y}p_{J^{+}(x^{0},y^{0})}&p_{J^{+}(x^{0},y^{0})}&0&0\\\
{\lambda}_{J_{+}^{0}(x^{0},y^{0},d)}\nabla_{y}p_{J^{0}_{+}(x^{0},y^{0},d)}&0&p_{J^{0}_{+}(x^{0},y^{0},d)}&0\\\
\nabla_{y}q&0&0&0\end{array}\right]\left[\begin{array}[]{c}\nabla_{d}y\\\
\nabla_{d}\lambda_{J^{+}(x^{0},y^{0})}\\\
\nabla_{d}{\lambda}_{J_{+}^{0}(x^{0},y^{0},d)}\\\
\nabla_{d}\nu\end{array}\right]$
$\displaystyle+\left[\begin{array}[]{c}\nabla_{xy}^{2}\mathcal{L}\\\
\lambda_{J^{+}(x^{0},y^{0})}\nabla_{x}p_{J^{+}(x^{0},y^{0})}\\\
{\lambda}_{J_{+}^{0}(x^{0},y^{0},d)}\nabla_{x}p_{J^{0}_{+}(x^{0},y^{0},d)}\\\
\nabla_{x}q\end{array}\right]d=0.$

From (c)(d), $p_{J^{+}(x^{0},y^{0})}=0$, $p_{J^{0}_{+}(x^{0},y^{0},d)}=0$,
$\lambda_{J^{+}(x^{0},y^{0})}>0$, and
${\lambda}_{J_{+}^{0}(x^{0},y^{0},d)}>0$. Then, $\lambda_{J^{+}(x^{0},y^{0})}$
and ${\lambda}_{J_{+}^{0}(x^{0},y^{0},d)}$ are cancelled. We have

$\begin{array}[]{c}\left[\begin{array}[]{c}\nabla_{d}{y}(x^{0})\\\
\nabla_{d}\lambda_{J^{+}(x^{0},y^{0})}(x^{0})\\\ \nabla_{d}{\nu}(x^{0})\\\
\nabla_{d}{\lambda}_{J_{+}^{0}(x^{0},y^{0},d)}(x^{0})\\\
\end{array}\right]=-M_{D}^{-1}(x^{0},y^{0},d)N_{D}(x^{0},y^{0},d)d\end{array}$

where $M_{D}(x^{0},y^{0},d)$ and $N_{D}(x^{0},y^{0},d)$ is defined in (17) and
(18). Since the LICQ holds, $M_{D}(x^{0},y^{0},d)$ is nonsingular.

∎

Consider Assumptions 1, 2, 3 are satisfied, $y^{*}(x)$ is the optimal solution
of $P(x)$. Define the matrix functions

$M_{+}(x)\triangleq\left[\begin{array}[]{ccccccc}\nabla_{y}^{2}\mathcal{L}&\nabla_{y}p_{J^{+}(x,y^{*}(x))}^{\top}&\nabla_{y}q^{\top}\\\
\nabla_{y}p_{J^{+}(x,y^{*}(x))}&0&0\\\
\nabla_{y}q&0&0\end{array}\right](x,y^{*}(x),\lambda(x),\nu(x))$

and

$N_{+}(x)\triangleq=[\nabla_{xy}^{2}\mathcal{L}^{\top},\nabla_{x}p_{J^{+}(x,y^{*}(x))}^{\top},\nabla_{x}q^{\top}]^{\top}(x,y^{*}(x)).$

For a direction $d\in\mathbb{R}^{d_{x}}$, define $J^{0}_{+}(x,y^{*}(x),d)$ as
set which contains all $j\in J^{0}(x,y^{*}(x))$ such that, there exists
${\epsilon}_{0}>0$, for any $0<{\epsilon}<{\epsilon}_{0}$, $p_{j}(x+\epsilon
d,y^{*}(x+\epsilon d))=0$ and $\lambda_{j}(x+\epsilon d)>0$. Denote
$J^{0}_{-}(x,y^{*}(x),d)\triangleq J^{0}(x,y^{*}(x))\setminus
J^{0}_{+}(x,y^{*}(x),d)$. Define

$M_{D}(x,d)\triangleq\left[\begin{array}[]{ccc}M_{+}&\begin{array}[]{ccc}\nabla_{y}p^{\top}_{J^{0}_{+}(x,y^{*}(x),d)}\\\
0\\\ 0\\\ \end{array}\\\
\begin{array}[]{ccc}\nabla_{y}p_{J^{0}_{+}(x,y^{*}(x),d)}&0&0\\\
\end{array}&0\\\ \end{array}\right](x,y^{*}(x))$

and

$N_{D}(x,d)\triangleq\left[N_{+}^{\top}(x),\nabla_{x}p_{J^{0}_{+}(x,y^{*}(x),d)}^{\top}(x,y^{*}(x))\right]^{\top}.$

######  Theorem 6 (Full version of the combination of Theorems 1 and 2).

Suppose Assumptions 1, 2, 3 hold. Then,

  * (i)

The global minimum $y^{*}(x)$ of $P\left(x\right)$ exists and is unique. The
KKT conditions hold at $y^{*}(x)$ with unique Lagrangian multipliers
$\lambda(x)$ and $\nu(x)$.

  * (ii)

The vector function $z(x)\triangleq[y^{*}(x),\lambda(x),\nu(x)]$ is continuous
and locally Lipschitz.

  * (iii)

The directional derivative of $z$ at $x$ on any direction
$d\in\mathbb{R}^{d_{x}}$ with $\|d\|=1$ exists and given by

$\begin{array}[]{c}\left[\begin{array}[]{c}\nabla_{d}{y}^{*}(x)\\\
\nabla_{d}\lambda_{J^{+}(x,y^{*}(x))}(x)\\\ \nabla_{d}{\nu}(x)\\\
\nabla_{d}{\lambda}_{J_{+}^{0}(x,y^{*}(x),d)}(x)\end{array}\right]=-M_{D}^{-1}(x,d)N_{D}(x,d)d,\\\
\nabla_{d}{\lambda}_{J_{-}^{0}(x,y^{*}(x),d)}(x)=0,\\\
\nabla_{d}{\lambda}_{J(x,y^{*}(x))^{C}}(x)=0,\end{array}$ (20)

where $M_{D}(x,d)$ is nonsingular.

  * (iv)

If the SCSC holds at $y^{*}(x)$ w.r.t. $\lambda(x)$, ${z}$ is continuously
differentiable at $x$ and the gradient is computed by

$\left[\begin{array}[]{c}\nabla_{x}y^{*}(x)\\\
\nabla_{x}\lambda_{J(x,y^{*}(x))}(x)\\\
\nabla_{x}\nu(x)\end{array}\right]=-M_{+}^{-1}(x)N_{+}(x),$
$\nabla_{x}{\lambda}_{J(x,y^{*}(x))^{C}}(x)=0,$

where ${M}_{+}(x)$ is nonsingular.

###### Proof.

(i) Firstly, we show $y^{*}(x)$ exists and is unique. Function $g(x,y)$ is
$\mu$-strongly-convex w.r.t. $y$, and the feasible set $K\left(x\right)$ is
convex and closed for all ${x}\in\mathbb{R}^{d_{x}}$. Case one: $K(x)$ is
bounded. Then, $K(x)$ is a compact set and $g(x,y)$ is continuous, which imply
that the minimum $y^{*}(x)$ exists. Case two: $K(x)$ is not bounded. Function
$g(x,y)$ is $\mu$-strongly-convex w.r.t. $y$, then

$g(x,y)\geq
g(x,y^{0})+\nabla_{y}g(x,y^{0})^{\top}(y-y^{0})+\frac{\mu}{2}\|y-y^{0}\|^{2}.$

Then, $\lim_{\|y\|\rightarrow\infty}g(x,y)=+\infty$. Then, for any real number
$\alpha$, the set $\\{x\mid g(x,y)\leq\alpha\\}$ is closed and bounded, and
there exists $\alpha$ such that $\\{y\mid g(x,y)\leq\alpha\\}$ is not empty.
Then, $\\{x\mid g(x,y)\leq\alpha\\}$ is compact. Then, the compactness of
$\\{y\mid g(x,y)\leq\alpha\\}$ and the continuity of $g(x,y)$ imply that, the
optimization problem $\min g(x,y)\text{ s.t. }y\in\\{t\mid
g(x,t)\leq\alpha\\}$ is feasible and has a minimum, which is also the minimum
of problem $P(x)$. Thus, the global minimum $y^{*}(x)$ exists.

The solution $y^{*}(x)$ is a global minimum of $P(x)$ implies it is a local
minimum. Assume $y^{*}(x)$ is not the unique local minimum of $P(x)$ and there
exists $y^{\prime}\in K(x)$ is also a local minimum, then there exists a
$0<\alpha<1$ such that $g(x,y^{*}(x))\leq g(x,\alpha
y^{*}(x)+(1-\alpha)y^{\prime})$ and $g(x,y^{\prime}\leq g(x,\alpha
y^{*}(x)+(1-\alpha)y^{\prime})$, then $\alpha
g(x,y^{*}(x))+(1-\alpha)g(x,y^{\prime})\leq g(x,\alpha
y^{*}(x)+(1-\alpha)y^{\prime})$, which contradicts that $g(x,y)$ is
$\mu$-strongly-convex w.r.t. $y$. Thus, $y^{*}(x)$ is the unique local
minimum, and then it is the unique global minimum.

The solution $y^{*}(x)$ is a global minimum of $P(x)$ implies that $y^{*}(x)$
is a local minimum. By Assumptions 3, the LICQ holds at $y^{*}(x)$ for $P(x)$.
Then, the KKT conditions hold at $y^{*}(x)$ with unique Lagrangian multipliers
$\lambda(x)$ and $\nu(x)$ for $P(x)$ by (i) of Theorem 5.

(ii)(iii) Firstly show that, for all ${x}\in\mathbb{R}^{d_{x}}$, the SSOSC
holds at ${y}^{*}(x)$ with Lagrangian multipliers $\lambda(x)$ and $\nu(x)$
for $P(x)$. By Assumption 2, $g(x,y)$ is $\mu$-strongly-convex w.r.t. $y$,
which implies that $\nabla_{y}^{2}g(x,{y}^{*}(x))$ is positive definite;
$p_{j}(x,y)$ is convex implies that $\nabla_{y}^{2}p_{j}(x,{y}^{*}(x))$ is
positive semi-definite; $q_{j}(x,y)$ is affine implies
$\nabla_{y}^{2}q(x,{y}^{*}(x))=0$. The KKT condition in (i) implies that
$\lambda(x)\geq 0$. Then,

$\nabla_{y}^{2}\mathcal{L}\left({y}^{*}(x),{\lambda}(x),\hat{\nu}(x),x\right)=\nabla_{y}^{2}g(x,{y}^{*}(x))+\lambda(x)^{\top}\nabla_{y}^{2}p(x,{y}^{*}(x))+\nu(x)^{\top}\nabla_{y}^{2}q(x,{y}^{*}(x))$

is positive definite. Therefore, the SSOSC holds.

The KKT conditions, the LICQ, and the SSOSC hold at ${y}^{*}(x)$ with
Lagrangian multipliers $\lambda(x)$ and $\nu(x)$ for $P(x)$. By Lemma 3, for
all ${x}^{0}\in\mathbb{R}^{d_{x}}$, in a neighborhood of ${x}^{0}$, there
exists a unique Lipschitz continuous vector function
$\hat{z}(x)\triangleq[\hat{y}^{\top}(x),\hat{\lambda}^{\top}(x),\hat{\nu}^{\top}(x)]^{\top}$
and $\hat{y}(x)$ is a locally unique local minimum of $P(x)$. Then the local
minimum $y^{*}(x)$ with unique Lagrangian multipliers $\lambda(x)$ and
$\nu(x)$ for $P(x)$ is unique implies that $\hat{z}(x)=z(x)$.

For any $x^{0}\in\mathbb{R}^{d_{x}}$, the vector function
$z(x)\triangleq[y^{*}(x)^{\top},\lambda(x)^{\top},\nu(x)^{\top}]^{\top}$ is
Lipschitz in a neighborhood of $x^{0}$ implies that, $z(x)$ is locally
Lipschitz on $\mathbb{R}^{d_{x}}$. The computation of gradient is given in
Lemma 3.

(iv) The KKT conditions, the LICQ, and the SSOSC hold at ${y}^{*}(x)$ with
Lagrangian multipliers $\lambda(x)$ and $\nu(x)$ for $P(x)$. By Lemma 2, the
SCSC holds at $y^{*}(x^{0})$ w.r.t. $\lambda(x^{0})$ implies that, for all
${x}^{0}\in\mathbb{R}^{d_{x}}$, in a neighborhood of ${x}^{0}$, there exists a
unique continuously differentiable vector function
$\hat{z}(x)\triangleq[\hat{y}^{\top}(x),\hat{\lambda}^{\top}(x),\hat{\nu}^{\top}(x)]^{\top}$
and $\hat{y}(x)$ is a locally unique local minimum of $P(x)$. Then the local
minimum $y^{*}(x)$ with unique Lagrangian multipliers $\lambda(x)$ and
$\nu(x)$ for $P(x)$ is unique implies that $\hat{z}(x)=z(x)$. The computation
of gradient is given in Lemma 2.

∎

For a constrained lower-level optimization $P(x)$, for each direction $d$,
paper (Ralph and Dempe 1995) computes $\nabla_{d}y^{*}(x)$ by solving a
quadratic programming problem. In Theorem 6, we compute $\nabla_{d}y^{*}(x)$
by (20) and the set $J^{0}_{+}(x,y^{*}(x),d)$ can be determined by sampling
${\epsilon}_{0}$ in a small neighborhood.

###  C.2 Proofs of Propositions 1 and 2

The following lemma provides a way to compute Clarke subdifferential of
$y^{*}$ without the SCSC.

######  Lemma 4.

Suppose all assumptions in Theorem 2 hold. Then,

$\bar{\partial}y^{*}\left(x^{0}\right)=\operatorname{conv}\left\\{{w}^{S}(x^{0}):S\subseteq
J^{0}(x^{0},y^{*}(x^{0}))\right\\}.$ (21)

Here, ${w}^{S}(x^{0})$ is obtained by extracting the first $d_{x}$ rows from
matrix $-M^{S}_{+}(x^{0},y^{*}(x^{0}))^{-1}N^{S}_{+}(x^{0},y^{*}(x^{0}))$.
When $S$ is not empty,

$M^{S}_{+}(x,y)\triangleq\left[\begin{array}[]{ccccccc}\nabla_{y}^{2}\mathcal{L}&\nabla_{y}p_{J^{+}(x^{0},y^{*}(x^{0}))}^{\top}&\nabla_{y}q^{\top}&\nabla_{y}p_{S}^{\top}\\\
\nabla_{y}p_{J^{+}(x^{0},y^{*}(x^{0}))}&0&0&0\\\ \nabla_{y}q&0&0&0\\\
\nabla_{y}p_{S}&0&0&0\end{array}\right](x,y),$

and

$N^{S}_{+}(x,y)\triangleq\left[\nabla_{xy}^{2}\mathcal{L}^{\top},\nabla_{x}p_{J^{+}(x^{0},y^{*}(x^{0}))}^{\top},\nabla_{x}q^{\top},\nabla_{x}p_{S}^{\top}\right]^{\top}(x,y).$

When $S$ is empty, $M^{S}_{+}(x^{0},y^{*}(x^{0}))={M}_{+}(x^{0},y^{*}(x^{0}))$
and $N^{S}_{+}(x^{0},y^{*}(x^{0}))={N}_{+}(x^{0},y^{*}(x^{0}))$, where

$M_{+}(x,y)=\left[\begin{array}[]{ccccccc}\nabla_{y}^{2}\mathcal{L}&\nabla_{y}p_{J^{+}(x^{0},y^{*}(x^{0}))}^{\top}&\nabla_{y}q^{\top}\\\
\nabla_{y}p_{J^{+}(x^{0},y^{*}(x^{0}))}&0&0\\\
\nabla_{y}q&0&0\end{array}\right](x,y),$

and

$N_{+}(x,y)=[\nabla_{xy}^{2}\mathcal{L}^{\top},\nabla_{x}p_{J^{+}(x^{0},y^{*}(x^{0}))}^{\top},\nabla_{x}q^{\top}]^{\top}(x,y).$

Lemma 4 is provided in papers (Dempe 1998; Malanowski 1985), and also can be
derived from the directional derivative in part (iii) of Theorem 2.

######  Lemma 5.

Let $f:\mathbb{R}^{d_{x}}\longrightarrow\mathbb{R}$ a locally Lipschitz
function. Then $f$ is Lipschitz continuous on any compact set
$S\in\mathbb{R}^{d_{x}}$.

###### Proof.

The function $f:\mathbb{R}^{d_{x}}\longrightarrow\mathbb{R}$ locally
Lipschitz, then for any $x\in\mathbb{R}^{d_{x}}$, there are a Lipschitz
constant $l(x)$ and $\epsilon(x)>0$, such that $l(x)$ is the Lipschitz
constant of $f$ on $\mathcal{B}(x,\epsilon(x))$. For any compact set
$S\in\mathbb{R}^{d_{x}}$, we have $S\subset{\cup}_{x\in
S}\mathcal{B}(x,\epsilon(x))$, then ${\cup}_{x\in
S}\mathcal{B}(x,\epsilon(x))$ is a open cover of $S$. The set $S$ is compact
implies that, there exists a finite set $F$ such that $S\subset{\cup}_{x\in
F}\mathcal{B}(x,\epsilon(x))$. Then, $\operatorname{max}_{x\in F}l(x)<\infty$
is a Lipschitz constant of $f$ on ${\cup}_{x\in F}\mathcal{B}(x,\epsilon(x))$,
and thus is a Lipschitz constant of $f$ on $S$. ∎

######  Lemma 6.

Suppose all assumptions in Theorem 6 hold. Given a open ball $B$, if for each
$j$, either

$j\in J^{+}(x,y^{*}(x))^{C}=J(x,y^{*}(x))^{C}\cup J^{0}(x,y^{*}(x))\ \text{
for all }x\in B,$

or

$j\in J^{+}(x,y^{*}(x))\ \text{ for all }x\in B.$

Then $y^{*}(x)$ is continuously differentiable on $B$.

###### Proof.

For any $j$, $\text{ either }p_{j}(x,y^{*}(x))\leq 0,\lambda_{j}(x)=0\text{
for all }x\in B,\text{ or }p_{j}(x,y^{*}(x))=0,\lambda_{j}(x)>0\text{ for all
}x\in B$. Consider the set

$B^{\prime}\triangleq\\{x^{\prime}\in B:\text{for all }j,\text{ either
}p_{j}(x^{\prime},y^{*}(x^{\prime}))<0,\lambda_{j}(x^{\prime})=0\text{ or
}p_{j}(x^{\prime},y^{*}(x^{\prime}))=0,\lambda_{j}(x^{\prime})>0\\}.$

(i) By part (iii) of Theorem 6, for any point $x^{\prime}\in B^{\prime}$, the
SCSC holds at $y^{*}(x^{\prime})$, and $y^{*}$ is continuously differentiable
at $x^{\prime}$.

(ii) Consider the points $x\in B\setminus B^{\prime}$, there exist $j$ such
that $p_{j}(x,y^{*}(x))=0$, $\lambda_{j}(x)=0$, i.e., $J^{0}(x,y^{*}(x))$ is
not empty.

(ii.a) Consider $j$ such that $p_{j}(x,y^{*}(x))\leq 0$, $\lambda_{j}(x)=0$
for all $x\in B$. By the definitions in Theorem 6, $j\in
J^{0}_{-}(x,y^{*}(x),d)$ is not added to the computation of $-M_{D}^{-1}N_{D}$
in (19) for any direction $d$.

(ii.b) Consider $j$ such that $p_{j}(x,y^{*}(x))=0$, $\lambda_{j}(x)>0$ for
all $x\in B$. By the definitions in Theorem 6, $j\in J^{0}_{+}(x,y^{*}(x),d)$
is added to the computation of $-M_{D}^{-1}N_{D}$ in (19) for any direction
$d$.

From (ii.a) and (ii.b), for the points $x\in B\setminus B^{\prime}$, for any
$d$, the computation of $-M_{D}^{-1}N_{D}$ in (19) is totally same, i.e.,
$\lim_{h\rightarrow
0}\frac{\left\|y^{*}(x+h)-y^{*}(x)+M_{D}^{-1}(x,d)N_{D}(x,d)h\right\|}{|h|}=0$.
Thus, $y^{*}(x)$ is differentiable on $B$. Then, $y^{*}(x)$ is differentiable
on $B\setminus B^{\prime}$. Moreover, The derivative
$M_{D}^{-1}(x,d)N_{D}(x,d)$ is continuous for any $x$ and $d$. Thus,
$y^{*}(x)$ is continuously differentiable on $B$.

∎

#### Proof of Proposition 1

###### Proof of Proposition 1.

By the computation of gradient of $y^{*}$ in part (iii) of Theorem 6,
$\Phi(x)$ and $y^{*}$ are differentiable on $\mathcal{B}(x^{0},\epsilon)$,
then they are twice-differentiable on $\mathcal{B}(x^{0},\epsilon)$. When
$\epsilon$ is sufficiently small,
$|\|\nabla\Phi(x^{0})\|-\|\nabla\Phi(x^{\prime})\||<o(\epsilon)$ for any
$x^{\prime}\in\mathcal{B}(x^{0},\epsilon)$. Then,
$|\|\nabla\Phi(x^{0})\|-d(0,\bar{\partial}_{\epsilon}\Phi(x^{0}))|<o(\epsilon)$.
∎

#### Proof of Proposition 2

######  Proposition 4 (Full version of Proposition 2).

Suppose Assumptions 1, 2, 3 hold. Consider $x^{0}\in\mathbb{R}^{d_{x}}$ and
$\epsilon>0$, there exists $x\in\mathcal{B}(x^{0},\epsilon)$ such that $y^{*}$
is not continuously differentiable at $x$. Then, there exists at least one
$j$, such that there exist $x^{\prime}$,
$x^{\prime\prime}\in\mathcal{B}(x^{0},\epsilon)$ with

$\displaystyle j\in
J^{+}(x^{\prime},y^{*}(x^{\prime}))^{C}=J(x^{\prime},y^{*}(x^{\prime}))^{C}\cup
J^{0}(x^{\prime},y^{*}(x^{\prime}))\text{ and }\ j\in
J^{+}(x^{\prime\prime},y^{*}(x^{\prime\prime});$ (22)

Define the set $I^{\epsilon}(x^{0})$ which contains all $j$ that satisfy (22).
Define the set $I^{\epsilon}_{+}(x^{0})$ which contains all $j$ such that, for
any $x\in\mathcal{B}(x^{0},\epsilon)$,

$j\in J^{+}(x,y^{*}(x));$

Define the set $I^{\epsilon}_{-}(x^{0})$ which contains all $j$ such that, for
any $x\in\mathcal{B}(x^{0},\epsilon)$,

$j\in J(x,y^{*}(x))^{C}\cup J^{0}(x,y^{*}(x)).$

The set $G(x^{0},\epsilon)$ is defined as

$G(x^{0},\epsilon)\triangleq\\{\nabla_{x}f\left(x^{0},y^{*}\left(x^{0}\right)\right)+{w}^{S}(x^{0})^{\top}\nabla_{y}f\left(x^{0},y^{*}\left(x^{0}\right)\right):S\subseteq
I^{\epsilon}(x^{0})\\}.$

Here, ${w}^{S}(x^{0})$ is obtained by extracting the first $d_{x}$ rows from
matrix
$-M^{S}_{\epsilon}(x^{0},y^{*}(x^{0}))^{-1}N^{S}_{\epsilon}(x^{0},y^{*}(x^{0}))$,
with

$M^{S}_{\epsilon}\triangleq\left[\begin{array}[]{ccccccc}\nabla_{y}^{2}\mathcal{L}&\nabla_{y}p_{I^{\epsilon}_{+}(x^{0})}^{\top}&\nabla_{y}q^{\top}&\nabla_{y}p^{\top}_{S}\\\
\nabla_{y}p_{I^{\epsilon}_{+}(x^{0})}&0&0&0\\\ \nabla_{y}q&0&0&0\\\
\nabla_{y}p_{S}&0&0&0\end{array}\right],$

and

$N^{S}_{\epsilon}\triangleq\left[\nabla_{xy}^{2}\mathcal{L}^{\top},\nabla_{x}p_{I^{\epsilon}_{+}(x^{0})}^{\top},\nabla_{x}q^{\top},\nabla_{x}p_{S}^{\top}\right]^{\top}.$

Consider $x^{0}\in\mathbb{R}^{d_{x}}$, and assume there exists a sufficiently
small $\epsilon>0$ such that, there exists $x\in\mathcal{B}(x^{0},\epsilon)$
with that $y^{*}(x)$ is not continuously differentiable at $x$. Then, the
following holds

  * (i)

For any $g\in G\left(x^{0},\epsilon\right)$, there exists
$x^{\prime}\in\mathcal{B}(x^{0},\epsilon)$ such that
$\|g-\nabla\Phi(x^{\prime})\|<o(\epsilon)$. For any
$x^{\prime\prime}\in\mathcal{B}(x^{0},\epsilon)$ and $y^{*}(x)$ is
differentiable at $x^{\prime\prime}$, there exists $g\in
G\left(x^{0},\epsilon\right)$ such that
$\|g-\nabla\Phi(x^{\prime\prime})\|<o(\epsilon)$.

  * (ii)

For any $z\in\mathbb{R}^{d_{x}}$,

$|d(z,\operatorname{conv}G(x^{0},\epsilon))-d(z,\bar{\partial}_{\epsilon}\Phi(x^{0}))|<o(\epsilon).$

###### Proof of Proposition 4.

If for $x^{0}\in\mathbb{R}^{d_{x}}$ and $\epsilon>0$, $y^{*}(x)$ is not
continuously differentiable on the open ball $\mathcal{B}(x^{0},\epsilon)$.
Suppose that, for all $j$, points $x^{\prime}$,
$x^{\prime\prime}\in\mathcal{B}(x^{0},\epsilon)$ with (22) do not exist. By
Lemma 6, $y^{*}(x)$ is continuously differentiable on
$\mathcal{B}(x^{0},\epsilon)$, which leads to contradiction. Then, there
exists at least one $j$, such that there exist $x^{\prime}$,
$x^{\prime\prime}\in\mathcal{B}(x^{0},\epsilon)$ with (22).

(i) Firstly, similar to the proof in Proposition 1, if the components of

$M^{S}_{\epsilon}=\left[\begin{array}[]{ccccccc}\nabla_{y}^{2}\mathcal{L}&\nabla_{y}p_{I^{\epsilon}_{+}(x^{0})}^{\top}&\nabla_{y}q^{\top}&\nabla_{y}p^{\top}_{S}\\\
\nabla_{y}p_{I^{\epsilon}_{+}(x^{0})}&0&0&0\\\ \nabla_{y}q&0&0&0\\\
\nabla_{y}p_{S}&0&0&0\end{array}\right],$

and

$N^{S}_{\epsilon}=\left[\nabla_{xy}^{2}\mathcal{L}^{\top},\nabla_{x}p_{I^{\epsilon}_{+}(x^{0})}^{\top},\nabla_{x}q^{\top},\nabla_{x}p_{S}^{\top}\right]^{\top}.$

are same with the components of $M_{D}(x^{0},d)$ and $N_{D}(x^{0},d)$ shown in
(20), i.e., the sets which are involved in the matrix computation:

$I^{\epsilon}_{+}(x^{\prime})\cup
S={J^{0}_{+}(x^{\prime\prime},y^{*}(x^{\prime\prime}),d)}\cup
J^{+}(x^{\prime\prime},y^{*}(x^{\prime\prime})),$

then the difference
$\|M^{S}_{\epsilon}(x^{\prime},y^{*}(x^{\prime}))^{-1}N^{S}_{\epsilon}(x^{\prime},y^{*}(x^{\prime}))-M_{D}(x^{\prime\prime},d))^{-1}N_{D}(x^{\prime\prime},d)\|<o(\epsilon)$
for all $x^{\prime}$ and $x^{\prime\prime}\in\mathcal{B}(x^{0},\epsilon)$,
since the function ${(M^{S}_{\epsilon})}^{-1}N^{S}_{\epsilon}$ is
differentiable (refer to the proof in Proposition 1).

(a) Suppose that, for any $x^{\prime}\in\mathcal{B}(x^{0},\epsilon)$ and any
$d\in\mathbb{R}^{d_{x}}$, there exists $g^{S}\in G\left(x^{0},\epsilon\right)$
such that

$I^{\epsilon}_{+}(x^{0})\cup S={J^{0}_{+}(x^{\prime},y^{*}(x^{\prime}),d)}\cup
J^{+}(x^{\prime},y^{*}(x^{\prime}));$

Then, for any $x^{\prime}\in\mathcal{B}(x^{0},\epsilon)$ such that $y^{*}$ is
differentiable at $x^{\prime}$, there exists $g^{S}\in
G\left(x^{0},\epsilon\right)$ such that, for a direction
$d\in\mathbb{R}^{d_{x}}$,
$\|M^{S}_{\epsilon}(x^{0},y^{*}(x^{0}))^{-1}N^{S}_{\epsilon}(x^{0},y^{*}(x^{0}))-M_{D}(x^{\prime},d)^{-1}N_{D}(x^{\prime},d)\|<o(\epsilon)$.
Then, $\|w^{S}(x^{0})-y^{*}{(x^{\prime})}\|<o(\epsilon)$ and
$\|g^{S}-\nabla\Phi(x^{\prime})\|<o(\epsilon)$.

(b) Suppose that, for any $g^{S}\in G\left(x^{0},\epsilon\right)$, there
exists $x^{\prime}\in\mathcal{B}(x^{0},\epsilon)$ and $d\in\mathbb{R}^{d_{x}}$
such that

$I^{\epsilon}_{+}(x^{0})\cup S={J^{0}_{+}(x^{\prime},y^{*}(x^{\prime}),d)}\cup
J^{+}(x^{\prime},y^{*}(x^{\prime})).$

Since the set ${J^{0}_{+}(x^{\prime},y^{*}(x^{\prime}),d)}\subseteq
J^{0}(x^{\prime},y^{*}(x^{\prime}))$, from Lemma 4 and its proof shown in
(Dempe 1998; Malanowski 1985),
$g^{S}\in\bar{\partial}y^{*}\left(x^{\prime}\right)$ and exists
$\left\\{x^{j}\right\\}$ such that $g^{S}=\lim_{j\rightarrow\infty}\nabla
y^{*}\left(x^{j}\right):\left\\{x^{j}\right\\}\rightarrow x^{\prime}$ where
$y^{*}$ is differentiable at $y^{j}$ for all $j$. Then, there exists
$x^{\prime\prime}$ in any small neighborhood of $x^{\prime}$, such that
${J^{0}_{+}(x^{\prime},y^{*}(x^{\prime}),d)}\cup
J^{+}(x^{\prime},y^{*}(x^{\prime}))=J^{+}(x^{\prime\prime},y^{*}(x^{\prime\prime}))$
and $y^{*}$ is differentiable at $x^{\prime\prime}$. Then,

$I^{\epsilon}_{+}(x^{0})\cup
S=J^{+}(x^{\prime\prime},y^{*}(x^{\prime\prime})),$

and we have $\|w^{S}(x^{0})-y^{*}{(x^{\prime\prime})}\|<o(\epsilon)$ and
$\|g^{S}-\nabla\Phi(x^{\prime\prime})\|<o(\epsilon)$ with
$x^{\prime\prime}\in\mathcal{B}(x^{0},\epsilon)$. Then, the part (i) of the
proposition is shown.

Now, we can prove (i) by showing that the assumptions of (a) and (b) hold.
Define
$J^{N}(x,y^{*}(x))\triangleq\\{j:j\not\in{J^{+}(x,y^{*}(x))}\cup{J^{0}(x,y^{*}(x))}\\}$.
Then, for any $x^{*}\in\mathcal{B}(x^{0},\epsilon)$ and any
$d\in\mathbb{R}^{d_{x}}$, $I^{\epsilon}(x^{0})\cup I_{+}^{\epsilon}(x^{0})\cup
I_{-}^{\epsilon}(x^{0})=J^{0}({x^{*},y^{*}(x^{*})})\cup
J^{+}({x^{*},y^{*}(x^{*})})\cup
J^{N}(x^{*},y^{*}(x^{*}))=J^{0}_{-}({x^{*},y^{*}(x^{*}),d})\cup
J^{0}_{+}({x^{*},y^{*}(x^{*}),d})\cup J^{+}({x^{*},y^{*}(x^{*})})\cup
J^{N}(x^{*},y^{*}(x^{*}))$, since they both contain all constraints $p_{j}$.
Note that the intersection of two in $I^{\epsilon}(x^{0})$,
$I_{+}^{\epsilon}(x^{0})$ and $I_{-}^{\epsilon}(x^{0})$ is empty, the
intersection of two in $J^{0}_{-}({x^{*},y^{*}(x^{*}),d})$,
$J^{0}_{+}({x^{*},y^{*}(x^{*}),d})$, $J^{+}({x^{*},y^{*}(x^{*})})$ and
$J^{N}(x^{*},y^{*}(x^{*}))$ is empty, and
$J^{0}({x^{*},y^{*}(x^{*})})=J^{0}_{+}({x^{*},y^{*}(x^{*}),d})\cup
J^{0}_{-}({x^{*},y^{*}(x^{*}),d})$.

  * (1)

Consider $j\in I_{+}^{\epsilon}(x^{0})$, i.e., $p_{j}(x,y^{*}(x))=0$ and
$\lambda_{j}(x)>0$ for all $x\in\mathcal{B}(x^{0},\epsilon)$. Then
$j\in{J^{+}(x^{\prime},y^{*}(x^{\prime}))}$ for any
$x^{\prime}\in\mathcal{B}(x^{0},\epsilon)$. Then,
$j\in{J^{0}_{+}(x^{\prime},y^{*}(x^{\prime}),d)}\cup{J^{+}(x^{\prime},y^{*}(x^{\prime}))}$
for any $d\in\mathbb{R}^{d_{x}}$ and any
$x^{\prime}\in\mathcal{B}(x^{0},\epsilon)$. Thus,

$I_{+}^{\epsilon}(x^{0})\subseteq{J^{0}_{+}(x^{\prime},y^{*}(x^{\prime}),d)}\cup{J^{+}(x^{\prime},y^{*}(x^{\prime}))}$

for any $d\in\mathbb{R}^{d_{x}}$ and any
$x^{\prime}\in\mathcal{B}(x^{0},\epsilon)$.

  * (2)

Consider $j\in I_{-}^{\epsilon}(x^{0})$. If given
$x\in\mathcal{B}(x^{0},\epsilon)$, we have $p_{j}(x,y^{*}(x))<0$ and
$\lambda_{j}(x)=0$, then $j\not\in{J^{+}(x,y^{*}(x))}\cup{J^{0}(x,y^{*}(x))}$,
i.e., $j\in J^{N}(x,y^{*}(x))$. If given $x\in\mathcal{B}(x^{0},\epsilon)$, we
have $p_{j}(x,y^{*}(x))=0$, $\lambda_{j}(x)=0$ and this holds for any
$x\in\mathcal{B}(x^{0},\epsilon)$, then $j\in{J^{0}_{-}(x,y^{*}(x),d)}$ for
any $d\in\mathbb{R}^{d_{x}}$. If given $x\in\mathcal{B}(x^{0},\epsilon)$, we
have $p_{j}(x,y^{*}(x))=0$, $\lambda_{j}(x)=0$ but this does not hold for all
set $\mathcal{B}(x^{0},\epsilon)$, then $j\in{J^{0}_{-}(x,y^{*}(x),d)}$ for
any $d\in\mathbb{R}^{d_{x}}$. Then,

$I_{-}^{\epsilon}(x^{0})\subseteq{J^{0}_{-}(x,y^{*}(x),d)}\cup
J^{N}(x,y^{*}(x)),$

for any $x\in\mathcal{B}(x^{0},\epsilon)$ and any $d\in\mathbb{R}^{d_{x}}$.

  * (3)

Consider $j\in I^{\epsilon}(x^{0})$. When $\epsilon>0$ is sufficiently small
such that, there exists $x^{*}\in\mathcal{B}(x^{0},\epsilon)$ such that
$p_{j}(x^{*},y^{*}(x^{*}))=0$ and $\lambda_{j}(x^{*})=0$ for all $j\in
I^{\epsilon}(x^{0})$. Then, we have

$I^{\epsilon}(x^{0})\subseteq J^{0}({x^{*},y^{*}(x^{*})}).$

Then, for any $S\subseteq I^{\epsilon}(x^{0})$, $S\subseteq
J^{0}({x^{*},y^{*}(x^{*})})$. Also,

${J^{+}(x^{*},y^{*}(x^{*}))}\subseteq I_{+}^{\epsilon}(x^{0}).$

This is true because that, assume that $j\in{J^{+}(x^{*},y^{*}(x^{*}))}$ and
$j\not\in I_{+}^{\epsilon}(x^{0})$, then $j\in I^{\epsilon}(x^{0})$, then
$p_{j}(x^{*},y^{*}(x^{*}))=0$ and $\lambda_{j}(x^{*})=0$, and
$j\in{J^{0}(x^{*},y^{*}(x^{*}))}$ which contradicts
$j\in{J^{+}(x^{*},y^{*}(x^{*}))}$.

From (1) and (3), we have that, there exists
$x^{*}\in\mathcal{B}(x^{0},\epsilon)$, for any $d\in\mathbb{R}^{d_{x}}$,

$J^{+}(x^{*},y^{*}(x^{*}))\subseteq
I_{+}^{\epsilon}(x^{0})\subseteq{J^{+}(x^{*},y^{*}(x^{*}))}\cup{J_{+}^{0}(x^{*},y^{*}(x^{*}),d)}.$
(23)

From Lemma 4 and the proof of the lemma shown in (Dempe 1998; Malanowski
1985), for any set $A\subseteq J^{0}({x^{*},y^{*}(x^{*})})$, we can find a
direction $d$ such that $A={J^{0}_{+}(x^{*},y^{*}(x^{*}),d)}$. Here, we can
let $A=S\cup I_{+}^{\epsilon}(x^{0})\setminus J^{+}(x^{*},y^{*}(x^{*}))$. From
(23), $A\subseteq J^{0}({x^{*},y^{*}(x^{*})})$. Then, $S\cup
I_{+}^{\epsilon}(x^{0})\setminus
J^{+}(x^{*},y^{*}(x^{*}))={J^{0}_{+}(x^{*},y^{*}(x^{*}),d)}$. Then, for any
$g^{S}\in G\left(x^{0},\epsilon\right)$, there exists
$x^{*}\in\mathcal{B}(x^{0},\epsilon)$ and $d\in\mathbb{R}^{d_{x}}$ such that

$I^{\epsilon}_{+}(x^{0})\cup S={J^{0}_{+}(x^{*},y^{*}(x^{*}),d)}\cup
J^{+}(x^{*},y^{*}(x^{*})).$

The assumption of (b) is shown.

From (2), if $j\in I_{-}^{\epsilon}(x^{0})$, for any
$x\in\mathcal{B}(x^{0},\epsilon)$ and any $d\in\mathbb{R}^{d_{x}}$,
$j\in{J^{0}_{-}(x,y^{*}(x),d)}\cup J^{N}(x,y^{*}(x))$. Then,
$j\not\in{J^{0}_{+}(x,y^{*}(x),d)}\cup{J^{+}(x,y^{*}(x))}$. Then, for any set
$C\subseteq I_{-}^{\epsilon}(x^{0})$,
$C\cap{(J^{0}_{+}(x,y^{*}(x),d)}\cup{J^{+}(x,y^{*}(x)))}$ is empty. Moreover,
from (1),
$I_{+}^{\epsilon}(x^{0})\subseteq{J^{0}_{+}(x,y^{*}(x),d)}\cup{J^{+}(x,y^{*}(x))}$.
Then, for any $x\in\mathcal{B}(x^{0},\epsilon)$ and any
$d\in\mathbb{R}^{d_{x}}$, there exists $g^{S}\in G\left(x^{0},\epsilon\right)$
such that

$I^{\epsilon}_{+}(x^{0})\cup S={J^{0}_{+}(x,y^{*}(x),d)}\cup
J^{+}(x,y^{*}(x));$

The assumption of (a) is shown. Then, the proof of the part (i) of the
proposition is done.

(ii) From the definition of the Clarke $\epsilon\text{-subdifferential}$, it
is easy to see
$\bar{\partial}_{\epsilon}\Phi(x^{0})=\operatorname{conv}\\{\nabla\Phi(x^{\prime}):x^{\prime}\in\mathcal{B}(x^{0},\epsilon),y^{*}$
is differentiable at $x^{\prime}\\}$. Then, for any
$g_{0}\in\bar{\partial}_{\epsilon}\Phi(x^{0})$, there exist $g_{1}$,
$g_{2}\in\\{\nabla\Phi(x^{\prime}):x^{\prime}\in\mathcal{B}(x^{0},\epsilon),y^{*}$
is differentiable at $x^{\prime}\\}$, such that $g_{0}=\theta
g_{1}+(1-\theta)g_{2}$ and $0\leq\theta\leq 1$. From (i), we can find
$g_{1}^{\prime}$, $g_{2}^{\prime}\in G\left(x^{0},\epsilon\right)$, such that
$\|g_{1}-g_{1}^{\prime}\|<o(\epsilon)$ and
$\|g_{2}-g_{2}^{\prime}\|<o(\epsilon)$. Then,

$g_{0}^{\prime}=\theta
g_{1}^{\prime}+(1-\theta)g_{2}^{\prime}\in\operatorname{conv}G(x^{0},\epsilon),$

and for any $z\in\mathbb{R}^{d_{x}}$,

$\displaystyle|\|z-g_{0}\|-\|z-g_{0}^{\prime}\||$ $\displaystyle=|\|z-(\theta
g_{1}+(1-\theta)g_{2})\|-\|z-(\theta
g_{1}^{\prime}+(1-\theta)g_{2}^{\prime})\||$
$\displaystyle\leq|\|\theta(z-g_{1})+(1-\theta)(z-g_{2})\|-\|(\theta(z-g_{1}^{\prime}))+(1-\theta)(z-g_{2}^{\prime})\||$
$\displaystyle\leq\|\theta(z-g_{1})+(1-\theta)(z-g_{2})-(\theta(z-g_{1}^{\prime}))-(1-\theta)(z-g_{2}^{\prime})\|$
$\displaystyle\leq\|\theta(z-g_{1})-(\theta(z-g_{1}^{\prime}))\|+\|(1-\theta)(z-g_{2})-(1-\theta)(z-g_{2}^{\prime})\|$
$\displaystyle<o(\epsilon).$

Let $l=d(z,\bar{\partial}_{\epsilon}\Phi(x^{0}))$. Then, for any $\sigma>0$,
there exists $g_{0}\in\bar{\partial}_{\epsilon}\Phi(x^{0}))$ such that
$l\leq\|z-g_{0}\|<l+\sigma$. Then, there exists
$g_{0}^{\prime}\in\operatorname{conv}G(x^{0},\epsilon))$ with
$|\|z-g_{0}\|-\|z-g_{0}^{\prime}\||<o(\epsilon)$. Then,
$l-o(\epsilon)\leq\|z-g_{0}^{\prime}\|<l+\sigma+o(\epsilon)$. Since
$\|z-g_{0}^{\prime}\|\geq d(z,\operatorname{conv}G(x^{0},\epsilon))$, we have
$d(z,\operatorname{conv}G(x^{0},\epsilon))=\inf\\{\|z-a\|\mid
a\in\operatorname{conv}G(x^{0},\epsilon)\\}<l+\sigma+o(\epsilon)$. Then,
$d(z,\operatorname{conv}G(x^{0},\epsilon))<d(z,\bar{\partial}_{\epsilon}\Phi(x^{0}))+\sigma+o(\epsilon)$
for any $\sigma>0$, i.e., $d(z,\operatorname{conv}G(x^{0},\epsilon))\leq
d(z,\bar{\partial}_{\epsilon}\Phi(x^{0}))+o(\epsilon)$.

Similar to the proof of $d(z,\operatorname{conv}G(x^{0},\epsilon))\leq
d(z,\bar{\partial}_{\epsilon}\Phi(x^{0}))+o(\epsilon)$, from (i), we can also
get $d(z,\bar{\partial}_{\epsilon}\Phi(x^{0}))\leq
d(z,\operatorname{conv}G(x^{0},\epsilon))+o(\epsilon)$. Then,
$|d(z,\operatorname{conv}G(x^{0},\epsilon))-d(z,\bar{\partial}_{\epsilon}\Phi(x^{0}))|<o(\epsilon)$.
Then, the proof of the part (ii) of Proposition 4 is done.

∎

Note that Proposition 2 is included in Proposition 4, then Proposition 2 is
shown.

###  C.3 Proof of Theorem 3

We start part (i) of the proof of Theorem 3 from Lemma 7, and show part (ii)
of the proof from Lemma 8.

######  Lemma 7.

Let $\emptyset\neq C\subset\mathbb{R}^{n}$ be compact and convex and
$\beta\in(0,1)$ and $0\notin C$. If $u,v\in C$ and $\|u\|=d(0,C)$, then
$\langle v,u\rangle\geq\|u\|^{2}$.

###### Proof.

Suppose that $\|u\|=d(0,C)$ and $\langle v,u\rangle<\|u\|^{2}$. Then, there
exists $0<\theta<1$ such that $w=\theta v+(1-\theta)u$ and $\|w\|<\|u\|$.
Then, $w\in C$ since $C$ is convex. Then $\|u\|\neq d(0,C)$, which has
contradiction. ∎

###### Proof of part (i) of Theorem 3.

Firstly, consider $y^{*}$ is differentiable at $x^{k}$. We have
$g^{k}=\min\\{\|g\|:g\in\operatorname{conv}G(x^{k},\epsilon_{k})\\}$ and
$\|g^{k}\|>0$. We have $\operatorname{conv}G(x^{k},\epsilon_{k})$ is closed,
bounded and convex, then is convex and compact. Since
$\operatorname{conv}G(x^{k},\epsilon_{k})$ is closed,
$g^{k}\in\operatorname{conv}G(x^{k},\epsilon_{k})$ and
$\|g^{k}\|=d(0,\operatorname{conv}G(x^{k},\epsilon_{k}))$. By Lemma 7,
$\langle v,g_{k}\rangle\geq\|g^{k}\|^{2}$ for any
$v\in\operatorname{conv}G(x^{k},\epsilon_{k})$. Since $y^{*}$ is
differentiable at $x^{k}$, we have
$\nabla\Phi(x^{k})\in\operatorname{conv}G(x^{k},\epsilon_{k})$. Then,
$\langle\nabla\Phi(x^{k}),g_{k}\rangle\geq\|g^{k}\|^{2}$. Since $y^{*}$ is
differentiable at $x^{k}$, $\nabla\Phi$ is differentiable at $x^{k}$, then
$\Phi$ is twice-differentiable at $x^{k}$. Then, when $t$ is sufficiently
small,

$\displaystyle\Phi(x^{k}-tg^{k})=$
$\displaystyle\Phi(x^{k})-t\langle\nabla\Phi(x^{k}),g^{k}\rangle+o(t^{2})$
$\displaystyle\leq$ $\displaystyle\Phi(x^{k})-t\|g^{k}\|^{2}+o(t^{2})$
$\displaystyle<$ $\displaystyle\Phi(x^{k})-\beta t\|g^{k}\|^{2},$

for any $0<\beta<1$. Then, the line search has a positive solution $t_{k}$.

Secondly, consider $y^{x}$ is not differentiable at $x^{k}$. From Lemma 4,
Proposition 2 and the proof of Proposition 2 (also shown in (Dempe 1998;
Malanowski 1985)), $\Phi(x)$ is a piecewise function by finite number of
twice-differentiable functions $\\{\Phi_{i}(x)\\}_{1\leq i\leq m}$, and for
each $1\leq i\leq m$,
$\nabla\Phi_{i}(x^{k})\in\operatorname{conv}G(x^{k},\epsilon_{k})$. Then, when
$t$ is sufficiently small, for all $1\leq i\leq m$,

$\displaystyle\Phi_{i}(x^{k}-tg^{k})=$
$\displaystyle\Phi_{i}(x^{k})-t\langle\nabla\Phi_{i}(x^{k}),g^{k}\rangle+o(t^{2})$
$\displaystyle\leq$ $\displaystyle\Phi_{i}(x^{k})-t\|g^{k}\|^{2}+o(t^{2})$
$\displaystyle<$ $\displaystyle\Phi_{i}(x^{k})-\beta t\|g^{k}\|^{2}$
$\displaystyle=$ $\displaystyle\Phi(x^{k})-\beta t\|g^{k}\|^{2},$

for any $0<\beta<1$. Then, we have $\Phi(x^{k}-tg^{k})<\Phi(x^{k})-\beta
t\|g^{k}\|^{2}$. Then, the line search has a positive solution $t_{k}$.

∎

######  Lemma 8.

If
$\liminf\limits_{k\rightarrow\infty}{\max\left\\{\|x^{k}-x\|,\|g^{k}\|,\epsilon_{k}\right\\}}=0$
with
$|\|g^{k}\|-d(0,\bar{\partial}_{\epsilon_{k}}\Phi(x^{k}))|<o(\epsilon_{k})$
for sufficiently small $\epsilon_{k}$, then $0\in\bar{\partial}\Phi(x)$.

###### Proof.

If
$\liminf\limits_{k\rightarrow\infty}{\max\left\\{\|x^{k}-x\|,\|g^{k}\|,\epsilon_{k}\right\\}}=0$,
then the sequence $\\{x^{k}\\}$ has a subsequence $\\{x^{k_{n}}\\}$ such that
$x^{k_{n}}\rightarrow x$, $\|g^{k}\|\rightarrow 0$ and
$\epsilon_{k}\rightarrow 0$. Since
$|\|g^{k}\|-d(0,\bar{\partial}_{\epsilon}\Phi(x^{k}))|<o(\epsilon_{k})$ and
$\epsilon_{k}\rightarrow 0$, we have
$d(0,\bar{\partial}_{\epsilon_{k}}\Phi(x^{k}))\rightarrow 0$, i.e., there
exists a sequence $\\{h^{k}\\}$ with
$h^{k}\in\bar{\partial}_{\epsilon_{k}}\Phi(x^{k})$ and $\|h^{k}\|\rightarrow
0$, which implies $0\in\bar{\partial}\Phi(x)$. ∎

###### Proof of parts (ii)-(iv) of Theorem 3.

(ii.a) From part (i) of Theorem 3, the line search has a non-zero solution
$t_{k}$, we have $\Phi(x^{k+1})<\Phi(x^{k})-\beta t_{k}\|g^{k}\|^{2}$, Then,

$\sum_{k=1}^{\infty}\beta
t_{k}\|g^{k}\|^{2}<\sum_{k=1}^{\infty}\Phi(x^{k})-\Phi(x^{k+1})\leq\Phi(x^{1})-a<\infty,$

where $a$ is a lower bound of $\Phi(x)$ on $\mathbb{R}^{d_{x}}$. Since
$x^{k+1}=x^{k}-tg^{k}$, we have

$\sum_{k=1}^{\infty}\|x^{k+1}-x^{k}\|\|g^{k}\|<\infty.$ (24)

(ii.b) We now show $\lim_{k\rightarrow\infty}\nu_{k}=0$ and
$\lim_{k\rightarrow\infty}\epsilon_{k}=0$. Assume this does not hold. There
are $k_{1}$, $\hat{\nu}$ and $\hat{\epsilon}$, such that
${\nu}_{k}=\hat{\nu}$, ${\epsilon}_{k}=\hat{\epsilon}$ and
$\|g^{k}\|>\hat{\nu}$ for all $k>k_{1}$. Then, by (24), we have
$\sum_{k=1}^{\infty}\|x^{k+1}-x^{k}\|<\infty$, and then $x^{k}$ converges to a
point $\bar{x}$ and $t_{k}\|g^{k}\|\rightarrow 0$ which means
$t_{k}\rightarrow 0$.