Abide by the Law and Follow the Flow:
Conservation Laws for Gradient Flows
January 01, 1970
Understanding the geometric properties of gradient descent dynamics is a key ingredient in deciphering the recent success of very large machine learning models. A striking observation is that trained over-parameterized models retain some properties of the optimization initialization. This “implicit bias” is believed to be responsible for some favorable properties of the trained models and could explain their good generalization properties. The purpose of this article is threefold. First, we rigorously expose the definition and basic properties of “conservation laws”, that define quantities conserved during gradient flows of a given model (e.g. of a ReLU network with a given architecture) with any training data and any loss. Then we explain how to find the maximal number of independent conservation laws by performing finite-dimensional algebraic manipulations on the Lie algebra generated by the Jacobian of the model. Finally, we provide algorithms to: a) compute a family of polynomial laws; b) compute the maximal number of (not necessarily polynomial) independent conservation laws. We provide showcase examples that we fully work out theoretically. Besides, applying the two algorithms confirms for a number of ReLU network architectures that all known laws are recovered by the algorithm, and that there are no other independent laws. Such computational tools pave the way to understanding desirable properties of optimization initialization in large machine learning models.
State-of-the-art approaches in machine learning rely on the conjunction of gradient-based optimization with vastly “over-parameterized” architectures. A large body of empirical [1] and theoretical [2] works suggest that, despite the ability of these models to almost interpolate the input data, they are still able to generalize well. Analyzing the training dynamics of these models is thus crucial to gain a better understanding of this phenomenon. Of particular interest is to understand what properties of the initialization are preserved during the dynamics, which is often loosely referred to as being an “implicit bias” of the training algorithm. The goal of this article is to make this statement precise, by properly defining maximal sets of such “conservation laws”, by linking these quantities to algebraic computations (namely a Lie algebra) associated with the model parameterization (in our framework, this parameterization is embodied by a re-parameterization mapping \(\phi\)), and finally by exhibiting algorithms to implement these computations in SageMath [3].
Modern machine learning practitioners and researchers have found that over-parameterized neural networks (with more parameters than training data points), which are often trained until perfect interpolation, have impressive generalization properties [1], [2]. This performance seemingly contradicts classical learning theory [4], and a large part of the theoretical deep learning literature aims at explaining this puzzle. The choice of the optimization algorithm is crucial to the model generalization performance [5]–[7], thus inducing an implicit bias.
The terminology “implicit bias” informally refers to properties of trained models which are induced by the optimization procedure, typically some form of regularization [8]. For gradient descent, in simple cases such as scalar linear neural networks or two-layer networks with a single neuron, it is actually possible to compute in closed form the implicit bias, which induces some approximate or exact sparsity regularization [5]. Another interesting case is logistic classification on separable data, where the implicit bias selects the max-margin classifier both for linear models [9] and for two-layer neural networks in the mean-field limit [10]. A key hypothesis to explicit the implicit bias is often that the Riemannian metric associated to the over-parameterization is either of Hessian type [5], [11], or can be somehow converted to be of Hessian type [11], which is seemingly always a strong constraint. For example, even for simple two-layer linear models (i.e., matrix factorization) with more than a single hidden neuron, the Hessian type assumption does not hold, and no closed form is known for the implicit bias [12]. The work of [13] gives conditions on the over-parameterization for this to be possible (for instance certain Lie brackets should vanish). These conditions are (as could be expected) stronger than those required to apply Frobenius theory, as we do in the present work to retrieve conservation laws.
Finding functions conserved during gradient flow optimization of neural networks (a continuous limit of gradient descent often used to model the optimization dynamics) is particularly useful to better understand the flow behavior. One can see conservation laws as a “weak” form of implicit bias: to explain, among a possibly infinite set of minimizers, which properties (e.g. in terms of sparsity, low-rank, etc.) are being favored by the dynamic. If there are enough conservation laws, one has an exact description of the dynamic (see 3.4), and in some cases, one can even determine explicitly the implicit bias. Otherwise, one can still predict what properties of the initialization are retained at convergence, and possibly leverage this knowledge. For example, in the case of linear neural networks, certain balancedness properties are satisfied and provide a class of conserved functions [14]–[20]. These conservation laws enable for instance to prove the global convergence of the gradient flow [21] under some assumptions. We detail these laws in Proposition 10. A subset of these “balancedness” laws still holds in the case of a ReLU activation [15], which reflects the rescaling invariance of these networks (see 4 for more details). More generally such conservation laws bear connections with the invariances of the model [22]: to each 1-parameter group of transformation preserving the loss, one can associate a conserved quantity, which is in some sense analogous to Noether’s theorem [23]–[25]. Similar reasoning is used by [26] to show the influence of initialization on convergence and generalization performance of the neural network. Our work is somehow complementary to this line of research: instead of assuming a priori known symmetries, we directly analyze the model and give access to conservation laws using algebraic computations. For matrix factorization as well as for certain ReLU network architectures, this allows us to show that the conservation laws reported in the literature are complete (there are no other independent quantities that would be preserved by all gradient flows).
We formalize the notion of a conservation law, a quantity preserved through all gradient flows given a model architecture (e.g. a ReLU neural network with prescribed layers). Our main contributions are:
to show that for several classical losses, characterizing conservation laws for deep linear (resp. shallow ReLU) networks boils down to analyzing a finite dimensional space of vector fields;
to propose an algorithm (coded in SageMath) identifying polynomial conservation laws on linear / ReLU network architectures; it identifies all known laws on selected examples;
to formally define the maximum number of (not necessarily polynomial) independent conservation laws and characterize it a) theoretically via Lie algebra computations; and b) practically via an algorithm (coded in SageMath) computing this number on worked examples;
to illustrate that in certain settings these findings allow to rewrite an over-parameterized flow as an “intrinsic” low-dimensional flow;
to highlight that the cost function associated to the training of linear and ReLU networks, shallow or deep, with various losses (quadratic and more) fully fits the proposed framework.
A consequence of our results is to show for the first time that conservation laws commonly reported in the literature are maximal: there is no other independent preserved quantity (see Propositions 12, 11, 2) and 4.2).
After some reminders on gradient flows, we formalize the notion of conservation laws.
We consider learning problems, where we denote \(x_i \in \mathbb{R}^m\) the features and \(y_i \in \mathcal{Y}\) the targets (for regression, typically with \(\mathcal{Y} = \mathbb{R}^n\)) or labels (for classification) in the case of supervised learning, while \(y_i\) can be considered constant for unsupervised/self-supervised learning. We denote \(X \mathrel{\vcenter{:}}= (x_i)_i\) and \(Y \mathrel{\vcenter{:}}= (y_i)_i\). Prediction is performed by a parametric mapping \(g(\theta, \cdot): \mathbb{R}^m \to \mathbb{R}^n\) (for instance a neural network) which is trained by empirically minimizing over parameters \(\theta\in \Theta \subseteq \mathbb{R}^D\) a cost \[\label{eq:erm} \mathcal{E}_{X,Y}(\theta) \mathrel{\vcenter{:}}= \sum_i \ell(g({\theta},x_i),y_i),\tag{1}\] where \(\ell\) is the loss function. In practical examples with linear or ReLU networks, \(\Theta\) is either \(\mathbb{R}^D\) or an open set of “non-degenerate” parameters. The goal of this paper is to analyze what functions \(h(\theta)\) are preserved during the gradient flow (the continuous time limit of gradient descent) of \(\mathcal{E}_{X,Y}\): \[\label{gradientflow} \overset{.}{\theta}(t) = -\nabla \mathcal{E}_{X,Y} (\theta(t)), \text{ with } \theta(0) = \theta_{\text{init}}.\tag{2}\] A priori, one can consider different “levels” of conservation, depending whether \(h\) is conserved: during the optimization of \(\mathcal{E}_{X,Y}\) for a given loss \(\ell\) and a given data set \((x_i,y_i)_i\); or given a loss \(\ell\), during the optimization of \(\mathcal{E}_{X,Y}\) for any data set \((x_i,y_i)_i\). Note that using stochastic optimization methods and discrete gradients would break the exact preservation of the conservation laws, and only approximate conservation would hold, as remarked in [22].
As they are based on gradient flows, conserved functions are first defined locally.
Definition 1 (Conservation through a flow). Consider an open subset \(\Omega\subseteq \Theta\) and a vector field \(\chi \in \mathcal{C}^1(\Omega, \mathbb{R}^D)\). By the Cauchy-Lipschitz theorem, for each initial condition \(\theta_{\text{init}}\), there exists a unique maximal solution \(t \in [0, T_{\theta_{\text{init}}}) \mapsto \theta(t,\theta_{\text{init}})\) of the ODE \(\dot{\theta}(t) = \chi(\theta(t))\) with \(\theta(0) = \theta_{\text{init}}\). A function \(h: \Omega\subseteq \mathbb{R}^D \to \mathbb{R}\) is conserved on \(\Omega\) through the vector field \(\chi\) if \(h(\theta(t,\theta_{\text{init}}))=h(\theta_{\text{init}})\) for each choice of \(\theta_{\text{init}} \in \Omega\) and every \(t \in [0, T_{\theta_{\text{init}}})\). It is conserved on \(\Omega\) through a subset \(W \subset \mathcal{C}^1(\Omega, \mathbb{R}^D)\) if \(h\) is conserved on \(\Omega\) during all flows induced by all \(\chi \in W\).
In particular, one can adapt this definition for the flow induced by the cost 1 .
Definition 2 (Conservation during the flow 2 with a given dataset). Consider an open subset \(\Omega\subseteq \Theta\) and a dataset \((X, Y)\) such that \(\mathcal{E}_{X, Y} \in \mathcal{C}^{2}(\Omega, \mathbb{R})\). A function \(h: \Omega\subseteq \mathbb{R}^D \to \mathbb{R}\) is conserved on \(\Omega\) during the flow 2 if it is conserved through the vector field \(\chi(\cdot) \mathrel{\vcenter{:}}= \nabla \mathcal{E}_{X, Y} (\cdot)\).
Our goal is to study which functions are conserved during “all” flows defined by the ODE 2 . This in turn leads to the following definition.
Definition 3 (Conservation during the flow 2 with “any” dataset). Consider an open subset \(\Omega \subset \Theta\) and a loss \(\ell(z, y)\) such that \(\ell(\cdot, y)\) is \(\mathcal{C}^2\)-differentiable for all \(y \in \mathcal{Y}\). A function \(h: \Omega\subseteq \mathbb{R}^D \to \mathbb{R}\) is conserved on \(\Omega\) for any data set if, for each data set \((X, Y)\) such that \(g(\cdot, x_i) \in \mathcal{C}^{2}(\Omega, \mathbb{R}^n)\) for each \(i\), the function \(h\) is conserved on \(\Omega\) during the flow 2 . This leads us to introduce the family of vector fields: \[\label{eq:W95ell} W_\Omega^{g} := \left\{ \chi(\cdot): \exists X,Y, \forall i\;g(\cdot, x_i) \in \mathcal{C}^{2}(\Omega,\mathbb{R}^n) ,\;\chi = \nabla \mathcal{E}_{X,Y} \right\} \subseteq \mathcal{C}^{1}(\Omega, \mathbb{R}^D)\tag{3}\] so that being conserved on \(\Omega\) for any dataset is the same as being conserved on \(\Omega\) through \(W_\Omega^{g}\).
The above definitions are local and conditioned on a choice of open set of parameters \(\Omega\subset \Theta\). We are rather interested in functions defined on the whole parameter space \(\Theta\), hence the following definition.
Definition 4. A function \(h: \Theta \mapsto \mathbb{R}\) is locally conserved on \(\Theta\) for any data set if for each open subset \(\Omega\subseteq \Theta\), \(h\) is conserved on \(\Omega\) for any data set.
A basic property of \(\mathcal{C}^1\) conserved functions (which proof can be found in 5) corresponds to an “orthogonality” between their gradient and the considered vector fields.
Proposition 1. Given a subset \(W \subset \mathcal{C}^{1}(\Omega, \mathbb{R}^D)\), its trace* at \(\theta\in \Omega\) is defined as the linear space \[\label{eq:DefTrace} W(\theta) \mathrel{\vcenter{:}}= \mathrm{span}{\{\chi(\theta): \chi \in W\}} \subseteq \mathbb{R}^D.\tag{4}\] A function \(h \in \mathcal{C}^1(\Omega, \mathbb{R})\) is conserved on \(\Omega\) through \(W\) if, and only if \(\nabla h(\theta) \perp W(\theta),\forall \theta\in \Omega\).*
Therefore, combining 1 and 4, the object of interest to study locally conserved functions is the union of the traces \[\label{eq:def95W95ell} W^{g}_\theta\mathrel{\vcenter{:}}= \bigcup \Big\{ W_{\Omega}^{g}(\theta) \;:\; \Omega\subseteq \Theta \text{ with } \Omega \text{ a neighborhood of } \theta\Big\}.\tag{5}\]
Corollary 1. A function \(h: \Theta \mapsto \mathbb{R}\) is locally conserved on \(\Theta\) for any data set if and only if \(\nabla h(\theta) \perp W^{g}_\theta\) for all \(\theta\in \Theta\).
It will soon be shown (cf 4) that \(W^g_\theta\) can be rewritten as the trace \(W(\theta)\) of a simple finite-dimensional functional space \(W\). Meanwhile, we keep the specific notation. For the moment, this set is explicitly characterized via the following proposition (which proof can be found in 6).
Proposition 2. Assume that for each \(y \in \mathcal{Y}\) the loss \(\ell(z, y)\) is \(\mathcal{C}^2\)-differentiable with respect to \(z \in \mathbb{R}^n\). For each \(\theta\in \Theta\) we have: \[ W_\theta^g = \underset{(x, y) \in {\mathcal{X}}_\theta\times \mathcal{Y}}{\mathrm{span}} \{ [\partial_\theta g(\theta,x)]^\top \nabla_z \ell (g(\theta,x), y) \}\] where \(\mathcal{X}_\theta\) is the set of data points \(x\) such that \(g(\cdot,x)\) is \(\mathcal{C}^2\)-differentiable in the neighborhood of \(\theta\).
Example 1. As a first simple example, consider a two-layer linear neural network in dimension 1 (both for the input and output), with a single neuron. For such – admittedly trivial – architecture, the parameter is \(\theta= (u,v) \subseteq \mathbb{R}^2\) and the model writes \(g(\theta,x) = uvx\). One can directly check that the function: \(h(u, v) = u^2-v^2\) is locally conserved on \(\mathbb{R}^2\) for any data set. Indeed in that case \(\nabla h(u, v) = (2u, -2v)^\top \perp W_\theta^g = \underset{(x, y) \in {\mathbb{R}\times \mathcal{Y}}}{\mathrm{span}} \{ (vx, ux)^\top \nabla_z \ell (g(\theta, x), y) \} = \mathbb{R}\times (v, u)^\top\) given that the gradient \(\nabla_z \ell (g(\theta, x), y)\) is an arbitrary scalar.
In this example we obtain a simple expression of \(W_\theta^g\), however in general cases it is not possible to obtain such a simple expression from 2. We will show that in some cases, it is possible to express \(W_\theta^g\) as the trace \(W(\theta)\) of a simple finite-dimensional space \(W\) (cf. 4).
To make the mathematical analysis tractable and provide an algorithmic procedure to determine these functions, our fundamental hypothesis is that the model \(g(\theta, x)\) can be (locally) factored via a reparametrization \(\phi\) as \(f(\phi(\theta),x)\). We require that the model \(g(\theta, x)\) satisfies the following central assumption.
Assumption 1 (Local reparameterization). There exists \(d\) and \(\phi \in \mathcal{C}^2(\Theta,\mathbb{R}^d)\) such that: for each parameter \(\theta_0\) in the open set \(\Theta \subseteq \mathbb{R}^D\), for each \(x \in \mathcal{X}\) such that \(\theta\mapsto g(\theta,x)\) is \(\mathcal{C}^{2}\) in a neighborhood of \(\theta_0\)1, there is a neighborhood \(\Omega\) of \(\theta_0\) and \(f(\cdot, x) \in \mathcal{C}^2(\phi(\Omega), \mathbb{R}^n)\) such that \[\label{eq:elr-general}\forall \theta\in \Omega, \quad g(\theta,x) = f(\phi(\theta), x).\tag{6}\]
Note that if the model \(g(\cdot, x)\) is smooth on \(\Omega\) then 6 is always satisfied with \(\phi \mathrel{\vcenter{:}}= \texttt{id}\) and \(f(\cdot, x) \mathrel{\vcenter{:}}= g(\cdot,x)\), yet this trivial factorization fails to capture the existence and number of conservation laws as studied in this paper. This suggests that, among all factorizations shaped as 6 , there may be a notion of an optimal one.
Example 2. (Factorization for linear neural networks) In the two-layer case, with \(r\) neurons, denoting \(\theta=(U,V) \in \mathbb{R}^{n \times r} \times \mathbb{R}^{m \times r}\) (so that \(D=(n+m)r\)), we can factorize \(g(\theta,x) \mathrel{\vcenter{:}}= U V^\top x\) by the reparametrization \(\phi(\theta) \mathrel{\vcenter{:}}= U V^\top \in \mathbb{R}^{n \times m}\) using \(f(\phi, x) = \phi \cdot x\). More generally for \(q\) layers, with \(\theta= (U_1, \cdots, U_q)\), we can still factorize \(g(\theta,x) \mathrel{\vcenter{:}}= U_1 \cdots U_q x\) using \(\phi(\theta) \mathrel{\vcenter{:}}= U_1 \cdots U_q\) and the same \(f\). This factorization is globally valid on \(\Omega = \Theta = \mathbb{R}^D\) since \(f(\cdot, x)\) does not depend on \(\theta_0\).
The notion of locality of the factorization 6 is illustrated by the next example.
Example 3 (Factorization for two-layer ReLU networks). Consider \(g(\theta,x) = \big( \sum_{j=1}^{r} u_{k, j} \sigma(\langle v_j, x \rangle + b_j)+ c_k\big)_{k = 1}^{n}\), with \(\sigma(t) \mathrel{\vcenter{:}}= \max(t,0)\) the ReLU activation function and \(v_j \in \mathbb{R}^m\), \(u_{k,j} \in \mathbb{R}\), \(b_j, c_k \in \mathbb{R}\). Then, denoting \(\theta= (U,V, b, c)\) with \(U = (u_{k,j})_{k, j} =: (u_1, \cdots, u_r) \in \mathbb{R}^{n \times r}\), \(V = (v_1, \cdots, v_r) \in \mathbb{R}^{m \times r}\), \(b = (b_1, \cdots, b_r)^\top \in \mathbb{R}^r\) and \(c = (c_1, \cdots, c_n) \in \mathbb{R}^n\) (so that \(D = (n+m+1)r + n\)), we rewrite \(g(\theta,x) = \sum_{j=1}^r u_j \varepsilon_{j, x} \left(v_j^\top x + b_j\right) + c\) where, given \(x\), \(\varepsilon_{j, x} = \mathbb{1} ( v_j^\top x + b_j > 0 )\) is piecewise constant with respect to \(\theta\). Consider \(\theta^0 = (U^0, V^0, b^0, c^0) \in \mathbb{R}^D\) where \(V^0 = (v_1^0, \cdots, v_r^0)\) and \(b^0 = (b_1^0, \cdots, b_r^0)^\top\). Then the set \(\mathcal{X}_{\theta^0}\) introduced in 2 is \(\mathcal{X}_{\theta^0} = \mathbb{R}^m - \cup_j \{ {v_j^0}^\top x + b_j^0= 0 \}\). Let \(x \in \mathcal{X}_{\theta^0}\). Then on any domain \(\Omega\subset \mathbb{R}^D\) such that \(\theta^0 \in \Omega\) and \(\varepsilon_{j,x}(\theta) \mathrel{\vcenter{:}}= \mathbb{1}(v_j^\top x + b_j> 0)\) is constant over \(\theta\in \Omega\), the model \(g_{\theta}(x)\) can be factorized by the reparametrization \(\phi(\theta) = ((u_j v_j^\top, u_j b_j )_{j=1}^r, c)\). In particular, in the case without bias (\((b, c) = (0, 0)\)), the reparametrization is defined by \(\phi(\theta) = (\phi_j)_{j=1}^r\) where \(\phi_j = \phi_j(\theta) \mathrel{\vcenter{:}}= u_j v_j^\top \in \mathbb{R}^{n \times m}\) (here \(d =rmn\)) using \(f(\phi,x) = \sum_{j} \varepsilon_{j,x} \phi_{j}x\): the reparametrization \(\phi(\theta)\) contains \(r\) matrices of size \(m \times n\) (each of rank at most one) associated to a “local” \(f(\cdot, x)\) valid in a neighborhood of \(\theta\). A similar factorization is possible for deeper ReLU networks [27], as further discussed in the proof of 4 in 7.
Combining 2 and using chain rules, we get a new characterization of \(W^g_\theta\):
Proposition 3. Assume that the loss \(\ell(z, y)\) is \(\mathcal{C}^2\)-differentiable with respect to \(z\). We recall (cf 5 ) that \(W^g_\theta\mathrel{\vcenter{:}}= \cup_{\Omega\subseteq \Theta: \Omega\;\text{is open and}\;\Omega\ni \theta} W_{\Omega}^g(\theta).\) Under 1, for all \(\theta\in \Theta\): \[\label{eq:chain95rules} W^g_\theta= \partial \phi(\theta)^\top W^{f}_{\phi(\theta)}\qquad{(1)}\] with \(\partial \phi(\theta) \in \mathbb{R}^{d \times D}\) the Jacobian of \(\phi\) and \(W^{f}_{\phi(\theta)} \mathrel{\vcenter{:}}= \underset{(x, y) \in {\mathcal{X}}_\theta\times \mathcal{Y}}{\mathrm{span}} \{ \partial f^x(\phi(\theta))^\top \nabla_z \ell (g(\theta, x), y) \}\), where \(f^x(\cdot)\mathrel{\vcenter{:}}= f(\cdot, x)\).
We show in 2.4 that, under mild assumptions on the loss \(\ell\), \(W^{f}_{\phi(\theta)} = \mathbb{R}^d\), so that 3 yields \(W^g_\theta= \mathrm{range}(\partial \phi (\theta)^\top)\). Then by 1, a function \(h\) that is locally conserved on \(\Theta\) for any data set is entirely characterized via the kernel of \(\partial \phi(\theta)^\top\): \(\partial \phi(\theta)^\top \nabla h(\theta) = 0\) for all \(\theta\in \Theta\). The core of our analysis is then to analyze the (Lie algebraic) structure of \(\mathrm{range}(\partial \phi(\cdot)^\top)\).
For linear and ReLU networks we show in 4 and 5 that under (mild) assumptions on the loss \(\ell(\cdot,\cdot)\), being locally conserved on \(\Theta\) for any data set (according to 4) is the same as being conserved (according to 1) on \(\Theta\) through the finite-dimensional subspace \[\label{eq:v-phi}W_\phi \mathrel{\vcenter{:}}= \mathrm{span}\{\nabla \phi_1(\cdot), \cdots, \nabla \phi_{d}(\cdot) \} = \Big\{\theta\mapsto \sum_i a_i \nabla \phi_i(\theta): (a_1,\ldots,a_{d}) \in \mathbb{R}^{d}\Big\}\tag{7}\] where we write \(\partial \phi(\theta)^\top = (\nabla \phi_1(\theta), \cdots, \nabla \phi_{d}(\theta)) \in \mathbb{R}^{D \times d}\), with \(\nabla \phi_i \in \mathcal{C}^1(\Theta, \mathbb{R}^D)\).
The following results (which proofs can be found in 7) establish that in some cases, the functions locally conserved for any data set are exactly the functions conserved through \(W_\phi\).
Lemma 1. Assume that the loss \((z,y) \mapsto\ell(z,y)\) is \(\mathcal{C}^2\)-differentiable with respect to \(z \in \mathbb{R}^n\) and satisfies the condition: \[\label{eq:condition95loss} \underset{y \in \mathcal{Y}}{\mathrm{span}}\{\nabla_z \ell (z, y) \}= \mathbb{R}^n, \forall z \in \mathbb{R}^n.\tag{8}\] Then for linear neural networks (resp. for two-layer ReLU networks) and all \(\theta\in \Theta\) we have \(W^{f}_{\phi(\theta)} = \mathbb{R}^d\), with the reparametrization \(\phi\) from 2 and \(\Theta \mathrel{\vcenter{:}}=\mathbb{R}^D\) (resp. with \(\phi\) from 3 and \(\Theta\) consisting of all parameter \(\theta\) of the network such that hidden neurons are associated to pairwise distinct “hyperplanes”, cf 7 for details).
Condition 8 holds for classical losses \(\ell\) (e.g. quadratic/logistic losses), as shown in 5 in 7. Note that the additional hypothesis of pairwise distinct hyperplanes for the two-layer ReLU case is a generic hypothesis and is usual (see e.g. the notion of twin neurons in [27]). The tools from 7 extend 4 beyond (deep) linear and shallow ReLU networks. An open problem is whether the conclusions of 1 still hold for deep ReLU networks.
Theorem 4. Under the same assumptions as in 1, we have that for linear neural networks, for all \(\theta\in \Theta \mathrel{\vcenter{:}}= \mathbb{R}^D\): \[W_\theta^{g} = W_\phi(\theta).\] The same result holds for two-layer ReLU networks with \(\phi\) from 3 and \(\Theta\) the (open) set of all parameters \(\theta\) such that hidden neurons are associated to pairwise distinct “hyperplanes”.
This means as claimed that for linear and two-layer ReLU networks, being locally conserved on \(\Theta\) for any data set exactly means being conserved on \(\Theta\) through the finite-dimensional functional space \(W_\phi \subseteq \mathcal{C}^1(\Theta, \mathbb{R}^D)\). This motivates the following definition
Definition 5. A real-valued function \(h\) is a conservation law of \(\phi\) if it is conserved through \(W_\phi\).
1 yields the following intermediate result.
Proposition 5. \(h \in \mathcal{C}^1(\Omega, \mathbb{R})\) is a conservation law for \(\phi\) if and only if \[\nabla h(\theta) \perp \nabla \phi_j(\theta),\;\forall\;\theta\in \Omega,\;\forall j \in \{1,\ldots,d\}.\]
Thanks to 4, the space \(W_\phi\) defined in 7 introduces a much simpler proxy to express \(W_\theta^g\) as a trace of a subset of \(\mathcal{C}^1(\Theta, \mathbb{R}^D)\). Moreover, when \(\phi\) is \(\mathcal{C}^\infty\), \(W_\phi\) is a finite-dimensional space of infinitely smooth functions on \(\Theta\), and this will be crucial in 4.1 to provide a tractable scheme (i.e. operating in finite dimension) to compute the maximum number of independent conservation laws, using the Lie algebra computations that will be described in 3.
Example 4. Revisiting 1, the function to minimize is factorized by the reparametrization \(\phi: (u \in \mathbb{R}, v\in \mathbb{R}) \mapsto u v \in \mathbb{R}\) with \(\theta\mathrel{\vcenter{:}}= (u, v)\). We saw that \(h((u, v)) \mathrel{\vcenter{:}}= u^2-v^2\) is conserved: and indeed \(\langle \nabla h(u, v), \nabla \phi(u, v) \rangle = 2u v - 2v u = 0\), \(\forall (u, v)\).
In this simple example, the characterization of 5 gives a constructive way to find such a conserved function: we only need to find a function \(h\) such that \(\langle \nabla h(u, v), \nabla \phi(u, v) \rangle = \langle \nabla h(u, v), (v,u)^\top \rangle = 0\). The situation becomes more complex in higher dimensions, since one needs to understand the interplay between the different vector fields in \(W_\phi\).
Observe that in 4 both the reparametrization \(\phi\) and the conservation law \(h\) are polynomials, a property that surprisingly systematically holds in all examples of interest in the paper, making it possible to algorithmically construct some conservation laws as detailed now.
By 5, a function \(h\) is a conservation law if it is in the kernel of the linear operator \(h \in \mathcal{C}^{1}(\Omega, \mathbb{R}) \mapsto \left(\theta\in \Omega\mapsto (\langle \nabla h (\theta), \nabla \phi_i (\theta) \rangle)_{i =1, \cdots, d}\right)\). Thus, one could look for conservation laws in a prescribed finite-dimensional space by projecting these equations in a basis (as in finite-element methods for PDEs). Choosing the finite-dimensional subspace could be generally tricky, but for the linear and ReLU cases all known conservation laws are actually polynomial “balancedness-type conditions” [15]–[17], see 4. In these cases, the vector fields in \(W_\phi\) are also polynomials (because \(\phi\) is polynomial, see 15 and 16 in 7), hence \(\theta\mapsto \langle \nabla h (\theta), \nabla \phi_i (\theta) \rangle\) is a polynomial too. This allows us to compute a basis of independent polynomial conservation laws of a given degree (to be freely chosen) for these cases, by simply focusing on the corresponding subspace of polynomials. We coded the resulting equations in SageMath, and we found back on selected examples (see 14) all existing known conservation laws both for ReLU and linear networks. Open-source code is available at [28].
Having an algorithm to build conservation laws is nice, yet how can we know if we have built “all” laws? This requires first defining a notion of a “maximal” set of functions, which would in some sense be independent. This does not correspond to linear independence of the functions themselves (for instance, if \(h\) is a conservation law, then so is \(h^k\) for each \(k \in \mathbb{N}\) but this does not add any other constraint), but rather to pointwise linear independence of their gradients. This notion of independence is closely related to the notion of “functional independence” studied in [29], [30]. For instance, it is shown in [30] that smooth functionally dependent functions are characterized by having dependent gradients everywhere. This motivates the following definition.
Definition 6. A family of \(N\) functions \((h_1, \cdots, h_N)\) conserved through \(W \subset \mathcal{C}^1(\Omega, \mathbb{R}^D)\) is said to be independent if the vectors \((\nabla h_1(\theta), \cdots, \nabla h_N(\theta))\) are linearly independent for all \(\theta\in \Omega\).
An immediate upper bound holds on the largest possible number \(N\) of functionally independent functions \(h_1,\ldots,h_N\) conserved through \(W\): for \(\theta\in \Omega \subseteq \mathbb{R}^D\), the space \(\mathrm{span}\{\nabla h_1(\theta),\ldots, \nabla h_N(\theta)\} \subseteq \mathbb{R}^D\) is of dimension \(N\) (by independence) and (by 1) orthogonal to \(W(\theta)\). Thus, it is necessary to have \(N \leq D-\dim W(\theta)\). As we will now see, this bound can be tight under additional assumptions on \(W\) related to Lie brackets (corresponding to the so-called Frobenius theorem). This will in turn lead to a characterization of the maximum possible \(N\).
The study of hyper-surfaces trapping the solution of ODEs is a recurring theme in control theory, since the existence of such surfaces is the basic obstruction of controllability of such systems [31]. The basic result to study these surfaces is the so-called Frobenius theorem from differential calculus (See Section 1.4 of [32] for a good reference for this theorem). It relates the existence of such surfaces, and their dimensions, to some differential condition involving so-called “Lie brackets” \([u,v]\) between pairs of vector fields (see [liealgebrabackground] below for a more detailed exposition of this operation). However, in most cases of practical interest (such as for instance matrix factorization), the Frobenius theorem is not suitable for a direct application to the space \(W_\phi\) because its Lie bracket condition is not satisfied. To identify the number of independent conservation laws, one needs to consider the algebraic closure of \(W_\phi\) under Lie brackets. The fundamental object of interest is thus the Lie algebra generated by the Jacobian vector fields, that we recall next. While this is only defined for vector fields with stronger smoothness assumption, the only consequence is that \(\phi\) is required to be infinitely smooth, unlike the loss \(\ell(\cdot,y)\) and the model \(g(\cdot,x)\) that can be less smooth. All concretes examples of \(\phi\) in this paper are polynomial hence indeed infinitely smooth.
Given a vector subspace of infinitely smooth vector fields \(W \subseteq \mathcal{X}(\Theta) \mathrel{\vcenter{:}}= \mathcal{C}^{\infty}(\Theta, \mathbb{R}^D)\), where \(\Theta\) is an open subset of \(\mathbb{R}^D\), we recall (cf 1) that its trace at some \(\theta\) is the subspace \[\label{trace} W(\theta) \mathrel{\vcenter{:}}= \mathrm{span}\{ \chi(\theta) : \chi \in W \} \subseteq \mathbb{R}^D.\tag{9}\] For each open subset \(\Omega\subseteq \Theta\), we introduce the subspace of \(\mathcal{X}(\Omega)\): \(W_{|\Omega} \mathrel{\vcenter{:}}= \{ \chi_{|\Omega}: \chi \in W \}.\)
A Lie algebra \(A\) is a vector space endowed with a bilinear map \([\cdot, \cdot]\), called a Lie bracket, that verifies for all \(X, Y, Z \in A\): \([X, X]= 0\) and the Jacobi identity: \([X, [Y, Z]] + [Y, [Z, X]] + [Z, [X, Y]] = 0.\)
For the purpose of this article, the Lie algebra of interest is the set of infinitely smooth vector fields \(\mathcal{X}(\Theta)\), endowed with the Lie bracket \([\cdot, \cdot]\) defined by \[\label{eq:def-lie-brac} [\chi_1,\chi_2]:\quad \theta\in \Theta \mapsto [\chi_1, \chi_2](\theta)\mathrel{\vcenter{:}}= \partial \chi_1(\theta) \chi_2(\theta) - \partial \chi_2(\theta) \chi_1(\theta),\tag{10}\] with \(\partial \chi (\theta) \in \mathbb{R}^{D \times D}\) the jacobian of \(\chi\) at \(\theta\). The space \(\mathbb{R}^{n \times n}\) of matrices is also a Lie algebra endowed with the Lie bracket \([A, B] \mathrel{\vcenter{:}}= AB-BA.\) This can be seen as a special case of 10 in the case of linear vector fields, i.e. \(\chi(\theta)=A\theta\).
Let \(A\) be a Lie algebra and let \(W \subset A\) be a vector subspace of \(A\). There exists a smallest Lie algebra that contains \(W\). It is denoted \(\mathrm{Lie}(W)\) and called the generated Lie algebra of \(W\). The following proposition [31] constructively characterizes \(\mathrm{Lie}(W)\), where for vector subspaces \([W,W'] \mathrel{\vcenter{:}}= \{[\chi_1,\chi_2]: \chi_1 \in W, \chi_2 \in W'\}\), and \(W+W' = \{\chi_1+\chi_2: \chi_1 \in W, \chi_2 \in W'\}\).
Proposition 6. Given any vector subspace \(W \subseteq A\) we have \(\mathrm{Lie}(W) = \bigcup_k W_k\) where: \[\left\{ \begin{array}{ll} W_0 &\mathrel{\vcenter{:}}= W\\ W_k &\mathrel{\vcenter{:}}= W_{k-1} + [W_0, W_{k-1}]\;\text{ for }\;k \geq 1. \end{array} \right.\]
We will see in [section95dim95lie95algebra] that the number of conservation laws is characterized by the dimension of the trace \(\mathrm{Lie}(W_\phi)(\theta)\) defined in 9 . The following lemma (proved in 8) gives a stopping criterion to algorithmically determine this dimension (see [subsection-method] for the algorithm).
Lemma 2. Given \(\theta\in \Theta\), if for a given \(i\), \(\mathrm{dim}W_{i+1}(\theta') = \mathrm{dim}W_i(\theta)\) for every \(\theta'\) in a neighborhood of \(\theta\), then there exists a neighborhood \(\Omega\) of \(\theta\) such that \(W_k(\theta')= W_i (\theta')\) for all \(\theta' \in \Omega\) and \(k\geq i\), where the \(V_i\) are defined by 6. Thus \(\mathrm{Lie}(W)(\theta')= W_i (\theta')\) for all \(\theta' \in \Omega\). In particular, the dimension of the trace of \(\mathrm{Lie}(W)\) is locally constant and equal to the dimension of \(W_i(\theta)\).
The following theorem uses the Lie algebra generated by \(W_\phi\) to characterize the number of conservation laws. The proof of this result is based on two successive uses of the Frobenius theorem and can be found in 9 (where we also recall Frobenius theorem for the sake of completeness).
Theorem 7. If \(\mathrm{dim}(\mathrm{Lie}(W_\phi)(\theta))\) is locally constant then each \(\theta\in \Omega\subseteq \mathbb{R}^D\) admits a neighborhood \(\Omega'\) such that there are \(D- \mathrm{dim}(\mathrm{Lie}(W_\phi)(\theta))\) (and no more) independent conserved functions through \({W_\phi}_{\mid \Omega'}\), i.e., there are \(D-\mathrm{dim}(\mathrm{Lie}(W_\phi)(\theta))\) independent conservation laws of \(\phi\) on \(\Omega'\).
Remark 8. The proof of the Frobenius theorem (and therefore of our generalization 7) is actually constructive. From a given \(\phi\), conservation laws are obtained in the proof by integrating in time (i.e. solving an advection equation) the vector fields belonging to \(W_\phi\). Unfortunately, this cannot be achieved in closed form in general, but in small dimensions, this could be carried out numerically (to compute approximate discretized laws on a grid or approximate them using parametric functions such as Fourier expansions or neural networks).
A fundamental aspect of 7 is to rely only on the dimension of the trace of the Lie algebra associated with the finite-dimensional vector space \(W_\phi\). Yet, even if \(W_\phi\) is finite-dimensional, it might be the case that \(\mathrm{Lie}(W_\phi)\) itself remains infinite-dimensional. Nevertheless, what matters is not the dimension of \(\mathrm{Lie}(W_\phi)\), but that of its trace \(\mathrm{Lie}(W_\phi)(\theta)\), which is always finite (and potentially much smaller that \(\dim \mathrm{Lie}(W_\phi)\) even when the latter is finite) and computationally tractable thanks to 2 as detailed in [subsection-method]. In section 4.1 we work out the example of matrix factorization, a non-trivial case where the full Lie algebra \(\mathrm{Lie}(W_\phi)\) itself remains finite-dimensional.
7 requires that the dimension of the trace at \(\theta\) of the Lie algebra is locally constant. This is a technical assumption, which typically holds outside a set of pathological points. A good example is once again matrix factorization, where we show in Section 4.1 that this condition holds generically.
Given a reparametrization \(\phi\) for the architectures to train, to determine the number of independent conservation laws of \(\phi\), we leverage the characterization 6 to algorithmically compute \(\mathrm{dim}(\mathrm{Lie}(W_\phi)(\theta))\) using an iterative construction of bases for the subspaces \(W_k\) starting from \(W_0 \mathrel{\vcenter{:}}= W_\phi\), and stopping as soon as the dimension stagnates thanks to Lemma 2. Our open-sourced code is available at [28] and uses SageMath. As we now show, this algorithmic principle allows to fully work out certain settings where the stopping criterion of 2 is reached at the first step (\(i=0\)) or the second one (\(i=1\)). 4.2 also discusses its numerical use for an empirical investigation of broader settings.
This corresponds to the case where \(\mathrm{Lie}W_\phi (\theta) = W_1(\theta) = W_0(\theta) \mathrel{\vcenter{:}}= W_\phi(\theta)\) on \(\Omega\). This is the case if and only if \(W_\phi\) satisfies that \[\label{eq:frob-crochets} [\chi_1, \chi_2](\theta) \mathrel{\vcenter{:}}= \partial \chi_1 (\theta) \chi_2 (\theta) - \partial \chi_2(\theta) \chi_1(\theta) \in W_\phi(\theta), \quad \text{for all}\;\chi_1, \chi_2 \in W_\phi\;\text{and all}\;\theta\in \Omega.\tag{11}\] i.e., when Frobenius Theorem (see 17 in 9) applies directly. The first example is a follow-up to 3.
Example 5 (two-layer ReLU networks without bias). Consider \(\theta= (U,V)\) with \(U \in \mathbb{R}^{n\times r}, V \in \mathbb{R}^{m \times r}\), \(n, m,r \geq 1\) (so that \(D=(n+m)r\)), and the reparametrization \(\phi(\theta) \mathrel{\vcenter{:}}= (u_i v_i^\top)_{i=1, \cdots, r} \in \mathbb{R}^{n \times m \times r},\) where \(U=(u_1; \cdots; u_r)\) and \(V=(v_1; \cdots; v_r)\). As detailed in 10.1, since \(\phi(\theta)\) is a collection of \(r\) rank-one \(n\times m\) matrices, \(\mathrm{dim}(W_\phi(\theta)) = \mathtt{rank} \partial \phi(\theta)=(n+m-1)r\) is constant on the domain \(\Omega\) such that \(u_i, v_j \neq 0\), and \(W_\phi\) satisfies 11 , hence by 7 each \(\theta\) has a neighborhood \(\Omega'\) such that there exists \(r\) (and no more) independent conserved function through \({W_\phi}_{|\Omega'}\). The \(r\) known conserved functions [15] given by \(h_i: (U, V) \mapsto \|u_i\|^2 - \|v_i\|^2\), \(i=1, \cdots, r\), are independent, hence they are complete.
Our primary example is matrix factorization, as a follow-up to 2.
Example 6 (two-layer linear neural networks). With \(\theta= (U,V)\), where \((U \in \mathbb{R}^{n\times r}, V \in \mathbb{R}^{m \times r})\) the reparameterization \(\phi(\theta) \mathrel{\vcenter{:}}= U V^\top \in \mathbb{R}^{n \times m}\) (here \(d=nm\)) factorizes the functions minimized during the training of linear two-layer neural networks (see 2). As shown in 13, condition 11 is not satisfied when \(r > 1\) and \(\text{max}(n, m) > 1\). Thus, the stopping criterion of 2 is not satisfied at the first step. However, as detailed in 25 in 12, \((W_\phi)_1 = (W_\phi)_2 = \mathrm{Lie}(W_\phi)\), hence the iterations of 2 stop at the second step.
We complete this example in the next section by showing (2) that known conservation laws are indeed complete. Whether known conservation laws remain valid and/or complete in this settings and extended ones is further studied in [sectionlinearNN,annex:ExamplesSection3].
As we now show, one striking application of 7 (in simple cases where \(\mathrm{dim}(W_\phi( \theta)) = \mathrm{dim}(\mathrm{Lie}W_\phi( \theta))\) is constant on \(\Omega\), i.e., \(\mathtt{rank}(\partial \phi(\theta))\) is constant on \(\Omega\) and \(W_\phi\) satisfies 11 ) is to fully rewrite the high-dimensional flow \(\theta(t) \in \mathbb{R}^D\) as a low-dimensional flow on \(z(t) \mathrel{\vcenter{:}}= \phi(\theta(t)) \in \mathbb{R}^d\), where this flow is associated with a Riemannian metric tensor \(M\) that is induced by \(\phi\) and depends on the initialization \(\theta_{\text{init}}\). We insist on the fact that this is only possible in very specific cases, but this phenomenon is underlying many existing works that aim at writing in closed form the implicit bias associated with some training dynamics (see 1 for some relevant literature. Our analysis sheds some light on cases where this is possible, as shown in the next proposition.
Proposition 9. Assume that \(\mathtt{rank}(\partial\phi(\theta))\) is constant on \(\Omega\) and that \(W_\phi\) satisfies 11 . If \(\theta(t) \in \mathbb{R}^D\) satisfies the ODE 2 where \(\theta_{\text{init}} \in \Omega\), then there is \(0<T^{\star}_{\theta_\mathtt{init}}\leq T_{\theta_\mathtt{init}}\) such that \(z(t) \mathrel{\vcenter{:}}= \phi(\theta(t)) \in \mathbb{R}^d\) satisfies the ODE \[\label{transfertGF} \overset{.}{z}(t) = -M(z(t), \theta_{\text{init}}) \nabla f(z(t)) \quad for allt \in [0, T^{\star}_{\theta_{\mathtt{init}}} ), \text{ with } z(0) = \phi(\theta_{\text{init}}),\qquad{(2)}\] where \(M(z(t),\theta_{\text{init}}) \in \mathbb{R}^{d \times d}\) is a symmetric positive semi-definite matrix.
See 11 for a proof. Revisiting 5 leads to the following analytic example.
Example 7. Given the reparametrization \(\phi: (u \in \mathbb{R}^*, v \in \mathbb{R}^d) \mapsto u v \in \mathbb{R}^d\), the variable \(z \mathrel{\vcenter{:}}= uv\) satisfies ?? with \(M(z, \theta_{\text{init}}) = \|z\|_\delta \mathrm{I}_{d} + \|z\|_\delta ^{-1} z z^\top,\) with \(\|z\|_\delta \mathrel{\vcenter{:}}= \delta + \sqrt{\delta ^{2} + \| z \| ^2}\), \(\delta \mathrel{\vcenter{:}}= 1/2(u_{\text{init}}^2-\| v _{\text{init}} \|^2)\).
Another analytic example is discussed in 11. In light of these results, an interesting perspective is to better understand the dependance of the Riemannian metric with respect to initialization, to possibly guide the choice of initialization for better convergence dynamics.
Note that the metric \(M(z,\theta_{\text{init}})\) can have a kernel. Indeed, in practice, while \(\phi\) is a function from \(\mathbb{R}^D\) to \(\mathbb{R}^d\), the dimensions often satisfy \(\mathtt{rank} \partial \phi(\theta) < \min(d,D)\), i.e., \(\phi(\theta)\) lives in a manifold of lower dimension. The evolution ?? should then be understood as a flow on this manifold. The kernel of \(M(z,\theta_{\text{init}})\) is orthogonal to the tangent space at \(z\) of this manifold.
To showcase the impact of our results, we show how they can be used to determine whether known conservation laws for linear (resp. ReLU) neural networks are complete, and to recover these laws algorithmically using reparametrizations \(\phi\) adapted to these two settings. Concretely, we study the conservation laws for neural networks with \(q\) layers, and either a linear or ReLU activation, with an emphasis on \(q=2\). We write \(\theta= (U_1, \cdots, U_q)\) with \(U_i \in \mathbb{R}^{n_{i-1} \times n_{i}}\) the weight matrices and we assume that \(\theta\) satisfies the gradient flow 2 . In the linear case the reparametrization is \(\phi_{\mathtt{Lin}}(\theta) \mathrel{\vcenter{:}}= U_1 \cdots U_q\). For ReLU networks, we use the (polynomial) reparametrization \(\phi_{\mathtt{ReLu}}\) of [27], which is defined for any (deep) feedforward ReLU network, with or without bias. In the simplified setting of networks without biases it reads explicitly as: \[\phi_{\mathtt{ReLu}}(U_1, \cdots, U_q) \mathrel{\vcenter{:}}= \Big(U_1[:, j_1] U_2[j_1, j_2] \cdots U_{q-1}[j_{q-2}, j_{q-1}] U_{q}[j_{q-1},:]\Big)_{j_1, \cdots, j_{q-1}}\] with \(U[i, j]\) the \((i, j)\)-th entry of \(U\). This covers \(\phi(\theta) \mathrel{\vcenter{:}}= (u_j v_j^\top)_{j=1}^r \in \mathbb{R}^{n \times m \times r}\) from 3.
Some conservation laws are known for the linear case \(\phi_{\mathtt{Lin}}\) [16], [17] and for the ReLu case \(\phi_{\mathtt{ReLu}}\) [15].
Proposition 10 ( [15]–[17] ). If \(\theta\mathrel{\vcenter{:}}=(U_1, \cdots, U_q)\) satisfies the gradient flow 2 , then for each \(i = 1, \cdots, q-1\) the function \(\theta\mapsto U_{i}^\top U_{i} - U_{i+1} U_{i+1}^\top\) (resp. the function \(\theta\mapsto \text{diag} \left(U_{i}^\top U_{i} - U_{i+1} U_{i+1}^\top \right)\)) defines \(n_i \times (n_i +1)/2\) conservation laws for \(\phi_{\mathtt{Lin}}\) (resp. \(n_i\) conservation laws for \(\phi_{\mathtt{ReLu}}\)).
Proposition 10 defines \(\sum_{i=1}^{q-1} n_i \times (n_i +1)/2\) conserved functions for the linear case. In general they are not independent, and we give below in Proposition 11, for the case of \(q=2\), the exact number of independent conservation laws among these particular laws. Establishing whether there are other (previously unknown) conservation laws is an open problem for \(q>2\). We already answered negatively to this question in the two-layer ReLu case without bias (See 5). In the following Section (2), we show the same result in the linear case \(q=2\). Numerical computations suggest this is still the case for deeper linear and ReLU networks as detailed in 4.2.
To simplify the analysis when \(q=2\), we rewrite \(\theta= (U,V)\) as a vertical matrix concatenation denoted \((U; V) \in \mathbb{R}^{(n+m) \times r}\), and \(\phi(\theta) = \phi_{\mathtt{Lin}}(\theta) = U V^\top \in \mathbb{R}^{n \times m}\).
The following proposition refines Proposition 10 for \(q=2\) by detailing how many independent conservation laws are already known. See Appendix 12.1 for a proof.
Proposition 11. Consider \(\Psi: \theta= (U; V) \mapsto U^\top U - V^\top V \in \mathbb{R}^{r \times r}\) and assume that \((U; V)\) has full rank noted \(\mathtt{rk}\). Then the function \(\Psi\) gives \(\mathtt{rk} \cdot (2r + 1-\mathtt{rk})/2\) independent conservation laws.
We now come to the core of the analysis, which consists in actually computing \(\mathrm{Lie}(W_\phi)\) as well as its traces \(\mathrm{Lie}(W_\phi)(\theta)\) in the matrix factorization case. The crux of the analysis, which enables us to fully work out theoretically the case \(q=2\), is that \(W_\phi\) is composed of linear vector fields (that are explicitly characterized in 24 in 12), the Lie bracket between two linear fields being itself linear and explicitly characterized with skew matrices, see 25 in 12. Eventually, what we need to compute is the dimension of the trace \(\mathrm{Lie}(W_\phi) (U, V)\) for any \((U, V)\). We prove the following in 12.
Proposition 12. If \((U; V) \in \mathbb{R}^{(n+m) \times r}\) has full rank noted \(\mathtt{rk}\), then: \(\mathrm{dim}(\mathrm{Lie}(W_\phi) (U; V)) \!=\! (n+m)r - \mathtt{rk}(2r + 1-\mathtt{rk})/2\).
With this explicit characterization of the trace of the generated Lie algebra and 11, we conclude that 10 has indeed exhausted the list of independent conservation laws.
Corollary 2. If \((U; V)\) has full rank, then all conservation laws are given by \(\Psi: (U, V) \mapsto U^\top U - V^\top V\). In particular, there exist no more independent conservation laws.
The expressions derived in the previous section are specific to the linear case \(q=2\). For deeper linear networks and for ReLU networks, the vector fields in \(W_\phi\) are non-linear polynomials, and computing Lie brackets of such fields can increase the degree, which could potentially make the generated Lie algebra infinite-dimensional. One can however use 2 and stop as soon as \(\mathrm{dim}\left(({W_\phi})_k(\theta)\right)\) stagnates. Numerically comparing this dimension with the number \(N\) of independent conserved functions known in the literature (predicted by 10) on a sample of depths/widths of small size, we empirically confirmed that there are no more conservation laws than the ones already known for deeper linear networks and for ReLU networks too (see 14 for details). Our code is open-sourced and is available at [28]. It is worth mentioning again that in all tested cases \(\phi\) is polynomial, and there is a maximum set of conservation laws that are also polynomial, which are found algorithmically (as detailed in 2.5).
In this article, we proposed a constructive program for determining the number of conservation laws. An important avenue for future work is the consideration of more general classes of architectures, such as deep convolutional networks, normalization, and attention layers. Note that while we focus in this article on gradient flows, our theory can be applied to any space of displacements in place of \(W_\phi\). This could be used to study conservation laws for flows with higher order time derivatives, for instance gradient descent with momentum, by lifting the flow to a higher dimensional phase space. A limitation that warrants further study is that our theory is restricted to continuous time gradient flow. Gradient descent with finite step size, as opposed to continuous flows, disrupts exact conservation. The study of approximate conservation presents an interesting avenue for future work.
The work of G. Peyré was supported by the European Research Council (ERC project NORIA) and the French government under management of Agence Nationale de la Recherche as part of the “Investissements d’avenir” program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). The work of R. Gribonval was partially supported by the AllegroAssai ANR project ANR-19-CHIA-0009. We thank Thomas Bouchet for introducing us to SageMath, as well as Léo Grinsztajn for helpful feedbacks regarding the numerics. We thank Pierre Ablin and Raphaël Barboni for comments on a draft of this paper. We also thank the anonymous reviewers for their fruitful feedback.
1 is a direct consequence of the following lemma (remember that \(\nabla h(\theta) = [\partial h(\theta)]^\top\)).
Lemma 3 ( Smooth functions conserved through a given flow.). Given \(\chi \in \mathcal{C}^1(\Omega, \mathbb{R}^D)\), a function \(h \in \mathcal{C}^1(\Omega, \mathbb{R})\) is conserved through the flow induced by \(\chi\) if and only if \(\partial h (\theta) \chi(\theta) = 0\) for all \(\theta\in \Omega\).
Proof. Assume that \(\partial h (\theta) \chi(\theta) = 0\) for all \(\theta\in \Omega\). Then for all \(\theta_{\text{init}} \in \Omega\) and for all \(t \in (0, T_{\theta_{\text{init}}}):\) \[\begin{align} \frac{\mathrm{d}}{\mathrm{d}t} h(\theta(t, \theta_{\text{init}})) &= \partial h(\theta(t, \theta_{\text{init}})) \overset{.}{\theta}(t, \theta_{\text{init}}) = \partial h(\theta(t, \theta_{\text{init}})) \chi(\theta(t, \theta_{\text{init}}))= 0. \end{align}\] Thus: \(h(\theta(t, \theta_{\text{init}}))= h(\theta_{\text{init}})\), i.e., \(h\) is conserved through \(\chi\). Conversely, assume that there exists \(\theta_0 \in \Omega\) such that \(\partial h(\theta_0) \chi(\theta_0) \neq 0\). Then by continuity of \(\theta\in \Omega\mapsto \partial h(\theta)\chi(\theta)\), there exists \(r > 0\) such that \(\partial h(\theta) \chi(\theta) \neq 0\) on \(B(\theta_0, r)\). With \(\theta_{\text{init}} = \theta_0\) by continuity of \(t \mapsto \theta(t, \theta_{\text{init}})\), there exists \(\varepsilon> 0\), such that for all \(t< \varepsilon\), \(\theta(t, \theta_{\text{init}}) \in B(\theta_0, r)\). Then for all \(t \in (0, \varepsilon)\):\(\frac{\mathrm{d}}{\mathrm{d}t} h(\theta(t,\theta_{\text{init}})) = \partial h(\theta(t, \theta_{\text{init}})) \chi(\theta(t, \theta_{\text{init}})) \neq 0,\) hence \(h\) is not conserved through the flow induced by \(\chi\). ◻
Proposition 13. Assume that for each \(y \in \mathcal{Y}\) the loss \(\ell(z, y)\) is \(\mathcal{C}^2\)-differentiable with respect to \(z \in \mathbb{R}^n\). For each \(\theta\in \Theta\) we have: \[W_\theta^g = \underset{(x, y) \in {\mathcal{X}}_\theta\times \mathcal{Y}}{\mathrm{span}} \{ [\partial_\theta g(\theta,x)]^\top \nabla_z \ell (g(\theta,x), y) \}\] where \(\mathcal{X}_\theta\) is the set of data points \(x\) such that \(g(\cdot,x)\) is \(\mathcal{C}^2\)-differentiable in the neighborhood of \(\theta\).
Proof. Let us first show the direct inclusion. Let \(\Omega\subseteq \Theta\) be a neighborhood of \(\theta\) and let \(\chi \in W_{\Omega}^g\). Let us show that \(\chi(\theta) \in \underset{(x, y) \in {\mathcal{X}}_\theta\times \mathcal{Y}}{\mathrm{span}} \{ [\partial_\theta g(\theta,x)]^\top \nabla_z \ell (g(\theta,x), y) \}\). As \(\chi \in W_{\Omega}^g\), there exist \(X = (x_i)_i, Y = (y_i)_i\) such that \(\forall i\;g(\cdot, x_i) \in \mathcal{C}^{2}(\Omega,\mathbb{R})\) (and thus \(x_i \in \mathcal{X}_\theta\)) and \(\chi(\cdot) = \nabla \mathcal{E}_{X, Y}(\cdot) \in \mathcal{C}^1(\Omega, \mathbb{R}^D)\) (cf 3 ). Moreover, for each \(\theta' \in \Omega\), by chain rules and 1 , we have: \[\nabla \mathcal{E}_{X, Y}(\theta') = \sum_i [\partial_\theta g(\theta', x_i)]^\top \nabla_z \ell (g(\theta', x_i), y_i),\] where \(x_i \in \mathcal{X}_\theta\). Thus \(\chi(\theta) \in \underset{(x, y) \in {\mathcal{X}}_\theta\times \mathcal{Y}}{\mathrm{span}} \{ [\partial_\theta g(\theta,x)]^\top \nabla_z \ell (g(\theta,x), y) \}\). This leads to the direct inclusion.
Now let us show the converse inclusion. Let \((x, y) \in \mathcal{X}_\theta\times \mathcal{Y}\). Let us show that \([\partial_\theta g(\theta, x)]^\top \nabla_z \ell (g(\theta, x), y) \in W_\theta^g\). By definition of \(\mathcal{X}_\theta\), there exists a neighborhood \(\Omega\) of \(\theta\) such that \(g(\cdot, x) \in \mathcal{C}^2(\Omega, \mathbb{R}^D)\). By taking \(X = x\) and \(Y = y\) (i.e. a data set of one feature and one target), one has still by chain rules \(\nabla \mathcal{E}_{X, Y} (\cdot) = [\partial_\theta g(\cdot, x)]^\top \nabla_z \ell (g(\cdot, x), y) \in W_{\Omega}^g\). Finally by definition 4 of the trace and by 5 , \([\partial_\theta g(\theta, x)]^\top \nabla_z \ell (g(\theta, x), y) = \nabla \mathcal{E}_{X, Y} (\theta) \in W_{\Omega}^g (\theta) \subseteq W_\theta^g\) as \(\Omega\) is a neighborhood of \(\theta\). ◻
We recall (cf 2 and 3) that linear and \(2\)-layer ReLU neural networks satisfy 1, which we recall reads as:
Assumption 2.9(Local reparameterization) For each parameter \(\theta_0 \in \mathbb{R}^D\), for each \(x \in \mathcal{X}_{\theta_0}\), there is a neighborhood \(\Omega\) of \(\theta_0\) and a function \(f(\cdot, x) \in \mathcal{C}^2(\phi(\Omega), \mathbb{R}^n)\) such that \[\forall \theta\in
\Omega, \quad g(\theta,x) = f(\phi(\theta), x),\] where we also recall that \[\label{eq:X}
\mathcal{X}_{\theta_0}\mathrel{\vcenter{:}}= \{ x \in \mathcal{X}: \theta\mapsto g(\theta, x) \text{ is } \mathcal{C}^2 \text{ in the neighborhood of } \theta_0\}.\tag{12}\] A common assumption to 1 and 4 is that the loss \(\ell(z, y)\) is
such that \(\ell(\cdot, y)\) is \(\mathcal{C}^2\)-differentiable for all \(y\), hence by 2 and 3 we have \[W_\theta^g = \underset{(x, y) \in {\mathcal{X}}_\theta\times \mathcal{Y}}{\mathrm{span}} \{
[\partial_\theta g(\theta,x)]^\top \nabla_z \ell (g(\theta,x), y) \} \quad \text{ and } \quad W_\theta^g = \partial \phi(\theta)^\top W^{f}_{\phi(\theta)}\] where \[W^{f}_{\phi(\theta)} \mathrel{\vcenter{:}}= \underset{(x,
y) \in {\mathcal{X}}_\theta\times \mathcal{Y}}{\mathrm{span}} \{ \partial f^x(\phi(\theta))^\top \nabla_z \ell (g(\theta, x), y) \} \text{ and } f^x(\cdot) \mathrel{\vcenter{:}}= f(\cdot, x).\] Consequence of the assumption 8 . To proceed further we will rely on the following lemma that shows a direct consequence of 8 (in addition to 1 on the model \(g(\theta, \cdot)\)).
Lemma 4. Under 1, considering a loss \(\ell(z, y)\) such that \(\ell(\cdot, y)\) is \(\mathcal{C}^2\)-differentiable for all \(y\). Denote \(f^x(\cdot) \mathrel{\vcenter{:}}= f(\cdot, x)\). If the loss satisfies 8 , i.e. \[\underset{y \in \mathcal{Y}}{\mathrm{span}}\{\nabla_z \ell (z, y) \}= \mathbb{R}^n, \forall z \in \mathbb{R}^n,\]
then for all \(\theta \in \mathbb{R}^D\), \[W^{f}_{\phi(\theta)} = \underset{(x, w) \in {\mathcal{X}}_\theta\times \mathbb{R}^n}{\mathrm{span}} \{ \partial f^x(\phi(\theta))^\top w \}\]
Proof. For \(\theta\in \mathbb{R}^D\), we have \[\begin{align} W^{f}_{\phi(\theta)} &=\underset{(x, y) \in {\mathcal{X}}_\theta\times \mathcal{Y}}{\mathrm{span}} \{ \partial f^x(\phi(\theta))^\top \nabla_z \ell (g(\theta,x), y) \} \\ &= \underset{x \in {\mathcal{X}}_\theta}{\mathrm{span}} \big\{ \partial f^x(\phi(\theta))^\top \underset{y \in \mathcal{Y}}{\mathrm{span}} \{ \nabla_z \ell (g(\theta, x), y) \} \big\} \\ &\stackrel{\eqref{eq:condition95loss}}{=} \underset{x \in {\mathcal{X}}_\theta}{\mathrm{span}} \{ \partial f^x(\phi(\theta))^\top \mathbb{R}^n \}\\ &= \underset{(x, w) \in {\mathcal{X}}_\theta\times \mathbb{R}^n}{\mathrm{span}} \{ \partial f^x(\phi(\theta))^\top w \}.\qedhere \end{align}\] ◻
Verification of 8 for standard ML losses. Before proceeding to the proof of 1 and 4, let us show that 8 holds for standard ML losses.
Lemma 5. The mean-squared error loss \((z, y) \mapsto \ell_2(z, y) \mathrel{\vcenter{:}}= \| y-z \|^2\) and the logistic loss \((z \in \mathbb{R}, y \in \{-1, 1 \}) \mapsto \ell_{\mathtt{logis}}(z, y) \mathrel{\vcenter{:}}= \log (1+ \exp(-zy) )\) satisfy condition 8 .
Proof. To show that \(\ell_2\) satisfies 8 we observe that, with \(e_i\) the \(i\)-th canonical vector, we have \[\mathbb{R}^n = \mathrm{span}\{e_i: 1 \leq i \leq n\} = \underset{y \in \{z-e_i/2\}_{i=1}^n}{\mathrm{span}}\;2(z-y) \subseteq \underset{y \in \mathbb{R}^n}{\mathrm{span}}\; 2(z-y) = \underset{y \in \mathbb{R}^n}{\mathrm{span}} \nabla_z \ell_2(z, y) \subseteq \mathbb{R}^n.\]
For the logistic loss, \(\nabla_z \ell_{\mathtt{logis}}(z, y) = \frac{-y \exp(-zy)}{1+ \exp(-zy)} \neq 0\) hence \(\mathrm{span}_y \nabla_z \ell_{\mathtt{logis}}(z, y) =\mathbb{R}\). ◻
Remark 14. In the case of the cross-entropy loss \((z \in \mathbb{R}^{n}, y \in \{ 1, \cdots, n\}) \mapsto \ell_{\mathtt{cross}}(z,y) \mathrel{\vcenter{:}}= - z_y + \log\left(\sum_{i=1}^n \exp z_i \right)\), \(\ell_{\mathtt{cross}}\) does not satisfy 8 as \(\nabla_z \ell_{\mathtt{cross}} (z, y) = -e_y + \begin{pmatrix} \exp(z_1)/(\sum_i \exp z_i) \\ \cdots \\ \exp(z_n)/(\sum_i \exp z_i) \end{pmatrix}\) satisfies for all \(z \in \mathbb{R}^n\): \[\mathrm{span}_y \nabla_z \ell_{\mathtt{cross}}(z, y) = \{ w\mathrel{\vcenter{:}}=(w_1, \cdots, w_n) \in \mathbb{R}^n: \sum w_i = 0 \}=: L_{\mathtt{cross}}.\]
An interesting challenge is to investigate variants of 1 under weaker assumptions that would cover the cross-entropy loss.
The case of linear neural networks of any depth. Let us first prove 1 and 4 for the case of linear neural networks.
Theorem 15 (linear networks). Consider a linear network parameterized by \(q\) matrices, \(\theta= (U_1,\ldots, U_q)\) and defined via \(g(\theta,x) \mathrel{\vcenter{:}}= U_1\ldots U_q x\). With \(\phi(\theta) \mathrel{\vcenter{:}}= U_1\ldots U_q \in \mathbb{R}^{n \times m}\) (identified with \(\mathbb{R}^d\) with \(d = nm\)), and for any loss \(\ell\) satisfying 8 , we have for all \(\theta\in \mathbb{R}^D\), \(W^{f}_{\phi(\theta)}= \mathbb{R}^d\) and \(W_\theta^g =\mathrm{range}( \partial \phi(\theta)^\top )\).
Proof. Let \(\theta\in \Theta = \mathbb{R}^D\). As we can factorize the model (cf 2) by \(g(\cdot, x) = \phi(\cdot) x=: f^x (\phi(\cdot)) \in \mathbb{R}^n\) for \(x \in \mathcal{X}_{\theta} = \mathbb{R}^m\). Thus, by using 4: \(W^{f}_{\phi(\theta)} = \mathrm{span}_{x \in \mathcal{X}_{\theta}, w \in \mathbb{R}^n} \{ [\partial f^{x}(\phi(\theta))]^\top w \} = \mathrm{span}_{x \in \mathbb{R}^m, w \in \mathbb{R}^n} \{ w x^\top \} = \mathbb{R}^d\). Finally by 3: \(W_\theta^g = \partial \phi(\theta)^\top W^{f}_{\phi(\theta)} = \mathrm{range}(\partial \phi(\theta)^\top).\) ◻
The case of two-layer ReLU networks. In the case of two-layer ReLU networks with \(r\) neurons, one can write \(\theta= (U,V,b,c) \in \mathbb{R}^{n \times r} \times \mathbb{R}^{m \times r} \times \mathbb{R}^r \times \mathbb{R}^n\), and denote \(u_j\) (resp. \(v_j\), \(b_j\)) the columns of \(U\) (resp. columns of \(V\), entries of \(b\)), so that \(g_\theta(x) = \sum_{j=1}^r u_j \sigma(v_j^\top x+b_j)+c\). The set \(\mathcal{X}_\theta\) (defined in 12 ) is simply the complement in the input domain \(\mathbb{R}^m\) of the union of the hyperplanes \[\label{eq:hyperplan} \mathcal{H}_j \mathrel{\vcenter{:}}= \{x \in \mathbb{R}^m: v_j^\top x+b_j=0\}.\tag{13}\]
Theorem 16 (two-layer ReLU networks). Consider a loss \(\ell(z, y)\) satisfying 8 and such that \(\ell(\cdot, y)\) is \(\mathcal{C}^2\)-differentiable for all \(y\). On a two-layer ReLU network architecture, let \(\theta\) be a parameter such that all hyperplanes \(\mathcal{H}_j\) defined in 13 are pairwise distinct. Then, with \(\phi_{\mathtt{ReLU}}\) the reparameterization of 3, we have: \(W^{f}_{\phi_{\mathtt{ReLU}}(\theta)}= \mathbb{R}^d\) and \(W_\theta^g =\mathrm{range}( \partial \phi_{\mathtt{ReLU}}(\theta)^\top )\).
Proof. Let \(\theta\) be a parameter such that all hyperplanes \(\mathcal{H}_j\) defined in 13 are pairwise distinct. Since the loss \(\ell\) satisfies 8 , by 4, we only need to show that: \[\underset{(x, w) \in {\mathcal{X}}_\theta\times \mathbb{R}^n}{\mathrm{span}} \{ \partial f^x(\phi(\theta))^\top w \} = \mathbb{R}^d.\] For convenience, we will use the shorthand \(C_{\theta,x}\) for the Jacobian matrix \(\partial f^x(\phi(\theta))\).
1st case: We consider first the case without bias (\(b_j, c = 0\)). In that case, by 3 we have \(\phi(\theta) \mathrel{\vcenter{:}}= (u_jv_j^\top)_{j=1}^r\) where we write: \(\theta= (U,V) \in \mathbb{R}^{n \times r} \times \mathbb{R}^{m \times r}\), and denote \(u_j\) (resp. \(v_j\)) the columns of \(U\) (resp. columns of \(V\)). Here \(d=rnm\) and it can be checked (see 3) that \[C_{\theta, x}^\top \mathrel{\vcenter{:}}= \begin{pmatrix} \varepsilon_1(x, \theta) A(x) \\ \cdots \\ \varepsilon_r(x, \theta) A(x) \end{pmatrix} \in \mathbb{R}^{(rnm) \times n}\] where: \[A: x \in \mathbb{R}^m \mapsto A(x) \mathrel{\vcenter{:}}= \begin{pmatrix} x & 0 & \cdots & 0 \\ 0 & x & \cdots & 0 \\ \cdots & \cdots & \cdots & \cdots \\ 0 & \cdots & 0 & x \end{pmatrix} \in \mathbb{R}^{(nm) \times n},\] and where \(\varepsilon_i(x, \theta) = \mathbb{1} (v_i^\top x > 0)\).
For \(j = 1, \cdots, r\) we denote: \[\mathcal{A}_j^+ \mathrel{\vcenter{:}}= \{ x \in \mathbb{R}^m: v_j^\top x > 0 \}, \quad\text{and}\quad \mathcal{A}_j^- \mathrel{\vcenter{:}}= \{ x \in \mathbb{R}^m: v_j^\top x < 0 \}.\] The open Euclidean ball of radius \(r>0\) centered at \(c \in \mathbb{R}^m\) is denoted \(B(c,r)\).
Consider a hidden neuron \(i \in \{1, \cdots, r \}\) and denote \(\mathcal{H}_i' \mathrel{\vcenter{:}}= \mathcal{H}_i - \left(\bigcup_{j \neq i} \mathcal{H}_j \right)\). Since the hyperplanes are pairwise distinct, \(\mathcal{H}_i' \neq \emptyset\) so we can consider an arbitrary \(x' \in \mathcal{H}'_i\). Given any \(\eta > 0\), by continuity of \(x \in \mathbb{R}^m \mapsto (v_1^\top x, \cdots, v_r^\top x) \in \mathbb{R}^r\), there exists \(x_\eta^+ \in B(x', \eta) \cap \mathcal{A}_i^+\) and \(x_\eta^- \in B(x', \eta) \cap \mathcal{A}_i^-\) such that for all \(j \neq i\), \(\text{sign}(v_j^\top x_\eta^{\pm}) = \text{sign}(v_j^\top x')\). It follows that \(x_\eta^\pm \in \mathcal{X}_{\theta}\) (remember that \(\mathcal{X}_\theta\) is the complement of \(\cup_j \mathcal{H}_j\)). As a consequence: \[\begin{pmatrix} 0 \\ \cdots \\ 0 \\ A(x') \\ 0 \\\cdots \\ 0 \end{pmatrix} = \lim_{\eta \to 0} \left(C_{\theta, x_\eta^+}^\top - C_{\theta, x_\eta^-}^\top \right) \in \overline{\underset{x \in \mathcal{X}_{\theta}}{\mathrm{span}} \{ C_{\theta, x} ^\top \} } = \underset{x \in \mathcal{X}_{\theta}}{\mathrm{span}} \{ C_{\theta, x} ^\top \},\] where the nonzero line in the left-hand-side is the \(i\)-th, and we used that every finite-dimensional space is closed.
Moreover still by continuity of \(x \in \mathbb{R}^m \mapsto (v_1^\top x, \cdots, v_r^\top x) \in \mathbb{R}^r\), there exists \(\gamma > 0\), such that for \(k = \{-2, -1, 1, 2 \}\), the vectors defined as: \[x_{k} \mathrel{\vcenter{:}}= x' + \gamma k v_i,\] satisfy for all \(j \neq i\), \(\text{sign}(v_j^\top x_{k}) = \text{sign}(v_j^\top x')\) and \(v_i^\top x_k \neq 0\), so that \(x_k \in \mathcal{X}_{\theta}\) and we similarly obtain \[\begin{pmatrix} 0 \\ \cdots \\ 0 \\ \gamma A(v_i) \\ 0 \\\cdots \\ 0 \end{pmatrix} = C_{\theta, x_2}^\top - C_{\theta, x_1}^\top - \left( C_{\theta, x_{-1}}^\top - C_{\theta, x_{-2}}^\top \right) \in \underset{x \in \mathcal{X}_{\theta}}{\mathrm{span}} \{ C_{\theta, x} ^\top \}.\] As this holds for every \(x' \in \mathcal{H}_i'\), and since \(\mathrm{span}\{v_i,\mathcal{H}'_i\} = \mathbb{R}^m\), we deduce that for any \(x \in \mathbb{R}^m\) \[\begin{pmatrix} 0 \\ \cdots \\ 0 \\ A(x) \\ 0 \\\cdots \\ 0 \end{pmatrix} \in \underset{x \in \mathcal{X}_{\theta}}{\mathrm{span}} \{ C_{\theta, x} ^\top \}.\] As this holds for every hidden neuron \(i = 1, \cdots, r\) it follows that for every \(x^1, \cdots, x^r \in \mathbb{R}^m\) \[\begin{pmatrix} A(x^1) \\ \cdots \\ A(x^r) \end{pmatrix} \in \underset{x \in \mathcal{X}_{\theta}}{\mathrm{span}} \{ C_{\theta, x} ^\top \}.\] Moreover, by definition of \(A(\cdot)\), for each \(x \in \mathbb{R}^m\) and each \(w = (w_1, \cdots, w_n) \in \mathbb{R}^n\), we have \[A(x)w = \begin{pmatrix} w_1 x \\ \cdots \\ w_n x \end{pmatrix} \in \mathbb{R}^{nm}.\] Identifying \(\mathbb{R}^{nm}\) with \(\mathbb{R}^{m \times n}\) and the above expression with \(x w^\top\), we deduce that \[\underset{x \in \mathbb{R}^m, w \in \mathbb{R}^n}{\mathrm{span}} A(x)w = \mathbb{R}^{nm}\] and we let the reader check that this implies \[\underset{x^1, \cdots, x^r \in \mathbb{R}^m, w \in \mathbb{R}^n}{\mathrm{span}} \begin{pmatrix} A(x^1) \\ \cdots \\ A(x^r) \end{pmatrix} w = \underset{x^1, \cdots, x^r \in \mathbb{R}^m, w \in \mathbb{R}^n}{\mathrm{span}} \begin{pmatrix} A(x^1) w \\ \cdots \\ A(x^r)w \end{pmatrix} = \mathbb{R}^{rnm}.\] Thus, as claimed, we have \[\underset{x \in \mathcal{X}_{\theta}, w \in \mathbb{R}^n}{\mathrm{span}} \{ C_{\theta, x} ^\top w \} = \mathbb{R}^{rnm} = \mathbb{R}^d.\] 2d case: General case with biases. The parameter is \(\theta= (U,V,b, c) \in \mathbb{R}^{n \times r} \times \mathbb{R}^{m \times r} \times \mathbb{R}^r \times \mathbb{R}^n\) with \(b = (b_i)_{i=1}^r\), where \(b_i \in \mathbb{R}\) the bias of the \(i\)-the hidden neuron, and \(c\) the output bias.
In that case, \(d= rn(m+1)\) and one can check that the conditions of 1 hold with \(\phi_{\mathtt{ReLU}}(\theta) \mathrel{\vcenter{:}}= ((u_iv_i^\top, u_ib_i)_{i=1}^r, c)\) and \(f^x(\phi) \mathrel{\vcenter{:}}= C_{\theta,x}\phi\) where \(C_{\theta, x}\) is expressed as: \[C_{\theta, x}^\top \mathrel{\vcenter{:}}= \begin{pmatrix} \varepsilon_1(x, \theta) A'(x) \\ \cdots \\ \varepsilon_r(x, \theta) A'(x) \\ I_n \end{pmatrix} \in \mathbb{R}^{(rn(m+1) + n) \times n}\] where, denoting \(\bar{x} = (x^\top, 1)^\top \in \mathbb{R}^{m+1}\), we defined
\[A': x \in \mathbb{R}^m \mapsto A'(x) \mathrel{\vcenter{:}}= \begin{pmatrix} \bar{x} & 0 & \cdots & 0 \\ 0 & \bar{x} & \cdots & 0 \\ \cdots & \cdots & \cdots & \cdots \\ 0 & \cdots & 0 & \bar{x} \end{pmatrix} \in \mathbb{R}^{n(m+1) \times n},\] and \(\varepsilon_i(x, \theta) \mathrel{\vcenter{:}}= \mathbb{1} (v_i^\top x + b_i > 0)\).
Using the sets \[\mathcal{A}_j^+ \mathrel{\vcenter{:}}= \{ x \in \mathbb{R}^m: v_j^\top x+b_j > 0 \}, \quad\text{and}\quad \mathcal{A}_j^- \mathrel{\vcenter{:}}= \{ x \in \mathbb{R}^m: v_j^\top x+b_j < 0 \},\] a reasoning analog to the case without bias allows to show that for each \(i = 1, \cdots, r\):
\[\underset{x \in \mathbb{R}^m}{\mathrm{span}} \begin{pmatrix} 0 \\ \cdots \\ 0 \\ A'(x) \\ 0 \\\cdots \\ 0 \end{pmatrix} \in \underset{x \in \mathcal{X}_{\theta}}{\mathrm{span}} \{ C_{\theta, x} ^\top \}\] so that, again, for every \(x^1,\ldots, x^r \in \mathbb{R}^m\) we have \[\begin{pmatrix} A'(x^1) \\ \cdots \\ A'(x^r) \\ 0 \end{pmatrix} \in \underset{x \in \mathcal{X}_{\theta}}{\mathrm{span}} \{ C_{\theta, x} ^\top \}.\] As \(\begin{pmatrix} 0 \\ \cdots \\ 0 \\ I_n \end{pmatrix} \in \underset{x \in \mathcal{X}_{\theta}}{\mathrm{span}} \{ C_{\theta, x} ^\top \}\) too, we obtain that \(\begin{pmatrix} A'(x^1) \\ \cdots \\ A'(x^r) \\ I_n \end{pmatrix} \in \underset{x \in \mathcal{X}_{\theta}}{\mathrm{span}} \{ C_{\theta, x} ^\top \}.\)
Now, for each \(x \in \mathbb{R}^m\) and \(w = (w_1, \cdots, w_n) \in \mathbb{R}^n\), we have \[A'(x)w = \begin{pmatrix} w_1 \bar{x} \\ \cdots \\ w_n \bar{x} \end{pmatrix} = \begin{pmatrix} w_1 x \\ w_1 \\ \cdots \\ w_n x \\ w_n \end{pmatrix}\in \mathbb{R}^{n(m+1)}.\] Again, identifying the above expression with \(w (x^\top,1) \in \mathbb{R}^{n \times (m+1)}\) it is not difficult to check that \[\underset{x \in \mathbb{R}^m, w \in \mathbb{R}^n}{\mathrm{span}} A'(x)w = \mathbb{R}^{n (m+1)},\] and we conclude as before.
In both cases we established that \(W^f_{\phi_{\mathtt{ReLU}}}(\theta) = \mathbb{R}^d\). Finally by 3 we obtain \(W_\theta^g = \partial \phi_{\mathtt{ReLU}}(\theta)^\top W^{f}_{\phi_{\mathtt{ReLU}}(\theta)} = \mathrm{range}(\partial \phi_{\mathtt{ReLU}}(\theta)^\top)\). ◻
Combining 15 and 16 establishes 1 4 as claimed. One can envision extensions of these results to deeper ReLU networks, using notations and concepts from [27] that generalize observations from 3 to deep ReLU networks with biases. Given a feedforward network architecture of arbitrary depth, denote \(\theta\) the collection of all parameters (weights and biases) of a ReLU network on this architecture, and consider \(\theta\mapsto \phi_{\mathtt{ReLU}}(\theta)\) the rescaling-invariant polynomial function of [27] and \(C_{\theta,x}\), the matrices of [27] such that the output of the network with parameters \(\theta\), when fed with an input vector \(x \in \mathbb{R}^m\), can be written \(g(\theta,x) = C_{\theta,x} \phi(\theta)\). From its definition in [27], given \(x\), the matrix \(C_{\theta,x}\) only depends on \(\theta\) via the so-called activation status of the neurons in the network (cf [27]).
Lemma 6. Given \(\theta\in \Theta\), if for a given \(i\), \(\mathrm{dim}(W_{i+1}(\theta')) = \mathrm{dim}( W_i(\theta))\) for every \(\theta'\) in a neighborhood of \(\theta\), then for all \(k \geq i\), we have \(W_k(\theta')= W_i (\theta')\) for all \(\theta'\) in a neighborhood \(\Omega\) of \(\theta\), where the \(W_i\) are defined by 6. Thus \(\mathrm{Lie}(W)(\theta')= W_i (\theta')\) for all \(\theta' \in \Omega\). In particular, the dimension of the trace of \(\mathrm{Lie}(W)\) is locally constant and equal to the dimension of \(W_i(\theta)\).
Proof. The result is obvious for \(k=i\). The proof is by induction on \(k\) starting from \(k=i+1\). We denote \(m:= \dim (W_i(\theta))\).
1st step: Initialization \(k=i+1\). By definition of the spaces \(W_i\) (cf 6) we have \(W_i \subset W_{i+1}\) hence \(W_i(\theta) \subseteq W_{i+1}(\theta)\). Since \(\mathrm{dim}(W_{i+1} (\theta)) = \mathrm{dim}(W_i (\theta)) = m\), it follows that there exists \(\chi_1, \cdots, \chi_m \in W_i\) such that \(\underset{j}{\mathrm{span}} \chi_j(\theta) = W_i(\theta) = W_{i+1}(\theta)\) (hence the \(m\) vectors \((\chi_1(\theta), \cdots, \chi_m(\theta))\) are linearly independent). Since each \(\chi_j\) is smooth, it follows that \((\chi_1(\theta'), \cdots \chi_m(\theta'))\) remain linearly independent on some neighborhood \(\Omega\) of \(\theta\), which we assume to be small enough to ensure \(\dim W_{i+1}(\theta') = m\) for all \(\theta' \in \Omega\). As \(\chi_j \in W_i \subset W_{i+1}\), we obtain that for each \(\theta' \in \Omega\), the family \(\{\chi_j(\theta')\}_{j=1}^m\) is a basis of the \(m\)-dimensional subspace \(W_{i+1}(\theta')\), hence: \[\label{initialization} W_i(\theta') \subset W_{i+1} (\theta') = \mathrm{span}_j {\chi_j(\theta')} \subset W_i(\theta'), \quad \forall \theta' \in \Omega\tag{14}\] 2nd step: Induction. We assume \(W_k(\theta') = W_i(\theta')\) on \(\Omega\). Let us show that \(W_{k+1}(\theta') = W_i (\theta')\) on \(\Omega\). Since \(W_{k+1} \mathrel{\vcenter{:}}= W_k + [W_0, W_k]\) it is enough to show that \([W_0, W_k](\theta') \subseteq W_i(\theta')\) on \(\Omega\). For this, considering two vector fields, \(f \in W_0\) and \(\chi \in {W_k}\), we will show that \([f, \chi](\theta') \in W_{i+1}(\theta')\) for each \(\theta' \in \Omega\). In light of 14 , this will allow us to conclude.
Indeed, from the induction hypothesis we know that \(W_{k} (\theta') = \mathrm{span}_j \chi_j(\theta') = W_i(\theta')\) on \(\Omega\), hence for each \(\theta' \in \Omega\) there are coefficients \(a_j(\theta')\) such that \(\chi(\theta') = \sum_{j=1}^{m} a_j(\theta') \chi_j(\theta')\). Standard linear algebra shows that these coefficients depend smoothly on \(\chi(\theta')\) and \(\chi_j(\theta')\), which are smooth functions of \(\theta'\), hence the functions \(a_j(\cdot)\) are smooth. By linearity of the Lie bracket and of \(W_{i+1}(\theta')\) it is enough to show that \([f,a_j\chi_j](\theta') \in W_{i+1}(\theta')\) on \(\Omega\) for each \(j\). Standard calculus yields
\[\begin{align} [f,a_j\chi_j] &= (\partial f) (a_j \chi_j) - \underbrace{\partial (a_j\chi_j)}_{=\chi_j \partial a_j+a_j\partial \chi_j} f = a_j [(\partial f) \chi_j-(\partial \chi_j)f]-\chi_j (\partial a_j)f\\ &= a_j [f,\chi_j] - [(\partial a_j)f] \chi_j \end{align}\] since \((\partial a_j) f\) is scalar-valued (consider the corresponding dimensions). Since \(f \in W_0\) and \(\chi_j \in W_i\), by definition of \(W_{i+1}\) (cf 6) we have \([f,\chi_j],\chi_j \in W_{i+1}\) hence by linearity we conclude that \([f,a_j\chi_j](\theta') \in W_{i+1}(\theta')\). As this holds for all \(j\), we obtain \([f,\chi](\theta') \in W_{i+1}(\theta')\). As this is valid for any \(f \in W_0\), \(\chi \in W_k\) this establishes \([W_0,W_k](\theta') \subseteq W_{i+1}(\theta')\stackrel{\eqref{initialization}}{=}W_i(\theta')\) and we conclude as claimed that \(W_i(\theta') \subseteq W_{k+1}(\theta')= W_k(\theta')+[W_0,W_k](\theta') \subseteq W_i(\theta')\) on \(\Omega\). ◻
We recall first the fundamental result of Frobenius using our notations (See Section 1.4 of [32]). When we refer to a “non-singular distribution”, it implies that the dimension of the associated trace remains constant (refer to the definition of “non-singular” on page 15 of [32]). Being “involutively consistent” directly relates to our second assertion using the Lie bracket (see equation 1.13 on page 17 of [32]). Lastly, “completely integrable” aligns with our first assertion regarding orthogonality conditions (refer to equation 1.16 on page 23 of [32]).
Theorem 17 (Frobenius theorem). Consider \(W \subseteq \mathcal{X}(\Omega)\), and assume that the dimension of \(W(\theta)\) is constant on \(\Omega\subseteq \mathbb{R}^D\). Then the two following assertions are equivalent:
each \(\theta\in \Omega\) admits a neighborhood \(\Omega'\) such that there exists \(D-\mathrm{dim}(W(\theta))\) independent conserved functions through \(W_{|\Omega'}\);
the following property holds: \[\quad \quad [u,v](\theta) \in W(\theta),\quad \text{for each}\; u, v \in W,\;\theta\in \Omega \label{eq:frob-crochets-app}\tag{15}\]
Proposition 18. Under the assumption that \(\mathrm{dim}(W(\theta))\) is locally constant on \(\Omega\), Condition 15 of Frobenius Theorem holds if, and only if, the linear space \(W' \mathrel{\vcenter{:}}= \{ \chi \in \mathcal{X}(\Omega), \forall \theta\in \Omega: \chi(\theta) \in W(\theta) \}\) (which is a priori infinite-dimensional) is a Lie algebra.
Proof. \(\Leftarrow\) If \(W'\) is a Lie algebra, then as \(W \subset W'\) we get: for all \(u, v \in W \subset W', [u, v] \in W'\). Given the definition of \(W'\) this means that 15 is satisfied.
\(\Rightarrow\) Assuming now that 15 holds, we prove that \(W'\) is a Lie algebra. For this, given \(X, Y \in W'\) we wish to show that \([X,Y](\theta) \in W(\theta)\) for every \(\theta\in \Omega\).
Given \(\theta\in \Omega\), we first reason as in the first step of the proof of 2 to obtain the existence of a neighborhood \(\Omega'\) of \(\theta\) and of \(m \mathrel{\vcenter{:}}= \mathrm{dim}(W(\theta'))\) vector fields \(\chi_1, \cdots, \chi_m \in W\) such that \((\chi_1(\theta'), \cdots, \chi_m(\theta'))\) is a basis of \(W(\theta')\) for each \(\theta' \in \Omega\). By definition of \(W'\) we have \(X(\theta') \in W(\theta')\) and \(Y(\theta') \in W(\theta')\) for every \(\theta' \in \Omega'\). Thus, there are smooth functions \(a_j,b_j\) such that \(X(\cdot) = \sum_{1}^{m} a_i(\cdot) \chi_i(\cdot)\) and \(Y(\cdot) = \sum_{1}^{m} b_i(\cdot) \chi_i(\cdot)\) on \(\Omega'\), and we deduce by bilinearity of the Lie brackets that \([X, Y](\theta') = \sum_{i, j} [a_i \chi_i, b_j \chi_j](\theta')\) on \(\Omega'\). Since \(W(\theta)\) is a linear space, we will conclude that \([X,Y](\theta) \in W(\theta)\) if we can show that \([a_i \chi_i, b_j \chi_j](\theta) \in W(\theta)\). Indeed, we can compute \[\begin{align} [a_i \chi_i, b_j \chi_j] &= a_ib_j [\chi_i, \chi_j] + b_j [(\partial a_i) \chi_j] \chi_i - a_i [(\partial b_j) \chi_i] \chi_j \end{align}\] where, due to dimensions, both \((\partial a_i) \chi_j\) and \((\partial b_j) \chi_i\) are smooth scalar-valued functions. By construction of the basis \(\{\chi_j\}_j\) we have \(\chi_i(\theta), \chi_j(\theta) \in W(\theta)\), and by assumption 15 we have \([\chi_i, \chi_j](\theta) \in W(\theta)\), hence we conclude that \([X, Y](\theta) \in W(\theta)\). Since this holds for any choice of \(X,Y \in W'\), this establishes that \(W'\) is a Lie algebra. ◻
Theorem 19. If \(\mathrm{dim}(\mathrm{Lie}(W_\phi)(\theta))\) is locally constant then each \(\theta\in \Omega\) has a neighborhood \(\Omega'\) such that there are \(D-\mathrm{dim}(\mathrm{Lie}(W_\phi)(\theta))\) (and no more) independent conserved functions through \({W_\phi}_{|\Omega'}\).
Proof. 1st step: Existence of \(\Omega'\) and of \(D-\mathrm{dim}(\mathrm{Lie}(W_\phi)(\theta))\) independent conserved functions. Let \(\theta\in \Omega\). Since \(\mathrm{dim}(\mathrm{Lie}(W_\phi)(\theta))\) is locally constant there is a neighborhood \(\Omega''\) of \(\theta\) on which it is constant. Since \(W \mathrel{\vcenter{:}}=\mathrm{Lie}(W_\phi)_{\mid \Omega''} \subseteq \mathcal{X}(\Omega'')\) is a Lie Algebra, by 18 and Frobenius theorem (17) there exists a neighborhood \(\Omega' \subseteq \Omega''\) of \(\theta\) and \(D-\mathrm{dim}(W(\theta))\) independent conserved functions through \(W_{\mid \Omega'}\). As \(W_\phi \subset \mathrm{Lie}(W_\phi)\), these functions are (locally) conserved through \(W_\phi\) too. We only need to show that there are no more conserved functions.
2nd step: There are no more conserved functions. By contradiction, assume there exists \(\theta_0 \in \Omega\), an open neighborhood \(\Omega'\) of \(\theta_0\), a dimension \(k < \mathrm{dim}(\mathrm{Lie}(W_\phi)(\theta_0))\), and a collection of \(D-k\) independent conserved functions through \(W_\phi\), gathered as the coordinates of a vector-valued function \(h \in \mathcal{C}^1(\Omega', \mathbb{R}^{D-k})\). Consider \(W \mathrel{\vcenter{:}}= \{ X \in \mathcal{X}(\Omega'), \forall \theta\in \Omega', X(\theta) \in \mathrm{ker} \partial h(\theta) \}\). By the definition of independent conserved functions, the rows of the \((D-k) \times D\) Jacobian matrix \(\partial h(\theta)\) are linearly independent on \(\Omega'\), and the dimension of \(W(\theta) = \mathrm{ker}\partial h(\theta)\) is constant and equal to \(k\) on \(\Omega'\). By construction of \(W\) and 1, the \(D-k\) coordinate functions of \(h\) are independent conserved functions through \(W\). Thus, by Frobenius Theorem (17) and Proposition 18, \(W\) is a Lie algebra. By 1 we have \(W_\phi (\theta) = \mathrm{range}\partial \phi(\theta)^\top\subset \mathrm{ker} \partial h(\theta)\) on \(\Omega'\), hence \({W_\phi}_{|\Omega'} \subset W\), and therefore \(\mathrm{Lie}(W_\phi)_{|\Omega'} = \mathrm{Lie}({W_\phi}_{|\Omega'}) \subset W\). In particular: \(\mathrm{Lie}(W_\phi)(\theta_0) \subset W(\theta_0)\), which leads to the claimed contradiction that \(\mathrm{dim}(\mathrm{Lie}(W_\phi)(\theta_0)) \leq \mathrm{dim}(W(\theta_0)) = k\). ◻
Proposition 20. Consider \(\theta= (U,V) \in \mathbb{R}^{n\times r} \times \mathbb{R}^{m \times r}\), \(\phi\), and \(\Omega \subseteq \mathbb{R}^D\), \(D = (n+m)r\), as in 5. The dimension of \(W_\phi(\theta)\) is constant and equal to \((n+m-1)r\) and \(W_\phi\) verifies condition 11 of Frobenius Theorem (i.e. condition 15 of 17).
Proof. Denoting \(u_i\) (resp. \(v_i\)) the columns of \(U\) (resp. of \(V\)), for \(\theta\in \Omega\) we can write \(\phi(\theta) = (\psi(u_i, v_i))_{i = 1, \cdots r}\) with \(\psi: (u \in \mathbb{R}^n - \{0\}, v \in \mathbb{R}^m - \{ 0 \}) \mapsto uv^\top \in \mathbb{R}^{n\times m}\). As this decouples \(\phi\) into \(r\) functions each depending on a separate block of coordinates, Jacobian matrices and Hessian matrices are block-diagonal. Establishing condition 15 of Frobenius theorem is thus equivalent to showing it for each block, which can be done by dealing with the case \(r=1\). Similarly, \(W_\phi(\theta)\) is a direct sum of the spaces associated to each block, hence it is enough to treat the case \(r=1\) (by proving that the dimension is \(n+m-1\)) to obtain that for any \(r \geq 1\) the dimension is \(r(n+m-1)\).
1st step: We show that \(W_\phi\) satisfies condition 15 of Frobenius Theorem. For \(u \in \mathbb{R}^n - \{0\}\), \(v \in \mathbb{R}^m - \{0\}\) we write \(\theta= (u;v) \in \mathbb{R}^D= \mathbb{R}^{n+m}\) and \(\phi_{i, j} (\theta) \mathrel{\vcenter{:}}= u_i v_j\) for \(i = 1, \cdots, n\) and \(j = 1, \cdots, m\). Now \(u_i\) and \(v_j\) are scalars (and no longer columns of \(U\) and \(V\)). Denoting \(e_i\in \mathbb{R}^D= \mathbb{R}^{n +m}\) the vector such that all its coordinates are null except the \(i\)-th one, we have: \[\begin{align} \nabla \phi_{i, j}(\theta) &= v_j e_i + u_i e_{n + j} \in \mathbb{R}^D,\\ \partial ^{2} \phi_{i, j}(\theta) &= E_{j+n, i} + E_{i, j + n} \in \mathbb{R}^{D \times D}, \end{align}\] with \(E_{i, j} \in \mathbb{R}^{ D \times D}\) the one-hot matrix with the \((i, j)\)-th entry being \(1\). Let \(i, k \in \{1, \cdots, n \}\) and \(j, l \in \{1, \cdots, m \}\).
1st case: \((i, j) = (k, l)\) Then trivially \(\partial ^{2} \phi_{i, j} (\theta) \nabla \phi_{k, l} (\theta) - \partial ^{2} \phi_{k, l} (\theta) \nabla \phi_{i, j}(\theta) =
0.\)
2nd case: \(( (i \neq k)\) and \((j \neq l))\) Then \[[\nabla \phi_{i, j}, \nabla \phi_{k, l}](\theta) = (E_{j+n, i} + E_{i, j + n}) (v_l e_k + u_k e_{n +
l}) - (E_{l+n, k} + E_{k, l + n}) (v_j e_i + u_i e_{n + j}) = 0 - 0.\] 3d case: \(i = k\) and \(j \neq l\). Then as \(u \neq 0\), there
exists \(l' \in \{1, \cdots, n \}\) such that \(u_{l'} \neq 0\). \[\begin{align}
\partial ^{2} \phi_{i, j} (\theta) \nabla \phi_{k, l} (\theta) - \partial ^{2} \phi_{k, l} (\theta) \nabla \phi_{i, j}(\theta)
&= v_l e_{n + j} - v_j e_{n +l} \\
&= \frac{v_l}{u_{l'}} \nabla \phi_{l', j} (\theta) - \frac{v_j}{u_{l'}} \nabla \phi_{l', l} (\theta), \\
&\in \text{span} \{ \nabla \phi_{i, j} (\theta) \} = W_\phi(\theta).
\end{align}\] 4d case: (\((i \neq k)\) and \((j = l)\)) We treat this case in the exact same way than the 3d case.
Thus \(W_\phi\) verifies condition 11 of Frobenius Theorem.
2d step: We show that \(\mathrm{dim}(W_\phi (\theta) )= (n + m -1)\). As \(u, v \neq 0\) each of these vectors has at least one nonzero entry. For simplicity of notation, and without loss of generality, we assume that \(u_1 \neq 0\) and \(v_1 \neq 0\). It is straightforward to check that \((\nabla \phi_{1, 1} (\theta), (\nabla \phi_{1, j}(\theta))_{j =2, \cdots, m}, (\nabla \phi_{i, 1}(\theta))_{i =2, \cdots, n })\) are \(n+m-1\) linearly independent vectors. To show that \(\mathrm{dim}(W_\phi (\theta)) = (n + m -1)\) is it thus sufficient to show that they span \(W_\phi(\theta)\). This is a direct consequence of the fact that, for any \(i, j\), we have \[\begin{align} \nabla \phi_{i, j} (\theta) = v_j e_i + u_i e_{n + j} &= \frac{v_j}{v_1} (v_1 e_i + u_i e_{n +1}) + \frac{u_i}{u_1}(u_1 e_{n + j} + v_j e_1) - \frac{v_j u_i}{u_1 v_1} \left(u_1 e_{n +1} + v_1 e_1 \right), \\ &= \frac{v_j}{v_1} \nabla \phi_{i, 1}(\theta) + \frac{u_i}{u_1} \nabla \phi_{1, j}(\theta) + \frac{v_j u_i}{u_1 v_1} \nabla \phi_{1, 1}(\theta). \qedhere \end{align}\] ◻
In complement to 5, we give a simple example studying a two-layer network with a positively homogeneous activation function, which include the ReLU but also variants such as the leaky ReLU or linear networks.
Example 8 (Beyond ReLU: Neural network with one hidden neuron with a positively homogeneous activation function of degree one). Let \(\sigma\) be a positively one-homogeneous activation function. In 6 , this corresponds to setting \(g(\theta,x) = \sum_{i=1}^r u_i \sigma( \langle v_i, x\rangle ) \in \mathbb{R}\). Assuming \(\langle v_i, x\rangle \neq 0\) for all \(i\) to avoid the issue of potential non-differentiability at \(0\) of \(\sigma\) (for instance for the ReLU), and in particular assuming \(v_i \neq 0\), the function minimized during training can be factored via \(\phi(\theta) = (\psi(u_i,v_i))_{i=1}^r\) where \[\label{paramNN} \theta\mathrel{\vcenter{:}}= (u \in \mathbb{R}, v \in \mathbb{R}^{d-1}-\{0 \}) \overset{\psi}{\mapsto} (u \|v\|, v/ \|v\|) \in \mathbb{R}\times \mathcal{S}_{d-1} \subset \mathbb{R}^{d}.\tag{16}\]
Proposition 21. Consider \(d \geq 2\) and \(\phi(\theta) = (\psi(u_i,v_i))_{i=1}^r\) where \(\psi\) is given by 16 on \(\Omega\mathrel{\vcenter{:}}= \{\theta= (u \in \mathbb{R}^r,V = (v_1,\ldots,v_r) \in \mathbb{R}^{m \times r}): v_i \neq 0\}\). We have \(\mathrm{dim}(W_\phi(\theta)) = r(d-1)\) and \(W_\phi\) verifies condition 15 of Frobenius Theorem (17), so each \(\theta=(u, V) \in \Omega\) admits a neighborhood \(\Omega'\) such that there exists \(r\) (and no more) conserved function through \({W_\phi}_{|\Omega'}\).
As in 5, such candidate functions are given by \(h_i: (u_i, v_i) \mapsto u_i^2 - \|v_i\|^2\). A posteriori, these functions are in fact conserved through all \(W_\phi\).
Proof of 21. As in the proof of 20 it is enough to prove the result for \(r = 1\) hidden neuron. Note that here \(D = d\). To simplify notations, we define \(\phi_0, ..., \phi_{d-1}\) for \(\theta= (u,v)\) as: \[\phi_0(\theta) = u \| v \|,\] and for \(i = 1, ..., d-1\): \[\phi_i(\theta) = v_i/ \| v \|.\]
1st step: explicitation of \(\text{span} \{ \nabla \phi_0, ..., \nabla \phi_{d-1}\}\). We have \[\partial \phi(\theta) = \begin{pmatrix} \|v \| & \vline& uv^\top / \|v \| \quad \\ \hline 0_{(d-1) \times 1} & \vline& \begin{matrix} & \\ \frac{1}{\|v\|} P_v\\ & \end{matrix} \end{pmatrix},\] where: \(P_v := \mathrm{I}_{d-1} - v v^\top / \| v \|^2\) is the orthogonal projector on \((\mathbb{R}v)^{\perp}\) (seen here as a subset of \(\mathbb{R}^{d-1}\)) and its rank is \(d-2\). Thus \(\mathrm{dim}(W_\phi(\theta)) = \mathtt{rank}(\partial \phi(\theta))=d-1\) and \(\text{span} \{ \nabla \phi_0, ..., \nabla \phi_{d-1}\} = \mathbb{R}\nabla \phi_0 + (\mathbb{R}v)^{\perp}\).
2d step: calculation of the Hessians.
1st case: The Hessian of \(\phi_i\) for \(i \geq 1\). In this case, \(\phi_i\) does not depend on the first coordinate \(u\) so we proceed as if the ambient space here was \(\mathbb{R}^{d-1}\). We have already that for \(i \geq 1\): \[\nabla \phi_i(\theta) = e_i / \| v \| - v_i v / {\| v \|}^3\] hence \[\partial ^{2} \phi_i = 3 v_i v v^\top / {\| v \|}^5 - 1 / {\| v \|}^3 \left( v_i \mathrm{I}_{d-1} + V_i + V_i^\top \right),\] where all columns of matrix \(V_i := (0, ..., v, 0, ...,0)\) are zero except the \(i\)-th one, which is set to \(v\).
2d case: The Hessian of \(\phi_0\). Since \[\nabla \phi_0 (\theta) = {\left(\| v \|, u v^\top/ \| v \| \right)}^\top.\] we have \[\partial^2 \phi_0(\theta) = \begin{pmatrix} 0 & \vline& v^\top / \|v \| \quad \\ \hline v / \|v \| & \vline& \begin{matrix} & \\ \frac{u}{\|v\|} P_v \\ & \end{matrix} \end{pmatrix}.\]
3rd step: Conclusion.
1st case: \(i, j \geq 1\) and \(i \neq j\). We have: \[\begin{align} &\partial ^{2} \phi_i(\theta) \nabla \phi_j (\theta)- \partial ^{2} \phi_j(\theta) \nabla \phi_i(\theta), \\ &=v_j / {\|v\|}^4 e_i - v_i/ {\|v\|}^4 e_j \in (\mathbb{R}v)^{\perp},\\ &\subset \text{span} \{ \nabla \phi_0(\theta), ..., \nabla \phi_{d-1}(\theta)\}. \end{align}\]
2d case: \(i \geq 1\) and \(j=0\). We have: \[\begin{align} &\partial ^{2} \phi_i (\theta)\nabla \phi_0 (\theta)- \partial ^{2} \phi_0 (\theta)\nabla \phi_i (\theta), \\ &= -2 u / {\|v\|} \nabla \phi_i (\theta), \\ &\in \text{span} \{ \nabla \phi_0(\theta), ..., \nabla \phi_{d-1} (\theta)\}.\qedhere \end{align}\] In both cases, we obtain as claimed that the condition 15 of Frobenius Theorem is satisfied, and we conclude using the latter. ◻
Proposition 22. Assume that \(\mathtt{rank}(\partial \phi(\theta))\) is constant on \(\Omega\) and that \(W_\phi\) satisfies 11 . If \(t \mapsto \theta(t)\) satisfies the ODE 2 then there is \(0< T^\star_{\theta_{\mathtt{init}}}<T_{\theta_{\mathtt{init}}}\) such that \(z(t) \mathrel{\vcenter{:}}= \phi(\theta(t)) \in \mathbb{R}^d\) satisfies the ODE \[\label{transfertGF-app} \left\{ \begin{array}{ll} \overset{.}{z}(t) &= -M(z(t), \theta_{\text{init}}) \nabla f(z(t)) \quad for all0 \leq t < T^\star_{\theta_{\mathtt{init}}}, \\ z(0) &= \phi(\theta_{\text{init}}), \end{array} \right.\qquad{(3)}\] where \(M(z(t),\theta_{\text{init}}) \in \mathbb{R}^{d \times d }\) is a symmetric positive semi-definite matrix.
Proof. As \(z = \phi(\theta)\) and as \(\theta\) satisfies 2 , we have: \[\begin{align} \overset{.}{z} = \partial \phi (\theta) \overset{.}{\theta} &= - \partial \phi (\theta) \nabla (f\circ \phi)(\theta) = - \partial \phi (\theta) [\partial \phi(\theta)]^\top \nabla f (z). \end{align}\] Thus, we only need to show \(M(t) \mathrel{\vcenter{:}}= \partial \phi (\theta(t)) [\partial \phi(\theta(t))]^\top\), which is a symmetric, positive semi-definite \(d \times d\) matrix, only depends on \(z(t)\) and \(\theta_{\text{init}}\). Since \(\dim W_\phi(\theta)=\mathtt{rank}(\partial \phi(\theta))\) is constant on \(\Omega\) and \(W_\phi\) satisfies 11 , by Frobenius Theorem (17), for each \(\theta\in \Omega\), there exists a neighborhood \(\Omega_1\) of \(\theta\) and \(D-d'\) independent conserved functions \(h_{d'+1}, \cdots, h_{D}\) through \((W_\phi)_{|\Omega'}\), with \(d' := \dim W_\phi(\theta) = \mathtt{rank}(\partial\phi(\theta))\). Moreover, by definition of the rank, for the considered \(\theta\), there exists a set \(I \subset \{1,\ldots,d\}\) of \(d'\) indices such that the gradient vectors \(\nabla \phi_i(\theta)\), \(i \in I\) are linearly independent. By continuity, they stay linearly independent on a neighborhood \(\Omega_2\) of \(\theta\). Let us denote \(P_I\) the restriction to the selected indices and \[\theta' \in \mathbb{R}^D\longmapsto \Phi_I(\theta') \mathrel{\vcenter{:}}= ( P_I\phi(\theta'), h_{d'+1}(\theta'), ..., h_{D}(\theta')) \in \mathbb{R}^D\] As the functions \(h_i\) are independent conserved functions, for each \(\theta' \in \Omega' \mathrel{\vcenter{:}}= \Omega_1 \cap \Omega_2\) their gradients \(\nabla h_i(\theta')\), \(d'+1 \leq i \leq D\) are both linearly independent and (by 1 and 7 ) orthogonal to \(W_\phi(\theta') = \mathrm{range}[\partial \phi(\theta')]^\top = \mathrm{span}\{\nabla \phi_i(\theta): i \in I\}\). Hence, on \(\Omega'\), the Jacobian \(\partial \Phi_I\) is an invertible \(D \times D\) matrix. By the implicit function theorem, the function \(\Phi_I\) is thus locally invertible. Applying this analysis to \(\theta= \theta(0)\) and using that \(h_i\) are conserved functions, we obtain that in an interval \([0,T^\star_{\theta_{\mathtt{init}}})\) we have \[\label{dep} \Phi_I(\theta(t)) = (P_I z(t), h_{d+1}(\theta_{\text{init}}), ..., h_{D}(\theta_{\text{init}}))\tag{17}\] By local inversion of \(\Phi_I\) this allows to express \(\theta(t)\) (and therefore also \(M(t) = \partial \phi(\theta(t)) [\partial \phi(\theta(t))]^\top\)) as a function of \(z(t)\) and of the initialization. ◻
In complement to 7 we provide another example related to 8.
Example 9. Given the reparametrization \(\phi: (u \in \mathbb{R}, v \in \mathbb{R}^{d-1}-\{0 \}) \mapsto (u \|v\| , v/ \|v\|) \in \mathbb{R}\times \mathcal{S}_{d-1} \subset \mathbb{R}^d\) (cf 16 ), the variable \(z \mathrel{\vcenter{:}}= (r, h) = (u \|v\| , v/ \|v\|)\) satisfies ?? with: \(M(z, \theta_{\text{init}})~=~\begin{pmatrix} \sqrt{r^2 + \delta^2} & \vline& \quad 0_{1 \times k} \quad \\ \hline 0_{(d-1) \times 1} & \vline& \begin{matrix} & \\ \frac{1}{\delta + \sqrt{r^2 + \delta^2}} P_h \\ & \end{matrix} \end{pmatrix},\) where \(P_h := \mathrm{I}_{d-1} - h h^T / \| h \|^2\) and \(\delta \mathrel{\vcenter{:}}= u_{\text{init}}^2-\| v _{\text{init}} \|^2\).
Proposition 23. Consider \(\Psi: (U, V) \mapsto U^\top U - V^\top V \in \mathbb{R}^{r \times r}\) and assume that \((U; V)\) has full rank. Then:
if \(n+m \leq r\), the function \(\Psi\) gives \((n+m)(r-1/2(n+m-1))\) independent conserved functions,
if \(n+m > r\), the function \(\Psi\) gives \(r(r+1)/2\) independent conserved functions.
Proof. Let write \(U = (U_1; \cdots; U_r)\) and \(V= (V_1; \cdots;V_r)\) then: \(\Psi_{i, j}(U, V) = \langle U_i, U_j \rangle - \langle V_i, V_j \rangle\) for \(i, j = 1, \cdots, r\). Then \(f_{i, j} \mathrel{\vcenter{:}}= \nabla \Psi_{i, j} (U, V) = (0; \cdots; 0; \underset{(i)}{U_j}; \cdots; \underset{(j)}{U_i}; 0; \cdots; \underset{(i+r)}{-V_j}; \cdots; \underset{(j+r)}{-V_i}; \cdots; 0)^\top \in \mathbb{R}^{(n+m)r \times 1}\).
1st case: \(n+m \leq r\). As \((U; V)\) has full rank, its rank is \(n+m\). Thus, by elementary operations, \((U;-V)\) has full rank \((n+m)\) too. Let us note \((U; -V) = (w_1, \cdots, w_r)\). Without loss of generality we can assume that its \((n+m)\) first columns \(w_1, \cdots, w_{(n+m)}\) are linearly independent. Now we want to count the number of \(f_{i,j}\) that are linearly independent.
if \(i\in [\![ 1, n+m ]\!]\) and if \(i \leq j \leq r\), then let us show that all the associated \(f_{i, j}\) are linearly independent together. There are \((n+m)(n+m+1)/2 + (n+m)(r-(n+m))\) such functions. Indeed, let us assume that there exists \((\lambda_{i, j})_{i, j}\) such that \(\sum_{1 \leq i \leq j \leq n+m} \lambda_{i, j} f_{i, j} = 0\). Let \(j_0 \in [\![ 1, r ]\!]\). By looking this sum at the restriction on the coordinates \([\![ n j_0, n (j_0 +1 ) ]\!] \cup [\![ nr + m j_0, nr + m (j_0 +1) ]\!]\), we obtain: \[\sum_{i \leq \max(j_0, n+m)} \lambda_{i, j_0} w_i = 0.\] Then by independence of \(w_1, \cdots, w_{n+m}\), \(\lambda_{i, j_0} = 0\) for all \(i \leq \max(j_0, n+m)\), and for all \(j_0 \leq r\). Thus all these \(f_{i, j}\) are linearly independent.
if \(i\leq j \in [\![ n+m +1, r]\!]\), the associated \(f_{i, j}\) are linearly dependent of thus already obtained. Indeed as \(w_i\) and \(w_j\) are linear combinations of \(\{w_1, \cdots w_{n+m}\}\), there exists \((\alpha_j)_j \neq (0)\) and \((\beta_j)_j \neq (0)\) such that \(w_i = \sum_{k =1}^{n+m} \alpha_k w_k\) and \(w_j = \sum_{k=1}^{n+m} \beta_k w_k\). Then, one has: \[f_{i, j} = \sum_k \beta_k f_{k, i} + \sum_k \alpha_k f_{k, j} - \sum_{k, l} \alpha_k \beta_l f_{k, l}.\]
Finally there are exactly \((n+m)(r-1/2(n+m-1)\) independent conserved functions given by \(\Psi\).
2d case: \(n+m > r\). Then all \((U_i; -V_i)\) for \(i = 1, \cdots r\) are linearly independent. Then there are \(r(r+1)/2\) independent conserved functions given by \(\Psi\). ◻
Proposition 24. For every \(\Delta \in \mathbb{R}^{n \times m}\) denote \(S_{\Delta} \mathrel{\vcenter{:}}= \left(\begin{matrix} 0 & \Delta\\ \Delta^\top & 0 \end{matrix}\right),\) one has \(\partial \phi(U, V)^\top : \Delta \in \mathbb{R}^{n \times m} \mapsto S_\Delta \cdot (U; V).\) Hence \(W_\phi = \mathrm{span}\{A_{\Delta}, \forall \Delta \in \mathbb{R}^{n \times m} \}\), where \(A_{\Delta}: (U; V) \mapsto S_\Delta \cdot (U; V)\) is a linear endomorphism. Moreover one has \([A_{\Delta}, A_{\Delta'}]: (U, V) \mapsto [S_{\Delta}, S_{\Delta'}]\times(U; V).\)
This proposition enables the computation of the Lie brackets of \(W_\phi\) by computing the Lie bracket of matrices. In particular, \(\mathrm{Lie}(W_\phi)\) is necessarily of finite dimension.
Proposition 25. The Lie algebra \(\mathrm{Lie}(W_\phi)\) is equal to \[\left\{ (U; V) \mapsto \begin{pmatrix} \mathrm{I}_{n} & 0 \\ 0 & -\mathrm{I}_{m} \end{pmatrix} \times M \times \begin{pmatrix} U\\V \end{pmatrix} : M \in \mathcal{A}_{n+m} \right\}\] where \(\mathcal{A}_{n+m} \subset \mathbb{R}^{(n+m)\times (n+m)}\) is the space of skew symmetric matrices.
Remark 26. By the characterization of \(\mathrm{Lie}(W_\phi)\) in Proposition 25 we have that the dimension of \(\mathrm{Lie}(W_\phi)\) is equal to \((n+m)\times (n+m-1)/2.\)
Proof. 1st step: Let us characterize \(W_1 = \mathrm{span}\{W_\phi + [W_\phi, W_\phi] \}\). Let \(\Delta, \Delta' \in \mathbb{R}^{n \times m}\), then: \[\label{liebracketmatrix} [A_{\Delta}, A_{\Delta'}]((U, V)) = [S_{\Delta}, S_{\Delta'}] \times(U; V) = \begin{pmatrix} Y& 0 \\ 0& Z \end{pmatrix} \times \begin{pmatrix} U\\V \end{pmatrix},\tag{18}\] with \(Y \mathrel{\vcenter{:}}= \Delta \Delta'^\top - \Delta' \Delta^\top \in \mathcal{A}_n\) and \(Z \mathrel{\vcenter{:}}= \Delta^\top \Delta'- \Delta'^\top \Delta \in \mathcal{A}_m\). Then: \[\begin{align} W_1 &= \left\{ (U; V) \mapsto \begin{pmatrix} Y& X \\ X^\top& Z \end{pmatrix} \times \begin{pmatrix} U\\V \end{pmatrix}: X \in \mathbb{R}^{n \times m }, Y \in \mathcal{A}_{n}, Z \in \mathcal{A}_m \right\}, \\ &= \left\{ u_M \mathrel{\vcenter{:}}= (U; V) \mapsto \begin{pmatrix} \mathrm{I}_{n}& 0 \\ 0& -\mathrm{I}_{m} \end{pmatrix} \times M \times \begin{pmatrix} U\\V \end{pmatrix}: M \in \mathcal{A}_{n+m} \right\}. \end{align}\] 2d step: Let us show that \(W_2 = W_1\). Let \(M, M' \in \mathcal{A}_{n+m}\). Then: \[[u_M, u_{M'}] = \begin{pmatrix} \mathrm{I}_{n}& 0 \\ 0& -\mathrm{I}_{m} \end{pmatrix} \left(M \begin{pmatrix} \mathrm{I}_{n}&0 \\ 0& -\mathrm{I}_{m} \end{pmatrix} M' - M' \begin{pmatrix} \mathrm{I}_{n}&0 \\ 0& -\mathrm{I}_{m} \end{pmatrix} M\right) = \begin{pmatrix} \mathrm{I}_{n}& 0 \\ 0& -\mathrm{I}_{m} \end{pmatrix} \tilde{M},\] with \(\tilde{M} \mathrel{\vcenter{:}}= M \begin{pmatrix} \mathrm{I}_{n}& 0 \\ 0& -\mathrm{I}_{m} \end{pmatrix} M' - M' \begin{pmatrix} \mathrm{I}_{n}& 0 \\ 0& -\mathrm{I}_{m} \end{pmatrix} M \in \mathcal{A}_{n+m}\).
Finally: \(\mathrm{Lie}(W_\phi) = W_1 = \left\{ (U; V) \mapsto \begin{pmatrix} \mathrm{I}_{n}& 0 \\ 0& -\mathrm{I}_{m} \end{pmatrix} \times M \times \begin{pmatrix} U\\V \end{pmatrix}: M \in \mathcal{A}_{n+m} \right\}.\) ◻
Eventually, what we need to compute is the dimension of the trace \(\mathrm{Lie}(W_\phi) (U, V)\) for any \((U, V)\).
Proposition 27. Let us assume that \((U; V) \in \mathbb{R}^{(n+m) \times r}\) has full rank. Then:
if \(n+m \leq r\), then \(\mathrm{dim}(\mathrm{Lie}(W_\phi) (U; V)) = (n+m)(n+m-1)/2\);
if \(n+m > r\), then \(\mathrm{dim}(\mathrm{Lie}(W_\phi) (U; V)) = (n+m)r - r(r+1)/2\).
Proof. Let us consider the linear application: \[\Gamma: M \in \mathcal{A}_{n+m}\mapsto \begin{pmatrix} \mathrm{I}_{n}& 0 \\ 0& -\mathrm{I}_{m} \end{pmatrix} \times M \times \begin{pmatrix} U\\V \end{pmatrix},\] where \(\mathcal{A}_{n+m} \subset \mathbb{R}^{(n+m)^2}\) is the space of skew symmetric matrices. As \(\mathrm{range}\Gamma (\mathcal{A}_{n+m}) = \mathrm{Lie}(W_\phi)(U;V)\), we only want to calculate \(\textrm{rank} \Gamma ( \mathcal{A}_{n+m})\). But by rank–nullity theorem, we have: \[\mathrm{dim}\;\operatorname{ker}\;\Gamma + \operatorname{rank}\;\Gamma = (n+m)(n+m-1)/2.\] 1st case: \(n+m \leq r\). Then as \(\begin{pmatrix} \mathrm{I}_{n}& 0 \\ 0& -\mathrm{I}_{m} \end{pmatrix}\) is invertible and as \((U; V)\) has full rank \(n+m\), \(\Gamma\) is injective and then \(\textrm{rank} \Gamma ( \mathcal{A}_{n+m})= (n+m)(n+m-1)/2\).
2d case: \(n+m > r\). Since \(\begin{pmatrix} \mathrm{I}_{n}& 0 \\ 0& -\mathrm{I}_{m} \end{pmatrix}\) is invertible, \(\operatorname{ker}( \Gamma)\) is the set of matrices \(M \in \mathcal{A}_{n+m}\) such that \(M (U;V)=0\). Denote \(M_i\), \(1 \leq i \leq 2(n+m)\) the rows of such a matrix, so that \(M^\top = (M_1; \cdots; M_{2(n+m)})\). Denoting \(C_j\), \(1 \leq j \leq r\) the columns of \(\left(U; V\right)\) and \(\mathcal{C} \mathrel{\vcenter{:}}= \underset{j = 1, \cdots, r}{\mathrm{span}} C_j\), we observe that since \(\left(U; V\right)\) has full rank \(r = \min(m+n,r)\) the columns \(C_j\) are linearly independent and \(\mathrm{dim}\;\mathcal{C} = r\). Since \(M\times \left(U; V\right) = 0\), we have \(\langle M_i, C_j \rangle = 0\) for all \(1 \leq i \leq n+m\) and \(1 \leq j \leq r\), i.e., each \(M_i \in \mathbb{R}^{n+m}\) belongs to \(\mathcal{C}^\perp\), of dimension \(\mathrm{dim}\;\mathcal{C}^\perp = n+m-r\).
To determine \(\mathrm{dim}\;\operatorname{ker}(\Gamma)\) we now count the number of degrees of freedom to choose \(M \in \mathcal{A}_{n+m}\) such that \(M_i \in \mathcal{C}^\perp\) for every \(i\). We first show the following lemma.
Lemma 7. The matrix \(C \in \mathbb{R}^{(n+m) \times r}\) has full rank \(r\) if and only if there exists a subset \(T\) of \(n+m-r\) indices such that the horizontal concatenation \(\left(C, \mathrm{Id}_{T}\right)\) is invertible, where \(\mathrm{Id}_{T} \in \mathbb{R}^{(n+m) \times (n+m-r)}\) is the restriction of the identity matrix to its columns indexed by \(T\).
Proof. The converse implication is clear. Let us show the direct one. By denoting \(e_1, \cdots, e_{n+m}\) the canonical basis in \(\mathbb{R}^{n+m}\), there is \(i_1\) such that \(e_{i_1}\) is linearly independent from all \(C_j\): otherwise all \(e_i\) would be spanned by \(C_1, \cdots, C_r\), i.e. we would have \({\mathrm{span}} \{ e_i: 1 \leq i \leq n+m\}\subseteq \mathcal{C}\) hence \(n+m \leq r\), which contradicts our assumption. Similarly, by recursion, after finding \(i_1, \cdots, i_{k}\) for some \(k < n+m-r\) such that \(i_1, \cdots, i_k\) are linearly independent from \(C_1, \dots, C_r\) (so that \(\tilde{\mathcal{C}} \mathrel{\vcenter{:}}= {\mathrm{span}} \{\mathcal{C} , e_{i_l}: 1\leq l \leq k \}\) has dimension \(r+k < n+m\)), there exists \(i_{k+1}\) such that \(e_{i_{k+1}}\) is linearly independent from all \(C_j\) and all \(e_{i_1}, \cdots, e_{i_k}\). Stopping this construction when \(k = n+m-r\) yields \(T:= \{i_1,\ldots, i_k\}\). ◻
Consider the index set \(T = \{i_1, \cdots, i_{n+m-r} \}\) given by 7, so that \(\left(C, \mathrm{Id}_{T}\right) \in \mathbb{R}^{(n+m) \times (n+m)}\) is invertible.
We first build the column \(M_{i_1}\). The \(i_1\)-th coordinate of \(M_{i_1}\) is equal to \(0\) as \(M\) is a skew matrix, and its remaining \(n+m-1\) coordinates can be freely chosen provided that \(M_{i_1}\) belongs to \(\mathcal{C}^\perp\). Thus, \(M_{i_1}\) can be arbitrarily chosen in the space of dimension \(n+m-r-1\) defined by \[\left(C, e_{i_1}\right)^\top M_{i_1} = \begin{pmatrix} 0 \\ \cdots \\ 0 \\ 0 \end{pmatrix},\] where the matrix \(\left(C, e_{i_1}\right)^\top \in \mathbb{R}^{(r+1) \times (n+m)}\) has full rank \(r+1\) by contruction.
Then, the \(i_2\)-th coordinate of \(M_{i_2}\) is equal to \(0\), and its \(i_1\)-th coordinate is determined by \(M_{i_1}\) (and equal to the opposite of its \(i_2\)-th one) as \(M\) is a skew matrix. Its remaining \(n+m-2\) coordinates can be freely chosen provided that \(M_{i_2}\) belongs to \(\mathcal{C}^\perp\). Thus, \(M_{i_2}\) can be arbitrarily chosen in the affine space of dimension \(n+m-r-2\) defined by \[\left(C, e_{i_1}, e_{i_2}\right)^\top M_{i_2} = \begin{pmatrix} 0 \\ \cdots \\ 0 \\- M_{i_1}[i_2] \\ 0 \end{pmatrix},\] where the matrix \(\left(C, e_{i_1}, e_{i_2} \right)^\top \in \mathbb{R}^{(r+2) \times (n+m)}\) has full rank \(r+2\) by construction. By recursion, after building \(k\) columns \(M_{i_1}, \cdots, M_{i_k}\) with \(k < n+m-r\), the coordinates indexed by \(i_1, \cdots, i_k\) of the column \(M_{i_{k+1}}\) are determined by \(M_{i_1}, \cdots, M_{i_k}\) and its \(i_{k+1}\)-th coordinate is equal to zero to ensure that \(M\) is a skew matrix, and the remaining \(n+m-(k+1)\) coordinates must ensure that \(M_{i_{k+1}} \in \mathcal{C}^\perp\). Thus \(M_{i_{k+1}}\) can be arbitrarily chosen in the affine space of dimension \(n+m-r-(k+1)\) defined by \[\left(C, e_{i_1}, \cdots, e_{i_{k+1}} \right)^\top M_{i_{k+1}} = \begin{pmatrix} 0 \\ \cdots \\ 0 \\ -M_{i_1}[i_{k+1}] \\ \cdots \\ -M_{i_k} [i_{k+1}] \\0 \end{pmatrix},\] where the matrix \(\left(C, e_{i_1}, \cdots, e_{i_{k+1}} \right)^\top\in \mathbb{R}^{(r+k+1) \times (n+m)}\) has full rank \(r+k+1\) by construction. Finally the dimension of \(\mathrm{ker}(\Gamma)\) is equal to: \[\sum_{i=1}^{n+m-r}(n+m-r-i) = (n+m-r-1)(n+m-r)/2.\] Eventually we obtain \(\operatorname{rank}(\Gamma)= (n+m)r -r(r+1)/2\). ◻
Thanks to this explicit characterization of the trace of the generated Lie algebra, combined with 11, we conclude that 10 has indeed exhausted the list of independent conservation laws.
Corollary 3. If \((U; V)\) has full rank, then all conserved functions are given by \(\Psi: (U, V) \mapsto U^\top U - V^\top V\). In particular, there exist no more conserved functions.
Proof. As \((U;V)\) has full rank, this remains locally the case. By 12 the dimension of \(\mathrm{Lie}(W_\phi) (U;V)\) is locally constant, denoted \(m(U,V)\). By Theorem 7, the exact number of independent conserved functions is equal to \((n+m)r - m(U, V)\) and that number corresponds to the one given in Proposition 11. ◻
Proposition 28. Let us assume that \((U; V) \in \mathbb{R}^{(n+m) \times r}\) has full rank. If \(\max(n, m) > 1\) and \(r > 1\), then \(W_\phi\) does not satisfy the condition 11 .
Proof. Let us consider the linear application: \[\Gamma': \Delta \in \mathbb{R}^{n \times m} \mapsto \begin{pmatrix} 0 & \Delta \\ \Delta^\top & 0 \end{pmatrix} \times \begin{pmatrix} U\\V \end{pmatrix}.\] By 24, \(\mathrm{range}\Gamma' (\mathbb{R}^{n \times m}) = W_\phi(U;V)\). Thus, as by definition \(W_\phi(U;V) \subseteq \mathrm{Lie}(W_\phi (U;V))\), \(W_\phi\) does not satisfy the condition 11 if and only if \(\mathrm{dim}(W_\phi(U;V)) < \mathrm{dim}(\mathrm{Lie}W_\phi (U;V))\).
1st case: \(n+m \leq r\). Then as \((U; V)\) has full rank \(n+m\), \(\Gamma'\) is injective and then \(\textrm{rank} \Gamma' ( \mathbb{R}^{n \times m})= n \times m\).
Thus by 27, we only need to verify that: \(n\times m < (n+m)(n+m-1)/2 =: \mathrm{Lie}W_{\phi}(U;V)\). It is the case as \(\max(n, m) > 1\).
2d case: \(n+m > r\). We write \((U;V) = (C_1; \cdots; C_r)\) with \((C_1, \cdots, C_r)\) that are linearly independent as \((U; V)\) has full rank \(r\). Let \(\Delta \in \mathbb{R}^{n \times m}\) such that \(\Gamma'(\Delta) = 0\). Let us define the symmetric matrix \(M\) by: \[\label{form-m} M \mathrel{\vcenter{:}}= \begin{pmatrix} 0& \Delta \\ \Delta^\top& 0 \end{pmatrix}.\tag{19}\] Then \(M\cdot (U;V) = 0\). Then we write \(M^\top = (M_1; \cdots; M_{n+m})\). Then as \(M\times (U;V) = 0\), we have that \(\langle M_i, C_j \rangle = 0\) for all \(i = 1, \cdots, n+m\) and for all \(j = 1, \cdots, r\). We note \(C \mathrel{\vcenter{:}}= \underset{i = 1, \cdots, r}{\mathrm{span}} C_i\) that is of dimension \(r\) as \((U;V)\) has full rank \(r\).
For all \(i = 1, \cdots, n\), \(M_i\) must be in \(C^\perp\) and its \(n\) first coordinate must be zero by definition 19 . Then \(M_i\) lies in a space of dimension \(\max(0, n+m-r-n)\). For all \(j > n\), \(M_j\) are entirely determined by \(\{ M_i \}_{i \leq n}\) by definition 19 . Finally the dimension of \(\mathrm{ker} \Gamma'\) is equal to: \(n \times \max(0, m-r).\) Then: \(\mathrm{dim}(W_{\phi}(U; V)) = \textrm{rank} \Gamma' ( \mathbb{R}^{n \times m})= nm - n \times \max(0, m-r)\).
Thus by 27, we only need to verify that: \(nm - n\max(0, m-r) < (n+m)r - r(r+1)/2 =: \mathrm{Lie}W_{\phi}(U;V)\).
Let us assume \(m < r\). Then by looking at \(f(r) \mathrel{\vcenter{:}}= (n+m)r - r(r+1)/2 - nm = \mathrm{dim}(\mathrm{Lie}W_{\phi}(U;V)) - \mathrm{dim}(W_{\phi}(U;V))\) for \(r \in \{m+1, \cdots, n + m -1 \}=: I_{n, m}\), we have: \(f'(r) = (n+m) - 1/2 - r > 0\) (as \(n+m> r\) is an integer), so \(f\) is increasing, so on \(I_{n, m}\), we have (as \(r> m\)): \(f(r) > f(m) = (n+m)m - m(m+1)/2-nm = m^2 - m(m+1)/2 \geq 0\) as \(m \geq 1\).
Let us assume \(m \geq r\). Then \[\begin{align} \mathrm{dim}(\mathrm{Lie}W_{\phi}(U;V)) - \mathrm{dim}(W_{\phi}(U;V)) &= (n+m)r - r(r+1)/2 - (nm -n(m-r)), \\ &= mr - r(r+1)/2, \\ &\geq r^2 - r(r+1)/2 \quad \text{as } m\geq r, \\ &> 0 \quad \text{as } r > 1. \end{align}\] Thus \(\mathrm{dim}(\mathrm{Lie}W_{\phi}(U;V)) - \mathrm{dim}(W_{\phi}(U;V) )> 0\). ◻
We used the software SageMath [3] that relies on a Python interface. Computations were run in parallel using 64 cores on an academic HPC platform.
First we compared the dimension of the generated Lie algebra \(\mathrm{Lie}(W_{\phi})(\theta)\) (computed using the algorithm presented in [subsection-method]) with \(D-N\), where \(N\) is the number of independent conserved functions known by the literature (predicted by 10 for ReLU and linear neural networks). We tested both linear and ReLU architectures (with and without biases) of various depths and widths, and observed that the two numbers matched in all our examples.
For this, we draw \(50\) random ReLU (resp. linear) neural network architectures, with depth drawn uniformly at random between \(2\) to \(5\) and i.i.d. layer widths drawn uniformly at random between \(2\) to \(10\) (resp. between \(2\) to \(6\)). For ReLU architectures, the probability to include biases was \(1/2\).
Then we checked that all conservation laws can be explicitly computed using the algorithm presented in 2.5 and looking for polynomial solutions of degree \(2\) (as conservation laws already known by the literature are polynomials of degree \(2\)). As expected we found back all known conservation laws by choosing \(10\) random ReLU (resp. linear) neural network architectures with depth drawn uniformly at random between \(2\) to \(4\) and i.i.d. layer widths drawn uniformly at random between \(2\) to \(5\).