Deep Learning Approximation of Diffeomorphisms via Linear-Control Systems

Residual Neural Networks (ResNets) were originally introduced in [18] in order to overcome some issues related to the training process of traditional Deep Learning architectures. Indeed, it had been observed that, as the number of the layers in non-residual architectures is increased, the learning of the parameters is affected by the vanishing of the gradients (see, e.g., [7]) and the accuracy of the network gets rapidly saturated (see [17]). ResNets can be represented as the composition of non-linear mappings

$$\Phi=\Phi_{N}\circ\ldots\circ\Phi_{1},$$

where $N$ represents the depth of the Neural Network and, for every $k=1\ldots N$, the building blocks $\Phi_{k}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ are of the form

$$\Phi_{k}(x)=x+\sigma(W_{k}x+b_{k}),$$

(1.1)

where $\sigma:\mathbb{R}^{n}\to\mathbb{R}^{n}$ is a non-linear activation function that acts component-wise, and $W_{k}\in\mathbb{R}^{n\times n}$ and $b_{k}\in\mathbb{R}^{n}$ are the parameters to be learned. In contrast, we recall that in non-residual architectures $\bar{\Phi}=\bar{\Phi}_{N}\circ\ldots\circ\bar{\Phi}_{1}$, the building blocks have usually the form

$$\bar{\Phi}_{k}(x)=\sigma(W_{k}x+b_{k})$$

for $k=1,\ldots,N$. In some recent contributions [14, 19, 16], ResNets have been studied in the framework of Mathematical Control Theory. The bridge between ResNets and Control Theory was independently discovered in [14] and [16], where it was observed that each function $\Phi_{1},\ldots,\Phi_{N}$ defined as in (1.1) can be interpreted as an Explicit Euler discretization of the control system

$$\dot{x}=\sigma(Wx+b),$$

(1.2)

where $W$ and $b$ are the control variables. Since then, Control Theory has been fruitfully applied to the theoretical understanding of ResNets. In [24] a Universal Approximation result for the flow generated by (1.2) was established under suitable assumptions on the activation function $\sigma$. In [19] and [8] the problem of learning an unknown mapping was formulated as an Optimal Control problem, and the Pontryagin Maximum Principle was employed in order to learn the optimal parameters. In [10] it was consider the mean-field limit of (1.2), and it was proposed a training algorithm based on the discretization of the necessary optimality conditions for an Optimal Control problem in the space of probability measures. The Maximum Principle for Optimal Control of probability measures was first introduced in [21], and recently it has been independently rediscovered in [9]. In this paper, rather than using tools from Control Theory to study properties of existing ResNets, we propose an architecture inspired by theoretical observations on control systems with linear dependence in the control variables. As a matter of fact, the building blocks of the ResNets that we shall construct depend linearly in the parameters, namely they have the form

$$\Phi_{k}(x)=x+G(x)u_{k},$$

where $G:\mathbb{R}^{n}\to\mathbb{R}^{n\times l}$ is a non-linear function of the input, and $u_{k}\in\mathbb{R}^{l}$ is the vector of the parameters at the $k$-th layer. The starting points of this paper are the controllability results proved in [4, 5], where the authors considered a control system of the form

$$\dot{x}=F(x)u=\sum_{i=1}^{l}F_{i}(x)u_{i},$$

(1.3)

