Self-Expanding Neural Networks
The results of training a neural network are heavily dependent on the
architecture chosen; and even a modification of only its size, however small,
typically involves restarting the training process. In contrast to this, we
begin training with a small architecture, only increase its capacity as
necessary for the problem, and avoid interfering with previous optimization
while doing so. We thereby introduce a natural gradient based approach which
intuitively expands both the width and depth of a neural network when this is
likely to substantially reduce the hypothetical converged training loss. We
prove an upper bound on the ``rate'' at which neurons are added, and a
computationally cheap lower bound on the expansion score. We illustrate the
benefits of such Self-Expanding Neural Networks with full connectivity and
convolutions in both classification and regression problems, including those
where the appropriate architecture size is substantially uncertain a priori.
Rupert Mitchell, Robin Menzenbach, Kristian Kersting, Martin Mundt
# Self-Expanding Neural Networks

###### Abstract

The results of training a neural network are heavily dependent on the architecture chosen; and even a modification of only the size of the network, however small, typically involves restarting the training process. In contrast to this, we begin training with a small architecture, only increase its capacity as necessary for the problem, and avoid interfering with previous optimization while doing so. We thereby introduce a natural gradient based approach which intuitively expands both the width and depth of a neural network when this is likely to substantially reduce the hypothetical converged training loss. We prove an upper bound on the "rate" at which neurons are added, and a computationally cheap lower bound on the expansion score. We illustrate the benefits of such Self-Expanding Neural Networks in both classification and regression problems, including those where the appropriate architecture size is substantially uncertain a priori.

## 1 Introduction

Correctly tailoring a model's capacity to an arbitrary task is extremely challenging, especially when the latter is not yet well studied. This challenge can be side stepped by choosing an architecture which is so large that a poor solution is nevertheless unlikely to occur [19], e.g. due to the double-descent phenomenon. However, since it is hard to predict what size would be large enough this will often in practice entail using a massively overparameterized network [22][12][11]. Surely it is possible to detect that the existing capacity of the network is insufficient and add more neurons when and where they are needed? In fact, biological neural networks are grown by adding new neurons to the existing network through the process of neurogenesis. The popular review [9] discusses the relatively recent discovery that this process is still active in the adult mammalian brain [23], and [13][5] identify it as a key ability underpinning lifelong learning. Thus inspired, we propose an analogous process for adding both neurons and layers to an artificial neural network during training, based on a local notion of "sufficient capacity" derived from first principles in close relation to the natural gradient [1][17].

Any method for artificial neurogenesis must answer three questions to avoid the problem of locally insufficient capacity [6]. It must determine **when** the current capacity is insufficient and that neuron(s) must therefore be added. It must identify **where** these neurons should be introduced. Finally, it must choose **what** initialization is appropriate for these neurons. These questions, if they are addressed at all in the literature, are normally addressed piecemeal or in ad-hoc ways. For example, very few methods address the question of **what**[6][26]. **When** is answered either by assuming predetermined schedules [26][21], or by waiting for the training loss to converge [27][25], neither of which are informative about **where**. "Whenever you party, hit, spring,..., you must cut the enemy in the same movement." 1 Our metaphorical enemy is not a loss which is momentarily poor, or even one which is
converging to a poor value: it is a deficiency in our parameterization such that the optimizer cannot make progress. We argue that by inspecting the degrees of freedom of the optimizer in function space, one may not only strike faster in answer to **when**, but answer **where** and **what** in the same stroke.

From a mathematical perspective, these degrees of freedom available to the optimizer are given by the image of the parameter space under the Jacobian, and the derivative with respect to the loss in function space will not in general lie in this subspace. It is however possible to project this derivative onto that subspace, and the natural gradient, \(\mathbf{F}^{-1}\mathbf{g}\), is exactly the change in parameters which changes the function according to this projection. In order to measure the size of that projection for a given parameterization, we introduce the natural expansion score \(\eta=\mathbf{g}^{T}\mathbf{F}^{-1}\mathbf{g}\). Specifically, the capacity of a neural network is locally insufficient when this score is small for the current parameterization. We therefore add neurons **when** this substantially increases \(\eta\), **where** they will maximally increase \(\eta\), and choose **what** initialization to use for the new parameters according to how it increases \(\eta\). To summarize, our **contributions** are:

1. We introduce the _natural expansion score_ which measures the increase in rate of loss reduction under natural gradient descent when width or depth is added to a neural network.
2. We show how such additions may be made during training without altering the function represented by the network. Our neurogenesis inspired Self-Expanding Neural Networks (SENN) thus avoid interfering with previous optimization or requiring restarts of training.
3. We prove that the number of neurons added simultaneously in SENN is bounded. We further introduce a computationally efficient approximation as a provable lower bound to increases in natural expansion score resulting from additions.
4. We demonstrate SENN's effectiveness for regression and classification.

In the remainder of this paper, we proceed as follows: In section 2 we summarize existing growth methods, in section 3 we then describe SENN, and in section 4 we illustrate its operation in practice.

