# Theoretical smoothing frameworks for general nonsmooth bilevel problems

Jan Harold Alcantara Akiko Takeda<EMAIL_ADDRESS>Center for
Advanced Intelligence Project, RIKEN, Tokyo,
<EMAIL_ADDRESS>Department of Mathematical Informatics,
Graduate School of Information Science and Technology, University of Tokyo,
Tokyo, Japan Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan

###### Abstract

Bilevel programming has recently received a great deal of attention due to its
abundant applications in many areas. The optimal value function approach
provides a useful reformulation of the bilevel problem, but its utility is
often limited due to the nonsmoothness of the value function even in cases
when the associated lower-level function is smooth. In this paper, we present
two smoothing strategies for the value function associated with lower-level
functions that are not necessarily smooth but are Lipschitz continuous. The
first method employs quadratic regularization for partially convex lower-level
functions, while the second utilizes entropic regularization for general
lower-level objective functions. Meanwhile, the property known as gradient
consistency is crucial in ensuring that a designed smoothing algorithm is
globally subsequentially convergent to stationary points of the value function
reformulation. With this motivation, we prove that the proposed smooth
approximations satisfy the gradient consistent property under certain
conditions on the lower-level function.

Keywords. bilevel optimization; value function; smooth approximation; gradient
consistency; quadratic regularization; entropic regularization

##  1 Introduction

Consider the bilevel optimization problem

$\displaystyle\begin{array}[]{rl}\displaystyle\min_{(x,y)\in X\times
Y}{}&f(x,y)\\\ \mbox{s.t.}{}&\displaystyle
y\in\operatorname*{arg\,min}_{\bar{y}\in Y}g(x,\bar{y})\end{array}$ (1.3)

where $f,g:{\rm I}\\!{\rm R}^{n}\times{\rm I}\\!{\rm R}^{m}\to{\rm I}\\!{\rm
R}$ are Lipschitz continuous but possibly nonsmooth functions, and $X,Y$ are
closed and convex subsets of ${\rm I}\\!{\rm R}^{n}$ and ${\rm I}\\!{\rm
R}^{m}$, respectively. The minimization of $g(x,\cdot)$ over $Y$ is known as
the _lower-level problem_ , while the minimization of $f$ is called the
_upper-level problem_. The bilevel optimization problem (1.3) has recently
gained significant attention due to its numerous applications, including
hyperparameter optimization [Franceschi et al., 2018, Okuno et al., 2021],
meta-learning [Franceschi et al., 2018], and Stackelberg games [von
Stackelberg, 2010], among others. We refer the reader to [Dempe et al., 2015,
Dempe and Zemkoho, 2020] and the references therein for more applications of
bilevel optimization.

Traditional methods for solving the bilevel problem (1.3) involve
reformulation or relaxation of (1.3) as a one-level problem, thereby
permitting the use of solution methods from nonlinear programming [Dempe et
al., 2015]. A widely used approach is to replace the lower-level minimization
problem by its optimality conditions. This yields an equivalent problem if
$g(x,\cdot)$ is convex for each $x\in X$. Among the recent trends that gained
considerable attention is the case when $f$ is continuously differentiable,
$g$ is a twice continuously differentiable, $g(x,\cdot)$ is strongly convex
for all $x\in X$, and $Y={\rm I}\\!{\rm R}^{m}$. In this case, the lower-level
problem of (1.3) defines a smooth map $x\mapsto y(x)$ that corresponds to the
unique minimizer of $g(x,\cdot)$. In turn, (1.3) simplifies to the
minimization of a smooth function $f(x,y(x))$ over $x\in X$, which can be
handled by typical smooth optimization methods such as the projected gradient
descent algorithm. Indeed, this framework has been the basis of some recent
works in the literature [Ghadimi and Wang, 2018, Ji et al., 2021, Pedregosa,
2016], but the main drawback is that this approach is heavily dependent on the
smoothness of $f$ and $g$, as well as the strong convexity of $g(x,\cdot)$. In
many applications, such smoothness requirements are not met [Okuno et al.,
2021]. Moreover, we note that when $g(x,\cdot)$ is nonconvex, a local optimal
solution of (1.3) may not even correspond to a stationary point of its
reformulation via optimality conditions of the lower-level problem [Mirrlees,
1999].

An alternative stream of research, which is the direction pursued in this
paper, employs the value function reformulation approach. The value function
associated with the lower-level problem of (1.3) is defined as

$v(x)\coloneqq\min_{y\in Y}~{}g(x,y).$ (1.4)

With this, the bilevel problem (1.3) is equivalent to the nonlinear
programming problem

$\displaystyle\begin{array}[]{rl}\displaystyle\min_{(x,y)\in X\times
Y}{}&f(x,y)\\\ \text{s.t.}{}&\displaystyle g(x,y)-v(x)\leq 0,\end{array}$
(VFP)

which was first proposed by Outrata [1990]. Note that the reformulation (VFP)
is independent of any smoothness and convexity assumptions on $g$, so that
this framework is theoretically applicable to any bilevel optimization
problem. However, one difficulty that comes with this flexible reformulation
is determining under what conditions local solutions of (VFP) correspond to
its stationary points. In nonlinear programming, these conditions pertain to
constraint qualifications (CQs), and unfortunately, usual CQs such as the
Mangasarian-Fromovitz constraint qualification (MFCQ) are violated by feasible
points of (VFP) [Ye and Daoli, 1995]. One promising alternative is to consider
an approximate bilevel program

$\displaystyle\begin{array}[]{rl}\displaystyle\min_{(x,y)\in X\times
Y}{}&f(x,y)\\\ \text{s.t.}{}&\displaystyle
g(x,y)-v(x)\leq\epsilon.\end{array}$ ($\text{VFP}_{\epsilon}$)

where $\epsilon>0$. The above perturbed problem is a reasonable approximation
of (VFP) as its local and global solutions are arbitrarily close to the
solution set of (VFP) [Lin et al., 2014, Ye et al., 2023]. Moreoever, unlike
(VFP), (nonsmooth) MFCQ is automatically satisfied by feasible points of
($\text{VFP}_{\epsilon}$), which is a sufficient constraint qualification for
local solutions of ($\text{VFP}_{\epsilon}$) to be stationary [Lampariello and
Sagratella, 2020, Lin et al., 2014, Ye et al., 2023].

While the approximate bilevel problem ($\text{VFP}_{\epsilon}$) addresses the
CQ issue, another hurdle is the need for an algorithmic framework that is
capable of obtaining stationary points. Solution methods for solving nonlinear
programming problems often hinge on the assumption that both the objective and
constraint functions involved are smooth. Unfortunately, the value function
reformulation (VFP) of the bilevel problem introduces a challenge, since the
value function $v$ defined by (1.4), in general, is nonsmooth even when $g$ is
a smooth function (see Theorem 2.1). In the absence of smoothness, a popular
adopted strategy involves employing smooth approximations, which have been
extensively utilized in many nonsmooth optimization problems, complementarity
problems and variational inequalities; see Chen [2012] and the references
therein. As a consequence, it is natural to expect that smooth approximations
for the functions $f$ and $g$ in the bilevel problem (1.3) may be readily
available, since these often correspond to loss functions with a nonsmooth
regularizer in many applications; for instance, see Chen [2012]. However, as
previously mentioned, the smoothness of $g$ is in general not adequate to
ensure the smoothness of $v$. Consequently, employing traditional methods for
the nonlinear programming reformulation (VFP) or ($\text{VFP}_{\epsilon}$)
necessitates smoothing techniques for the value function. Unfortunately, to
date, smooth approximations of the value functions have not been thoroughly
investigated yet in the literature. One work that pursued this direction in
the context of bilevel optimization is studied by Lin et al. [2014]. The
authors adopted the entropic regularization approach originally formulated in
[Fang and Wu, 1996], which yields an approximation (in the sense of Definition
2.5) that is valid for a smooth function $g$ and a compact set $Y$. Gradient
consistency (see Definition 2.6) of the proposed smoothing family is also
proved, which is an essential property to guarantee convergence to stationary
points. Apart from this work, there has been no other existing works on
smoothing methods for bilevel problems, to the best of our knowledge.

In this paper, we present theoretical frameworks of smoothing strategies for
solving the bilevel problem that do not require smoothness assumptions on $g$.
In particular, we focus on the value function reformulation, and propose
smooth approximations of the value function for Lipschitz continuous functions
$g$. We propose two different techniques: First, we present a simple quadratic
regularization approach for nonsmooth lower-level function $g$ that is convex
in $y$. The other technique is a more general approach that has no partial
convexity requirement on $g$. More specifically, we extend the framework of
Fang and Wu [1996], Lin et al. [2014] to obtain a smooth approximation of the
value function for a nonsmooth function $g$ and a compact set $Y$. In
addition, we also present a possible extension to unbounded closed sets $Y$.
Meanwhile, as mentioned above, gradient consistency is a very important
property to guarantee that a smoothing algorithm is globally (subsequentially)
convergent to stationary points (see Proposition 2.13). Motivated by this, we
prove that under certain conditions on $g$, all the proposed smooth
approximations possess gradient consistency. Instrumental to this goal are
Danskin-type theorems for arbitrary closed sets $Y$, which are also derived in
this paper.

##  2 Mathematical Preliminaries

Throughout the paper, $B_{\delta}(x)$ denotes an open ball centered at $x$
with radius $\delta>0$. The interior, closure and convex hull of a set $X$ are
denoted by $\operatorname*{int}(X)$, $\operatorname*{cl}(X)$ and
$\operatorname*{co}(X)$, respectively. The projection onto $X$ and the
distance function on $X$ are given respectively by

$\Pi_{X}(z)\coloneqq\operatorname*{arg\,min}\\{\|x-z\|:x\in X\\}$

and

$\operatorname*{dist}(z,X)\coloneqq\min\\{\|x-z\|:x\in X\\}.$

We will always use $O_{X}$ and $O_{Y}$ to denote an open set containing the
closed sets $X$ and $Y$, respectively. For a set $S\subseteq{\rm I}\\!{\rm
R}^{n}\times{\rm I}\\!{\rm R}^{m}$, we define

$\pi_{x}(S)\coloneqq\\{x^{\prime}\in{\rm I}\\!{\rm R}^{n}:\exists
y^{\prime}\in{\rm I}\\!{\rm R}^{m}~{}\text{s.t. }(x^{\prime},y^{\prime})\in
S\\}.$ (2.1)

###  2.1 Nonsmooth and variational analysis

We recall some important concepts and results from nonsmooth and variational
analysis. Most of these materials can be found in [Clarke, 1983, Chapter 2]
and Rockafellar and Wets [1998].

Let $\phi$ be a Lipschitz continuous function on an open set $O\subseteq{\rm
I}\\!{\rm R}^{n}$. The _Clarke generalized directional derivative_ of $\phi$
at $\bar{x}\in O$ in the direction $d$, denoted by $\phi^{\circ}(x;d)$, is
defined as

$\phi^{\circ}(\bar{x};d)=\limsup_{x\to\bar{x},t\searrow
0}\frac{\phi(x+td)-\phi(x)}{t},$

and the (usual) _directional derivative_ of $\phi$ at $\bar{x}$ in the
direction $d$ is

$\phi^{\prime}(\bar{x};d)=\lim_{t\searrow
0}\frac{\phi(\bar{x}+td)-\phi(\bar{x})}{t}.$

We say that $\phi$ is at $\bar{x}$ _Clarke regular_ if for all $d\in{\rm
I}\\!{\rm R}^{n}$, $\phi^{\prime}(\bar{x};d)$ exists and
$\phi^{\prime}(\bar{x};d)=\phi^{\circ}(\bar{x};d)$. For instance, if $\phi$ is
differentiable at $\bar{x}$ or if $\phi$ is convex, then it is Clarke regular
at $\bar{x}$.

The _Clarke generalized gradient_ of $\phi$ at $\bar{x}$, denoted by
$\partial\phi(\bar{x})$, is given by

$\partial\phi(\bar{x})\coloneqq\\{\xi\in{\rm I}\\!{\rm
R}^{n}:\phi^{\circ}(\bar{x};d)\geq\langle\xi,d\rangle~{}\forall d\in{\rm
I}\\!{\rm R}^{n}\\},$

which is a compact and convex set. When $\phi$ is convex, this coincides with
the subdifferential in the sense of convex analysis:

$\partial^{c}\phi(\bar{x})\coloneqq\\{\xi\in{\rm I}\\!{\rm
R}^{n}:\phi(x)\geq\phi(\bar{x})+\langle\xi,x-\bar{x}\rangle~{}\forall x\in{\rm
I}\\!{\rm R}^{n}\\}.$

The Clarke generalized directional derivative $\phi^{\circ}(\bar{x};\cdot)$
can be expressed as the support function of $\partial\phi(\bar{x})$, that is,

$\phi^{\circ}(\bar{x};d)=\sigma_{\partial\phi(\bar{x})}(d)\coloneqq\max\\{\langle
d,\xi\rangle:\xi\in\partial\phi(\bar{x})\\},$ (2.2)

and so when $\phi$ is convex,
$\phi^{\prime}(\bar{x};d)=\sigma_{\partial^{c}\phi(\bar{x})}(d)$.

As a set-valued mapping, $\partial\phi(\cdot)$ is upper semicontinuous at any
$\bar{x}\in O$. That is, given any $\varepsilon>0$, there exists $\delta>0$
such that

$\partial\phi(x)\subseteq\partial\phi(\bar{x})+\varepsilon
B_{1}(0)\quad\forall x\in B_{\delta}(\bar{x}).$

By a standard argument using Heine-Borel theorem and noting the boundedness of
$\partial\phi(x)$ for any $x\in O$, note that
$\bigcup_{x\in\Omega}\partial\phi(x)$ is a bounded set for any compact subset
$\Omega$ of $O$.

For the Clarke subdifferential of the value function, we have the following
celebrated result due to Danskin (see Danskin [1967] and [Clarke et al., 1998,
Ex. 9.13]).

######  Theorem 2.1 (Danskin’s Theorem).

Let $g:{\rm I}\\!{\rm R}^{n}\times Y\to{\rm I}\\!{\rm R}$ be given, where $Y$
is a compact subset of ${\rm I}\\!{\rm R}^{m}$. Suppose that for a
neighborhood $\Omega$ of $\bar{x}\in{\rm I}\\!{\rm R}^{n}$, the derivative
$\nabla_{x}g(x,y)$ exists and is continuous (jointly) as a function of
$(x,y)\in\Omega\times Y$. Then, the value function $v$ given by (1.4) is
Lipschitz and Clarke regular near $\bar{x}$, and

$\partial
v(\bar{x})=\operatorname*{co}\\{\nabla_{x}g(\bar{x},\bar{y}):\bar{y}\in
S(\bar{x})\\},$

where $S:{\rm I}\\!{\rm R}^{n}\rightrightarrows Y$ is given by

$S(x)\coloneqq\operatorname*{arg\,min}_{y\in Y}g(x,y).$

An extension of the above result to the nonsmooth case was also provided in
Bertsekas [1971] under additional structural assumption on $g$.

######  Theorem 2.2 (Extended Danskin’s Theorem).

Let $g:{\rm I}\\!{\rm R}^{n}\times Y\to{\rm I}\\!{\rm R}$ be given, where $Y$
is a compact subset of ${\rm I}\\!{\rm R}^{m}$. Suppose that for a
neighborhood $\Omega$ of $\bar{x}\in{\rm I}\\!{\rm R}^{n}$, $g$ is continuous
on $\Omega\times Y$, and for every $y\in Y$, the function $g(\cdot,y)$ is a
concave function on ${\rm I}\\!{\rm R}^{n}$. Then $v$ given by (1.4) is
concave on ${\rm I}\\!{\rm R}^{n}$ and

$\partial v(\bar{x})=P(\bar{x})\coloneqq\operatorname*{co}\\{\xi\in{\rm
I}\\!{\rm
R}^{n}:\xi\in\partial_{x}g(\bar{x},\bar{y})~{}\text{and}~{}\bar{y}\in
S(\bar{x})\\}.$ (2.3)

###### Proof.

The original result is stated for the maximum value function. Denoting
$\displaystyle V(x)\coloneqq\max_{y\in Y}\left(-g(x,y)\right)$, which is a
convex function, we have from [Bertsekas, 1971, Proposition A.22] that

$\partial^{c}V(\bar{x})=\operatorname*{co}\\{\xi\in{\rm I}\\!{\rm
R}^{n}:\xi\in\partial_{x}^{c}(-g(\bar{x},\bar{y}))~{}\text{and}~{}\bar{y}\in
S(\bar{x})\\}.$

Noting that $\partial v=\partial(-V)=-\partial V=-\partial^{c}V$, we get the
desired result. ∎

In Theorem 3.8, we further extend the above theorem to non-compact sets $Y$
under the assumption that $g$ is a uniform level-bounded function, in the
sense defined below; see Rockafellar and Wets [1998].

######  Definition 2.3.

A function $h:{\rm I}\\!{\rm R}^{m}\times{\rm I}\\!{\rm R}^{d}\to{\rm
I}\\!{\rm R}\cup\\{+\infty\\}$ with values $h(y,z)$ is _level-bounded in $y$
locally uniform in $z$_ if for each $z^{\prime}\in{\rm I}\\!{\rm R}^{d}$ and
$M\in{\rm I}\\!{\rm R}$, there exists an open ball $B$ around $z^{\prime}$
such that $\\{(y,z):z\in B,h(y,z)\leq M\\}$ is bounded. We also say that $h$
is a _uniformly level-bounded_ function.

We recall the following important result on uniform level-bounded functions;
see [Rockafellar and Wets, 1998, Theorem 1.17].

######  Theorem 2.4.

Let $h:{\rm I}\\!{\rm R}^{m}\times{\rm I}\\!{\rm R}^{d}\to{\rm I}\\!{\rm
R}\cup\\{+\infty\\}$ be a proper lower-semicontinuous function that is level-
bounded in $y\in{\rm I}\\!{\rm R}^{d}$ locally uniform in $z\in{\rm I}\\!{\rm
R}^{d}$. Define for all $z\in{\rm I}\\!{\rm R}^{d}$ the functions

$v(z)\coloneqq\min_{y\in{\rm I}\\!{\rm R}^{m}}h(y,z)\quad\text{and}\quad
S(z)\coloneqq\operatorname*{arg\,min}_{y\in{\rm I}\\!{\rm R}^{m}}h(y,z)$

and let $\bar{z}\in{\rm I}\\!{\rm R}^{d}$.

  1. (a)

If there exists $\bar{y}\in S(\bar{z})$ such that $h(\bar{y},\cdot)$ is
continuous on a set $U$ containing $\bar{z}$, then $v$ is continuous on $U$;
and

  2. (b)

If $v$ is continuous on a set $U$ containing $\bar{z}$, $\\{z^{k}\\}\subseteq
U$ such that $z^{k}\to\bar{z}$ and $\\{y^{k}\\}$ is a sequence such that
$y^{k}\in S(z^{k})$ for all $k$, then $\\{y^{k}\\}$ is bounded and its
accumulation points lie on $S(\bar{z})$.