where $F_{1},\ldots,F_{l}$ are smooth and bounded vector fields on $\mathbb{R}^{n}$, and $u\in\mathcal{U}:=L^{2}([0,1],\mathbb{R}^{l})$ is the control. We immediately observe that (1.3) has a simpler structure than (1.2), having linear dependence with respect to the control variables. Despite this apparent simplicity, the flows associated to (1.3) are capable of interesting approximating results. Given a control $u\in\mathcal{U}$, let $\Phi_{u}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ be the flow obtained by evolving (1.3) on the time interval $[0,1]$ using the control $u$. In [5] it was formulated a condition for the controlled vector fields $F_{1},\ldots,F_{l}$ called Lie Algebra Strong Approximating Property. On one hand, this condition guarantees exact controllability on finite ensembles, i.e., for every $M\geq 1$, for every $\{x^{j}_{0}\}_{j=1,\ldots,M}\subset\mathbb{R}^{n}$ such that $j_{1}\neq j_{2}\implies x^{j_{1}}_{0}\neq x^{j_{2}}_{0}$, and for every injective mapping $\Psi:\mathbb{R}^{n}\to\mathbb{R}^{n}$, there exists a control $u\in\mathcal{U}$ such that $\Phi_{u}(x^{j}_{0})=\Psi(x^{j}_{0})$ for every $j=1,\ldots,M$. On the other hand, this property is also a sufficient condition for a $C^{0}$-approximate controllability result in the space of diffeomorphisms. More precisely, given a diffeomorphism $\Psi:\mathbb{R}^{n}\to\mathbb{R}^{n}$ diffeotopic to the identity, and given a compact set $K\subset\mathbb{R}^{n}$, for every $\varepsilon>0$ there exists a control $u_{\varepsilon}\in\mathcal{U}$ such that $\sup_{K}|\Phi_{u_{\varepsilon}}(x)-\Psi(x)|\leq\varepsilon$. The aim of this paper is to use this machinery to provide implementable algorithms for the approximation of diffeomorphisms diffeotopic to the identity. More precisely, we discretize the control system (1.3) on the evolution interval $[0,1]$ using the Explicit Euler scheme and the uniformly distributed time-nodes $\{0,\frac{1}{N},\ldots,\frac{N-1}{N},1\}$, and we obtain the ResNet represented by the composition $\Phi=\Phi_{N}\circ\ldots\circ\Phi_{1}$, where, for every $k=1,\ldots,N$, $\Phi_{k}$ is of the form

$$x_{k}=\Phi_{k}(x_{k-1})=x_{k-1}+h\sum_{i=1}^{l}F_{i}(x_{k-1})u_{i,k},\quad h=\frac{1}{N},$$

(1.4)

where $x_{0}\in\mathbb{R}^{n}$ represents an initial input of the network. In this construction, the points $(x_{k})_{k=0,\ldots,N}$ represent the approximations at the time-nodes $\{\frac{k}{N}\}_{k=0,\ldots,N}$ of the trajectory $x_{u}:[0,1]\to\mathbb{R}^{n}$ that solves (1.3) with Cauchy datum $x_{u}(0)=x_{0}$. We insist on the fact that in our discrete-time model we assume that the controls are piecewise constant on the time intervals $\left\{[\frac{k-1}{N},\frac{k}{N})\right\}_{k=1,\ldots,N}$. For this reason, when we derive a ResNet with $N$ hidden layers, we deal with $N$ building blocks (i.e., $\Phi_{1},\ldots,\Phi_{N}$) and with $N$ $l$-dimensional parameters $(u_{k})_{k=1,\ldots,N}=(u_{i,k})_{k=1,\ldots,N}^{i=1,\ldots,l}$. Moreover, when we evaluate the ResNet at a point $x_{0}\in\mathbb{R}^{n}$, we end up with $N+1$ input/output variables $(x_{k})_{k=0,\ldots,N}\subset\mathbb{R}^{n}$.

As anticipated before, we use the ResNet (1.4) for the task of a data-driven reconstruction of diffeomorphisms. The idea is that we may imagine to observe the action of an unknown diffeomorphism $\Psi:\mathbb{R}^{n}\to\mathbb{R}^{n}$ on a finite ensemble of points $\{x^{j}_{0}\}_{j=1,\ldots,M}$ with $M\geq 1$. Using these data, we try to approximate the mapping $\Psi$. Assuming that the controlled vector fields $F_{1},\ldots,F_{l}$ satisfy the Lie Algebra Strong Approximating Property, a first natural attempt consists in exploiting the exact controllability for finite ensembles. Indeed, this ensures that we can find a control $u^{M}\in\mathcal{U}$ that achieves a null training error, i.e., the corresponding flow $\Phi_{u^{M}}$ satisfies $\Phi_{u^{M}}(x^{j}_{0})=\Psi(x^{j}_{0})$ for every $j=1,\ldots,M$. Unfortunately, when the number of observation $M$ grows, this training strategy can not guarantee any theoretical upper bound for the generalization error. Indeed, as detailed in Section 4, in the case $\Psi$ is not itself a flow of the control system (1.3), if we pursue the null-training error strategy then the sequence of the controls $(u^{M})_{M\geq 1}$ will be unbounded in the $L^{2}$-norm. Since the Lipschitz constant of a flow generated by (1.3) is related to the $L^{2}$-norm of the corresponding control, it follows that we cannot bound from above the Lipschitz constants of the approximating diffeomorphisms $(\Phi_{u^{M}})_{M\geq 1}$. Therefore, even though for every $M\geq 1$ we achieve perfect matching $\Phi_{u^{M}}=\Psi$ on the training dataset $\{x_{0}^{j}\}_{j=1,\ldots,M}$, we have no control on the generalization error made outside the training points. This is an example of overfitting, a well-known phenomenon in the practice of Machine Learning.

