# Growing Tiny Networks: Spotting Expressivity Bottlenecks and Fixing Them Optimally

Manon Verbockhaven, Sylvain Chevallier, Guillaume Charpiat

<figure><img src="image_1.png" /></figure>

## To cite this version:

Manon Verbockhaven, Sylvain Chevallier, Guillaume Charpiat. Growing Tiny Networks: Spotting Expressivity Bottlenecks and Fixing Them Optimally. 2024. hal-04591472

HAL Id: hal-04591472

https://hal.science/hal-04591472

Preprint submitted on 29 May 2024

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Growing Tiny Networks: Spotting Expressivity Bottlenecks and Fixing Them Optimally

Manon Verbockhaven, Théo Rudkiewicz, Sylvain Chevallier, Guillaume Charpiat

► To cite this version:

Manon Verbockhaven, Théo Rudkiewicz, Sylvain Chevallier, Guillaume Charpiat. Growing Tiny Networks: Spotting Expressivity Bottlenecks and Fixing Them Optimally. Transactions on Machine Learning Research Journal, 2024. hal-04591472v2

HAL Id: hal-04591472

https://hal.science/hal-04591472v2

Submitted on 11 Dec 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# GROWING TINY NETWORKS: SPOTTING EXPRESSIVITY BOTTLENECKS AND FIXING THEM OPTIMALLY

Manon Verbockhaven, Sylvain Chevallier, Guillaume Charpiat

TAU team, Université Paris-Saclay, CNRS, Inria, LISN, 91405, Orsay, France

firstname.name@inria.fr

## ABSTRACT

Machine learning tasks are generally formulated as optimization problems, where one searches for an optimal function within a certain functional space. In practice, parameterized functional spaces are considered, in order to be able to perform gradient descent. Typically, a neural network architecture is chosen and fixed, and its parameters (connection weights) are optimized, yielding an architecture-dependent result. This way of proceeding however forces the evolution of the function during training to lie within the realm of what is expressible with the chosen architecture, and prevents any optimization across architectures. Costly architectural hyper-parameter optimization is often performed to compensate for this. Instead, we propose to adapt the architecture on the fly during training.

We show that the information about desirable architectural changes, due to expressivity bottlenecks when attempting to follow the functional gradient, can be extracted from backpropagation. To do this, we propose a mathematical definition of expressivity bottlenecks, which enables us to detect, quantify and solve them while training, by adding suitable neurons when and where needed. Thus, while the standard approach requires large networks, in terms of number of neurons per layer, for expressivity and optimization reasons, we are able to start with very small neural networks and let them grow appropriately. As a proof of concept, we show results on the CIFAR dataset, matching large neural network accuracy, with competitive training time, while removing the need for standard architectural hyper-parameter search.

## 1 INTRODUCTION

**Issues with the fixed-architecture paradigm.** Universal approximation theorems such as (Hornik et al., 1989; Cybenko, 1989) are historically among the first theoretical results obtained on neural networks, stating the family of neural networks with arbitrary width as a good candidate for a parameterized space of functions to be used in machine learning. However the current common practice in neural network training consists in choosing a fixed architecture, and training it, without any possible architecture modification meanwhile. This inconveniently prevents the direct application of these universal approximation theorems, as expressivity bottlenecks that might arise in a given layer during training will not be able to be fixed. There are two approaches to circumvent this in daily practice. Either one chooses a (very) large width, to be sure to avoid expressivity and optimization issues (Hanin & Rolnick, 2019b; Raghu et al., 2017), to the cost of extra computational power consumption for training and applying such big models; to mitigate this cost, model reduction techniques are often used afterwards, using pruning, tensor factorization, quantization (Louizos et al., 2017) or distillation (Hinton et al., 2015). Or one tries different architectures and keeps the most suitable one (in terms of performance-size compromise for instance), which multiplies the computational burden by the number of trials. This latter approach relates to the Auto-DeepLearning field (Liu et al., 2020), where different exploration strategies over the space of architecture hyper-parameters (among other ones) have been tested, including reinforcement learning (Baker et al., 2017; Zoph & Le, 2016), Bayesian optimization techniques (Mendoza et al., 2016), and evolutionary approaches (Miller et al., 1989; Stanley et al., 2009; Miikkulainen et al., 2017; Bennet et al., 2021), that all rely on random tries and consequently take time for exploration. Within that line, Net2Net (Chen et al., 2015), AdaptNet (Yang et al., 2018) and MorphNet (Gordon et al., 2018) propose different strategies to explore possible variations of a given architecture, possibly guided by model size con-
# Growing Tiny Networks: Spotting Expressivity Bottlenecks and Fixing Them Optimally

Manon Verbockhaven, Théo Rudkiewicz, Sylvain Chevallier, Guillaume Charpiat

TAU team, LISN, Université Paris-Saclay, CNRS, Inria, 91405, Orsay, France

firstname.name@inria.fr

Reviewed on OpenReview: https://openreview.net/forum?id=hbtG6s6e7r

## Abstract

Machine learning tasks are generally formulated as optimization problems, where one searches for an optimal function within a certain functional space. In practice, parameterized functional spaces are considered, in order to be able to perform gradient descent. Typically, a neural network architecture is chosen and fixed, and its parameters (connection weights) are optimized, yielding an architecture-dependent result. This way of proceeding however forces the evolution of the function during training to lie within the realm of what is expressible with the chosen architecture, and prevents any optimization across architectures. Costly architectural hyper-parameter optimization is often performed to compensate for this. Instead, we propose to adapt the architecture on the fly during training. We show that the information about desirable architectural changes, due to expressivity bottlenecks when attempting to follow the functional gradient, can be extracted from backpropagation. To do this, we propose a mathematical definition of expressivity bottlenecks, which enables us to detect, quantify and solve them while training, by adding suitable neurons. Thus, while the standard approach requires large networks, in terms of number of neurons per layer, for expressivity and optimization reasons, we provide tools and properties to develop an architecture starting with a very small number of neurons. As a proof of concept, we show results on the CIFAR dataset, matching large neural network accuracy, with competitive training time, while removing the need for standard architectural hyper-parameter search.

## 1 Introduction

**Issues with the fixed-architecture paradigm.** Universal approximation theorems such as (Hornik et al., 1989; Cybenko, 1989) are historically among the first theoretical results obtained on neural networks, stating the family of neural networks with arbitrary width as a good candidate for a parameterized space of functions to be used in machine learning. However the current common practice in neural network training consists in choosing a fixed architecture, and training it, without any possible architecture modification meanwhile. This inconveniently prevents the direct application of these universal approximation theorems, as expressivity bottlenecks that might arise in a given layer during training will not be able to be fixed. There are two approaches to circumvent this in daily practice. Either one chooses a (very) large width, to be sure to avoid expressivity and optimization issues (Hanin & Rolnick, 2019b; Raghu et al., 2017), to the cost of extra computational power consumption for training and applying such big models; to mitigate this cost, model reduction techniques are often used afterwards, using pruning, tensor factorization, quantization (Louizos et al., 2017) or distillation (Hinton et al., 2015). Or one tries different architectures and keeps the most suitable one (in terms of performance-size compromise for instance), which multiplies the computational burden by the number of trials. This latter approach relates to the Auto-DeepLearning field (Liu et al., 2020), where different exploration strategies over the space of architecture hyper-parameters (among other ones) have been tested, including reinforcement learning (Baker et al., 2017; Zoph & Le, 2016), Bayesian optimization techniques (Mendoza et al., 2016), and evolutionary approaches (Miller et al., 1989; Stanley et al., 2009; Miikkulainen et al., 2017; Bennet et al., 2021), that all rely on random tries and consequently
straints. Instead, we aim at providing a way to locate precisely expressivity bottlenecks in a trained
network, which might speed up neural architecture search significantly. Moreover, based on such
observations, we aim at modifying the architecture on the fly during training, in a single run (no
re-training), using first-order derivatives only, while avoiding neuron redundancy. Related work on
architecture adaptation while training includes probabilistic edges (Liu et al., 2019) or sparsifying
priors (Wolinski et al., 2020). Yet the training is done on the largest architecture allowed, which is
resource-consuming. On the opposite we aim at starting from the simplest architecture possible.

**Optimization properties.** An important reason for common practice to choose wide architectures is the associated optimization properties: sufficiently larger networks are proved theoretically and shown empirically to be better optimized than small ones (Jacot et al., 2018). Typically, small networks exhibit issues with spurious local minima, while wide ones find good nearly-global minima. One of our goals is to train small networks without suffering from such optimization difficulties.

**Neural architecture growth.** A related line of work consists in growing networks neuron by neuron, by iteratively estimating the best possible neurons to add, according to a certain criterion. For instance, approaches such as (Wu et al., 2019) or Firefly (Wu et al., 2020) aim at escaping local minima by adding neurons that minimize the loss under neighborhood constraints. These neurons are found by gradient descent or by solving quadratic problems involving second-order derivatives. Other approaches (Causse et al., 2019; Bashtova et al., 2022), including GradMax (Evci et al., 2022), seek to minimize the loss as fast as possible and involve another quadratic problem. However the neurons added by these approaches are possibly redundant with existing neurons, especially if one does not wait for training convergence to a local minimum (which is time consuming) before adding neurons, therefore producing larger-than-needed architectures.

**Redundancy.** To our knowledge, the only approach tackling redundancy in neural architecture growth adds random neurons that are orthogonal in some sense to the ones already present (Maile et al., 2022). More precisely, the new neurons are picked within the *kernel* (preimage of {0}) of an application describing already existing neurons. Two such applications are proposed, respectively the matrix of fan-in weights and the pre-activation matrix, yielding two different notions of orthogonality. The latter formulation is close to the one of GradMax, in that both study first-order loss variations and use the same pre-activation matrix, with an important difference though: GradMax optimally decreases the loss without caring about redundancy, while the other one avoids redundancy but picks random directions instead of optimal ones. In this paper we bridge the gap between these two approaches, picking optimal directions that avoid redundancy in the pre-activation space.

**Notions of expressivity.** Several concepts of expressivity or complexity exist in the Machine Learning literature, ranging from Vapnik-Chervonenkis dimension (Vapnik & Chervonenkis, 1971) and Rademacher complexity (Koltchinskii, 2001) to the number of pieces in a piecewise affine function (as networks with ReLU activations are) (Serra et al., 2018; Hanin & Rolnick, 2019a). Bottlenecks have been also studied from the point of view of Information Theory, through mutual information between the activities of different layers (Tishby & Zaslavsky, 2015; Dai et al., 2018); this quantity is difficult to estimate though. Also relevant and from Information Theory, the Minimum Description Length paradigm and Kolmogorov complexity (Kolmogorov, 1965; Li et al., 2008) enable to define trade-offs between performance and model complexity.

In this article, we aim at measuring lacks of expressivity as the difference between what the back-
propagation asks for and what can be done by a small parameter update (such as a gradient step),
that is, between the desired variation for each activation in each layer (for each sample) and the best
one that can be realized by a parameter update. Intuitively, differences arise when a layer does not
have sufficient expressive power to realize the desired variation. Our main contributions are that we:

* take a functional analysis viewpoint over gradient descent on neural networks, suggesting to attempt to follow the functional gradient. We optimize not only the weights of the current architecture, but also the architecture itself on the fly, in order to progressively move towards more suitable parameterized functional spaces. This removes the optimization issues (local minima) that are due to thin architectures;

* properly define and quantify the notion of expressivity bottlenecks, globally at the neural network output as well as at each layer, and this in an easily computable way. This allows to localize expressivity bottlenecks in a neural network;
take time for exploration. Within that line, Net2Net (Chen et al., 2015), AdaptNet (Yang et al., 2018) and MorphNet (Gordon et al., 2018) propose different strategies to explore possible variations of a given architecture, possibly guided by model size constraints. Instead, we aim at providing a way to locate precisely expressivity bottlenecks in a trained network, which might speed up neural architecture search significantly. Moreover, based on such observations, we aim at modifying the architecture on the fly during training, in a single run (no re-training), using first-order derivatives only, while avoiding neuron redundancy. Related work on architecture adaptation while training includes probabilistic edges (Liu et al., 2019) or sparsifying priors (Wolinski et al., 2020). Yet the training is done on the largest architecture allowed, which is resource-consuming. On the opposite we aim at starting from the simplest architecture possible.

**Optimization properties.** An important reason for common practice to choose wide architectures is the associated optimization properties: sufficiently larger networks are proved theoretically and shown empirically to be better optimized than small ones (Jacot et al., 2018). Typically, small networks exhibit issues with spurious local minima, while wide ones find good nearly-global minima. One of our goals is to train small networks without suffering from such optimization difficulties.

**Neural architecture growth.** A related line of work consists in growing networks neuron by neuron, by iteratively estimating the best possible neurons to add, according to a certain criterion. For instance, approaches such as (Wu et al., 2019) or Firefly (Wu et al., 2020) aim at escaping local minima by adding neurons that minimize the loss under neighborhood constraints. These neurons are found by gradient descent or by solving quadratic problems involving second-order derivatives. Other approaches (Causse et al., 2019; Bashtova et al., 2022), including GradMax (Evci et al., 2022), seek to minimize the loss as fast as possible and involve another quadratic problem. However the neurons added by these approaches are possibly redundant with existing neurons, especially if one does not wait for training convergence to a local minimum (which is time consuming) before adding neurons, therefore producing larger-than-needed architectures.

**Redundancy.** To our knowledge, the only approach tackling redundancy in neural architecture growth adds random neurons that are orthogonal in some sense to the ones already present (Maile et al., 2022). More precisely, the new neurons are picked within the *kernel* (preimage of $\{0\}$) of an application describing already existing neurons. Two such applications are proposed, respectively the matrix of fan-in weights and the pre-activation matrix, yielding two different notions of orthogonality. The latter formulation is close to the one of GradMax, in that both study first-order loss variations and use the same pre-activation matrix, with an important difference though: GradMax optimally decreases the loss without caring about redundancy, while the other one avoids redundancy but picks random directions instead of optimal ones. In this paper we bridge the gap between these two approaches, picking optimal directions that avoid redundancy in the pre-activation space.

**Notions of expressivity.** Several concepts of expressivity or complexity exist in the Machine Learning literature, ranging from Vapnik-Chervonenkis dimension (Vapnik & Chervonenkis, 1971) and Rademacher complexity (Koltchinskii, 2001) to the number of pieces in a piecewise affine function (as networks with ReLU activations are) (Serra et al., 2018; Hanin & Rolnick, 2019a). Bottlenecks have been also studied from the point of view of Information Theory, through mutual information between the activities of different layers (Tishby & Zaslavsky, 2015; Dai et al., 2018); this quantity is difficult to estimate though. Also relevant and from Information Theory, the Minimum Description Length paradigm (Rissanen, 1978; Grünwald & Roos, 2019) and Kolmogorov complexity (Kolmogorov, 1965; Li et al., 2008) enable to define trade-offs between performance and model complexity.

In this article, we aim at measuring lacks of expressivity as the difference between what the backpropagation asks for and what can be done by a small parameter update (such as a gradient step), that is, between the desired variation for each activation in each layer (for each sample) and the best one that can be realized by a parameter update. Intuitively, differences arise when a layer does not have sufficient expressive power to realize the desired variation. Our main contributions are that we:

* adopt a functional analysis perspective on gradient descent in neural networks, advocating to follow the functional gradient. We not only optimize the weights of the current architecture but also
* mathematically define the best possible neurons to add to a given layer to decrease lacks of expressivity as a quadratic problem; compute them and their associated expressivity gain;

* automatically adapt the architecture to the task at hand by making it grow where needed, and this in a single run, in competitive computational complexity with respect to classically training a large model just once. To remove any need for layer width hyper-optimization, one could define a target accuracy and stop adding neurons when it is reached.

# 2 MAIN CONCEPTS

## 2.1 NOTATIONS

Let $\mathcal{F}$ be a functional space, e.g. $L_2(\mathbb{R}^p \to \mathbb{R}^d)$, and a loss function $\mathcal{L}: \mathcal{F} \to \mathbb{R}$ defined on it, of the form $\mathcal{L}(f) = \mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(f(x), y)]$, where $\ell$ is the per-sample loss, assumed to be differentiable, and where $\mathcal{D}$ is the sample distribution, from which the dataset $\{(x_1, y_1), \dots, (x_N, y_N)\}$ is sampled, with $x_i \in \mathbb{R}^p$ and $y_i \in \mathbb{R}^d$.

For the sake of simplicity we consider a feedforward neural network $f_\theta: \mathbb{R}^p \to \mathbb{R}^d$ with $L$ hidden layers, each of which consisting of an affine layer with weights $W_l$ followed by a differentiable activation function $\sigma_l(0) = 0$. The network parameters are then $\theta := (W_l)_{l=1...L}$. The network iteratively computes:

<figure><img src="image_3.png" /><figcaption>Figure 1: Notations</figcaption></figure>

To any vector-valued function noted $t(x)$ and any batch of inputs $X := [x_1, \dots, x_n]$, we associate the concatenated matrix $T(X) := (t(x_1) \dots t(x_n)) \in \mathbb{R}^{t(\cdot)|\times n}$. The matrices of pre-activation and post-activation activities at layer $l$ over a minibatch $X$ are thus respectively: $A_l(X) = (a_l(x_1) \dots a_l(x_n))$ and $B_l(X) = (b_l(x_1) \dots b_l(x_n))$.

NB: convolutions can also be considered, with appropriate representations (cf matrix $b_l^c(x)$ in 13).

## 2.2 APPROACH

**Functional gradient descent.** We take a functional perspective on the use of neural networks. Ideally in a machine learning task, one would search for a function $f: \mathbb{R}^p \to \mathbb{R}^d$ that minimizes the loss $\mathcal{L}$ by gradient descent: $\frac{\partial f}{\partial t} = -\nabla_f \mathcal{L}(f)$ for some metric on the functional space $\mathcal{F}$ (typically, $L_2(\mathbb{R}^p \to \mathbb{R}^d)$), where $\nabla_f$ denotes the functional gradient and $t$ denotes the evolution time of the gradient descent. The descent direction $v_{\text{goal}} := -\nabla_f \mathcal{L}(f)$ is a function of the same type as $f$ and whose value at $x$ is easily computable as $v_{\text{goal}}(x) = -(\nabla_f \mathcal{L}(f))(x) = -\nabla_u \ell(u, y(x))|_{u=f(x)}$ (see Appendix A.1 for more details). This direction $v_{\text{goal}}$ is the best infinitesimal variation in $\mathcal{F}$ to add to $f$ to decrease the loss $\mathcal{L}$.

**Parametric gradient descent reminder.** However in practice, to represent functions and to compute gradients, the infinite-dimensioned functional space $\mathcal{F}$ has to be replaced with a finite-dimensioned parametric space of functions, which is usually done by choosing a particular neural network architecture $\mathcal{A}$ with weights $\theta \in \Theta_{\mathcal{A}}$. The associated parametric search space $\mathcal{F}_{\mathcal{A}}$ then consists of all possible functions $f_\theta$ that can be represented with such a network for any parameter value $\theta$. Under standard weak assumptions (see Appendix A.2), the gradient descent is of the form:

$$ \frac{\partial \theta}{\partial t} = -\nabla_{\theta} \mathcal{L}(f_{\theta}) = - \mathbb{E}_{(x,y) \sim \mathcal{D}} [\nabla_{\theta} \ell(f_{\theta}(x), y)]. $$
dynamically adjust the architecture itself to progress towards a suitable parameterized functional space. This approach mitigates optimization challenges like local minima that are due to thin architectures;

* properly define and quantify the concept of expressivity bottlenecks, both globally at the neural network output and locally at individual layers, in a computationally accessible manner. This methodology enables to localize expressivity bottlenecks within a neural network;

* formally define as a quadratic problem the best possible neurons to add to a given layer to decrease lacks of expressivity; solve it and compute the associated expressivity gain;

* use a naive strategy on the basis of our approach to expand a neural network while maintaining competitive computational complexity and performance compared to large and well-known model or other NAS search methods.

# 2 Main concepts

## 2.1 Notations

Let $\mathcal{F}$ be a functional space, e.g. $L_2(\mathbb{R}^p \to \mathbb{R}^d)$, and a loss function $\mathcal{L}: \mathcal{F} \to \mathbb{R}^+$ defined on it, of the form $\mathcal{L}(f) = \mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(f(x), y)]$, where $\ell$ is the per-sample loss, assumed to be differentiable, and where $\mathcal{D}$ is the sample distribution, from which the dataset $\{(x_1, y_1), \dots, (x_N, y_N)\}$ is sampled, with $x_i \in \mathbb{R}^p$ and $y_i \in \mathbb{R}^d$.

For the sake of simplicity we consider a feedforward neural network $f_\theta: \mathbb{R}^p \to \mathbb{R}^d$ with $L$ hidden layers, each of which consisting of an affine layer with weights $W_l$ followed by a differentiable activation function $\sigma_l$ which satisfies $\sigma_l(0) = 0$. The network parameters are then $\theta := (W_l)_{l=1\dots L}$. The network iteratively computes:

$$ 
\begin{gathered}
b_0(\mathbf{x}) = \begin{pmatrix} \mathbf{x} \\ 1 \end{pmatrix} \\
\forall l \in [1, L], \quad 
\begin{cases}
a_l(\mathbf{x}) = W_l b_{l-1}(\mathbf{x}) \\
b_l(\mathbf{x}) = \begin{pmatrix} \sigma_l(a_l(\mathbf{x})) \\ 1 \end{pmatrix}
\end{cases} \\
f_\theta(\mathbf{x}) = \sigma_L(a_L(\mathbf{x}))
\end{gathered}
$$

<figure><img src="image_2.png" /><figcaption>Figure 1: Notations</figcaption></figure>

To any vector-valued function noted $t(\mathbf{x})$ and any batch of inputs $\mathbf{X} := [\mathbf{x}_1, \dots, \mathbf{x}_n]$, we associate the concatenated matrix $T(\mathbf{X}) := (t(\mathbf{x}_1) \dots t(\mathbf{x}_n)) \in \mathbb{R}^{t(\cdot)|\times n}$. The matrices of pre-activation and post-activation activities at layer $l$ over a minibatch $\mathbf{X}$ are thus respectively: $A_l(\mathbf{X}) = (a_l(\mathbf{x}_1) \dots a_l(\mathbf{x}_n))$ and $B_l(\mathbf{X}) = (b_l(\mathbf{x}_1) \dots b_l(\mathbf{x}_n))$.

NB: convolutions can also be considered, with appropriate representations (cf matrix $B_l^c(\mathbf{x})$ in C.1).

## 2.2 Approach

**Functional gradient descent.** We take a functional perspective on the use of neural networks. Ideally in a machine learning task, one would search for a function $f: \mathbb{R}^p \to \mathbb{R}^d$ that minimizes the loss $\mathcal{L}$ by gradient descent: $\frac{\partial f}{\partial t} = -\nabla_f \mathcal{L}(f)$ for some metric on the functional space $\mathcal{F}$ (typically, $L_2(\mathbb{R}^p \to \mathbb{R}^d)$), where $\nabla_f$ denotes the functional gradient and $t$ denotes the evolution time of the gradient descent. The descent direction $v_{\text{goal}} := -\nabla_f \mathcal{L}(f)$ is a function of the same type as $f$ and whose value at $\mathbf{x}$ is easily computable as $v_{\text{goal}}(\mathbf{x}) = -(\nabla_f \mathcal{L}(f))(\mathbf{x}) = -\nabla_u \ell(\mathbf{u}, \mathbf{y}(\mathbf{x}))|_{\mathbf{u}=f(\mathbf{x})}$ (see Appendix A.1 for more details). This direction $v_{\text{goal}}$ is the best infinitesimal variation in $\mathcal{F}$ to add to the output ($u = f(\mathbf{x})$) to decrease the loss $\mathcal{L}$, regardless of the parametrization of $f$.
Using the chain rule, these parameter updates yield a functional evolution :

$$v_{\text{GD}} := \frac{\partial f_{\theta}}{\partial t} = \frac{\partial f_{\theta}}{\partial \theta} \frac{\partial \theta}{\partial t} = \frac{\partial f_{\theta}}{\partial \theta} \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \frac{\partial f_{\theta}}{\partial \theta}^{T}(x) v_{\text{goal}}(x) \right]$$

which significantly differs from the original functional gradient descent. We will aim to augment the neural network architecture so that parametric gradient descents can get closer to the functional one.

**Optimal move direction.** We name $\mathcal{T}_A^{f_\theta}$, or just $\mathcal{T}_A$, the tangent space of $\mathcal{F}_A$ at $f_\theta$, that is, the set of all possible infinitesimal variations around $f_\theta$ under small parameter variations:

$$\mathcal{T}_A^{f_\theta} := \left\{ \left. \frac{\partial f_\theta}{\partial \theta} \delta\theta \right| \text{s.t. } \delta\theta \in \Theta_A \right\}$$

This linear space is a first-order approximation of the neighborhood of $f_\theta$ within $\mathcal{F}_A$. The direction $v_{GD}$ obtained above by gradient descent is actually not the best one to consider within $\mathcal{T}_A$. Indeed, the best move $v^*$ would be the orthogonal projection of the desired direction $v_{goal} := -\nabla_{f_\theta} \mathcal{L}(f_\theta)$ onto $\mathcal{T}_A$. This projection is what a (generalization of the notion of) natural gradient would compute (Ollivier, 2017).

<figure><img src="image_4.png" /><figcaption>Figure 2: Expressivity bottleneck</figcaption></figure>

Indeed, the parameter variation $\delta\theta^*$ associated to the functional variation $v^* = \frac{\partial f_\theta}{\partial \theta} \delta\theta^*$ is the gradient $-\nabla_{\theta}^{\mathcal{T}_A} \mathcal{L}(f_\theta)$ of $\mathcal{L} \circ f_\theta$ w.r.t. parameters $\theta$ when considering the $L_2$ metric on functional variations $\|\frac{\partial f_\theta}{\partial \theta} \delta\theta\|_{L_2(\mathcal{T}_A)}$, not to be confused with the usual gradient $\nabla_{\theta} \mathcal{L}(f_\theta)$, based on the $L_2$ metric on parameter variations $\|\delta\theta\|_{L_2(\mathbb{R}^d|\Theta_A|)}$. This can be seen in a proximal formulation as:

$$v^* = \arg\min_{v \in \mathcal{T}_A} \|v - v_{\text{goal}}\|^2 = \arg\min_{v \in \mathcal{T}_A} \left\{ D_f \mathcal{L}(f)(v) + \frac{1}{2} \|v\|^2 \right\} \quad (1)$$

where $D$ is the directional derivative (see details in Appendix A.3), or equivalently as:

$$\delta\theta^* = \arg\min_{\delta\theta \in \Theta_A} \left\| \frac{\partial f_\theta}{\partial \theta} \delta\theta - v_{\text{goal}} \right\|^2 = \arg\min_{\delta\theta \in \Theta_A} \left\{ D_\theta \mathcal{L}(f_\theta)(\delta\theta) + \frac{1}{2} \left\| \frac{\partial f_\theta}{\partial \theta} \delta\theta \right\|^2 \right\} =: -\nabla_{\theta}^{\mathcal{T}_A} \mathcal{L}(f_\theta).$$

