{'fraction_non_alphanumeric': 0.04635432826559106, 'fraction_numerical': 0.020312338401075603, 'mean_word_length': 3.5216984661429107, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 45, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Universal Approximation Power of Deep Neural Networks via Nonlinear Control Theory

In this paper, we explain the universal approximation capabilities of deep neural networks through geometric nonlinear control. Inspired by recent work establishing links between residual networks and control systems, we provide a general sufficient condition for a residual network to have the power of universal approximation by asking the activation function, or one of its derivatives, to satisfy a quadratic differential equation. Many activation functions used in practice satisfy this assumption, exactly or approximately, and we show this property to be sufficient for an adequately deep neural network with n states to approximate arbitrarily well any continuous function defined on a compact subset of R^n. We further show this result to hold for very simple architectures, where the weights only need to assume two values. The key technical contribution consists of relating the universal approximation problem to controllability of an ensemble of control systems corresponding to a residual network, and to leverage classical Lie algebraic techniques to characterize controllability.


Introduction
In the past few years, we have witnessed a resurgence in the use of techniques from dynamical and control systems for the analysis of neural networks. This recent development was sparked by the papers [Weinan, 2017, Haber and Ruthotto, 2017, Lu et al., 2018] establishing a connection between certain classes of neural networks, such as residual networks [He et al., 2016], and control systems. However, the use of dynamical and control systems to describe and analyze neural networks goes back at least to the 70's. For example, Wilson-Cowan's equations [Wilson and Cowan, 1972] are differential equations and so is the model proposed by Hopfield in [Hopfield, 1984]. These techniques have been used to study several problems such as weight identifiability from data , controllability Qiao, 1999, Sontag andSussmann, 1997], and stability [Michel et al., 1989, Hirsch, 1989.
The objective of this paper is to shed new light into the approximation power of deep neural networks. It has been empirically observed that deep networks have better approximation capabilities than their shallow counterparts and are easier to train [Ba andCaruana, 2014, Urban et al., 2017]. An intuitive explanation for this fact is based on the different ways in which these types of networks perform function approximation. While shallow networks prioritize parallel compositions of simple functions (the number of neurons per layer is a measure of parallelism), deep networks prioritize sequential compositions of simple functions (the number of layers is a measure sequentiality). It is therefore natural to seek insights using control theory where the problem of producing interesting behavior by manipulating a few inputs over time, i.e., by sequentially composing them, has been extensively studied. Even though control-theoretic techniques have been utilized in the literature to showcase the controllability properties of neural networks, to best of our knowledge, this paper is the first to use tools from geometric control theory to analyze the function approximation properties of deep neural networks given an ensemble of data points. As we illustrate, the latter makes the problem challenging, as we are required to design a single input, for the control system modeling a neural network, driving an ensemble of initial data points to target data points dictated by the function to be approximated, while guaranteeing function approximation in an appropriate norm.
The work of the first author was supported the CONIX research center, one of six centers in JUMP, a Semiconductor Research Corporation (SRC) program sponsored by DARPA. The work of the second author was supported by the Alexander von Humboldt Foundation, and the Natural Sciences and Engineering Research Council of Canada.
1.1. Contributions. In this paper we focus on residual networks. This being said, as explained in [Lu et al., 2018], similar techniques can be exploited to analyze other classes of networks. It is known that deep residual networks have the power of universal approximation. What is less understood is where this power comes from. We show in this paper that it stems from the activation functions in the sense that when using a sufficiently rich activation function, even networks with very simple architectures and weights taking only two values suffice for universal approximation. It is the power of sequential composition, analyzed in this paper via geometric control theory, that unpacks the richness of the activation function into universal approximability. Surprisingly, the level of richness required from an activation function also has a very simple characterization; it suffices for activation functions (or a suitable derivative) to satisfy a quadratic differential equation. Most activation functions in the literature either satisfy this condition or can be suitably approximated by functions satisfying it.
More specifically, given an ensemble of data points, we cast the problem of designing weights for training a deep residual network as the problem of driving the state of an ensemble of initial points with a single openloop control input to the ensemble of target points produced by the function to be learned when evaluated at the initial points. In spite of the fact that we only have access to a single open-loop control input, we prove that the corresponding ensemble of control systems is generically controllable. We then utilize this property to obtain universal approximability results for continuous functions in an L p sense.
1.2. Related work. Several papers have studied and established that residual networks have the power of universal approximation. This was done in [Lin and Jegelka, 2018] by focusing on the particular case of residual networks with the ReLU activation function. It was shown that any such network with n states and one neuron per layer can approximate an arbitrary Lebesgue integrable function f : R n Ñ R. The paper [Zhang et al., 2019] shows that the functions described by deep networks with n states per layer, when these networks are modeled as control systems, are restricted to be homeomorphisms. The authors then show that increasing the number of states per layer to 2n suffices to approximate arbitrary homeomorphisms f : R n Ñ R n . Note that the results in [Lin and Jegelka, 2018] do not model deep networks as control systems and, for this reason, bypass the homeomorphism restriction. There is also an important distinction to be made between requiring a network to exactly implement a function and to approximate it. The homeomorphism restriction does not prevent a network from approximating arbitrary functions; it just restricts the functions that can be implemented as a network. Closer to this paper are the results in [Li et al., 2019] establishing universal approximation based on a general sufficient condition satisfied by several examples of activation functions. Deep networks are modeled as control systems 9 x " f px, uq and the sufficient conditions are placed on f px, uq " f u pxq regarded as a family of functions f u : R n Ñ R n parametrized by the control input u. It is proved that if this family is sufficiently rich, e.g., by requiring a certain closure of its convex hull to contain a well function, then universal approximability follows. These results are a major step forward in identifying what is needed for universal approximability, as they are not tied to specific architectures or activation functions. In this paper, we go further by deriving sufficient conditions directly on the activation function. The key difference is that all the work required to unpack the richness of the activation function into universal approximability is done by suitably sequentially composing the simple functions f u : R n Ñ R n , i.e., by training the network. In contrast, the sufficient conditions proposed in [Li et al., 2019] require some of this work to be done when determining if such conditions are satisfied. In other words, determining if a certain closure of the convex hull of the family f u contains a well function can be seen as testing if well functions can be written as a combination of the simpler functions f u .
Other papers, e.g., [Lu et al., 2017, Daubechies et al., 2019 have used different metrics to compare the approximation power of deep networks with shallow networks or other classes of universal approximation schemes and are less related to our results.
At the technical level, our results build upon the controllability properties of deep networks studied in this paper for the first time. Earlier work on controllability of differential equation models for neural networks, e.g., [Sontag and Qiao, 1999], assumed the weights to be constant and that an exogenous control signal was fed into the neurons. In contrast, we regard the weights as control inputs and that no additional control inputs are present. These two different interpretations of the model lead to two very different technical problems. More recent work in the control community includes [Agrachev and Caponigro, 2009], where it is shown that any orientation preserving diffeomorphism on a compact manifold, can be obtained as the flow of a control system when using a time-varying feedback controller. In the context of this paper those results can be understood as: residual networks can represent any orientation preserving diffeomorphism provided that we can make the weights depend on the state. Although quite insightful, such results are not applicable to the standard neural network models where the weights are not allowed to depend on the state. Another relevant topic is ensemble control. Most of the work on the control of ensembles, see for instance [Li and Khaneja, 2006, Helmke and Schönlein, 2014, Brockett, 2007, considers parametrized ensembles of vector fields. In other words, the individual systems that drive the state of the whole ensemble are different, whereas in our setting the ensemble consists of exact copies of the same system, albeit initialized differently. In this sense, our work is most closely related to the setting of [Agrachev and Sarychev, 2020] where controllability results for ensembles of infinitely many control systems are provided. In this paper, in contrast, we are concerned with only finitely many systems and the specific structure of the problem at hand allows us to provide sharp controllability conditions. 2. Control-theoretic view of residual networks 2.1. From residual networks to control systems and back. We start by providing a control system perspective on residual neural networks. We mostly follow the treatment proposed in [Weinan, 2017, Haber and Ruthotto, 2017, Lu et al., 2018, where it was suggested that residual neural networks with an update equation of the form: where k P N 0 indexes each layer, xpkq P R n , and pSpkq, W pkq, bpkqq P R nˆnˆRnˆnˆRn , can be interpreted as a control system when k is viewed as indexing time. In (2.1), Sp¨q, W p¨q, and bp¨q are the weights functions assigning weights to each time instant k, and Σ : R n Ñ R n is of the form Σpxq " pσpx 1 q, σpx 2 q, . . . , σpx n qq, where σ : R n Ñ R n is an activation function. By drawing an analogy between (2.1) and Euler's forward method to discretize differential equations, one can interpret (2.1) as the time discretization of the continuous-time control system: where xptq P R n and pSptq, W ptq, bptqq P R nˆnˆRnˆnˆRn ; in what follows, and in order to make the presentation simpler, we sometimes drop the dependency on time. To make the connection between the discretization and (2.2) precise, let x : r0, τ s Ñ R n be a solution of the control system (2.2) for the control input pS, W, bq : r0, τ s Ñ R nˆnˆRnˆnˆRn , where τ P R`. Then, given any desired accuracy ε P R`and any norm |¨| in R n , there exists a sufficiently small time step T P R`so that the function z : t0, 1, . . . , tτ {T uu Ñ R n defined by: zp0q " xp0q, zpk`1q " zpkq`T SpkT qΣpW pkT qzpkq`bpkT qq, approximates the sequence txpkT qu k"0,...,tτ {T u with error ε, i.e.: |zpkq´xpkT q| ď ε, for all k P t0, 1, . . . , tτ {T uu. Intuitively, any statement about the solutions of (2.2) holds for the solutions of (2.1) with arbitrarily small error ε, provided that we can choose the depth to be arbitrarily large since by making T small we increase the depth, given by 1`tτ {T u.
2.2. Network training and controllability. Given a function f : R n Ñ R n and a finite set of samples E samples Ă R n , the problem of training a residual network so that it maps x P E samples to f pxq can be phrased as the problem of constructing an open-loop control input pS, W, bq : r0, τ s Ñ R nˆnˆRnˆnˆRn so that the resulting solution of (2.2) takes the sates x P E samples to the states f pxq. It should then come as no surprise that the ability to approximate a function f is tightly connected with the control-theoretic problem of controllability: given, one initial state x init P R n and one final state x fin P R n , when does there exist a finite time τ P R`and a control input pS, W, bq : r0, τ s Ñ R nˆnˆRnˆnˆRn so that the solution of (2.2) starting at x init at time 0 ends at x fin at time τ ?
To make the connection between controllability and the problem of mapping every x P E samples to f pxq clear, it is convenient to consider the ensemble of d " |E samples | copies of (2.2) given by the matrix differential equation: Xptq " rSptqΣpW ptqX ‚1 ptq`bptqq|SptqΣpW ptqX ‚2 ptq`bptqq| . . . |SptqΣpW X ‚d ptq`bptqqqs , where for time t P R0 the ith column of the matrix Xptq P R nˆd , denoted by X ‚i ptq, is the solution of the ith copy of (2.2) in the ensemble. If we now index the elements of E samples as tx 1 , . . . , x d u, where d is the cardinality of E samples , and consider the matrices X init " rx 1 |x 2 | . . . |x n s and X fin " rf px 1 q|f px 2 q| . . . |f px n qs, we see that the existence of a control input resulting in a solution of (2.3) starting at X init and ending at X fin , i.e., controllability of (2.3), is equivalent to existence of an input for (2.2) so that the resulting solution starting at x i P E samples ends at f px i q, for all i P t1, . . . , du.
Note that achieving controllability of (2.3) is especially difficult, since all the copies of (2.2) in (2.3) are identical and they all use the same input. Therefore, to achieve controllability, we must have sufficient diversity in the initial conditions to overcome the symmetries present in (2.3), see [Aguilar and Gharesifard, 2014]. Our controllability result, Theorem 4.2, describes precisely such diversity. As mentioned in the introduction, this observation also distinguishes the problem under study here from the classical setting of ensemble control [Li andKhaneja, 2006, Helmke andSchönlein, 2014], with the exception of the recent work [Agrachev and Sarychev, 2020], where a collection of systems with different dynamics are driven by the same control input.

Problem formulation
Our starting point is the control system: (3.1) 9 xptq " sptqΣpW ptqxptq`bptqq, a slightly simplified version of (2.2), where xptq P R n , psptq, W ptq, bptqq P RˆR nˆnˆRn , and the input Sp¨q in (2.2) is now the scalar-valued function sp¨q; as we will prove in what follows, this model is enough for universal approximation. In fact, we will later see 1 that it suffices to let s assume two arbitrary values only (one positive and one negative). Moreover, for certain activation functions, we can dispense with s altogether.
We make the following assumptions regarding the model (3.1): ‚ The function Σ is defined as Σ : x Þ Ñ pσpx 1 q, σpx 2 q, . . . , σpx n qq, where the activation function σ : R Ñ R, or a suitable derivative of it, satisfies a quadratic differential equation, i.e., Dξ " a 0`a1 ξ`a 2 ξ 2 with a 1 , a 2 , a 3 P R, a 2 ‰ 0, and ξ " D j σ for some j P N 0 . Here, D j σ denotes the derivative of σ of order j and D 0 σ " σ. ‚ The activation function σ : R Ñ R is Lipschitz continuous and ξ " D j σ defined above is injective.
Several activation functions used in the literature are solutions of quadratic differential equations as can be seen in Table 1. Moreover, activation functions that are not differentiable can also be handled via approximation. For example, the ReLU function defined by maxt0, xu can be approximated by σpxq " logp1`e rx q{r, as r Ñ 8, which satisfies the quadratic differential equation given in Table 1.
The Lipschitz continuity assumption is made to simplify the presentation and can be replaced with local Lipschitz continuity, which then does not need to be assumed, since σ is analytic in virtue of being the solution of an analytic (quadratic) differential equation. Moreover, all the activation functions in Table 1 are Lipschitz continuous and injective.

Function name
Definition Satisfied differential equation Table 1. Activation functions and the differential equations they satisfy.
To formally state the problem under study in this paper, we need to discuss a different point of view on the solutions of the control system (3.1) given by flows. A continuously differentiable curve x : r0, τ s Ñ R n is said to be a solution of (3.1) under the piecewise continuous input ps, W, bq : r0, τ s Ñ RˆR nˆnˆRn if it satisfies (3.1). Under the stated assumptions on σ, given a piecewise continuous input and a state x init P R n , there is one and at most one solution xp¨q of (3.1) satisfying xp0q " x init . Moreover, solutions are defined for all τ P R0 . We can thus define the flow of (3.1) under the input ps, W, bq as the map φ τ : R n Ñ R n given by the assignment x init Þ Ñ xpτ q. In other words, φ τ px init q is the point reached at time τ by the unique solution starting at x init at time 0. When the time τ is clear from context, we denote a flow simply by φ.
We will use flows to approximate arbitrary continuous functions f : R n Ñ R m . Since flows have the same domain and co-domain, and f : R n Ñ R m may not, we first lift f to a mapf : R k Ñ R k . When n ą m, we lift f tof " ı˝f : R n Ñ R n , where ı : R m Ñ R n is the injection given by ıpxq " px 1 , . . . , x n , 0, . . . , 0q. In this case k " n. When n ă m, we lift f tof " f˝π : R m Ñ R m , where π : R m Ñ R n is the projection πpx 1 , . . . , x n , x n`1 , . . . , x m q " px 1 , . . . , x n q. In this case k " m. Although we could consider factoring f through a map g : R n Ñ R m , i.e., to constructf : R n Ñ R n so that f " g˝f as done in, e.g., [Li et al., 2019], the construction of g requires a deep understanding of f , since a necessary condition for this factorization is f pR n q Ď gpR n q. Constructing g so as to contain f pR n q on its image requires understanding what f pR n q is and this information is not available in learning problems. Given this discussion, in the remainder of this paper we directly assume we seek to approximate a map f : R n Ñ R n .
The final ingredient we need before stating the problem solved in this paper is the precise notion of approximation. Throughout the paper, we will utilize approximation in the sense of L p norms, where 1 ď p ă 8, i.e., where E Ă R n is the compact set over which is the approximation is going to be conducted and 2 |f pxq| 8 " max iPt1,...,nu |f i pxq|. For some results we will also use the infinity norm defined as follows for the previously mentioned function f : We are now ready to state the problem that we study in this paper.
Problem 3.1. Let f : R n Ñ R n be a continuous function, E Ă R n be a compact set, and ε P R`be the desired approximation accuracy. Under what conditions on the activation function of control system (3.1) does there exist a time τ P R`and an input ps, W, bq : r0, τ s Ñ RˆR nˆnˆRn so that the flow φ τ : R n Ñ R n defined by the solution of (3.1) under the said input satisfies: for 1 ď p ď 8?
In the next section, we will show the answer is remarkably simple. It suffices for the activation function to satisfy a quadratic differential equation. As we argued in the previous section, several activation functions satisfy this assumption exactly or approximately.

Function approximation through controllability
4.1. Outline of the technical arguments. We approximate the function f : R n Ñ R n on the compact set E Ă R n by a flow φ generated by the control system (3.1) in several steps. We first build a flow ψ by constructing a discrete set E samples Ă E that approximates E and by crafting ψ so that it approximately satisfies ψpxq " f pxq for all x P E samples . In order to control the mismatch between ψ and f at points in E but not in E samples , we build another flow ψ 1 of (3.1) that takes most points in E but not in E samples to points sufficiently close to E samples . Points not taken to E samples by ψ 1 will form a set that can be made arbitrarily small and thus have a small contribution to the approximation error in the L p sense for 1 ď p ă 8. We then show that φ " ψ˝ψ 1 approximates f . This strategy was already employed in [Li et al., 2019], however, our construction of ψ differs significantly from the one proposed in [Li et al., 2019]. The technique employed in [Li et al., 2019] consists of directly constructing ψ using the so-called well functions, whereas we only use the fact that σ satisfies a quadratic differential equation and leverage tools from geometric control theory to establish controllability of the ensemble (2.3).
Let us take E samples " tx 1 , x 2 , . . . , x d u, where d is the number of copies of the control system (3.1) in (2.3).
If the ensemble control system (2.3) is controllable on a manifold M Ă R nˆd , then given the initial state we can find a time τ P Rà nd an input ps, W, bq : r0, τ s Ñ RˆR nˆnˆRn so that the solution Xp¨q of (2.3) satisfies Xp0q " X init and Xpτ q " X fin . This, in turn, implies that the flow ψ defined by the solution of (3.1) under the input ps, W, bq takes every x P E samples to f pxq. It is simple to see that controllability of (2.3) cannot hold on all of R nˆd , since if the initial state Xp0q satisfies X ‚i p0q " X ‚j p0q for some i ‰ j, we must have X ‚i ptq " X ‚j ptq for all t P r0, τ s; as we will see shortly, for the previously described purpose of function approximation, such scenarios will not be an issue. Remarkably, we show in Theorem 5.1 that controllability only fails in cases similar to the one we just described.

4.2.
Main results. Our first result establishes that the controllability property holds for the ensemble control system (2.3) on a dense and connected sub-manifold of R nˆd , independently of the (finite) number of copies d, as long the activation function satisfies a quadratic differential equation. Before stating this result, we recall the formal definition of controllability.
Definition 4.1. A point X fin P R nˆd is said to be reachable from a point X init P R nˆd for the control system (2.3) if there exist τ P R`and a control input ps, W, bq : r0, τ s Ñ RˆR nˆnˆRn so that the solution X of (2.3) under said input satisfies Xp0q " X init and Xpτ q " X fin . Control system (2.3) is said to be controllable on a submanifold M of R nˆd if any point in M is reachable from any point in M .
Theorem 4.2. Consider the control system given by (2.3) and let N Ă R nˆd be the set defined by: Suppose that σ is injective and satisfies the quadratic differential equation Dσ " a 0`a1 σ`a 2 σ 2 with a 2 ‰ 0. If n ą 1, then the ensemble control system (2.3) is controllable on M " R nˆd zN .
We postpone the proof of this result to the Appendix. The following corollary of Theorem 4.2 on reachability is useful to prove one of our latter results; its proof can also be found in the Appendix.
Corollary 4.3. Consider the control system given by (2.3) and let M Ă R nˆd be the manifold defined in Theorem 4.2. Under assumptions of Theorem 4.2, any point in M is reachable from a point A P R nˆd for which: holds for all i ‰ j, where i, j P t1, . . . , du.
Some remarks are in order. The assumptions above on σ can be relaxed; in particular, it is enough for D j σ to be injective and to satisfy the mentioned quadratic differential equation for some j P N 0 . Moreover, Theorem 4.2 and Corollary 4.3 do not directly apply to the ReLU activation function, defined by maxt0, xu, since this function is not differentiable. However, the ReLU is approximated by the activation function: 1 r logp1`e rx q, as r Ñ 8. In particular, as r Ñ 8 the ensemble control system (2.3) with σpxq " logp1`e rx q{r converges to the ensemble control system (2.3) with σpxq " maxt0, xu and thus the solutions of the latter are arbitrarily close to the solutions of the former whenever r is large enough. Moreover, ξ " Dσ satisfies Dξ " rξ´rξ 2 and Dξ " re rx {p1`e rx q 2 ą 0 for x P R and r ą 0 thus showing that ξ is an increasing function and, consequently, injective.
The conclusions of Theorem 4.2 and Corollary 4.3 also hold if we weaken the assumptions on the inputs of (3.1). It suffices for the entries of W and b to take values on a set with two elements, see the discussion after the proof of Theorem 4.2 for details. Moreover, when the activation function is and odd function, i.e., σp´xq "´σpxq, as is the case for the hyperbolic tangent, the conclusions of Theorem 4.2 hold for the simpler version of (3.1), where we fix s to be 1.
It is worthwhile comparing the assumption in Theorem 4.2 with the assumptions in Theorem 2.3, page 8, of [Li et al., 2019]; the reader not familiar with the latter result can safely pass this technical point. To make the comparison transparent, we consider n " 2 and the family of vector fields F " tXȋ , Yȋ j u i,j"1,2 defined by: The proof of Theorem 4.2 shows this family to be controllable 3 . In particular, the conclusions of Theorem 4.2 hold for any network for which there exists a choice of constant weights that, when used, make the right hand side of (3.1) become one of these vector fields. If we apply Theorem 2.3 of [Li et al., 2019] to this family, we would first compute the corresponding convex hull of F , given by: and would then require convpF q to either contain a well-function or to contain a sequence of functions converging to a well-function. For our purposes it suffices to recall that if g : R n Ñ R is a well-function (see [Li et al., 2019] for the exact definition) then its zero set, i.e., the set tx P R n | gpxq " 0u, is bounded and contains an open set. When σ is the ReLU, this assumption is not satisfied. The reasoning for this is as follows. Consider Z P convpF q, which is of the form: for some u 1 , u 11 , u 12 as prescribed above. There are four cases to be considered: 1) x 1 ă 0 and x 2 ă 0; in this case, the first component of Z which we denote by Z 1 is given by Z 1 px 1 , x 2 q " u 1 . The zero set of this function is non-empty when u 1 " 0 and, in such case, it is not bounded. Hence, Z 1 is not a well-function; 2) x 1 ă 0 and x 2 ą 0; in this case Z 1 px 1 , x 2 q " u 1`u12 x 2 . If u 12 ‰ 0 then the zero set of Z 1 does not contain an open set since it consists of a point. When u 12 " 0 we are back to case 1). Hence, we conclude that Z 1 is not a well function; 3) x 1 ą 0 and x 2 ă 0; same as case 2); 4) x 1 ą 0 and x 2 ą 0; in this case Z 1 px 1 , x 2 q " u 1`u11 x 1`u12 x 2 and similar arguments show the zero set of Z 1 is either empty, a single point, or unbounded.
We now state our main results. The first asserts that any continuous function f : R n Ñ R n that is the Cartesian product of n strictly monotone functions f i : R Ñ R, i.e., f pxq " pf 1 px 1 q, . . . , f n px n qq and x i ą x 1 i implies f i px i q ą f i px 1 i q for i P t1, . . . , nu, can be approximated with any desired accuracy on any compact set E Ă R n with respect to the infinity norm. The second result does not rely on the monotonicity assumption, however, weakens the infinity norm to the L p norm.
Proposition 4.4. Assume there exists k P N 0 so that ξ " D k σ is injective and satisfies a quadratic differential equation Dξ " a 0`a1 ξ`a 2 ξ 2 with a 2 ‰ 0. Then, for every continuous function f : R n Ñ R n that is the Cartesian product of n strictly monotone functions, for every compact set E Ă R n , and for every ε P R`there exist a time τ P R`and an input ps, W, bq : r0, τ s Ñ RˆR nˆnˆRn so that the flow φ τ : R n Ñ R n defined by the solution of (3.1) under the said input satisfies: The proof of this result and the next are provided in the appendix.
Theorem 4.5. Let n ą 1 and assume there exists k P N 0 so that ξ " D k σ is injective and satisfies a quadratic differential equation Dξ " a 0`a1 ξ`a 2 ξ 2 with a 2 ‰ 0. Then, for every continuous function f : R n Ñ R n , for every compact set E Ă R n , and for every ε P R`there exist a time τ P R`and an input ps, W, bq : r0, τ s Ñ RˆR nˆnˆRn so that the flow φ τ : R n Ñ R n defined by the solution of (3.1) under the said input satisfies: This result generalizes that of [Li et al., 2019] in the sense that it does not require the well-function assumption and the sufficient condition for approximability is stated directly in terms of the activation function. Moreover, the conclusions of Theorem 4.5 hold for a class of neural networks larger than (3.1), as discussed after the proof of Theorem 4.2.

Proofs
The proof of Theorem 4.2 is based on two technical results. The first characterizes the rank of a certain matrix that will be required for our controllability result. In essence, the proof of this result follows from [Krattenthaler, 2001, Proposition 1], however, we provide a proof for completeness.
Lemma 5.1. Let ξ : R Ñ R be a function that satisfies the quadratic differential equation: Dξpxq " a 0`a1 ξpxq`a 2 ξ 2 pxq, where a 0 , a 1 , a 2 P R. Suppose that derivatives of ξ of up to order pℓ´2q exist at ℓ points x 1 , . . . , x ℓ P R. Then, the determinant of the matrix: is given by: Proof. We assume that the elements of the set tx 1 , x 2 , . . . , x ℓ u are distinct, as otherwise, the determinant is clearly zero. We also assume that ℓ ě 3 to exclude the trivial case. First, by the Vandermonde determinant formula, we have that: Our proof technique is to use elementary row operations to construct the determinant of Lpx 1 , x 2 , . . . , x ℓ q from (5.3). To illustrate the idea, let us use (5.3) to show that: For later use, we denote by V i px 1 , x 2 , . . . , x ℓ q the determinant of the matrix constructed by substituting rows 3 to i in V 0 px 1 , x 2 , . . . , x ℓ q by derivatives of order 1 to i´2, respectively. First, note that multiplying the third row of Lpx 1 , x 2 , . . . , x ℓ q by a 2 leads to: Moreover, by the fact that the determinant is unchanged by adding a constant multiple of a row to another row, using rows one and two for this purpose, we have that: . ξpx ℓ q a 0`a1 ξpx 1 q`a 2 ξ 2 px 1 q a 0`a1 ξpx 2 q`a 2 ξ 2 px 2 q . . . a 0`a1 ξpx ℓ q`a 2 ξ 2 px ℓ q ξ 3 px 1 q ξ 3 px 2 q . . .
which yields that: V 1 px 1 , x 2 , . . . , x ℓ q " a 2 V 0 px 1 , x 2 , . . . , x ℓ q, proving the claim. The idea of the proof is to use this same procedure, row by row, to construct D i ξpx j q in the entry pi`2qˆj of the matrix. In order to proceed, however, we need to find a formula for D i ξpxq, where x P R. Note that, for i ě 2, we have that: and D i ξpxq, as a polynomial in ξpxq, is of degree pi`1q. We now make an observation that finishes the proof. In particular, in the computation of V 1 px 1 , x 2 , . . . , x ℓ q and in order to construct Dξpxq in the third row, we only needed to know the coefficient of the highest degree monomial, in terms of ξpxq, that constitutes Dξpxq. In other words, the lower degree terms do not contribute to the determinant, as they can be constructed, without changing the determinant, from previous rows. Using this observation, the term a 1 D i´1 ξpxq in the expansion of D i ξpxq does not contributed to V i px 1 , x 2 , . . . , x ℓ q, as it can be added from the previously constructed rows. Using this reasoning for all i, we conclude that the determinant of Lpx 1 , . . . , x ℓ q is independent of a 1 , and a 0 . Substituting a 0 " 0 and a 1 " 0, since D i ξpxq " i!a i 2 ξ i`1 , we have that: as claimed.
Our second technical result is stated next.
Proposition 5.2. Let N Ă R nˆd be the set defined by: The set M " R nˆd zN is an open and dense sub-manifold of R nˆd which is connected when n ą 1.
Proof. Note that N is a finite union of vector subspaces of R nˆd , hence topologically closed. Therefore, R nˆd zN is an open and dense subset of R nˆd and thus a sub-manifold of dimension nd. It remains to show that M is connected.
Let A init , A fin P M , and assume that n ą 1. We prove that there exists a continuous curve γ : r0, ns Ñ M connecting A init to A fin , i.e., γp0q " A init and γpnq " A fin . Since A init P M there exists ℓ init P t1, . . . , nu so that ś 1ďiăjďd pA ℓ init i´Aℓ init j q ‰ 0. Similarly, since A fin P M there exists ℓ fin P t1, . . . , nu so that ś 1ďiăjďd pA ℓ fin i´Aℓ fin j q ‰ 0. We first consider the case where ℓ init ‰ ℓ fin (which is possible since n ą 1). Without loss of generality assume that ℓ init " n and ℓ fin " 1 and let γ k : R nˆdˆr k´1, ks Ñ R nˆd be defined as: . . . where A k‚ denotes the kth row of A. We now define the curve γ : r0, ns Ñ R nˆd by: γpλq " γ k λ˝γ k´1 k´1˝. . .˝γ 2 2˝γ 1 1 pA init q, λ P rk´1, ks, and note that γpλq P M for all λ P r0, ns. This is because, by definition, there exists at least one index ℓ P t1, . . . , nu such that ś 1ďiăjďd pγ ℓi pλq´γ ℓj pλqq ‰ 0. When λ ď n´1, we can choose ℓ to be ℓ init because γ ℓ init ‚ pλq " γ n‚ pλq " A init n‚ . When λ ě n´1, we can choose ℓ to be ℓ fin because γ ℓ fin ‚ pλq " γ 1‚ pλq " A fin 1‚ . Since γ is the composition of continuous functions, it is continuous. Moreover, by construction, γp0q " A init and γpnq " A fin .
We now consider the case where ℓ init " ℓ fin . Since n ą 1, we can choose A P M so that ś 1ďiăjďd pA ℓi´Aℓj q ‰ 0 with ℓ ‰ ℓ fin and ℓ ‰ ℓ init . By the previous argument, there is a continuous curve connecting A init to A without leaving M and there is also a continuous curve connecting A to A fin without leaving M . Therefore, their concatenation produces the desired continuous curve γ connecting A init to A fin and the proof is finished.
The proof of Theorem 4.2 uses several key ideas from geometric control that we now review. A collection of vector fields F " tZ 1 , . . . , Z k u on a manifold M is said to be controllable if given x init , x fin P M , there exists a finite sequence of times 0 ă t 1 ă t 1`t2 ă . . . ă t 1`. . .`t ℓ so that: i is the flow of Z i . When the vector fields Z i are smooth, M is smooth and connected, and the collection F satisfies: Z P F ùñ αZ P F for some α ă 0, then F is controllable provided the evaluation of the Lie algebra generated by F at every point x P M has the same dimension as M , see, e.g., [Jurdjevic, 1996] 4 . Recall that the Lie algebra generated by F , and denoted by LiepF q, is the smallest vector space of vector fields on M containing F and closed under the Lie bracket. By evaluation of LiepF q at x P M , we mean the finite-dimensional vector subspace of the tangent space of M at x that is obtained by evaluating every vector field in LiepF q at x. The proof consists in establishing controllability by determining the points at which LiepF q has the right dimension for a collection of vector fields F induced by the ensemble control system (2.3).
We are now in position to prove Theorem 4.2.
Proof of Theorem 4.2. Consider the control system given in (2.3). We prove that under the mentioned assumptions, there is a choice of the control inputs ps, W, bq that renders (2.3) controllable in M .
It will be sufficient to work with inputs that are piecewise constant, and we can further simplify the analysis by choosing the family of inputs ps, W, bq given by (5.4) and (5.5), where: ‚ the first class of inputs is given by: In this footnote we provide additional details relating controllability of a family of vector fields to the Lie algebra rank condition. Let us denote by A F pxq the reachable set of the family of smooth vector fields F from x P M , i.e., the set of all points x fin P R n of the form: t 1 1 pxq, for Z i P F and 0 ă t 1 ă t 1`t2 ă . . . ă t 1`. . .`t ℓ ,, and denote by LiexpF q the evaluation of the Lie algebra generated by F at x P M . By F 1 we denote the family of vector fields of the form ř i λ i X i with X i P F and λ i ě 0. Since F Ď F 1 we have A F pxq Ď A F 1 pxq. By Theorem 8 in Chapter 3 of [Jurdjevic, 1996] we have that: where cl denotes topological closure. Moreover, by Theorem 2 in Chapter 3 of [Jurdjevic, 1996], if LiexpF q " TxM for every x P M , then intpclpA F pxqqq " intpA F pxqq. We thus obtain: But if F 1 is controllable, intpA 1 F pxqq " M and thus F is also controllable. Therefore, we now focus on determining if F 1 is controllable. Provided that for each X P F there exists X 1 P F satisfying X " σX 1 with σ ă 0 (this is weaker than symmetry, symmetry is this property for σ "´1), F 1 is simply the vector space spanned by F . Moreover, since the control system 9 x " ř i X i u i with X i P F and u i P R generates the same family of vector fields as F 1 , we conclude that we can instead study the reachable set of 9 x " ř i X i u i with X i P F which is driftless. By Theorem 2 in Chapter 4, in [Jurdjevic, 1996] the control system 9 x " ř i X i u i is controllable provided that LiexpF 1 q " TxM for every x P M .
where j P t1, 2, . . . , nu and c P R is any value such that σpcq ‰ 0 and e j P R n has zeros in all its entries except for a 1 on its jth entry; ‚ the second class of inputs is given by: where j, k P t1, 2, . . . , nu and E ij is the nˆn matrix that has zeros in all its entries except for a 1 in its jth row and kth column.
Once we substitute these inputs into the right hand side of the ensemble control system (2.3), we obtain a family of vector fields on R nˆd . More specifically, the vector fields arising from the inputs (5.4), denoted by tXj u jPt1,...,nu , are given by: and Xj "´Xj .
This definition abuses notation, since defining a vector field on R nˆd requires one summation over i and one over j. However, summation over j, i.e., summation over rows, only produces non-zero terms for one row, that we decided to index by j.
We make the observation that, since σpcq ‰ 0, we can simplify the vector fields Xj to: and Xj "´Xj , without altering controllability. This follows from the observation that for any vector field X with flow X t we have X ατ " pαXq τ for any α P R.
By Proposition 5.2, M is a connected smooth sub-manifold of R nˆd . The remainder of the proof consists of showing that the family of vector fields F " tXj , Yj k u j,kPt1,...,nu , restricted to M , is controllable on M . As discussed prior to this proof, since these vector fields in F are smooth and satisfy Z P F ùñ´Z P F , it suffices to establish that dimpLie A pF qq " dimpM q " nd for every A P M and where Lie A pF q denotes the evaluation at A of the Lie algebra generated by F .
We generate LiepF q by iteratively computing Lie brackets. For two vector fields X and Y on R nˆd , we use the notation ad X Y " rX, Y s and ad ℓ`1 X Y " rX, ad ℓ X Y s where rX, Y s denotes the Lie bracket between X and Y . For our purpose, it is enough to compute ad ℓ Xk Yj k and, given the implication Z P F ùñ´Z P F , it suffices to compute: In order to show that dimpLie A pF qq " dimpM q at every A P M , we find it convenient to work with the vectorization of elements of R nˆd . In particular, we associate the vector vecpAq P R nd to each matrix A P R nˆd where the entry pi, jq of A is identified with the entry d i´1`j of vecpAq. For a collection of matrices tA 1 , . . . , A k u, we denote by vectA 1 , . . . , A k u the collection of vectors vectA 1 , . . . , A k u " tvecpA 1 q, . . . , vecpA k qu.
We note that every Z P S belongs to LiepF q since the vector fields in S either belong to F or are obtained by computing Lie brackets between elements of F and elements of S. Moreover, we claim the evaluation of the vector fields in S at every A P M results in nd linearly independent vectors. To establish this claim, we form the matrix: GpvecpAqq " " Z 1 pvecpAqq|Z 2 pvecpAqq| . . . |Z n 2 pd´1q pvecpAqq ‰ , and note that a simple but tedious computation, using (5.8), shows that G is a block diagonal matrix with d blocks, all of which being equal to: 1 σpA 11 q¨¨¨σpA 1n q DσpA 11 q¨¨¨DσpA 1n q D d´2 σpA 11 q¨¨¨D d´2 pA 1n q 1 σpA 21 q¨¨¨σpA 2n q DσpA 21 q¨¨¨DσpA 2n q D d´2 σpA 21 q¨¨¨D d´2 pA 2n q . . . To finish the proof, it suffices to show that G blk has rank n (since it has n rows) and this is accomplished by showing there is a choice of n columns that are linearly independent. Since A P M implies A R N , by definition, there exists ℓ P t1, . . . , nu such that: ź 1ďiăjďd pA ℓi´Aℓj q ‰ 0.
Moreover, by our assumption on injectivity of σ, we conclude that: ź 1ďiăjďd pσpA ℓi q´σpA ℓj qq ‰ 0, and it follows from Lemma 5.1 that the matrix: has rank n, i.e., for every A P M there exists n columns of G blk pvecpAqq that are linearly independent. The proof is then complete by noting that for n ą 1, M is connected, as asserted by Proposition 5.2.
The preceding proof used the controllability properties of the vector fields (5.6) and (5.7); upon a closer look, the reader can observe that it suffices for s to take values in the set t´1, 1u (or any set with two elements, one being positive and one being negative), for W to take values on t1, 0u (or any other set t0, cu with c ‰ 0) and for b to take values on t0, cu for some c P R such that σpcq ‰ 0. Taking this observation one step further, one can establish controllability of an alternative network architecture defined by: where the nˆn matrix S and the n vector b only need to assume values in a set of the form tc´, 0, c`u where c´P R´and c`P R`.
Proof of Corollary 4.3. The result follows from Theorem 4.2 once we establish the existence of a solution of (2.3) taking X init to some point X fin P M . This is because Theorem 4.2 states that any other point in M will then be reachable. We proceed by showing the existence of a solution taking X init to a point X fin satisfying X fin 1i ‰ X fin 1j for all i ‰ j, i, j P t1, . . . , du. Clearly, X fin P M . Assume, without loss of generality, that X init 11 " X init 12 . We will design an input of duration τ that will result in a solution Xptq with X 11 pτ q ‰ X 12 pτ q, while ensuring that if X init 1i is different from X init 1j we have that X 1i pτ q is different from X 1j pτ q.
By assumption, X init ‚1 ‰ X init ‚2 . Hence, there must exist k P t1, . . . , nu so that X init k1 ‰ X init k2 . We use k to define the input s " 1, b " 0, and the matrix W all of whose entries are zero except for W 1k that is equal to 1. This choice of input results in the solution: We note that d dtˇt"0 pX 11 ptq´X 12 ptqq " σpX init k1 q´σpX init k2 q ‰ 0 since σ is injective. Therefore, there exists τ 1 P R`such that X 11 ptq´X 12 ptq ‰ 0 for all t Ps0, τ 1 s, i.e., X 11 ptq ‰ X 12 ptq for all t Ps0, τ 1 s. Moreover, we now show existence of τ 2 so that for all t P r0, τ 2 s we have X 1i ptq ‰ X 2j ptq whenever X 1i p0q " X init 1i ‰ X init 2j " X 2j p0q. For a particular pair pX 1i , X 2j q for which X init 1i ‰ X init 2j , the equality X init 1i`t σpX init ki p0qq " X init 1j`t σpX init kj p0qq defines the intersection of two lines. If they intersect for positive t, say t 2 , it suffices to choose τ 2 smaller t 2 . Moreover, by choosing τ 2 to be smaller than the positive intersection points for all pairs of lines corresponding to all pairs pX 1i , X 2j q for which X init 1i ‰ X init 2j , we conclude that for all t P r0, τ 2 s, X 1i p0q " X init 1i ‰ X init 2j " X 2j p0q implies X 1i ptq ‰ X 2j ptq. Let now τ " mintτ 1 , τ 2 u. The point Xpτ q satisfies the two properties we set to achive: 1) X 11 pτ q ‰ X 12 pτ q; and 2) X 1i pτ q ‰ X 1j pτ q if X init 1i ‰ X init 1j . By noticing that X init ij " X ij pτ q for i ą 1 and any j P t1, . . . , du, we can repeat this process iteratively to force all the entires of the first row of X to become different, the same way we forced the first two.
The core ideas in the following two proofs come from [Li et al., 2019] although the proofs have been suitably modified to rely on Theorem 4.2.
Proof of Proposition 4.4. Let E be a compact set in R n and E samples Ă R n be a finite set with d elements satisfying: i) For all ℓ P t1, . . . , nu: where A is the matrix whose columns are the d elements of E samples . ii) For every x P E, there exist x, x P E samples satisfying x i ď x i ď x i for i P t1, . . . , nu and: where δ P R`is a constant to be chosen later.
We claim that f pA ‚i q and f pA ‚j q satisfy: ź 1ďiăjďd f ℓ pA ‚i q´f ℓ pA ‚j qq ‰ 0, for all ℓ P t1, . . . , nu. Since A ℓi´Aℓj ‰ 0, assume without loss of generality that A ℓi ą A ℓj . Since f is a Cartesian product of strictly monotone functions and, in particular, f ℓ is strictly monotone, we have f ℓ pA ‚i q " f ℓ pA ℓi q ą f ℓ pA ℓj q " f ℓ pA ‚j q thus showing that f ℓ pA ‚i q´f ℓ pA ‚j q ‰ 0 as desired.
We now claim the ensemble control system (2.3) with d copies of (3.1) restricted to the set of matrices A P R nˆd satisfying (5.10) is controllable. Since the proof of this claim is analogous to the proof of Theorem 4.2 we discuss only where it differs. We choose a subset of the inputs resulting in the vector fields Xj and Yj j . Computing the matrix GpvecpAqq, we still obtain a block diagonal matrix but its blocks are now distinct and given by: 1 σpA nℓ q DσpA nℓ q . . . D d´2 σpA nℓ q fi ffi ffi ffi fl , ℓ P t1, . . . , nu.
It now follows from injectivity of σ, Lemma 5.1, and the fact that (5.10) holds that all these matrices are of full rank and we conclude controllability. The set of matrices satisfying (5.10) is a disjoint union of connected components and we now show that A and f pAq " rf pA ‚i q|f pA ‚2 q| . . . |f pA ‚n qs belong to the same connected component. Given A, consider the continuous curve: γpλq " p1´λqA`λf pAq, for λ P r0, 1s. Since A ℓi´Aℓj ‰ 0, assume without loss of generality that A ℓi ą A ℓj and note that it follows from the strict monotonicity and the Cartesian product assumption on f , as we previously argued, that f ℓ pA ‚i q " f ℓ pA ℓi q ą f ℓ pA ℓj q " f ℓ pA ‚j q. Hence, we have: γ ℓi pλq " p1´λqA ℓi`λ f ℓi pAq " p1´λqA ℓi`λ f ℓ pA ‚i q ą p1´λqA ℓj`λ f ℓ pA ‚j q " p1´λqA ℓj`λ f ℓj pAq " γ ℓj pλq, thereby showing that γ ℓi pλq´γ ℓj pλq ‰ 0 for all λ P r0, 1s. Since A and f pAq belong to the same connected component and the ensemble control system is controllable, there exists a time τ P R`and an input ps, W, bq : r0, τ s Ñ RˆR nˆnˆRn so that the resulting flow φ τ takes A to f pAq. The flow φ τ is of the form Z t k k˝. . .˝Z t2 2˝Z t1 1 where t k`. . .`t 1 " τ and each Z i is of the form Xj or Yj j . All the vector fields Xj and Yj j are monotone since the off diagonal terms of the corresponding Jacobians are zero [Smith, 2008]. Since the composition of monotone maps is a monotone map, we conclude that φ τ is a monotone flow. Denoting by ω f the modulus of continuity 5 of f on a compact set containing E samples , we now compute: |f pxq´φ τ pxq| 8 ď |f pxq´φ τ pxq| 8`| φ τ pxq´φ τ pxq| 8 ď |f pxq´f pxq| 8`| φ τ pxq´φ τ pxq| 8 ď ω f p|x´x| 8 q`|f pxq´f pxq| 8 ď ω f p|x´x| 8 q`ω f p|x´x| 8 q ď 2ω f pδq, where we have used φ τ pxq " f pxq as well as the monotonicity property of φ τ in the second inequality, in particular, the fact that φ τ i pxq ď φ τ i pxq ď φ τ i pxq. The result now follows by making δ sufficiently small. 6 Proof of Theorem 4.5. Since E is compact, without loss of generality, we assume E " r0, Ls n , where L P R`. We let L " qδ for some q P N and a δ P R`to be specified later and cover E by a collection of hyper-cubes whose vertices are given by: V " tpr 1 δ, r 2 δ, . . . , r n δq P R n | r i P t0, 1, . . . , qu, i P t1, . . . , nuu.
Any x P E belongs to the hypercube: where x P V is given by the vector with components x i " r i δ with r i " maxtr i P t0, . . . , q´1u | r i δ ď x i u and x P V is given by the vector with components x i " r i δ with r i " r i`1 . We note that for any x P E: (5.11) |x´x| 8 ď |x´x| 8 ď δ.