###  2.2 Smooth approximations

We formally recall some concepts related to smooth approximations. The
definitions herein are adopted from Chen et al. [2011].

######  Definition 2.5.

Let $O\subseteq{\rm I}\\!{\rm R}^{d}$ be an open set. We say that
$\\{\phi_{\mu}:\mu>0\\}$ is a _family of smooth approximations_ for a
continuous function $\phi:O\to{\rm I}\\!{\rm R}$ over the set $O$ if
$\phi_{\mu}:O\to{\rm I}\\!{\rm R}$ is continuously differentiable and if for
all $\bar{z}\in O$, we have $\lim_{z\to\bar{z},\mu\to
0}\phi_{\mu}(z)=\phi(\bar{z})$.

With the availability of a smooth approximation, a traditional smoothing
method is as follows: Given a nonsmooth optimization problem (P) involving a
nonsmooth function $g$, we consider a smooth approximate problem (Pμ) obtained
by replacing $g$ with $g_{\mu}$. This is a convenient approach as there are
many powerful algorithms for dealing with smooth optimization problems, which
may then be used for solving (Pμ).

Intuitively, we expect that a sequence of solutions (or stationary points) of
(Pμ) with $\mu$ decreasing to zero will converge to a solution (or stationary
point) of the original problem (P). Theoretically, this is achieved through
the notion of gradient consistency defined as follows. Note that this property
is very important in characterizing stationary points of any smoothing method.

######  Definition 2.6.

Let $O\subseteq{\rm I}\\!{\rm R}^{d}$ be an open set and $\\{g_{\mu}:\mu>0\\}$
be a family of smoothing functions for a continuous function $g:O\to{\rm
I}\\!{\rm R}$ over the set $O$. This family is said to satisfy the _gradient
consistent property_ at $\bar{z}\in O$ if

$\emptyset\neq\limsup_{z\to\bar{z},\mu\searrow 0}\nabla
g_{\mu}(z)\subseteq\partial g(\bar{z}),$

where

$\limsup_{z\to\bar{z},\mu\searrow 0}\nabla
g_{\mu}(z)\coloneqq\left\\{\xi\in{\rm I}\\!{\rm
R}^{d}:\exists\\{z^{k}\\},\exists\\{\mu_{k}\\}~{}\emph{such
that}~{}z^{k}\to\bar{z},\mu_{k}\searrow 0~{}\emph{and}~{}\nabla
g_{\mu_{k}}(z^{k})\to\xi\right\\}.$

We now provide some examples of smooth approximations that satisfy gradient
consistency. We also highlight the uniform convergence of these smoothing
families, to illustrate the satisfiability of the hypotheses of some results
in Sections 3 and 4.

######  Example 2.7.

Chen and Mangasarian [1995] proposed a smooth approximation of the plus
function $\phi(z)=z_{+}=\max\\{z,0\\}$, $z\in{\rm I}\\!{\rm R}$, using
symmetric density functions $\rho$ with $\kappa\coloneqq\int_{{\rm I}\\!{\rm
R}}|s|\rho(s)ds<+\infty$. In particular, they defined

$\phi_{\mu}(z)\coloneqq\int_{{\rm I}\\!{\rm R}}(z-\mu s)_{+}\rho(s)ds,$

which satisfies the inequality $0\leq\phi_{\mu}(z)-\phi(z)\leq\kappa\mu$ for
all $z\in{\rm I}\\!{\rm R}$. With this, it is straightforward to see that
$\\{\phi_{\mu}:\mu>0\\}$ is a family of smooth approximations of $\phi$ in the
sense of Definition 2.5, and in addition, $\phi_{\mu}\to\phi$ uniformly on
${\rm I}\\!{\rm R}$. Moreover, it also holds that

$\limsup_{z\to\bar{z},\mu\searrow
0}\phi_{\mu}^{\prime}(z)\begin{cases}=\operatorname*{sgn}(\bar{z})&\text{if
}\bar{z}\neq 0\\\ \subseteq[0,1]&\text{if }\bar{z}=0\end{cases},$

and thus gradient consistency is satisfied. This smoothing is particularly
useful since many other loss functions and structure-promoting regularizers
are expressible in terms of the plus function (see Alcantara et al. [2021],
Chen [2012]).

######  Example 2.8.

The Moreau envelope of a closed proper function $\phi:{\rm I}\\!{\rm
R}^{n}\to{\rm I}\\!{\rm R}\cup\\{+\infty\\}$ is given by

$e_{\mu}\phi(z)\coloneqq\min_{u\in{\rm I}\\!{\rm
R}^{n}}\phi(u)+\frac{1}{2\mu}{\left\|{z-u}\right\|}^{2}.$

When $\phi$ is a convex function, $e_{\mu}\phi$ is $(\mu^{-1})-$smooth with
$\nabla e_{\mu}\phi(z)=\frac{1}{\mu}(z-p_{\mu}(z))$ where
$p_{\mu}(z)\coloneqq\operatorname*{arg\,min}_{u\in{\rm I}\\!{\rm
R}^{n}}\phi(u)+\frac{1}{2\mu}{\left\|{z-u}\right\|}^{2}$ [Rockafellar and
Wets, 1998, Theorem 2.26(b)]. Moreover, for any open subset
$\Omega\subseteq\operatorname*{int}(\operatorname*{dom}(\phi))$, we have
$0\leq\phi(z)-e_{\mu}\phi(z)\leq\frac{L_{\phi,\Omega}^{2}}{2}\mu$ for all
$z\in\Omega$, where $L_{\phi,\Omega}$ is the Lipschitz constant of $\phi$ on
$\Omega$ (see [Rockafellar and Wets, 1998, Example 9.14] and [Beck, 2017,
Theorem 10.51]). Hence, $\\{e_{\mu}\phi:\mu>0\\}$ is a family of smooth
approximations of $\phi$, and we also note that $e_{\mu}\phi$ converges to
$\phi$ uniformly on $\Omega$. Using [Liu et al., 2019, Lemma 1] and noting
that $\nabla e_{\mu}\phi(z)\in\partial\phi(p_{\mu}(z))$ and $\partial\phi$ is
upper semicontinuous, it is not difficult to check that the gradient
consistent property is satisfied.

######  Example 2.9.

Let $g:{\rm I}\\!{\rm R}^{n}\times{\rm I}\\!{\rm R}^{m}\to{\rm I}\\!{\rm R}$
be a convex function (that is, convex in $(x,y)$) and level-bounded in $y$
locally uniform in $x$. Then the value function $v$ given by (1.4) is convex
[Rockafellar and Wets, 1998, Theorem 10.13] and by Example 2.8,
$\\{v_{\mu}:\mu>0\\}$ where

$v_{\mu}(x)\coloneqq e_{\mu}(v(x))=\min_{z\in{\rm I}\\!{\rm R}^{n}}\min_{y\in
Y}g(z,y)+\frac{1}{2\mu}\|z-x\|^{2}$

is a family of smooth approximations of the value function satisfying gradient
consistency.

######  Example 2.10.

Let $g:{\rm I}\\!{\rm R}^{n}\times{\rm I}\\!{\rm R}^{m}\to{\rm I}\\!{\rm R}$
be such that $g(\cdot,y)$ is a concave function for all $y\in Y\subseteq{\rm
I}\\!{\rm R}^{m}$. Then $-v$ is a convex function and we may consider

$v_{\mu}(x)\coloneqq-e_{\mu}(-v(x))=\max_{z\in{\rm I}\\!{\rm R}^{n}}\min_{y\in
Y}g(z,y)-\frac{1}{2\mu}\|z-x\|^{2}$

as a family of smooth approximations of the value function satisfying gradient
consistency.

Aside from the restrictive structural assumptions on $g$, another main
drawback of the smoothing functions in the preceding two examples is that
function and gradient evaluations at a single point would require solving a
min-min or max-min optimization problems.

###  2.3 Necessary Optimality Conditions

We recall the definition of stationary point for the value function
reformulation ($\text{VFP}_{\epsilon}$) with $\epsilon\geq 0$.

######  Definition 2.11 (Stationary point[Ye et al., 2023, Definition 4]).

Let $(\bar{x},\bar{y})$ be a feasible point of ($\text{VFP}_{\epsilon}$) with
$\epsilon\geq 0$. We say that $(\bar{x},\bar{y})$ is a _stationary point_ of
($\text{VFP}_{\epsilon}$) if there exists $\lambda\geq 0$ such that

$\begin{cases}0\in\partial f(\bar{x},\bar{y})+\lambda\partial
g(\bar{x},\bar{y})-\lambda\partial v(\bar{x})\times\\{0\\}+N_{X\times
Y}(\bar{x},\bar{y})\\\
\lambda(g(\bar{x},\bar{y})-v(\bar{x})-\epsilon)=0\end{cases}$

The following result indicates that local minima of ($\text{VFP}_{\epsilon}$)
are stationary points in the sense of Definition 2.11. Note that since the
nonsmooth MFCQ automatically holds when $\epsilon>0$ (see [Ye et al., 2023,
Proposition 8]), the theorem below does not require any CQs, which are
typically essential in proving necessary optimality conditions. As mentioned
above, lack of a CQ for $\epsilon=0$ is the main hurdle when directly dealing
with the reformulation (VFP). Nevertheless, an analogous result as below can
be obtained by imposing so-called “partial calmness condition”. Since this is
not the main focus of the present manuscript, we refer the reader to Ye and
Daoli [1995], Ye et al. [2023] for further discussions.

######  Theorem 2.12 ([Ye et al., 2023, Theorem 4]).

If $(\bar{x},\bar{y})$ is a local optimal solution to
($\text{VFP}_{\epsilon}$) with $\epsilon>0$, then $(\bar{x},\bar{y})$ is a
stationary point of ($\text{VFP}_{\epsilon}$).

We now highlight the importance of gradient consistency when employing
smoothing techniques.

######  Proposition 2.13.

Let $\epsilon>0$. For each $\mu>0$, consider the smooth problem

$\displaystyle\begin{array}[]{rl}\displaystyle\min_{(x,y)\in X\times
Y}{}&f_{\mu}(x,y)\\\ \text{s.t.}{}&\displaystyle
g_{\mu}(x,y)-v_{\mu}(x)\leq\epsilon.\end{array}$
($\text{VFP}_{\epsilon}^{\mu}$)

where $\\{f_{\mu}:\mu>0\\}$, $\\{g_{\mu}:\mu>0\\}$ and $\\{v_{\mu}:\mu>0\\}$
are families of smooth approximations of $f$, $g$ and $v$, respectively, that
all satisfy the gradient consistent property. Let $\\{\mu_{k}\\}$ be a
sequence of positive numbers with $\mu_{k}\searrow 0$, and let $(x^{k},y^{k})$
be a stationary point of ($\text{VFP}_{\epsilon}^{\mu}$) with $\mu=\mu_{k}$,
and denote by $\lambda_{k}$ the corresponding Lagrange multiplier. If
$\\{(x^{k},y^{k},\lambda_{k})\\}$ is bounded, then its accumulation points are
stationary points of ($\text{VFP}_{\epsilon}$).

###### Proof.

From the KKT conditions of ($\text{VFP}_{\epsilon}^{\mu}$) with $\mu=\mu_{k}$,
we have that $(x^{k},y^{k})$ belongs to $X\times Y$ and satisfies the
conditions

$\begin{cases}0\in\nabla f_{\mu_{k}}(x^{k},y^{k})+\lambda_{k}\nabla
g_{\mu_{k}}(x^{k},y^{k})-\lambda_{k}\nabla
v_{\mu_{k}}(x^{k})\times\\{0\\}+N_{X\times Y}(x^{k},y^{k}),\\\ \lambda_{k}\geq
0,\quad g_{\mu_{k}}(x^{k},y^{k})-v_{\mu_{k}}(x^{k})-\epsilon\leq
0,\quad\lambda_{k}(g_{\mu_{k}}(x^{k},y^{k})-v_{\mu_{k}}(x^{k})-\epsilon)=0,\end{cases}$
(2.6)

for all $k$. We immediately get the desired result by noting the closedness of
$X\times Y$, invoking gradient consistency, and letting $k\to\infty$ in (2.6),
taking subsequences if necessary. ∎

Motivated by the above proposition, we propose smoothing techniques for the
value function that satisfy gradient consistency.

##  3 Quadratic Regularization

In this section, we consider the case when $g(x,\cdot)$ is a convex function
for each $x\in O_{X}$, which will be our standing assumption. We also assume
that we have a family $\\{g_{\mu}:\mu>0\\}$ of smooth approximations of $g$.
In this case, note that $\\{\tilde{g}_{\mu}:\mu>0\\}$ where

$\tilde{g}_{\mu}(x,y)\coloneqq g_{\mu}(x,y)+\frac{\mu}{2}\|y\|^{2},$ (3.1)

is likewise a family of smoothing functions for $g$.

###  3.1 Smooth approximation of the value function

Intuitively, we see that we may approximate the value function $v$ by
replacing the corresponding objective function $g$ by its smooth approximation
$\tilde{g}_{\mu}$ (or $g_{\mu}$). Here, we consider the functions
$v_{\mu}:{\rm I}\\!{\rm R}^{n}\to{\rm I}\\!{\rm R}$ and $S_{\mu}:{\rm
I}\\!{\rm R}^{n}\rightrightarrows{\rm I}\\!{\rm R}^{m}$ given by

$v_{\mu}(x)\coloneqq\min_{y\in Y}\tilde{g}_{\mu}(x,y)\quad\text{and}\quad
S_{\mu}(x)\coloneqq\operatorname*{arg\,min}_{y\in Y}\tilde{g}_{\mu}(x,y)$
(3.2)

where $\tilde{g}_{\mu}$ is given by (3.1). In the following discussion, we
show that $\\{v_{\mu}:\mu>0\\}$ is indeed a family of smoothing functions for
$v$.

######  Lemma 3.1.

Suppose that for any open set $\Omega$ with
$\operatorname*{cl}(\Omega)\subseteq O_{X}$, $g_{\mu}(x,y)$ is uniformly
bounded below over $\operatorname*{cl}(\Omega)\times Y$ for any $\mu>0$. If
$g_{\mu}(x,\cdot)$ is convex for any $x\in O_{X}$ and $\mu>0$, then $S_{\mu}$
given in (3.2) is a (single-valued) continuous function on $O_{X}$ for any
$\mu>0$.

###### Proof.

Note that $S_{\mu}$ is single-valued on $O_{X}$ by the strong convexity of
$\tilde{g}_{\mu}(x,\cdot)$ and the convexity of $Y$. To show continuity of
$S_{\mu}$ on $O_{X}$, let $\bar{x}\in O_{X}$ and $\Omega\subseteq O_{X}$ be a
neighborhood of $\bar{x}$ with closure in $O_{X}$. Given $\mu>0$, define
$h_{\mu}:{\rm I}\\!{\rm R}^{m}\times{\rm I}\\!{\rm R}^{n}\to{\rm I}\\!{\rm
R}\cup\\{+\infty\\}$ by

$h_{\mu}(y;x)\coloneqq\tilde{g}_{\mu}(x,y)+\delta_{\operatorname*{cl}(\Omega)\times
Y}(x,y)=g_{\mu}(x,y)+\frac{\mu}{2}\|y\|^{2}+\delta_{\operatorname*{cl}(\Omega)\times
Y}(x,y).$ (3.3)

Observe that

$v_{\mu}(x)=\min_{y\in{\rm I}\\!{\rm R}^{m}}h_{\mu}(y;x)\quad\text{and}\quad
S_{\mu}(x)=\operatorname*{arg\,min}_{y\in{\rm I}\\!{\rm R}^{m}}h_{\mu}(y;x)$
(3.4)

for any $x\in\operatorname*{cl}(\Omega)$. Now, consider the level set
$L_{\mu}(x;M)\coloneqq\\{y\in{\rm I}\\!{\rm R}^{m}:h_{\mu}(y;x)\leq M\\}$
where $M$ is any real number. Since $g_{\mu}(x,y)\geq m$ for all
$(x,y)\in\operatorname*{cl}(\Omega)\times Y$ for some constant $m$, it is not
difficult to see that $L_{\mu}(x,M)\subseteq B_{\delta}(0)$ for any
$x\in\operatorname*{cl}(\Omega)$, where
$\delta\coloneqq\max\\{2(M-m)/\mu,0\\}$. It follows that $h_{\mu}$ is level-
bounded in $y$ locally uniform in $x$, which permits the use of Theorem 2.4.
In particular, noting that $S_{\mu}(\bar{x})\neq\emptyset$, $h_{\mu}$ is a
continuous function on its closed domain, and using (3.4), we see from Theorem
2.4(a) that $v_{\mu}$ is continuous at $\bar{x}$. Consequently, given any
sequence $\\{x^{k}\\}\subseteq\Omega$ such that $x^{k}\to\bar{x}$, the
sequence $\\{S_{\mu}(x^{k})\\}$ is bounded and any accumulation point belongs
to $S_{\mu}(\bar{x})$ by Theorem 2.4(b). Since $S_{\mu}(\bar{x})$ is a
singleton, it follows that $S_{\mu}(x^{k})\to S_{\mu}(\bar{x})$. Hence,
$S_{\mu}$ is continuous at $\bar{x}$, as desired. ∎

######  Remark 3.2.

We make some comments about the uniform boundedness assumption in Lemma 3.1.

  1. 1.

If $Y$ is compact, this assumption automatically holds by the continuity of
$g_{\mu}$.

  2. 2.

Note that the uniform boundedness assumption holds for a wide class of bilevel
problems with unbounded $Y$. For instance, consider the class of
hyperparameter problems in Alcantara et al. [2021], where the lower-level
function takes the form

$g(x,y)=\ell(y)+\sum_{i=1}^{n}x_{i}p_{i}(y),$ (3.5)

where $\ell$ corresponds to a nonnegative loss function, $x$ is a
hyperparameter, and $p_{i}$ are (possibly nonsmooth) regularizers which are
nonnegative. The function $g$ along with the family of smoothing functions
derived in Alcantara et al. [2021] are uniformly bounded below by $0$ over
${\rm I}\\!{\rm R}^{n}_{+}\times{\rm I}\\!{\rm R}^{m}$. Hence, uniform
boundedness holds when $Y={\rm I}\\!{\rm R}^{m}$ and
$X=[\varepsilon_{1},\infty)\times\cdots\times[\varepsilon_{n},\infty)$, where
$\varepsilon_{i}>0$ for all $i$.

######  Remark 3.3.

If $g(x,\cdot)$ is convex for each $x\in O_{X}$, then its Moreau envelope
$e_{\mu}g(x,y)$ is convex in $y$ for any $x\in O_{X}$, which satisfies the
convexity requirement of the smoothing function $g_{\mu}$ in Lemma 3.1.