In order to overcome this issue, when constructing the approximating diffeomorphism we need to find a balance between the training error and the $L^{2}$-norm of the control. For this reason we consider the non-linear functional $\mathcal{F}^{M}:\mathcal{U}\to\mathbb{R}$ defined on the space of admissible controls as follows:

$$\mathcal{F}^{M}(u):=\frac{1}{M}\sum_{j=1}^{M}a(\Phi_{u}(x^{j}_{0})-\Psi(x^{j}_{0}))+\frac{\beta}{2}||u||_{L^{2}}^{2},$$

(1.5)

where $a:\mathbb{R}^{n}\to\mathbb{R}$ is a non-negative function such that $a(0)=0$, and $\beta>0$ is a fixed parameter that tunes the squared $L^{2}$-norm regularization. A training strategy alternative to the one described above consists in looking for a minimizer $\tilde{u}^{M}$ of $\mathcal{F}^{M}$, and taking $\Phi_{\tilde{u}^{M}}$ as an approximation of $\Psi$. Under the assumption that the training dataset is sampled from a compactly-supported Borel probability measure $\mu$ on $\mathbb{R}^{n}$, we prove a $\Gamma$-convergence result. Namely, we show that, as the size $M$ of the training dataset tends to infinity, the problem of minimizing $\mathcal{F}^{M}$ converges to the problem of minimizing the functional $\mathcal{F}:\mathcal{U}\to\mathbb{R}$, defined as

$$\mathcal{F}(u):=\int_{\mathbb{R}^{n}}a(\Phi_{u}(x)-\Psi(x))\,d\mu(x)+\frac{\beta}{2}||u||_{L^{2}}^{2}.$$

(1.6)

Using this $\Gamma$-convergence result, we deduce the following upper bound for the expected testing error:

$$\mathbb{E}_{\mu}[a(\Phi_{\tilde{u}^{M}}(\cdot)-\Psi(\cdot))]\leq 2\kappa_{\beta}+C_{a,\Psi,\beta}W_{1}(\mu_{M},\mu),$$

(1.7)

where $\tilde{u}^{M}$ is a minimizer of $\mathcal{F}^{M}$, $\kappa_{\beta}$ and $C_{a,\Psi,\beta}$ are constants such that $\kappa_{\beta}\to 0$ and $C_{a,\Psi,\beta}\to\infty$ as $\beta\to 0$, and $W_{1}(\mu_{M},\mu)$ is the Wasserstein distance between $\mu$ and the empirical measure

$$\mu_{M}:=\frac{1}{M}\sum_{j=1}^{M}\delta_{x^{j}}.$$

Recalling that $W_{1}(\mu_{M},\mu)\to 0$ as $M\to\infty$, inequality (1.7) ensures that we can achieve arbitrarily small expected testing error by choosing $\beta$ small enough and having a large enough training dataset. Indeed, assuming that we can choose the size of the dataset, for every $\varepsilon>0$ we consider $\beta>0$ such that $\kappa_{\beta}\leq\frac{\varepsilon}{2}$, and then we take $M$ such that $C_{a,\Psi,\beta}W_{1}(\mu_{M},\mu)\leq\frac{\varepsilon}{2}$. We insist on the fact that the estimate in (1.7) holds a priori with respect to the choice of a testing dataset and the corresponding computation of the generalization error. We report that the minimization of the functional (1.6) plays a crucial role in [10].