**Lack of expressivity.** When $v_{goal}$ does not belong to the reachable subspace $\mathcal{T}_A$, there is a lack of expressivity, that is, the parametric space $\mathcal{A}$ is not rich enough to follow the ideal functional gradient descent. This happens frequently with small neural networks (see Appendix A.4 for an example). The expressivity bottleneck is then quantified as the distance $\|v^* - v_{goal}\|$ between the functional gradient $v_{goal}$ and the optimal functional move $v^*$ given the architecture $\mathcal{A}$ (in the sense of Eq. 1).

## 2.3 GENERALIZING TO ALL LAYERS

**Ideal updates.** The same reasoning can be applied to the pre-activations $a_l$ at each layer $l$, seen as functions $a_l: x \in \mathbb{R}^p \mapsto a_l(x) \in \mathbb{R}^{d_l}$ defined over the input space of the neural network. The optimal parameter update for a given layer $l$ then follows the projection of the desired update $-\nabla_{a_l} \mathcal{L}(f_\theta)$ of the pre-activation functions $a_l$ onto the linear subspace $\mathcal{T}_A^{a_l}$ of pre-activation variations that are possible with the architecture, as we will detail now.

Given an sample $(x, y) \in D$, standard backpropagation already iteratively computes $v_{goal}^l(x) := -(\nabla_{a_l} \mathcal{L}(f_\theta))(x) = -\nabla_u \ell(\sigma_L(W_L \sigma_{L-1}(W_{L-1} \dots \sigma_L(u))), y)|_{u=a_l(x)}$, which is the derivative of the loss $\ell(f_\theta(x), y)$ with respect to the pre-activations $u = a_l(x)$ of each layer. This is usually performed in order to compute the gradients w.r.t. model parameters $W_l$, as $\nabla_{W_l} \ell(f_\theta(x), y) = \frac{\partial a_l(x)}{\partial W_l} \nabla_{a_l} \ell(f_\theta(x), y)$.

$v_{goal}^l(x) := -(\nabla_{a_l} \mathcal{L}(f_\theta))(x)$ indicates the direction in which one would like to change the layer pre-activations $a_l(x)$ in order to decrease the loss at point $x$. However, given a minibatch of points $(x_i)$, most of the time no parameter move $\delta\theta$ is able to induce this progression for each $x_i$ simultaneously, because the $\theta$-parameterized family of functions $a_l$ is not expressive enough.
**Parametric gradient descent reminder.** However in practice, to represent functions and to compute gradients, the infinite-dimensioned functional space $\mathcal{F}$ has to be replaced with a finite-dimensioned parametric space of functions, which is usually done by choosing a particular neural network architecture $\mathcal{A}$ with weights $\theta \in \Theta_{\mathcal{A}}$. The associated parametric search space $\mathcal{F}_{\mathcal{A}}$ then consists of all possible functions $f_{\theta}$ that can be represented with such a network for any parameter value $\theta$. Under standard weak assumptions (see Appendix A.2), the gradient descent is of the form:

$$ \frac{\partial \theta}{\partial t} = -\nabla_{\theta} \mathcal{L}(f_{\theta}) = - \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \nabla_{\theta} \ell(f_{\theta}(x), y) \right]. \quad (1) $$

Using the chain rule (on $\frac{\partial f_{\theta}}{\partial t}$ then on $\nabla_{\theta} \ell(f_{\theta}(x), y)$), these parameter updates yield a functional evolution:

$$ v_{\text{GD}} := \frac{\partial f_{\theta}}{\partial t} = \frac{\partial f_{\theta}}{\partial \theta} \frac{\partial \theta}{\partial t} = \frac{\partial f_{\theta}}{\partial \theta} \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \frac{\partial f_{\theta}}{\partial \theta}^{\text{T}}(x) v_{\text{goal}}(x) \right] \quad (2) $$

which significantly differs from the original functional gradient descent. We will aim to augment the neural network architecture so that the parametric gradient descent can get closer to the functional one.

**Optimal move direction.** We name $\mathcal{T}_{\mathcal{A}}^{f_{\theta}}$, or just $\mathcal{T}_{\mathcal{A}}$, the tangent space of $\mathcal{F}_{\mathcal{A}}$ at $f_{\theta}$, that is, the set of all possible infinitesimal variations around $f_{\theta}$ under small parameter variations:

$$ \mathcal{T}_{\mathcal{A}}^{f_{\theta}} := \left\{ \left. \frac{\partial f_{\theta}}{\partial \theta} \delta \theta \right| \text{s.t. } \delta \theta \in \Theta_{\mathcal{A}} \right\} $$

This linear functional<fnref n="1" /> space is a first-order approximation of the neighborhood of $f_{\theta}$ within $\mathcal{F}_{\mathcal{A}}$. The direction $v_{\text{GD}}$ obtained above by gradient descent is actually not the best one to consider within $\mathcal{T}_{\mathcal{A}}$. Indeed, the best move $v^*$ would be the orthogonal projection of the desired direction $v_{\text{goal}} := -\nabla_{f_{\theta}} \mathcal{L}(f_{\theta})$ onto $\mathcal{T}_{\mathcal{A}}$. This projection is what a (generalization of the notion of) natural gradient would compute (Ollivier, 2017).

<figure><img src="image_3.png" /><figcaption>Figure 2: Expressivity bottleneck</figcaption></figure>

Indeed, the parameter variation $\delta \theta^*$ associated to the functional variation $v^* = \frac{\partial f_{\theta}}{\partial \theta} \delta \theta^*$ is the gradient $-\nabla_{\theta}^{\mathcal{T}_{\mathcal{A}}} \mathcal{L}(f_{\theta})$ of $\mathcal{L} \circ f_{\theta}$ w.r.t. parameters $\theta$ when considering the $L_2$ metric on functional variations $\|\frac{\partial f_{\theta}}{\partial \theta} \delta \theta\|_{L_2(\mathcal{T}_{\mathcal{A}})}$, not to be confused with the usual gradient $\nabla_{\theta} \mathcal{L}(f_{\theta})$, based on the $L_2$ metric on parameter variations $\|\delta \theta\|_{L_2(\mathbb{R}^{\mathcal{I}_{\mathcal{A}}})}$. This can be seen in a proximal formulation as:

$$ v^* = \arg \min_{v \in \mathcal{T}_{\mathcal{A}}} \|v - v_{\text{goal}}\|^2 = \arg \min_{v \in \mathcal{T}_{\mathcal{A}}} \left\{ D_f \mathcal{L}(f)(v) + \frac{1}{2} \|v\|^2 \right\} \quad (3) $$

where $D$ is the directional derivative (see details in Appendix A.3), or equivalently as:

$$ \delta \theta^* = \arg \min_{\delta \theta \in \Theta_{\mathcal{A}}} \left\| \frac{\partial f_{\theta}}{\partial \theta} \delta \theta - v_{\text{goal}} \right\|^2 = \arg \min_{\delta \theta \in \Theta_{\mathcal{A}}} \left\{ D_{\theta} \mathcal{L}(f_{\theta})(\delta \theta) + \frac{1}{2} \left\| \frac{\partial f_{\theta}}{\partial \theta} \delta \theta \right\|^2 \right\} =: - \nabla_{\theta}^{\mathcal{T}_{\mathcal{A}}} \mathcal{L}(f_{\theta}). $$

**Lack of expressivity.** When $v_{\text{goal}}$ does not belong to the reachable subspace $\mathcal{T}_{\mathcal{A}}$, there is a lack of expressivity, that is, the parametric space $\mathcal{A}$ is not rich enough to follow the ideal functional gradient descent. This happens frequently with small neural networks (see Appendix A.4 for an example). The expressivity bottleneck is then quantified as the distance $\|v^* - v_{\text{goal}}\|$ between the functional gradient $v_{\text{goal}}$ and the optimal functional move $v^*$ given the architecture $\mathcal{A}$ (in the sense of Eq. 3).

<footnote n="1">¹ $\frac{\partial f_{\theta}}{\partial \theta} \delta \theta : \mathbb{R}^p \to \mathbb{R}^d$, $x \mapsto \frac{\partial f_{\theta}(x)}{\partial \theta} \delta \theta$</footnote>
**Activity update resulting from a parameter change.** Given a subset of parameters $\tilde{\theta}$ (such as the ones specific to a layer: $\tilde{\theta} = W_l$), and an incremental direction $\delta\tilde{\theta}$ to update these parameters (e.g. the one resulting from a gradient descent: $\delta\tilde{\theta} = -\eta \sum_{(x,y) \in \text{minibatch}} \nabla_{\tilde{\theta}} \ell(f_{\theta}(x), y)$ for some learning rate $\eta$), the impact of the parameter update $\delta\tilde{\theta}$ on the pre-activations $a_l$ at layer $l$ at order 1 in $\delta\tilde{\theta}$ is $v^l(x_i, \delta\tilde{\theta}) := \frac{\partial a_l(x)}{\partial \tilde{\theta}} \delta\tilde{\theta}$.

Note: given a learning rate $\eta$, in the sequel we will rather consider $v_{\text{goal}}^l(x) := -\eta \nabla_{a_l} \mathcal{L}(f_{\theta})(x)$.

## 3 EXPRESSIVITY BOTTLENECKS

We now quantify expressivity bottlenecks at any layer $l$ as the distance between the desired activity update $v_{\text{goal}}^l(.)$ and the best realizable one $v^l(.)$ (cf Figure 2):

**Definition 3.1 (Lack of expressivity).** For a neural network $f_{\theta}$ and a minibatch of points $\mathbf{X} = \{(x_i, y_i)\}_{i=1}^n$, we define the lack of expressivity at layer $l$ as how far the desired activity update $V_{\text{goal}}^l = (v_{\text{goal}}^l(x_1), v_{\text{goal}}^l(x_2), ...)$ is from the closest possible activity update $V^l = (v^l(x_1), v^l(x_2), ...)$ realizable by a parameter change $\delta\theta$:

$$ \Psi^l := \min_{v^l \in T_A^{\alpha_l}} \frac{1}{n} \sum_{i=1}^n \|v^l(x_i) - v_{\text{goal}}^l(x_i)\|^2 = \min_{\delta\theta} \frac{1}{n} \|V^l(\mathbf{X}, \delta\theta) - V_{\text{goal}}^l(\mathbf{X})\|_{\text{Tr}}^2 \quad (2) $$

where $||.||$ stands for the $L_2$ norm, $||.||_{\text{Tr}}$ for the Frobenius norm, and $V^l(\mathbf{X}, \delta\theta)$ is the activity update resulting from parameter change $\delta\theta$ as defined in previous section. In the two following parts we fix the minibatch $\mathbf{X}$ and simplify notations accordingly by removing the dependency on $\mathbf{X}$.

### 3.1 BEST MOVE WITHOUT MODIFYING THE ARCHITECTURE OF THE NETWORK

Let $\delta W_l^*$ be the solution of 2 when the parameter variation $\delta\theta$ is restricted to involve only layer $l$ parameters, i.e. $W_l$. This move is sub-optimal in that it does not result from an update of all architecture parameters but only of the current layer ones:

$$ \delta W_l^* = \arg\min_{\delta W_l} \frac{1}{n} \| V^l(\delta W_l) - V_{\text{goal}}^l \|_{\text{Tr}}^2 \quad (3) $$

**Proposition 3.1.** The solution of Problem (3) is:

$$ \delta W_l^* = \frac{1}{n} V_{\text{goal}}^l B_{l-1}^T (\frac{1}{n} B_{l-1} B_{l-1}^T)^+ $$

where $P^+$ denotes the generalized inverse of matrix $P$.

This update $\delta W_l^*$ is not equivalent to the usual gradient descent update, whose form is $\delta W_l^{\text{GD}} \propto V_{\text{goal}}^l B_{l-1}^T$. In fact the associated activity variation, $\delta W_l^* B_{l-1}$, is the projection of $V_{\text{goal}}^l$ on the post-activation matrix of layer $l-1$, that is to say onto the span of all possible post-activation directions, through the projector $\frac{1}{n} B_{l-1}^T (\frac{1}{n} B_{l-1} B_{l-1}^T)^+ B_{l-1}$. To increase expressivity if needed, we will aim at increasing this span with the most useful directions to close the gap between this best update and the desired one. Note that the update $\delta W_l^*$ consists of a standard gradient ($V_{\text{goal}}^l B_{l-1}^T$) and of a (kind of) natural gradient only for the last part (projector), as we consider metrics in the pre-activation space.

### 3.2 REDUCING EXPRESSIVITY BOTTLENECK BY MODIFYING THE ARCHITECTURE

To get as close as possible to $V_{\text{goal}}^l$ and to increase the expressive power of the current neural network, we modify each layer of its structure. At layer $l-1$, we add $K$ neurons $n_1, ..., n_K$ with input weights $\alpha_1, ..., \alpha_k$ and output weights $\omega_1, ..., \omega_K$ (cf Figure 3). We have the following expansions by concatenation: $W_{l-1}^T \leftarrow (W_{l-1}^T \quad \alpha_1 \quad ... \quad \alpha_K)$ and $W_l \leftarrow (W_l \quad \omega_1 \quad ... \quad \omega_K)$.

We note this architecture modification $\theta \leftarrow \theta \oplus \theta_{\leftrightarrow}^K$ where $\oplus$ is the concatenation sign and $\theta_{\leftrightarrow}^K := (\alpha_k, \omega_k)_{k=1}^K$ are the $K$ added neurons.
## 2.3 Generalizing to all layers

**Ideal updates.** The same reasoning can be applied to the pre-activations $a_l$ at each layer $l$, seen as functions $a_l: x \in \mathbb{R}^p \mapsto a_l(x) \in \mathbb{R}^{d_l}$ defined over the input space of the neural network. The optimal parameter update for a given layer $l$ then follows the projection of the desired update $-\nabla_{a_l} \mathcal{L}(f_\theta)$ of the pre-activation functions $a_l$ onto the linear subspace $\mathcal{T}_{\mathcal{A}}^{a_l}$ of pre-activation variations that are possible with the architecture, as we will detail now.

Given a sample $(x, y) \in \mathcal{D}$, standard backpropagation already iteratively computes $v_{\text{goal}}^l(x) := -(\nabla_{a_l} \mathcal{L}(f_\theta))(x) = -\nabla_u \ell(\sigma_L(W_L \sigma_{L-1}(W_{L-1}...\sigma_L(u))), y)|_{u=a_l(x)}$, which is the derivative of the loss $\ell(f_\theta(x), y)$ with respect to the pre-activations $u = a_l(x)$ of each layer. This is usually performed in order to compute the gradients w.r.t. model parameters $W_l$, as $\nabla_{W_l} \ell(f_\theta(x), y) = \frac{\partial a_l(x)}{\partial W_l} \nabla_{a_l} \ell(f_\theta(x), y)$.

$v_{\text{goal}}^l(x) := -(\nabla_{a_l} \mathcal{L}(f_\theta))(x)$ indicates the direction in which one would like to change the layer pre-activations $a_l(x)$ in order to decrease the loss at point $x$. However, given a minibatch of points $(x_i)$, most of the time no parameter move $\delta\theta$ is able to induce this progression for each $x_i$ simultaneously, because the $\theta$-parameterized family of functions $a_l$ is not expressive enough.

**Activity update resulting from a parameter change.** Given a subset of parameters $\tilde{\theta}$ (such as the ones specific to a layer: $\tilde{\theta} = W_l$), and an incremental direction $\delta\tilde{\theta}$ to update these parameters (e.g. the one resulting from a gradient descent: $\delta\tilde{\theta} = -\sum_{(x,y)\in\text{minibatch}} \nabla_{\tilde{\theta}}\ell(f_\theta(x), y)$), the impact of the parameter update $\gamma\delta\tilde{\theta}$ on the pre-activations $a_l$ at layer $l$ at order 1 in $\gamma$, where $\gamma$ an amplitude factor, is as $v^l(x, \gamma\delta\tilde{\theta}) := \gamma \frac{\partial a_l(x)}{\partial \tilde{\theta}} \delta\tilde{\theta}$. The factor $\gamma$ is the analogue of the learning rate and is considered to be small.

# 3 Expressivity bottlenecks

We now quantify expressivity bottlenecks at any layer $l$ as the distance between the desired activity update $v_{\text{goal}}^l(.)$ and the best realizable one $v^l(.)$ (cf. Figure 2):

**Definition 3.1 (Lack of expressivity).** For a neural network $f_\theta$ and a minibatch of points $X = \{(x_i, y_i)\}_{i=1}^n$, we define the lack of expressivity at layer $l$ as how far the desired activity update $V_{\text{goal}}^l = (v_{\text{goal}}^l(x_1), v_{\text{goal}}^l(x_2),...)$ is from the closest possible activity update $V^l = (v^l(x_1), v^l(x_2),...)$ realizable by a parameter change $\delta\theta$:

$$ \Psi^l := \min_{v^l \in \mathcal{T}_{\mathcal{A}}^{a_l}} \frac{1}{n} \sum_{i=1}^n \|v^l(x_i) - v_{\text{goal}}^l(x_i)\|^2 = \min_{\delta\theta} \frac{1}{n} \|V^l(X, \delta\theta) - V_{\text{goal}}^l(X)\|_{\text{Tr}}^2 \quad (4) $$

where $||.||$ stands for the $L_2$ norm, $||.||_{\text{Tr}}$ for the Frobenius norm, and $V^l(X, \delta\theta)$ is the activity update resulting from parameter change $\delta\theta$ as defined in previous section. In the two following parts we fix the minibatch $X$ and simplify notations accordingly by removing the dependency on $X$. Proofs of this section are deferred to Appendix C.

## 3.1 Best move without modifying the architecture of the network

Let $\delta W_l^*$ be the solution of Equation (4) when the parameter variation $\delta\theta$ is restricted to involve only layer $l$ parameters, i.e. $W_l$. This move is sub-optimal in that it does not result from an update of all architecture parameters but only of the current layer ones. In this case the activity update simplifies as $V^l(W_l) = \delta W_l B_{l-1}$ and the problem becomes:

$$ \delta W_l^* = \arg\min_{\delta W} \frac{1}{n} \|V^l(\delta W) - V_{\text{goal}}^l\|_{\text{Tr}}^2. \quad (5) $$

**Proposition 3.1.** The solution of Problem equation 5 is: $\delta W_l^* = \frac{1}{n} V_{\text{goal}}^l B_{l-1}^T (\frac{1}{n} B_{l-1} B_{l-1}^T)^+ \text{ where } P^+$ denotes the pseudoinverse of matrix $P$.

This update $\delta W_l^*$ is not equivalent to the usual gradient descent update, whose form is $\delta W_l^{\text{GD}} \propto V_{\text{goal}}^l B_{l-1}^T$. In fact the associated activity variation, $\delta W_l^* B_{l-1}$, is the projection of $V_{\text{goal}}^l$ on the post-activation matrix
<figure><img src="image_5.png" /><figcaption>Figure 3: Adding one neuron to layer $l$ in cyan ($K=1$), with connections in cyan. Here, $\alpha \in \mathbb{R}^5$ and $\omega \in \mathbb{R}^3$.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 4: Sum of functional moves</figcaption></figure>

The added neurons could be chosen randomly, as in usual neural network initialization, but this would not yield any guarantee regarding the impact on the system loss. Another possibility would be to set either input weights $(\alpha_k)_{k=1}^K$ or output weights $(\omega_k)_{k=1}^K$ to 0, so that the function $f_\theta(\cdot)$ would not be modified, while its gradient w.r.t. $\theta$ would be enriched from the new parameters. Another option is to solve an optimization problem as in the previous section with the modified structure $\theta \leftarrow \theta \oplus \theta_{\leftrightarrow}^K$ and jointly search for both the optimal new parameters $\theta_{\leftrightarrow}^K$ and the optimal variation $\delta W_l$ of the old ones:

$$ \arg\min_{\theta_{\leftrightarrow}^K, \delta W_l} \| V^l(\delta W_l \oplus \theta_{\leftrightarrow}^K) - V_{\text{goal}}^l \|_{\text{Tr}}^2 \quad (4) $$

As shown in figure 4, the displacement $V^l$ at layer $l$ is actually a sum of the moves induced by the neurons already present ($\delta W_l$) and by the added neurons ($\theta_{\leftrightarrow}^K$), our problem rewrites as :

$$ \arg\min_{\theta_{\leftrightarrow}^K, \delta W_l} \left\| V^l(\theta_{\leftrightarrow}^K) + V^l(\delta W_l) - V_{\text{goal}}^l \right\|_{\text{Tr}}^2 \quad (5) $$

with $v^l(x, \theta_{\leftrightarrow}^K) := \sum_{k=1}^K \omega_k (b_{l-2}(x))^T \alpha_k$ (See A.5). We choose $\delta W_l$ as the best move of already-existing parameters as defined in Proposition 3.1 and we note $V_{\text{goal} \text{proj}}^l := V_{\text{goal}}^l - V^l(\delta W_l^*)$. We are looking for the solution $(K^*, \theta_{\leftrightarrow}^{K*})$ of the optimization problem :

$$ \arg\min_{K, \theta_{\leftrightarrow}^K} \left\| V^l(\theta_{\leftrightarrow}^K) - V_{\text{goal} \text{proj}}^l \right\|_{\text{Tr}}^2 . \quad (6) $$

This quadratic optimization problem can be solved thanks to the low-rank matrix approximation theorem (Eckart & Young, 1936), using matrices $N := \frac{1}{n} B_{l-2} (V_{\text{goal} \text{proj}}^l)^T$ and $S := \frac{1}{n} B_{l-2} B_{l-2}^T$. As $S$ is semi-positive definite, let its truncated SVD be $S = U \Sigma U^T$, and define $S^{-\frac{1}{2}} := U \sqrt{\Sigma}^{-1} U^T$, with the convention that the inverse of 0 eigenvalues is 0. Finally, consider the truncated SVD of matrix $S^{-\frac{1}{2}} N = \sum_{k=1}^R \lambda_k u_k v_k^T$, where $R$ is the rank of the matrix $S^{-\frac{1}{2}} N$. Then:

**Proposition 3.2.** The solution of Problem (6) is:

* optimal number of neurons: $K^* = R$

* their optimal weights: $\theta_{\leftrightarrow}^{K*} = (\alpha_k^*, \omega_k^*)_{k=1}^{K*} = (\text{sign}(\lambda_k) \sqrt{|\lambda_k|} S^{-\frac{1}{2}} u_k, \sqrt{|\lambda_k|} v_k)_{k=1}^{K*}$

Moreover for any number of neurons $K \le R$, and associated weights $\theta_{\leftrightarrow}^{K,*}$, the expressivity gain and the first order in $\eta$ of the loss improvement due to the addition of these $K$ neurons are equal and can be quantified very simply as a function of the singular values $\lambda_k$:

$$ \Psi_{\theta \oplus \theta_{\leftrightarrow}^{K,*}}^l = \Psi_{\theta}^l - \sum_{k=1}^{K} \lambda_k^2 \quad \text{and} \quad \mathcal{L}(f_{\theta \oplus \theta_{\leftrightarrow}^{K,*}}) = \mathcal{L}(f_{\theta}) + \frac{\sigma_l'(0)}{\eta} \sum_{k=1}^{K} \lambda_k^2 + o(||\theta_{\leftrightarrow}^{K,*}||^2) $$
<figure><img src="image_4.png" /><figcaption>Figure 3: Adding one neuron to layer $l$ in cyan ($K = 1$), with connections in cyan. Here, $\alpha \in \mathbb{R}^5$ and $\omega \in \mathbb{R}^3$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 4: Sum of functional moves</figcaption></figure>

of layer $l-1$, that is to say onto the span of all possible post-activation directions, through the projector $\frac{1}{n}B_{l-1}^T(\frac{1}{n}B_{l-1}B_{l-1}^T)^+B_{l-1}$. To increase expressivity if needed, we will aim at increasing this span with the most useful directions to close the gap between this best update and the desired one. Note that the update $\delta W_l^*$ consists of a standard gradient ($V_{\text{goal}}^l B_{l-1}^T$) followed by a change of metric in the pre-activation space as an application of $(\frac{1}{n}B_{l-1}B_{l-1}^T)^+$, a structure which is reminiscent of the natural gradient.

## 3.2 Reducing expressivity bottleneck by modifying the architecture

To get as close as possible to $V_{\text{goal}}^l$ and to increase the expressive power of the current neural network, we modify each layer of its structure. At layer $l-1$, we add $K$ neurons $n_1, ..., n_K$ with input weights $\alpha_1, ..., \alpha_K$ and output weights $\omega_1, ..., \omega_K$ (cf. Figure 3). We have the following expansions by concatenation: $W_{l-1}^T \leftarrow (W_{l-1}^T \quad \alpha_1 \quad ... \quad \alpha_K)$ and $W_l \leftarrow (W_l \quad \omega_1 \quad ... \quad \omega_K)$. We note this architecture modification $\theta \leftarrow \theta \oplus \theta_{\leftrightarrow}^K$ where $\oplus$ is the concatenation sign and $\theta_{\leftrightarrow}^K := (\alpha_k, \omega_k)_{k=1}^K$ are the $K$ added neurons.

The added neurons could be chosen randomly, as in usual neural network initialization, but this would not yield any guarantee regarding the impact on the system loss. Another possibility would be to set either input weights $(\alpha_k)_{k=1}^K$ or output weights $(\omega_k)_{k=1}^K$ to 0, so that the function $f_{\theta}(\cdot)$ would not be modified, while its gradient w.r.t. $\theta$ would be enriched from the new parameters. Another option is to solve an optimization problem as in the previous section with the modified structure $\theta \leftarrow \theta \oplus \theta_{\leftrightarrow}^K$ and jointly search for both the optimal new parameters $\theta_{\leftrightarrow}^K$ and the optimal variation $\delta W$ of the old ones:

$$ \arg\min_{\theta_{\leftrightarrow}^K, \delta W} \frac{1}{n} \left\| V^l(\delta W \oplus \theta_{\leftrightarrow}^K) - V_{\text{goal}}^l \right\|_{\text{Tr}}^2. \qquad (6) $$

As shown in Figure 4, the displacement $V^l$ at layer $l$ is actually a sum of the moves induced by the neurons already present ($\delta W$) and by the added neurons ($\theta_{\leftrightarrow}^K$). Our problem rewrites as :

$$ \arg\min_{\theta_{\leftrightarrow}^K, \delta W} \frac{1}{n} \left\| V^l(\theta_{\leftrightarrow}^K) + V^l(\delta W) - V_{\text{goal}}^l \right\|_{\text{Tr}}^2 \qquad (7) $$

with $v^l(x, \theta_{\leftrightarrow}^K) := \sum_{k=1}^K \omega_k (b_{l-2}(x))^T \alpha_k$ (see A.5). We choose $\delta W$ as the best move of already-existing parameters as defined in Proposition 3.1 and we note $V_{\text{goal,proj}}^l := V_{\text{goal}}^l - V^l(\delta W^*)$. We are looking for the solution $(K^*, \theta_{\leftrightarrow}^{K*})$ of the optimization problem :

$$ \arg\min_{K, \theta_{\leftrightarrow}^K} \frac{1}{n} \left\| V^l(\theta_{\leftrightarrow}^K) - V_{\text{goal,proj}}^l \right\|_{\text{Tr}}^2. \qquad (8) $$

One should note that Problems (7) and (8) are generally not equivalent, though similar (cf. C.4). This quadratic optimization problem can be solved thanks to the low-rank matrix approximation theorem
**Proposition 3.3.** If S is positive definite, then solving (5) is equivalent to taking $\omega_k = N\alpha_k$ and finding the K first eigenvectors $\alpha_k$ associated to the K largest eigenvalues $\lambda$ of the generalized eigenvalue problem :

$$NN^T\alpha_k = \lambda S\alpha_k$$

**Corollary 1.** For all integers $m, m'$ such that $m + m' \le R$, at order one in $\eta$, adding $m + m'$ neurons simultaneously according to the previous method is equivalent to adding $m$ neurons then $m'$ neurons by applying successively the previous method twice.

*Note*: Problems (5) and (6) are generally not equivalent, though similar (cf C.4).

*Note 2*: Minimizing the distance (4), ie the distance between $V_{\text{goal}}^l$ and $V^l$, is equivalent to minimizing the loss $\mathcal{L}$ at order one in $V^l$:

$$\mathcal{L}(f_{\theta \oplus \theta_{\leftarrow K}}) \approx \mathcal{L}(f_{\theta}) - \frac{\sigma'_{l-1}(0)}{\eta n} \langle V_{\text{goal}}^l, V^l \rangle_{\text{Tr}} \quad (7)$$

The family $\{V^{l+1}((\alpha_k, \omega_k))\}_{k=1}^K$ of pre-activity variations induced by adding the neurons $\theta_{\leftarrow K,*}$ is orthogonal for the trace scalar product. We could say that the added neurons are orthogonal to each other (and to the already-present ones) in that sense. Interestingly, the GradMax method (Evci et al., 2022) also aims at minimizing the loss 7, but without avoiding redundancy (see Appendix B.1 for more details).

**Addition of new neurons.** In practice before adding new neurons $(\alpha, \omega)$, we multiply them by an amplitude factor $\gamma$ found by a simple line search (see Appendix D.3), i.e. we add $(\sqrt{\gamma}\alpha, \sqrt{\gamma}\omega)$. The addition of each neuron $k$ has an impact on the loss of the order of $\gamma\lambda_k^2$ provided $\gamma$ is small. This performance gain could be used in a selection criterion realizing a trade-off with computational complexity. A selection based on statistical significance of singular values can also be performed. The full algorithm and its complexity are detailed in Appendices D.4 and D.5.

# 4 ABOUT GREEDY GROWTH SUFFICIENCY

One might wonder whether a greedy approach on layer growth might get stuck in a non-optimal state. We derive the following series of propositions in this regard. Since in this work we add neurons layer per layer independently, we study here the case of a single hidden layer network, to spot potential layer growth issues. For the sake of simplicity, we consider the task of least square regression towards an explicit continuous target $f^*$, defined on a compact set. That is, we aim at minimizing the loss:

$$\inf_f \sum_{x \in \mathcal{D}} \|f(x) - f^*(x)\|^2$$

where $f(x)$ is the output of the neural network and $\mathcal{D}$ is the training set.

**Proposition 4.1 (Greedy completion of an existing network).** If $f$ is not $f^*$ yet, then there exists a set of neurons to add to the hidden layer such that the new function $f'$ will have a lower loss than $f$.

One can even choose the added neurons such that the loss is arbitrarily well minimized. Furthermore:

**Proposition 4.2 (Greedy completion by one single neuron).** If $f$ is not $f^*$ yet, there exists a neuron to add to the hidden layer such that the new function $f'$ will have a lower loss than $f$.

As a consequence, there exists no situation where one would need to add many neurons simultaneously to decrease the loss: it is always feasible with a single neuron. One can express a lower bound on how much the loss has improved (for the best such neuron), but it is not a very good bound without further assumptions on $f$. Furthermore, finding the optimal neuron to add is actually NP-hard (Bach, 2017), so we will not necessarily search for the optimal one.

**Proposition 4.3 (Greedy completion by one infinitesimal neuron).** The neuron in the previous proposition can be chosen to have arbitrarily small input weights.

This detail is important in that our approach is based on the tangent space of the function $f$ and thus manipulates infinitesimal quantities. Our optimization problem indeed relies on the linearization of the activation function by requiring the added neuron to have infinitely small input weights, to make the problem easier to solve. This proposition confirms that such neuron exists indeed.
(Eckart & Young, 1936), using matrices $N := \frac{1}{n}B_{l-2}(V_{goal\,proj}^l)^T$ and $S := \frac{1}{n}B_{l-2}B_{l-2}^T$. As $S$ is positive semi-definite, let its SVD be $S = O\Sigma O^T$, and define $S^{-\frac{1}{2}} := O\sqrt{\Sigma^{-1}}O^T$, with the convention that the inverse of 0 eigenvalues is 0. Finally, consider the SVD of matrix $S^{-\frac{1}{2}}N = \sum_{k=1}^R \lambda_k u_k v_k^T$, where $R$ is the rank of the matrix $S^{-\frac{1}{2}}N$. Then:

**Proposition 3.2.** The solution of Problem (8) is:

* optimal number of neurons: $K^* = R$

* their optimal weights: $\theta_{\leftrightarrow}^{K^*} = (\alpha_k^*, \omega_k^*)_{k=1}^{K^*} = (\sqrt{\lambda_k}S^{-\frac{1}{2}}u_k, \sqrt{\lambda_k}v_k)_{k=1}^{K^*}$

Moreover for any number of neurons $K \le R$, and associated optimal weights $\theta_{\leftrightarrow}^{K^*}$ consisting of the first $K$ neurons of $\theta_{\leftrightarrow}^{K^*}$, the expressivity gain can be quantified very simply as a function of the singular values $\lambda_k$:

$$ \Psi_{\theta \oplus \theta_{\leftrightarrow}^{K^*}}^l = \Psi_{\theta}^l - \sum_{k=1}^{K} \lambda_k^2 \quad (9) $$

where $\Psi_{\theta}^l$ is the expressivity bottleneck (defined in Eq. (4)). For convolutional layers instead of fully-connected ones, Equation (9) becomes an inequality ($\le$).

In practice before adding new neurons $(\alpha, \omega)$, we multiply them by an amplitude factor $\gamma$ found by a simple line search (see Appendix E.3), i.e. we add $(\sqrt{\gamma}\alpha, \sqrt{\gamma}\omega)$. The addition of each neuron $k$ has an impact on the bottleneck of the order of $\gamma\lambda_k^2$ provided $\gamma$ is small. We observe the same phenomenon with the loss as stated in the next proposition:

**Proposition 3.3.** For $\gamma > 0$, solving (8) using $V_{goal\,proj} = V_{goal} - V(\gamma\delta W^*)$ is equivalent to minimizing the loss $\mathcal{L}$ at order one in $\gamma V^l$. Furthermore, performing an architecture update with $\gamma\delta W^*$ (5) and a neuron addition with $\gamma\theta_{\leftrightarrow}^{K^*}$ (3.2) has an impact on the loss at first order in $\gamma$ as:

$$ \mathcal{L}(f_{\theta \oplus \gamma \theta_{\leftrightarrow}^{K^*}}) := \frac{1}{n} \sum_{i=1}^{n} \ell(f_{\theta \oplus \gamma \theta_{\leftrightarrow}^{K^*}}(\mathbf{x}_i), \mathbf{y}_i) = \mathcal{L}(f_{\theta}) - \gamma (\sigma'_{l-1}(0)\Delta_{\theta_{\leftrightarrow}^{K^*}} + \Delta_{\delta W^*}) + o(\gamma) \quad (10) $$

with

$$ \Delta_{\theta_{\leftrightarrow}^{K^*}} := \frac{1}{n} \langle V_{goal\,proj}^l, V^l(\theta_{\leftrightarrow}^{K^*}) \rangle_{\text{Tr}} = \sum_{k=1}^{K} \lambda_k^2 \quad (11) $$

$$ \Delta_{\delta W^*} := \frac{1}{n} \langle V_{goal}^l, V^l(\delta W^*) \rangle_{\text{Tr}} \ge 0. \quad (12) $$

The $\lambda_k$ could be used in a selection criterion realizing a trade-off with computational complexity. A selection based on statistical significance of singular values can also be performed. The full algorithm and its complexity are detailed in Appendices E.4 and E.5. We finish this section by some additional propositions and remarks.

**Proposition 3.4.** If $S$ is positive definite, then solving (8) is equivalent to taking $\omega_k = N\alpha_k$ and finding the $K$ first eigenvectors $\alpha_k$ associated to the $K$ largest eigenvalues $\lambda$ of the generalized eigenvalue problem:

$$ NN^T\alpha_k = \lambda S\alpha_k. $$

**Corollary 1.** For all integers $m, m'$ such that $m + m' \le R$, at order one in $V$, adding $m + m'$ neurons simultaneously according to the previous method is equivalent to adding $m$ neurons then $m'$ neurons by applying successively the previous method twice.

One should also note that the family $\{V^{l+1}((\alpha_k, \omega_k))\}_{k=1}^K$ of pre-activity variations induced by adding the neurons $\theta_{\leftrightarrow}^{K^*}$ is orthogonal for the trace scalar product. We could say that the added neurons are orthogonal to each other (and to the already-present ones) in that sense. Interestingly, the GradMax method (Evci et al., 2022) also aims at minimizing the loss 10, but without avoiding redundancy (see Appendix B.1 for more details).
**Correlations and higher orders.** Note that, as a matter of fact, our approach exploits linear correlations between inputs of a layer and desired output variations. It might happen that the loss is not minimized yet but there is no such correlation to exploit anymore. In that case the optimization problem (6) will not find neurons to add. Yet following Prop. 4.3 there does exist a neuron with arbitrarily small input weights that can reduce the loss. This paradox can be explained by pushing further the Taylor expansion of that neuron output in terms of weight amplitude (single factor $\epsilon$ on all of its input weights), for instance $\sigma(\epsilon\alpha \cdot x) \approx \sigma(0) + \sigma'(0)\epsilon\alpha \cdot x + \frac{1}{2}\sigma''(0)\epsilon^2(\alpha \cdot x)^2 + O(\epsilon^3)$. Though the linear term $\alpha \cdot x$ might be uncorrelated over the dataset with desired output variation, i.e. $E_{x \sim D}[\alpha \cdot x] = 0$, the quadratic term $(\alpha \cdot x)^2$, or higher-order ones otherwise, might be correlated. Finding neurons with such higher-order correlations can be done by increasing accordingly the power of $(\alpha \cdot x)$ in the optimization problem (5). Note that one could consider other function bases than the polynomials from Taylor expansion. In all cases, one does not need to solve such problems exactly but just to find an approximate solution, i.e. a neuron improving the loss.

**Adding random neurons.** Another possibility to suggest additional neurons, when expressivity bottlenecks are detected but no correlation (up to order $p$) can be exploited anymore, is to add random neurons. The first $p$ order Taylor expansions will show 0 correlation with desired output variation, hence no loss improvement nor worsening, but the correlation of the $p+1$-th order will be non-0, with probability 1, in the spirit of random projections. Furthermore, in the spirit of common neural network training practice, one could consider brute force combinatorics by adding many random neurons and hoping some will be close enough to the desired direction (Frankle & Carbin, 2018). The difference with usual training is that we would perform such computationally-costly searches only when and where relevant, exploiting all simple information first (linear correlations in each layer).

# 5 RESULTS

## 5.1 COMPARISON WITH GRADMAX ON CIFAR-100

The closest growing method to TINY is GradMax Evci et al. (2022), as it solves a quadratic problem similar to 6. By construction, the objective of GradMax is to decrease the loss as fast as possible considering an infinitesimal increment of new neurons. In fact, this method is equivalent to ours, with the main difference that GradMax does not take into account the expressivity of the current architecture as TINY does in 6 by projecting $v_{goal}$. In-depth details about the difference between the GradMax and TINY are provided in B.1.

In this section, we show on the CIFAR-100 dataset that solving (6) instead of B.1(defined by Grad-Max) to grow a network allows better final performance and almost full expressivity power. To do so, we have re-implemented the GradMax method and mimicked its growing process which consists in increasing the architecture of a shallow ResNet18$_s$ until it reaches the architecture of the usual ResNet18. This process is described in the pseudo code 1, where two parameters can be chosen : the starting architecture of the model of the usual ResNet18 architecture 3 ($s = 1/4$ or $s = 1/64$) and the time of training between each neurons addition ($\Delta t = 1$ or $\Delta t = 0.25$). Then the number of parameters and the performance of the growing network are evaluated at regular intervals to plot Figure 5.

Once the models have reached the final architecture ResNet18, they are trained for 250 epochs (or 500 epochs if they have not converged on the training set). We have summarized the final performance in table 1. We also added the column Reference, which gives the performance of a ResNet18 trained from scratch by usual gradient descent with all its neurons. We do not expect TINY or GradMax to achieve the performance of the reference as its architecture and optimisation process have been optimised for years.

The details of the protocol can be found in the annexes E.1, as well as other technical details such as the dynamic of the learning batch size D.2, the number of examples used to solve the expressivity bottleneck 6 and the complexity of the algorithms D.5. For both methods, all the latter apply so that the main differences between GradMax and TINY is the mathematical definition of the new neurons.

For $s = 1/64$, we observe a significant difference in performance between TINY and GradMax methods. While TINY models almost achieve the reference's performance, they remain stuck 10 points below with GradMax. It suggests that starting with an architecture far from full expressivity,
# 4 About greedy growth sufficiency and TINY convergence

One might wonder whether a greedy approach on layer growth might get stuck in a non-optimal state. By greedy we mean that every neuron added has to decrease the loss. Since in this work we add neurons layer per layer independently, we study here the case of a single hidden layer network, to spot potential layer growth issues. For the sake of simplicity, we consider the task of least square regression towards an explicit continuous target $f^*$, defined on a compact set. That is, we aim at minimizing the loss:

$$ \inf_{f} \sum_{x \in \mathcal{D}} \|f(x) - f^*(x)\|^2 \qquad (13) $$

where $f(x)$ is the output of the neural network and $\mathcal{D}$ is the training set. Proofs and supplementary propositions are deferred to Appendix D, in particular D.4 and D.7.

First, if one allows only adding neurons but no modification of already existing ones:

**Proposition 4.1** (Exponential convergence to 0 training error by ReLU neuron additions). It is possible to decrease the loss exponentially fast with the number $t$ of added neurons, i.e. as $\gamma^t \mathcal{L}(f)$, towards 0 training loss, and this in a greedy way, that is, such that each added neuron decreases the loss. The factor $\gamma$ is $\gamma = 1 - \frac{1}{n^2 d'} (\frac{d_m}{d_M})^2$, where $d_m$ and $d_M$ are quantities solely dependent on the dataset geometry, $d'$ is the output dimension of the network, and $n$ is the dataset size.

In particular, there exists no situation where one would need to add many neurons simultaneously to decrease the loss: it is always feasible with a single neuron.

TINY might get stuck when no correlation between inputs $x_i$ and desired output variations $f^*(x_i) - f(x_i)$ can be found anymore. To prevent this, one can choose an auxiliary method to add neurons in such cases, for instance random neurons (with a line search over their amplitude, cf. Appendix D.3), or locally-optimal neurons found by gradient descent, or solutions of higher-order expressivity bottleneck formulations using further developments of the activation function. We will name completed-TINY the completion of TINY by any such auxiliary method.

Now, if we also update already existing weights when adding new neurons, we get a stronger result:

**Proposition 4.2** (Completed-TINY reaches 0 training error in at most $n$ neuron additions). Under certain assumptions (full batch optimization, updating already existing parameters, and, more technically: polynomial activation function of order $\ge n^2$), completed-TINY reaches 0 training error in at most $n$ neuron additions almost surely.

Hence we see the importance of updating existing parameters on the convergence speed. This optimization protocol is actually the one we follow in practice when training neural networks with TINY (except when comparing with other methods using their protocol).

Note that our approach shares similarity with gradient boosting Friedman (2001) somehow, as we grow the architecture based on the gradient of the loss. Note also that finding the optimal neuron to add is actually NP-hard (Bach, 2017), but that we do not need new neuron optimality to converge to 0 training error.

# 5 Results

## 5.1 Comparison with GradMax on CIFAR-100

The closest growing method to TINY is GradMax (Evci et al. (2022)), as it solves a quadratic problem similar to (8). By construction, the objective of GradMax is to decrease the loss as fast as possible considering an infinitesimal increment of new neurons. The main difference is that GradMax does not take into account the expressivity of the current architecture as TINY does in (8) by projecting $v_{goal}$. In-depth details about the difference between the GradMax and TINY are provided in Appendix B.1.

In this section, we show on the CIFAR-100 dataset that solving (8) instead of (23) (defined by GradMax) to grow a network using a naive strategy allows better final performance and almost full expressive power.
<figure><img src="image_7.png" /><figcaption>Figure 5: Accuracy on test of as a function of the number of parameters during architecture growth from ResNet$_s$ to ResNet18. The left (resp. right) column is for the starting architecture ResNet$_{1/4}$(resp. ResNet$_{1/64}$). The upper (resp. lower) row is for $\Delta t$ equal to 0.25 (resp. 1) epoch.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 6: Evolution of accuracy and number of parameters as a function of gradient step for the setting $\Delta t = 1$, $s = 1/64$ for TINY and GradMax, mean and standard deviation over two runs. Other settings in the annexes 13</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Figure 5: Test accuracy as a function of the number of parameters during architecture growth from ResNet$_s$ to ResNet18. The starting architecture in the left (resp. right) column is ResNet$_{1/4}$ (resp. ResNet$_{1/64}$). The amount of training time $\Delta t$ between consecutive neuron additions in the upper (resp. lower) row is 0.25 (resp. 1) epoch. Statistics over 4 runs are performed for each setting.</figcaption></figure>

To do so, we have re-implemented the GradMax method and mimicked its growing process which consists in increasing the architecture of a thin ResNet18 until it reaches the architecture of the usual ResNet18. This process is described in the pseudo code 1, where two parameters can be chosen : the relative thinness $s$ of the starting architecture, w.r.t. the usual ResNet18 architecture ($s = 1/4$ or $s = 1/64$, cf. Table 3), and the amount of training time between consecutive neuron additions ($\Delta t = 1$ or $\Delta t = 0.25$ epochs). Then the number of parameters and the performance of the growing network are evaluated at regular intervals to plot Figure 5. We note that both methods reach their final accuracy within less than one GPU day, outperforming by far other NAS search methods in their category (cf. Table 5).

Once the models have reached the final architecture ResNet18, they are trained for 250 more epochs (or 500 epochs if they have not converged yet) on the training set. We have summarized the final performance in Table 1. We also added the column *Reference*, which gives the performance of a ResNet18 trained from scratch by usual gradient descent with all its neurons. We do not expect TINY or GradMax to achieve the performance of the reference as its architecture and optimisation process have been optimised for years. The column *Small references* corresponds to the training of the architecture ResNet18$_s$ for $s = 1/4$ and $s = 1/64$ using standard gradient descent without any increase in architecture.

The details of the protocol can be found in the annexes F.1, as well as other technical details such as the dynamic of the training batch size E.2, the normalization of the new neurons E.3, the number of examples used to estimate and solve the expressivity bottleneck E.1 and the complexity of the algorithms E.5. For both methods, all the latter apply so that the main differences between GradMax and TINY in this experiment is the mathematical definition of the new neurons.

For $s = 1/64$, we observe a significant difference in performance between TINY and GradMax methods. While TINY models almost achieve the reference's performance, GradMax remains stuck 10 points below. This suggests that the framework proposed by GradMax is not sufficient to be able to start with an archi-
<table><caption>Table 1: Final accuracy on test of ResNet18 after the architecture growth (grey) and after convergence (black). The number of start indicated grossly the multiple of 50 epochs needed to achieve convergence. With the starting architecture ResNet$_{1/64}$ and $\Delta t = 0.25$ the method TINY achieves $66.0 \pm 0.1$ on test after its growth and it reaches $69.0 \pm 0.1$ $5*$ after $5*$ := $5 \times 50$ epochs (examples of training curves for the extra training 14). Mean and standard deviation performed on 2 runs for each setting.</caption><thead><tr><th rowspan="2">s</th><th colspan="2">TINY</th><th colspan="2">GradMax</th><th rowspan="2">Reference</th></tr><tr><th>0.25</th><th>1</th><th>0.25</th><th>1</th></tr></thead><tbody><tr><th>1/4</th><td>67.0 ± 0.1</td><td>71.0 ± 0.1</td><td>65.0 ± 0.1</td><td>69.0 ± 0.1</td><td rowspan="4">72.9 ± 0.1<sup>5*</sup></td></tr><tr><th>1/4</th><td>70.0 ± 0.2<sup>5*</sup></td><td><b>71.0 ± 0.2<sup>5*</sup></b></td><td>67.0 ± 0.2<sup>5*</sup></td><td>69.0 ± 0.1<sup>5*</sup></td></tr><tr><th>1/64</th><td>66.0 ± 0.1</td><td>68.0 ± 0.4</td><td>45.0 ± 0.2</td><td>57.0 ± 0.2</td></tr><tr><th>1/64</th><td>69.0 ± 0.1<sup>5*</sup></td><td><b>69.0 ± 0.6<sup>5*</sup></b></td><td>57.0 ± 0.3<sup>10*</sup></td><td>59.0 ± 0.1<sup>10*</sup></td></tr></tbody></table>

<figure><img src="image_9.png" /><figcaption>Figure 7: Evolution of accuracy and number of parameters as a function of gradient step for the setting $\Delta t = 1$, $s = 1/64$ during extra training for TINY and GradMax, mean and standard deviation over two runs. Other settings in the annexes 15 and 14.</figcaption></figure>

The ResNet$_{1/64}$, the theory proposed by GradMax is not sufficient and TINY is more robust. As for the setting $s = 1/4$, both methods seem equivalent in terms of final performance and achieve full expressivity.

The curves on Figure 6, which are extracted from Figure 13 in the annexes, show that TINY models have converged at the end of the growing process, while GradMax ones do not. This latter effects contrast with GradMax formulation which is to accelerate the gradient descent as fast as possible by adding neurons. Furthermore GradMax need extra training to achieve full expressivity as for the particular setting $s = 1/64$, $\Delta t = 1$, the extra training time of GradMax is twice as high as TINY's, as shown in Figure 7. This need for extra training also appear in Table 1 where for all settings the difference in performance after and before extra training goes up to 20 % ($s = 1/64$, $\Delta t = 0.25$, resp. 6% for TINY).

## 5.2 COMPARISON WITH RANDOM ON CIFAR-100 : INITIALISATION IMPACT

In this section, we focus on the impact of the new neurons' initialization. To do so, we consider as a baseline the Random method, which initializes the new neurons according to a Gaussian distribution: $(\alpha_k^*, \omega_k^*)_{k=1}^K \sim N(0, I_d)$. Also, when adding new neurons, instead of normalizing them as previously, we search for the best scaling using a line-search on the loss. Thus, we perform the
<figure><img src="image_7.png" /><figcaption>Figure 6: Evolution of accuracy and number of parameters as a function of gradient steps for the setting $\Delta t = 1$, $s = 1/64$, for TINY and GradMax. Mean and standard deviations are estimated over four runs. Results with other settings can be found in Fig. 13 in the appendix.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 7: Evolution of accuracy as a function of epochs for the setting $\Delta t = 1$, $s = 1/64$ during extra training for TINY and GradMax. Mean and standard deviations are estimated over four runs. Results with other settings can be found in Figures 14 and 15 in the appendix.</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>Figure 8: Accuracy on test as a function of the number of parameters during architecture growth from ResNet$_{1/64}$ to ResNet$_{18}$.</figcaption></figure>

operation $\theta_{\leftarrow\leftarrow}^K \leftarrow \gamma^* \theta_{\leftarrow\leftarrow}^K 1$, with the amplitude factor $\gamma^* \in \mathbb{R}$ defined as :

$$ \gamma^* := \arg \min_{\gamma \in [-L, L]} \sum_i \mathcal{L}(f_{\theta \oplus \gamma \theta_{\leftarrow\leftarrow}^K}(\mathbf{x}_i), \mathbf{y}_i) \quad \text{with} \quad \gamma \theta_{\leftarrow\leftarrow}^K = (\gamma \alpha_k^*, \gamma \omega_k^*)^K \quad (8) $$

with $L$ a positive constant. More details can be found in D.3.2. With such an amplitude factor, one can measure the quality of the directions generated by TINY and Random by quantifying the decrease of loss.

To better measure the impact of the initialisation method, and to distinguish it from the optimization process, we do not perform any gradient descent. This contrasts with the previous section where long training time after architecture growth was modifying the direction of the added neurons, dampening initialization impact with training time, especially as they were added with a small amplitude factor (cf Section D.3.1).

With these two modifications to the protocol of previous section, we obtain Figure 8. We see the crucial impact of TINY initialization over the Random method. Indeed, the random method does not learn through the growing process and it can be quantified as follows. In the random setting, we models $v(\mathbf{X})$, $v_{\text{goal}}(\mathbf{X})$ as independent Gaussian variable following $N(0_d, I_d \frac{1}{\sqrt{d}})$ where $d$ approximate the dimension of $v_{\text{goal}}$ and $v$. From equation 7, the scalar product $\langle V(\mathbf{X}), V_{\text{goal}}(\mathbf{X}) \rangle := \frac{1}{n} \sum_i v_{\text{goal}}(\mathbf{x}_i)^T v(\mathbf{x}_i)$ is a proxy of the expected decrease of loss after each architecture growth. This quantity can be approximated by its standard deviation, ie $\frac{1}{\sqrt{d}}$ and therefore making the expected gain of loss comparable to to $\frac{1}{\sqrt{64}}$ for the first layer and $\frac{1}{\sqrt{512}}$ for the last layer.

A first supplementary remarks is that the search interval of equation 8 for can be shrunk to $[0, L]$ as the first order development of the loss in equation 7 is positive. This property is the direct consequence of the definition of $V^*$ as the minimizer of the expressivity bottleneck equation 6. One can also note that we do not include GradMax in Figure 8, because its protocol initializes the on-going weight to zero ($\alpha_k \leftarrow 0$) and imposes a small norm on its out-going weights ($||\omega_k|| = \epsilon$). Those two aspects make the amplitude factor $\gamma^*$ meaningless and the impact of the new neurons initialization invisible without gradient descent.

The code and the DEMO-notebook are available at https://gitlab.inria.fr/mverbock/tinypub.
<table><caption>Table 1: Final accuracy on test set of ResNet18 after architecture growth (grey) and after convergence (blue). The number of stars indicates the multiple of 50 epochs needed to achieve convergence. With the starting architecture ResNet$_{1/64}$ and $\Delta t = 0.25$, the method TINY achieves $65.8 \pm 0.1$ on test set after its growth and it reaches $69.5 \pm 0.2$ <sup>5*</sup> after $5* := 5 \times 50$ additional epochs (examples of training curves for the extra training can be found in Figure 14). Means and standard deviations are performed on 4 runs for each setting.</caption><thead><tr><th rowspan="2"></th><th rowspan="2">Δt</th><th colspan="2">TINY</th><th colspan="2">GradMax</th><th rowspan="2">Small<br>references</th><th rowspan="2">Reference</th></tr><tr><th>0.25</th><th>1</th><th>0.25</th><th>1</th></tr></thead><tbody><tr><td rowspan="2">s</td><td>1/4</td><td>67.2 ± 0.1</td><td>70.4 ± 0.2</td><td>65.1 ± 0.2</td><td>68.6 ± 0.1</td><td rowspan="2">68.6 ± 0.4 <sup>5*</sup></td><td rowspan="2">72.8 ±</td></tr><tr><td>1/4</td><td><span style="color:blue;">70.3 ± 0.2</span><sup>5*</sup></td><td><span style="color:blue;">70.9 ± 0.2</span><sup>5*</sup></td><td><span style="color:blue;">67.0 ± 0.2</span><sup>5*</sup></td><td><span style="color:blue;">69.0 ± 0.2</span><sup>5*</sup></td></tr><tr><td></td><td>1/64</td><td>65.8 ± 0.1</td><td>68.1 ± 0.5</td><td>45.0 ± 0.4</td><td>56.8 ± 0.2</td><td rowspan="2">63.4 ± 0.3 <sup>5*</sup></td><td rowspan="2">0.3 <sup>5*</sup></td></tr><tr><td></td><td>1/64</td><td><span style="color:blue;">69.5 ± 0.2</span><sup>5*</sup></td><td><span style="color:blue;">68.7 ± 0.6</span><sup>5*</sup></td><td><span style="color:blue;">57.0 ± 0.4</span><sup>10*</sup></td><td><span style="color:blue;">58.4 ± 0.2</span><sup>10*</sup></td></tr></tbody></table>

tecture far from full expressivity, i.e. ResNet$_{1/64}$, while TINY is able to handle it. As for the setting $s = 1/4$, both methods seem equivalent in terms of final performance and achieve full expressivity.

The curves on Figure 6, which are extracted from Figure 13 in the appendix, show that TINY models have converged at the end of the growing process, while GradMax ones have not. This latter effect contrasts with GradMax formulation which is to accelerate the gradient descent as fast as possible by adding neurons. Furthermore GradMax needs extra training to achieve full expressivity: for the particular setting $s = 1/64$, $\Delta t = 1$, the extra training time required by GradMax is twice as high as TINY's, as shown in Figure 7. This need for extra training also appears for all settings in Table 1. In particular for $s = 1/64$, $\Delta t = 0.25$, the difference in performance after and before extra training goes up to 20 % above the initial performance while it is only of 6% for TINY.

## 5.2 Comparison with Random on CIFAR-100 : initialisation impact

In this section, we focus on the impact of the new neurons' initialization. To do so, we consider as a baseline the Random method, which initializes the new neurons according to a Gaussian distribution: $(\alpha_k^*, \omega_k^{*})_{k=1}^K \sim \mathcal{N}(0, I_d)$ or a uniform distribution $U[-1, 1]$. Also, when adding new neurons, we now search for the best scaling using a line-search on the loss. Thus, we perform the operation $\theta_{\leftarrow}^K \leftarrow \gamma^* \theta_{\leftarrow}^K$, with the amplitude factor $\gamma^* \in \mathbb{R}$ defined as :

$$ \gamma^* := \arg \min_{\gamma \in [-L, L]} \sum_i \ell(f_{\theta \oplus \gamma \theta_{\leftarrow}^K}(\mathbf{x}_i), \mathbf{y}_i) \quad \text{with} \quad \gamma \theta_{\leftarrow}^K = (\gamma \alpha_k^*, \gamma \omega_k^{*})_{k=1}^K \quad (14) $$

with $L$ a positive constant. More details can be found in Appendix E.3.2 and in Algorithm 1. With such an amplitude factor, one can measure the quality of the directions generated by TINY and Random by quantifying the maximal decrease of loss in these directions.

To better measure the impact of the initialisation method, and to distinguish it from the optimization process, we do not perform any gradient descent. This contrasts with the previous section where long training time after architecture growth was modifying the direction of the added neurons, dampening initialization impact with training time, especially as they were added with a small amplitude factor (cf Section E.3.1).

With these two modifications to the protocol of previous section, we obtain Figure 8. We see the crucial impact of TINY initialization compared to the Random one. Indeed, TINY reaches more than 17% accuracy just by adding neurons (without any further update), which accounts for about one quarter of the total accuracy with the full method (69% in Table 1 using in plus gradient descent). On the opposite, the Random initialization does not contribute to the accuracy through the growing process (just about 1%); this can be explained and quantified as follows. To study the random setting, we can model $v(X)$ and $v_{\text{goal}}(X)$ as independent variables where $v_{\text{goal}} \sim \mathcal{N}(0_d, \frac{1}{d}I_d)$ and $v$ either $\sim \mathcal{N}(0_d, \frac{1}{d}I_d)$ or $\sim U[-\frac{1}{d}, \frac{1}{d}]$, $d$ being the dimension of $v_{\text{goal}}$ and $v$. From Equation (10), the scalar product $\langle V(X), V_{\text{goal}}(X) \rangle := \frac{1}{n} \sum_i v_{\text{goal}}(\mathbf{x}_i)^T v(\mathbf{x}_i)$ is a proxy for the expected decrease of loss after each architecture growth. This quantity can be approximated
# 6 CONCLUSION

We provided the theoretical principles of TINY, a method to grow the architecture of a neural net while training it; starting from a very thin architecture, TINY adds the neurons where needed and yields a fully trained architecture at the end. Our method relies on the functional gradient to find new directions that tackle the expressivity bottleneck, even for small networks, by expanding their space of parameters. This way, we combine in the same framework gradient descent and neural architecture search, that is optimizing the network parameters and its architectures at the same time.

The method is generic for all architectures and is instantiated for linear and convolutional layers. Extension to self-attention mechanism (transformers) is part of future works. Although the common architectures consist of a succession of layers, a new research direction is to develop tool handling general computational graphs (U-net, Inception, Dense-Net).

Another possible development would be to study the statistics reliability of the TINY method, for instance using tools borrowed from random matrix theory. Indeed statistical tests can be applied on intermediate computations to obtain the new neurons. An interesting byproduct of this approach would define a threshold to select neurons found by 3.2, based on statistical significance.

# REFERENCES

* Francis Bach. Breaking the curse of dimensionality with convex neural networks. *The Journal of Machine Learning Research*, 18(1):629–681, 2017.

* Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar. Designing neural network architectures using reinforcement learning. In *International Conference on Learning Representations*, 2017. URL https://openreview.net/forum?id=S1c2cvqee.

* Kateryna Bashtova, Mathieu Causse, Cameron James, Florent Masmoudi, Mohamed Masmoudi, Houcine Turki, and Joshua Wolff. Application of the topological gradient to parsimonious neural networks. In *Computational Sciences and Artificial Intelligence in Industry*, pp. 47–61. Springer, 2022.

* Pauline Bennet, Carola Doerr, Antoine Moreau, Jeremy Rapin, Fabien Teytaud, and Olivier Teytaud. Nevergrad: black-box optimization platform. *ACM SIGEV* *Olation*, 14(1):8–15, 2021.

* Mathieu Causse, Cameron James, Mohamed Slim Masmoudi, and Houcine Turki. Parsimonious neural networks. In *Cesar Conference*, 2019. URL https://www.cesar-conference.org/wp-content/uploads/2019/10/s5_p1_21_1330.pdf.

* Tianqi Chen, Ian Goodfellow, and Jonathon Shlens. Net2net: Accelerating learning via knowledge transfer. *arXiv preprint arXiv:1511.05641*, 2015.

* G. Cybenko. Approximation by superpositions of a sigmoidal function. *Mathematics of control, signals and systems*, 2(4):303–314, 1989.

* Bin Dai, Chen Zhu, Baining Guo, and David Wipf. Compressing neural networks using the variational information bottleneck. In *International Conference on Machine Learning*, pp. 1135–1144. PMLR, 2018.

* Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. *Psychometrika*, 1(3):211–218, September 1936. ISSN 1860-0980. doi: 10.1007/BF02288367. URL https://doi.org/10.1007/BF02288367.

* Utku Evci, Bart van Merrienboer, Thomas Unterthiner, Fabian Pedregosa, and Max Vladymyrov. Gradmax: Growing neural networks using gradient information. In *International Conference on Learning Representations*, 2022. URL https://openreview.net/forum?id=qjN4hWWUO.

* Harley Flanders. Differentiation under the integral sign. *The American Mathematical Monthly*, 80 (6):615–627, 1973. ISSN 00029890, 19300972. URL http://www.jstor.org/stable/2319163.

* Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Training pruned neural networks. *CoRR*, abs/1803.03635, 2018. URL http://arxiv.org/abs/1803.03635.
<figure><img src="image_9.png" /><figcaption>Figure 8: Test accuracy as a function of the number of parameters during pure architecture growth (no gradient steps performed, only neuron addition with a given initialization) from ResNet$_{1/64}$ to ResNet$_{18}$, averaged over four independent runs.</figcaption></figure>

by its standard deviation, ie $\frac{1}{\sqrt{n_d}}$, which makes the expected relative gain of loss (for a gradient step) of the order of magnitude of $\frac{1}{\sqrt{64}}$ for the first layer and $\frac{1}{\sqrt{512}}$ for the last layer when compared to the true gradient, and consequently when compared to TINY. Furthermore, one can take into account the effect of a line search over the random direction: in that case the expected relative loss gain is quadratic in the angle between the directions and therefore of the order of magnitude of $\frac{1}{64}$ or $\frac{1}{512}$ respectively (see Appendix D.3).

Note that the search interval of Equation (14) can be shrunk to $[0, L]$ with TINY initialization, as the first order development of the loss in Equation (10) is positive. This property is the direct consequence of the definition of $V^*$ as the minimizer of the expressivity bottleneck (Eq. (8)). One can also note that we do not include GradMax in Figure 8, because its protocol initializes the on-going weights to zero ($\alpha_k \leftarrow 0$) and imposes a small norm on its out-going weights ($||\omega_k|| = \varepsilon$). Those two aspects make the amplitude factor $\gamma^*$ meaningless and the impact of the new neurons initialization invisible without gradient descent.

The code is available at https://gitlab.inria.fr/mverbock/tinypub.

# 6 Conclusion

We provided the theoretical principles of TINY, a method to grow the architecture of a neural net while training it; starting from a very thin architecture, TINY adds neurons where needed and yields a fully trained architecture at the end. Our method relies on the functional gradient to find new directions that tackle the expressivity bottleneck, even for small networks, by expanding their space of parameters. This way, we combine in the same framework gradient descent and neural architecture search, that is, optimizing the network parameters and its architecture at the same time, and this, in a way that guarantees convergence to 0 training error, thus escaping expressivity bottlenecks indeed.

While transfer learning works well on ordinary tasks, for it to succeed, it needs to fine-tune and use large architectures at deployment in order to extract and manipulate common knowledge. Our method has the advantage of being generic and could also produce smaller models as it adapts the architecture to a single task.
Ariel Gordon, Elad Eban, Ofir Nachum, Bo Chen, Hao Wu, Tien-Ju Yang, and Edward Choi. Morphnet: Fast & simple resource-constrained structure learning of deep networks. In *Proceedings of the IEEE conference on computer vision and pattern recognition*, pp. 1586–1595, 2018.

Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), *Proceedings of the 36th International Conference on Machine Learning*, volume 97 of *Proceedings of Machine Learning Research*, pp. 2596–2604. PMLR, 09–15 Jun 2019a. URL https://proceedings.mlr.press/v97/hanin19a.html.

Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), *Advances in Neural Information Processing Systems*, volume 32. Curran Associates, Inc., 2019b. URL https://proceedings.neurips.cc/paper/2019/file/9766527f2b5d3e95d4a733fcfb77bd7e-Paper.pdf.

Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. *arXiv preprint arXiv:1503.02531*, 2015.

K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approximators. *Neural Networks*, 2(5):359–366, 1989.

Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), *Advances in Neural Information Processing Systems*, volume 31. Curran Associates, Inc., 2018. URL https://proceedings.neurips.cc/paper/2018/file/5a4be1fa34e62bb8a6ec6b91d2462f5a-Paper.pdf.

Andrei N Kolmogorov. Three approaches to the quantitative definition of information'. *Problems of information transmission*, 1(1):1–7, 1965.

Vladimir Koltchinskii. Rademacher penalties and structural risk minimization. *IEEE Transactions on Information Theory*, 47(5):1902–1914, 2001.

Ming Li, Paul Vitányi, et al. *An introduction to Kolmogorov complexity and its applications*, volume 3. Springer, 2008.

Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In *International Conference on Learning Representations*, 2019. URL https://openreview.net/forum?id=S1eYHoC5FX.

Zhengying Liu, Zhen Xu, Shangeth Rajaa, Meysam Madadi, Julio CS Jacques Junior, Sergio Escalera, Adrien Pavao, Sebastien Treguer, Wei-Wei Tu, and Isabelle Guyon. Towards automated deep learning: Analysis of the autodl challenge series 2019. In *NeurIPS 2019 Competition and Demonstration Track*, pp. 242–252. PMLR, 2020.

Christos Louizos, Karen Ullrich, and Max Welling. Bayesian compression for deep learning. *Advances in neural information processing systems*, 30, 2017.

Kaitlin Maile, Emmanuel Rachelson, Hervé Luga, and Dennis George Wilson. When, where, and how to add new neurons to ANNs. In *First Conference on Automated Machine Learning (Main Track)*, 2022. URL https://openreview.net/forum?id=SWOg-arIg9.

Hector Mendoza, Aaron Klein, Matthias Feurer, Jost Tobias Springenberg, and Frank Hutter. Towards automatically-tuned neural networks. In Frank Hutter, Lars Kotthoff, and Joaquin Van-schoren (eds.), *Proceedings of the Workshop on Automatic Machine Learning*, volume 64 of *Proceedings of Machine Learning Research*, pp. 58–65, New York, New York, USA, 24 Jun 2016. PMLR. URL https://proceedings.mlr.press/v64/mendoza_towards_2016.html.

Risto Miikkulainen, Jason Zhi Liang, Elliot Meyerson, Aditya Rawal, Daniel Fink, Olivier Francon, Bala Raju, Hormoz Shahrzad, Arshak Navruzyan, Nigel Duffy, and Babak Hodjat. Evolving deep neural networks. *CoRR*, abs/1703.00548, 2017. URL http://arxiv.org/abs/1703.00548.
It is already instantiated for linear and convolutional layers; extension to self-attention mechanisms (transformers) is part of future works. Although common architectures consist of a succession of layers, a research direction is to develop tools handling general computational graphs (such as U-net, Inception, Dense-Net), which offers the possibility to let the architecture graph grow and bypass manual design.

Another possible development would be to study the statistical reliability of the TINY method, for instance using tools borrowed from random matrix theory. Indeed statistical tests can be applied to the intermediate computations from which the new neurons are obtained. An interesting byproduct of this approach would be to define a threshold to select neurons found by Prop. 3.2, based on statistical significance.

# 7 Acknowledgments

The authors address their deepest thanks to Stella Douka, Andrei Pantea, Stéphane Rivaud & François Landes for the exchanges and discussions on this project.

This work was supported by grants ANR-22-CE33-0015-01 and ANR-17-CONV-0003 operated by LISN to Sylvain Chevallier and by ANR-20-CE23-0025 operated by Inria to Guillaume Charpiat. This work was also funded by the European Union under GA no. 101135782 (MANOLO project).

Numerical computation was enabled by the scientific Python ecosystem: Matplotlib Hunter (2007), Numpy Harris et al. (2020), Scipy Virtanen et al. (2020), pandas development team (2020), PyTorch Paszke et al. (2019).

# References

* Francis Bach. Breaking the curse of dimensionality with convex neural networks. *The Journal of Machine Learning Research*, 18(1):629–681, 2017.

* Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar. Designing neural network architectures using reinforcement learning. In *International Conference on Learning Representations*, 2017. URL https://openreview.net/forum?id=S1c2cvqee.

* Kateryna Bashtova, Mathieu Causse, Cameron James, Florent Masmoudi, Mohamed Masmoudi, Houcine Turki, and Joshua Wolff. Application of the topological gradient to parsimonious neural networks. In *Computational Sciences and Artificial Intelligence in Industry*, pp. 47–61. Springer, 2022.

* Pauline Bennet, Carola Doerr, Antoine Moreau, Jeremy Rapin, Fabien Teytaud, and Olivier Teytaud. Nevergrad: black-box optimization platform. *ACM SIGEVOLution*, 14(1):8–15, 2021.

* Mathieu Causse, Cameron James, Mohamed Slim Masmoudi, and Houcine Turki. Parsimonious neural networks. In *Cesar Conference*, 2019. URL https://www.cesar-conference.org/wp-content/uploads/2019/10/s5_p1_21_1330.pdf.

* Tianqi Chen, Ian Goodfellow, and Jonathon Shlens. Net2net: Accelerating learning via knowledge transfer. *arXiv preprint arXiv:1511.05641*, 2015.

* G. Cybenko. Approximation by superpositions of a sigmoidal function. *Mathematics of control, signals and systems*, 2(4):303–314, 1989.

* Bin Dai, Chen Zhu, Baining Guo, and David Wipf. Compressing neural networks using the variational information bottleneck. In *International Conference on Machine Learning*, pp. 1135–1144. PMLR, 2018.

* Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. *Psychometrika*, 1(3):211–218, September 1936. ISSN 1860-0980. doi: 10.1007/BF02288367. URL https://doi.org/10.1007/BF02288367.

* Utku Evci, Bart van Merrienboer, Thomas Unterthiner, Fabian Pedregosa, and Max Vladymyrov. Gradmax: Growing neural networks using gradient information. In *International Conference on Learning Representations*, 2022. URL https://openreview.net/forum?id=qjN4h_wwU0.
Geoffrey F. Miller, Peter M. Todd, and Shailesh U. Hegde. Designing neural networks using genetic algorithms. In *ICGA*, 1989.

Yann Ollivier. True asymptotic natural gradient optimization, 2017.

Allan Pinkus. Approximation theory of the mlp model in neural networks. *ACTA NUMERICA*, 8: 143–195, 1999.

Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. In Doina Precup and Yee Whye Teh (eds.), *Proceedings of the 34th International Conference on Machine Learning*, volume 70 of *Proceedings of Machine Learning Research*, pp. 2847–2854. PMLR, 06–11 Aug 2017. URL https://proceedings.mlr.press/v70/raghu17a.html.

Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In Jennifer Dy and Andreas Krause (eds.), *Proceedings of the 35th International Conference on Machine Learning*, volume 80 of *Proceedings of Machine Learning Research*, pp. 4558–4566. PMLR, 10–15 Jul 2018. URL https://proceedings.mlr.press/v80/serra18b.html.

Kenneth O Stanley, David B D'Ambrosio, and Jason Gauci. A hypercube-based encoding for evolving large-scale neural networks. *Artificial life*, 15(2):185–212, 2009.

Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. *CoRR*, abs/1503.02406, 2015. URL http://dblp.uni-trier.de/db/journals/corr/corr1503.html#TishbyZ15.

V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. *Theory of Probability and its Applications*, 16(2):264–280, 1971. doi: 10.1137/1116025. URL http://link.aip.org/link/?TPR/16/264/1.

P. Wolinski, G. Charpiat, and O. Ollivier. Asymmetrical scaling layers for stable network pruning. *OpenReview Archive*, 2020.

Lemeng Wu, Dilin Wang, and Qiang Liu. Splitting steepest descent for growing neural architectures. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), *Advances in Neural Information Processing Systems*, volume 32. Curran Associates, Inc., 2019. URL https://proceedings.neurips.cc/paper/2019/file/3a01fc0853ebeba94fde4d1cc6fb842a-Paper.pdf.