We mention that the differentiability of the value function associated with a
quadratically regularized smooth function of $(x,y)$ that is convex in $y$ has
already been noted in other works; for instance, see Liu et al. [2023]. Since
this is precisely the structure of the function $\tilde{g}_{\mu}$ (i.e., it is
the sum of $g_{\mu}$, a smooth function convex in $y$, and the quadratic term
$\mu\|y\|^{2}/2$), then $v_{\mu}$ given in (3.2) must be smooth. For the sake
of completeness, we present a simple proof of this result in the following
proposition. Moreover, we emphasize as well that in this paper, we prove that
the obtained function $v_{\mu}$ is a smooth approximation of $v$ in the sense
of Definition 2.5, which has not been shown in the literature yet. Even more
importantly, we establish the gradient consistency of this smoothing family,
which is instrumental in developing smoothing algorithms that converge to
stationary points of the bilevel problem (see Proposition 2.13).

######  Proposition 3.4.

Under the hypotheses of Lemma 3.1, $v_{\mu}$ is continuously differentiable on
$O_{X}$ with $\nabla v_{\mu}(x)=\nabla_{x}g_{\mu}(x,S_{\mu}(x))$.

###### Proof.

Fix $\bar{x}\in O_{X}$ and let $\bar{y}\coloneqq S_{\mu}(\bar{x})$. Given
$\varepsilon>0$, we have from Lemma 3.1 that there exists sufficiently small
$\delta>0$ such that $B_{\delta}(\bar{x})\subseteq O_{X}$ and for any $x\in
B_{\delta}(\bar{x})$, $S_{\mu}(x)\in B_{\varepsilon}(\bar{y})$. Let
$\hat{Y}\coloneqq{\rm cl}(B_{\varepsilon}(\bar{y}))\cap Y$. Moreover, define
$\hat{v}_{\mu}:{\rm I}\\!{\rm R}^{n}\to{\rm I}\\!{\rm R}$ and
$\hat{S}_{\mu}:{\rm I}\\!{\rm R}^{n}\to{\rm I}\\!{\rm R}^{m}$ as

$\hat{v}_{\mu}(x)\coloneqq\min_{y\in\hat{Y}}\tilde{g}_{\mu}(x,y)\quad\text{and}\quad\hat{S}_{\mu}(x)\coloneqq\operatorname*{arg\,min}_{y\in\hat{Y}}\tilde{g}_{\mu}(x,y).$

Observe that $v_{\mu}(x)\leq\hat{v}_{\mu}(x)$ for all $x\in{\rm I}\\!{\rm
R}^{n}$ and $\hat{S}_{\mu}$ is single-valued on $O_{X}$. Moreover, we have
from Theorem 2.1, Lemma 3.1 and [Clarke, 1983, Proposition 2.1.5(d)] that
$\hat{v}_{\mu}$ is continuously differentiable on $O_{X}$ with
$\nabla\hat{v}_{\mu}(x)=\nabla_{x}g_{\mu}(x,\hat{S}_{\mu}(x))$ for all $x\in
O_{X}$. In particular, these properties of $\hat{S}_{\mu}$ and $\hat{v}_{\mu}$
hold on the open subset $B_{\delta}(\bar{x})$. Meanwhile, by choice of
$\delta$, it follows that for any $x\in B_{\delta}(\bar{x})$, we have
$S_{\mu}(x)\in B_{\varepsilon}(\bar{y})\cap Y\subseteq\hat{Y}$. Hence,
$\tilde{g}_{\mu}(x,\hat{S}_{\mu}(x))\leq\tilde{g}_{\mu}(x,S_{\mu}(x))$; that
is, $\hat{v}_{\mu}(x)\leq v_{\mu}(x)$ for all $x\in B_{\delta}(\bar{x})$.
Consequently, noting the strong convexity of $\tilde{g}_{\mu}$ and the
convexity of $\hat{Y}$, we have $v_{\mu}\equiv\hat{v}_{\mu}$ and
$S_{\mu}\equiv\hat{S}_{\mu}$ on the open set $B_{\delta}(\bar{x})$. Hence,
$v_{\mu}$ is also continuously differentiable on $B_{\delta}(\bar{x})$ with
$\nabla
v_{\mu}(x)=\nabla_{x}g_{\mu}(x,\hat{S}_{\mu}(x))=\nabla_{x}g_{\mu}(x,S_{\mu}(x))$.
This completes the proof. ∎

When $\tilde{g}_{\mu}$ has a Lipschitz continuous gradient, the following
proposition shows that $S_{\mu}$ is Lipschitz continuous and $v_{\mu}$ has
Lipschitz continuous gradient over $O_{X}$.

######  Proposition 3.5.

Suppose that in addition to the hypotheses of Lemma 3.1, $\tilde{g}_{\mu}$ is
$L_{\mu}$-smooth. Then, $S_{\mu}$ is $(L_{\mu}/\mu)$-Lipschitz continuous and
$\nabla v_{\mu}$ is $(L_{\mu}\sqrt{1+L_{\mu}^{2}/\mu^{2}})$-Lipschitz
continuous on $O_{X}$.

###### Proof.

Since $\tilde{g}_{\mu}(x,\cdot)$ is $\mu$-strongly convex over $Y$, then
$\nabla_{y}\tilde{g}_{\mu}(x,\cdot)+N_{Y}(\cdot)$ is $\mu$-strongly monotone
over $Y$, where $N_{Y}$ denotes the normal cone to $Y$ [Beck, 2017, Theorem
5.24]. That is, for all $x\in O_{X}$,

$\left\langle\nabla_{y}\tilde{g}_{\mu}(x,y)+\eta_{y}-\nabla_{y}\tilde{g}_{\mu}(x,\bar{y})-\eta_{\bar{y}},y-\bar{y}\right\rangle\geq\mu\|y-\bar{y}\|^{2},$
(3.6)

for any $y,\bar{y}\in Y$, $\eta_{y}\in N_{Y}(y)$, and $\eta_{\bar{y}}\in
N_{Y}(\bar{y})$. Set $\bar{y}=S_{\mu}(x)$ and choose $\eta_{\bar{y}}\in
N_{Y}(\bar{y})$ so that
$\nabla_{y}\tilde{g}_{\mu}(x,\bar{y})+\eta_{\bar{y}}=0$. With these choices,
we have from (3.6) and Cauchy-Schwarz inequality that

$\|\nabla_{y}\tilde{g}_{\mu}(x,y)+\eta_{y}\|\geq\mu\|y-S_{\mu}(x)\|\quad\forall(x,y)\in
O_{X}\times Y,~{}~{}\forall\eta_{y}\in N_{Y}(y).$ (3.7)

Now let $x_{i}\in O_{X}$ and set $y_{i}\coloneqq S_{\mu}(x_{i})$ for $i=1,2$.
Choose $\eta_{y_{2}}\in N_{Y}(y_{2})$ such that
$\nabla_{y}\tilde{g}_{\mu}(x_{2},y_{2})+\eta_{y_{2}}=0$. We have from (3.7)
that

$\|\nabla_{y}\tilde{g}_{\mu}(x_{1},y_{2})+\eta_{y_{2}}\|\geq\mu\|y_{2}-S_{\mu}(x_{1})\|=\mu\|S_{\mu}(x_{2})-S_{\mu}(x_{1})\|.$

Meanwhile, since $\eta_{y_{2}}=-\nabla_{y}\tilde{g}_{\mu}(x_{2},y_{2})$ and
$\nabla\tilde{g}_{\mu}$ is $L_{\mu}$-Lipschitz continuous, we have

$\|\nabla_{y}\tilde{g}_{\mu}(x_{1},y_{2})+\eta_{y_{2}}\|=\|\nabla_{y}\tilde{g}_{\mu}(x_{1},y_{1})-\nabla_{y}\tilde{g}_{\mu}(x_{2},y_{1})\|\leq
L_{\mu}\|x_{1}-x_{2}\|.$

Combining the preceding two inequalities, we see that $S_{\mu}$ is
$(L_{\mu}/\mu)$-Lipschitz continuous. The claim about $\nabla v_{\mu}$ is
immediate by using the formula given in Proposition 3.4. ∎

Note that under a simple assumption that $g_{\mu}$ is uniformly lower-bounded,
we were able to conclude that $h_{\mu}$ given by (3.3) is level bounded in $y$
locally uniform in $x$ for a fixed $\mu$. With this, we obtained the
continuous differentiability of $v_{\mu}$ in Proposition 3.4. On the other
hand, our technique for proving that $v_{\mu}$ is a smoothing function for $v$
requires that $h_{\mu}(y;x)$ is level bounded in $y$ locally uniform jointly
in $(x,\mu)$, as shown in the following result.

######  Theorem 3.6.

Suppose that in addition to the hypotheses of Lemma 3.1, $g_{\mu}\to g$
uniformly on $\operatorname*{cl}(\Omega)\times Y$ and $g_{\mu}(x,y)$ is
continuous as a function of $(x,y,\mu)\in{\rm I}\\!{\rm R}^{n}\times{\rm
I}\\!{\rm R}^{m}\times{\rm I}\\!{\rm R}_{++}$. If $g$ is level-bounded in $y$
locally uniform in $x$, then $\\{v_{\mu}:\mu>0\\}$ is a family of smoothing
functions over $O_{X}$ for the value function $v$.

###### Proof.

Since $v_{\mu}$ is continuously differentiable on $O_{X}$ by Proposition 3.4,
it is enough to show that $\lim_{x\to\bar{x},\mu\to 0}v_{\mu}(x)=v(\bar{x})$
for any $\bar{x}\in O_{X}$. To this end, define $h:{\rm I}\\!{\rm
R}^{m}\times{\rm I}\\!{\rm R}^{n}\times{\rm I}\\!{\rm R}\to{\rm I}\\!{\rm
R}\cup\\{+\infty\\}$ as

$h(y;x,\mu)\coloneqq
h_{|\mu|}(y;x)=\begin{cases}g_{|\mu|}(x,y)+\frac{|\mu|}{2}\|y\|^{2}+\delta_{\operatorname*{cl}(\Omega)\times
Y}(x,y)&\text{if}~{}\mu\neq 0\\\
g(x,y)+\delta_{\operatorname*{cl}(\Omega)\times
Y}(x,y)&\text{if}~{}\mu=0\end{cases},$ (3.8)

where $\Omega$ is an open set containing $\bar{x}$ with
$\operatorname*{cl}(\Omega)\subseteq O_{X}$. For all
$(x,\mu)\in\operatorname*{cl}(O_{X})\times{\rm I}\\!{\rm R}$, define

$v_{\mu}(x)\coloneqq\min_{y\in{\rm I}\\!{\rm
R}^{m}}h(y;x,\mu)\quad\text{and}\quad
S_{\mu}(x)\coloneqq\operatorname*{arg\,min}_{y\in{\rm I}\\!{\rm
R}^{m}}h(y;x,\mu),$ (3.9)

which agree on the set $\operatorname*{cl}(\Omega)$ with the definitions of
$v_{\mu}$ and $S_{\mu}$ given in (3.2) when $\mu>0$. We now claim that
$v_{\mu}(x)$ viewed as a function of $(x,\mu)\in{\rm I}\\!{\rm
R}^{n}\times{\rm I}\\!{\rm R}$ is continuous on a neighborhood of
$(\bar{x},0)$. To this end, Theorem 2.4 asserts that it is enough to show that
(i) $h$ given by (3.8) is a proper lower semicontinuous function; (ii) $h$ is
level-bounded in $y$ locally uniform in $(x,\mu)$; and (iii) there exists
$\bar{y}\in S_{0}(\bar{x})=S(\bar{x})$ such that $h(\bar{y};x,\mu)$ is a
continuous function of $(x,\mu)$ in some neighborhood of $(\bar{x},0)$.

To prove (i), we use our hypothesis that $g_{\mu}(x,y)$ is continuous as a
function of $(x,y,\mu)$ on ${\rm I}\\!{\rm R}^{n}\times{\rm I}\\!{\rm
R}^{m}\times{\rm I}\\!{\rm R}_{++}$ to conclude that $h$ is lower
semicontinuous at any $(y,x,\mu)$ with $\mu\neq 0$. On the other hand, since
$g_{\mu}$ is a smoothing function of $g$, it follows from Definition 2.5 that
$h$ is also lower semicontinuous at any point $(y,x,0)$ with $(y,x)\in{\rm
I}\\!{\rm R}^{m}\times{\rm I}\\!{\rm R}^{n}$. In fact, we have that $h$ is
continuous on the set $Y\times\operatorname*{cl}(O_{X})\times{\rm I}\\!{\rm
R}$. From this, we also obtain claim (iii) by noting that
$S_{0}(\bar{x})=S(\bar{x})\neq\emptyset$ due to our uniform level-boundedness
assumption on $g$. It remains to show that (ii) holds. We need to show that
given any $M\in{\rm I}\\!{\rm R}$, there exists $\delta>0$ such that
$L(M;\delta)\coloneqq\\{(y,x,\mu):x\in
B_{\delta}(\bar{x}),|\mu|<\delta,~{}h(y;x,\mu)\leq M\\}$ is bounded. By the
uniform convergence hypothesis, there exists $\delta_{1}>0$ such that
$g_{\mu}(x,y)>g(x,y)-1$ for all $(x,y)\in\operatorname*{cl}(\Omega)\times Y$
and $\mu\in(0,\delta_{1})$. Then $h(y;x,\mu)\geq g(x,y)-1$ for all
$(x,y,\mu)\in{\rm I}\\!{\rm R}^{n}\times{\rm I}\\!{\rm
R}^{m}\times(-\delta_{1},\delta_{1})$. Since $g$ is level bounded in $y$
locally uniform in $x$, there exists $\delta_{2}>0$ such that $\\{(y,x):x\in
B_{\delta_{2}}(\bar{x}),~{}g(x,y)\leq M+1\\}$ is bounded. Choosing
$\delta\coloneqq\min\\{\delta_{1},\delta_{2}\\}$, the resulting set
$L(M;\delta)$ is in turn bounded, and therefore $h$ is level bounded in $y$
locally uniform in $(x,\mu)$. Hence, we have completed the proof that
$v_{\mu}(x)$ is continuous at $(\bar{x},0)$ for any $\bar{x}\in O_{X}$.
Consequently, by definition of continuity,

$\lim_{x\to\bar{x},\mu\to 0}v_{\mu}(x)=v_{0}(\bar{x})=\min_{y\in{\rm I}\\!{\rm
R}^{m}}~{}h(y;\bar{x},0)=\min_{y\in{\rm I}\\!{\rm
R}^{m}}g(\bar{x},y)+\delta_{Y}(y)=\min_{y\in Y}g(\bar{x},y)=v(\bar{x}),$

showing that $v_{\mu}$ is indeed a smoothing function for $V$. ∎

###  3.2 Danskin-type theorems and gradient consistency

We have shown above that regularized smoothing approximations
$\\{\tilde{g}_{\mu}:\mu>0\\}$ of $g$ lead to smoothing functions
$\\{v_{\mu}:\mu>0\\}$ for the value function $v$. Unfortunately, the gradient
consistent property is not necessarily inherited by the approximations for
$v$; that is, $\\{v_{\mu}:\mu>0\\}$ does not necessarily possess gradient
consistent property when $\\{\tilde{g}_{\mu}:\mu>0\\}$ has this property.
Fortunately, we can obtain gradient consistency for several classes of
functions $g$.

#### Danskin-type theorems

To prove gradient consistency of $\\{v_{\mu}:\mu>0\\}$, it is important to
determine what exactly the elements of the Clarke subdifferential111Note that
$v$ is Lipschitz continuous so that its Clarke subdifferential is well-
defined. This fact follows from the Lipschitz continuity of $g$. Indeed, given
$x$ and $\bar{x}$, denote $y\in S(x)$ and $\bar{y}\in S(\bar{x})$. Then
$v(x)-v(\bar{x})=g(x,y)-g(\bar{x},\bar{y})\leq
g(x,\bar{y})-g(\bar{x},\bar{y})\leq L\|x-\bar{x}\|$, where $L$ is the
Lipschitz constant of $g$. Reversing the roles of $x$ and $\bar{x}$, we
immediately get $|v(x)-v(\bar{x})|\leq L\|x-\bar{x}\|$. of $v$ are. For
compact sets $Y$, the subdifferential $\partial v$ is characterized by
Danskin’s Theorem (Theorem 2.1) for smooth functions $g$, and its extension
Eq. 2.3 for a nonsmooth $g$ that is concave in $x$. We now establish
extensions of these results for non-compact sets $Y$ by assuming uniform
level-boundedness of $g$.

We start with the following extension of the classical Danskin’s Theorem
(Theorem 2.1). This result should be well-known, and we provide a simple proof
for self-containednenss.

######  Theorem 3.7.

Let $g:{\rm I}\\!{\rm R}^{n}\times Y\to{\rm I}\\!{\rm R}$ be given, where $Y$
is a closed subset of ${\rm I}\\!{\rm R}^{m}$ and $g$ is level-bounded in $y$
locally uniform in $x$. Suppose that for a neighborhood $\Omega$ of
$\bar{x}\in{\rm I}\\!{\rm R}^{n}$, the derivative $\nabla_{x}g(x,y)$ exists
and is continuous (jointly) as a function of $(x,y)\in\Omega\times Y$. Then
the value function $v$ given by (1.4) is Lipschitz and Clarke regular near
$\bar{x}$, and

$\partial
v(\bar{x})=\operatorname*{co}\\{\nabla_{x}g(\bar{x},\bar{y}):\bar{y}\in
S(\bar{x})\\},$

where $S(x)\coloneqq\operatorname*{arg\,min}_{y\in Y}g(x,y).$

###### Proof.

Set $M\coloneqq\max_{x\in\operatorname*{cl}(B_{1}(\bar{x}))}g(x,y^{\prime})$
for some fixed and arbitrarily chosen $y^{\prime}\in Y$. Note that by
continuity of $g$, $M$ is finite. By uniform level-boundedness of $g$, there
exists some ball $B_{\alpha}(\bar{x})$ with $\alpha<1$ such that
$\\{(x,y):x\in\operatorname*{cl}(B_{\alpha}(\bar{x})),g(x,y)\leq M\\}$ is
bounded. Since $\alpha<1$, then

$\bigcup_{x\in\operatorname*{cl}(B_{\alpha}(\bar{x}))}S(x)\subseteq\bigcup_{x\in\operatorname*{cl}(B_{\alpha}(\bar{x}))}\\{y\in
Y:g(x,y)\leq M\\}.$