## 2 Related Methods for Growing Neural Networks

The problem of adding nodes to neural networks during training has been under consideration for over 30 years (e.g. Dynamic Node Creation (DyNC) [2]), but remains substantially unsolved. There does not seem to exist a unified answer to **when**, **where** and **what**, as we summarize in table 1. Most methods cannot add depth and sideline at least one of these questions.

Inspired by neurogenesis like SENN, Draelos _et al._[5] examine the case of representational learning with stacked autoencoders, where they exploit local reconstruction error to determine **when** and **where** to add neurons. Due to their more general setting, DyNC, Progressive NNs (PrNNs) [21] and Dynamically Expandable NNs (DENNs) [27] use simple training loss convergence or even task boundaries to answer **when**, but must then fall back on ad-hoc preset decisions for **where**. (However, DENNs use subsequent pruning to mitigate the excess capacity introduced by the preset.) All four methods freeze old neurons or continue training from their present values, but randomly initialize new neurons in answer to **what**. While ActiveNAS [7] can add both width and depth, it does so by

\begin{table}
\begin{tabular}{l l l l l}
**METHOD** & **WHEN** & **WHERE** & **WHAT** & **DEPTH?** \\ \hline ActiveNAS [7] & end of training & argmax on presets & reinitialize & Yes \\ DyNC [2] & converged loss & preset & random & No \\ NeurDL [5] & recon error & recon error & random & No \\ DENNs [27] & converged loss & preset then prune & random & No \\ PrNNs [21] & at new task & preset & random & No \\ \hline GradMax [6] & future work & future work & vanilla gradient & No \\ SSD [25] & converged loss & loss reduction & loss reduction & No \\ Firefly [26] & N epochs & vanilla gradient & loss reduction & No \\ \hline SENN (ours) & natural gradient & natural gradient & natural gradient & Yes \\ \end{tabular}
\end{table}
Table 1: Existing expansion methods’ answer to when, where, what and whether they consider depth. SENN is the only approach to provide a cohesive answer to all three based on natural gradients.
completely restarting training with a fresh initialization of the whole network after every modification. It then waits for convergence, and uses preset answers to **where** similar to the previous methods.

The final cluster of three methods all aim to improve on random initialization as an answer to **what**. Splitting Steepest Descent (SSD) [25] and Firefly [26] make small changes to the existing function and answer **what** by optimizing the consequent loss reduction. The former answers **when** by waiting for convergence and examining the loss, whereas the latter simply adds more capacity every \(N\) epochs. Gradmax [6] is the closest to SENN in spirit, but is based on vanilla rather than natural gradient descent. More importantly, potential extensions of the method to the **where** and **when** questions are mentioned briefly and their investigation deferred to future work. All three of these latter methods are only able to avoid redundancy of added neurons with existing neurons to the extent that the network is already converged. Of these three, only GradMax completely avoids changing the overall function. In contrast, SENN provides a monolithic answer to all three questions via the natural expansion score.

## 3 Self-Expanding Neural Networks

To provide a cohesive answer to **when**, **where**, **what** with Self-Expanding Neural Networks, we start with the definition of the natural expansion score as the foundation:

**Definition 1**.: _The natural expansion score \(\eta=\mathbf{g}^{T}\mathbf{F}^{-1}\mathbf{g}\) is given by the inner product of the natural gradient \(\mathbf{F}^{-1}\mathbf{g}\) with the gradient \(\mathbf{g}\)._

With this definition we will describe **how** we add capacity without interfering with the existing optimized parameters in section 3.1. We then in section 3.2 give an intuitive account of what our score \(\eta\) measures, and why we use this to decide **when** to add capacity. Section 3.3 gives a more mathematically precise account of the meaning of \(\eta\), and what this says about **what** initializations should be used for new capacity. Section 3.4 extends the argument of 3.3 to deciding **where** new capacity should be added and whether it should be depth or width, allowing us to put the ingredients of SENN together and summarize this combination. Finally, sections 3.5 and 3.6 cover the practical questions of convergence guarantees and computational efficiency respectively.

### How to add: expanding without changing the overall function

In order to explain how to add without changing the overall function, we will consider the illustration in figure 1. This shows a perceptron with two hidden layers, each with three neurons. The number of neurons a hidden layer may be increased by introducing a new copy of the activation function \(\sigma_{p}\) and connecting it to the neurons of the preceding layer with some linear transform \(\mathbf{W}_{p}\). As shown on the left of the figure, we connect the new neuron to the subsequent layer (in this case the output \(\mathbf{y}\)) with a linear transform initialized to zero. In doing so, we guarantee that we will not perturb the function specified by the existing parameters. Although \(\mathbf{W}_{p}\) will initially receive zeroed gradients