Lemeng Wu, Bo Liu, Peter Stone, and Qiang Liu. Firefly neural architecture descent: a general approach for growing neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), *Advances in Neural Information Processing Systems*, volume 33, pp. 22373–22383. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper/2020/file/fdbe012e2e11314b96402b32c0df26b7-Paper.pdf.

Tien-Ju Yang, Andrew Howard, Bo Chen, Xiao Zhang, Alec Go, Mark Sandler, Vivienne Sze, and Hartwig Adam. Netadapt: Platform-aware neural network adaptation for mobile applications. In *Proceedings of the European Conference on Computer Vision (ECCV)*, pp. 285–300, 2018.

Barret Zoph and Quoc V. Le. Neural architecture search with reinforcement learning, 2016. URL http://arxiv.org/abs/1611.01578. cite arxiv:1611.01578.

## Appendix outline

* Section A details the theoretical approach of TINY.

* Section B compares the theoretical approach of TINY with other approaches.

* Section C proves the propositions of the paper.

* Section D provides the hyper parameters for learning.

* Section E gives additional graphics associated to the result part.

We provide additional details, following the same order as the sections in the paper.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Training pruned neural networks. *CoRR*, abs/1803.03635, 2018. URL http://arxiv.org/abs/1803.03635.

Jerome H Friedman. Greedy function approximation: a gradient boosting machine. *Annals of statistics*, pp. 1189–1232, 2001.

Ariel Gordon, Elad Eban, Ofir Nachum, Bo Chen, Hao Wu, Tien-Ju Yang, and Edward Choi. Morphnet: Fast & simple resource-constrained structure learning of deep networks. In *Proceedings of the IEEE conference on computer vision and pattern recognition*, pp. 1586–1595, 2018.

Peter Grünwald and Teemu Roos. Minimum description length revisited. *International Journal of Mathematics for Industry*, 11(01):1930001, 2019. doi: 10.1142/S2661335219300018. URL https://doi.org/10.1142/S2661335219300018.

Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), *Proceedings of the 36th International Conference on Machine Learning*, volume 97 of *Proceedings of Machine Learning Research*, pp. 2596–2604. PMLR, 09–15 Jun 2019a. URL https://proceedings.mlr.press/v97/hanin19a.html.

Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), *Advances in Neural Information Processing Systems*, volume 32. Curran Associates, Inc., 2019b. URL https://proceedings.neurips.cc/paper/2019/file/9766527f2b5d3e95d4a733fcfb77bd7e-Paper.pdf.

C.R. Harris, K.J. Millman, S.J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, J. Taylor, S. Berg, N.J. Smith, R. Kern, M. Picus, S. Hoyer, M.H. van Kerkwijk, M. Brett, A. Haldane, J. Fernández del Río, M. Wiebe, P. Peterson, P. G'erard-Marchant, K. Sheppard, T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and T.E. Oliphant. Array programming with NumPy. *Nature*, 585(7825):357–362, 2020.

Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. *arXiv preprint arXiv:1503.02531*, 2015.

K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approximators. *Neural Networks*, 2(5):359–366, 1989.

J.D. Hunter. Matplotlib: A 2D graphics environment. *Computing in science & engineering*, 9(3):90–95, 2007.

Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), *Advances in Neural Information Processing Systems*, volume 31. Curran Associates, Inc., 2018. URL https://proceedings.neurips.cc/paper/2018/file/5a4be1fa34e62bb8a6ec6b91d2462f5a-Paper.pdf.

Andrei N Kolmogorov. Three approaches to the quantitative definition of information. *Problems of information transmission*, 1(1):1–7, 1965.

Vladimir Koltchinskii. Rademacher penalties and structural risk minimization. *IEEE Transactions on Information Theory*, 47(5):1902–1914, 2001.

Jean-François Le Gall. *Intégration, Probabilités et Processus Aléatoires*. 2006.

Ming Li, Paul Vitányi, et al. *An introduction to Kolmogorov complexity and its applications*, volume 3. Springer, 2008.

Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In *International Conference on Learning Representations*, 2019. URL https://openreview.net/forum?id=S1eYHoC5FX.
# A THEORETICAL DETAILS FOR PART 2

## A.1 FUNCTIONAL GRADIENT

The functional loss $\mathcal{L}$ is a functional that takes as input a function $f \in \mathcal{F}$ and outputs a real score:

$$ \mathcal{L}: f \in \mathcal{F} \mapsto \mathcal{L}(f) = \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \ell(f(x), y) \right] \in \mathbb{R}. $$

The function space $\mathcal{F}$ can typically be chosen to be $L_2(\mathbb{R}^p \to \mathbb{R}^d)$, which is a Hilbert space. The directional derivative (or Gateaux derivative, or Fréchet derivative) of functional $\mathcal{L}$ at function $f$ in direction $v$ is defined as:

$$ D\mathcal{L}(f)(v) = \lim_{\epsilon \to 0} \frac{\mathcal{L}(f + \epsilon v) - \mathcal{L}(f)}{\epsilon} $$

if it exists. Here $v$ denotes any function in the Hilbert space $\mathcal{F}$ and stands for the direction in which we would like to update $f$, following an infinitesimal step (of size $\epsilon$), resulting in a function $f + \epsilon v$.

If this directional derivative exists in all possible directions $v \in \mathcal{F}$ and moreover is continuous in $v$, then the Riesz representation theorem implies that there exists a unique direction $v^* \in \mathcal{F}$ such that:

$$ \forall v \in \mathcal{F}, D\mathcal{L}(f)(v) = \langle v^*, v \rangle. $$

This direction $v^*$ is named the *gradient* of the functional $\mathcal{L}$ at function $f$ and is denoted by $\nabla_f \mathcal{L}(f)$.

Note that while the inner product $\langle \cdot, \cdot \rangle$ considered is usually the $L_2$ one, it is possible to consider other ones, such as Sobolev ones (e.g., $H^1$). The gradient $\nabla_f \mathcal{L}(f)$ depends on the chosen inner product and should consequently rather be denoted by $\nabla_f^{L_2} \mathcal{L}(f)$ for instance.

Note that continuous functions from $\mathbb{R}^p$ to $\mathbb{R}^d$, as well as $C^\infty$ functions, are dense in $L_2(\mathbb{R}^p \to \mathbb{R}^d)$.

Let us now study properties specific to our loss design: $\mathcal{L}(f) = \mathbb{E}_{(x,y) \sim \mathcal{D}} [\ell(f(x), y)]$. Assuming sufficient $\ell$-loss differentiability and integrability, we get, for any function update direction $v \in \mathcal{F}$ and infinitesimal step size $\epsilon \in \mathbb{R}$:

$$ \begin{aligned} \mathcal{L}(f + \epsilon v) - \mathcal{L}(f) &= \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \ell(f(x) + \epsilon v(x), y) - \ell(f(x), y) \right] \\ &= \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \nabla_u \ell(u, y) \bigg|_{u=f(x)} \cdot \epsilon v(x) + O(\epsilon^2 \|v(x)\|^2) \right] \end{aligned} $$

using the usual gradient of function $\ell$ at point $(u = f(x), y)$ w.r.t. its first argument $u$, with the standard Euclidean dot product $\cdot$ in $\mathbb{R}^p$. Then the directional derivative is:

$$ D\mathcal{L}(f)(v) = \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \nabla_u \ell(u, y) \bigg|_{u=f(x)} \cdot v(x) \right] = \mathbb{E}_{x \sim \mathcal{D}} \left[ \mathbb{E}_{y \sim \mathcal{D}|x} \left[ \nabla_u \ell(u, y) \bigg|_{u=f(x)} \right] \cdot v(x) \right] $$

and thus the functional gradient for the inner product $\langle v, v' \rangle_{\mathbb{E}} := \mathbb{E}_{x \sim \mathcal{D}} \left[ v(x) \cdot v'(x) \right]$ is the function:

$$ \nabla_f^\mathcal{E} \mathcal{L}(f) : x \mapsto \mathbb{E}_{y \sim \mathcal{D}|x} \left[ \nabla_u \ell(u, y) \bigg|_{u=f(x)} \right] $$

which simplifies into:

$$ \nabla_f^\mathcal{E} \mathcal{L}(f) : x \mapsto \nabla_u \ell(u, y(x)) \bigg|_{u=f(x)} $$

if there is no ambiguity in the dataset, i.e. if for each $x$ there is a unique $y(x)$.

Note that by considering the $L_2(\mathbb{R}^p \to \mathbb{R}^d)$ inner product $\int v \cdot v'$ instead, one would respectively get:

$$ \nabla_f^{L_2} \mathcal{L}(f) : x \mapsto p_D(x) \mathbb{E}_{y \sim \mathcal{D}|x} \left[ \nabla_u \ell(u, y) \bigg|_{u=f(x)} \right] $$

and

$$ \nabla_f^{L_2} \mathcal{L}(f) : x \mapsto p_D(x) \nabla_u \ell(u, y(x)) \bigg|_{u=f(x)} $$

instead, where $p_D(x)$ is the density of the dataset distribution at point $x$. In practice one estimates such gradients using a minibatch of samples $(x, y)$, obtained by picking uniformly at random within a finite dataset, and thus the formulas for the two inner products coincide (up to a constant factor).
Zhengying Liu, Zhen Xu, Shangeth Rajaa, Meysam Madadi, Julio CS Jacques Junior, Sergio Escalera, Adrien Pavao, Sebastien Treguer, Wei-Wei Tu, and Isabelle Guyon. Towards automated deep learning: Analysis of the autodl challenge series 2019. In *NeurIPS 2019 Competition and Demonstration Track*, pp. 242–252. PMLR, 2020.

Christos Louizos, Karen Ullrich, and Max Welling. Bayesian compression for deep learning. *Advances in neural information processing systems*, 30, 2017.

Kaitlin Maile, Emmanuel Rachelson, Hervé Luga, and Dennis George Wilson. When, where, and how to add new neurons to ANNs. In *First Conference on Automated Machine Learning (Main Track)*, 2022. URL https://openreview.net/forum?id=SW0g-arIg9.

Hector Mendoza, Aaron Klein, Matthias Feurer, Jost Tobias Springenberg, and Frank Hutter. Towards automatically-tuned neural networks. In Frank Hutter, Lars Kotthoff, and Joaquin Vanschoren (eds.), *Proceedings of the Workshop on Automatic Machine Learning*, volume 64 of *Proceedings of Machine Learning Research*, pp. 58–65, New York, New York, USA, 24 Jun 2016. PMLR. URL https://proceedings.mlr.press/v64/mendoza_towards_2016.html.

Risto Miikkulainen, Jason Zhi Liang, Elliot Meyerson, Aditya Rawal, Daniel Fink, Olivier Francon, Bala Raju, Hormoz Shahrzad, Arshak Navruzyan, Nigel Duffy, and Babak Hodjat. Evolving deep neural networks. *CoRR*, abs/1703.00548, 2017. URL http://arxiv.org/abs/1703.00548.

Geoffrey F. Miller, Peter M. Todd, and Shailesh U. Hegde. Designing neural networks using genetic algorithms. In *ICGA*, 1989.

Yann Ollivier. True asymptotic natural gradient optimization, 2017.

The pandas development team. `pandas-dev/pandas`: Pandas, February 2020. URL https://doi.org/10.5281/zenodo.3509134.

A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In *Advances in Neural Information Processing Systems (NeurIPS)*, pp. 8024–8035. Curran Associates, Inc., 2019.

Allan Pinkus. Approximation theory of the mlp model in neural networks. *ACTA NUMERICA*, 8:143–195, 1999.

Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. In Doina Precup and Yee Whye Teh (eds.), *Proceedings of the 34th International Conference on Machine Learning*, volume 70 of *Proceedings of Machine Learning Research*, pp. 2847–2854. PMLR, 06–11 Aug 2017. URL https://proceedings.mlr.press/v70/raghu17a.html.

J. Rissanen. Modeling by shortest data description. *Automatica*, 14(5):465–471, 1978. ISSN 0005-1098. doi: https://doi.org/10.1016/0005-1098(78)90005-5. URL https://www.sciencedirect.com/science/article/pii/0005109878900055.

Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In Jennifer Dy and Andreas Krause (eds.), *Proceedings of the 35th International Conference on Machine Learning*, volume 80 of *Proceedings of Machine Learning Research*, pp. 4558–4566. PMLR, 10–15 Jul 2018. URL https://proceedings.mlr.press/v80/serra18b.html.

Kenneth O Stanley, David B D'Ambrosio, and Jason Gauci. A hypercube-based encoding for evolving large-scale neural networks. *Artificial life*, 15(2):185–212, 2009.

Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. *CoRR*, abs/1503.02406, 2015. URL http://dblp.uni-trier.de/db/journals/corr/corr1503.html#TishbyZ15.
## A.2 DIFFERENTIATION UNDER THE INTEGRAL SIGN

Let $X$ be an open subset of $\mathbb{R}$, and $\Omega$ be a measure space. Suppose $f: X \times \Omega \to \mathbb{R}$ satisfies the following conditions:

* $f(x, \omega)$ is a Lebesgue-integrable function of $\omega$ for each $x \in X$.

* For almost all $\omega \in \Omega$, the partial derivative $f_x$ of $f$ according to $x$ exists for all $x \in X$.

* There is an integrable function $\theta: \Omega \to \mathbb{R}$ such that $|f_x(x, \omega)| \le \theta(\omega)$ for all $x \in X$ and almost every $\omega \in \Omega$.

Then, for all $x \in X$,

$$ \frac{d}{dx} \int_{\Omega} f(x, \omega) \, d\omega = \int_{\Omega} f_x(x, \omega) \, d\omega $$

See proof and details: Flanders (1973).

## A.3 GRADIENTS AND PROXIMAL POINT OF VIEW

Gradients with respect to standard variables such as vectors are defined the same way as functional gradients above: given a sufficiently smooth loss $\tilde{\mathcal{L}}: \theta \in \Theta_A \mapsto \tilde{\mathcal{L}}(\theta) = \mathcal{L}(f_\theta) \in \mathbb{R}$, and an inner product $\cdot$ in the space $\Theta_A$ of parameters $\theta$, the gradient $\nabla_\theta \tilde{\mathcal{L}}(\theta)$ is the unique vector $\tau \in \Theta_A$ such that:

$$ \forall \delta\theta \in \Theta_A, \quad \tau \cdot \delta\theta = D_{\theta} \tilde{\mathcal{L}}(\theta)(\delta\theta) $$

where $D_{\theta} \tilde{\mathcal{L}}(\theta)(\delta\theta)$ is the directional derivative of $\tilde{\mathcal{L}}$ at point $\theta$ in the direction $\delta\theta$, defined as in the previous section. This gradient depends on the inner product chosen, which can be highlighted by the following property. The opposite $-\nabla_\theta \tilde{\mathcal{L}}(\theta)$ of the gradient is the unique solution of the problem:

$$ \arg\min_{\delta\theta \in \Theta_A} \left\{ D_{\theta} \tilde{\mathcal{L}}(\theta)(\delta\theta) + \frac{1}{2} \|\delta\theta\|_P^2 \right\} $$

where $\| \cdot \|_P$ is the norm associated to the chosen inner product. Changing the inner product obviously changes the way candidate directions $\delta\theta$ are penalized, leading to different gradients. This proximal formulation can be obtained as follows. For any $\delta\theta$, its distance to the gradient descent direction is:

$$ \begin{aligned} \|\delta\theta - (-\nabla_{\theta} \tilde{\mathcal{L}}(\theta))\|^2 &= \|\delta\theta\|^2 + 2\delta\theta \cdot \nabla_{\theta} \tilde{\mathcal{L}}(\theta) + \|\nabla_{\theta} \tilde{\mathcal{L}}(\theta)\|^2 \\ &= 2\left(\frac{1}{2} \|\delta\theta\|^2 + D_{\theta} \tilde{\mathcal{L}}(\theta)(\delta\theta)\right) + K \end{aligned} $$

where $K$ does not depend on $\delta\theta$. For the above to hold, the inner product used has to be the one from which the norm is derived. By minimizing this expression with respect to $\delta\theta$, one obtains the desired property.

In our case of study, for the norm over the space $\Theta_A$ of parameter variations, we consider a norm of in the space of associated functional variations, i.e.:

$$ \|\delta\theta\|_P := \left\| \frac{\partial f_\theta}{\partial \theta} \delta\theta \right\| $$

which makes more sense from a physical point of view, as it is more intrinsic to the task to solve and depends as little as possible on the parameterization (i.e. on the architecture chosen). This results in a functional move that is the projection of the functional one to the set of possible moves given the architecture. On the opposite, the standard gradient (using Euclidean parameter norm $\|\delta\theta\|$ in parameter space) yields a functional move obtained not only by projecting the functional gradient but also by multiplying it by a matrix $\frac{\partial f_\theta}{\partial \theta} \frac{\partial f_\theta}{\partial \theta}^T$ which can be seen as a strong architecture bias over optimization directions.

We consider here that the loss $\mathcal{L}$ to be minimized is the real loss that the user wants to optimize, possibly including regularizers to avoid overfitting, and since the architecture is evolving during training, possibly to architectures far from usual manual design and never tested before, one cannot assume architecture bias to be desirable. We aim at getting rid of it in order to follow the functional gradient descent as closely as possible.
V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. *Theory of Probability and its Applications*, 16(2):264–280, 1971. doi: 10.1137/1116025. URL http://link.aip.org/link/?TPR/16/264/1.

P. Virtanen, R. Gommers, T.E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S.J. van der Walt, M. Brett, J. Wilson, J.K. Millman, N. Mayorov, A.R.J. Nelson, E. Jones, R. Kern, E. Larson, C.J. Carey, I. Polat, Y. Feng, E.W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E.A. Quintero, C.R. Harris, A.M. Archibald, A.H. Ribeiro, F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. *Nature Methods*, 17:261–272, 2020.

P. Wolinski, G. Charpiat, and O. Ollivier. Asymmetrical scaling layers for stable network pruning. *OpenReview Archive*, 2020.

Lemeng Wu, Dilin Wang, and Qiang Liu. Splitting steepest descent for growing neural architectures. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), *Advances in Neural Information Processing Systems*, volume 32. Curran Associates, Inc., 2019. URL https://proceedings.neurips.cc/paper/2019/file/3a01fc0853ebeba94fde4d1cc6fb842a-Paper.pdf.

Lemeng Wu, Bo Liu, Peter Stone, and Qiang Liu. Firefly neural architecture descent: a general approach for growing neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), *Advances in Neural Information Processing Systems*, volume 33, pp. 2237–2238. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper/2020/file/fdb012e2e11314b96402b32c0df26b7-Paper.pdf.

Tien-Ju Yang, Andrew Howard, Bo Chen, Xiao Zhang, Alec Go, Mark Sandler, Vivienne Sze, and Hartwig Adam. Netadapt: Platform-aware neural network adaptation for mobile applications. In *Proceedings of the European Conference on Computer Vision (ECCV)*, pp. 285–300, 2018.

Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In *International Conference on Learning Representations*, 2017. URL https://openreview.net/forum?id=Sy8gdB9xx.

Barret Zoph and Quoc V. Le. Neural architecture search with reinforcement learning, 2016. URL http://arxiv.org/abs/1611.01578. cite arxiv:1611.01578.

## Appendix outline

* Appendix A details the theoretical approach of TINY.

* Appendix B reformulates related works with a common theoretical framework and compares those approaches.

* Appendix C proves the propositions of Section 3.

* Appendix D details the proofs regarding the convergence (related to Section 4).

* Appendix E provides the hyper parameters for learning.

* Appendix F gives additional graphics associated to the result part.

For Appendices B and C, we use the trace scalar product and its associated norm. We note $\langle \cdot, \cdot \rangle := \langle \cdot, \cdot \rangle_{\text{Tr}}$ and $|| \cdot || := || \cdot ||_{\text{Tr}}$. One should remark that $|| \cdot || = || \cdot ||_{\text{Tr}} = || \cdot ||_2$.
Searching for

$$v^* = \arg \min_{v \in \mathcal{T}_A} \|v - v_{\text{goal}}\|^2 = \arg \min_{v \in \mathcal{T}_A} \left\{ D_f \mathcal{L}(f)(v) + \frac{1}{2} \|v\|^2 \right\}$$

or equivalently for:

$$\delta\theta^* = \arg \min_{\delta\theta \in \Theta_A} \left\| \frac{\partial f_{\theta}}{\partial \theta} \delta\theta - v_{\text{goal}} \right\|^2 = \arg \min_{\delta\theta \in \Theta_A} \left\{ D_{\theta} \mathcal{L}(f_{\theta})(\delta\theta) + \frac{1}{2} \left\| \frac{\partial f_{\theta}}{\partial \theta} \delta\theta \right\|^2 \right\} =: - \nabla_{\theta}^{\mathcal{T}_A} \mathcal{L}(f_{\theta})$$

then appears as a natural goal.

## A.4 EXAMPLE OF EXPRESSIVITY BOTTLENECK

**Example.** Suppose one tries to estimate the function $y = f_{\text{true}}(x) = 2 \sin(x) + x$ with a linear model $f_{\text{predict}}(x) = ax + b$. Consider $(a, b) = (1, 0)$ and the square loss $\mathcal{L}$. For the dataset of inputs $(x_0, x_1, x_2, x_3) = (0, \frac{\pi}{2}, \pi, \frac{3\pi}{2})$, there exists no parameter update $(\delta a, \delta b)$ that would improve prediction at $x_0, x_1, x_2$ and $x_3$ simultaneously, as the space of linear functions $\{f : x \to ax+b \mid a, b \in \mathbb{R}\}$ is not expressive enough. To improve the prediction at $x_0, x_1, x_2$ and $x_3$, one should look for another, more expressive functional space such that for $i = 0, 1, 2, 3$ the functional update $\Delta f(x_i) := f^{i+1}(x_i) - f^i(x_i)$ goes into the same direction as the functional gradient $v_{\text{goal}}(x_i) := -\nabla_{f(x_i)} \mathcal{L}(f(x_i), y_i) = -2(f(x_i) - y_i)$ where $y_i = f_{\text{true}}(x_i)$.

<figure><img src="image_11.png" /><figcaption>Figure 9: Linear interpolation</figcaption></figure>

## A.5 PROBLEM FORMULATION AND CHOICE OF PRE-ACTIVITIES

There are several ways to design the problem of adding neurons, which we discuss now, in order to explain our choice of the pre-activities to express expressivity bottlenecks.

Suppose one wishes to add $K$ neurons $\theta^K \stackrel{\leftrightarrow}{:=} (\alpha_k, \omega_k)_{k=1}^K$ to layer $l-1$, which impacts the activities $a_l$ at the next layer, in order to improve its expressivity. These neurons could be chosen to have only nul weights, or nul input weights $\alpha_k$ and non-nul output weights $\omega_k$, or the opposite, or both non-nul weights. Searching for the best neurons to add for each of these cases will produce different optimization problems.

Let us remind first that adding such $K$ neurons with weights $\theta^K \stackrel{\leftrightarrow}{:=} (\alpha_k, \omega_k)_{k=1}^K$ changes the activities $a_l$ of the (next) layer by

$$\delta a_l = \sum_{k=1}^{K} \omega_k \sigma(b_{l-2}(\boldsymbol{x})^T \boldsymbol{\alpha}_k) \qquad (9)$$

**Small weights approximation** Under the hypothesis of small input weights $\alpha_k$, the activity variation 9 can be approximated by:

$$\sigma'(0) \sum_{k=1}^{K} \omega_k b_{l-2}(\boldsymbol{x})^T \boldsymbol{\alpha}_k$$

at first order in $\|\boldsymbol{\alpha}_k\|$. We will drop the constant $\sigma'(0)$ in the sequel.

This quantity is linear both in $\alpha_k$ and $\omega_k$, therefore the first-order parameter-induced activity variations are easy to compute:

$$v^l(\boldsymbol{x}, (\boldsymbol{\alpha}_k)_{k=1}^K) = \frac{\partial a_l(\boldsymbol{x})}{\partial((\boldsymbol{\alpha}_k)_{k=1}^K)} \Big|_{(\boldsymbol{\alpha}_k)_{k=1}^K=0} (\boldsymbol{\alpha}_k)_{k=1}^K = \sum_{k=1}^K \omega_k b_{l-2}(\boldsymbol{x})^T \boldsymbol{\alpha}_k$$

$$v^l(\boldsymbol{x}, (\boldsymbol{\omega}_k)_{k=1}^K) = \frac{\partial a_l(\boldsymbol{x})}{\partial((\boldsymbol{\omega}_k)_{k=1}^K)} \Big|_{(\boldsymbol{\omega}_k)_{k=1}^K=0} (\boldsymbol{\omega}_k)_{k=1}^K = \sum_{k=1}^K \omega_k b_{l-2}(\boldsymbol{x})^T \boldsymbol{\alpha}_k$$
# A Theoretical details for part 2

## A.1 Functional gradient

The functional loss $\mathcal{L}$ is a functional that takes as input a function $f \in \mathcal{F}$ and outputs a real score:

$$ \mathcal{L}: f \in \mathcal{F} \mapsto \mathcal{L}(f) = \mathbb{E}_{(x,y)\sim\mathcal{D}} [\ell(f(x), y)] \in \mathbb{R}. $$

The function space $\mathcal{F}$ can typically be chosen to be $L_2(\mathbb{R}^p \to \mathbb{R}^d)$, which is a Hilbert space. The directional derivative (or Gateaux derivative, or Fréchet derivative) of functional $\mathcal{L}$ at function $f$ in direction $v$ is defined as:

$$ D\mathcal{L}(f)(v) = \lim_{\varepsilon \to 0} \frac{\mathcal{L}(f + \varepsilon v) - \mathcal{L}(f)}{\varepsilon} $$

if it exists. Here $v$ denotes any function in the Hilbert space $\mathcal{F}$ and stands for the direction in which we would like to update $f$, following an infinitesimal step (of size $\varepsilon$), resulting in a function $f + \varepsilon v$.

If this directional derivative exists in all possible directions $v \in \mathcal{F}$ and moreover is continuous in $v$, then the Riesz representation theorem implies that there exists a unique direction $v^* \in \mathcal{F}$ such that:

$$ \forall v \in \mathcal{F}, D\mathcal{L}(f)(v) = \langle v^*, v \rangle. $$

This direction $v^*$ is named the gradient of the functional $\mathcal{L}$ at function $f$ and is denoted by $\nabla_f \mathcal{L}(f)$.

Note that while the inner product $\langle \cdot, \cdot \rangle$ considered is usually the $L_2$ one, it is possible to consider other ones, such as Sobolev ones (e.g., $H^1$). The gradient $\nabla_f \mathcal{L}(F)$ depends on the chosen inner product and should consequently rather be denoted by $\nabla_f^{L_2} \mathcal{L}(f)$ for instance.

Note that continuous functions from $\mathbb{R}^p \to \mathbb{R}^d$, as well as $C^\infty$ functions, are dense in $L_2(\mathbb{R}^p \to \mathbb{R}^d)$.

Let us now study properties specific to our loss design: $\mathcal{L}(f) = \mathbb{E}_{(x,y)\sim\mathcal{D}} [\ell(f(x), y)]$. Assuming sufficient $\ell$-loss differentiability and integrability, we get, for any function update direction $v \in \mathcal{F}$ and infinitesimal step size $\varepsilon \in \mathbb{R}$:

$$ \begin{aligned} \mathcal{L}(f + \varepsilon v) - \mathcal{L}(f) &= \mathbb{E}_{(x,y)\sim\mathcal{D}} [\ell(f(x) + \varepsilon v(x), y) - \ell(f(x), y)] \\ &= \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ \nabla_u \ell(\mathbf{u}, y) \Big|_{\mathbf{u}=f(\mathbf{x})} \cdot \varepsilon v(\mathbf{x}) + O(\varepsilon^2 \|v(\mathbf{x})\|^2) \right] \end{aligned} $$

using the usual gradient of function $\ell$ at point $(\mathbf{u} = f(\mathbf{x}), y)$ w.r.t. its first argument $\mathbf{u}$, with the standard Euclidean dot product $\cdot$ in $\mathbb{R}^p$. Then the directional derivative is:

$$ D\mathcal{L}(f)(v) = \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ \nabla_{\mathbf{u}} \ell(\mathbf{u}, y) \Big|_{\mathbf{u}=f(\mathbf{x})} \cdot v(\mathbf{x}) \right] = \mathbb{E}_{\mathbf{x}\sim\mathcal{D}} \left[ \mathbb{E}_{y\sim\mathcal{D}|\mathbf{x}} \left[ \nabla_{\mathbf{u}} \ell(\mathbf{u}, y) \Big|_{\mathbf{u}=f(\mathbf{x})} \right] \cdot v(\mathbf{x}) \right] $$

and thus the functional gradient for the inner product $\langle v, v' \rangle_{\mathbb{E}} := \mathbb{E}_{x\sim\mathcal{D}} [v(x) \cdot v'(x)]$ is the function:

$$ \nabla_f^\mathcal{E} \mathcal{L}(f) : x \mapsto \mathbb{E}_{y\sim\mathcal{D}|x} \left[ \nabla_u \ell(\mathbf{u}, y) \Big|_{\mathbf{u}=f(\mathbf{x})} \right] $$

which simplifies into:

$$ \nabla_f^\mathcal{E} \mathcal{L}(f) : x \mapsto \nabla_u \ell(\mathbf{u}, y(x)) \Big|_{\mathbf{u}=f(\mathbf{x})} $$

if there is no ambiguity in the dataset, i.e. if for each $x$ there is a unique $y(x)$.

Note that by considering the $L_2(\mathbb{R}^p \to \mathbb{R}^d)$ inner product $\int v \cdot v'$ instead, one would respectively get:

$$ \nabla_f^{L_2} \mathcal{L}(f) : x \mapsto p_D(x) \mathbb{E}_{y\sim\mathcal{D}|x} \left[ \nabla_u \ell(\mathbf{u}, y) \Big|_{\mathbf{u}=f(\mathbf{x})} \right] $$

and

$$ \nabla_f^{L_2} \mathcal{L}(f) : x \mapsto p_D(x) \nabla_u \ell(\mathbf{u}, y(x)) \Big|_{\mathbf{u}=f(\mathbf{x})} $$

instead, where $p_D(x)$ is the density of the dataset distribution at point $x$. In practice one estimates such gradients using a minibatch of samples $(x, y)$, obtained by picking uniformly at random within a finite dataset, and thus the formulas for the two inner products coincide (up to a constant factor).
so with a slight abuse of notation we have:

$$v^l(x, \theta_{\leftarrow}^K) = \sum_{k=1}^{K} \omega_k b_{l-2}(x)^T \alpha_k$$

Note also that technically the quantity above is first-order in $\alpha_k$ and in $\omega_k$ but second-order in the joint variable $\theta_{\leftarrow}^K = (\alpha_k, \omega_k)$.

**Adding neurons with 0 weights (both input and output weights).** In that case, one increases the number of neurons in the layer, but without changing the function (since only nul quantities are added) and also without changing the gradient with respect to the parameters, thus not improving expressivity. Indeed, the added quantity (Eq. 9) involves $0 \times 0$ multiplications, and consequently the derivative $\frac{\partial a_l(x)}{\partial \theta_{\leftarrow}^K}|_{\theta_{\leftarrow}=0}$ w.r.t. these new parameters, that is, $b_{l-2}(x)^T \alpha_k$ w.r.t. $\omega_k$ and $\omega_k b_{l-2}(x)^T$ w.r.t. $a_k$ is 0, as both $a_k$ and $\omega_k$ are 0.

**Adding neurons with non-0 input weights and 0 output weights or the opposite.** In these cases, the addition of neurons will not change the function (because of multiplications by 0), but just the gradient. One of the 2 gradients (w.r.t. $a_k$ or w.r.t $\omega_k$) will be non-0, as the variable that is 0 has non-0 derivatives.

The question is then how to pick the best non-0 variable, ($a_k$ or $\omega_k$) such that the added gradient will be the most useful. The problem can then be formulated similarly as what is done in the paper.

**Adding neurons with small yet non-0 weights.** In this case, both the function and its gradient will change when adding the neurons. Fortunately, Proposition 3.2 states that the best neurons to add in terms of expressivity (to get the gradient closer to the variation desired by the backpropagation) are also the best neurons to add to decrease the loss, i.e. the function change they will imply goes into the right direction.

For each family $(\omega_k)_{k=1}^K$, the tangent space in $a_l$ restricted to the family $(\alpha_k)_{k=1}^K$, ie $T_A^{a_l} := \{\frac{\partial a_l}{\partial(\alpha_k)_{k=1}^K} | (\alpha_k)_{k=1}^K \in (\mathbb{R}^{|b_{l-2}(x)|})^K\}$ varies with the family $(\omega_k)_{k=1}^K$, ie $T_A^{a_l} := T_A^{a_l}((\omega_k)_{k=1}^K)$. Optimizing w.r.t. the $\omega_k$ is equivalent to search for the best tangent space for the $\alpha_k$, while symmetrically optimizing w.r.t. the $\alpha_k$ is equivalent to find the best projection on the tangent space defined by the $\omega_k$.

<figure><img src="image_12.png" /><figcaption>Figure 10: Changing the tangent space with different values of $(\omega_k)_{k=1}^K$.</figcaption></figure>

**Pre-activities vs. post-activities.** The space of pre-activities $a_l$ is a natural space for this framework, as they are formed with linear operations and we compute first-order variation quantities.
## A.2 Differentiation under the integral sign

Let $X$ be an open subset of $\mathbb{R}$, and $\Omega$ be a measure space. Suppose $f: X \times \Omega \to \mathbb{R}$ satisfies the following conditions:

* $f(x, \omega)$ is a Lebesgue-integrable function of $\omega$ for each $x \in X$.

* For almost all $\omega \in \Omega$, the partial derivative $\frac{\partial}{\partial x} f$ of $f$ according to $x$ exists for all $x \in X$.

* There is an integrable function $\theta: \Omega \to \mathbb{R}$ such that $|\frac{\partial}{\partial x}(x, \omega)| \le \theta(\omega)$ for all $x \in X$ and almost every $\omega \in \Omega$.

Then, for all $x \in X$,

$$ \frac{\partial}{\partial x} \int_{\Omega} f(x, \omega) \, d\omega = \int_{\Omega} \frac{\partial}{\partial x} f(x, \omega) \, d\omega \quad (15) $$