On the base of the previous theoretical results, we propose two possible training algorithms to approximate the unknown diffeomorphism $\Psi$, having observed its action on an ensemble $\{x^{j}_{0}\}_{j=1,\ldots,M}$. The first one consists in introducing a finite-dimensional subspace $\mathcal{U}_{N}\subset\mathcal{U}$, and in projecting onto $\mathcal{U}_{N}$ the gradient flow induced by $\mathcal{F}^{M}$ in the space of admissible controls. Here we make use of the gradient flow formulation for optimal control problems derived in [23]. The second approach is based on the Pontryagin Maximum Principle, and it is similar to one followed in [19], [8], [10] for control system (1.2). We used the iterative method proposed in [22] for the the numerical resolution of Optimal Control problems. The main advantage of dealing with a linear-control system is that the maximization of the Hamiltonian (which is a key-step for the controls update) can be carried out with a low computational effort. In contrast, in [19] a non-linear optimization software was employed to manage this task, while in [10] the authors wrote the maximization as a root-finding problem and solved it with Brent’s method.
The paper is organized as follows. In Section 2 we establish the notations and we prove preliminary results regarding the flow generated by control system (1.3). In Section 3 we recall some results contained in [4] and [5] concerning exact and approximate controllability of ensembles. In Section 4 we explain why the “null training error strategy” is not suitable for the approximation purpose, and we outline the alternative strategy based on the resolution of an Optimal Control problem. In Section 5 we prove a $\Gamma$-convergence result that holds when the size $M$ of the training dataset tends to infinity. As a byproduct, we obtain the upper bound on the expected generalization error reported in (1.7). In Section 6 we describe the training algorithm based on the projection of the gradient flow induced by the cost $\mathcal{F}^{M}$. In Section 7 we propose the training procedure based on the Pontryagin Maximum Principle. In Section 8 we test numerically the algorithms by approximating a diffeomorphism in the plane.

In this paper we consider control systems of the form

$$\dot{x}=F(x)u=\sum_{i=1}^{l}F_{i}(x)u_{i},$$

(2.1)

where the controlled vector fields $(F_{i})_{i=1,\ldots,l}$ satisfy the following assumption.

In particular, this implies that there exists $C_{1}>0$ such that

$$\sup_{i=1,\ldots,l}\,\,\sup_{x,y\in\mathbb{R}^{n}}\frac{|F_{i}(x)-F_{i}(y)|_{2}}{|x-y|_{2}}\leq C_{1}$$

(2.2)

The space of admissible controls is $\mathcal{U}:=L^{2}([0,1],\mathbb{R}^{l})$, endowed with the usual Hilbert space structure. Using Assumption 1, the classical Caratéodory Theorem guarantees that, for every $u\in\mathcal{U}$ and for every $x_{0}\in\mathbb{R}^{n}$, the Cauchy problem

$$\begin{cases}\dot{x}(s)=\sum_{i=1}^{l}F_{i}(x(s))u_{i}(s),\\ x(0)=x_{0},\end{cases}$$

(2.3)

has a unique solution $x_{u,x_{0}}:[0,1]\to\mathbb{R}^{n}$. Hence, for every $u\in\mathcal{U}$, we can define the flow $\Phi_{u}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ as follows:

$$\Phi_{u}:x_{0}\mapsto x_{u,x_{0}}(1),$$

(2.4)

where $x_{u,x_{0}}$ solves (2.3). We recall that $\Phi_{u}$ is a diffeomorphism, since it is smooth and invertible.

In the paper we will make extensive use of the weak topology of $\mathcal{U}$. We recall that a sequence $(u_{\ell})_{\ell\geq 1}\subset\mathcal{U}$ is weakly convergent to an element $u\in\mathcal{U}$ if, for every $v\in\mathcal{U}$, we have that

$$\lim_{\ell\to\infty}\int_{0}^{1}v(s)u_{\ell}(s)\,ds=\int_{0}^{1}v(s)u(s)\,ds,$$