Figure 1: **SENN is able to add width (orange, left side) and depth (green, right side) to a neural network without changing the overall function. In the diagram, the model’s component functions are composed vertically, e.g. \(\sigma_{1}(\mathbf{W}_{1}\mathbf{x})\) gives the first set of hidden activations. \(\uplus\) indicates concatenation along a hidden dimension, i.e. width addition. \(\mathbf{W}_{2}\mathbf{W}_{p}^{-1}\) indicates matrix multiplication, used in depth expansion via the insertion of an identity function. (Best viewed in color.)**
since the output transform is zero, this latter transform will immediately receive non-zero gradients and thereby become non-zero. The new neuron may thus be used in future optimization.

In addition to width expansion, we now consider inserting an entirely new layer, as shown on the right of figure 1. In essence, a particular linear transform, \(\mathbf{W}_{2}\) in the figure, is replaced with a single layer perceptron. To this end, we assume our nonlinearity \(\sigma_{p}\) to be parameterised, and there to exist a choice of those parameters such that \(\sigma_{p}=\mathbf{I}\) is the identity. If we require the initial linear transform \(\mathbf{W}_{p}\) of the inserted perceptron to be invertible (but otherwise arbitrary), then we may choose the output linear transform of the perceptron to be the matrix product \(\mathbf{W}_{2}\mathbf{W}_{p}^{-1}\). With these choices made, the inserted perceptron is equivalent to the linear transform \(\mathbf{W}_{2}\) it replaces, and the overall parameterized function once again remains unchanged. We thus have the first ingredient of SENN:

**SENN Ingredient 1: How to add more capacity without changing the overall function.**

We add proposed neurons \(p\) to layer \(i\) by concatenation along the the \(i\)th hidden dimension \((0\!\uplus\mathbf{W}_{i+1})\circ(\sigma_{p}\!\uplus\sigma_{i})\circ(\mathbf{W}_{p} \!\uplus\mathbf{W}_{i})=\mathbf{W}_{i+1}\circ\sigma_{i}\circ\mathbf{W}_{i}\), and initialize the output weights of \(p\) to zero. We insert a new layer \(q\) by replacing some linear transform \(\mathbf{W}_{i}\) with the composition \((\mathbf{W}_{i}\mathbf{W}_{q}^{-1})\circ(\sigma_{q}=\mathbf{I})\circ\mathbf{W}_{q}\), where \(\mathbf{W}_{q}\) is invertible and \(\sigma_{q}\) is initialized to be the identity.

We must therefore choose a suitable parameterized activation function. Rational activation functions satisfy the above conditions and were shown to obtain good real world performance [18]. We use the simplified parameterization \(\sigma_{\mathbf{\theta}}(x)=\alpha x+(\beta+\gamma x)/(1+x^{2})\), where \(\mathbf{\theta}=\{\alpha,\beta,\gamma\}\) are the three parameters of \(\sigma\), and setting \(\mathbf{\theta}=\{1,0,0\}\) results in the identity function, as required. Since this parameter count is small, we do not share the activation function weights within our layers.

### When to add: deciding whether more capacity is useful

Having decided how to add, perhaps the most natural way to evaluate the utility of making some change to the parameterization is to ask what immediate effect this has on the total loss. However, we cannot do this as we have assumed the overall function to remain unaltered. We must therefore consider additional information such as the gradients of the function. Specifically, one can favor adding neurons which maximally increase the euclidean norm of the gradients \(||\mathbf{g}||_{2}\). As found in Evci _et al._[6] this norm functions well for selecting which neurons to add when the network is close to convergence since it is a direct measure of the rate at which gradient descent will decrease the loss.

Unfortunately, comparing the gradient norms \(||\mathbf{g}||_{2}^{2}\) and \(||\mathbf{g}^{\prime}||_{2}^{2}\) for the current parameterization \(\mathbf{\theta}\) and some new expanded parameterization \(\mathbf{\theta}^{\prime}\) is insufficient to determine whether or not more capacity is needed in the first place. This is primarily because it does not account for redundancy in the parameterization: if there is some neuron \(a\) such that the gradients of the linear weights in the next layer "listening" to it have some large norm \(||\mathbf{g}_{a}||_{2}\), then we could introduce an exact copy of this neuron \(a^{\prime}\) for which the corresponding norm would also be \(||\mathbf{g}_{a}^{\prime}||_{2}=||\mathbf{g}_{a}||_{2}\). Since the squared euclidean norm is additive across parameters, we could unboundedly increase \(||\mathbf{g}||_{2}^{2}\) just by adding very many copies of this one neuron \(a\). 2

Footnote 2: More generally, the same problem would occur when considering a new neuron \(c\) whose activations were some linear combination of those of some existing neurons \(a\) and \(b\).

In SENN, we avoid this problem with the following simple notion of redundancy. We are using our parameters to express a point in function space. At some point in optimization we are therefore also using them to express a small change in function space. There is some direction that our optimizer "wants" to move in (i.e. the direction in function space which most quickly reduces the loss). We can define new parameters as being useful in a way which is non-redundant with the old parameters to the extent that they allow the optimizer to better express the direction in function space it "wants" to move in. Our natural expansion score \(\eta=\mathbf{g}^{T}\mathbf{F}^{-1}\mathbf{g}\) captures this combined sense of usefulness and non-redundancy in a way which will be made more mathematically precise in the next section. This description of its function is sufficient, however, to justify our answer to **when**:

**SENN Ingredient 2: When to add more capacity.**

A new neuron or layer will be helpful and non-redundant if it provides a fractional increase in \(\eta=\mathbf{g}^{T}\mathbf{F}^{-1}\mathbf{g}\) greater than some threshold \(\tau\). **When** we find a potential new neuron or layer for which this is true, we add it.
We defer specific choices for \(\tau\) to section 3.4, at which point we may draw on the derivation of \(\eta\).

### What to add: determining the initial value of new neurons

The reader may at this point be expecting us to tackle the question of **where** additional capacity is most useful, but this would put the cart before the horse. Additional capacity is useful to the extent that it can be initialized in a way which is useful, which we now consider.

To simplify mathematical notation in this section, we consider the output \(\mathbf{y}\) to be concatenated over the entire training dataset. While the gradient of the loss with respect to the output \(\mathbf{g_{y}}\) tells us how the loss changes for arbitrary changes in \(\mathbf{y}\), the only changes in \(\mathbf{y}\) we can actually achieve with some parameterization \(\Theta\) are given by Jacobian product \(\mathbf{J}\mathbf{t}\) for some small parameter change \(\mathbf{t}\in\Theta\).

Let \(\mathbf{P}_{\Theta}\) be the orthogonal projection onto this space of directions in output space. The vector \(\mathbf{P}_{\Theta}\mathbf{g_{y}}\) is then the portion of \(\mathbf{g_{y}}\) which lies in the space of achievable output changes, and its squared norm \(||\mathbf{P}_{\Theta}\mathbf{g_{y}}||_{2}^{2}\) is a scalar measure of how much of \(\mathbf{g_{y}}\) this portion is. The vector \(\mathbf{P}_{\Theta}\mathbf{g_{y}}\) is the image under the Jacobian \(\mathbf{J}\mathbf{t}\) of some tangent vector \(\mathbf{t}\) in the parameter space. By the definition of orthogonal projection, \(\mathbf{t}\) minimizes \(||\mathbf{J}\mathbf{t}-\mathbf{g_{y}}||_{2}\), but if there are redundant directions in \(\Theta\) then there may exist multiple such \(\mathbf{t}\). There is however a unique \(\mathbf{t}_{*}\) which minimizes \(||\mathbf{t}||_{2}\) among those \(\mathbf{t}\) which minimise \(||\mathbf{J}\mathbf{t}-\mathbf{g_{y}}||_{2}\). The Moore-Penrose inverse, \(\mathbf{J}^{+}\), of \(\mathbf{J}\) is the unique matrix such that \(\mathbf{t}_{*}=\mathbf{J}^{+}\mathbf{g_{y}}\) for arbitrary \(\mathbf{g_{y}}\). However, \(\mathbf{J}\) is a map from parameter space to total output space, which depends on dataset size \(N\). This dependency can be avoided by working with maps from the parameter space to itself, such as the following average over the dataset \(\mathbf{F}=\frac{1}{N}\mathbf{J}^{T}\mathbf{J}\), known as the Fisher information matrix. The natural gradient is then given by \(\hat{\mathbf{F}}^{-1}\mathbf{g}\), where \(\mathbf{g}=\frac{1}{N}\mathbf{J}^{T}\mathbf{g_{y}}\) is the gradient of the loss with respect to the parameters averaged over the training set, and existence of \(\hat{\mathbf{F}}=\mathbf{F}+\epsilon\mathbf{I}\) is guaranteed by the addition of a small multiple \(\epsilon\) of the identity. In the limit of small \(\epsilon\) this is exactly our \(\mathbf{t}_{*}\).3 We are now able to rewrite the squared norm \(||\mathbf{P}_{\Theta}\mathbf{g_{y}}||_{2}^{2}\) in the familiar form of definition 1:

Footnote 3: In fact, an alternative definition of the Moore-Penrose inverse is: \(\mathbf{J}^{+}:=\lim_{\epsilon\to 0}(\mathbf{J}^{T}\mathbf{J}+\epsilon\mathbf{I})^{-1}\mathbf{J}^{T}\)

\[||\mathbf{P}_{\Theta}\mathbf{g_{y}}||_{2}^{2}=\mathbf{t}_{*}^{T}\mathbf{J}^{T}\mathbf{J}\mathbf{t}_{*} =\mathbf{g}^{T}\mathbf{F}^{-1}\mathbf{J}^{T}\mathbf{J}\mathbf{F}^{-1}\mathbf{g}=N\mathbf{g}^{T}\mathbf{F}^{-1} \mathbf{g}=N\eta\quad. \tag{1}\]

Here, the factor of the dataset size \(N\) appears because the average gradient \(\mathbf{g}\) and our \(\eta\) are normalized according to the training set size. With this formula, we have now derived \(\eta\) from first principles and may use it to choose between specific initializations, yielding our third SENN ingredient:

**SENN Ingredient 3: What Initialization to Use.** If \(\mathbf{\theta}^{\prime}\in\Theta^{\prime}\) is an initialization of an expanded parameterization \(\Theta^{\prime}\) such that the overall function remains unchanged (see section 3.1), then the best such initialization \(\mathbf{\theta}^{\prime}_{*}\) is given by \(\operatorname*{arg\,max}_{\mathbf{\theta}^{\prime}}(\eta^{\prime})\). When we add new neurons or layers, we choose **what** initialization to use by this method.

### Where to add: completing the algorithm

Much as the euclidean norm \(||\mathbf{g}||_{2}\) measures the rate of loss reduction according to vanilla gradient descent, our \(\eta\) measures the rate of loss reduction according to natural gradient descent. This gives a uniform way of comparing the effect of new capacity no matter where it is added in the network or whether it takes the form of new neurons in an existing layer or a new layer. In particular, one may compare the \(\eta\) values of the best initializations (see section 3.3) for each such variety of addition. 4

Footnote 4: In general one can also adjust for the “size” of each addition in some relevant sense. We found it sufficient to just penalize adding entire new layers versus single new neurons by some constant factor.

**SENN Ingredient 4: Where to Add.** A choice of whether to add width or depth, and **where** in the network the new neuron/layer will be added, specifies a particular extension of the current parameter space \(\Theta^{\prime}\). We make those choices which correspond to the extension \(\Theta^{\prime}_{*}=\operatorname*{arg\,max}_{\Theta^{\prime}}\operatorname*{ arg\,max}_{\mathbf{\theta}^{\prime}}(\eta^{\prime})\) for which the best initialization is possible.

Our newfound knowledge of \(\eta\) as a rate of loss reduction in hand, we return to the question of specifying the expansion threshold \(\tau\), which we deferred from section 3.2 in our previous answer to **when**. An increase from the current natural expansion score \(\eta_{c}\) to a new score \(\eta_{p}\) due to some
proposed expansion \(p\) corresponds to an increase in the rate of loss reduction by natural gradient descent. We define this increase to be "sufficient" when it corresponds to a relative increase \(\eta_{p}/\eta_{c}>\tau\) in loss reduction rate greater than the **expansion threshold**\(\tau\). For example, with the intuitive choice \(\tau=2\), each addition must at least double the rate of loss reduction. Following the well known intuition that a network does not practically converge without setting the learning rate to zero, it is generally considered to have converged once changes in loss become sufficiently small. In analogy to monitoring plateaus in loss, we further require the increase in loss reduction resulting from new capacity to surpass an absolute **stopping criterion**\(\alpha\). While we answer **when, where** and **what** cohesively with \(\eta\) during training, we thus concur with all prior works on terminating training. Overall, we may now summarize all ingredients of SENN on the basis of the natural expansion score:

[leftmargin=*]
**SENN: Summary.** When we add width or depth we do so without changing the overall function. We add new capacity **when** this produces a relative increase in score \(\eta_{p}/\eta_{c}>\tau\) larger than the expansion threshold \(\tau\). We add new capacity **where** it would most increase \(\eta\), and choose **what** initialization to use in order to maximize \(\eta\). We ensure the addition process terminates by additionally comparing each \(\Delta\eta\) to the absolute stopping criterion \(\alpha\), and not adding capacity **when**\(\eta_{p}-\eta_{c}\leq\alpha\).

### Bounds on convergence of expansion

Consider repeatedly running our addition algorithm for a network with initial expansion score \(\eta_{0}\). The expansion threshold \(\tau\) guarantees that \(\eta_{i}>\tau\eta_{i-1}\) after the \(i\)-th addition. Since \(\eta=\mathbf{g}^{T}\mathbf{F}^{-1}\mathbf{g}\) is the squared length of the projected gradient in output space \(||P_{0}\mathbf{g}_{\mathbf{y}}||_{2}\), it is non-negative and bounded above by \(\eta\leq\lambda=||\mathbf{g}_{\mathbf{y}}||_{2}^{2}\). Since \(\eta_{i}\) grows exponentially with \(i\) and is bounded above by \(\lambda\) the maximum number of sequential additions \(i<N_{s}\) increases logarithmically with \(\lambda\). Specifically, \(N_{s}<(\ln\lambda-\ln\eta_{0})/\ln\tau\). This bound becomes large when \(\eta_{0}\) is small, but we also know that \(\eta_{1}>\alpha\) from the stopping criterion \(\alpha\).

**Theorem 1** (Upper bound on the "rate" of neuron addition).: _The maximum number of additions \(N_{s}\) from repeatedly running the expansion algorithm is bounded: \(N_{s}<1+(\ln\lambda-\ln\alpha)/\ln\tau\)._

(Proof in supplementary material.) For example, if \(\tau=2\) and \(\alpha/\lambda>10^{-3}\) then \(N_{s}<1+\frac{3\ln 10}{\ln 2}<11\). Note that exponentially large ratios between \(\alpha\) and \(\lambda\) produce only linearly large bounds on \(N_{s}\).