It follows that
$\hat{Y}\coloneqq\bigcup_{x\in\operatorname*{cl}(B_{\alpha}(\bar{x}))}S(x)$ is
a bounded set. If we have a sequence $\\{y^{k}\\}\subseteq\hat{Y}$ such that
$y^{k}\to y^{*}$, then there exists
$x^{k}\in\operatorname*{cl}(B_{\alpha}(\bar{x}))$ such that
$g(x^{k},y^{k})\leq g(x^{k},y)$ for all $k$ and for all $y\in Y$. We may
assume without loss of generality that $x^{k}\to x^{*}$ where
$x^{*}\in\operatorname*{cl}(B_{\alpha}(\bar{x}))$. Noting the continuity of
$g$, we have $g(x^{*},y^{*})\leq g(x^{*},y)$ for all $y\in Y$ so that
$y^{*}\in S(x^{*})$. Hence, $y^{*}\in\hat{Y}$ and therefore $\hat{Y}$ is in
fact compact. Consider now the functions

$\hat{v}(x)\coloneqq\min_{y\in\hat{Y}}g(x,y)\quad\text{and}\quad\hat{S}(x)\coloneqq\operatorname*{arg\,min}_{y\in\hat{Y}}g(x,y).$

Since the global minimizers of $g(x,\cdot)$ are contained in $\hat{Y}$ for any
$x\in\operatorname*{cl}(B_{\alpha}(\bar{x}))$, it follows that $\hat{S}\equiv
S$ on $\operatorname*{cl}(B_{\alpha}(\bar{x}))$. In particular, $\hat{v}\equiv
v$ on the open set $B_{\alpha}(\bar{x})$ so that their Clarke subdifferentials
agree. Hence, together with Danskin’s theorem, $\partial
v(\bar{x})=\partial\hat{v}(\bar{x})=\operatorname*{co}\\{\nabla_{x}g(\bar{x},\bar{y}):\bar{y}\in\hat{S}(\bar{x})\\}=\operatorname*{co}\\{\nabla_{x}g(\bar{x},\bar{y}):\bar{y}\in{S}(\bar{x})\\}$.
This completes the proof. ∎

On the other hand, the following theorem is an extension of Eq. 2.3 that is
applicable for unbounded closed sets $Y$ provided that $g$ is uniformly level-
bounded. Moreover, we also relax the concavity assumption to weak concavity.
Recall that given a convex set $\Omega$, a function $h$ is $\rho$-weakly
convex on $\Omega$ if $h+\frac{\rho}{2}\|\cdot\|^{2}$ is convex on $\Omega$,
where $\rho>0$. We say that $h$ is $\rho$-weakly concave on $\Omega$ if $-h$
is a weakly convex function on $\Omega$.

######  Theorem 3.8.

Let $g:{\rm I}\\!{\rm R}^{n}\times Y\to{\rm I}\\!{\rm R}$ be level-bounded in
$y$ locally uniform in $x$, where $Y$ is a closed subset of ${\rm I}\\!{\rm
R}^{m}$. Suppose that for a convex neighborhood $\Omega$ of $\bar{x}\in{\rm
I}\\!{\rm R}^{n}$ and an open set $O_{Y}$ containing $Y$, $g$ is Lipschitz
continuous on $\Omega\times O_{Y}$ and $g(\cdot,y)$ is a $\rho$-weakly concave
function on $\Omega$ for every $y\in O_{Y}$. Then $v$ given by (1.4) is weakly
concave on $\Omega$ and

$\displaystyle\partial v(\bar{x})=P(\bar{x})=\operatorname*{co}\\{\xi\in{\rm
I}\\!{\rm
R}^{n}:\xi\in\partial_{x}g(\bar{x},\bar{y})~{}\text{and}~{}\bar{y}\in
S(\bar{x})\\}.$ (3.10)

###### Proof.

Define $h\coloneqq-g$, so that $V(x)\coloneqq\max_{y\in Y}h(x,y)=-v(x)$ and
$h(\cdot,y)$ is $\rho$-weakly convex on $\Omega$ for each $y\in O_{Y}$. It
follows that $\hat{h}(\cdot,y)\coloneqq
h(\cdot,y)+\frac{\rho}{2}\|\cdot\|^{2}$ is a convex function on $\Omega$, and
therefore the maximum over all $y\in Y$ is convex on $\Omega$. That is,

$\max_{y\in Y}\hat{h}(x,y)=\max_{y\in
Y}\left(h(x,y)+\frac{\rho}{2}\|x\|^{2}\right)=\left(\max_{y\in
Y}h(x,y)\right)+\frac{\rho}{2}\|x\|^{2}=V(x)+\frac{\rho}{2}\|x\|^{2}\eqqcolon\hat{V}(x)$

is convex on $\Omega$, which proves that $V$ is $\rho$-weakly convex on
$\Omega$. Hence, $v$ is $\rho$-weakly concave on $\Omega$.

Let $d\in{\rm I}\\!{\rm R}^{n}$, $t_{k}\searrow 0$, and denote
$x^{k}\coloneqq\bar{x}+t_{k}d$ and $y^{k}\in S(x^{k})$. Note that given any
$y\in S(\bar{x})$,

$\displaystyle\frac{\hat{V}(\bar{x}+t_{k}d)-\hat{V}(\bar{x})}{t_{k}}$
$\displaystyle=\frac{\hat{h}(\bar{x}+t_{k}d,y^{k})-\hat{h}(\bar{x},y)}{t_{k}}\geq\frac{\hat{h}(\bar{x}+t_{k}d,y)-\hat{h}(\bar{x},y)}{t_{k}}$

Letting $k\to\infty$, we have

$\hat{V}^{\prime}(\bar{x};d)\geq\hat{h}_{y}^{\prime}(\bar{x};d),\quad\forall
y\in S(\bar{x}),$ (3.11)

where $\hat{h}_{y}^{\prime}(\bar{x};d)$ denotes the directional derivative of
$h(\cdot,y)$ at $\bar{x}$ in the direction $d$. Meanwhile, we also have

$\displaystyle\frac{\hat{V}(\bar{x}+t_{k}d)-\hat{V}(\bar{x})}{t_{k}}$
$\displaystyle=\frac{\hat{h}(\bar{x}+t_{k}d,y^{k})-\hat{h}(\bar{x},y)}{t_{k}}\leq\frac{\hat{h}(\bar{x}+t_{k}d,y^{k})-\hat{h}(\bar{x},y^{k})}{t_{k}}.$
(3.12)

Note that since $g$ is level-bounded in $y$ locally uniform in $x$, we have
from Theorem 2.4 that $\\{y^{k}\\}$ is bounded with accumulation points lying
in $S(\bar{x})$. Hence, we may assume without loss of generality that
$y^{k}\to\bar{y}\in S(\bar{x})$. Letting $k\to\infty$ in (3.12) and from the
definition of the Clark generalized directional derivative, we see that

$\hat{V}^{\prime}(\bar{x};d)\leq\hat{h}^{\circ}(\bar{x},\bar{y};d,0).$ (3.13)

From the max formula (2.2) for Clarke generalized directional derivative, we
have

$\hat{h}^{\circ}(\bar{x},\bar{y};d,0)=\max\\{\langle\zeta,(d,0)\rangle:\zeta\in\partial\hat{h}(\bar{x},\bar{y})\\}=\max\\{\langle\zeta_{x},d\rangle:\zeta_{x}\in\pi_{x}(\partial\hat{h}(\bar{x},\bar{y}))\\},$
(3.14)

where $\pi_{x}$ is defined as in (2.1). On the other hand, by the convexity of
$\hat{h}(\cdot,y)$ for all $y$ on some neighborhood of $\bar{y}$, we have from
[Clarke, 1983, Proposition 2.5.3] that
$\pi_{x}(\partial\hat{h}(\bar{x},\bar{y}))\subseteq\partial_{x}\hat{h}(\bar{x},\bar{y})$.
From (3.14), we conclude that

$\hat{h}^{\circ}(\bar{x},\bar{y};d,0)\leq\max\\{\langle\zeta_{x},d\rangle:\zeta_{x}\in\partial_{x}\hat{h}(\bar{x},\bar{y})\\}=\hat{h}_{\bar{y}}^{\prime}(\bar{x};d),$
(3.15)

where the last equation holds by the max formula for the (usual) directional
directive for the convex function $\hat{h}_{\bar{y}}$. Combining (3.11),
(3.13) and (3.15) while noting that $\bar{y}\in S(\bar{x})$, we conclude that

$\displaystyle\hat{V}^{\prime}(\bar{x};d)=\max_{y\in
S(\bar{x})}\hat{h}_{y}^{\prime}(\bar{x};d)$ $\displaystyle=\max_{y\in
S(\bar{x})}\max_{\zeta\in\partial_{x}\hat{h}_{y}(\bar{x})}\langle\zeta,d\rangle$
$\displaystyle=\max\left\\{\langle\zeta,d\rangle:\zeta\in\bigcup_{y\in
S(\bar{x})}\partial_{x}\hat{h}(\bar{x},y)\right\\}$
$\displaystyle=\max\left\\{\langle\zeta,d\rangle:\zeta\in\operatorname*{cl}\left(\operatorname*{co}\left(\bigcup_{y\in
S(\bar{x})}\partial_{x}\hat{h}(\bar{x},y)\right)\right)\right\\},$

where the last equation holds by [Beck, 2017, Lemma 2.35]. Noting the upper
semicontinuity of $\partial h$ and compactness of $S(\bar{x})$, we obtain the
compactness of $\bigcup_{y\in S(\bar{x})}\partial_{x}\hat{h}(\bar{x},y)$, and
therefore its convex hull is likewise compact [Rudin, 1991, Theorem 3.20].
Thus, we may equivalently write

$\hat{V}^{\prime}(\bar{x};d)=\max\left\\{\langle\zeta,d\rangle:\zeta\in\operatorname*{co}\left(\bigcup_{y\in
S(\bar{x})}\partial_{x}\hat{h}(\bar{x},y)\right)\right\\}.$

Meanwhile, we have from the convexity of $\hat{V}$ that
$\hat{V}^{\prime}(\bar{x};d)=\max_{\xi\in\partial\hat{V}(\bar{x})}\langle\xi,d\rangle$.
By the closedness and convexity of both $\partial\hat{V}(\bar{x})$ and
$\operatorname*{co}\left(\bigcup_{y\in
S(\bar{x})}\partial_{x}\hat{h}(\bar{x},y)\right)$, we have from [Beck, 2017,
Lemma 2.34] that

$\partial\hat{V}(\bar{x})=\operatorname*{co}\left(\bigcup_{y\in
S(\bar{x})}\partial_{x}\hat{h}(\bar{x},y)\right).$

Subtracting $\rho\bar{x}$ from both sides of the above equation, we see that
$\partial V(\bar{x})=\operatorname*{co}\left(\bigcup_{y\in
S(\bar{x})}\partial_{x}h(\bar{x},y)\right)$. From here, we immediately obtain
(3.10), thus completing the proof. ∎

We also take note of the following special case which should also be well-
known, but a proof is provided for completeness.

######  Theorem 3.9.

Let $g(x,y)$ be convex in $(x,y)$ and level-bounded in $y$ locally uniform in
$x$. If the partial differentiation formula

$\partial
g(\bar{x},\bar{y})=\partial_{x}g(\bar{x},\bar{y})\times\partial_{y}g(\bar{x},\bar{y})$
(3.16)

holds for all $\bar{y}\in S(\bar{x})$, then

$\partial v(\bar{x})=\partial_{x}g(\bar{x},\bar{y}),$

where $\bar{y}$ can be arbitrarily chosen from $S(\bar{x})$.

###### Proof.

Since $g$ is convex in $(x,y)$, we have from [Rockafellar and Wets, 1998,
Theorem 10.13] that $\partial v(\bar{x})=\\{\xi\in{\rm I}\\!{\rm
R}^{n}:(\xi,0)\in\partial\left(g(\bar{x},\bar{y})+\delta_{Y}(\bar{y})\right)\\}$
where $\bar{y}$ can be arbitrarily chosen from $S(\bar{x})$. Meanwhile,
$\partial\left(g(\bar{x},\bar{y})+\delta_{Y}(\bar{y})\right)=\partial
g(\bar{x},\bar{y})+\left(\\{0\\}\times N_{Y}(\bar{y})\right)$ by [Beck, 2017,
Theorem 3.36(a)] and [Clarke, 1983, Corollary 1 of Theorem 2.9.8], noting that
$g$ is Lipschitz continuous. Further applying (3.16), we then obtain

$\partial v(\bar{x})=\left\\{\xi\in{\rm I}\\!{\rm
R}^{n}:(\xi,0)\in\partial_{x}g(\bar{x},\bar{y})\times\left(\partial_{y}g(\bar{x},\bar{y})+N_{Y}(\bar{y})\right)\right\\}=\partial_{x}g(\bar{x},\bar{y})\quad\forall\bar{y}\in
S(\bar{x}),$

where the last equality holds by the optimality of $\bar{y}$, noting the
convexity of $g$ and $Y$. ∎

We note that for a convex function $g$, we always have $\partial
g(\bar{x},\bar{y})\subseteq\partial_{x}g(\bar{x},\bar{y})\times\partial_{y}g(\bar{x},\bar{y})$.
More generally, this inclusion holds when $g$ is Clarke regular at
$(\bar{x},\bar{y})$ by [Clarke, 1983, Proposition 2.3.15]. Conditions under
which equality holds, as required by condition (3.16), are provided in [Ye et
al., 2023, Proposition 1].

#### Gradient consistency

With the above characterizations of the Clarke subdifferential of the value
function, we can now derive the gradient consistency of the proposed smoothing
family $\\{v_{\mu}:\mu>0\\}$ given in (3.2). Our main tool is the following
simple lemma.

######  Lemma 3.10.

Suppose that the hypotheses of Theorem 3.6 hold and that $\\{g_{\mu}:\mu>0\\}$
is a smoothing family of functions that satisfies the gradient consistent
property. Let $\bar{x}\in O_{X}$ and suppose that

$\pi_{x}(\partial
g\left(\bar{x},\bar{y})\right)\subseteq\partial_{x}g(\bar{x},\bar{y})\quad\forall\bar{y}\in
S(\bar{x}),$ (3.17)

and $\\{\nabla g_{\mu}(x,y):(x,y,\mu)\in\Theta\\}$ is bounded222This condition
is easily satisfied by several smoothing functions; see Section 2.2 and
Alcantara et al. [2021], Chen [2012]. for some neighborhood $\Theta$ of
$(\bar{x},\bar{y},0)$ for $\bar{y}\in S(\bar{x})$. Then

$\emptyset\neq\limsup_{x\to\bar{x},\mu\to 0}\nabla
v_{\mu}(x)\subseteq\bigcup_{\bar{y}\in
S(\bar{x})}\partial_{x}g(\bar{x},\bar{y}).$ (3.18)

###### Proof.

Consider any sequence $\mu_{k}\searrow 0$ and $x^{k}\to\bar{x}$. That
$\limsup_{x\to\bar{x},\mu\to 0}\nabla v_{\mu}(x)$ is non-empty holds due to
our boundedness assumption. Suppose that $\nabla v_{\mu_{k}}(x^{k})\to\xi$. By
Proposition 3.4, $\nabla_{x}g_{\mu_{k}}(x^{k},y^{k})\to\xi$ where
$y^{k}=S_{\mu_{k}}(x^{k})$. Using (3.9), the uniform level boundedness of $h$
given by (3.8), and Theorem 2.4(b), we know that $\\{y^{k}\\}$ is bounded with
accumulation points in $S(\bar{x})$, and so we may assume without loss of
generality that $y^{k}\to\bar{y}\in S(\bar{x})$. Meanwhile, using again our
boundedness assumption, note that $\nabla g_{\mu_{k}}(x^{k},y^{k})$ is bounded
so that we may assume without loss of generality that it converges to a point
$(\xi,\eta)$, which belongs to $\partial g(\bar{x},\bar{y})$ by gradient
consistency of $\\{g_{\mu}:\mu>0\\}$. With (3.17), we infer that
$\xi\in\partial_{x}g(\bar{x},\bar{y})$ and therefore (3.18) holds. ∎

In general, under some regularity conditions (see [Rockafellar and Wets, 1998,
Definition 7.25]) and the assumption that $g(x,\cdot)$ is convex for all $x\in
O_{X}$, we can only obtain

$\partial v(\bar{x})\subseteq\bigcup_{\bar{y}\in
S(\bar{x})}\partial_{x}g(\bar{x},\bar{y})$ (3.19)

by using [Rockafellar and Wets, 1998, Theorem 10.13], [Clarke, 1983,
Proposition 2.3.15], and [Clarke, 1983, Corollary 1 of Theorem 2.9.8]. Hence,
(3.18) is in general a weaker result as it only guarantees that
$\limsup_{x\to\bar{x},\mu\to 0}\nabla v_{\mu}(x)$ is contained on the right
hand side of (3.19). Nevertheless, with the above, we immediately obtain the
gradient consistency of $\\{v_{\mu}:\mu>0\\}$ for several special cases.

######  Theorem 3.11.

Suppose that the hypotheses of Theorem 3.6 hold and that $\\{g_{\mu}:\mu>0\\}$
is a smoothing family of functions satisfying the gradient consistent
property. Let $\bar{x}\in O_{X}$ and suppose that $\\{\nabla
g_{\mu}(x,y):(x,y,\mu)\in\Theta\\}$ is bounded for some neighborhood $\Theta$
of $(\bar{x},\bar{y},0)$ for $\bar{y}\in S(\bar{x})$. Then, under any of the
following conditions, $\\{v_{\mu}:\mu>0\\}$ is a family of smooth
approximations of $v$ that satisfies the gradient consistent property at
$\bar{x}$:

  1. (a)

$\nabla_{x}g(x,y)$ exists and is continuous on $\Omega\times Y$;

  2. (b)

$g(\cdot,y)$ is $\rho$-weakly concave on $\Omega$ for all $y\in O_{Y}$; or

  3. (c)

(3.16) holds and $g$ is convex in $(x,y)$,

where $\Omega$ is a neighborhood of $\bar{x}$.

###### Proof.

We first show that condition (3.17) holds for each of the cases described. To
this end, let $\xi\in\pi_{x}(\partial g(\bar{x},\bar{y}))$ and let
$\eta\in{\rm I}\\!{\rm R}^{m}$ such that $(\xi,\eta)\in\partial
g(\bar{x},\bar{y})$. For (a), it is enough to show that
$\xi=\nabla_{x}g(\bar{x},\bar{y})$. Let $\\{(x^{k},y^{k})\\}$ be a sequence
converging to $(\bar{x},\bar{y})$ such that $g$ is differentiable at each
$(x^{k},y^{k})$ and $\\{\nabla g(x^{k},y^{k})\\}$ is convergent. By continuity
of $\nabla_{x}g$, we conclude that
$\nabla_{x}g(x^{k},y^{k})\to\nabla_{x}g(\bar{x},\bar{y})$. It now directly
follows from [Clarke, 1983, Theorem 2.5.1] that
$\xi=\nabla_{x}g(\bar{x},\bar{y})$, proving that (3.17) holds. For (b), we
have from [Clarke, 1983, Proposition 2.5.3] that
$\pi_{x}\left(\partial\hat{h}(\bar{x},\bar{y})\right)\subseteq\partial_{x}\hat{h}(\bar{x},\bar{y})$
where $\hat{h}(x,y)\coloneqq h(x,y)+\frac{\rho}{2}\|x\|^{2}$ and $h=-g$ as in
the proof of Theorem 3.8. The inclusion (3.17) immediately follows. Lastly, in
part (c), the hypothesis that (3.16) holds directly implies (3.17). Hence, we
may use Lemma 3.10. By Theorem 3.7, Theorem 3.8 and Theorem 3.9, which can be
applied for cases (a), (b) and (c), respectively, the right-hand side of
(3.18) is either equal to or contained in $\partial v(\bar{x})$. Hence,
gradient consistency holds at $\bar{x}$. ∎