See proof and details: Le Gall (2006).

## A.3 Gradients and proximal point of view

Gradients with respect to standard variables such as vectors are defined in the same way as functional gradients above: given a sufficiently smooth loss $\tilde{\mathcal{L}}: \theta \in \Theta_A \mapsto \tilde{\mathcal{L}}(\theta) = \mathcal{L}(f_\theta) \in \mathbb{R}$, and an inner product $\cdot$ in the space $\Theta_A$ of parameters $\theta$, the gradient $\nabla_\theta \tilde{\mathcal{L}}(\theta)$ is the unique vector $\tau \in \Theta_A$ such that:

$$ \forall \delta\theta \in \Theta_A, \quad \tau \cdot \delta\theta = D_{\theta} \tilde{\mathcal{L}}(\theta)(\delta\theta) $$

where $D_{\theta} \tilde{\mathcal{L}}(\theta)(\delta\theta)$ is the directional derivative of $\tilde{\mathcal{L}}$ at point $\theta$ in the direction $\delta\theta$, defined as in the previous section. This gradient depends on the inner product chosen, which can be highlighted by the following property. The opposite $-\nabla_\theta \tilde{\mathcal{L}}(\theta)$ of the gradient is the unique solution of the problem:

$$ \arg\min_{\delta\theta \in \Theta_A} \left\{ D_{\theta} \tilde{\mathcal{L}}(\theta)(\delta\theta) + \frac{1}{2} \|\delta\theta\|_P^2 \right\} $$

where $\| \cdot \|_P$ is the norm associated to the chosen inner product. Changing the inner product changes the way candidate directions $\delta\theta$ are penalized, leading to different gradients. This proximal formulation can be obtained as follows. For any $\delta\theta$, its distance to the gradient descent direction is:

$$ \begin{aligned} \|\delta\theta - (-\nabla_{\theta} \tilde{\mathcal{L}}(\theta))\|^2 &= \|\delta\theta\|^2 + 2\delta\theta \cdot \nabla_{\theta} \tilde{\mathcal{L}}(\theta) + \|\nabla_{\theta} \tilde{\mathcal{L}}(\theta)\|^2 \\ &= 2\left(\frac{1}{2} \|\delta\theta\|^2 + D_{\theta} \tilde{\mathcal{L}}(\theta)(\delta\theta)\right) + K \end{aligned} $$

where $K$ does not depend on $\delta\theta$. For the above to hold, the inner product used has to be the one from which the norm is derived. By minimizing this expression with respect to $\delta\theta$, one obtains the desired property.

In our case of study, for the norm over the space $\Theta_A$ of parameter variations, we consider a norm in the space of associated functional variations, i.e.:

$$ \|\delta\theta\|_P := \left\| \frac{\partial f_\theta}{\partial \theta} \delta\theta \right\| $$

which makes more sense from a physical point of view, as it is more intrinsic to the task to solve and depends as little as possible on the parameterization (i.e. on the architecture chosen). This results in a functional move that is the projection of the functional one to the set of possible moves given the architecture. On the opposite, the standard gradient (using Euclidean parameter norm $\|\delta\theta\|$ in parameter space) yields a
Considering the space of post-activities $b_l = \sigma(a_l)$ is also possible, though computing variations will be more complex. Indeed, without first-order approximation, the obtained problem is not manageable, because of the non-linear activation function $\sigma$ added in front of all quantities (while in the case of pre-activations, quantity 9 is linear in $\omega_k$ and thus does not require approximation in $\omega_k$, which allow considering large $\omega_k$), and, with first-order approximation, it would add the derivative of the activation function, taken at various locations $\sigma'(a_l)$ (while in the previous case the derivatives of the activation function were always taken at 0).

## A.6 ADDING CONVOLUTIONAL NEURONS

To add a convolutional neuron at layer $l-1$, one should add a kernel at layer $l-1$ and expand one dimension to all the kernels in layer $l$ to match the new dimension of the post-activity.

<figure><img src="image_13.png" /><figcaption>Figure 11: Adding one convolutional neuron at layer one for a input with tree channels.</figcaption></figure>

# B THEORETICAL COMPARISON WITH OTHER APPROACHES

## B.1 GRADMAX METHOD

The theoretical approach of GradMax is to add neurons with zero fan-in and choose the fan-out that will decrease the loss as much as possible after one gradient step. At time $t$, we perform such neuron addition and we note $\Omega$ the fan-out of the new neurons. After one gradient step, ie $t \to t+1$, we have the approximation :

$$ \mathcal{L}^{t+1} \approx \mathcal{L}^t - ||\nabla_{\theta}\mathcal{L}||^2 - ||\nabla_{\Omega}\mathcal{L}||^2 $$

The solution of GradMax is then :

$$ (\omega_1^*, ..., \omega_K^*) := \Omega^* = \arg\max_{\Omega} ||\nabla_{\Omega}\mathcal{L}||^2 \qquad \text{s.t. } ||\Omega||_F^2 < c $$

$$ = \arg\max_{\Omega} \left\| \sum_{i} b_{l-2}(x_i) v_{\text{goal}}^{l+1} (x_i) \Omega \right\|_{F}^{2} \qquad \text{s.t. } ||\Omega||_{F}^{2} < c $$

$$ := \arg\max_{\Omega} ||\mathbf{B}_{l-2} \mathbf{V}_{\text{goal}}^{l+1} \Omega||_F^2 \qquad \text{s.t. } ||\Omega||_F^2 < c $$

$$ := \arg\max_{\Omega} \mathrm{Tr} (\Omega^T \tilde{\mathbf{N}}^T \tilde{\mathbf{N}} \Omega) \qquad \text{s.t. } ||\Omega||_F^2 < c \qquad (10) $$
functional move obtained not only by projecting the functional gradient but also by multiplying it by a matrix $\frac{\partial f_\theta}{\partial \theta} \frac{\partial f_\theta}{\partial \theta}^T$ which can be seen as a strong architecture bias over optimization directions.

We consider here that the loss $\mathcal{L}$ to be minimized is the real loss that the user wants to optimize, possibly including regularizers to avoid overfitting, and since the architecture is evolving during training, possibly to architectures far from usual manual design and never tested before, one cannot assume architecture bias to be desirable. We aim at getting rid of it in order to follow the functional gradient descent as closely as possible.

Searching for

$$v^* = \arg\min_{v \in \mathcal{T}_A} \|v - v_{\text{goal}}\|^2 = \arg\min_{v \in \mathcal{T}_A} \left\{ D\mathcal{L}(f)(v) + \frac{1}{2} \|v\|^2 \right\} \quad (16)$$

or equivalently for:

$$\delta\theta^* = \arg\min_{\delta\theta \in \Theta_A} \left\| \frac{\partial f_\theta}{\partial \theta} \delta\theta - v_{\text{goal}} \right\|^2 = \arg\min_{\delta\theta \in \Theta_A} \left\{ D_\theta \mathcal{L}(f_\theta)(\delta\theta) + \frac{1}{2} \left\| \frac{\partial f_\theta}{\partial \theta} \delta\theta \right\|^2 \right\} =: -\nabla_{\theta}^{\mathcal{T}_A} \mathcal{L}(f_\theta) \quad (17)$$

then appears as a natural goal.

## A.4 Example of expressivity bottleneck

**Example.** Suppose one tries to estimate the function $y = f_{\text{true}}(x) = 2\sin(x) + x$ with a linear model $f_{\text{predict}}(x) = ax + b$. Consider $(a, b) = (1, 0)$ and the square loss $\mathcal{L}$. For the dataset of inputs $(x_0, x_1, x_2, x_3) = (0, \frac{\pi}{2}, \pi, \frac{3\pi}{2})$, there exists no parameter update $(\delta a, \delta b)$ that would improve prediction at $x_0, x_1, x_2$ and $x_3$ simultaneously, as the space of linear functions $\{f : x \to ax + b \mid a, b \in \mathbb{R}\}$ is not expressive enough. To improve the prediction at $x_0, x_1, x_2$ and $x_3$, one should look for another, more expressive functional space such that for $i = 0, 1, 2, 3$ the functional update $\Delta f(x_i) := f^{i+1}(x_i) - f^i(x_i)$ goes into the same direction as the functional gradient $v_{\text{goal}}(x_i) := -\nabla_{f(x_i)} \mathcal{L}(f(x_i), y_i) = -2(f(x_i) - y_i)$ where $y_i = f_{\text{true}}(x_i)$.

<figure><img src="image_10.png" /><figcaption>Figure 9: Linear interpolation</figcaption></figure>

## A.5 Problem formulation and choice of pre-activities

There are several ways to design the problem of adding neurons, which we discuss now, in order to explain our choice of the pre-activities to express expressivity bottlenecks.

Suppose one wishes to add $K$ neurons $\theta^K := (\alpha_k, \omega_k)_{k=1}^K$ to layer $l-1$, which impacts the activities $a_l$ at the next layer, in order to improve its expressivity. These neurons could be chosen to have only null weights, or null input weights $\alpha_k$ and non-null output weights $\omega_k$, or the opposite, or both non-null weights. Searching for the best neurons to add for each of these cases will produce different optimization problems.

Let us remind first that adding such $K$ neurons with weights $\theta^K := (\alpha_k, \omega_k)_{k=1}^K$ changes the activities $a_l$ of the (next) layer by

$$\delta a_l = \sum_{k=1}^{K} \omega_k \sigma(\alpha_k^T b_{l-2}(x)) \quad (18)$$

**Small weight approximation** Under the hypothesis of small input weights $\alpha_k$, and assuming smooth activation function $\sigma$ at 0, the activity variation 18 can be approximated by:

$$\sigma'(0) \sum_{k=1}^{K} \omega_k \alpha_k^T b_{l-2}(x) \quad (19)$$
Where c is a normalisation constant. On the other hand, TINY is equivalent to the following optimisation problem :

$$
\begin{align*}
(\omega_1^*, \dots, \omega_K^*) = \Omega^* &= \arg\max_{\Omega} \left\| \sum_i b_{l-2}(x_i) v_{\text{goal}_{proj}}^{l+1} {}^T(x_i) \Omega \right\|_F^2 & \text{s.t. } & \left\| B_{l-1} \Omega \right\|_F^2 < c \\
&= \arg\max_{\Omega} \left\| B_{l-2} v_{\text{goal}_{proj}}^{l+1} \Omega \right\|_F^2 & \text{s.t. } & \left\| B_{l-1} \Omega \right\|_F^2 < c \\
&= \arg\max_{\substack{\Omega \\ \tilde{\Omega}}} \text{Tr} \left( \tilde{\Omega}^T S^{-\frac{1}{2}} N^T N S^{-\frac{1}{2}} \tilde{\Omega} \right) & \text{s.t. } & \left\| \tilde{\Omega} \right\|_F^2 < c, \tilde{\Omega} := S^{\frac{1}{2}} \Omega \\
&= \arg\max_{\Omega} \text{Tr} \left( \Omega S^{-1} N^T N S^{-1} \Omega \right) & \text{s.t. } & \left\| \Omega \right\|_F^2 < \tilde{c}
\end{align*}
$$

One can note three differences between those optimization problems:

• First, the matrix $\tilde{N}$ is not defined using the projection of the desired update $V_{\text{goal}_{proj}}^{l+1}$. As a consequence, GradMax does not take into account redundancy, and on the opposite will actually try to add new neurons that are as redundant as possible with the part of the goal update that is already feasible with already-existing neurons.

• Second, the constraint lies in the weight space for GradMax method while it lies in the pre-activation space in our case. The difference is that GradMax relies on the Euclidean metric in the space of parameters, which arguably offers less meaning that the Euclidean metric in the space of activities. Essentially this is the same difference as between the standard L2 gradient w.r.t. parameters and the natural gradient, which takes care of parameter redundancy and measures all quantities in the output space in order to be independent from the parameterization. In practice we do observe that the "natural" gradient direction improves the loss better than the usual L2 gradient.

• Third, our fan-in weights are not set to 0 but directly to their optimal values (at first order).

## B.2 NORTH PREACTIVATION

In paper Maile et al. (2022), fan-out weights are initialized to 0 while fan-in weights are initialized as $\alpha_i = S^{-1}B_{l-1}V_{Z_l}^T r_i$ where $r_i$ is a random vector and $V_{Z_l} \in \mathcal{M}(|Ker(B_{l-1}^T)|, |b_{l-1}(\boldsymbol{x})|)$ is a matrix consisting of the orthogonal vectors of the kernel of pre-activations $B_l$, i.e $\{z | B_l^T z = 0\}$. In our paper fan-in weights are initialized as $\alpha_i = S^{-1}B_{l-1}V_{\text{goal}_{proj}}^T v_i = S^{-1}B_{l-1}V_{\text{goal}_{proj}}^T V_{Z_l} V_{Z_l}^T v_i$, where the $v_i$ are right eigenvectors of the matrix $S^{-\frac{1}{2}}N$.

The main difference is thus that we use the backpropagation to find the best $v_i$ or $r_i$ directly, while the NORTH approach tries random directions $r_i$ to explore the space of possible neuron additions.

# C PROOFS OF PART 3 AND 4

## C.1 PROPOSITION 3.1

Denoting by $\delta \mathbf{W}_l^+$ the generalized (pseudo-)inverse of $\delta \mathbf{W}_l$, we have:

$$ \delta \mathbf{W}_l^* = \frac{1}{n} \mathbf{V}_{\text{goal}}^l B_{l-1}^T \left( \frac{1}{n} B_{l-1} B_{l-1}^T \right)^+ \text{ and } \mathbf{V}_0^l = \frac{1}{n} \mathbf{V}_{\text{goal}}^l B_{l-1}^T \left( \frac{1}{n} B_{l-1} B_{l-1}^T \right)^+ B_{l-1} $$

$$ g(\delta \mathbf{W}_l) = \| \mathbf{V}_{\text{goal}}^l - \delta \mathbf{W}_l \mathbf{B}_{l-1} \|_{\text{Tr}}^2 \quad (11) $$

<footnote>*Proof*
Consider the function</footnote>
at first order in $||\alpha_k||$. We will drop the constant $\sigma'(0)$ in the sequel.

This quantity is linear both in $\alpha_k$ and $\omega_k$, therefore the first-order parameter-induced activity variations are easy to compute:

$$v^l(x, (\alpha_k)_{k=1}^K) = \frac{\partial a_l(x)}{\partial((\alpha_k)_{k=1}^K)} \Big|_{(\alpha_k)_{k=1}^K=0} (\alpha_k)_{k=1}^K = \sum_{k=1}^K \omega_k b_{l-2}(x)^T \alpha_k$$

$$v^l(x, (\omega_k)_{k=1}^K) = \frac{\partial a_l(x)}{\partial((\omega_k)_{k=1}^K)} \Big|_{(\omega_k)_{k=1}^K=0} (\omega_k)_{k=1}^K = \sum_{k=1}^K \omega_k b_{l-2}(x)^T \alpha_k$$

so with a slight abuse of notation we have:

$$v^l(x, \theta_{\leftrightarrow}^K) = \sum_{k=1}^K \omega_k \alpha_k^T b_{l-2}(x)$$

Note also that technically the quantity above is first-order in $\alpha_k$ and in $\omega_k$ but second-order in the joint variable $\theta_{\leftrightarrow}^K = (\alpha_k, \omega_k)$.

**Adding neurons with 0 weights (both input and output weights).** In that case, one increases the number of neurons in the layer, but without changing the function (since only null quantities are added) and also without changing the gradient with respect to the parameters, thus not improving expressivity. Indeed, the added quantity (Eq. 18) involves 0 × 0 multiplications, and consequently the derivative $\frac{\partial a_l(x)}{\partial \theta_{\leftrightarrow}^K} \Big|_{\theta_{\leftrightarrow}^K=0}$ w.r.t. these new parameters, that is, $b_{l-2}(x)^T \alpha_k$ w.r.t. $\omega_k$ and $\omega_k b_{l-2}(x)^T$ w.r.t. $\alpha_k$ is 0, as both $a_k$ and $\omega_k$ are 0.

**Adding neurons with non-0 input weights and 0 output weights or the opposite.** In these cases, the addition of neurons will not change the function (because of multiplications by 0), but just the gradient. One of the 2 gradients (w.r.t. $\alpha_k$ or w.r.t $\omega_k$) will be non-0, as the variable that is 0 has non-0 derivatives.

The question is then how to pick the best non-null variable, ($\alpha_k$ or $\omega_k$) such that the added gradient will be the most useful. The problem can then be formulated similarly as what is done in the paper.

**Adding neurons with small yet non-0 weights.** In this case, both the function and its gradient will change when adding the neurons. Fortunately, Proposition 3.2 states that the best neurons to add in terms of expressivity (to get the gradient closer to the variation desired by the backpropagation) are also the best neurons to add to decrease the loss, i.e. the function change they will imply goes into the right direction.

For each family $(\omega_k)_{k=1}^K$, the tangent space in $a_l$ restricted to the family $(\alpha_k)_{k=1}^K$, i.e. $T_A^{a_l} := \left\{ \frac{\partial a_l}{\partial(\alpha_k)_{k=1}^K} \right\} \text{ varies with the family } (\omega_k)_{k=1}^K$, i.e. $T_A^{a_l} := T_A^{a_l}((\omega_k)_{k=1}^K)$. Optimizing w.r.t. the $\omega_k$ is equivalent to search for the best tangent space for the $\alpha_k$, while symmetrically optimizing w.r.t. the $\alpha_k$ is equivalent to find the best projection on the tangent space defined by the $\omega_k$ (Figure 10).

**Pre-activities vs. post-activities.** The space of pre-activities $a_l$ is a natural space for this framework, as they are formed with linear operations and we compute first-order variation quantities. Considering the space of post-activities $b_l = \sigma(a_l)$ is also possible, though computing variations will be more complex. Indeed, without first-order approximation, the obtained problem is not manageable, because of the non-linear activation function $\sigma$ added in front of all quantities (while in the cases of pre-activations, quantity 18 is linear in $\omega_k$ and thus does not require approximation in $\omega_k$, which allow considering large $\omega_k$), and, with first-order approximation, it would add the derivative of the activation function, taken at various locations $\sigma'(a_l)$ (while in the previous case the derivatives of the activation function were always taken at 0).
then:

$$
\begin{align*}
g(\delta \mathbf{W}_l + \mathbf{H}) &= ||\mathbf{V}_{\text{goal}}^l - \delta \mathbf{W}_l \mathbf{B}_{l-1} - \mathbf{H} \mathbf{B}_{l-1}||_{\text{Tr}}^2 \\
&= g(\delta \mathbf{W}_l) - 2\langle \mathbf{V}_{\text{goal}}^l - \delta \mathbf{W}_l \mathbf{B}_{l-1}, \mathbf{H} \mathbf{B}_{l-1} \rangle_{\text{Tr}} + o(||\mathbf{H}||) \\
&= g(\delta \mathbf{W}_l) - 2 \text{Tr} \left( (\mathbf{V}_{\text{goal}}^l - \delta \mathbf{W}_l \mathbf{B}_{l-1})^T \mathbf{H} \mathbf{B}_{l-1} \right) + o(||\mathbf{H}||) \\
&= g(\delta \mathbf{W}_l) - 2 \text{Tr} \left( \mathbf{B}_{l-1} (\mathbf{V}_{\text{goal}}^l - \delta \mathbf{W}_l \mathbf{B}_{l-1})^T \mathbf{H} \right) + o(||\mathbf{H}||) \\
&= g(\delta \mathbf{W}_l) - 2 \langle (\mathbf{V}_{\text{goal}}^l - \delta \mathbf{W}_l \mathbf{B}_{l-1}) \mathbf{B}_{l-1}^T, \mathbf{H} \rangle_{\text{Tr}} + o(||\mathbf{H}||)
\end{align*}
$$

By identification $\nabla_{\delta \mathbf{W}_l} g(\delta \mathbf{W}_l) = -2(\mathbf{V}_{\text{goal}}^l - \delta \mathbf{W}_l \mathbf{B}_{l-1}) \mathbf{B}_{l-1}^T$, and thus:

$$ \nabla_{\delta \mathbf{W}_l} g(\delta \mathbf{W}_l) = 0 \implies \mathbf{V}_{\text{goal}}^l \mathbf{B}_{l-1}^T = \delta \mathbf{W}_l \mathbf{B}_{l-1} \mathbf{B}_{l-1}^T $$

Using the definition of the generalized inverse of $M^+$, we get:

$$ \delta \mathbf{W}_l^* = \frac{1}{n} \mathbf{V}_{\text{goal}}^l \mathbf{B}_{l-1}^T \left( \frac{1}{n} \mathbf{B}_{l-1} \mathbf{B}_{l-1}^T \right)^+ $$

as one solution. For convolutional layer, we defined as $b_i^c$ the input associated to the activation $a_l(X_i) \in \mathbb{R}^{k;p;p}$, such that for any convolutional layer Conv with parameter $W$, we have:

$$ \text{Conv}(a_l(X_i)) = B_i^c \text{ vect}(W) \qquad (12) $$

Example: considering the kernel of Conv to be (2, 2), then:

$$ \mathbf{b}_i^k = \begin{pmatrix} b_i^{1,k} & b_i^{2,k} & \cdots & b_i^{p,k} \\ b_i^{p+1,k} & b_i^{p+2,k} & \cdots & b_i^{2p,k} \\ \vdots & \vdots & \ddots & \vdots \\ b_i^{p(p-1)+1,k} & b_i^{p^2,k} & \cdots & b_i^{p^2,k} \end{pmatrix} \qquad (13) $$

$$ \mathbf{B}_i^c = \begin{pmatrix} b_i^{1,1} & b_i^{2,1} & b_i^{p+1,1} & b_i^{p+2,1} & b_i^{1,2} & b_i^{2,2} & b_i^{p+1,2} & b_i^{p+2,2} & b_i^{1,3} \\ b_i^{2,1} & b_i^{3,1} & b_i^{p+2,1} & b_i^{p+3,1} & b_i^{2,2} & b_i^{3,2} & b_i^{p+2,2} & b_i^{p+3,2} & b_i^{2,3} \\ \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \end{pmatrix} $$

Then the function to minimize is

$$ g(\delta \mathbf{W}_l) = ||\mathbf{V}_{\text{goal}}^l - \mathbf{B}^c \delta \mathbf{W}_l||_{\text{Tr}}^2 $$

$$ \text{where } \mathbf{B}^c := (\mathbf{B}_1^c \quad \dots \quad \mathbf{B}_n^c). \qquad \square $$

## C.2 PROPOSITION 3.2

We define the matrices $N := \frac{1}{n} \mathbf{B}_{l-2} (\mathbf{V}_{\text{goalproj}}^l)^T$ and $S := \frac{1}{n} \mathbf{B}_{l-2} \mathbf{B}_{l-2}^T$. Let us denote its SVD by $S = U \Sigma U^T$, and note $S^{-\frac{1}{2}} := U \sqrt{\Sigma^{-1}} U^T$ and consider the SVD of the matrix $S^{-\frac{1}{2}} N = \sum_{k=1}^R \lambda_k \mathbf{u}_k \mathbf{v}_k^T$ with $\lambda_1 \ge \dots \ge \lambda_R \ge 0$, where $R$ is the rank of the matrix $N$. Then:

**Proposition C.1 (3.2).** The solution of (5) can be written as:

* optimal number of neurons: $K^* = R$

* their optimal weights: $(\alpha_k^*, \omega_k^*) = (\text{sign}(\lambda_k)\sqrt{\lambda_k}S^{-\frac{1}{2}}\mathbf{u}_k, \sqrt{\lambda_k}\mathbf{v}_k)$ for $k = 1, \dots, R$.

Moreover for any number of neurons $K \le R$, and associated scaled weights $\theta_{\leftarrow\leftrightarrow}^{K,*}$, the expressivity gain and the first order in $\eta$ of the loss improvement due to the addition of these $K$ neurons are equal and can be quantified very simply as a function of the eigenvalues $\lambda_k$:

$$ \begin{align*} \Psi_{\theta \oplus \theta_{\leftarrow\leftrightarrow}^{K,*}}^{l} &= \Psi_{\theta}^{l} - \sum_{k=1}^{K} \lambda_{k}^{2} \\ \mathcal{L}(f_{\theta \oplus \theta_{\leftarrow\leftrightarrow}^{K,*}}) &= \mathcal{L}(f_{\theta}) + \frac{\sigma_{l}^{\prime}(0)}{\eta} \sum_{k=1}^{K} \lambda_{k}^{2} + o(||\theta_{\leftarrow\leftrightarrow}^{K,*}||^{2}) \end{align*} $$
<figure><img src="image_11.png" /><figcaption>Figure 10: Changing the tangent space with different values of $(\omega_k)_{k=1}^K$.</figcaption></figure>

## A.6 Adding convolutional neurons

To add a convolutional neuron at layer $l-1$, one should add a kernel at layer $l-1$ and expand one dimension to all the kernels in layer $l$ to match the new dimension of the post-activity, see Figure 11.

<figure><img src="image_12.png" /><figcaption>Figure 11: Adding one convolutional neuron at layer one for an input with tree channels.</figcaption></figure>

# B Theoretical comparison with other approaches

## B.1 GradMax method

To facilitate reading we remove the layer index of each quantity, i.e. $b := b_{l-2}$, $B := B_{l-2}$, $V_{goal} := V_{goal}^l$ and $V_{goal_{proj}} := V_{goal_{proj}}^l$.

The theoretical approach of GradMax is to add neurons with zero fan-in weights and choose the fan-out weights that would decrease the loss as much as possible after one gradient step. We note $\Omega$ the fan-out weights of such neurons and perform the addition at layer $l-1$ at time $t$. After one gradient step, i.e. $t \to t+1$,
Proof

We first compute the proof for a linear layer.

The optimal neurons $n_1, ..., n_K$ are defined by $n_i := (\alpha_i, \omega_i)$ and are the solution of the optimization problem :

$$ \arg\min_{\delta\mathbf{W}_l, \delta\theta_{l-1}^K \leftrightarrow l} \left\| \underbrace{\mathbf{V}_{\text{goal}\text{proj}}^l}_{\text{goalproj}} - \delta\mathbf{W}_l \mathbf{B}_{l-1} - \mathbf{\Omega}\mathbf{A}^T \mathbf{B}_{l-2} \right\|_{\text{Tr}}^2 $$

$$ \text{where } \mathbf{\Omega} := (\omega_1 \ \dots \ \omega_K) \quad \text{and} \quad \mathbf{A} := (\alpha_1 \ \dots \ \alpha_K) $$

This is equivalent to :

$$ \arg\min_{C=\mathbf{\Omega}\mathbf{A}^T} \left\| \underbrace{\mathbf{V}_{\text{goal}}^l}_{\text{goal}} - \delta\mathbf{W}_l \mathbf{B}_{l-1} - \mathbf{C}\mathbf{B}_{l-2} \right\|_{\text{Tr}}^2 \quad (14) $$

Then $C^* = S^+N$. Taking $R = \text{rank}(S^+N)$ and a family $(\alpha_k, \omega_k)_{1,...,K}$ such that $\mathbf{\Omega}\mathbf{A}^T = \sum_k \omega_k \alpha_k^T = S^+N$ is an optimal solution. But what if we decide to only add $K < R$ neurons ?