We now consider the number of additions \(N_{T}\) made over the course of training with natural gradient descent. Intuitively, \(\lambda\) is the total possible loss reduction and \(\alpha\) is the minimum reduction which justifies expanding the network. If every time we expand the network it only achieves this minimum reduction then we must expand a total of roughly \(N_{T}\approx\lambda/\alpha\) times. If the loss function has constant curvature equal to the fisher \(\mathbf{F}\), then the total loss reduction possible with the current parameters is given by \(\frac{1}{2}\eta\) and we have \(N_{T}<\lambda/\alpha\) exactly. More generally, we expect that when \(\mathbf{F}\) is an underestimate of the true curvature, \(\eta\) will overestimate the usefulness of new neurons causing \(N_{T}\) to be larger, and vice versa for \(\mathbf{F}\) an overestimate. See supplementary for more in depth discussion.

### Efficiently computing a lower bound on score increase

Recall that the natural expansion score \(\eta\) is given by the inner product of the gradient \(\mathbf{g}\) with the natural gradient \(\mathbf{F}^{-1}\mathbf{g}\). Since working with the natural gradient can be challenging due to the matrix inverse \(\mathbf{F}^{-1}\), we will make use of established approximation techniques. Specifically, when we need the natural gradient for the whole network we will use the iterative conjugate gradient method, as suggested for the Hessian in Martens [16], performing Fisher-vector multiplication cheaply via auto-differentiation. When we require the inverse Fisher \(\mathbf{F}_{l}^{-1}\) for the linear transform in some layer \(l\) considered in isolation, we approximate \(\mathbf{F}_{l}\) by the Kronecker product \(\mathbf{F}_{l}\approx\tilde{\mathbf{F}}_{l}=\mathbf{S}_{l}\otimes\mathbf{A}_{l}\), where \(\mathbf{A}_{l}\) is the second moment of the activations at the input of the linear transform, and \(\mathbf{S}_{l}\) is given by the second moment of some distribution of gradients with respect to the output of the linear transform. The relevant gradient distribution is determined by the choice of metric on the output space implicit in the exact definition of \(\mathbf{F}\) one is using, which for us is the euclidean metric. The advantage of this Kronecker factorization is that \(\tilde{\mathbf{F}}_{l}\) may be inverted by inverting \(\mathbf{A}_{l}\) and \(\mathbf{S}_{l}\) separately: \(\tilde{\mathbf{F}}_{l}^{-1}=\mathbf{A}_{l}^{-1}\otimes\mathbf{S}_{l}^{-1}\), which is much cheaper. If \(\partial\mathbf{W}\) is the gradient with respect to the weights as
a matrix, then the natural gradient is given by \(\mathbf{S}^{-1}\partial\mathbf{W}\mathbf{A}^{-1}\)[15]. The natural expansion score \(\eta\) is given by the inner product of the gradient with the natural gradient as vectors, which in this matrix form becomes the elementwise inner product \(\eta=\sum_{i,j}\partial\mathbf{W}_{ij}(\mathbf{S}^{-1}\partial\mathbf{W}\mathbf{A}^{-1})_{ij}\), which can also be expressed as a trace: \(\eta=\operatorname{Tr}[\partial\mathbf{W}^{T}\mathbf{S}^{-1}\partial\mathbf{W}\mathbf{A}^{-1}]\).

The trace formula for \(\eta\) is reminiscent of the definition of the pearson correlation coefficient \(r^{2}=\operatorname{\mathbb{E}}\left[xy\right]^{2}/(\operatorname{\mathbb{E }}\left[xx\right]\operatorname{\mathbb{E}}\left[yy\right])\). The gradient for \(\mathbf{W}\) is given by the expectation \(\partial\mathbf{W}=\operatorname{\mathbb{E}}\left[\mathbf{a}\mathbf{g}^{T}\right]\), where \(\mathbf{a}\) is the input activation vector, \(\mathbf{g}\) is the derivative of the loss with respect to the outputs, and the expectation is over the dataset. Let the residual gradient \(\mathbf{g}_{r}=\mathbf{g}-\operatorname{\mathbb{E}}\left[\mathbf{g}\mathbf{a}^{T}\right]\mathbf{ A}^{-1}\mathbf{a}\) be the part of the gradient not predicted by the current activations \(\mathbf{a}\). Then if \(\mathbf{a}_{p}\) is the activation vector of a set of proposed neurons, and \(\mathbf{A}_{p}\) is their second moment, then the "correlation coefficient" of the new activations with the residual gradients is a lower bound \(\Delta\eta^{\prime}\) on the improvement \(\Delta\eta\) in natural expansion score (proof in appendix via block LDU decomposition of joint activation covariance):