##  4 Entropic Regularization

Lin et al. [2014] proposed the function
$x\mapsto-\mu\ln\left(\int_{Y}\exp\left(-\mu^{-1}g(x,y)\right)dy\right)$ as a
smooth approximation333For an intuitive interpretation of this smoothing
function, recall that a usual approximation of
$\max\\{x_{1},x_{2},\dots,x_{r}\\}$ is
$\mu\ln\sum_{i=1}^{r}\exp(\mu^{-1}x_{i})$. We may thus view the given
smoothing function as a continuous extension of this approximation. of the
value function when $g$ is smooth and $Y$ is a compact set. This is based on
the earlier works of Fang and Wu [1996], Li and Fang [1997] on smoothing by
entropic regularization for the maximum value function. A natural way to
extend this to a nonsmooth function $g$ is to replace $g$ with a smooth
approximation. That is, if $\\{g_{\mu}:\mu>0\\}$ is a family of smooth
approximations of $g$, then we consider

$v_{\mu}(x)\coloneqq-\mu\ln\left(\int_{Y}\exp\left(-\mu^{-1}g_{\mu}(x,y)\right)dy\right)$
(4.1)

as a smooth approximation of the value function.

We show that when $Y$ is a compact set, the function (4.1) is indeed a smooth
approximation of $v$ which satisfies gradient consistency under certain
conditions. In fact, we can further extend this result to the case when $Y$ is
non-compact by replacing $Y$ in (4.1) with $Y_{\mu}$, where
$\\{Y_{\mu}:\mu>0\\}$ is a family of compact subsets of $Y$ such that
$Y_{\mu}\nearrow Y$. These considerably extend the smoothing framework of Li
and Fang [1997], Lin et al. [2014] to unbounded closed sets and nonsmooth
functions. Such an extension is not trivial, neccessitating subtle
modifications to the proofs established for the compact case, as well as
sufficient conditions required to obtain a smoothing family and gradient
consistency. These intricacies are systematically discussed in this
manuscript. To concentrate on the main ideas, we focus first on the compact
case in Section 4.1, and then present analogous results for the noncompact
case in Section 4.2.

###  4.1 Entropic regularization for bounded constraint set

We start by proving that $v_{\mu}$ given by (4.1) is continuously
differentiable.

######  Proposition 4.1.

Suppose that $Y$ is compact and $\\{g_{\mu}:\mu>0\\}$ is a family of smooth
approximations of $g$ over some open set $O_{X}\times O_{Y}$. Then for each
$\mu>0$, $v_{\mu}$ given by (4.1) is continuously differentiable on $O_{X}$.

###### Proof.

Let $\Omega$ be any bounded open set whose closure is contained in $O_{X}$.
Note that by the continuity of $g_{\mu}$,
$\|\nabla_{x}\exp\left(-\mu^{-1}g_{\mu}(x,y)\right)\|$ is uniformly bounded
over $\operatorname*{cl}(\Omega)\times Y$ by any constant $c$ such that

$c\geq\max_{(x,y)\in\operatorname*{cl}(\Omega)\times
Y}\mu^{-1}\exp(\mu^{-1}g_{\mu}(x,y))\|\nabla_{x}g_{\mu}(x,y)\|,$

By Leibniz rule, we obtain

$\nabla
v_{\mu}(x)=\int_{Y}\alpha_{\mu}(x,y)\nabla_{x}g_{\mu}(x,y)dy\quad\forall
x\in\Omega,$ (4.2)

where

$\alpha_{\mu}(x,y)\coloneqq\frac{\exp(-\mu^{-1}g_{\mu}(x,y))}{\int_{Y}\exp(-\mu^{-1}g_{\mu}(x,z))dz}.$
(4.3)

We now show that $\nabla v_{\mu}$ is continuous on $\Omega$. First, we claim
that $\alpha_{\mu}$ is a continuous function on $\Omega\times Y$. Note that
$\exp(-\mu^{-1}g_{\mu}(x,z))$ is uniformly bounded above by some constant over
the compact set $\operatorname*{cl}(\Omega)\times Y$. Hence, continuity of
$\alpha_{\mu}$ on $\Omega\times Y$ holds by the bounded convergence theorem.
By continuity of $\alpha_{\mu}$ and $\nabla_{x}g_{\mu}$, we can again apply
the same argument to show that $\nabla v_{\mu}$ is continuous on $\Omega$.
Since $\Omega$ is arbitrarily chosen, we have completed the proof. ∎

We now show that $\\{v_{\mu}:\mu>0\\}$ is a family of smooth approximations in
the sense of Definition 2.5. We need the following lemma.

######  Lemma 4.2.

Let $Y$ be a compact set, $g$ be a Lipschitz continuous function on some open
set $O_{X}\times O_{Y}$ containing $X\times Y$, and let $\Omega$ be any convex
open set such that $\operatorname*{cl}(\Omega)\subseteq O_{X}$. For any
$\tau\in(0,1)$, there exists $\delta>0$ such that for any $\mu\in(0,\delta)$,

$\tau(\mu\operatorname*{vol}(Y))^{\mu}\max_{y\in
Y}\exp(-g(x,y))\leq\left(\int_{Y}\exp\left(-\mu^{-1}g(x,y)\right)dy\right)^{\mu}\quad\forall
x\in\operatorname*{cl}(\Omega).$ (4.4)

###### Proof.

From the proof of [Fang and Wu, 1996, Theorem 1], the result follows if we can
show that for any $\tau\in(0,1)$, there exists a sufficiently large $N$ such
that

$\displaystyle\max_{j=1,2,\dots,k}~{}~{}\min_{y\in
Y_{j}}\exp(-g(x,y))>\tau\cdot\max_{y\in Y}\exp(-g(x,y))\quad\forall
x\in\operatorname*{cl}(\Omega)$ (4.5)

holds for all integers $k\geq N$ and any partition
$\\{Y_{1},Y_{2},\dots,Y_{k}\\}$ of $Y$ with
$\max_{j=1,2,\dots,k}\operatorname*{diam}(Y_{j})\to 0$ as $k\to\infty$, where
$\operatorname*{diam}(Y_{j})$ is the diameter of $Y_{j}$. This is similar to
[Fang and Wu, 1996, Lemma 2] where the inequality (4.5) holds on the set $X$
but the function $g$ should be such that $g(\cdot,y)$ is continuously
differentiable for any $y\in Y$. We show that the result can be extended to
the setting described in Lemma 4.2.

For the sake of contradiction, suppose that there exists $\tau\in(0,1)$, a
sequence $\\{x^{k}\\}\subseteq\operatorname*{cl}(\Omega)$, and integers
$i_{k}$ with $i_{k}\to\infty$ such that

$\frac{\displaystyle\max_{j=1,2,\dots,i_{k}}~{}~{}\min_{y\in
Y_{j}}\exp(-g(x,y))}{\tau\cdot\max_{y\in Y}\exp(-g(x,y))}\leq 1$

for some partition $\\{Y_{1},Y_{2},\dots,Y_{i_{k}}\\}$ with
$\max_{j=1,2,\dots,i_{k}}\operatorname*{diam}(Y_{j})\to\infty$ as
$k\to\infty$. By the compactness of $\operatorname*{cl}(\Omega)$, we may
assume that $x^{k}\to x^{*}$ for some $x^{*}\in\operatorname*{cl}(\Omega)$.
Now, we use the mean-value theorem for Lipschitz continuous functions. Noting
that $\operatorname*{cl}(\Omega)\subseteq O_{X}$, we have from [Clarke, 1983,
Theorem 2.3.7] that there exists $u^{k}$ in the relative interior of the line
segment joining $x^{*}$ and $x^{k}$ such that

$\exp(-g(x^{k},y))-\exp(-g(x^{*},y))\in\langle\partial
h_{y}(u^{k}),x^{k}-x^{*}\rangle,$

where $h_{y}(x)\coloneqq\exp(-g(x,y))$. By Theorem 2.3.9(ii) and Proposition
2.3.1 of Clarke [1983], we have

$\exp(-g(x^{k},y))-\exp(-g(x^{*},y))=-\langle\exp(-g(u^{k},y))v^{k},x^{k}-x^{*}\rangle,$
(4.6)

where $v^{k}\in\partial_{x}g(u^{k},y)$. Meanwhile, noting the convexity of
$\operatorname*{cl}(\Omega)$, each $u^{k}$ is in
$\operatorname*{cl}(\Omega)\subseteq O_{X}$. On the other hand, $\partial
g(u,y)$ is a compact set for any $(u,y)$ by [Facchinei and Pang, 2003,
Proposition 7.1.4(a)]. Hence, with the upper-semicontinuity of the Clarke
subdifferential (see [Facchinei and Pang, 2003, Proposition 7.1.4(b)] or
[Clarke, 1983, Proposition 2.1.5(d)]), we conclude that
$\bigcup_{(u,y)\in\operatorname*{cl}(\Omega)\times Y}\partial g(u,y)$ is
bounded. (Note that here, the Lipschitz continuity of $g$ over the open set
$O_{X}\times O_{Y}$ containing the compact set
$\operatorname*{cl}(\Omega)\times Y$ plays an important role; see also Section
2.1). Since $\partial_{x}g(u,y)\subseteq\pi_{x}\left(\partial g(u,y)\right)$
by [Clarke, 1983, Proposition 2.3.16], we conclude that the set
$\bigcup_{(u,y)\in\operatorname*{cl}(\Omega)\times Y}\partial_{x}g(u,y)$ is
likewise bounded, which together with the continuity of $g$ implies that
$M\coloneqq\sup\left\\{\exp(-g(u,y))\|v\|:v\in\partial_{x}g(u,y)~{}\text{and}~{}(u,y)\in\operatorname*{cl}(\Omega)\times
Y\right\\}$ is finite. Going back to (4.6) and using Cauchy-Schwarz
inequality, we have

$\min_{y\in Y_{j}}(-g(x^{*},y))-M\|x^{k}-x^{*}\|\leq\min_{y\in
Y_{j}}\exp(-g(x^{k},y))\leq\min_{y\in
Y_{j}}\exp(-g(x^{*},y))+M\|x^{k}-x^{*}\|.$

At this point, we follow arguments analogous to those in the proof of [Fang
and Wu, 1996, Lemma 2] to obtain a contradiction, thus completing the proof.
We note, however, that showing that equation (17) in Fang and Wu [1996] does
not require the “super uniform continuity” assumption imposed by the authors,
as it automatically follows from Theorem 2.4. ∎

######  Theorem 4.3.

Suppose that the hypotheses of Lemma 4.2 hold and $\\{g_{\mu}:\mu>0\\}$ is a
family of smooth approximations of $g$ over $O_{X}\times O_{Y}$ such that
$g_{\mu}$ converges uniformly to $g$ on $\operatorname*{cl}(\Omega)\times Y$
for any open subset $\Omega$ with $\operatorname*{cl}(\Omega)\subseteq O_{X}$.
Then, $\\{v_{\mu}:\mu>0\\}$ is a family of smooth approximations for the value
function over $O_{X}$.

###### Proof.

Proposition 4.1 already provides the continuous differentiability of each
$v_{\mu}$ on $O_{X}$. We just need to show that for any $\bar{x}\in O_{X}$,
$v_{\mu}(x)\to v(\bar{x})$ as $\mu\to 0$ and $x\to\bar{x}$. Take any
$\bar{x}\in O_{X}$ and let $\varepsilon>0$ be given, and
$\tau\in(\exp(-\varepsilon),1)$. By Lemma 4.2 there exists $\delta>0$ such
that (4.4) holds for all $\mu\in(0,\delta)$. Together with [Fang and Wu, 1996,
Theorem 1], we have

$\tau(\mu\operatorname*{vol}(Y))^{\mu}\max_{y\in
Y}\exp(-g(x,y))\overset{\eqref{eq:integral_lower_bound}}{\leq}\left(\int_{Y}\exp\left(-\mu^{-1}g(x,y)\right)dy\right)^{\mu}\leq\operatorname*{vol}(Y)^{\mu}\max_{y\in
Y}\exp(-g(x,y))$

for all $x\in\operatorname*{cl}(\Omega)$, where $\Omega$ is an open set
containing $\bar{x}$ whose closure is contained in $O_{X}$. Noting the
monotonicity of the logarithmic function, we have

$-\mu\ln\operatorname*{vol}(Y)-\max_{y\in
Y}(-g(x,y))\leq-\mu\ln\left(\int_{Y}\exp\left(-\mu^{-1}g(x,y)\right)dy\right)\\\
\leq-\ln\tau-\mu\ln(\mu\operatorname*{vol}(Y))-\max_{y\in Y}(-g(x,y)).$

By the choice of $\tau$ and the definition of $v$, we have

$v(x)-\mu\ln\operatorname*{vol}(Y)\leq-\mu\ln\left(\int_{Y}\exp\left(-\mu^{-1}g(x,y)\right)dy\right)\leq
v(x)-\mu\ln(\mu\operatorname*{vol}(Y))+\varepsilon.$

We may choose $\delta>0$ to be sufficiently small enough so that for all
$\mu\in(0,\delta)$, we have $\mu\ln\operatorname*{vol}(Y)<2\varepsilon$ and
$-\mu\ln(\mu\operatorname*{vol}(Y))<\varepsilon$. Hence,

$\left|-\mu\ln\left(\int_{Y}\exp\left(-\mu^{-1}g(x,y)\right)dy\right)-v(x)\right|<2\varepsilon,$
(4.7)

valid for all $x\in\operatorname*{cl}(\Omega)$ and $\mu\in(0,\delta)$. On the
other hand, invoking the uniform convergence of $g_{\mu}$ to $g$ on
$\operatorname*{cl}(\Omega)\times Y$, we may choose $\delta$ to be small
enough so that (4.7) holds and $|g_{\mu}(x,y)-g(x,y)|<\varepsilon$ for all
$\mu\in(0,\delta)$ and $(x,y)\in\operatorname*{cl}(\Omega)\times Y$.
Consequently, we have

$\left|-\mu\ln\left(\int_{Y}\exp\left(-\mu^{-1}g_{\mu}(x,y)\right)dy\right)+\mu\ln\left(\int_{Y}\exp\left(-\mu^{-1}g(x,y)\right)dy\right)\right|<\varepsilon$

for all $x\in\operatorname*{cl}(\Omega)$ and $\mu\in(0,\delta)$. Together with
(4.7) and the definition of $v_{\mu}$, we have

$|v_{\mu}(x)-v(x)|<3\varepsilon\qquad\forall
x\in\operatorname*{cl}(\Omega),~{}\forall\mu\in(0,\delta).$ (4.8)

By the continuity of the value function on $\operatorname*{cl}(\Omega)$ (see
Theorem 2.4(a)), we may choose $\delta>0$ so that
$|v(x)-v(\bar{x})|<\varepsilon$ for all $x\in\operatorname*{cl}(\Omega)$ with
$\|x-\bar{x}\|<\delta$. Together with (4.8), we have
$|v_{\mu}(x)-v(\bar{x})|<4\varepsilon$ for all $\mu\in(0,\delta)$ and
$x\in\operatorname*{cl}(\Omega)$ with $\|x-\bar{x}\|<\delta$. This completes
the proof. ∎

We next show that $v_{\mu}$ satisfies the gradient consistent property. To
this end, we need the following lemmas. Note that Lemma 4.4 is an extension of
[Lin et al., 2014, Theorem 5.3], but we provide a simpler and shorter proof as
shown below. Moreover, we also need another technical result shown in Lemma
4.5, which will be helpful in our proof of gradient consistency.

######  Lemma 4.4.

Let $\bar{x}\in O_{X}$ and $y^{\prime}\in Y\setminus S(\bar{x})$. Under the
hypotheses of Theorem 4.3, we have $\alpha_{\mu}(x,y^{\prime})\to 0$ as
$(x,\mu)\to(\bar{x},0)$, where $\alpha_{\mu}$ is given by (4.3).

###### Proof.

By Theorem 4.3,
$-g_{\mu}(x,y^{\prime})+v_{\mu}(x)\to-g(\bar{x},y^{\prime})+v(\bar{x})$ as
$(x,\mu)\to(\bar{x},0)$. Meanwhile, observe that we can rewrite $\alpha_{\mu}$
as $\alpha_{\mu}(x,y)=\exp\left(\mu^{-1}(-g_{\mu}(x,y)+v_{\mu}(x))\right).$
Hence, letting $(x,\mu)\to(\bar{x},0)$ and noting that
$-g(\bar{x},y^{\prime})+v(\bar{x})<0$ since $y^{\prime}\notin S(\bar{x})$, we
see that $\alpha_{\mu}(x,y^{\prime})\to 0$, as desired. ∎

######  Lemma 4.5.

Let $\bar{x}\in O_{X}$ and let $Z$ be any closed subset of $Y\setminus
S(\bar{x})$. Under the hypotheses of Theorem 4.3,
$\int_{Z}\alpha_{\mu}(x,y)dy\to 0$ as $(x,\mu)\to(\bar{x},0)$.

###### Proof.

First, we claim that $g_{\mu}(x,\cdot)\to g(\bar{x},\cdot)$ as
$(x,\mu)\to(\bar{x},0)$ uniformly on $Y$. Note that by hypothesis, $g_{\mu}\to
g$ as $\mu\to 0$ uniformly on
$\operatorname*{cl}(B_{\delta_{0}}(\bar{x}))\times Y$, where $\delta_{0}$ is
any positive number such that $\operatorname*{cl}(B_{\delta_{0}})\subseteq
O_{X}$. Thus, given any $\varepsilon>0$, there exists
$\delta\in(0,\delta_{0})$ such that

$\mu\in(0,\delta)\quad\Longrightarrow\quad|g_{\mu}(x,y)-g(x,y)|<\varepsilon/2\quad\forall(x,y)\in\operatorname*{cl}(B_{\delta_{0}}(\bar{x}))\times
Y.$ (4.9)

Meanwhile, since $g$ is uniformly continuous on the compact set
$\operatorname*{cl}(B_{\delta_{0}}(\bar{x}))\times Y$, we may choose a smaller
$\delta>0$, if necessary, so that

$|g(x,y)-g(x^{\prime},y^{\prime})|<\varepsilon/2\quad\forall(x,y),(x^{\prime},y^{\prime})~{}\text{with}~{}{\left\|{(x,y)-(x^{\prime},y^{\prime})}\right\|}<\delta.$
(4.10)