and we write $u_{\ell}\rightharpoonup_{L^{2}}u$. In the following result we consider a sequence of solutions of (2.3), corresponding to a weakly convergent sequence of controls.

We now prove an estimate of the Lipschitz constant of the flow $\Phi_{u}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ for $u\in\mathcal{U}$.

The next result regards the convergence of the flows $(\Phi_{u_{\ell}})_{\ell\geq 1}$ corresponding to a weakly convergent sequence $(u_{\ell})_{\ell\geq 1}\subset\mathcal{U}$.

In this section we recall the most important results regarding the issue of ensemble controllability. For the proofs and the statements in full generality we refer the reader to [4] and [5]. We begin with the definition of ensemble in $\mathbb{R}^{n}$. In this section we will further assume that $n>1$, which is the most interesting case.

We give the notion of reachable ensemble.

We recall the definition of Lie algebra generated by a system of vector fields. Given the vector fields $F_{1},\ldots,F_{l}$, the linear space $\mathrm{Lie}(F_{1},\ldots,F_{l})$ is defined as

$$\mathrm{Lie}(F_{1},\ldots,F_{l}):=\mathrm{span}\{[F_{i_{s}},[\ldots,[F_{i_{2}},F_{i_{1}}]\ldots]]:s\geq 1,i_{1},\ldots,i_{s}\in\{1,\ldots,l\}\},$$

(3.1)

where $[F,F^{\prime}]$ denotes the Lie bracket between $F,F^{\prime}$, smooth vector fields of $\mathbb{R}^{n}$. In the case of finite ensembles, i.e., when $|\Theta|=M<\infty$, we can provide sufficient condition for controllability. The proof reduces to the classical Chow-Rashevsky theorem (see ,e.g, the textbook [1]).

For a finite ensemble, the global exact controllability holds for a generic system of vector fields.

We recall that a set is said residual if it is the complement of a countable union of nowhere dense sets. Proposition 3.3 means that, given any $l$-tuple $(F_{1},\ldots,F_{l})$ of vector fields, the corresponding control system (2.1) can be made globally exactly controllable in $\mathcal{E}_{M}(\mathbb{R}^{n})$ by means of an arbitrary small perturbation of the fields $F_{1},\ldots,F_{l}$ in the $C^{m}$-topology.

When dealing with infinite ensembles, the notions of “exact reachable” and “exact controllable” are too strong. However, they can be replaced by their respective $C^{0}$-approximate versions.

Before stating the next result we introduce some notations. Given a vector field $X:\mathbb{R}^{n}\to\mathbb{R}^{n}$ and a compact set $K\subset\mathbb{R}^{n}$, we define

$$||X||_{1,K}:=\sup_{x\in K}\left(|X(x)|_{2}+\sum_{i=1}^{n}|D_{x_{i}}X(x)|_{2}\right).$$

Then we set

$$\mathrm{Lie}^{\delta}_{1,K}(F_{1},\ldots,F_{l}):=\{X\in\mathrm{Lie}(F_{1},\ldots,F_{l}):||X||_{1,K}\leq\delta\}.$$

We now formulate the assumption required for the approximability result.

The next result establishes a Universal Approximating Property for flows.

We recall that $\Psi:\mathbb{R}^{n}\to\mathbb{R}^{n}$ is diffeotopic to the identity if and only if there exists a family of diffeomorphisms $(\Psi_{s})_{s\in[0,1]}$ smoothly depending on $s$ such that $\Psi_{0}=\mathrm{Id}$ and $\Psi_{1}=\Psi$. In this case, $\Psi$ can be seen as the flow generated by the non-autonomous vector field $(s,x)\mapsto Y_{s}(x)$, where

$$Y_{s}(x):=\left.\frac{d}{d\varepsilon}\right|_{\varepsilon=0}\Psi_{s+\varepsilon}(x).$$

From Theorem 3.5 we can deduce a $C^{0}$-approximate reachability result for infinite ensembles.

We conclude this section with the exhibition of a system of vector fields in $\mathbb{R}^{n}$ meeting Assumptions 1 and 2.