**Theorem 2** (**Computationally cheap lower bound on increase in natural expansion score)**.: \(\Delta\eta^{\prime}:=\operatorname{Tr}[\mathbf{A}_{p}^{-1}\operatorname{\mathbb{ E}}\left[\mathbf{a}_{p}\mathbf{g}_{r}^{T}\right]\mathbf{G}_{l}^{-1}\operatorname{\mathbb{E}} \left[\mathbf{g}_{r}\mathbf{a}_{p}^{T}\right]]\) _is a lower bound \(\Delta\eta^{\prime}\leq\Delta\eta=\eta_{p}-\eta_{c}\) on the improvement in natural expansion score due to some proposed addition of neurons \(p\) to a layer \(l\)._

Intuitively, \(\Delta\eta^{\prime}\) is the fraction of variance in residual gradients "explained" by the output of our new neuron(s). This result holds for adding an arbitrary number of new neurons to an existing layer. If a layer was inserted while retaining residual connections around it, then the same result would hold if we treated the activations of the new layer as "new neurons" in the old layer to calculate \(\Delta\eta^{\prime}\). Because our activation function can represent the identity, we will automatically add these connections if in fact they are necessary, so we in fact use this same method for evaluating our actual layer insertions.

The bound \(\Delta\eta^{\prime}\) can be computed for an arbitrary proposal \(p\) of additional neurons using only those intermediate activations and gradients which it would be necessary to cache in order to calculate the gradient \(\mathbf{g}\) and (Kronecker factored approximate) natural gradient \(\tilde{\mathbf{F}}^{-1}\mathbf{g}\) via backpropagation. Therefore, if we have an outer optimizer which computes \(\mathbf{g}\) and \(\tilde{\mathbf{F}}^{-1}\), then we may optimize arbitrarily many proposals \(p\) for arbitrarily many steps with an inner optimizer without incurring any additional costs related to the evaluation of the existing network. The costs of this inner optimizer instead scale with the size of the (very small) networks whose addition to the existing network is being considered.

## 4 Experiments

We now apply Self-Expanding Neural Networks to regression and classification, to illustrate the behavior of the natural expansion score and demonstrate SENN's efficacy.

### Width Addition in Least-Squares Regression

We first show that the evolution over training of the possible improvements \(\Delta\eta^{\prime}\) in natural expansion score due to potential width expansions is meaningful. In order to do so we consider the application of a single layer SENN to a one dimensional least squares regression task as shown in figure 2, i.e. SENN with depth addition deliberately disabled. The reason to have only one hidden layer is that this is effectively least squares regression with basis functions given by the neurons of that layer. We can therefore plot the normalized score increase \(\Delta\eta^{\prime}/\eta_{c}\) of the best neuron for each basis function location and length scale. Where \(\Delta\eta^{\prime}/\eta_{c}>1\) there exists an acceptable proposal. Accepted/rejected proposed neurons are shown on this landscape in red/black at key points in training. We see in the leftmost figure that the best such proposal is accepted because it achieves a large improvement in \(\eta\), and it corresponds to a basis function location close to datapoints with visibly large prediction error which we have been unable to reduce using the existing neurons. The next figure to the right shows the same landscape after the new neuron is introduced, and it can be seen that the \(\Delta\eta^{\prime}/\eta_{c}\) values for neurons with similar locations to it have been dramatically reduced since they would be redundant. The second figure from the right shows the result of optimizing the new expanded parameters until the point at which the next neuron would be added. It can be seen that the prediction errors in the region of the previously introduced neuron are now practically invisible, and that the next neuron is to be introduced in a different region in which errors remain. The rightmost figure shows the function approximation at the conclusion of training, and it can be seen that the prediction errors are negligible and proposals with large relative increase in \(\eta\) are not to be found in the region considered. The reader may note that there are some possible new neurons with small length scales which would surpass the
expansion threshold which we do not find; we could deliberately try optimizing initializations at this lengthscale to find these, but this would likely result in overfitting. Overall, SENN thus identifies regions of locally insufficient capacity in our parameterization, targets these regions precisely with new added neurons, and uses this selectively added capacity to achieve a good final fit.

### Layer Addition in Classification

We now highlight SENN's depth expansion in the context of classification. Specifically, we consider two-dimensional inputs from the half-moons dataset [20]. In figure 3 we plot \(\Delta\eta^{\prime}/\eta_{c}\) for the best layer addition proposals as a function of overall optimizer steps. Visualizations of the learned decision boundary at initialization and just before layer additions are shown. We can observe that \(\Delta\eta^{\prime}/\eta_{c}\) increases approximately monotonically during three phases, punctuated by large drops when layers are added. In the initial phase the network has zero hidden layers (i.e. is linear), and the simplicity of the decision boundary at the end of this phase reflects this. Since the datapoints are not linearly separable, the large \(\Delta\eta^{\prime}/\eta_{c}\) value correctly indicates that the introduction of a hidden layer is necessary in order to further reduce loss. The visible increase in decision boundary complexity

Figure 3: Classification is performed with SENN on the half moons [20] dataset. The normalized layer addition score \(\Delta\eta^{\prime}/\eta_{c}\) is shown as a function of optimization steps; the horizontal bar shows the point above which a layer will be added. The score increases during three phases during which the SENN has initial zero, one and then two hidden layers. The respective decision boundary is shown at the beginning and end of these. These layer additions allow SENN to represent more complex decision boundaries when required for global expressivity. (Best viewed in color.)