$$ \begin{aligned} \arg\min_{\theta^K} \left\{ \frac{1}{n} \left\| \mathbf{V}_{\text{goal}\text{proj}}^l - \mathbf{V}^l(\theta^K) \right\|_{\text{Tr}}^2 \right\} &= \arg\min_{\theta^K} \left\{ -\frac{2}{n} \left\langle \mathbf{V}_{\text{goal}\text{proj}}^l, \mathbf{V}^l(\theta^K) \right\rangle_{\text{Tr}} + \frac{1}{n} \left\| \mathbf{V}^l(\theta^K) \right\|_{\text{Tr}}^2 \right\} \\ &= \arg\min_{\theta^K} \frac{1}{n} g(\theta^K) \end{aligned} $$

We have

$$ \begin{aligned} \frac{1}{n} g(\theta^K) &= -\frac{2}{n} \sum_{i}^{n} \sum_{k} \mathbf{v}_{\text{goal\text{proj}}}^{l}(\mathbf{x}_i)^T (\boldsymbol{\alpha}_k^T \mathbf{b}_{l-2}(\mathbf{x}_i)) \boldsymbol{\omega}_k \\ &\quad + \frac{1}{n} \sum_{k,j}^{K} \sum_{i}^{n} (\boldsymbol{\alpha}_k^T \mathbf{b}_{l-2}(\mathbf{x}_i)) \boldsymbol{\omega}_k^T \boldsymbol{\omega}_j (\boldsymbol{\alpha}_j^T \mathbf{b}_{l-2}(\mathbf{x}_i)) \\ &= -2 \sum_{k}^{K} \boldsymbol{\alpha}_k^T \left( \frac{1}{n} \sum_{i}^{n} \mathbf{b}_{l-2}(\mathbf{x}_i) \mathbf{v}_{\text{goal\text{proj}}}^{l}(\mathbf{x}_i)^T \right) \boldsymbol{\omega}_k \\ &\quad + \sum_{k,j}^{K} \boldsymbol{\omega}_k^T \boldsymbol{\omega}_j \boldsymbol{\alpha}_k^T \left( \frac{1}{n} \sum_{i}^{n} \mathbf{b}_{l-2}(\mathbf{x}_i) \mathbf{b}_{l-2}(\mathbf{x}_i)^T \right) \boldsymbol{\alpha}_j \\ &= -2 \sum_{k}^{K} \boldsymbol{\alpha}_k^T \mathbf{N} \boldsymbol{\omega}_k + \sum_{k,j}^{K} \boldsymbol{\omega}_k^T \boldsymbol{\omega}_j \boldsymbol{\alpha}_k^T \mathbf{S} \boldsymbol{\alpha}_j \end{aligned} $$

$$ \text{with } \mathbf{N} := \frac{1}{n} \mathbf{B}_{l-2} (\mathbf{V}_{\text{goal\text{proj}}}^{l})^T \text{ and } \mathbf{S} := \frac{1}{n} \mathbf{B}_{l-2} \mathbf{B}_{l-2}^T. $$

$$ \text{Consider the SVD of } \mathbf{S} = \mathbf{U}\mathbf{\Sigma}\mathbf{U}^T. \text{ Define } \mathbf{S}^{\frac{1}{2}} := \mathbf{U}\sqrt{\mathbf{\Sigma}}\mathbf{U} \text{ and } \mathbf{S}^{-\frac{1}{2}} := \mathbf{U}\sqrt{\mathbf{\Sigma}^{-1}}\mathbf{U}^T. $$

$$ \text{Consider also the SVD of } \mathbf{S}^{-\frac{1}{2}}\mathbf{N} = \sum_{r=1}^{R} \lambda_r \mathbf{v}_r \mathbf{e}_r^T. $$

Note also $\beta_k := \mathbf{S}^{\frac{1}{2}}\boldsymbol{\alpha}_k$. Then :

$$ \begin{aligned} -\sum_{k=1}^{K} \boldsymbol{\alpha}_k^T \mathbf{N} \boldsymbol{\omega}_k &= -\sum_{k} \boldsymbol{\beta}_k^T \mathbf{S}^{-\frac{1}{2}} \mathbf{N} \boldsymbol{\omega}_k \\ &= -\text{Tr} \left( \sum_k \sum_r \lambda_r (\boldsymbol{\beta}_k^T \mathbf{v}_r \mathbf{e}_r^T) \boldsymbol{\omega}_k \right) \end{aligned} $$
and considering a learning rate equal to 1, the decrease of loss is :

$$ \mathcal{L}^{t+1} \approx \mathcal{L}^t + \langle \nabla_{\theta} \mathcal{L}, \delta\theta \rangle + \langle \nabla_{\Omega} \mathcal{L}, \delta\Omega \rangle \quad (20) $$

Taking the direction of the usual gradient descent, ie $\delta\theta = -\nabla_{\theta}\mathcal{L}$ and $\delta\Omega = -\nabla_{\Omega}\mathcal{L}$, we have :

$$ \mathcal{L}^{t+1} \approx \mathcal{L}^t - ||\nabla_{\theta}\mathcal{L}||^2 - ||\nabla_{\Omega}\mathcal{L}||^2 \quad (21) $$

The output weights of the new neurons as formulated in the original paper Evci et al. (2022) at eq (11) are the solution of :

$$ (\omega_1^*, \dots, \omega_K^*) := \Omega^* = \arg\max_{\Omega} ||\nabla_{\Omega}\mathcal{L}||^2 \quad \text{s.t.} \quad ||\Omega||^2 \le c \quad (22) $$

we remark that :

$$ \begin{aligned} ||\nabla_{\Omega}\mathcal{L}||^2 &= \left\| \sum_i b(x_i) v_{\text{goal}}^{T}(x_i) \Omega \right\|^2 \\ &= \left\| B V_{\text{goal}}^{T} \Omega \right\|^2 \\ &= \left\| \tilde{N} \Omega \right\|^2 \end{aligned} \qquad \tilde{N} := B V_{\text{goal}}^{T} $$

It follows that the fan-out of the neurons computed by GradMax are the solution of the problem :

$$ \Omega^* := \arg\max_{\Omega} ||\tilde{N}\Omega|| \quad \text{s.t.} \quad ||\Omega||^2 \le c \quad (23) $$

To compare this optimization problem with TINY, we use the following proposition:

**Proposition B.1.** $\forall D \in \mathbb{R}^{p,q}, B \in \mathbb{R}^{k,q}$,

$$ \exists c \in \mathbb{R} \quad \text{s.t.} \quad \arg\min_{H \in \mathbb{R}^{p,k}} ||D - HB||^2 = \arg\max_{H, ||HB||^2 \le c} \langle D, HB \rangle $$

The proof can be found in B.1.

Taking $V_{\text{goal}}$ as $D$ and $V = \Omega A^T B$ as $HB$, we can reformulate TINY optimization problem 8 as :

$$ A^*, \Omega^* = \arg\max_{A, \Omega} \langle V(A, \Omega), V_{\text{goalproj}} \rangle \quad \text{s.t.} \quad ||V(A, \Omega)||^2 \le c \quad (24) $$

We remark that

$$ \begin{aligned} \langle V(A, \Omega), V_{\text{goalproj}} \rangle &= \langle \Omega A^T B, V_{\text{goalproj}} \rangle \\ &= \text{Tr}(B^T A \Omega^T V_{\text{goalproj}}) \\ &= \text{Tr}(A \Omega^T V_{\text{goalproj}} B^T) \\ &= \langle \Omega A^T, V_{\text{goalproj}} B^T \rangle \end{aligned} $$

With the definition $N := BV_{\text{goalproj}}^T$,

$$ \langle V(A, \Omega), V_{\text{goalproj}} \rangle = \langle A\Omega^T, N \rangle \quad (25) $$

For the constrain on $V(A, \Omega)$, we perform the change of variable $\tilde{A} := S^{\frac{1}{2}}A$, it follows that :

$$ \begin{aligned} ||V(A, \Omega)||^2 &= ||\Omega A^T B||^2 \\ &= \text{Tr}(A\Omega^T \Omega A^T S) \\ &= ||\Omega(S^{\frac{1}{2}}A)^T|| \\ &= ||\Omega \tilde{A}^T|| \end{aligned} \qquad S = BB^T $$
Using the linearity of the Trace and that Tr(AB) = Tr(BA), we have :

$$
\begin{align*}
-\sum_{k=1}^{K} \alpha_k^T N \omega_k &= -\operatorname{Tr} \left( \sum_k \sum_r \lambda_r \omega_k \beta_k^T v_r e_r^T \right) \\
&= -\operatorname{Tr} \left( \sum_k \omega_k \beta_k^T \sum_r \lambda_r v_r e_r^T \right) \\
&= -\left\langle \sum_k \beta_k \omega_k^T, \sum_r \lambda_r v_r e_r^T \right\rangle_{\operatorname{Tr}} \quad \text{with} \quad \langle \mathbf{A}, \mathbf{B} \rangle_{\operatorname{Tr}} = \operatorname{Tr}(\mathbf{A}^T \mathbf{B})
\end{align*}
$$

For the second sum :

$$
\begin{align*}
\sum_{k,j}^{K} \omega_k^T \omega_j \alpha_k^T S \alpha_j &= \sum_{k,j} (\omega_k^T \omega_j) (\beta_j^T \beta_k) \\
&= \operatorname{Tr} \left( \sum_{k,j} ((\omega_k^T \omega_j) \beta_j^T) \beta_k \right) \\
&= \operatorname{Tr} \left( \sum_{k,j} \beta_k \omega_k^T \omega_j \beta_j^T \right) \\
&= \| \sum_k \omega_k \beta_k^T \|_{\mathrm{Tr}}^2 \quad \text{with} \quad \| \mathbf{A} \|_{\mathrm{Tr}} = \sqrt{\operatorname{Tr}(\mathbf{A}^T \mathbf{A})} \\
&= \| \sum_k \beta_k \omega_k^T \|_{\mathrm{Tr}}^2
\end{align*}
$$

Then we have :

$$
\arg\min_{K, \theta \leftrightarrow} \frac{1}{n} g(\alpha, \omega) = \arg\min_{K, \alpha = S^{-1/2}\gamma, \omega} \left\| S^{-1/2} N - \sum_{k=1}^{K} \beta_k \omega_k^T \right\|_{\mathrm{Tr}}^2
$$

The solution of such problems is given by the paper Eckart & Young (1936). For any $K \le R :=$
rank($S^{-1/2}N$), the best option is given by $\sum_{k=1}^K \beta_k \omega_k^T = \sum_{r=1}^K \lambda_r v_r e_r^T$. Thus we have that
$\sum_k^R \omega_k \alpha_k^T = S^{-1/2} \sum_k^R \lambda_k \beta_k \omega_k^T = S^{-1} N$.

We now consider the matrix $S^{-1/2}N$. The minimization also yields the following properties at the
optimum:

$$
\text{for } k \neq j, \quad \langle \beta_k \omega_k^T, \beta_j \omega_j^T \rangle_{\text{Tr}} = 0
$$

$$
\begin{align*}
\| S^{-1/2} \mathbf{N} - \sum_{k=1}^{K} \beta_k \omega_k^T \|_{\mathrm{Tr}}^2 &= \sum_{r=K+1}^{R} \lambda_r^2 \\
&= \| S^{-1/2} \mathbf{N} \|_{\mathrm{Tr}}^2 - \left\| \sum_{k=1}^{K} \beta_k \omega_k^T \right\|_{\mathrm{Tr}}^2
\end{align*}
$$

Furthermore :

$$
\begin{align*}
\frac{1}{n} \| \mathbf{V}_{\text{goal}^{\text{proj}}}^{l} - \mathbf{V}(\theta_{\leftrightarrow}^{K,*}) \|_{\text{Tr}}^{2} &= \frac{1}{n} \| \mathbf{V}_{\text{goal}^{\text{proj}}}^{l} \|_{\text{Tr}}^{2} + \| \mathbf{S}^{-\frac{1}{2}} \mathbf{N} - \sum_{k} \beta_{k} \omega_{k}^{T} \|^{2} - \| \mathbf{S}^{-\frac{1}{2}} \mathbf{N} \|_{\text{Tr}}^{2} \\
&= \sum_{r=K+1}^{R} \lambda_{r}^{2} + \frac{1}{n} \| \mathbf{V}_{\text{goal}^{\text{proj}}}^{l} \|_{\text{Tr}}^{2} - \| \mathbf{S}^{-\frac{1}{2}} \mathbf{N} \|_{\text{Tr}}^{2} \\
&= -\sum_{r=1}^{K} \lambda_{r}^{2} + \frac{1}{n} \| \mathbf{V}_{\text{goal}^{\text{proj}}}^{l} \|_{\text{Tr}}^{2}
\end{align*}
$$
With the same change of variable, the initial scalar product Equation (25) is :

$$ \langle V(\mathbf{A}, \mathbf{\Omega}), V_{\text{goal}_{\text{proj}}} \rangle = \langle \mathbf{\Omega} \tilde{\mathbf{A}}^T \mathbf{S}^{-\frac{1}{2}}, \mathbf{N}^T \rangle = \langle \mathbf{\Omega} \tilde{\mathbf{A}}^T, \mathbf{N}^T \mathbf{S}^{-\frac{1}{2}} \rangle = \langle \tilde{\mathbf{A}} \mathbf{\Omega}^T, \mathbf{S}^{-\frac{1}{2}} \mathbf{N} \rangle \quad (26) $$

TINY optimization problem is now equivalent to :

$$ \tilde{\mathbf{A}}^*, \mathbf{\Omega}^* = \arg\max_{\tilde{\mathbf{A}}, \mathbf{\Omega}} \langle \tilde{\mathbf{A}}\mathbf{\Omega}^T, \mathbf{S}^{-\frac{1}{2}}\mathbf{N} \rangle \quad \text{s.t.} \quad ||\mathbf{\Omega}\tilde{\mathbf{A}}^T||^2 \le c \quad (27) $$

To maximize the scalar product, we choose $\tilde{\mathbf{A}}\mathbf{\Omega}^T = \mathbf{S}^{-\frac{1}{2}}\mathbf{N}$. A solution for $(\tilde{\mathbf{A}}, \mathbf{\Omega})$ is the (left, right) eigenvectors of the matrix $\mathbf{S}^{-\frac{1}{2}}\mathbf{N}$. It implies that :

$$ \mathbf{\Omega}^* := \arg\max_{\mathbf{\Omega}} \left\| \mathbf{S}^{-\frac{1}{2}} \mathbf{N} \mathbf{\Omega} \right\|^2 \quad \text{s.t.} \quad ||\mathbf{\Omega}|| \le \tilde{c} \quad (28) $$

One can note three differences between GradMax optimization problem and the last formulation of TINY (Equation (28)):

* First, the matrix $\tilde{\mathbf{N}}$ is not defined using the projection of the desired update $V_{\text{goal}_{\text{proj}}}^{l+1}$. As a consequence, GradMax does not take into account redundancy, and on the opposite will actually try to add new neurons that are as redundant as possible with the part of the goal update that is already feasible with already-existing neurons.

* Second, the constraint lies in the weight space for GradMax method while it lies in the pre-activation space in our case. The difference is that GradMax relies on the Euclidean metric in the space of parameters, which arguably offers less meaning than the Euclidean metric in the space of activities. Essentially this is the same difference as between the standard L2 gradient w.r.t. parameters and the natural gradient, which takes care of parameter redundancy and measures all quantities in the output space in order to be independent from the parameterization. In practice we do observe that the "natural" gradient direction improves the loss better than the usual L2 gradient.

* Third, our fan-in weights are not set to 0 but directly to their optimal values (at first order).

We now prove the proposition B.1.

*Proof.* Indeed,

$$ \arg\min_{\mathbf{H}} ||\mathbf{D} - \mathbf{H}\mathbf{B}||^2 = \arg\min_{\mathbf{H}} ||\mathbf{H}\mathbf{B}||^2 - 2\langle \mathbf{D}, \mathbf{H}\mathbf{B} \rangle \quad (29) $$

$$ = \arg\min_{\mathbf{H}} ||\mathbf{H}\mathbf{B}||^2 - 2||\mathbf{H}\mathbf{B}|| \left\langle \mathbf{D}, \frac{\mathbf{H}\mathbf{B}}{||\mathbf{H}\mathbf{B}||} \right\rangle \quad (30) $$

$$ = \underset{h\mathbf{U}, \ ||\mathbf{H}\mathbf{B}||=h, \ \mathbf{U}=\frac{\mathbf{H}\mathbf{B}}{||\mathbf{H}\mathbf{B}||}}{\arg\min} \ h^2 - 2h\langle \mathbf{D}, \mathbf{U} \rangle \quad (31) $$

(32)

We note $\mathbf{U}^* := \arg\max_{\mathbf{U}=\frac{\mathbf{H}\mathbf{B}}{||\mathbf{H}\mathbf{B}||}} \langle \mathbf{D}, \mathbf{U} \rangle$ which depends on $\mathbf{B}$ and $\mathbf{D}$ but does not depend on $h$. Then :

$$ \arg\min_{\mathbf{H}} ||\mathbf{D} - \mathbf{H}\mathbf{B}||^2 = \arg\min_{h\mathbf{U}^*, h \ge 0} h^2 - 2h \langle \mathbf{D}, \mathbf{U}^* \rangle \quad (33) $$

$$ = h^* \mathbf{U}^* \quad (34) $$

With the convention that $\frac{0}{||0||} = 0$. □
We note $V_{\text{goal}_{\text{proj}}^l}(\delta\mathbf{W}_l^*) := V_{\text{goal}_{\text{proj}}^l}$. Suppose that $B_{l-1}$ and $B_{l-2}$ are orthogonal for the trace scalar product, then when adding the new neurons, the impact on the global loss is:

$$ \mathcal{L}(f_{\theta \oplus \theta_{\leftrightarrow}^K}) = \frac{1}{n} \sum_{i=1}^{n} L(f_{\theta}(\mathbf{x}_i), \mathbf{y}_i) - \frac{\gamma}{\eta} \frac{1}{n} \sigma_l'(0) \langle \mathbf{V}^l(\theta_{\leftrightarrow}^{K,*}), \mathbf{V}_{\text{goal}_{\text{proj}}^l} \rangle_{\text{Tr}} + o(1) $$

We also have the following property:

$$
\begin{aligned}
& \arg\min_{\theta_{\leftrightarrow}^K} \left\{ \frac{1}{n} \| \mathbf{V}_{\text{goal}_{\text{proj}}^l} - \mathbf{V}^l(\theta_{\leftrightarrow}^K) \|_{\text{Tr}}^2 \right\} \\
&= \arg\min_{H \ge 0} \quad \arg\min_{\theta_{\leftrightarrow}^K, \| \mathbf{V}^l(\theta_{\leftrightarrow}^K) \|_{\text{Tr}} = H} \left\{ \frac{1}{n} \| \mathbf{V}_{\text{goal}_{\text{proj}}^l} - \mathbf{V}^l(\theta_{\leftrightarrow}^K) \|_{\text{Tr}}^2 \right\} \\
&= \arg\min_{H \ge 0} \quad \arg\min_{\theta_{\leftrightarrow}^K, \| \mathbf{V}^l(\theta_{\leftrightarrow}^K) \|_{\text{Tr}} = H} \left\{ -\frac{2}{n} \langle \mathbf{V}_{\text{goal}_{\text{proj}}^l}, \mathbf{V}^l(\theta_{\leftrightarrow}^K) \rangle_{\text{Tr}} + \frac{1}{n} \| \mathbf{V}^l(\theta_{\leftrightarrow}^K) \|_{\text{Tr}}^2 \right\} \\
&= \arg\min_{H \ge 0} \quad \arg\min_{\theta_{\leftrightarrow}^K, \| \mathbf{V}^l(\theta_{\leftrightarrow}^K) \|_{\text{Tr}} = H} \left\{ -\frac{2}{n} \langle \mathbf{V}_{\text{goal}_{\text{proj}}^l}, \mathbf{V}^l(\theta_{\leftrightarrow}^K) \rangle_{\text{Tr}} + \frac{1}{n} H^2 \right\} \\
&= \arg\min_{H \ge 0} \quad \arg\min_{\theta_{\leftrightarrow}^K, \| \mathbf{V}^l(\theta_{\leftrightarrow}^K)^* \|_{\text{Tr}} = 1} \left\{ -H \langle \mathbf{V}_{\text{goal}_{\text{proj}}^l}, \mathbf{V}^l(\theta_{\leftrightarrow}^K)^* \rangle_{\text{Tr}} + \frac{1}{2} H^2 \right\}
\end{aligned}
$$

with $\mathbf{V}^l(\theta_{\leftrightarrow}^K)^*$ the solution of the second arg min (ie for $H=1$). Then the norm minimizing the first argmin is given by:

$$ H^* = \langle \mathbf{V}_{\text{goal}_{\text{proj}}^l}, \mathbf{V}^l(\theta_{\leftrightarrow}^K)^* \rangle_{\text{Tr}} $$

Furthermore

$$ \min_{\theta_{\leftrightarrow}^K} \left\{ \frac{1}{n} \| \mathbf{V}_{\text{goal}_{\text{proj}}^l} - \mathbf{V}^l(\theta_{\leftrightarrow}^K) \|_{\text{Tr}}^2 \right\} = - \sum_{r=1}^{K} \lambda_r^2 + \frac{1}{n} \| \mathbf{V}_{\text{goal}_{\text{proj}}^l} \|_{\text{Tr}}^2 \quad (15) $$

$$ \min_{\theta_{\leftrightarrow}^K} \left\{ \frac{1}{n} \| \mathbf{V}_{\text{goal}_{\text{proj}}^l} - \mathbf{V}^l(\theta_{\leftrightarrow}^K) \|_{\text{Tr}}^2 \right\} = -\frac{1}{n} H^{*2} + \frac{1}{n} \| \mathbf{V}_{\text{goal}_{\text{proj}}^l} \|_{\text{Tr}}^2 \quad (16) $$

$$ \Rightarrow H^* = \langle \mathbf{V}_{\text{goal}_{\text{proj}}^l}, \mathbf{V}^l(\theta_{\leftrightarrow}^K)^* \rangle_{\text{Tr}} = \sqrt{\sum_{r=1}^{K} \lambda_r^2} \times \sqrt{n} \quad (17) $$

$$ \mathbf{V}^l(\theta_{\leftrightarrow}^{K,*}) = H^* \mathbf{V}^l(\theta_{\leftrightarrow}^{K,*})^* \quad (18) $$

$$ \langle \mathbf{V}^l(\theta_{\leftrightarrow}^{K,*}), \mathbf{V}_{\text{goal}_{\text{proj}}^l} \rangle_{\text{Tr}} = H^* \times \langle \mathbf{V}_{\text{goal}_{\text{proj}}^l}, \mathbf{V}^l(\theta_{\leftrightarrow}^{K,*}) \rangle_{\text{Tr}} = H^{*2} \quad (19) $$

where the last equality is given by the optimisation of $||\mathbf{S}^{-\frac{1}{2}}\mathbf{N} - \sum_{k=1}^K \mathbf{u}_k \omega_k^T||_{\text{Tr}}^2$. So minimizing the scalar product $-\langle \mathbf{V}_{\text{goal}_{\text{proj}}^l}(\delta\mathbf{W}_l^*), \mathbf{V}^l(\theta_{\leftrightarrow}^K)^* \rangle_{\text{Tr}}$ for fixed norm of $\mathbf{V}^l(\theta_{\leftrightarrow}^K)$ is equivalent to minimizing the norm $||\mathbf{V}_{\text{goal}_{\text{proj}}^l}(\delta\mathbf{W}_l^*) - \mathbf{V}^l(\theta_{\leftrightarrow}^K)||_{\text{Tr}}^2$.

$$ \mathcal{L}(f_{\theta \oplus \theta_{\leftrightarrow}^K}) = \frac{1}{n} \sum_{i=1}^{n} \mathcal{L}(f_{\theta}(\mathbf{x}_i), \mathbf{y}_i) - \frac{1}{\eta} \sigma_l'(0) \sum_{r=1}^{K} \lambda_r^2 + o(1) $$

For convolutional layers, the same reasoning can be applied. Consider one adds one convolution layer, ie $K=1$. Use $B_i^c$ defined in the first proof and $T_j$ the linear application selecting the
## B.2 NORTH Preactivation

In paper Maile et al. (2022), fan-out weights are initialized to 0 while fan-in weights are initialized as $\alpha_i = S^{-1}B_{l-2}V_{A_{l-1}}r_i$ where $r_i$ is a random vector and $V_{Z_{l-1}} \in \mathbb{R}^{n, |\ker(A_{l-1}^T)|}$ is a matrix consisting of orthogonal vectors of the kernel of pre-activations $A_{l-1}$. In our paper fan-in weights are initialized as $\alpha_i = S^{-\frac{1}{2}}B_{l-2}V_{goal_{proj}}^T v_i = S^{-\frac{1}{2}}B_{l-2}P_{ker(B_{l-1})}V_{goal}^T v_i$, where $P_{ker(B_{l-1})} \in \mathbb{R}^{n,n}$ is the projector on the kernel of the linear application $B_{l-1}$ and $v_i$ are the right eigenvectors of the matrix $S^{-\frac{1}{2}}N$.

The main difference is thus that we use the backpropagation to find the best $v_i$ or $r_i$ directly, while the NORTH approach tries random directions $r_i$ to explore the space of possible neuron additions.

# C Proofs of Part 3

## C.1 Proposition 3.1

Denoting by $M^+$ the generalized (pseudo-)inverse of $M$, we have:

$$ \delta \mathbf{W}_l^* = \frac{1}{n} \mathbf{V}_{\text{goal}}^l \mathbf{B}_{l-1}^T \left( \frac{1}{n} \mathbf{B}_{l-1} \mathbf{B}_{l-1}^T \right)^+ \quad \text{and} \quad \mathbf{V}_0^l = \frac{1}{n} \mathbf{V}_{\text{goal}}^l \mathbf{B}_{l-1}^T \left( \frac{1}{n} \mathbf{B}_{l-1} \mathbf{B}_{l-1}^T \right)^+ \mathbf{B}_{l-1}. $$

**Proof.** Fully connected layers

Consider the function

$$ g(\delta \mathbf{W}) := \left\| \mathbf{V}_{\text{goal}}^l - \delta \mathbf{W} \mathbf{B}_{l-1} \right\|_F^2 \quad (35) $$

then:

$$ g(\delta \mathbf{W} + \mathbf{H}) = \|\mathbf{V}_{\text{goal}}^l - \delta \mathbf{W} \mathbf{B}_{l-1} - \mathbf{H} \mathbf{B}_{l-1}\|^2 \quad (36) $$

$$ = g(\delta \mathbf{W}) - 2 \langle \mathbf{V}_{\text{goal}}^l - \delta \mathbf{W} \mathbf{B}_{l-1}, \mathbf{H} \mathbf{B}_{l-1} \rangle + o(||\mathbf{H}||) \quad (37) $$

