Smooth bilevel stationary problems and their hypergradients

Let $p,d\ge 1$, let $\mathrm{\Theta }\subseteq {\mathbb{R}}^p$ and $W\subseteq {\mathbb{R}}^d$ be open, and let $f:\mathrm{\Theta }\times W\to \mathbb{R}$ be $C^2$ and $g:W\times \mathrm{\Theta }\to \mathbb{R}$ be $C^1$. Here $C^1$ means continuously differentiable on the open domain, and $C^2$ means that the derivative map is itself continuously differentiable. Gradients are column vectors, vector norms are Euclidean, and the norm of a matrix or linear map is the induced Euclidean operator norm.

For $(\theta ,w)\in \mathrm{\Theta }\times W$, define the inner stationarity residual $F(\theta ,w):={\mathrm{\nabla }}_{w}f(\theta ,w)\in {\mathbb{R}}^d$, its state Jacobian $H(\theta ,w):=D_{w}F(\theta ,w)\in {\mathbb{R}}^{d\times d}$, and its parameter Jacobian $B(\theta ,w):=D_{\theta }F(\theta ,w)\in {\mathbb{R}}^{d\times p}$. Thus $H$ is the inner Hessian and $B$ is the mixed derivative of the inner gradient. A point $({\theta }_0,w_0)$ is stationary when $F({\theta }_0,w_0)=0$. If a $C^1$ map $w^{\ast }:P\to Q$, for open neighborhoods $P\subseteq \mathrm{\Theta }$ of ${\theta }_0$ and $Q\subseteq W$ of $w_0$, satisfies $w^{\ast }({\theta }_0)=w_0$ and $F(\theta ,w^{\ast }(\theta ))=0$ for all $\theta \in P$, it is a local stationary branch. The associated outer objective is $J(\theta ):=g(w^{\ast }(\theta ),\theta )$, and its column gradient ${\mathrm{\nabla }}_{\theta }J$ is called the hypergradient of that branch. The definition of a local stationary branch imposes no global-minimality requirement.

For $\mu >0$, the phrase globally $\mu$-strongly convex in $w$ means that $f(\theta ,\cdot )$ is defined on all of ${\mathbb{R}}^d$ and, for every $u,v\in {\mathbb{R}}^d$, satisfies

$f(\theta ,v)\ge f(\theta ,u)+{\mathrm{\nabla }}_{w}f(\theta ,u{)}^T(v-u)+\frac{\mu }{2}\mathrm{\parallel }v-u{\mathrm{\parallel }}_2^2\mathrm{.}$

Continuously differentiable maps on open Euclidean domains

The C2 derivative-map convention for finite computational graphs