Figure 2: A single layer SENN (black, solid) is trained to approximate a target function (red, dashed) via non-linear least-squares regression on samples (blue, markers). The location of existing neurons is shown by vertical lines. The lower figures show \(\Delta\eta^{\prime}/\eta_{c}\) as a function of the location and scale of the nonlinearity introduced by a new neuron. Accepted and rejected proposals are marked in red and black respectively. From left to right we see the landscape before and immediately after the fourth neuron is added, before the fifth neuron is added, and at the end of training. SENN adds neurons where they are relevant in order to achieve a good final fit. (Best viewed in color.)
and accuracy over the course of the second phase confirms this. The beginning of the third phase marks the introduction of a second hidden layer and we wait until \(\Delta\eta^{\prime}/\eta_{c}\) rises again, indicating an exhaustion of this new capacity, before reexamining the decision boundary. The increase in boundary complexity is less visible this time, but close inspection reveals that the boundary has become narrower and more rounded. Conclusively, we have intentionally constructed a scenario where depth addition is necessary for a good fit to lie in the space of solutions, and seen that SENN inserts new layers when this is necessary for global expressivity.

### Dynamic Selection of Appropriate Architecture Size in Image Classification

Finally, we examine the ability of self-expanding neural networks to choose an appropriate size when classifying MNIST [4] images. The leftmost plots of figure 4 show SENN's total hidden size and validation accuracy during training on the full dataset as a function of total batches seen. This use of mini-batching is not strictly necessary for MNIST but we use it to better reflect the realities of training modern neural networks. Our SENN is initialized with a single hidden layer of size 10, and promptly adds a second hidden layer, also of size 10. All five seeds considered then proceed to consistently add width to these layers at a moderate rate until a total hidden size of around 40 is reached, at which point far fewer productive extensions of the network are found and addition slows dramatically. It can be seen that this results in respectable validation performance (>97%) by the end of training with very modest hidden neuron counts (50-60). It is of particular note that our method produces strong **anytime** performance: we are able to continually expand size, and even insert layers, during training without any attendant drops in validation accuracy. Indeed, our method exhibits mostly monotonic improvement up to stochasticity from batching, a property not shared by methods which rely on reinitializing a new network, e.g. [7]. This makes SENN a perfect fit to prospective applications in e.g. active or continual learning, in the spirit of our original neurogenesis inspiration.

Having verified sensible performance of SENN on the full MNIST dataset, we now examine the way in which they adapt their final converged size to the amount of information in the dataset. To this end, we take class-balanced subsets of MNIST of varying sizes and train SENNs to convergence. To maximize clarity in our examination of this relationship, we restrict the SENN to width addition. The converged hidden sizes are shown together with the standard error across five seeds in the rightmost plots of figure 4. The first of these shows log width against linear subset size for ease of comparison to the leftmost panel. It can be seen that the final width tails off rapidly with subset size. The rightmost plot shows instead linear width against logarithmic subset size, in which we can now distinguish three regimes. For the smallest subsets, the initial hidden size of 10 is sufficient. For subsets between 10% and 60% of the standard training set, the final hidden size increases logarithmically, but past that point further increases in subset size do not similarly increase the final network size. We posit that this is due to substantial redundancy within the MNIST training set, leaving further capacity growth unnecessary. Thus, SENN does not only provide desirable any time performance, but also tailors its size suitably to the available data.

Figure 4: SENN shows reasonable and reproducible hidden layer growth on MNIST at appealing any-time validation accuracy without intermittent perturbations (left pair of panels). SENN features appropriate scaling with respect to data complexity in its chosen network sizes (right pair of panels).
Conclusion

We have introduced the natural expansion score \(\eta\) and shown how it may be used to cohesively answer the three key questions **when**, **where** and **what** of growing neural networks. We have demonstrated its ability to capture redundancy of new neurons with old and thereby make sensible expansion decisions across time and tasks. While we have focused on providing a thorough mathematical grounding of the natural expansion score in this work, we acknowledge that the multilayer perceptrons on which it was demonstrated differ in scale and complexity from many of the architectures in active use for deep learning in the modern big data regime. Dually, however, prospects for further development are promising, as our theoretical results regarding \(\eta\) apply for arbitrary expansions of parameterized models, and our method of expansion would extend naturally to, for example, convolutional neural networks or normalizing flows where layers may be initialized invertibly.

## Acknowledgments

This work was supported by the project "safeFBDC - Financial Big Data Cluster" (FKZ: 01MK21002K), funded by the German Federal Ministry for Economics Affairs and Energy as part of the GAIA-x initiative, and the Hessian research priority programme LOEWE within the project "WhiteBox". It benefited from the Hessian Ministry of Higher Education, Research, Science and the Arts (HMWK; projects "The Third Wave of AI" and "The Adaptive Mind").