Since $\delta<\delta_{0}$ and
${\left\|{(x,y)-(\bar{x},y)}\right\|}={\left\|{x-\bar{x}}\right\|}$, then for
any $(x,\mu)$ such that ${\left\|{x-\bar{x}}\right\|}<\delta$ and
$\mu\in(0,\delta)$, it follows from triangle inequality and (4.9)-(4.10) that
$|g_{\mu}(x,y)-g(\bar{x},y)|<\varepsilon$ for any $y\in Y$. This completes
that $g_{\mu}(x,\cdot)\to g(\bar{x},\cdot)$ as $(x,\mu)\to(\bar{x},0)$
uniformly on $Y$.

Now, let $\varepsilon\coloneqq\displaystyle\max_{y\in
Z}g(\bar{x},y)-v(\bar{x})$. Note that since $Z$ is compact and lies outside
$S(\bar{x})$, then $\varepsilon$ is a finite positive number. Since
$\lim_{(x,\mu)\to(\bar{x},0)}v_{\mu}(x)=v(\bar{x})$ by Theorem 4.3, there
exists $\delta>0$ such that $v_{\mu}(x)-v(\bar{x})<\varepsilon/2$ for all
$(x,\mu)\in B_{\delta}(\bar{x},0)$. On the other hand, by the claim proved
above, we may choose a smaller $\delta>0$ if necessary so that
$g(\bar{x},y)-g_{\mu}(x,y)<\varepsilon/2$ for all $y\in Y$ and for all
$(x,\mu)\in B_{\delta}(\bar{x},0)$. Consequently,
$-g_{\mu}(x,y)+v_{\mu}(x)<-g(\bar{x},y)+v(\bar{x})+\varepsilon$ for all $y\in
Y$ and for all $(x,\mu)\in B_{\delta}(\bar{x},0)$. On the other hand, by our
choice of $\varepsilon$, we have $-g(\bar{x},y)+v(\bar{x})+\varepsilon\leq 0$
for all $y\in Z$, so that $-g_{\mu}(x,y)+v_{\mu}(x)<0$ for all $(x,\mu)\in
B_{\delta}(\bar{x},0)$ and $y\in Z$. In turn,
$\alpha_{\mu}(x,\cdot)=\exp\left(\mu^{-1}(-g_{\mu}(x,\cdot)+v_{\mu}(x))\right)$
is uniformly bounded above by 1 on $Z$ for all $(x,\mu)\in
B_{\delta}(\bar{x},0)$. Finally, we obtain the desired limit
$\int_{Z}\alpha_{\mu}(x,y)dy\to 0$ as a direct consequence of Lemma 4.4 and
the bounded convergence theorem. ∎

We now prove the following result which is instrumental in showing gradient
consistency, as proved in Theorem 4.10. Note that unlike the smooth analogue
[Lin et al., 2014, Theorem 5.5], we do not assume compactness of the set $X$.
As mentioned above, we also need the additional result Lemma 4.5 to prove the
following lemma. We also point out that due to the nonsmoothness of $g$, the
main challenge and difficulty lie in finding an element of $P(\bar{x})$ (refer
to (2.3)) that is arbitrarily close to the set
$\limsup_{x\to\bar{x},\mu\searrow 0}\nabla v_{\mu}(x)$. Moreover, the
subsequent verification that the identified element is indeed close requires
some subtle techniques.

######  Lemma 4.6.

Suppose that the hypotheses of Theorem 4.3 hold and that there exists a
neighborhood $\Omega$ of $\bar{x}\in O_{X}$ such that
$\partial_{x}g(\cdot,\cdot)$ is upper semicontinuous on $\Omega\times O_{Y}$.
If $\operatorname*{dist}(\nabla_{x}g_{\mu}(x,\cdot),\partial_{x}g(x,\cdot))$
converges to $0$ uniformly on $Y$ as $(x,\mu)\to(\bar{x},0)$, then

$\emptyset\neq\limsup_{x\to\bar{x},\mu\searrow 0}\nabla v_{\mu}(x)\subseteq
P(\bar{x}),$

where $P(\bar{x})$ is given in (2.3).

###### Proof.

First, we show that $\limsup_{x\to\bar{x},\mu\searrow 0}\nabla v_{\mu}(x)$ is
indeed nonempty. By the uniform convergence assumption, there exists
$\delta^{\prime}>0$ such that
$\operatorname*{dist}(\nabla_{x}g_{\mu}(x,y),\partial_{x}g(x,y))<1$ for all
$\mu\in(0,\delta^{\prime})$ and
$(x,y)\in\operatorname*{cl}(B_{\delta^{\prime}}(\bar{x}))\times Y.$ It follows
that

$\|\nabla_{x}g_{\mu}(x,y)\|\leq
1+M\qquad\forall\mu\in(0,\delta^{\prime}),~{}\forall(x,y)\in
B_{\delta^{\prime}}(\bar{x})\times Y$ (4.11)

where

$M\coloneqq\sup\\{\|\xi\|:\xi\in\partial_{x}g(x,y)~{}\text{and}~{}(x,y)\in\operatorname*{cl}(B_{\delta^{\prime}}(\bar{x}))\times
Y\\}.$ (4.12)

We may choose $\delta^{\prime}>0$ to be sufficiently small so that
$\operatorname*{cl}(B_{\delta^{\prime}}(\bar{x}))\subseteq\Omega$. Thus,
$M<+\infty$ by the upper semicontinuity of $\partial_{x}g(\cdot,\cdot)$ and
compactness of $\operatorname*{cl}(B_{\delta^{\prime}}(\bar{x}))\times Y$.
From (4.2) and noting that $\int_{Y}\alpha_{\mu}(x,y)dy=1$, we see that
$\\{\nabla v_{\mu}(x):x\in
B_{\delta^{\prime}}(\bar{x}),\mu\in(0,\delta^{\prime})\\}$ is a bounded set,
thus proving the first claim.

To prove the inclusion, suppose that $\nabla v_{\mu_{k}}(x^{k})\to\xi\in{\rm
I}\\!{\rm R}^{n}$ for some sequences $x^{k}\to\bar{x}$ and $\mu_{k}\searrow 0$
as $k\to\infty$. We need to show that $\xi\in P(\bar{x})$. To this end, let
$\varepsilon>0$ be given. We will find an element $\xi^{k}$ of $P(\bar{x})$
such that $\|\nabla v_{\mu_{k}}(x^{k})-\xi^{k}\|<\varepsilon$ for sufficiently
large $k$. For any $y\in S(\bar{x})$, we have from upper semicontinuity that
there exists $\delta_{y}>0$ such that

$\partial_{x}g(x^{\prime},y^{\prime})\subseteq\partial_{x}g(\bar{x},y)+\frac{\varepsilon}{3}B_{1}(0)\quad\forall
x^{\prime}\in B_{\delta_{y}}(\bar{x}),~{}y^{\prime}\in B_{\delta_{y}}(y).$
(4.13)

Meanwhile, since $Y$ is compact and $g$ is continuous, $S(\bar{x})$ is
compact. Hence, there exist points $y_{1},y_{2},\dots,y_{r}\in S(\bar{x})$ and
numbers $\delta_{1},\delta_{2},\dots,\delta_{r}>0$ such that
$S(\bar{x})\subseteq\bigcup_{i=1}^{r}B_{\delta_{i}}(y_{i})$. Denote
$Y_{1}\coloneqq Y\cap B_{\delta_{1}}(y_{1})$, $Y_{i}\coloneqq
Y\cap\left(B_{\delta_{i}}(y_{i})\setminus\bigcup_{j=1}^{i-1}B_{\delta_{j}}(y_{j})\right)$
for $i=2,\dots,r$, and $Y_{r+1}\coloneqq
Y\setminus\bigcup_{i=1}^{r}B_{\delta}(y_{i})$. Note that since
$Y_{r+1}\subseteq Y\setminus S(\bar{x})$, it follows from Lemma 4.4 that
$\int_{Y_{r+1}}\alpha_{\mu_{k}}(x^{k},y)dy\to 0$.

Now, let $\delta>0$ be such that
$\delta<\min\\{\delta^{\prime},\delta_{1},\dots,\delta_{r}\\}$ and

$\operatorname*{dist}(\nabla_{x}g_{\mu}(x,y),\partial_{x}g(x,y))<\frac{\varepsilon}{3}\quad\forall\mu\in(0,\delta)~{}\text{and}~{}\forall(x,y)\in\operatorname*{cl}(B_{\delta}(\bar{x}))\times
Y.$ (4.14)

Choose $k$ large enough so that $x^{k}\in B_{\delta}(\bar{x})$,
$\mu_{k}\in(0,\delta)$ and

$\int_{Y_{r+1}}\alpha_{\mu_{k}}(x^{k},y)dy<\frac{\varepsilon}{3(2M+1)}$ (4.15)

where $M$ is given by (4.12). We now define $\xi^{k}$ as

$\xi^{k}\coloneqq\sum_{i=1}^{r+1}\int_{Y_{i}}\alpha_{\mu_{k}}(x^{k},y)\Pi_{\partial_{x}g(\bar{x},y_{i})}\left(\varphi^{(i)}_{k}(y)\right)dy,$

where $y_{r+1}$ is an arbitrarily chosen element of $S(\bar{x})$,
$\Pi_{\partial_{x}g(\bar{x},y_{i})}$ denotes the projection operator onto the
convex set $\partial_{x}g(\bar{x},y_{i})$, and $\varphi^{(i)}_{k}$ is any
single-valued mapping from $Y_{i}$ to $\partial_{x}g(x^{k},y)$. Note that
since $\bigcup_{i=1}^{r+1}Y_{i}=Y$, $\int_{Y}\alpha_{\mu_{k}}(x^{k},y)dy=1$,
and the range of $\Pi_{\partial_{x}g(\bar{x},y_{i})}$ is contained in
$P(\bar{x})$, it follows that $\xi^{k}$ is indeed in $P(\bar{x})$ by Jensen’s
inequality.

We now show that $\|\nabla v_{\mu_{k}}(x^{k})-\xi^{k}\|<\varepsilon$. For each
$i=1,\dots,r$, denote $E_{i}\coloneqq\\{y\in Y_{i}:g~{}\text{is not
differentiable at }(x^{k},y)\\}$. By Rademacher’s theorem, note that the
Lebesgue measure of $E_{i}$ is zero since $g$ is Lipschitz continuous on
$O_{X}\times O_{Y}$. Moreover,
$\partial_{x}g(x^{k},y)=\\{\nabla_{x}g(x^{k},y)\\}$ and
$\varphi^{(i)}_{k}(y)=\nabla_{x}g(x^{k},y)$ for any $y\in Y_{i}\setminus
E_{i}$ where $i\in\\{1,\dots,r\\}$. Hence, for all $y\in Y_{i}\setminus E_{i}$
with $i\in\\{1,\dots,r\\}$,

$\displaystyle{\left\|{\nabla_{x}g_{\mu_{k}}(x^{k},y)-\nabla_{x}g(x^{k},y)}\right\|}$
$\displaystyle={\left\|{\nabla_{x}g_{\mu_{k}}(x^{k},y)-\Pi_{\partial_{x}g(x^{k},y)}(\nabla_{x}g_{\mu_{k}}(x^{k},y))}\right\|}$
$\displaystyle=\operatorname*{dist}(\nabla_{x}g_{\mu_{k}}(x^{k},y),\partial_{x}g(x^{k},y))$
$\displaystyle<\frac{\varepsilon}{3},$ (4.16)

where the last inequality holds by (4.14). By (4.13) and our choice of
$\delta$, we have for any $y\in Y_{i}\setminus E_{i}$ ($i\in\\{1,\dots,r\\}$)
that there exists $\nu(y)\in\partial_{x}g(\bar{x},y_{i})$ such that
${\left\|{\nabla_{x}g(x^{k},y)-\nu(y)}\right\|}<\frac{\varepsilon}{3}$. It
follows that
${\left\|{\nabla_{x}g(x^{k},y)-\Pi_{\partial_{x}g(\bar{x},y_{i})}\left(\nabla_{x}g(x^{k},y)\right)}\right\|}<\frac{\varepsilon}{3}$.
This, together with (4.16), implies that

${\left\|{\nabla_{x}g_{\mu_{k}}(x^{k},y)-\Pi_{\partial_{x}g(\bar{x},y_{i})}\left(\varphi^{(i)}_{k}(y)\right)}\right\|}<\frac{2\varepsilon}{3},\quad\forall
y\in Y_{i}\setminus E_{i},~{}i\in\\{1,\dots,r\\},$ (4.17)

by triangle inequality. Meanwhile, we also have

$\displaystyle{\left\|{\int_{Y_{r+1}}\alpha_{\mu_{k}}(x^{k},y)\left(\nabla_{x}g_{\mu_{k}}(x^{k},y)-\Pi_{\partial_{x}g(\bar{x},y_{r+1})}\left(\varphi^{(r+1)}_{k}(y)\right)\right)dy}\right\|}$
$\displaystyle\quad\leq\int_{Y_{r+1}}\alpha_{\mu_{k}}(x^{k},y)\left({\left\|{\nabla_{x}g_{\mu_{k}}(x^{k},y)}\right\|}+{\left\|{\Pi_{\partial_{x}g(\bar{x},y_{r+1})}\left(\varphi^{(r+1)}_{k}(y)\right)}\right\|}\right)dy$
$\displaystyle\quad\leq(2M+1)\int_{Y_{r+1}}\alpha_{\mu_{k}}(x^{k},y)dy$
$\displaystyle\quad\overset{\eqref{eq:integral_alpha_epsilon}}{<}\frac{\varepsilon}{3},$
(4.18)

where the second inequality holds by (4.11) and (4.12) since
$\delta<\delta^{\prime}$. Finally, we have

$\displaystyle\|\nabla v_{\mu_{k}}(x^{k})-\xi^{k}\|$
$\displaystyle={\left\|{\int_{Y}\alpha_{\mu_{k}}(x^{k},y)\nabla_{x}g_{\mu_{k}}(x^{k},y)dy-\sum_{i=1}^{r+1}\int_{Y_{i}}\alpha_{\mu_{k}}(x^{k},y)\Pi_{\partial_{x}g(\bar{x},y_{i})}\left(\varphi^{(i)}_{k}(y)\right)dy}\right\|}$
$\displaystyle\leq{\left\|{\sum_{i=1}^{r}\int_{Y_{i}}\alpha_{\mu_{k}}(x^{k},y)\left(\nabla_{x}g_{\mu_{k}}(x^{k},y)-\Pi_{\partial_{x}g(\bar{x},y_{i})}\left(\varphi^{(i)}_{k}(y)\right)\right)dy}\right\|}$
$\displaystyle\qquad+{\left\|{\int_{Y_{r+1}}\alpha_{\mu_{k}}(x^{k},y)\left(\nabla_{x}g_{\mu_{k}}(x^{k},y)-\Pi_{\partial_{x}g(\bar{x},y_{r+1})}\left(\varphi^{(r+1)}_{k}(y)\right)\right)dy}\right\|}$
$\displaystyle\overset{\eqref{eq:outside_S(x)_integral}}{<}\sum_{i=1}^{r}\int_{Y_{i}}\alpha_{\mu_{k}}(x^{k},y){\left\|{\nabla_{x}g_{\mu_{k}}(x^{k},y)-\Pi_{\partial_{x}g(\bar{x},y_{i})}\left(\varphi^{(i)}_{k}(y)\right)}\right\|}dy+\frac{\varepsilon}{3}$
$\displaystyle=\sum_{i=1}^{r}\int_{Y_{i}\setminus
E_{i}}\alpha_{\mu_{k}}(x^{k},y){\left\|{\nabla_{x}g_{\mu_{k}}(x^{k},y)-\Pi_{\partial_{x}g(\bar{x},y_{i})}\left(\varphi^{(i)}_{k}(y)\right)}\right\|}dy+\frac{\varepsilon}{3}$
$\displaystyle\overset{\eqref{eq:dist_S(x)_integral}}{<}\frac{2\varepsilon}{3}\sum_{i=1}^{r}\int_{Y_{i}}\alpha_{\mu_{k}}(x^{k},y)dy+\frac{\varepsilon}{3}$
$\displaystyle\leq\varepsilon.$ (4.19)

Since $\varepsilon>0$ is arbitrary, it follows that we can extract a
subsequence $\\{\nabla v_{\mu_{k}}(x^{k})\\}_{k\in K}$ where
$K\subseteq\mathbb{N}$ together with $\\{\xi^{k}\\}_{k\in K}\subseteq
P(\bar{x})$ such that $\|\nabla v_{\mu_{k}}(x^{k})-\xi^{k}\|\to 0$ as
$k\to\infty$ with $k\in K$. Since $P(\bar{x})$ is closed (due to the
compactness of $S(\bar{x})$), any accumulation point $\xi^{*}$ of
$\\{\xi^{k}\\}_{k\in K}$ belongs to $P(\bar{x})$. Since $\|\nabla
v_{\mu_{k}}(x^{k})-\xi^{*}\|\leq\|\nabla
v_{\mu_{k}}(x^{k})-\xi^{k}\|+\|\xi^{k}-\xi^{*}\|$ and $\nabla
v_{\mu_{k}}(x^{k})\to\xi$, we conclude that $\xi=\xi^{*}$, so that $\xi\in
P(\bar{x})$ as desired. This completes the proof. ∎

######  Remark 4.7.

We note that the uniform convergence assumption in the above lemma can be
achieved in many situations. Suppose that $g$ takes the form
$g(x,y)=a(x,y)+b(p(x),q(y))$ where $a$ and $b$ are smooth, $b$ has Lipschitz
continuous derivative, $p$ and $q$ are Lipschitz continuous functions, and the
chain rule applies for $b(p(\cdot),q(y))$ for each $y$; for instance, under
the conditions stipulated in [Clarke, 1983, Theorem 2.3.9] or simply when $p$
is a smooth function. Let $\\{p_{\mu}:\mu>0\\}$ and $\\{q_{\mu}:\mu>0\\}$ be
smooth approximations of $p$ and $q$, respectively, such that
$\operatorname*{dist}(\nabla p_{\mu}(\cdot),\partial p(\cdot))\to 0$ pointwise
(uniform convergence is not required), and $q_{\mu}\to q$ uniformly on $Y$.
Note that these assumptions are satisfied by the Chen-Mangasarian smoothing
and the Moreau envelope smoothing described in Example 2.7 and Example 2.8.
Under these circumstances, we obtain the uniform convergence required in Lemma
4.6.

######  Remark 4.8.