$$ = g(\delta \mathbf{W}) - 2 \langle (\mathbf{V}_{\text{goal}}^l - \delta \mathbf{W} \mathbf{B}_{l-1}) \mathbf{B}_{l-1}^T, \mathbf{H} \rangle + o(||\mathbf{H}||) \quad (38) $$

By identification $\nabla_{\delta \mathbf{W}} g(\delta \mathbf{W}) = -2 (\mathbf{V}_{\text{goal}}^l - \delta \mathbf{W} \mathbf{B}_{l-1}) \mathbf{B}_{l-1}^T$, and thus:

$$ \nabla_{\delta \mathbf{W}} g(\delta \mathbf{W}) = 0 \implies \mathbf{V}_{\text{goal}}^l \mathbf{B}_{l-1}^T = \delta \mathbf{W} \mathbf{B}_{l-1} \mathbf{B}_{l-1}^T $$

Using that $g$ is convex and the definition of the generalized inverse, we get:

$$ \delta \mathbf{W}_l^* = \frac{1}{n} \mathbf{V}_{\text{goal}}^l \mathbf{B}_{l-1}^T \left( \frac{1}{n} \mathbf{B}_{l-1} \mathbf{B}_{l-1}^T \right)^+ $$

as one solution.

## Convolutional layers

For convolutional layers we aim to solve (where we dropped the index $l-1$ for readability):

$$ \arg \min_{\delta \mathbf{W}} \|\mathbf{V}_{\text{goal}} - \text{Conv}_{\delta \mathbf{W}}(\mathbf{B})\|_F \quad (39) $$

We convert this in a linear regression by transforming the convolution in a matrix multiplication. First we reshape and permute:
activities for the j-pixel, then one has to minimize the expression:

$$
\begin{align*}
g(\theta_{\leftrightarrow}^{1}) &= \sum_{m} \sum_{i} \sum_{j=1} (\omega_{m}^{T} T_{j} B^{c} \alpha - V_{\text{goal},j,m}^{i})^{2} \\
&= \sum_{m} \sum_{i} \sum_{j=1} (\omega_{m}^{T} T_{j} B_{i}^{c} \alpha)^{2} - 2\omega_{m}^{T} T_{j} B_{i}^{c} \alpha V_{\text{goal},j,m}^{i} + C \\
&= \sum_{m} \sum_{i} \sum_{j=1} \operatorname{Tr}(\omega_{m}^{T} T_{j} B_{i}^{c} \alpha)^{2} - 2\omega_{m}^{T} T_{j} B_{i}^{c} \alpha V_{\text{goal},j,m}^{i} + C \\
&= \sum_{m} \sum_{i} \sum_{j=1} \operatorname{Tr}(T_{j} B_{i}^{c} \alpha \omega_{m}^{T})^{2} - 2\omega_{m}^{T} T_{j} B_{i}^{c} \alpha V_{\text{goal},j,m}^{i} + C
\end{align*}
$$

for some constant C. We have the property that $\langle T_j^T B_i^c \alpha \omega_m^T \rangle_{\text{Tr}}^2 = \text{Tr}(T_j B_i^c \alpha \omega_m^T)^2 = \|T_j B_i^c \alpha \omega_m^T\|_{\text{Tr}}^2$. Ignoring the constant C:

$$
\begin{align*}
g(\theta_{\leftrightarrow}^{1}) &= \sum_{m} \operatorname{Tr}(\omega_{m} \alpha^{T} \left( \sum_{i} B_{i}^{c T} \sum_{j} T_{j}^{T} T_{j} B_{i}^{c} \right) \alpha \omega_{m}^{T}) - 2\omega_{m}^{T} \sum_{i,j} T_{j} B_{i}^{c} V_{\text{goal},j,m}^{i} \alpha \\
&= \sum_{m} \alpha^{T} \left( \sum_{i} B_{i}^{c T} \sum_{j} T_{j}^{T} T_{j} B_{i}^{c} \right) \alpha \omega_{m}^{T} \omega_{m} - 2\omega_{m}^{T} \sum_{i,j} T_{j} B_{i}^{c} V_{\text{goal},j,m}^{i} \alpha \\
&= \alpha^{T} \left( \sum_{i} B_{i}^{c T} \sum_{j} T_{j}^{T} T_{j} B_{i}^{c} \right) \alpha \omega^{T} \omega - 2 \sum_{m} \omega_{m}^{T} \sum_{i,j} T_{j} 1_{\text{full}} V_{\text{goal}}^{i} 1_{j,m} B_{i}^{c} \alpha \\
&= \alpha^{T} S \alpha \omega^{T} \omega - 2 \sum_{m} \omega_{m}^{T} \sum_{i} F_{i}^{m} B_{i}^{c} \alpha \\
&= \alpha^{T} S \alpha \omega^{T} \omega - 2\omega N \alpha
\end{align*}
$$

$$
\text{with } T_j = \begin{pmatrix}
\underbrace{0 \cdot \dots \ 0}_{j-1+\lfloor j/(p-1) \rfloor} & 1 & 0 & \dots & \dots \\
\underbrace{0 \cdot \dots \ 0}_{j-1+\lfloor j/(p-1) \rfloor} & 0 & 1 & \dots & \dots \\
\underbrace{0 \cdot \dots \ 0}_{j-1+\lfloor j/(p-1) \rfloor} & \underbrace{0 \cdot \dots \ 0}_{31} & 1 & 0 & \dots \\
\underbrace{0 \cdot \dots \ 0}_{j-1+\lfloor j/(p-1) \rfloor} & \underbrace{0 \cdot \dots \ 0}_{31} & 0 & 1 & 0 \\
\end{pmatrix} \quad \text{for a kernel size equal to } (2,2). \quad \square
$$

### C.3 PROPOSITION AND REMARK 3.3

Suppose $S$ is semi definite, we note $S = S^{1/2}S^{1/2}$. Solving (7) is equivalent to find the K first eigenvectors $\alpha_k$ associated to the K largest eigenvalues $\lambda$ of the generalized eigenvalue problem:

$$NN^T \alpha_k = \lambda S \alpha_k$$

#### Proof

This is equivalent to maximizing the following generalized Rayleigh quotient (which is solvable by the LOBPCG technique):

$$
\begin{align*}
\alpha^* &= \max_x \frac{\alpha^T N N^T \alpha}{\alpha^T S \alpha} \\
p^* &= \max_{p=S^{1/2}\alpha} \frac{p^T S^{-1/2} N N^T S^{-1/2} p}{p^T p} \\
p^* &= \max_{\|p\|=1} ||N^T S^{-1/2} p|| \\
\alpha^* &= S^{-1/2} p^*
\end{align*}
$$
* $\delta W \in (C[+1], C, d[+1], d[+1])$ is transformed in $\delta W_F \in (C[+1], Cd[+1], d[+1])$

* $V_{\text{goal}} \in (n, C[+1], H[+1], W[+1])$ is transformed in $V_{\text{goal}} \in (nH[+1], W[+1], C[+1])$

Then we can define $B^c \in (n, Cd[+1], d[+1], H[+1], W[+1])$ and its reshaped version $B_F^c \in (nH[+1], W[+1], Cd[+1], d[+1])$ that satisfies that $B_F^c \delta W_F^T \in (nH[+1], W[+1], C[+1])$ is a reshaped version of $\text{Conv}_{\delta W}(B)$. ($B^c$ can be easily computed using `torch.nn.Unfold`.)

Hence Equation (39) becomes:

$$ \arg\min_{\delta W_F} \left\| V_{\text{goal}} - B_F^c \delta W_F^T \right\|_F \qquad (40) $$

Using the same reasoning that for fully connected layers, we get an optimal solution:

$$ (\delta W_F^*)^T = ((B_F^c)^T B_F^c)^+ (B_F^c)^T V_{\text{goal}} \qquad (41) $$

<figure><img src="image_13.png" /></figure>

## C.2 Proposition 3.2

We define the matrices $N := \frac{1}{n}B_{l-2}(V_{\text{goal}}^l)^T$ and $S := \frac{1}{n}B_{l-2}B_{l-2}^T$. Let us denote its SVD by $S = O\Sigma O^T$, and note $S^{-\frac{1}{2}} := O\sqrt{\Sigma^{-1}}O^T$ and consider the SVD of the matrix $S^{-\frac{1}{2}}N = \sum_{k=1}^R \lambda_k u_k v_k^T$ with $\lambda_1 \ge \dots \ge \lambda_R \ge 0$, where $R$ is the rank of the matrix $N$. Then:

**Proposition C.1 (3.2).** The solution of equation 8 can be written as:

* optimal number of neurons: $K^* = R$

* their optimal weights: $(\alpha_k^*, \omega_k^*) = (\sqrt{\lambda_k}S^{-\frac{1}{2}}u_k, \sqrt{\lambda_k}v_k)$ for $k = 1, \dots, R$.

Moreover for any number of neurons $K \le R$, and associated scaled weights $\theta_{\leftrightarrow}^{K,*}$, the expressivity gain and the first order in $\eta$ of the loss improvement due to the addition of these $K$ neurons are equal and can be quantified very simply as a function of the eigenvalues $\lambda_k$:

$$ \Psi_{\theta \oplus \theta_{\leftrightarrow}^{K,*}}^l = \Psi_{\theta}^l - \sum_{k=1}^{K} \lambda_k^2 $$

for fully-connected layers, with an inequality instead ($\le$) for convolutional layers.

*Proof.*

To facilitate reading we remove the layer index of each quantity, ie $B := B_{l-2}$, $V^l(A, \Omega) := V(A, \Omega)$ and $V_{\text{goal}}^l := V_{\text{goal}}$.

To solve this problem, we consider the input of the incoming connections $B$ and the desired change in the output of the outgoing connections $V_{\text{goal}}$. Hence if we note $L(A)$ and $L(\Omega)$ the additional connections of the expanded representation and $\sigma$ the non linearity, we optimize the following proxy problem:

$$ \arg\min_{A, \Omega} \frac{1}{n} \left\| (L(\Omega) \circ \sigma \circ L(A))(B) - V_{\text{goal}} \right\|_{\text{Tr}} \qquad (42) $$

We solve this problem at first order by linearizing the non-linearity $\sigma$. We denote $\text{Lin}_{(a,b)}(W)$ the fully connected layer with input size $a$, output size $b$ and weight matrix $W$. We also note $C[+1]$ and $C[-1]$ the
Considering the SVD of $S^{-\frac{1}{2}}N = \sum_{r=1}^{R} \lambda_r e_r f_r^T$, then $S^{-\frac{1}{2}}NN^T S^{-\frac{1}{2}} = \sum_{r=1}^{R} \lambda_r^2 f_r f_r^T$, because $j \neq i \Rightarrow e_i^T e_j = 0$ and $f_i^T f_j = 0$. Hence maximizing the first quantity is equivalent to $p_k^* = f_k$, then $\alpha_k = S^{-\frac{1}{2}}e_k$. The same reasoning is used to find $\omega_k$.

We prove second corollary 3.2 by induction. For $m = m' = 1$:

$$ \begin{aligned} a_l(x)^{t+1} &= a_l(x)^t + V(\theta_{\leftarrow\leftrightarrow}^{1,*}, x)\gamma + o(\gamma) \\ v_{\text{goal}}^{l,t+1}(x) &= v_{\text{goal}}^{l,t}(x) + \nabla_{a_l(x)} \mathcal{L}(f_\theta(x), y)^T v(\theta_{\leftarrow\leftrightarrow}^{1,*}, x)\gamma + o(\gamma) \end{aligned} $$

Adding the second neuron we obtain the minimization problem:

$$ \arg\min_{\alpha_2, \omega_2} \|V_{\text{goal}}^{l,t} - V^l(\alpha_2, \omega_2)\|_{\text{Tr}} + o(1) $$

□

## C.4 ABOUT EQUIVALENCE OF QUADRATIC PROBLEMS

Problems 6 and 5 are generally not equivalent, but might be very close, depending on layer sizes and number of samples. The difference between the two problems is that in one case one minimizes the quadratic quantity:

$$ \| V^l(\theta_{\leftarrow\leftrightarrow}^K) + V^l(\delta W_l) - V_{\text{goal}}^l \|_{\text{Tr}}^2 $$

w.r.t. $\delta W_l$ and $\theta_{\leftarrow\leftrightarrow}^K$ jointly, while in the other case the problem is first minimized w.r.t. $\delta W_l$ and then w.r.t. $\theta_{\leftarrow\leftrightarrow}^K$. The latter process, being greedy, might thus provide a solution that is not as optimal as the joint optimization.

We chose this two-step process as it intuitively relates to the spirit of improving upon a standard gradient descent: we aim at adding neurons that complement what the other ones have already done. This choice is debatable and one could solve the joint problem instead, with the same techniques.

The topic of this section is to check how close the two problems are. To study this further, note that $V^l(\delta W_l) = \delta W_l B_{l-1}$ while $V^l(\theta_{\leftarrow\leftrightarrow}^K) = \sum_{k=1}^K \omega_k B_{l-2}^T \alpha_k$. The rank of $B_{l-1}$ is $\min(n_S, n_{l-1})$ where $n_S$ is the number of samples and $n_{l-1}$ the number of neurons (post-activities) in layer $l-1$, while the rank of $B_{l-2}$ is $\min(n_S, n_{l-2})$ where $n_{l-2}$ is the number of neurons (post-activities) in layer $l-2$. Note also that the number of degrees of freedom in the optimization variables $\delta W_l$ and $\theta_{\leftarrow\leftrightarrow}^K = (\omega_k, \alpha_k)$ is much larger than these ranks.

**Small sample case.** If the number $n_S$ of samples is lower than the number of neurons $n_{l-1}$ and $n_{l-2}$ (which is potentially problematic, see Section D.1), then it is possible to find suitable variables $\delta W_l$ and $\theta_{\leftarrow\leftrightarrow}^K$ to form any desired $V^l(\delta W_l)$ and $V^l(\theta_{\leftarrow\leftrightarrow}^K)$. In particular, if $n_S \le n_{l-1} \le n_{l-2}$, one can choose $V^l(\theta_{\leftarrow\leftrightarrow}^K)$ to be $V_{\text{goal}}^l - V^l(\delta W_l)$ and thus cancel any effect due to the greedy process in two steps. The two problems are then equivalent.

**Large sample case.** On the opposite, if the number of samples is very large (compared to the number of neurons $n_{l-1}$ and $n_{l-2}$), then the lines of matrices $B_{l-1}$ and $B_{l-2}$ become asymptotically uncorrelated, under the assumption of their independence (which is debatable, depending on the type of layers and activation functions). Thus the optimization directions available to $V^l(\delta W_l)$ and $V^l(\theta_{\leftarrow\leftrightarrow}^K)$ become orthogonal, and proceeding greedily does not affect the result, the two problems are asymptotically equivalent.

In the general case, matrices $B_{l-1}$ and $B_{l-2}$ are not independent, though not fully correlated, and the number of samples (in the minibatch) is typically larger than the number of neurons; the problems are then different.

Note that technically the ranks could be lower, in the improbable case where some neurons are perfectly redundant, or, e.g., if some samples yield exactly the same activities.

## C.5 SECTION *Theory behind Greedy Growth* WITH PROOFS

One might wonder whether a greedy approach on layer growth might get stuck in a non-optimal state. We derive the following series of propositions in this regard. Since in this work we add
layer width at layer $l+1$ and $l-1$ with the convention that $C[0]$ is the dimension of the input $\boldsymbol{x}$. With those notations, for fully connected layers, we have for the additions of $K$ neurons:

$$ \arg\min_{\mathbf{A},\Omega} \frac{1}{n} \left\| \mathbf{Lin}_{(C[+1],K)}(\Omega)(\mathbf{Lin}_{(K,C[-1])}(\mathbf{A})(\mathbf{B})) - \mathbf{V}_{\text{goal}_{proj}} \right\|_2 \quad (43) $$

With the same notations, for convolutional layers, we have for the additions of $K$ intermediate channels:

$$ \arg\min_{\mathbf{A},\Omega} \frac{1}{n} \left\| \mathbf{Conv}_{(C[+1],K)}(\Omega)(\mathbf{Conv}_{(K,C[-1])}(\mathbf{A})(\mathbf{B})) - \mathbf{V}_{\text{goal}_{proj}} \right\|_2 \quad (44) $$

If we note $\mathbf{V}(\mathbf{A}, \Omega)$ the result of $\mathbf{B}$ after applying the layers parametrized by $\mathbf{A}$ and $\Omega$, in both cases we aim to optimize:

$$ \arg\min_{\mathbf{A},\Omega} \frac{1}{n} \left\| \mathbf{V}(\mathbf{A}, \Omega) - \mathbf{V}_{\text{goal}_{proj}} \right\|_{\text{Tr}} \quad (45) $$

First we will transform the resolution of the problem in solving the following optimization problem:

$$ \arg\min_{\mathbf{A},\Omega} \left\| \mathbf{S}^{\frac{1}{2}} \mathbf{A} \Omega^T - \mathbf{S}^{-\frac{1}{2}} \mathbf{N} \right\|_2 \quad (46) $$

where $\mathbf{S}$ depends of $\mathbf{B}$ and $\mathbf{N}$ of $\mathbf{B}$ and $\mathbf{V}_{\text{goal}_{proj}}$.

If we note $\mathbf{S} = \mathbf{O}\mathbf{\Lambda}\mathbf{\Omega}^T$ the SVD of $\mathbf{S}$, we define the square root of $\mathbf{S}$ as $\mathbf{S}^{\frac{1}{2}} := \mathbf{O}\sqrt{\mathbf{\Lambda}}\mathbf{\Omega}^T$ and $\mathbf{S}^{-\frac{1}{2}} := \mathbf{O}\sqrt{\mathbf{\Lambda}^{-1}}\mathbf{\Omega}^T$ with the convention $0^{-1} = 0$.

### C.2.1 Fully connected layers

For a fully connected layer, we have

$$ \mathbf{V}(\mathbf{A}, \Omega) = \mathbf{Lin}_{(C[+1],K)}(\Omega)(\mathbf{Lin}_{(K,C[-1])}(\mathbf{A})(\mathbf{B})) = \Omega \mathbf{A}^T \mathbf{B} \quad (47) $$

**Lemma C.1.** Let $\mathbf{Y} \in \mathbb{R}(t, n)$, $\mathbf{X} \in \mathbb{R}(s, n)$, $\mathbf{C} \in \mathbb{R}(t, s)$

We define:

$$ \mathbf{S} := \frac{1}{n} \mathbf{X} \mathbf{X}^T \in \mathbb{R}(s, s) \quad (48) $$

$$ \mathbf{N} := \frac{1}{n} \mathbf{X} \mathbf{Y}^T \in \mathbb{R}(s, t) \quad (49) $$

$$ \frac{1}{n} \|\mathbf{C}\mathbf{X} - \mathbf{Y}\|^2 = \left\|\mathbf{C}\mathbf{S}^{\frac{1}{2}} - \mathbf{N}^T\mathbf{S}^{-\frac{1}{2}}\right\|^2 - \left\|\mathbf{S}^{-\frac{1}{2}}\mathbf{N}\right\|^2 + \frac{1}{n}\|\mathbf{Y}\|^2 \quad (50) $$

### Proof in C.2.2

Hence using Lemma C.5 with $\mathbf{C} \leftarrow \mathbf{\Lambda}\mathbf{A}^T$, $\mathbf{Y} \leftarrow \mathbf{V}_{\text{goal}_{proj}}$ and $\mathbf{B} \leftarrow \mathbf{X}$, we have:

$$ \begin{aligned} & \frac{1}{n} \left\| \mathbf{Lin}_{(C[+1],K)}(\Omega)(\mathbf{Lin}_{(K,C[-1])}(\mathbf{A})(\mathbf{B})) - \mathbf{V}_{\text{goal}_{proj}} \right\|^2 \\ & = \frac{1}{n} \left\| \mathbf{\Lambda}\mathbf{A}^T\mathbf{B} - \mathbf{V}_{\text{goal}_{proj}} \right\|^2 \quad (51) \\ & = \left\| \mathbf{\Lambda}\mathbf{A}^T\mathbf{S}^{\frac{1}{2}} - \mathbf{N}^T\mathbf{S}^{-\frac{1}{2}} \right\|^2 - \left\| \mathbf{S}^{-\frac{1}{2}}\mathbf{N} \right\|^2 + \frac{1}{n} \left\| \mathbf{V}_{\text{goal}_{proj}} \right\|^2 \end{aligned} $$
neurons layer per layer independently, we study here the case of a single hidden layer network, to spot potential layer growth issues. For the sake of simplicity, we consider the task of least square regression towards an explicit continuous target $f^*$, defined on a compact set. That is, we aim at minimizing the loss:

$$ \inf_{f} \sum_{x \in \mathcal{D}} \|f(x) - f^*(x)\|^2 $$

where $f(x)$ is the output of the neural network and $\mathcal{D}$ is the training set.

**Proposition C.2** (Greedy completion of an existing network). If $f$ is not $f^*$ yet, there exists a set of neurons to add to the hidden layer such that the new function $f'$ will have a lower loss than $f$.

One can even choose the added neurons such that the loss is arbitrarily well minimized.

*Proof.* The classic universal approximation theorem about neural networks with one hidden layer Pinkus (1999) states that for any continuous function $g$ defined on a compact set $\omega$, for any desired precision $\gamma$, and for any activation function $\sigma$ provided it is not a polynomial, then there exists a neural network $\hat{g}$ with one hidden layer (possibly quite large when $\gamma$ is small) and with this activation function $\sigma$, such that

$$ \forall x, \|g(x) - g^*(x)\| \le \gamma $$

We apply this theorem to the case where $g^* = f^* - f$, which is continuous as $f^*$ is continuous, and $f$ is a shallow neural network and as such is a composition of linear functions and of the function $\sigma$, that we will suppose to be continuous for the sake of simplicity. We will suppose that $f$ is real-valued for the sake of simplicity as well, but the result is trivially extendable to vector-valued functions (just concatenate the networks obtained for each output independently). We choose $\gamma = \frac{1}{10}\|f^* - f\|_{L2}$, where $\langle a | b \rangle_{L2} = \frac{1}{|\omega|} \int_{x \in \omega} a(x) b(x) dx$. This way we obtain a one-hidden-layer neural network $g$ with activation function $\sigma$ such that:

$$ \forall x \in \omega, \quad -\gamma \le g(x) - g^*(x) \le \gamma $$

$$ \forall x \in \omega, \quad g(x) = f^*(x) - f(x) + a(x) $$

with $\forall x \in \omega, |a(x)| \le \gamma$.

Then:

$$ \begin{aligned} \forall x \in \omega, \quad & f^*(x) - (f(x) + g(x)) = -a(x) \\ \forall x \in \omega, \quad & (f^*(x) - h(x))^2 = a^2(x) \end{aligned} \qquad (20) $$

with $h$ being the function corresponding to a neural network consisting in concatenating the hidden layer neurons of $f$ and $g$, and consequently summing their outputs.

$$ \|f^* - h\|_{L2}^2 = \|a\|_{L2}^2 $$

$$ \|f^* - h\|_{L2}^2 \le \gamma^2 = \frac{1}{100} \|f^* - f\|_{L2}^2 $$

and consequently the loss is reduced indeed (by a factor of 100 in this construction).

The same holds in expectation or sum over a training set, by choosing $\gamma = \frac{1}{10}\sqrt{\frac{1}{|\mathcal{D}|} \sum_{x \in \mathcal{D}} \|f(x) - f^*(x)\|^2}$, as Equation (20) then yields:

$$ \sum_{x \in \mathcal{D}} (f^*(x) - h(x))^2 = \sum_{x \in \mathcal{D}} a^2(x) \le \frac{1}{100} \sum_{x \in \mathcal{D}} (f^*(x) - f(x))^2 $$

which proves the proposition as stated.

For more general losses, one can consider order-1 (linear) development of the loss and ask for a network $g$ that is close to (the opposite of) the gradient of the loss.

□

*Proof of the additional remark.* The proof in Pinkus (1999) relies on the existence of real values $c_n$ such that the $n$-th order derivatives $\sigma^{(n)}(c_n)$ are not 0. Then, by considering appropriate values
With:

$$ S := \frac{1}{n} BB^T \in \mathbb{R}(C[-1], C[-1]) \qquad (52) $$

$$ N := \frac{1}{n} B V_{\text{goal}_{\text{proj}}}^T \in \mathbb{R}(C[-1], C[+1]) \qquad (53) $$

### C.2.2 Convolutional connected layers

We have $A \in \mathbb{R}(K, C[-1], d, d)$ and $\Omega \in \mathbb{R}(C[+1], K, d[+1], d[+1])$ where $d, d[+1]$ is the kernel size at $l$ and $l+1$. We note $A_F$ the flatten and transposed version of $A$ of shape $(C[-1]dd, K)$ and $\alpha_k := A_F[:,k] \in (C[-1]dd, 1)$. We will now consider $\Omega$ with the last order flatten i.e. $\Omega \in \mathbb{R}(C[+1], K, d[+1]d[+1])$. We also

note $\omega_{k,m} := \Omega[m, k] \in (d[+1]d[+1], 1)$. Using this we define $\Omega[m]_F := \begin{pmatrix} \omega_{1,m}^T \\ \vdots \\ \omega_{K,m}^T \end{pmatrix} \in (K, d[+1]d[+1])$ and $\Omega_F := (\Omega[1]_F \quad \dots \quad \Omega[m]_F) \in (K, C[+1]d[+1]d[+1])$.

We define the tensor $T$ such that for a pixel $j$ of the output of the convolutional layer, $T_j$ is a linear application that select the pixels of the input of the convolutional layer that are used to compute the pixel $j$ of the output in a flatten version image (flatten only on the space not on the channels). $T \in \mathbb{R}(H[+1]W[+1], d[+1]d[+1], HW)$ where $H$ and $W$ are the height and width of the intermediate image and $H[+1]$ and $W[+1]$ are the height and width of the output image.

As previously, we have $B^c$ the unfolded version of $B$ such that $B^c \in \mathbb{R}(n, C[-1]dd, HW)$ satisfying $\text{Conv}(B_i)$ is equal with the correct reshape to $AB_i^c$.

In addition, we use $j$ as an index on the space of pixels instead of having a couple $h, w$ for height and width. With those notations we have:

$$ V(\mathbf{A}, \mathbf{\Omega})[i, m, j] = \text{Conv}_{(C[+1], K)}(\mathbf{\Omega})(\text{Conv}_{(K, C[-1])}(\mathbf{A})(\mathbf{B}_i))[m, j] \qquad (54) $$

$$ = \sum_{k}^{K} \omega_{m,k}^{T} T_{j}(B_{i}^{c})^{T} \alpha_{k} \qquad (55) $$

In the following for simplicity, we note $B_{i,j}^t := T_j(B_i^c)^T$. To find the best neurons to add we solve the expressivity bottleneck as :

$$ \arg\min_{\mathbf{A}, \mathbf{\Omega}} \frac{1}{n} \sum_{i} \sum_{j} \sum_{m} \left\| V_{\text{goal}_{\text{proj}_i}}^{(j,m)} - \sum_{k=1}^{K} \omega_{m,k}^{T} B_{i,j}^{t} \alpha_{k} \right\|^{2} \qquad (56) $$