In this section we introduce the central problem of the paper, i.e., the training of control system (2.1) in order to approximate an unknown diffeomorphism $\Psi:\mathbb{R}^{n}\to\mathbb{R}^{n}$ diffeotopic to the identity. A typical situation that may arise in applications is that we want to approximate $\Psi$ on a compact set $K\subset\mathbb{R}^{n}$, having observed the action of $\Psi$ on a finite number of training points $\{x^{1}_{0},\ldots,x^{M}_{0}\}\subset K$. Our aim is to formulate a strategy that is robust with respect to the size $M$ of the training dataset, and for which we can give upper bounds for the generalization error. In order to obtain higher and higher degree of approximation, we may thing to triangulate the compact set $K$ with an increasing number of nodes where we can evaluate the unknown map $\Psi$. Using the language introduced in Section 3, we have that, for every $M\geq 1$, we may understand a triangulation of $K$ with $M$ nodes as an ensemble $\alpha^{M}(\cdot)\in\mathcal{E}_{M}(\mathbb{R}^{n})$. After evaluating $\Psi$ in the nodes, we obtain the target ensemble $\gamma^{M}(\cdot)\in\mathcal{E}_{M}(\mathbb{R}^{n})$ as $\gamma^{M}(\cdot):=\Psi(\alpha^{M}(\cdot))$.

If the vector fields $F_{1},\ldots,F_{l}$ that define control system (2.1) meet Assumptions 1 and 2, then Theorem 3.2 and Remark 3.7 may suggest a first natural attempt to design an approximation strategy. Indeed, for every $M$, we can exactly steer the ensemble $\alpha^{M}(\cdot)$ to the ensemble $\gamma^{M}(\cdot)$ with an admissible control $u^{M}\in\mathcal{U}$. Hence, we can choose the flow $\Phi_{u^{M}}$ defined in (2.4) as an approximation of $\Psi$ on $K$, achieving a null training error. Assume that, for every $M\geq 1$, the corresponding triangulation is a $\epsilon^{M}$-approximation of the set $K$, i.e., for every $y\in K$ there exists $\bar{j}\in\{1,\ldots,M\}$ such that $|y-x^{\bar{j},M}_{0}|_{2}\leq\epsilon^{M}$, where $x^{\bar{j},M}_{0}:=\alpha^{M}(\bar{j})$. Then, for every $y\in K$, we can give the following estimate for the generalization error:

	$\displaystyle|\Psi(y)-\Phi_{u^{M}}(y)|_{2}$	$\displaystyle\leq|\Psi(y)-\Psi(x^{\bar{j},M}_{0})|_{2}+|\Phi_{u^{M}}(x^{\bar{j},M}_{0})-\Phi_{u^{M}}(y)|_{2}$
		$\displaystyle\leq L_{\Psi}\epsilon^{M}+L_{\Phi_{u^{M}}}\epsilon^{M},$

where $L_{\Psi},L_{\Phi_{u^{M}}}$ are respectively the Lipschitz constants of $\Psi$ and $\Phi_{u^{M}}$. Assuming (as it is natural to do) that $\epsilon^{M}\to 0$ as $M\to\infty$, the strategy of achieving zero training error works if, for example, the Lipschitz constants of the approximating flows $(\Phi_{u^{M}})_{M\geq 1}$ keep bounded. This in turn would follow if the sequence of controls $(u^{M})_{M\geq 1}$ were bounded in $L^{2}$-norm. However, as we are going to see in the following proposition, in general this is not the case. Let us define

$$\mathrm{Flows}_{K}(F_{1},\ldots,F_{l}):=\{\Phi_{u}:u\in\mathcal{U}\},$$

the space of flows restricted to $K$ obtained via (2.4) with admissible controls, and let $\mathrm{Diff}_{K}^{0}(\mathbb{R}^{n})$ be the space of diffeomorphisms diffeotopic to the identity restricted to $K$. Theorem 3.5 guarantees that, for every $K\subset\mathbb{R}^{n}$,

$$\overline{\mathrm{Flows}_{K}(F_{1},\ldots,F_{l})}^{C^{0}}=\mathrm{Diff}_{K}^{0}(\mathbb{R}^{n}).$$