Upper semicontinuity of $\partial_{x}g$ can be attained under any condition
that will guarantee that if $(\xi,\xi^{\prime})\in\partial
g(\bar{x},\bar{y})$, then $\xi\in\partial_{x}g(\bar{x},\bar{y})$ for any
$(\bar{x},\bar{y})$. For instance, the latter condition can be satisfied under
Clarke regularity of $g$ (see [Clarke, 1983, Proposition 2.3.15]) or
convexity/concavity of $g$ with respect to $x$ (see [Clarke, 1983, Proposition
2.5.3]). To see how the said condition implies upper semicontinuity of
$\partial_{x}g$, note that given any $\varepsilon>0$, we have from upper
semicontinuity of $\partial g$ that we can find $\delta>0$ such that $\partial
g(x,y)\subseteq\partial g(\bar{x},\bar{y})+\varepsilon B_{1}(0)$ for all
$(x,y)\in B_{\delta}(\bar{x},\bar{y})$. From [Clarke, 1983, Proposition
2.3.16], we have $\partial_{x}g(x,y)\subset\pi_{x}\partial g(x,y)$. Finally,
we get the desired result by noting that $\pi_{x}(\partial
g(x,y))\subset\pi_{x}(\partial g(\bar{x},\bar{y})+\varepsilon B_{1}(0))$.

######  Example 4.9.

For the hyperparameter learning lower-level function $g$ given by (3.5) where
the $p_{i}$’s are not necessarily convex but may be nonsmooth, we may consider
any smooth approximation

$g_{\mu}(x,y)\coloneqq\ell_{\mu}(y)+\sum_{i=1}^{n}x_{i}p_{i,\mu}(y),$

where $p_{i,\mu}\to p_{i}$ uniformly on $Y\subseteq{\rm I}\\!{\rm R}^{m}$.
When $p_{i}$ is convex, such uniform convergence required can be attained by
using the Moreau envelope, or the Chen-Mangasarian smoothing. For nonconvex
$p_{i}$ such as the $l_{p}$-norm with $p\in(0,1)$, uniform convergence holds
for several examples as well (see Chen [2012]). For this example of $g$ and
$g_{\mu}$, it is not difficult to verify that the assumptions required by
Lemma 4.6 are all satisfied.

With Lemma 4.6, we immediately obtain gradient consistency as follows.

######  Theorem 4.10.

Under the hypotheses of Theorem 4.3 and assuming that
$\operatorname*{dist}(\nabla_{x}g_{\mu}(x,\cdot),\partial_{x}g(x,\cdot))$
converges to $0$ uniformly on $Y$ as $(x,\mu)\to(\bar{x},0)$, the family of
smooth approximations $\\{v_{\mu}:\mu>0\\}$ of $v$ satisfies the gradient
consistent property at $\bar{x}\in O_{X}$ under any of the following
conditions:

  1. (a)

$\nabla_{x}g(x,y)$ exists and is continuous on $\Omega\times Y$;

  2. (b)

$g(\cdot,y)$ is $\rho$-weakly concave function on $\Omega$ for any $y\in Y$;
or

  3. (c)

(3.16) holds and $g$ is convex in $(x,y)$,

where $\Omega$ is a neighborhood of $\bar{x}$.

###### Proof.

Under any of the conditions in (a), (b), and (c), the set-valued mapping
$\partial_{x}g$ is upper semicontinuous; see also Remark 4.8. Hence, this
theorem directly follows from Lemma 4.6, Theorem 2.1, Eq. 2.3 and Theorem 3.9.
∎

###  4.2 Entropic regularization for unbounded constraint set

We show that when $Y$ is a closed unbounded set, the family of functions given
by

$v_{\mu}(x)\coloneqq-\mu\ln\left(\int_{Y_{\mu}}\exp\left(-\mu^{-1}g_{\mu}(x,y)\right)dy\right),$
(4.20)

is a smoothing function for the value function $v(x)=\max_{y\in Y}g(x,y)$ for
a suitably chosen family $\\{Y_{\mu}:\mu>0\\}$ of subsets of $Y$.

######  Proposition 4.11.

Suppose that $\\{Y_{\mu}:\mu>0\\}$ is a family of compact subsets of $Y$ such
that $Y_{\mu}\nearrow Y$, and $\\{g_{\mu}:\mu>0\\}$ is a family of smoothing
functions of $g$ over $O_{X}\times O_{Y}$. For each $\mu>0$, $v_{\mu}$ given
by (4.20) is continuously differentiable on $O_{X}$.

###### Proof.

The claim can be proved by replacing $Y$ in the proof of Proposition 4.1 with
$Y_{\mu}$. We note that the gradient of $v_{\mu}$ is given by

$\nabla v_{\mu}(x)=\int_{Y_{\mu}}\alpha_{\mu}(x,y)\nabla_{x}g_{\mu}(x,y)dy,$

where

$\alpha_{\mu}(x,y)\coloneqq\frac{\exp(-\mu^{-1}g_{\mu}(x,y))}{\int_{Y_{\mu}}\exp(-\mu^{-1}g_{\mu}(x,z))dz}.$
(4.21)

∎

To prove an analogue of Lemma 4.2, we require the uniform level-boundedness
assumption.

######  Lemma 4.12.

Suppose that the hypotheses of Proposition 4.11 hold, $g$ is level-bounded in
$y$, locally uniform in $x$, and $g$ is Lipschitz continuous function on
$O_{X}\times O_{Y}$, where $O_{X}$ is convex. Given any $\bar{x}\in O_{X}$,
there exist a neighborhood $\Omega$ of $\bar{x}$ and a positive number
$\mu_{0}>0$ such that

$\max_{y\in Y_{\mu_{0}}}\exp(-g(x,y))=\max_{y\in Y}\exp(-g(x,y))\qquad\forall
x\in\operatorname*{cl}(\Omega).$ (4.22)

Moreover, for any $\tau\in(0,1)$, there exists $\delta>0$ such that

$\tau(\mu\operatorname*{vol}(Y_{\mu_{0}}))^{\mu}\max_{y\in
Y}\exp(-g(x,y))\leq\left(\int_{Y_{\mu}}\exp\left(-\mu^{-1}g(x,y)\right)dy\right)^{\mu}\quad\forall
x\in\operatorname*{cl}(\Omega),~{}\forall\mu\in(0,\delta).$ (4.23)

###### Proof.

From the proof of Theorem 3.8, we know that
$\bigcup_{x\in\operatorname*{cl}(B_{\alpha}(\bar{x}))}S(x)$ is a bounded set
for some $\alpha<1$. Therefore, we may choose $\mu_{0}$ small enough so that
$Y_{\mu_{0}}$ contains $\bigcup_{x\in\operatorname*{cl}(\Omega)}S(x)$ with
$\Omega=B_{\alpha}(\bar{x})$. Hence, (4.22) holds. Now, let $\tau\in(0,1)$. We
have from the proof of Lemma 4.2 that there exists a sufficiently large
$N_{0}$ such that

$\displaystyle\max_{j=1,2,\dots,k}~{}~{}\min_{y\in(Y_{\mu_{0}})_{j}}\exp(-g(x,y))>\tau\cdot\max_{y\in
Y_{\mu_{0}}}\exp(-g(x,y))\quad\forall x\in\operatorname*{cl}(\Omega)$ (4.24)

holds for all integers $k\geq N_{0}$ and any partition
$\\{(Y_{\mu_{0}})_{1},(Y_{\mu_{0}})_{2}\dots,(Y_{\mu_{0}})_{k}\\}$ of
$Y_{\mu_{0}}$ with
$\displaystyle\max_{j=1,2,\dots,k}\operatorname*{diam}(Y_{\mu_{0}})_{j}\to 0$
as $k\to\infty$. Choose $\delta<1/N_{0}$ and partition $Y_{\mu_{0}}$ into
$N_{0}$ equal parts. Then, for any $\mu\in(0,\delta)$,

$\displaystyle\left(\int_{Y_{\mu}}\exp\left(-\mu^{-1}g(x,y)\right)dy\right)^{\mu}$
$\displaystyle\geq\left(\int_{Y_{\mu_{0}}}\exp\left(-\mu^{-1}g(x,y)\right)dy\right)^{\mu}$
$\displaystyle\geq\left(\frac{\operatorname*{vol}(Y_{\mu_{0}})}{N_{0}}\sum_{j=1}^{N_{0}}\min_{y\in(Y_{\mu_{0}})_{j}}\exp\left(-\mu^{-1}g(x,y)\right)\right)^{\mu}$
$\displaystyle=\left(\frac{\operatorname*{vol}(Y_{\mu_{0}})}{N_{0}}\sum_{j=1}^{N_{0}}\left(\min_{y\in(Y_{\mu_{0}})_{j}}\exp\left(-g(x,y)\right)\right)^{\mu^{-1}}\right)^{\mu}$
$\displaystyle\geq\left(\frac{\operatorname*{vol}(Y_{\mu_{0}})}{N_{0}}\left(\max_{j=1,\dots,N_{0}}\min_{y\in(Y_{\mu_{0}})_{j}}\exp\left(-g(x,y)\right)\right)^{\mu^{-1}}\right)^{\mu}$
$\displaystyle\geq\tau\left(\frac{\operatorname*{vol}(Y_{\mu_{0}})}{N_{0}}\right)^{\mu}\max_{y\in
Y_{\mu_{0}}}\exp(-g(x,y))$
$\displaystyle\geq\tau\operatorname*{vol}(Y_{\mu_{0}})^{\mu}\mu^{\mu}\max_{y\in
Y_{\mu_{0}}}\exp(-g(x,y))$
$\displaystyle=\tau\operatorname*{vol}(Y_{\mu_{0}})^{\mu}\mu^{\mu}\max_{y\in
Y}\exp(-g(x,y)),$

where the fourth inequality holds by (4.24), and the last equality holds by
(4.22). This completes the proof. ∎

We now show that $\\{v_{\mu}:\mu>0\\}$ is a family of smooth approximations in
the sense of Definition 2.5.

######  Theorem 4.13.

Suppose that the hypotheses of Lemma 4.12 hold and the family
$\\{Y_{\mu}:\mu>0\\}$ is chosen so that $\mu\ln\operatorname*{vol}(Y_{\mu})\to
0$ as $\mu\to 0$444For instance, a simple choice would be to set
$Y_{\mu}\coloneqq Y\cap B_{r_{\mu}}(0)$ where $r_{\mu}$ is chosen so that
$r_{\mu}\nearrow+\infty$ as $\mu\searrow 0$ and
$\operatorname*{vol}(B_{r_{\mu}}(0))\leq\mu^{-p}$ for any $p>0$.. If $g_{\mu}$
converges uniformly to $g$ on $\operatorname*{cl}(\Omega)\times Y$ for any
open subset $\Omega$ with $\operatorname*{cl}(\Omega)\subseteq O_{X}$, then
$\\{v_{\mu}:\mu>0\\}$ is a family of smooth approximations for the value
function over $O_{X}$

###### Proof.

We only need to show that for any $\bar{x}\in O_{X}$, $v_{\mu}(x)\to
v(\bar{x})$ as $\mu\to 0$ and $x\to\bar{x}$. To this end, let $\varepsilon>0$
be given, and let $\tau\in(\exp(-\varepsilon),1)$. By Lemma 4.12 there exist a
neighborhood $\Omega$ of $\bar{x}$ and positive numbers $\mu_{0}$ and
$\delta<\mu_{0}$ such that (4.22) and (4.23) hold for all $\mu\in(0,\delta)$.
Meanwhile, arguing as in [Fang and Wu, 1996, Theorem 1], we have

$\left(\int_{Y_{\mu}}\exp\left(-\mu^{-1}g(x,y)\right)dy\right)^{\mu}\leq\operatorname*{vol}(Y_{\mu})^{\mu}\max_{y\in
Y_{\mu}}\exp(-g(x,y)),\quad\forall x\in O_{X}.$

Together with (4.23) and noting that $Y_{\mu}\supseteq Y_{\mu_{0}}$, we have

$\tau(\mu\operatorname*{vol}(Y_{\mu_{0}}))^{\mu}\max_{y\in
Y}\exp(-g(x,y))\leq\left(\int_{Y_{\mu}}\exp\left(-\mu^{-1}g(x,y)\right)dy\right)^{\mu}\leq\operatorname*{vol}(Y_{\mu})^{\mu}\max_{y\in
Y}\exp(-g(x,y))$

for all $x\in\operatorname*{cl}(\Omega)$. Since the logarithmic function is
monotonic, then

$-\mu\ln\operatorname*{vol}(Y_{\mu})-\max_{y\in
Y}(-g(x,y))\leq-\mu\ln\left(\int_{Y_{\mu}}\exp\left(-\mu^{-1}g(x,y)\right)dy\right)\\\
\leq-\ln\tau-\mu\ln(\mu\operatorname*{vol}(Y_{\mu_{0}}))-\max_{y\in
Y}(-g(x,y)).$

Then

$v(x)-\mu\ln\operatorname*{vol}(Y_{\mu})\leq-\mu\ln\left(\int_{Y_{\mu}}\exp\left(-\mu^{-1}g(x,y)\right)dy\right)\leq
v(x)-\mu\ln(\mu\operatorname*{vol}(Y_{\mu_{0}}))+\varepsilon.$

We may choose $\delta>0$ to be sufficiently small enough so that for all
$\mu\in(0,\delta)$, we have $\mu\ln\operatorname*{vol}(Y_{\mu})<2\varepsilon$
and $-\mu\ln(\mu\operatorname*{vol}(Y_{\mu_{0}}))<\varepsilon$. Hence,

$\left|-\mu\ln\left(\int_{Y_{\mu}}\exp\left(-\mu^{-1}g(x,y)\right)dy\right)-v(x)\right|<2\varepsilon,$

valid for all $x\in\operatorname*{cl}(\Omega)$ and $\mu\in(0,\delta)$. The
rest of the proof follows from the same arguments as in Theorem 4.3.

∎

As shown above, managing the unboundedness of the constraint set $Y$ to obtain
a smoothing function of the value function can be achieved by assuming uniform
level-boundedness of $g$ and restricting the region of integration to
$Y_{\mu}$. In particular, we need the $Y_{\mu}$’s to be compact sets whose
volumes increase in a controlled magnitude so that
$\mu\ln(\operatorname*{vol}(Y_{\mu}))\to 0$. However, these are not sufficient
to prove gradient consistency of the smoothing family, and the main difficulty
lies on the unbounded nature of $Y$. Integrable dominating functions would be
required to handle limits of sequences of integrals as shown in the following
results.

######  Lemma 4.14.

Let $\bar{x}\in O_{X}$ and $y^{\prime}\in Y\setminus S(\bar{x})$. Under the
hypotheses of Theorem 4.13, we have $\alpha_{\mu}(x,y^{\prime})\to 0$ as
$(x,\mu)\to(\bar{x},0)$, where $\alpha_{\mu}$ is given by (4.21).

###### Proof.

The proof is exactly identical to that of Lemma 4.4, ∎

To prove a counterpart of Lemma 4.5 for the unbounded case, we need to assume
the existence of an integrable dominating function $h$ for $\alpha_{\mu}(x,y)$
over a neighborhood of $(\bar{x},\mu)$. Note that in the case of Lemma 4.5, we
have shown in the proof that uniform convergence of $\\{g_{\mu}\\}$ and the
compactness of $Y$ lead us to obtain the constant function $h\equiv 1$ to be
the desired dominating function, which is indeed integrable over the compact
set $Z$.

######  Lemma 4.15.

Let $\bar{x}\in O_{X}$ and suppose that for any closed subset $Z$ of
$Y\setminus S(\bar{x})$, there exists an integrable function $h:Z\to{\rm
I}\\!{\rm R}$ such that $\alpha_{\mu}(x,y)\leq h(y)$ for all $y\in Z$ and for
all $(x,\mu)$ in some neighborhood of $(\bar{x},0)$. Under the hypotheses of
Theorem 4.13, we have $\int_{Z}\alpha_{\mu}(x,y)dy\to 0$ as
$(x,\mu)\to(\bar{x},0)$.

###### Proof.

This is a direct consequence of the Lebesgue dominated convergence theorem and
Lemma 4.14. ∎

The following is another technical lemma needed to prove the next theorem.

######  Lemma 4.16.

Suppose that the hypotheses of Lemma 4.15 hold, and that for any closed subset
$Z$ of $Y\setminus S(\bar{x})$, there exists an integrable function
$H:Z\to{\rm I}\\!{\rm R}$ such that
$\alpha_{\mu}(x,y){\left\|{\nabla_{x}g_{\mu}(x,y)}\right\|}\leq H(y)$ for all
$y\in Z$ and for all $(x,\mu)$ in some neighborhood of $(\bar{x},0)$. Further,
suppose that there exists a neighborhood $\Omega$ of $\bar{x}\in O_{X}$ such
that $\partial_{x}g(\cdot,\cdot)$ is upper semicontinuous on $\Omega\times
O_{Y}$. If
$\operatorname*{dist}(\nabla_{x}g_{\mu}(x,\cdot),\partial_{x}g(x,\cdot))$
converges to $0$ uniformly on $Y$ as $(x,\mu)\to(\bar{x},0)$, then there
exists $\delta^{\prime}>0$ such that $\\{\nabla
v_{\mu}(x):\mu\in(0,\delta^{\prime}),x\in\operatorname*{cl}(B_{\delta^{\prime}}(\bar{x}))\\}$
is bounded.

###### Proof.

Let $\Theta$ be a bounded open set that properly contains the compact set
$S(\bar{x})$, and let $Z\coloneqq Y\setminus\Theta$, which is a closed set
contained in $Y\setminus S(\bar{x})$. Meanwhile, we know from the uniform
convergence of
$\operatorname*{dist}(\nabla_{x}g_{\mu}(x,\cdot),\partial_{x}g(x,\cdot))$ on
$Y$ that there exists $\delta>0$ such that

$\operatorname*{dist}(\nabla_{x}g_{\mu}(x,y),\partial_{x}g(x,y))<1\quad\forall\mu\in(0,\delta),~{}~{}\forall(x,y)\in\operatorname*{cl}(B_{\delta}(\bar{x}))\times
Y.$ (4.25)

We may argue as in the first part of the proof of Lemma 4.6 to conclude that
the set

$\left\\{\int_{\Theta\cap
Y}\alpha_{\mu}(x,y)\|\nabla_{x}g_{\mu}(x,y)\|dy~{}:~{}x\in\operatorname*{cl}(B_{\delta}(\bar{x})),~{}\mu\in(0,\delta)\right\\}$
(4.26)

is bounded, noting the set $\operatorname*{cl}(\Theta)\cap Y$ is compact. From
the upper semicontinuity of $\partial_{x}g(\cdot,\cdot)$, we see that
$\bigcup_{x\in\operatorname*{cl}(B_{\delta}(\bar{x}))}\partial_{x}g(x,y)$ is
bounded for any given $y\in Z$. Together with (4.25) and triangle inequality,
we know that
$\\{{\left\|{\nabla_{x}g(x,y)}\right\|}:x\in\operatorname*{cl}(B_{\delta}(\bar{x})),~{}\mu\in(0,\delta)\\}$
is bounded for a fixed $y$. Hence, using Lemma 4.15, we conclude that
$\alpha_{\mu}(x,y){\left\|{\nabla_{x}g(x,y)}\right\|}$ converges pointwise to
$0$ as $(x,\mu)\to(\bar{x},0)$ for each $y\in Z$. Since an integrable
dominating function exists by our hypothesis, we conclude by the Lebesgue
dominated convergence theorem that

$\int_{Z}\alpha_{\mu}(x,y)\|\nabla_{x}g_{\mu}(x,y)\|dy\to
0\quad\text{as}\quad(x,\mu)\to(\bar{x},0).$ (4.27)

Finally, since

$\displaystyle{\left\|{\nabla v_{\mu}(x)}\right\|}$
$\displaystyle\leq\int_{Y_{\mu}}\alpha_{\mu}(x,y){\left\|{\nabla_{x}g_{\mu}(x,y)}\right\|}dy$
$\displaystyle=\int_{\Theta\cap
Y}\alpha_{\mu}(x,y){\left\|{\nabla_{x}g_{\mu}(x,y)}\right\|}dy+\int_{Y_{\mu}\setminus(\Theta\cap
Y)}\alpha_{\mu}(x,y){\left\|{\nabla_{x}g_{\mu}(x,y)}\right\|}dy$
$\displaystyle\leq\int_{\Theta\cap
Y}\alpha_{\mu}(x,y){\left\|{\nabla_{x}g_{\mu}(x,y)}\right\|}dy+\int_{Z}\alpha_{\mu}(x,y){\left\|{\nabla_{x}g_{\mu}(x,y)}\right\|}dy,$

the boundedness of (4.26) and the limit (4.27) imply the boundedness of
${\left\|{\nabla v_{\mu}(x)}\right\|}$ on a neighborhood of $(\bar{x},0)$,
thus completing the proof. ∎

######  Lemma 4.17.

Suppose that the hypotheses of Lemma 4.15 hold. Then,

$\emptyset\neq\limsup_{x\to\bar{x},\mu\searrow 0}\nabla v_{\mu}(x)\subseteq
P(\bar{x}),$

where $P(\bar{x})$ is given in (2.3).

###### Proof.

That $\limsup_{x\to\bar{x},\mu\searrow 0}\nabla v_{\mu}(x)$ is nonempty
follows from Lemma 4.16. To prove the inclusion, suppose that $\nabla
v_{\mu_{k}}(x^{k})\to\xi\in{\rm I}\\!{\rm R}^{n}$ for some sequences
$x^{k}\to\bar{x}$ and $\mu_{k}\searrow 0$ as $k\to\infty$. We need to show
that $\xi\in P(\bar{x})$. As in Lemma 4.6, it suffices to show that for any
given $\varepsilon>0$, there exists an element of $P(\bar{x})$ within
$\varepsilon$ unit away from $\nabla v_{\mu_{k}}(x^{k})$, if $k$ is chosen
sufficiently large. That is, there exists $\xi^{k}\in P(\bar{x})$ such that
$\|\nabla v_{\mu_{k}}(x^{k})-\xi^{k}\|<\varepsilon$. Following similar
arguments in Lemma 4.6, we know that we can find points
$y_{1},y_{2},\dots,y_{r}\in S(\bar{x})$ and numbers
$\delta_{1},\delta_{2},\dots,\delta_{r}>0$ such that
$S(\bar{x})\subseteq\bigcup_{i=1}^{r}B_{\delta_{i}}(y_{i})$ and

$\partial_{x}g(x^{\prime},y^{\prime})\subseteq\partial_{x}g(\bar{x},y_{i})+\frac{\varepsilon}{3}B_{1}(0)\quad\forall
x^{\prime}\in B_{\delta_{i}}(\bar{x}),~{}y^{\prime}\in B_{\delta_{i}}(y_{i}),$

for $i=1,\dots,r$. Denote $Y_{1}\coloneqq Y\cap B_{\delta_{1}}(y_{1})$, and
$Y_{i}\coloneqq
Y\cap\left(B_{\delta_{i}}(y_{i})\setminus\bigcup_{j=1}^{i-1}B_{\delta_{j}}(y_{j})\right)$
for $i=2,\dots,r$. Moreover, we let $y_{r+1}$ be an arbitrary element of
$S(\bar{x})$, and we denote $Y_{r+1}^{k}\coloneqq
Y_{\mu_{k}}\setminus\bigcup_{i=1}^{r}B_{\delta_{i}}(y_{i})$.

From the uniform convergence of
$\operatorname*{dist}(\nabla_{x}g_{\mu}(x,\cdot),\partial_{x}g(x,\cdot))$ on
$Y$, we can find a $\delta>0$ such that
$\delta<\min\\{\delta_{1},\dots,\delta_{r}\\}$ and

$\operatorname*{dist}(\nabla_{x}g_{\mu}(x,y),\partial_{x}g(x,y))<\frac{\varepsilon}{3}\quad\forall\mu\in(0,\delta)~{}\text{and}~{}\forall(x,y)\in\operatorname*{cl}(B_{\delta}(\bar{x}))\times
Y.$ (4.28)

Setting $\Theta\coloneqq\bigcup_{i=1}^{r}B_{\delta_{i}}(y_{i})$ and
$Z\coloneqq Y\setminus\Theta$, we know that (4.27) holds since $\Theta$
contains $S(\bar{x})$. Hence, we may choose a smaller $\delta$ if necessary so
that (4.28) holds and at the same time,

$\int_{Z}\alpha_{\mu}(x,y){\left\|{\nabla_{x}g(x,y)}\right\|}dy<\frac{\varepsilon}{6}\qquad\forall\mu\in(0,\delta),~{}\forall
x\in\operatorname*{cl}(B_{\delta}(\bar{x})).$ (4.29)

Choosing a smaller $\delta$ if needed, we have from Lemma 4.15 that

$\int_{Z}\alpha_{\mu}(x,y)<\frac{\varepsilon}{6M}\qquad\forall\mu\in(0,\delta),~{}\forall
x\in\operatorname*{cl}(B_{\delta}(\bar{x})),$ (4.30)

where $M\coloneqq\max\\{\|\xi\|:\xi\in\partial_{x}g(\bar{x},y_{r+1})\\}$,
which is finite due to the boundedness of $\partial_{x}g(\bar{x},y_{r+1})$.

Now, let us choose $k$ to be large enough so that $x^{k}\in
B_{\delta}(\bar{x})$ and $\mu_{k}\in(0,\delta)$. Define $\xi^{k}$ as

$\xi^{k}\coloneqq\sum_{i=1}^{r}\int_{Y_{i}}\alpha_{\mu_{k}}(x^{k},y)\Pi_{\partial_{x}g(\bar{x},y_{i})}\left(\varphi^{(i)}_{k}(y)\right)dy+\int_{Y_{r+1}^{k}}\alpha_{\mu_{k}}(x^{k},y)\Pi_{\partial_{x}g(\bar{x},y_{r+1})}\left(\varphi^{(r+1)}_{k}(y)\right)dy,$

where $\varphi^{(i)}_{k}$ ($i=1,\dots,r$) is any single-valued mapping from
$Y_{i}$ to $\partial_{x}g(x^{k},y)$, and $\varphi^{(r+1)}_{k}$ is a single-
valued mapping from $Y_{r+1}^{k}$ to $\partial_{x}g(x^{k},y)$. Note that since
$Y_{r+1}^{k}\cup\left(\bigcup_{i=1}^{r}Y_{i}\right)=Y_{\mu_{k}}$,
$\int_{Y_{\mu_{k}}}\alpha_{\mu_{k}}(x^{k},y)dy=1$, and the range of
$\Pi_{\partial_{x}g(\bar{x},y_{i})}$ is contained in $P(\bar{x})$, it follows
that $\xi^{k}$ is indeed in $P(\bar{x})$ by Jensen’s inequality.

We show that $\|\nabla v_{\mu_{k}}(x^{k})-\xi^{k}\|<\varepsilon$. As before,
we denote by $E_{i}$ the set $E_{i}\coloneqq\\{y\in Y_{i}:g~{}\text{is not
differentiable at }(x^{k},y)\\}$ for each $i=1,\dots,r$, and we note that each
$E_{i}$ has zero Lebesgue measure. We can follow the same arguments in Lemma
4.6 to show that

${\left\|{\nabla_{x}g_{\mu_{k}}(x^{k},y)-\Pi_{\partial_{x}g(\bar{x},y_{i})}\left(\varphi^{(i)}_{k}(y)\right)}\right\|}<\frac{2\varepsilon}{3},\quad\forall
y\in Y_{i}\setminus E_{i},~{}i\in\\{1,\dots,r\\}.$ (4.31)

On the other hand, we also have

$\displaystyle{\left\|{\int_{Y_{r+1}^{k}}\alpha_{\mu_{k}}(x^{k},y)\left(\nabla_{x}g_{\mu_{k}}(x^{k},y)-\Pi_{\partial_{x}g(\bar{x},y_{r+1})}\left(\varphi^{(r+1)}_{k}(y)\right)\right)dy}\right\|}$
$\displaystyle\quad\leq\int_{Y_{r+1}^{k}}\alpha_{\mu_{k}}(x^{k},y){\left\|{\nabla_{x}g_{\mu_{k}}(x^{k},y)}\right\|}dy+\int_{Y_{r+1}^{k}}\alpha_{\mu_{k}}(x^{k},y){\left\|{\Pi_{\partial_{x}g(\bar{x},y_{r+1})}\left(\varphi^{(r+1)}_{k}(y)\right)}\right\|}dy$
$\displaystyle\quad\leq\int_{Z}\alpha_{\mu_{k}}(x^{k},y){\left\|{\nabla_{x}g_{\mu_{k}}(x^{k},y)}\right\|}dy+\int_{Z}\alpha_{\mu_{k}}(x^{k},y){\left\|{\Pi_{\partial_{x}g(\bar{x},y_{r+1})}\left(\varphi^{(r+1)}_{k}(y)\right)}\right\|}dy$
$\displaystyle\quad\overset{\eqref{eq:integral_epsilon_6}}{<}\frac{\varepsilon}{6}+M\int_{Z}\alpha_{\mu_{k}}(x^{k},y)dy$
$\displaystyle\quad\overset{\eqref{eq:integral_epsilon_6M}}{<}\frac{\varepsilon}{3},$
(4.32)

where second inequality holds since $Y_{r+1}^{k}\subseteq Z$ for any $k$.
Finally, we can use (4.32) and (4.31) to show that $\|\nabla
v_{\mu_{k}}(x^{k})-\xi^{k}\|<\varepsilon$ by arguing as in (4.19). ∎

We finally show that $v_{\mu}$ satisfies the gradient consistent property.

######  Theorem 4.18.

Under the hypotheses of Lemma 4.17, the family of smooth approximations
$\\{v_{\mu}:\mu>0\\}$ of $v$ satisfies the gradient consistent property at
$\bar{x}$ under any of the following conditions:

  1. (a)

$\nabla_{x}g(x,y)$ exists and is continuous on $\Omega\times O_{Y}$; or

  2. (b)

$g(\cdot,y)$ is $\rho$-weakly concave function on $\Omega$ for any $y\in Y$;
or

  3. (c)

(3.16) holds and $g$ is convex in $(x,y)$,

where $\Omega$ is a neighborhood of $\bar{x}$

###### Proof.

This is a direct consequence of Lemma 4.17, Theorem 3.7, Theorem 3.8 and
Theorem 3.9. ∎

##  5 Concluding Remarks

We have presented two techniques for deriving smooth approximations of the
value function corresponding to a nonsmooth function. One approach is through
the use of quadratic regularization, which is applicable when the lower-level
objective is convex in the decision variable of the lower-level problem. In
the absence of this convexity structure, we also present another technique by
entropic regularization, which does not require any other structural
assumption other than Lipschitz continuity. While smoothing approaches are
often employed for the practical purpose that optimization toolboxes usually
require smoothness, it is equally important to theoretically investigate
whether or not the smoothing algorithm will converge to a stationary point. In
this work, we also proved the gradient consistent property for the proposed
smoothing techniques, which serve as a primary tool for convergence analysis
of a smoothing algorithm. This paper provides the theoretical framework for
smoothing approaches for bilevel optimization problems. In our future work, we
will further investigate if we can relax the Lipschitz continuity assumption
on the lower-level objective function, which played a pivotal role in almost
all of our analyses. Existence of dominating functions which were required in
entropic regularization for unbounded constraint sets also deserve further
investigation. Finally, it is a subject of our future work to look into
practical implementations of gradient-based algorithms for solving the bilevel
optimization problem using the proposed smoothing functions for the value
function.

## References

  * Alcantara et al. [2021] Jan Harold Alcantara, Chieu Thanh Nguyen, Takayuki Okuno, Akiko Takeda, and Jein-Shan Chen.  Unified smoothing approach for best hyperparameter selection problem using a bilevel optimization strategy, 2021.  arXiv:2110.12630.
  * Beck [2017] Amir Beck.  _First-Order Methods in Optimization_.  SIAM - Society for Industrial and Applied Mathematics, Philadelphia, PA, United States, 2017.
  * Bertsekas [1971] Dimitri P. Bertsekas.  _Control of Uncertain Systems with a Set-Membership Description_.  Phd thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, May 1971.  Available at https://web.mit.edu/dimitrib/www/phdthesis.pdf.
  * Chen and Mangasarian [1995] Chunhui Chen and Olvi L. Mangasarian.  A class of smoothing functions for nonlinear and mixed complementarity problems.  _Mathematical Programming_ , 71:51–70, 1995.
  * Chen [2012] Xiaojun Chen.  Smoothing methods for nonsmooth, nonconvex minimization.  _Mathematical Programming Series B_ , 134:71–99, 2012.
  * Chen et al. [2011] Xiaojun Chen, Robert S. Womersley, and Jane J. Ye.  Minimizing the condition number of a gram matrix.  _SIAM Journal on Optimization_ , 21:127–148, 2011.
  * Clarke [1983] Frank H. Clarke.  _Optimization and Nonsmooth Analysis_.  Wiley-Interscience, New York, 1983.
  * Clarke et al. [1998] Frank H. Clarke, Yu. S Ledyaev, Ron J. Stern, and Peter R. Wolenski.  _Nonsmooth Analysis and Control Theory_.  Springer, New York, 1998.
  * Danskin [1967] John M. Danskin.  _The Theory of Max-Min and its Applications to Weapons Allocation Problems_.  Springer, New York, 1967.
  * Dempe and Zemkoho [2020] Stephan Dempe and Alain Zemkoho.  _Bilevel Optimization: Advances and Next Challenges_.  Springer Optimization and Its Applications. Springer International Publishing, 2020.  ISBN 9783030521196.
  * Dempe et al. [2015] Stephan Dempe, Vyacheslav Kalashnikov, Gerardo A. Pérez-Valdés, and Nataliya Kalashnykova.  _Bilevel Programming Problems: Theory, Algorithms and Applications to Energy Networks_.  Energy Systems. Springer Berlin Heidelberg, 2015.  ISBN 9783662458273.
  * Facchinei and Pang [2003] Francisco Facchinei and Jong-Shi Pang.  _Finite-Dimensional Variational Inequalities and Complementarity Problems_.  Springer-Verlag, New York, NY, 2003.
  * Fang and Wu [1996] Shu-Cherng Fang and Soon-Yi Wu.  Solving min-max problems and linear semi-infinite programs.  _Computers and Mathematics with Applications_ , 32(6):87–93, 1996.
  * Franceschi et al. [2018] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil.  Bilevel programming for hyperparameter optimization and meta-learning.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 1568–1577. PMLR, 10–15 Jul 2018.
  * Ghadimi and Wang [2018] Saeed Ghadimi and Mengdi Wang.  Approximation methods for bilevel programming, 2018.  arXiv:1802.02246.
  * Ji et al. [2021] Kaiyi Ji, Junjie Yang, and Yingbin Liang.  Bilevel optimization: Convergence analysis and enhanced design.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 4882–4892. PMLR, 18–24 Jul 2021.
  * Lampariello and Sagratella [2020] Lorenzo Lampariello and Simone Sagratella.  Numerically tractable optimistic bilevel problems.  _Computational Optimization and Applications_ , 76:277–303, 2020.
  * Li and Fang [1997] Xing-Si Li and Shu-Cherng Fang.  On the entropic regularization method for solving min-max problems with applications.  _Mathematical Methods of Operations Research_ , 46:119–130, 1997.
  * Lin et al. [2014] Gui-Hua Lin, Mengwei Xu, and Jane J. Ye.  On solving simple bilevel programs with a nonconvex lower level program.  _Mathematical Programming Series A_ , 144:277–305, 2014\.
  * Liu et al. [2023] Risheng Liu, Xuan Liu, Shangzhi Zeng, Jin Zhang, and Yixuan Zhang.  Value-function-based sequential minimization for bi-level optimization.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 45:15930 – 15948, 2023.
  * Liu et al. [2019] Tianxiang Liu, Ting-Kei Pong, and Akiko Takeda.  A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems.  _Mathematical Programming Series B_ , 176:339–367, 2019\.
  * Mirrlees [1999] James Mirrlees.  The theory of moral hazard and unobservable behaviour: Part i.  _Review of Economic Studies_ , 66(1):3–21, 1999\.
  * Okuno et al. [2021] Takayuki Okuno, Akiko Takeda, Akihiro Kawana, and Motokazu Watanabe.  On $\ell_{p}$-hyperparameter learning via bilevel nonsmooth optimization.  _Journal of Machine Learning Research_ , 22:1–47, 2021\.
  * Outrata [1990] Jiri Outrata.  On the numerical solution of a class of stackelberg problems.  _Zeitschrift fÃ¼r Operations Research_ , 34:255–277, 1990\.
  * Pedregosa [2016] Fabian Pedregosa.  Hyperparameter optimization with approximate gradient.  In Maria Florina Balcan and Kilian Q. Weinberger, editors, _Proceedings of The 33rd International Conference on Machine Learning_ , volume 48 of _Proceedings of Machine Learning Research_ , pages 737–746, New York, New York, USA, 20–22 Jun 2016. PMLR.
  * Rockafellar and Wets [1998] R. Tyrrell Rockafellar and Roger J-B Wets.  _Variational Analysis_ , volume 317 of _Grundlehren der MathematischenWissenschaften_.  Springer, Berlin, 1998.
  * Rudin [1991] Walter Rudin.  _Functional Analysis_.  International series in pure and applied mathematics. McGraw-Hill, 1991\.
  * von Stackelberg [2010] H. von Stackelberg.  _Market Structure and Equilibrium_.  Springer Science and Business Media, Berlin, 2010.
  * Ye and Daoli [1995] Jane J. Ye and Zhu Daoli.  Optimality conditions for bilevel programming problems.  _Optimization_ , 33:9–27, 1995.
  * Ye et al. [2023] Jane J. Ye, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang.  Difference of convex algorithms for bilevel programs with applications in hyperparameter selection.  _Mathematical Programming_ , 198:1583–1616, 2023.