arbitrarily close to $c_n$, one can approximate the n-th derivative of $\sigma$ at $c_n$ and consequently the polynomial $c^n$ of order $n$. This standard proof then concludes by density of polynomials in continuous functions.

Provided the activation function $\sigma$ is not a polynomial, these values $c_n$ can actually be chosen arbitrarily, in particular arbitrarily close to 0. This corresponds to choosing neuron input weights arbitrarily close to 0. $\square$

**Proposition C.3 (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$.

*Proof.* From the previous proposition, there exists a finite set of neurons to add such that the loss will be decreased. In this particular setting of L2 regression, or for more general losses if considering small function moves, this means that the function represented by this set of neurons has a strictly negative component over the gradient $g$ of the loss ($g = 2(f^* - f)$ in the case of the L2 regression). That is, denoting by $a_i\sigma(W_i \cdot x)$ these $N$ neurons:

$$ \langle \sum_{i=1}^{N} a_i \sigma(w_i \cdot x) | g \rangle_{L2} = K < 0 $$

i.e.

$$ \sum_{i=1}^{N} \langle a_i \sigma(w_i \cdot x) | g \rangle_{L2} = K < 0 $$

Now, by contradiction, if there existed no neuron $i$ among these ones such that

$$ \langle a_i \sigma(w_i \cdot x) | g \rangle_{L2} \le \frac{1}{N} K $$

then we would have:

$$ \forall i \in [1, N], \quad \langle a_i \sigma(w_i \cdot x) | g \rangle_{L2} > \frac{1}{N} K $$

$$ \sum_{i=1}^{N} \langle a_i \sigma(w_i \cdot x) | g \rangle_{L2} > K $$

hence a contradiction. Then necessarily at least one of the $N$ neurons satisfies

$$ \langle a_i \sigma(w_i \cdot x) | g \rangle_{L2} \le \frac{1}{N} K < 0 $$

and thus decreases the loss when added to the hidden layer of the neural network representing $f$. Moreover this decrease is at least $\frac{1}{N}$ of the loss decrease resulting from the addition of all neurons. $\square$

As a consequence, our greedy approach will not get stuck in a situation where one would need to add many neurons simultaneously to decrease the loss: it is always feasible by a single neuron. On can express a lower bound on how much the loss has improved (for the best such neuron), but it not a very good one without further assumptions on $f$.

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

*Proof.* This is straightforward, as, following a previous remark, the neurons found to collectively decrease the loss can be supposed to all have arbitrarily small input weights. $\square$

This detail is important in that our approach is based on the tangent space of the function $f$ and consequently manipulates infinitesimal quantities. Though we perform line search in a second step and consequently add non-infinitesimal neurons, our first optimization problem relies on the linearization of the activation function by requiring the added neuron to have infinitely small input weights, without which it would be much harder to solve. This proposition confirms that such neuron does exist indeed.
Using the properties of the trace, it follows that:

$$ \sum_{i,j,m} \left\| V_{\text{goalproj}_i}^{(j,m)} - \sum_{k=1}^{K} \omega_{m,k}^T B_{i,j}^t \alpha_k \right\|^2 = \sum_{i,j,m} \left\| V_{\text{goalproj}_i}^{(j,m)} - \sum_k \text{Tr}(B_{i,j}^t \alpha_k \omega_{m,k}^T) \right\|^2 \quad (58) $$

$$ = \sum_{i,j,m} \left\| V_{\text{goalproj}_i}^{(j,m)} - \text{Tr} \left( B_{i,j}^t \underbrace{\sum_k \alpha_k \omega_{m,k}^T}_{F_m} \right) \right\|^2 \quad (59) $$

$$ = \sum_{i,j,m} \left\| V_{\text{goalproj}_i}^{(j,m)} - \text{flat}(B_{i,j}^t)^T \text{flat}(F_m) \right\|^2 \quad (60) $$

$$ = \sum_{i,j} \left\| V_{\text{goalproj}_i}^{(j)} - \text{flat}(B_{i,j}^t)^T F \right\|^2 \quad (61) $$

$$ \text{With } F := (\text{flat}(F_1) \dots \text{flat}(F_{C[+1]})). \quad (62) $$

We remark that $V(A, \Omega)$ is a linear function of the matrix $F$ which implies that the solution of 56 is the same as the one for linear layer. Replacing $\Omega A$ by $F$ in 47 and following the same reasoning as for linear layer, it follows that 56 is equivalent to:

$$ \arg\min_{F} \left\| \mathbf{S}^{\frac{1}{2}} F - \mathbf{S}^{-\frac{1}{2}} N \right\|_2 \quad (63) $$

$$ \text{with } S := \sum_{i,j} \text{flat}(B_{i,j}^t) \text{flat}(B_{i,j}^t)^T \text{ and } N := \sum_{i,j} V_{\text{goalproj}_i}^{(j)} \text{flat}(B_{i,j}^t)^T. $$

However, we remark that the dimension of $S \in \mathbb{R}(C[-1]d[+1]^2d^2, C[-1]d[+1]^2d^2)$ is quite large and that computing the SVD of such matrix is costly. To avoid expensive computation, we approximate 56 by defining the matrix $S$ and $N$ as 98 and 100. We now prove that 3.2, 3.4 and Equation (10) still hold with such new definitions of $S$ and $N$.

**Lemma C.2.** Let $r := \min(B_{1,1}^t, \text{shape})$, we define:

$$ S := \frac{r}{n} \sum_{i=1}^{n} \sum_{j=1}^{H[+1]W[+1]} (B_{i,j}^t)^T (B_{i,j}^t) \in (C[-1]dd, C[-1]dd) \quad (64) $$

$$ N_m := \frac{1}{n} \sum_{i,j}^{n, H[+1]W[+1]} V_{\text{goalproj}_{i,j,m}} (B_{i,j}^t)^T \in (C[-1]dd, d[+1]d[+1]) \quad (65) $$

$$ N := (N_1 \cdots N_{C[+1]}) \in (C[-1]dd, C[+1]d[+1]d[+1]) \quad (66) $$

We have:

$$ \frac{1}{n} \left\| V(\mathbf{A}, \mathbf{\Omega}) - V_{\text{goalproj}} \right\|^2 \le \left\| \mathbf{S}^{\frac{1}{2}} \mathbf{A}_F \mathbf{\Omega}_F - \mathbf{S}^{-\frac{1}{2}} \mathbf{N} \right\|^2 - \left\| \mathbf{S}^{-\frac{1}{2}} \mathbf{N} \right\|^2 + \frac{1}{n} \left\| V_{\text{goalproj}} \right\|^2 \quad (67) $$

Proof in C.2.2

**Lemma C.3.** For $S \in \mathbb{R}(s, s)$, $N \in \mathbb{R}(s, t)$, $A \in \mathbb{R}(s, K)$, $\Omega \in \mathbb{R}(K, t)$.

We note $U\Lambda V$ the singular value decomposition of $S^{-\frac{1}{2}}N$ and $U_K$ the first $K$ columns of $U$, $V_K$ the first $K$ lines of $V$, $\Lambda_K$ the first $K$ singular values of $\Lambda$ and $\Lambda_{K+1}$, the other singular values of $\Lambda$.

We define:

$$ A^* := S^{-\frac{1}{2}} U_K \sqrt{\Lambda_K} \quad (68) $$

$$ \Omega^* := \sqrt{\Lambda_K} V_K \quad (69) $$
# D TECHNICAL DETAILS

## D.1 BATCH SIZE TO ESTIMATE THE NEW NEURON AND THE BEST UPDATE

In this section we study the variance of the matrices $\delta W_l^*$ and $S^{-1/2}N$ computed using a minibatch of $n$ samples, seeing the samples as random variables, and the matrices computed as estimators of the true matrices one would obtain by considering the full distribution of samples. Those two matrices are the solutions of the multiple linear regression problems defined in (11) and in (14), as we are trying to regress the desired update noted $Y$ onto the span of the activities noted $X$. We suppose we have the following setting:

$$Y \sim AX + \varepsilon, \quad \varepsilon \sim \mathcal{N}(0, \sigma^2), \quad \mathbb{E}[\varepsilon|X] = 0$$

where the $(X_i, Y_i)$ are i.i.d. and $A$ is the oracle for $\delta W_l^*$ or matrix $S^{-1/2}N$. If $Y$ is multidimensional, the total variance of our estimator can be seen as the sum of the variances of the estimator on each dimension of $Y$.

We now suppose that $Y \in \mathbb{R}$. The estimator $\hat{A} := (XX^T)^{-1}XY^T$ has variance $\text{var}(\hat{A}) = \sigma^2(XX^T)^{-1}$. If $n$ is large, and if matrix $\frac{1}{n}XX^T \to Q$, with $Q$ non singular, then, asymptotically, we have $\hat{A} \sim \mathcal{N}(A, \sigma^2 \frac{Q^{-1}}{n})$, which is equivalent to $(\hat{A} - A)\sqrt{\frac{\pi}{\sigma}}Q^{1/2} \sim \mathcal{N}(0, I)$. Then $\| (\hat{A} - A)\sqrt{\frac{\pi}{\sigma}}Q^{1/2}\|^2 \sim \chi^2(k)$ where $k$ is the dimension of $X$. It follows that $\mathbb{E}[\| (\hat{A} - A)Q^{1/2}\|^2] = \frac{k\sigma}{n}$ and as $Q^{1/2}Q^{1/2}^T$ is positive definite, we conclude that $\text{var}(\hat{A}) \le \frac{k\sigma}{n\lambda_{\min}(Q)}$.

In practice and to keep the variance of our estimators stable during architecture growth, for the estimation of the best neuron to add we use batch size

$$n \propto \frac{(SW)^2}{P},$$

with the notations defined in Figure 12, since the matrices we estimate have side size $SW$ and that each input sample contains $P$ values, i.e. $P$ quantities that each play the role of $X$ here.

## D.2 BATCH SIZE FOR LEARNING

We adjust the batch size for gradient descent as follows: the batch size is set to $b_{t=0} = 32$ at the beginning of each experiment, and it is scheduled to increase as the square root of the complexity of the model (ie number of parameters). If at time $t$ the network has complexity $C_t$ parameters, then at time $t+1$ the training batch size is equal to $b_{t+1} = b_t \times \sqrt{\frac{C_{t+1}}{C_t}}$.

## D.3 NORMALIZATION

### D.3.1 FIGURES 5 AND 16: USUAL NORMALIZATION

For the GradMax method of figure 5 and 16, before adding the new neurons to the architecture, we normalize the out-going weight of the new neurons according to Evci et al. (2022), ie:

$$\alpha_k^* \leftarrow 0 \qquad (21)$$

$$\text{for } 5 \quad \omega_k^* \leftarrow \omega_k^* \times \frac{1e-3}{\sqrt{\|\{\omega_j^*\}_{j=1}^{n_d}\|^2/n_d}} \qquad (22)$$

$$\text{for } 16 \quad \omega_k^* \leftarrow \omega_k^* \times \sqrt{\frac{1e-3}{\|\{\omega_j^*\}_{j=1}^{n_d}\|^2/n_d}} \qquad (23)$$

For TINY method of both figures, the previous normalization process is mimicked by normalizing the in and out going weights by theirs norms and multiplying them by $\sqrt{1e-3}$, ie:

$$\alpha_k \leftarrow \alpha_k^* \times \sqrt{\frac{1e-3}{\|\{\alpha_j^*\}_{j=1}^{n_d}\|^2/n_d}} \qquad (24)$$

$$\omega_k \leftarrow \omega_k^* \times \sqrt{\frac{1e-3}{\|\omega_j^*\}_{j=1}^{n_d}\|_2^2/n_d} \qquad (25)$$
Then:

$$ \min_{A, \Omega} \frac{1}{n} \left\| V(A, \Omega) - V_{\text{goalproj}} \right\|^2 \le \frac{1}{n} \left\| V(A^*, \Omega^*) - V_{\text{goalproj}} \right\|^2 = -\|\Lambda_K\|^2 + \frac{1}{n} \left\| V_{\text{goalproj}} \right\|^2 \quad (70) $$

with equality in the linear case. Using expressivity bottlenecks notations, this rewrites:

$$ \Psi_{\theta \oplus \theta_K^*}^l \le \Psi_{\theta}^l - \sum_{k=1}^{K} \lambda_k^2. \quad (71) $$

Proof. Using Lemma C.5 and Lemma C.7:

$$ \frac{1}{n} \left\| V(A, \Omega) - V_{\text{goalproj}} \right\|^2 \le \left\| S^{\frac{1}{2}} A \Omega - S^{-\frac{1}{2}} N \right\|^2 - \left\| S^{-\frac{1}{2}} N \right\|^2 + \frac{1}{n} \left\| \underbrace{V_{\text{goalproj}}}_{\Psi_{\theta}^l} \right\|^2 \quad (72) $$

Hence we minimize the second term of the right term, that is:

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

As we suppose that $S$ is invertible, we can use the change of variable $\tilde{A} = S^{\frac{1}{2}}A$ thus we have:

$$ \min_{A, \Omega} \left\| S^{\frac{1}{2}} A \Omega - S^{-\frac{1}{2}} N \right\| = \min_{\tilde{A}, \Omega} \left\| \tilde{A} \Omega - S^{-\frac{1}{2}} N \right\| \quad (74) $$

The solution of such problems is given by the paper Eckart & Young (1936) and is:

$$ \tilde{A}^* = U_K \sqrt{\Lambda_K} \quad (75) $$

$$ \Omega^* = \sqrt{\Lambda_K} V_K \quad (76) $$

To recover $A^*$ we simply have to multiply by $S^{-\frac{1}{2}}$ on the left side of $\tilde{A}^*$. By definition of the SVD and the construction of $(A^*, \Omega^*)$ we have:

$$ \left\| S^{\frac{1}{2}} A^* \Omega^* - S^{-\frac{1}{2}} N \right\|^2 - \left\| S^{-\frac{1}{2}} N \right\|^2 = \| \Lambda_{K+1} \|^2 - \| \Lambda \|^2 = - \| \Lambda_K \|^2 \quad (77) $$

Using this and Equation (72) we immediately get the desired Equation (70). To conclude, we can also rewrite this with the bottleneck expression:

$$ \Psi_{\theta \oplus \theta_K^*} := \min_{A, \Omega} \frac{1}{n} \left\| V(A, \Omega) - V_{\text{goalproj}} \right\|^2 \le \Psi_{\theta}^l - \sum_{k=1}^{K} \lambda_k^2 \quad (78) $$

□

We now prove all the lemmas.

**Lemma C.4.** For $S \in \mathbb{R}(s, s)$, $N \in \mathbb{R}(s, t)$, $C \in \mathbb{R}(t, s)$.

If $N = S^{\frac{1}{2}}S^{-\frac{1}{2}}N$, we have:

$$ \langle C^T, SC^T \rangle - 2 \langle N, C^T \rangle = \left\| S^{\frac{1}{2}} C^T - S^{-\frac{1}{2}} N \right\|^2 - \left\| S^{-\frac{1}{2}} N \right\|^2 \quad (79) $$
### D.3.2 FIGURE 8: AMPLITUDE FACTOR

For the Random and the TINY methods of figure 8, we first normalize the parameters as:

For the new neurons:

$$ \alpha_k^* \leftarrow \alpha_k^* \times \frac{1}{\sqrt{\|\{\alpha_j^*\}_{j=1}^{n_d}\|_2^2/n_d}} $$

$$ \omega_k^* \leftarrow \alpha_k^* \times \frac{1}{\sqrt{\|\{\omega_j^*\}_{j=1}^{n_d}\|_2^2/n_d}} $$

For the best update:

$$ W^* \leftarrow W^* \times \frac{1}{\sqrt{\|W^*\|_2^2/n_d}} $$

Then, we multiply them by the amplitude factor $\gamma^*$:

For the new neurons:

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

For the best update:

$$ W_l^* \leftarrow \gamma^* W_l \\ \gamma^* := \arg \min_{\gamma \in [-L, L]} \sum_i \mathcal{L}(f_{\theta + \gamma W^*(\mathbf{x}_i)}, \mathbf{y}_i) $$

Where the operation $\gamma \theta_{\leftarrow K}^* = (\gamma \alpha_k^*, \gamma \omega_k^*)^K$ is the concatenation of the neural network with the new neurons and $\theta + \gamma W^*$ is the update of one layer with its best update. The batch on which $\gamma^*$ is computed is different from the one used to estimate the new parameters and its size is fixed to 1000 for all experiments.

## D.4 FULL ALGORITHM

In this section we describe in detail the pseudo code to plot 5 and 8. The function NewNeurons($l$), in Algorithm 2, computes the new neurons defined at Proposition 3.2 for layer $l$ sorted by decreasing eigenvalues. The function BestUpdate($l$), in Algorithm 4 computes the best update at Proposition 3.1 for layer $l$.

**Algorithm 1:** Algorithm to plot Figure 5 and 8.

**for** each method [TINY, MethodToCompareWith] **do**

Start from neural network $N$ with initial structure $\iota \in \{1/4, 1/64\}$;

**while** $N$ architecture doesn't match ResNet18f **do**

**for** $d$ in $\{\text{depths to growth}\}$ **do**

$\theta_{\leftarrow K}^* = \text{NewNeurons}(d, \text{method} = \text{method});$

Normalize $\theta_{\leftarrow K}^*$ according to D.3;

Add the neurons at $d$;

Train $N$ for $\Delta t$ epochs;

Save model $N$ and its performance;

end

end

end
Proof. • For the first term we have:

$$ \langle C^T, SC^T \rangle = \langle C^T, S^{\frac{1}{2}}S^{\frac{1}{2}}C^T \rangle \quad (80) $$

$$ = \langle S^{\frac{1}{2}}C^T, S^{\frac{1}{2}}C^T \rangle \quad (81) $$

$$ = \|S^{\frac{1}{2}}C^T\|^2 \quad (82) $$

• For the second term we have:

$$ \langle N, C^T \rangle = \langle S^{\frac{1}{2}}S^{-\frac{1}{2}}N, C^T \rangle \quad (83) $$

$$ = \langle S^{-\frac{1}{2}}N, S^{\frac{1}{2}}C^T \rangle \quad (84) $$

Hence we have that:

$$ \langle C^T, SC^T \rangle - 2 \langle N, C^T \rangle = \|S^{\frac{1}{2}}C^T\|^2 - 2 \langle S^{-\frac{1}{2}}N, S^{\frac{1}{2}}C^T \rangle + \|S^{-\frac{1}{2}}N\|^2 - \|S^{-\frac{1}{2}}N\|^2 \quad (85) $$

$$ = \|S^{\frac{1}{2}}C^T - S^{-\frac{1}{2}}N\|^2 - \|S^{-\frac{1}{2}}N\|^2 \quad (86) $$

□

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

We define:

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

$$ N := \frac{1}{n}XY^T \in \mathbb{R}(s, t) \quad (88) $$

$$ \frac{1}{n} \|CX - Y\|^2 = \|CS^{\frac{1}{2}} - N^T S^{-\frac{1}{2}}\|^2 - \|S^{-\frac{1}{2}}N\|^2 + \frac{1}{n} \|Y\|^2 \quad (89) $$

Proof. By developing the scalar product we get:

$$ \frac{1}{n} \|CX - Y\|^2 = \frac{1}{n} \|Y\|^2 - 2 \langle Y, \frac{1}{n}CX \rangle + \frac{1}{n} \|CX\|^2 \quad (90) $$

$$ = \frac{1}{n} \|Y\|^2 - 2 \langle Y, \frac{1}{n}CX \rangle + \frac{1}{n} \langle CX, CX \rangle \quad (91) $$

$$ = \frac{1}{n} \|Y\|^2 - 2 \langle Y^T, \frac{1}{n}(CX)^T \rangle + \frac{1}{n} \langle (CX)^T, (CX)^T \rangle \quad (92) $$

$$ = \frac{1}{n} \|Y\|^2 - 2 \langle \frac{1}{n}XY^T, C^T \rangle + \langle C^T, \frac{1}{n}XX^T C^T \rangle \quad (93) $$

We now use the two following lemma:

**Lemma C.6.** Let $Y \in \mathbb{R}(t, n)$, $X \in \mathbb{R}(s, n)$ and $S := XX^T \in \mathbb{R}(s, s)$.

$$ S^{\frac{1}{2}}S^{-\frac{1}{2}}XY^T = XY^T \quad (94) $$

Proof. Let decompose $Y$ on $\mathrm{Im}(X^T) \oplus \ker(X)$: $Y = X^T I + K$.

$$ XY^T = XX^T I + XK = XX^T I = SI $$

Hence $XY^T \in \mathrm{Im}(S)$, hence as $S|_{\mathrm{Im}(S)}$ is invertible, we have: $S^{-\frac{1}{2}}S^{\frac{1}{2}}XY^T = XY^T$. □
<table><thead><tr><th>Algorithm 2: NewNeurons</th><th>Algorithm 3: MatrixSN</th></tr></thead><tbody><tr><td><b>Data:</b> l, method = TINY<br><b>Result:</b> Best neurons at l<br><b>if method = TINY then</b><br> &nbsp;&nbsp;&nbsp;&nbsp; δW<sub>l</sub> = BestUpdate(l + 1);<br> &nbsp;&nbsp;&nbsp;&nbsp; S, N =<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; MatrixSN(l − 1, l + 1, δW<sub>l</sub> = δW<sub>l</sub>);<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Compute the SVD of S := UΣU<sup>T</sup>;<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Compute the SVD of<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; U√Σ<sup>−1</sup>U N := AΛΩ;<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Use the columns of A, the ligns of Ω<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; and the diagonal of Λ to construct<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; the new neurons of Prop. 3.2;<br><b>else if method = GradMax then</b><br> &nbsp;&nbsp;&nbsp;&nbsp; δW<sub>l</sub> = None;<br> &nbsp;&nbsp;&nbsp;&nbsp; -, N = MatrixSN(l − 1, l + 1, δW<sub>l</sub> =<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; δW<sub>l</sub>);<br> &nbsp;&nbsp;&nbsp;&nbsp; Compute the SVD of N<sup>T</sup>N;<br> &nbsp;&nbsp;&nbsp;&nbsp; Use the eigenvectors to define the<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; new out-going weights;<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Set the new in-going weight to 0;<br><b>else if method = Random then</b><br> &nbsp;&nbsp;&nbsp;&nbsp; | (α<sub>k</sub>, ω<sub>k</sub>)<sup>n<sub>d</sub></sup><sub>k=1</sub> ∼ N(0, I<sub>d</sub>);<br><b>end</b></td><td><b>Data:</b> p<sub>1</sub>, p<sub>2</sub> (layer indexes), δW<sub>l</sub> =<br> &nbsp;&nbsp;&nbsp;&nbsp; None<br><b>Result:</b> Construct matrices S and N<br> &nbsp;&nbsp;&nbsp;&nbsp; Take a minibatch X of size ∝ (SW)<sup>2</sup>/P;<br> &nbsp;&nbsp;&nbsp;&nbsp; Propagate and backpropagate X;<br> &nbsp;&nbsp;&nbsp;&nbsp; Compute V<sub>goal</sub> at p<sub>2</sub>, ie −∂L<sup>tot</sup>/∂A<sup>T</sup><sub>P2</sub>;<br><b>if δW<sub>l</sub> ≠ None then</b><br> &nbsp;&nbsp;&nbsp;&nbsp; | V<sub>goal</sub> = δW<sub>l</sub>B<sub>p1</sub><br><b>end</b><br><b>S, N = B<sub>p1</sub>B<sub>p1</sub><sup>T</sup>, B<sub>p1</sub>V<sub>goal</sub><sup>T</sup>;</b></td></tr></tbody></table>

## D.5 COMPUTATIONAL COMPLEXITY

We estimate here the computational complexity of the above algorithm for architecture growth.

**Theoretical estimate.** We use the following notations:

* number of layers: *L*

* layer width, or number of kernels if convolutions: *W* (assuming for simplicity that all layers have same width or kernels)

* number of pixels in the image: *P* (*P* = 1 for fully-connected)

* kernel filter size: *S* (*S* = 1 if fully-connected)

* minibatch size used for standard gradient descent: *M*

* minibatch size used for new neuron estimation: *M'*

* minibatch size used in the line-search to estimate amplitude factor: *M''*

* number of classical gradients steps performed between 2 addition tentatives: *T*

<figure><img src="image_14.png" /><figcaption>Figure 12: Notation and size for convolutional and linear layers</figcaption></figure>

Complexity, estimated as the number of basic operations, cumulated over all calls of the functions:
Continuing the demonstration from Equation (93), by applying Lemma C.4, we have:

$$ \frac{1}{n} \|C\mathbf{X} - \mathbf{Y}\|^2 = \frac{1}{n} \|\mathbf{Y}\|^2 - 2 \langle \mathbf{N}, C^T \rangle + \langle C^T, SC^T \rangle \quad (95) $$

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

$$ = \frac{1}{n} \|\mathbf{Y}\|^2 + \left\| 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 \quad (97) $$

□

**Lemma C.7.** Let $r := \min(\mathbf{B}_{1,1}^t, \text{shape})$, we define:

$$ \mathbf{S} := \frac{r}{n} \sum_{i=1}^{n} \sum_{j=1}^{H[+1]W[+1]} (\mathbf{B}_{i,j}^t)^T (\mathbf{B}_{i,j}^t) \in (C[-1]dd, C[-1]dd) \quad (98) $$

$$ \mathbf{N}_m := \frac{1}{n} \sum_{i,j}^{n, H[+1]W[+1]} \mathbf{V}_{\text{goalproj}_{i,j,m}} (\mathbf{B}_{i,j}^t)^T \in (C[-1]dd, d[+1]d[+1]) \quad (99) $$

$$ \mathbf{N} := (\mathbf{N}_1 \cdots \mathbf{N}_{C[+1]}) \in (C[-1]dd, C[+1]d[+1]d[+1]) \quad (100) $$

We have:

$$ \frac{1}{n} \left\| \mathbf{V}(\mathbf{A}, \mathbf{\Omega}) - \mathbf{V}_{\text{goalproj}} \right\|^2 \le \left\| \mathbf{S}^{\frac{1}{2}} \mathbf{A}_F \mathbf{\Omega}_F - \mathbf{S}^{-\frac{1}{2}} \mathbf{N} \right\|^2 - \left\| \mathbf{S}^{-\frac{1}{2}} \mathbf{N} \right\|^2 + \frac{1}{n} \left\| \mathbf{V}_{\text{goalproj}} \right\|^2 \quad (101) $$

Proof. We have:

$$ \frac{1}{n} \left\| \mathbf{V}(\mathbf{A}, \mathbf{\Omega}) - \mathbf{V}_{\text{goalproj}} \right\|^2 = \frac{1}{n} \|\mathbf{V}(\mathbf{A}, \mathbf{\Omega})\|^2 - \frac{2}{n} \langle \mathbf{V}(\mathbf{A}, \mathbf{\Omega}), \mathbf{V}_{\text{goalproj}} \rangle^2 + \frac{1}{n} \left\| -\mathbf{V}_{\text{goalproj}} \right\|^2 \quad (102) $$

We will now simplify the first two terms separately.

## Norm simplification

**Lemma C.8.** For any square matrix $\mathbf{A} \in \mathbb{R}^{(n,n)}$, $\text{Tr}(\mathbf{A})^2 \le \text{rank}(\mathbf{A}) \|\mathbf{A}\|^2$.

*Proof.* Using the truncated SVD we have $\mathbf{A} = \mathbf{U}\mathbf{\Sigma}\mathbf{V}$ with $\mathbf{\Sigma}$ a diagonal and $\mathbf{U} \in \mathbb{R}^{(n,\text{rank}(\mathbf{A}))}$, $\mathbf{V} \in \mathbb{R}^{(\text{rank}(\mathbf{A}),n)}$ truncated orthonormal matrices.

We have:

$$ \text{Tr}(\mathbf{A})^2 = \text{Tr}(\mathbf{U}\mathbf{\Sigma}\mathbf{V})^2 \quad (103) $$

$$ = \text{Tr}(\mathbf{V}\mathbf{U}\mathbf{\Sigma})^2 \quad (104) $$

$$ = \langle \mathbf{V}\mathbf{U}, \mathbf{\Sigma} \rangle^2 \quad (105) $$

$$ (\text{Cauchy-Swarz}) \quad \le \|\mathbf{V}\mathbf{U}\|^2 \|\mathbf{\Sigma}\|^2 \quad (106) $$

As $\mathbf{U}, \mathbf{V}$ are truncated orthonormal matrices, we have:

$$ \|\mathbf{V}\mathbf{U}\|^2 = \text{Tr}(\mathbf{U}^T \mathbf{V}^T \mathbf{V}\mathbf{U}) = \text{Tr}(\mathbf{U}^T \mathbf{U}) = \text{Tr}(I_{\text{rank}(\mathbf{A})}) = \text{rank}(\mathbf{A}) $$

Hence:

$$ \text{Tr}(\mathbf{A})^2 \le \text{rank}(\mathbf{A}) \|\mathbf{\Sigma}\|^2 \quad (107) $$
* of the standard training part: $TMLW^2SP$

* of the computation of matrices of interest (function MatrixSN): $LM'(SW)^2P$

* of SVD computations (function NewNeurons): $L(SW)^3$

* of line-searches (function AmplitudeFactor): $L^2M''W^2SP$

* of weight updates (function BestUpdate): $LSW$

The relative added complexity w.r.t. the standard training part is thus:

$$M'S/TM + S^2W/TMP + M''L/TM + 1/WTMP.$$

**SVD cost is negligible.** The relative cost of the SVD w.r.t. the standard training part is $S^2W/TMP$. In the fully-connected network case, $S = 1$, $P = 1$, and the relative cost of the SVD is then $W/TM$. It is then negligible, as layer width $W$ is usually much smaller than $TM$, which is typically $10 \times 100$ for instance. In the convolutional case, $S = 9$ for $3 \times 3$ kernels, and $P \approx 1000$ for CIFAR, $P \approx 100000$ for ImageNet, so the SVD cost is negligible as long as layer width $W \ll 10000$ or $100000$ respectively. So one needs no worrying about SVD cost.

Likewise, the update of existing weights using the “optimal move” (already computed as a by-product) is computationally negligible, and the relative cost of the line searches is limited as long as the network is not extremely deep ($L < TM/M'$).

On the opposite, the estimation of the matrices (to which SVD is applied) can be more ressource demanding. The factor $M'S/TM$ can be large if the minibatch size $M'$ needs to be large for statistical significance reasons. One can show that an upper bound to the value required for $M'$ to ensure estimator precision (see Appendix D.1) is $(SW)^2/P$. In that case, if $W > \sqrt{TMP}/S^3$, these matrix estimations will get costly. In the fully-connected network case, this means $W > \sqrt{TM} \approx 30$ for $T = 10$ and $M = 100$. In the convolutional case, this means $W > \sqrt{TMP}/S^3 \approx 30$ for CIFAR and $\approx 300$ for ImageNet. We are working on finer variance estimation and on other types of estimators to decrease $M'$ and consequently this cost. Actually $(SW)^2/P$ is just an upper bound on the value required for $M'$, which might be much lower, depending on the rank of computed matrices.

**In practice.** In practice the cost of a full training with our architecture growth approach is similar (sometimes a bit faster, sometimes a bit slower) than a standard gradient descent training using the final architecture from scratch. This is great as the right comparison should take into account the number of different architectures to try in the classical neural architecture search approach. Therefore we get layer width hyper-optimization for free.

# E ADDITIONAL EXPERIMENTAL RESULTS AND REMARKS

## E.1 RESNET18 ON CIFAR-100

**Figures.** In all plots the black line represents the average performance over two independent runs, and the colored regions indicate the confidence interval.

**technical details of figure 5 and 8** The experiment were performed on 1 GPU. The optimizer is SGD(lr = 1e-2) with the starting batch size 32 D.2. At each depth $l$ we set the number $n_l$ of neurons to be added at this depth 2. These numbers do not depend on the starting architecture and have been chosen such that each depth will reach its final width with the same number of layer extensions. For the initial structure $s = 1/4$, resp. $1/64$, we set the number of layer extensions to 16, resp. 21, such that at depth 2 (named Conv2 in Table 3), $n_2 = (Size_2^{final} - Size_2^{start})/nb$ of layer extensions = $(64 - 16)/16 = (64 - 1)/21 = 3$. The initial architecture is described in Table 3.
As $U, V$ are truncated orthonormal matrices, we have:

$$ ||\Sigma||^2 = \mathrm{Tr}(\Sigma^T \Sigma) = \mathrm{Tr}((V \Sigma U)U \Sigma V) = \mathrm{Tr}(A^T A) = ||A||^2 $$

We conclude that:

$$ \mathrm{Tr}(A)^2 \le \mathrm{rank}(A) ||A||^2 \qquad (108) $$

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

**Lemma C.9.** For $M \in (m, n), (u_k)_{k \in [[K]]} \in (m)^K, (v_k)_{k \in [[K]]} \in (n)^K$ and with $W := \sum_{k \in [[K]]} v_k u_k^T \in (n, m)$ we have:

$$ \left\| \sum_{k \in [[K]]} u_k^T M v_k \right\|^2 = \mathrm{Tr} (M W)^2 \qquad (109) $$

*Proof.* Let $i \in I$:

$$ \left\| \sum_{k \in [[K]]} v u_k^T M v_k \right\|^2 = \left( \sum_{k \in [[K]]} u_k^T M v_k \right)^2 \qquad (110) $$

$$ = \mathrm{Tr} \left( \sum_{k \in [[K]]} u_k^T M v_k \right)^2 \qquad (111) $$

$$ = \mathrm{Tr} \left( M \sum_{k \in [[K]]} v_k u_k^T \right)^2 \qquad (112) $$

$$ = \mathrm{Tr} (M W)^2 \qquad (113) $$

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

**Lemma C.10.** For $(M_i)_{i \in I} \in (m, n)^I$ such that $\forall i \in I$, $\mathrm{rank}(M_i W) \le H$ and with $W \in (n, m)$ we have:

$$ \sum_{i \in I} \mathrm{Tr} (M_i W)^2 \le \left\langle W, H \sum_{i \in I} M_i^T M_i W \right\rangle \qquad (114) $$

*Proof.* Let $i \in I$:

Using Lemma C.8 with $A \leftarrow M_i W$

$$ \mathrm{Tr}(M_i W)^2 \le \mathrm{rank}(M_i W) ||M_i W||^2 \qquad (115) $$

$$ \le H ||M_i W||^2 \quad H := \min(M_i \cdot \mathrm{shape}) \qquad (116) $$

Hence we have:

$$ \sum_{i \in I} \left\| \sum_{k \in [[K]]} u_k^T M_i v_k \right\|^2 \le H \sum_{i \in I} ||M_i W||^2 \qquad (117) $$

$$ = H \sum_{i \in I} \langle M_i W, M_i W \rangle \qquad (118) $$

$$ = H \sum_{i \in I} \langle W, M_i^T M_i W \rangle \qquad (119) $$

$$ = H \left\langle W, \sum_{i \in I} M_i^T M_i W \right\rangle \qquad (120) $$
architecture growth TINY

<figure><img src="image_15.png" /><figcaption>Figure 13: Accuracy and number of parameters during architecture growth for methods TINY and GradMax as a function of gradient step.</figcaption></figure>
□

Using first Lemma C.9 with $u_k \leftarrow \omega_{k,m}$, $v_k \leftarrow \alpha_k$ and $M \leftarrow B_{i,j}^t$, we have:

$$ \frac{1}{n} \|V(\mathbf{A}, \mathbf{\Omega})\|^2 = \frac{1}{n} \sum_{m}^{C[+1]} \sum_{i,j}^{n, H[+1]W[+1]} \left\| \sum_{k}^{K} \omega_{k,m}^{T} (B_{i,j}^{t}) \alpha_{k} \right\|^2 \quad (121) $$

$$ = \frac{1}{n} \sum_{m}^{C[+1]} \sum_{i,j}^{n, H[+1]W[+1]} \mathrm{Tr} \left( B_{i,j}^{t} \sum_{k}^{K} \alpha_{k} \omega_{k,m}^{T} \right)^{2} \quad (122) $$

$$ = \frac{1}{n} \sum_{m}^{C[+1]} \sum_{i,j}^{n, H[+1]W[+1]} \mathrm{Tr} \left( B_{i,j}^{t} A_{F} \Omega [m]_{F} \right)^{2} \quad (123) $$

Using Lemma C.10 with $i \leftarrow (i, j)$, $M_i \leftarrow B_{i,j}^t$ and $W \leftarrow A_F \Omega [m]_F$:

$$ \le \sum_{m}^{C[+1]} \left\langle A_F \Omega [m]_F, \frac{r}{n} \sum_{i,j}^{n, H[+1]W[+1]} (B_{i,j}^t)^T (B_{i,j}^t) A_F \Omega [m]_F \right\rangle \quad (124) $$

$$ = \sum_{m}^{C[+1]} \langle A_F \Omega [m]_F, S A_F \Omega [m]_F \rangle \quad (125) $$

$$ = \langle A_F \Omega_F, S A_F \Omega_F \rangle \quad (126) $$

## Scalar product simplification

**Lemma C.11.** For $M \in (m, n)$, $u \in (m)$, $v \in (n)$ we have:

$$ u^T M v = \langle v u^T, M^T \rangle \quad (127) $$

*Proof.*

$$ u^T M v = (u^T M v)^T \quad (128) $$

$$ = v^T M^T u \quad (129) $$

$$ = \langle v, M^T u \rangle \quad (130) $$

$$ = \langle v u^T, M^T \rangle \quad (131) $$

□

We have:

$$ \frac{1}{n} \left\langle V(\mathbf{A}, \mathbf{\Omega}), V_{\mathrm{goal}_{\mathrm{proj}_{i,j,m}}} \right\rangle^2 = \frac{1}{n} \sum_{m}^{C[+1]} \sum_{i,j}^{n, H[+1]W[+1]} \sum_{k}^{K} \omega_{k,m}^{T} B_{i,j}^{t} \alpha_{k} V_{\mathrm{goal}_{\mathrm{proj}_{i,j,m}}} \quad (132) $$

$$ (V_{\mathrm{goal}_{\mathrm{proj}_{i,j,m}}} \in (1)) = \sum_{m}^{C[+1]} \sum_{k}^{K} \omega_{k,m}^{T} \frac{1}{n} \sum_{i,j}^{n, H[+1]W[+1]} (B_{i,j}^{t} V_{\mathrm{goal}_{\mathrm{proj}_{i,j,m}}}) \alpha_{k} \quad (133) $$
Extra Training TINY

<figure><img src="image_16.png" /><figcaption>Figure 14: Accuracy as a function of the number of epochs during extra training for TINY.</figcaption></figure>

Extra Training GradMax

<figure><img src="image_17.png" /><figcaption>Figure 15: Accuracy curves as a function of the number of epochs during extra training for GradMax.</figcaption></figure>
Using Lemma C.11 with $M \leftarrow \sum_{i,j}^{n,H[+1]W[+1]} V_{\text{goalproj}}(B_{i,j}^t)^T$

$$ = \sum_{m}^{C[+1]} \left\langle \sum_{k}^{K} \alpha_k \omega_{k,m}^T, \frac{1}{n} \sum_{i,j}^{n,H[+1]W[+1]} V_{\text{goalproj}}(B_{i,j}^t)^T \right\rangle \quad (134) $$

$$ = \sum_{m}^{C[+1]} \langle \mathbf{A}_F \mathbf{\Omega}[m]_F, \mathbf{N}_m \rangle \quad (135) $$

$$ = \langle \mathbf{A}_F \mathbf{\Omega}_F, \mathbf{N} \rangle \quad (136) $$

**Conclusion** In total, we get:

$$ \frac{1}{n} \left\| V(\mathbf{A}, \mathbf{\Omega}) - V_{\text{goalproj}} \right\|^2 \le \langle \mathbf{A}_F \mathbf{\Omega}_F, S \mathbf{A}_F \mathbf{\Omega}_F \rangle - 2 \langle \mathbf{A}_F \mathbf{\Omega}_F, \mathbf{N} \rangle + \frac{1}{n} \left\| V_{\text{goalproj}} \right\|^2 \quad (137) $$

If we suppose that $S$ is invertible, we can apply Lemma C.4 and get the result.

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

**Proposition C.2.** Solving 8 is equivalent to minimizing the loss $\mathcal{L}$ at order one in $V^l$. Furthermore performing an update of architecture with $\gamma \delta \mathbf{W}^*$ (5) and a neuron addition with $\gamma \theta_{\leftarrow\leftrightarrow}^{K^*}$ (3.2), has an impact on the loss at first order in $\gamma$ as :

$$ \mathcal{L}(f_{\theta \oplus \theta_{\leftarrow\leftrightarrow}^K}) = \mathcal{L}(f_{\theta}) - \gamma (\sigma'_{l-1}(0) \Delta_{\theta_{\leftarrow\leftrightarrow}^{K^*}} + \Delta_{\delta \mathbf{W}^*}) + o(\gamma) \quad (138) $$

with

$$ \Delta_{\theta_{\leftarrow\leftrightarrow}^{K^*}} := \frac{1}{n} \left\langle V_{\text{goalproj}}^l, V^l(\theta_{\leftarrow\leftrightarrow}^{K^*}) \right\rangle_{\text{Tr}} = \sum_{k=1}^{K} \lambda_k^2 \quad (139) $$

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

To prove such proposition we use the following lemma :

**Lemma C.12.** We note $V(\mathbf{A}, \mathbf{\Omega})$ the result of $\mathbf{B}$ after applying the layers parameterized by $\mathbf{A}$ and $\mathbf{\Omega}$. Let us consider $V(\mathbf{A}^*, \mathbf{\Omega}^*)$ where $\mathbf{A}^*$ and $\mathbf{\Omega}^*$ are defined in 3.2. Then:

$$ \frac{1}{n} \langle V_{\text{goalproj}}, V(\mathbf{A}^*, \mathbf{\Omega}^*) \rangle = ||\Lambda_K||^2 \quad (141) $$

*Proof.* Starting from Lemma C.3

$$ \frac{1}{n} \left\| V(\mathbf{A}^*, \mathbf{\Omega}^*) - V_{\text{goalproj}} \right\|^2 = - ||\Lambda_K||^2 + \frac{1}{n} \left\| V_{\text{goalproj}} \right\|^2 \quad (142) $$

Hence by developing the norm, we have:

$$ \frac{1}{n} ||V(\mathbf{A}^*, \mathbf{\Omega}^*)||^2 - \frac{2}{n} \langle V(\mathbf{A}^*, \mathbf{\Omega}^*), V_{\text{goalproj}} \rangle = - ||\Lambda_K||^2 \quad (143) $$

Moreover by construction we have $\frac{1}{n} ||V(\mathbf{A}^*, \mathbf{\Omega}^*)||^2 = ||\Lambda_K||^2$ and therefore we get:

$$ -\frac{2}{n} \langle V(\mathbf{A}^*, \mathbf{\Omega}^*), V_{\text{goalproj}} \rangle = -2 ||\Lambda_K||^2 \quad (144) $$

which concludes the proof.

<figure><img src="image_17.png" /></figure>
<table><caption>Table 2: Number of neurons to add per layer. The depth is identified by its name on tab 3</caption><tr><td>depth l</td><td>Conv2</td><td>Conv3</td><td>Conv5</td><td>Conv6</td><td>Conv8</td><td>Conv9</td><td>Conv11</td><td>Conv12</td></tr><tr><td>n<sub>l</sub></td><td>3</td><td>3</td><td>6</td><td>6</td><td>12</td><td>12</td><td>24</td><td>24</td></tr></table>

<table><caption>Table 3: Initial and final architecture for the models of Figure 5. Numbers in color indicate where the methods were allowed to add neurons (middle of ResNet blocks). In blue the initial structure for the model 1/64 and in green the initial structure for the model 1/4, ie 1/16 indicates that the model 1/64 started with 1 neurons at this layer while the model 1/4 started with 16 neurons at the same layer.</caption><thead><tr><th colspan="8">ResNet18</th></tr><tr><th>Layer name</th><th>Output size</th><th>Initial layers (kernel=(3,3), padd.=1)</th><th>Final layers (end of Fig 5)</th></tr></thead><tbody><tr><td>Conv 1</td><td>32 × 32 × 64</td><td>[3 × 3,]</td><td>[3 × 3, 64]</td></tr><tr><td>Conv 2</td><td>32 × 32 × 64</td><td>[3 × 3, 64]<br>[3 × 3, 1/16]</td><td>[3 × 3, 64]<br>[3 × 3, 64]</td></tr><tr><td>Conv 3</td><td>32 × 32 × 64</td><td>[3 × 3, 64]<br>[3 × 3, 1/16]</td><td>[3 × 3, 64]<br>[3 × 3, 64]</td></tr><tr><td>Conv 4</td><td>16 × 16 × 64</td><td>[3 × 3, 128]</td><td>[3 × 3, 128]</td></tr><tr><td>Conv 5</td><td>16 × 16 × 128</td><td>[3 × 3, 128]<br>[3 × 3, 2/32]</td><td>[3 × 3, 128]<br>[3 × 3, 128]</td></tr><tr><td>Conv 6</td><td>16 × 16 × 128</td><td>[3 × 3, 128]<br>[3 × 3, 2/32]</td><td>[3 × 3, 128]<br>[3 × 3, 128]</td></tr><tr><td>Conv 7</td><td>8 × 8 × 256</td><td>[3 × 3, 256]</td><td>[3 × 3, 256]</td></tr><tr><td>Conv 8</td><td>8 × 8 × 256</td><td>[3 × 3, 256]<br>[3 × 3, 4/64]</td><td>[3 × 3, 256]<br>[3 × 3, 256]</td></tr><tr><td>Conv 9</td><td>8 × 8 × 256</td><td>[3 × 3, 256]<br>[3 × 3, 4/64]</td><td>[3 × 3, 256]<br>[3 × 3, 256]</td></tr><tr><td>Conv 10</td><td>4 × 4 × 512</td><td>[3 × 3, 512]</td><td>[3 × 3, 512]</td></tr><tr><td>Conv 11</td><td>4 × 4 × 512</td><td>[3 × 3, 512]<br>[3 × 3, 8/128]</td><td>[3 × 3, 512]<br>[3 × 3, 512]</td></tr><tr><td>Conv 12</td><td>4 × 4 × 512</td><td>[3 × 3, 512]<br>[3 × 3, 8/128]</td><td>[3 × 3, 512]<br>[3 × 3, 512]</td></tr><tr><td>AvgPool2d</td><td>1 × 1 × 512</td><td></td><td></td></tr><tr><td>FC 1</td><td>100</td><td>512 × 100</td><td>256 × 100</td></tr><tr><td>SoftMax</td><td>100</td><td></td><td></td></tr></tbody></table>
We now prove the main proposition. Suppose that each quantity is added to the architecture with an amplitude factor $\gamma$ i.e. the best update is then $\gamma \delta \mathbf{W}^*$ and the new neurons are $\{\sqrt{\gamma}\boldsymbol{\alpha}_i^*, \sqrt{\gamma}\boldsymbol{\omega}_i^*\}_i$.

Using the Fréchet derivative on $\gamma$, we have the following:

$$ \mathcal{L}(\mathbf{a}^l + \gamma \delta \mathbf{a}^l) = \mathcal{L}(\mathbf{a}^l) + \langle \nabla_{\mathbf{a}^l} \mathcal{L}, \gamma \delta \mathbf{a}^l \rangle + o(\gamma) \quad (145) $$

On one hand, performing an update of architecture, ie $\mathbf{W}^* \leftarrow \mathbf{W} + \gamma \delta \mathbf{W}^*$, changes the activation function $\mathbf{a}^l$ by $\gamma \delta \mathbf{a}_u^l := \mathbf{V}(\gamma \delta \mathbf{W}^*)$. Then, as explained in Appendix A.5, adding neurons $(\mathbf{A}^*, \mathbf{\Omega}^*)$ at layer $l-1$ changes the activation function $\mathbf{a}^l$ by:

$$ \gamma \delta \mathbf{a}_u^l = \sigma'(0) \gamma \mathbf{V}(\mathbf{A}^*, \mathbf{\Omega}^*) + o(\gamma). \quad (146) $$

We now suppose $\delta \mathbf{a}_u^l \neq -\delta \mathbf{a}_u^l$ and perform a first order development in $\gamma$. Then combining Equations (145) and (146), we have:

$$ \mathcal{L}(\mathbf{A}^*, \mathbf{\Omega}^*) = \mathcal{L} + \langle \nabla_{\mathbf{a}^l} \mathcal{L}, \gamma (\delta \mathbf{a}_u^l + \delta \mathbf{a}_u^l) \rangle + o(\gamma). \quad (147) $$

Using that $v_{\text{goal}}(\mathbf{x}_i) := -\nabla_{\mathbf{a}^l(\mathbf{x}_i)} \ell(\mathbf{x}_i)$ and that $\mathcal{L} = \frac{1}{n} \sum_i \ell(\mathbf{x}_i)$, it follows that:

$$ \mathcal{L}(\mathbf{A}^*, \mathbf{\Omega}^*) = \mathcal{L} - \frac{1}{n} \langle \mathbf{V}_{\text{goal}}, \gamma (\delta \mathbf{a}_u^l + \delta \mathbf{a}_u^l) \rangle + o(\gamma) \quad (148) $$

$$ = \mathcal{L} - \frac{\gamma}{n} \left( \langle \mathbf{V}_{\text{goal}}, \delta \mathbf{a}_u^l \rangle + \langle \mathbf{V}_{\text{goal}} - \mathbf{V}(\gamma \delta \mathbf{W}^*), \delta \mathbf{a}_u^l \rangle + \gamma \langle \delta \mathbf{a}_u^l, \delta \mathbf{a}_u^l \rangle \right) + o(\gamma). \quad (149) $$

Using C.12 we have:

$$ \mathcal{L}(\mathbf{A}^*, \mathbf{\Omega}^*) = \mathcal{L} - \gamma \left( \sigma'(0) \sum_{k=1}^{K} \lambda_k^2 + \frac{1}{n} \langle \mathbf{V}_{\text{goal}}, \delta \mathbf{a}_u^l \rangle \right) + o(\gamma). \quad (150) $$

**Note on the approximation for convolutional layer.** By developing the expression $||\mathbf{V} - \mathbf{V}_{\text{goalproj}}||^2$, we remark that minimizing $||\mathbf{V} - \mathbf{V}_{\text{goalproj}}||^2$ over $\mathbf{V}$ is equivalent to maximizing $\langle \mathbf{V}, \mathbf{V}_{\text{goalproj}} \rangle$ with a constraint on the norm of $\mathbf{V}$. This constraint lies in the functional space of the activities and can be reformulated in the parameter space with the matrix $\mathbf{S}$ as $||\mathbf{A}\mathbf{\Omega}^T||_{\mathbf{S}} = ||\mathbf{V}||$. By changing the matrix $\mathbf{S}$ for another positive semi-definite matrix $\mathbf{S}_{\text{pseudo}}$, we modify the metric on $\mathbf{V}$ and obtain a pseudo-solution $\mathbf{S}_{\text{pseudo}}^{-1}\mathbf{N}$.

### C.3 Proposition 3.4 and Corollary 3.2

**Proposition C.3.** 3.4 Suppose $\mathbf{S}$ is semi definite, we note $\mathbf{S} = \mathbf{S}^{\frac{1}{2}}\mathbf{S}^{\frac{1}{2}}$. Solving equation 8 is equivalent to find the K first eigenvectors $\alpha_k$ associated to the K largest eigenvalues $\lambda$ of the generalized eigenvalue problem:

$$ \mathbf{N}\mathbf{N}^T\alpha_k = \lambda\mathbf{S}\alpha_k \quad (151) $$

**Corollary 2.** (3.2) 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.

**Proof**

To prove 3.4, we show that the solution of 151 and the formula of 3.2 are collinear.
<figure><img src="image_18.png" /><figcaption>Figure 16: Accuracy on test of as a function of the number of parameters during architecture growth from ResNet$_{1/64}$ to ResNet18. The normalization for GradMax is $\sqrt{10^{-3}}$</figcaption></figure>

<table><caption>Table 4: Final accuracy on test of ResNet18 of 16 after the architecture growth (grey) and after convergence (black). The number of start indicated the multiple of 50 epochs needed to achieve convergence. With the starting architecture ResNet$_{1/64}$ and $\Delta t = 1$ the method TINY achieves $68.0 \pm 0.4$ on test after its growth and it reaches $69.0 \pm 0.6$ after $* := 5 \times 50$ epochs.</caption><thead><tr><th></th><th>TINY</th><th>GradMax</th><th>Baseline</th></tr></thead><tbody><tr><th>$\Delta t$</th><td>1</td><td>1</td><td></td></tr><tr><th>$s$</th><td></td><td></td><td></td></tr><tr><th>1/64</th><td>68.0 ± 0.4</td><td>57.2 ± 0.3</td><td></td></tr><tr><th>1/64</th><td><b>69.0 ± 0.6</b><sup>5*</sup></td><td>57.7 ± 0.3<sup>3*</sup></td><td>72.9 ± 0.1<sup>5*</sup></td></tr></tbody></table>
Solving 151 is equivalent to maximizing the following generalized Rayleigh quotient (which is solvable by the LOBPCG technique):

$$ \alpha^* = \arg\max_{\alpha} \frac{\alpha^T N N^T \alpha}{\alpha^T S \alpha} \qquad (152) $$

$$ p^* = \arg\max_{p=S^{1/2}\alpha} \frac{p^T S^{-1/2} N N^T S^{-1/2} p}{p^T p} \qquad (153) $$

$$ p^* = \arg\max_{\|p\|=1} ||N^T S^{-1/2} p|| \qquad (154) $$

$$ \alpha^* = S^{-1/2} p^* \qquad (155) $$

Considering the SVD of $N^T S^{-1/2} = \sum_{r=1}^R \lambda_r e_r f_r^T$, then $S^{-1/2} N N^T S^{-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^{-1/2} f_k$, which matches the formula of Proposition 3.2. The same reasoning can be applied to $\omega_k$.

We prove second corollary 3.2 by induction. Note that $v(\theta_{\leftrightarrow}^{K,*}, x) = o(\eta)$, then for $m = m' = 1$:

$$ a_l(x)^{t+1} = a_l(x)^t + v(\theta_{\leftrightarrow}^{1,*}, x) + o(\eta) \qquad (156) $$

Remark that $v_{\text{goal}}(x)$ is a function of $a_l(x)$, i.e. $v_{\text{goal}}(x) := g(a_l(x))$. Then suppose that $\mathcal{L}(f(x), y)$ is twice differentiable in $a_l(x)$. It follows that $g(a_l(x))$ is differentiable and:

$$ v_{\text{goal}}^{t+1}(x) = g(a_l^t(x) + v(\theta_{\leftrightarrow}^{1,*}, x)) \qquad (157) $$

$$ = g(a_l^t(x)) + \nabla_{a_l^t(x)} g(a_l^t(x))^T v(\theta_{\leftrightarrow}^{1,*}, x) + o(\eta^2) \qquad (158) $$

$$ = v_{\text{goal}}^t(x) + \eta \frac{\partial^2 \mathcal{L}(f_\theta(x), y)}{\partial a_l^t(x)^2} v(\theta_{\leftrightarrow}^{1,*}, x) + o(\eta^2) \qquad (159) $$

$$ = v_{\text{goal}}^t(x) + o(\eta) \qquad (160) $$

Adding the second neuron we obtain the minimization problem:

$$ \arg\min_{\alpha_2, \omega_2} ||V_{\text{goal}}^t - V(\alpha_2, \omega_2)|| + o(\eta) \qquad (161) $$

□

## C.4 About equivalence of quadratic problems

Problems 8 and 7 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_{\leftrightarrow}^K) + V^l(M) - V_{\text{goal}}^l\|^2 $$

w.r.t. $M$ and $\theta_{\leftrightarrow}^K$ jointly, while in the other case the problem is first minimized w.r.t. $M$ and then w.r.t. $\theta_{\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(M) = \delta W_l B_{l-1}$ while $V^l(\theta_{\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_{\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 E.1), then it is possible to find suitable variables $\delta W_l$ and $\theta_{\leftrightarrow}^K$ to form any desired $V^l(M)$ and $V^l(\theta_{\leftrightarrow}^K)$. In particular, if $n_S \le n_{l-1} \le n_{l-2}$, one can choose $V^l(\theta_{\leftrightarrow}^K)$ to be $V_{\text{goal}}^l - V^l(M)$ 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(M)$ and $V^l(\theta_{\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.

# D Section About greedy growth sufficiency and TINY convergence with more details and proofs

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. 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 \sum_{x \in \mathcal{D}} \|f(x) - f^*(x)\|^2 \qquad (162) $$

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

We start with an optional introductory section D.1 about greedy growth possibilities, then prepare lemmas in Sections D.2 and D.3 that will be used in Section D.4 to show that one can keep on adding neurons to a network (without modifying already existing weights) to make it converge exponentially fast towards the optimal function. Then in Section D.6 we present a growth method that explicitly overfits each dataset sample one by one, thus requiring only $n$ neurons, thanks to existing weights modification. Finally, more importantly, in Section D.7, we show that actually any reasonable growth method that follows a certain optimization protocol (this includes TINY completed by random neuron additions if necessary) will reach 0 training error in at most $n$ neuron additions.

## D.1 Possibility of greedy growth

**Proposition D.1 (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 $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 \qquad (163) $$
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\|_{L^2}$, where $\langle a|b\rangle_{L^2} = \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$, and we write $a(x) = g(x) - g^*(x)$ the error term, it follows that:

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

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

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

Then:

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

$$ \forall x \in \omega, \quad (f^*(x) - h(x))^2 = a^2(x) \qquad (167) $$

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

$$ \|f^* - h\|_{L^2}^2 = \|a\|_{L^2}^2 \qquad (168) $$

$$ \|f^* - h\|_{L^2}^2 \le \gamma^2 = \frac{1}{100} \|f^* - f\|_{L^2}^2 \qquad (169) $$

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}{|D|} \sum_{x \in D} \|f(x) - f^*(x)\|^2}$, as Equation (167) then yields:

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

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 arbitrarily close to $c_n$, one can approximate the $n$-th derivative of $\sigma$ at $c_n$ and consequently the polynomial $c^n$ of order $n$. This standard proof then concludes by density of polynomials in continuous functions.

Provided the activation function $\sigma$ is not a polynomial, these values $c_n$ can actually be chosen arbitrarily, in particular arbitrarily close to 0. This corresponds to choosing neuron input weights arbitrarily close to 0. □

**Proposition D.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$.

**Proof.** From the previous proposition, there exists a finite set of neurons to add such that the loss will be decreased. In this particular setting of $L^2$ regression, or for more general losses if considering small function moves, this means that the function represented by this set of neurons has a strictly negative component over
the gradient $g$ of the loss ($g = -2(f^* - f)$ in the case of the $L^2$ regression). That is, denoting by $a_i\sigma(W_i \cdot x)$ these $N$ neurons:

$$ \left\langle \sum_{i=1}^{N} a_i \sigma(w_i \cdot x) \mid g \right\rangle_{L^2} = K < 0 \qquad (171) $$

i.e.

$$ \sum_{i=1}^{N} \langle a_i \sigma(w_i \cdot x) | g \rangle_{L^2} = K < 0 \qquad (172) $$

We have:

$$ 0 > \frac{1}{N} K = \frac{1}{N} \sum_{i=1}^{N} \langle a_i \sigma(w_i \cdot x) | g \rangle_{L^2} \geq \min_{i=1}^{N} \langle a_i \sigma(w_i \cdot x) | g \rangle_{L^2} \qquad (173) $$

Then necessarily at least one of the $N$ neurons satisfies

$$ \langle a_i \sigma(w_i \cdot x) | g \rangle_{L^2} \leq \frac{1}{N} K < 0 \qquad (174) $$

and thus decreases the loss when added to the hidden layer of the neural network representing $f$. Moreover this decrease is at least $\frac{1}{N}$ of the loss decrease resulting from the addition of all neurons. $\square$

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

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. Note that finding the optimal neuron to add is actually NP-hard (Bach, 2017), so we will not necessarily search for the optimal one. A constructive lower bound on how much the loss can be improved will be given later in this section.

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

*Proof.* This is straightforward, as, following a previous remark, the neurons found to collectively decrease the loss can be supposed to all have arbitrarily small input weights. $\square$

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

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.

**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 (8) will not find neurons to add. Yet following Prop. D.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) \simeq \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 $v(x)$, i.e. $E_{x \sim D}[x v(x)] = 0$, the quadratic term $(\alpha \cdot x)^2$, or higher-order ones otherwise, might be correlated with $v(x)$. Finding neurons with such higher-order correlations can be done by increasing accordingly the power of $(\alpha \cdot x)$ in the optimization problem (7). Note that one could consider other function bases than the polynomials from Taylor expansion, such as Hermite or Legendre polynomials, for their orthogonality properties. 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 the 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).

## D.2 Loss decreases with a line search on a quadratic energy

Let $\mathcal{L}$ be a quadratic loss over $\mathbb{R}^d$ and $g$ be a vector in $\mathbb{R}^d$. The loss $\mathcal{L}$ can be written as:

$$ \mathcal{L}(g) = g^T Q g + v^T g + K \quad (175) $$

where $Q$ is a matrix that we will suppose to be symmetric positive definite. This is to ensure that all eigenvalues of $Q$ are positive, hence modeling a local minimum without a saddle point. $v$ is a vector in $\mathbb{R}^d$ and $K$ is a real constant.

For instance, the mean square loss $\mathbb{E}_{x \in \mathcal{D}} [\|f(x) - f^*(x)\|_S^2]$, where $\mathcal{D}$ is a finite dataset of $N$ samples, $f^*$ a target function, and $S$ is a symmetric positive definite matrix used as a metric, fits these hypotheses, considering $g = (f(x_1), f(x_2), ...)$ as a vector. Indeed this loss rewrites as

$$ \sum_{i=1}^{N} f(x_i)^T S f(x_i) - 2 \sum_{i} f^{*T}(x_i) S f(x_i) + K = g^T Q g + v^T g + K \quad (176) $$

by flattening and concatenating the vectors $f(x_i)$ and considering $Q = S \otimes S \otimes S \otimes ...$ the tensor product of $N$ times the same matrix $S$, i.e. a diagonal-block matrix with $N$ identical blocks $S$. Note that for the standard regression with the $L^2$ metric, this matrix $Q$ is just the Identity.

Starting from point $g$, and given a direction $h \in \mathbb{R}^d$, the question is to perform a line search in that direction, i.e. to optimize the factor $\lambda \in \mathbb{R}$ in order to minimize $\mathcal{L}(g + \lambda h)$.

Developing that expression, we get:

$$ \mathcal{L}(g + \lambda h) = (g + \lambda h)^T Q (g + \lambda h) + v^T (g + \lambda h) + K = \lambda^2 h^T Q h + \lambda (2h^T Q g + v^T h) + \mathcal{L}(g) \quad (177) $$

which is a second-order polynomial in $\lambda$ with a positive quadratic coefficient. Note that the linear coefficient is $h^T \nabla_g \mathcal{L}(g)$, where $\nabla_g \mathcal{L}(g) = 2Qg + v$ is the gradient of $\mathcal{L}$ at point $g$. The unique minimum of the polynomial in $\lambda$ is then:

$$ \lambda^* = -\frac{1}{2} \frac{h^T \nabla_g \mathcal{L}(g)}{h^T Q h} \quad (178) $$

which leads to

$$ \min_{\lambda} \mathcal{L}(g + \lambda h) = \lambda^{*2} h^T Q h + \lambda^* h^T \nabla_g \mathcal{L}(g) + \mathcal{L}(g) \quad (179) $$

$$ = \mathcal{L}(g) - \frac{1}{4} \frac{(h^T \nabla_g \mathcal{L}(g))^2}{h^T Q h} \quad (180) $$

$$ = \mathcal{L}(g) - \frac{1}{4} \left\langle \frac{h}{\|h\|_Q} \middle| \nabla_g^Q \mathcal{L}(g) \right\rangle_Q^2 . \quad (181) $$

Thus the loss gain obtained by a line search in a direction $h$ is quadratic in the angle between that direction and the gradient of the loss, in the sense of the $Q$ norm (and it is also quadratic in the norm of the gradient). Note that inner products with the gradient do not depend on the metric, in the sense that
$\langle h | \nabla_g \mathcal{L}(g) \rangle_{L^2} = \langle h | \nabla_g^S \mathcal{L}(g) \rangle_S \quad \forall h$ for any metric $S$, i.e. any symmetric definite positive matrix $S$, associated to the norm $\|h\|_S^2 = h^T S h$ and to the gradient $\nabla_g^S \mathcal{L}(g) = S^{-1} \nabla_g^{L^2} \mathcal{L}(g)$.

In the case of a standard $L^2$ regression this boils down to:

$$ \min_{\lambda} \|g + \lambda h\|_{L^2}^2 = \|g\|^2 - \left\langle \frac{h}{\|h\|} \middle| g \right\rangle_{L^2}^2 \quad (182) $$

i.e. considering $\mathcal{L}(f) := \mathbb{E}_{x \in \mathcal{D}} \left[ \|f(x) - f^*(x)\|^2 \right]$:

$$ \min_{\lambda} \mathcal{L}(f + \lambda h) = \mathcal{L}(f) - \left\langle \frac{h}{\|h\|} \middle| f^* - f \right\rangle_{L^2}^2 = \mathcal{L}(f) - \frac{\mathbb{E}_{x \in \mathcal{D}} [(f^* - f)h]^2}{\mathbb{E}_{x \in \mathcal{D}} [\|h\|^2]} \quad (183) $$

A result that is useful in the next sections.

## D.3 Expected loss gain with a line search in a random direction

Using Appendix D.2 above, the loss gain when performing a line search on a quadratic loss is quadratic in the angle $\alpha = \left\langle \frac{V(X)}{\|V(X)\|} \middle| \frac{V_{\text{goal}}(X)}{\|V_{\text{goal}}(X)\|} \right\rangle_{L^2}$ between the random search direction $V(X)$ and the gradient $V_{\text{goal}}(X)$.

This angle has average 0 and is of standard deviation $\frac{1}{nd}$, as described in Section 5.2. The loss gain is thus of the order of magnitude of $\frac{1}{d}$ in the best case (single-sample minibatch).

## D.4 Exponential convergence to 0 training error

Considering a regression to a target $f^*$ with the quadratic loss, the function $f$ represented by the current neural network (fully-connected, one hidden layer, with ReLU activation function) can be improved to reach 0 loss by an addition of $n$ neurons $(h_i)_{1 \le i \le n}$, with $n$ is the dataset size, using Zhang et al. (2017). Unfortunately there is no guarantee that if one adds each of these neurons one by one, the loss decreases each time. We will prove that one of these neurons does decrease the loss, and we will quantify by how much, relying on the explicit construction in Zhang et al. (2017). This decrease will actually be a constant factor of the loss, thus leading to exponential convergence towards the target $f^*$ on the training set.

As in the proof of Proposition D.2 in Appendix D, at least one of the added neurons satisfies that its inner product with the gradient direction is at least $1/n$. While one could consequently hope for a loss gain in $O(1/n)$, one has to see that this decrease would be the one of a gradient step, which is multiplied by a step size $\eta$, and asks for multiple steps to be done. Instead in our approach we actually perform a line search over the direction of the new neuron. In both cases (line search or multiple small gradient steps), one has to take into account at least order-2 changes of the loss to compute the line search or estimate suitable $\eta$ and/or its associated number of steps. Luckily in our case of least square regression, the loss is exactly equal to its second order Taylor development, and all following computations are exact.

We consider the mean square regression loss $\mathcal{L}(f) = \mathbb{E}_{x \in \mathcal{D}} \left[ \|f(x) - f^*(x)\|_S^2 \right]$, where $\mathcal{D}$ is a finite training dataset of $N$ samples. Its functional gradient $\nabla \mathcal{L}(f)$ at point $f$ is $2(f - f^*)$, which is proportional to the optimal change to add to $f$, that is, $f^* - f$. The $n$ neurons $(h_i)_{1 \le i \le n}$ to be added to $f$ following Zhang et al. (2017) satisfy $\sum_i h_i = f^* - f = -\frac{1}{2} \nabla \mathcal{L}(f)$. Thus

$$ \left\langle \sum_i h_i \middle| f^* - f \right\rangle_{L^2} = \|f^* - f\|_{L^2}^2 = \mathcal{L}(f) \quad (184) $$

Then like in the proof of D.2 we use that the maximum is greater or equal to the mean to get that there exists a neuron $h_i$ that satisfies:

$$ \langle h_i | f^* - f \rangle_{L^2} \ge \mathcal{L}(f)/n. \quad (185) $$
By applying Appendix D.2 one obtains that the new loss after line search into the direction of $h_i$ yields:

$$ \min_{\lambda} \mathcal{L}(f + \lambda h_i) = \mathcal{L}(f) - \frac{\langle h_i | f^* - f \rangle_{L^2}}{\|h_i\|^2} \le \mathcal{L}(f) \times \left(1 - \frac{\mathcal{L}(f)}{n^2 \|h_i\|^2}\right). \quad (186) $$

From the particular construction in Zhang et al. (2017) it is possible to bound the square norm of the neuron $\|h_i\|^2$ by $n d' \left(\frac{d_M}{d_m}\right)^2 \mathcal{L}(f)$, where $d_M$ is related to the maximum distance between 2 points in the dataset, $d_m$ is another geometric quantity related to the minimum distance, and $d'$ is the network output dimension. To ease the reading of this proof, we defer the construction of this bound to the next section, Appendix D.5.

Then the loss at each neuron addition decreases by a factor which is at least $\gamma = 1 - \frac{1}{n^3 d'} \left(\frac{d_M}{d_M}\right)^2 < 1$. This factor is a constant, as it is a bound that depends only on the geometry of the dataset (not on $f$).

Thus it is possible to decrease the loss exponentially fast with the number $t$ of added neurons, i.e. $\mathcal{L}(f_t) \le \gamma^t \mathcal{L}(f)$, towards 0 training loss, and this in a greedy way, that is, by adding neuron one by one, with the property that each neuron addition decreases the loss.

Note that, in the proof of Zhang et al. (2017), the added neurons could be chosen to have arbitrarily small input weights. This corresponds to choosing $a$ with small norm instead of unit norm in Equation 187.

The number of neuron additions expected to reach good performance according to this bound is in the order of magnitude of $n^3$, which is to be compared to $n$ (number of neurons needed to overfit the dataset, without the constraint that each addition decreases the loss). This bound might be improved using other constructions than Zhang et al. (2017), though with this proof the bound cannot be better than $n^2$ (supposing $\|h_i\|$ can be made not to depend on $n$).

Note also that with ReLU activation functions, all points that are on the convex hull of the dataset (which is necessarily the case of all points if the input dimension is higher than the number of points) can easily in turn be perfectly predicted (0 loss) by just one neuron addition each (without changing the outputs for the other points), by choosing an hyperplane that separates the current convex hull point from the rest of the dataset, and setting a ReLU neuron in that direction.

## D.5 Bound on the norm of the neurons

Here we prove that the neurons obtained by Zhang et al. (2017) can be chosen so as to bound the square norm of any neuron $\|h_i\|^2$ by $n d' \left(\frac{d_M}{d_m}\right)^2 \mathcal{L}(f)$, where $d_M$ is related to the maximum distance between 2 points in the dataset, and $d_m$ is another geometric quantity related to the minimum distance. For the sake of simplicity, we first consider the case where the output dimension is $d' = 1$.

In Zhang et al. (2017), the $n$ neurons are obtained by solving $y = Aw$, where $y = (y_1, y_2...)$ is the target function (here $(f^* - f)$ at each $x_j$), $A$ is the matrix given by $A_{jk} = \text{ReLU}(a \cdot x_j - b_k)$, representing neuron activations, and $a$ is any vector that separates the dataset points, i.e. $a \cdot x_j \ne a \cdot x_{j'} \forall j \ne j'$, that is, $a$ could be almost any vector in $\mathbb{R}^d$ (in the sense of random projections, that is, the set of vectors that do not satisfy this is of measure 0).

Here we will pick a particular unit direction $a$, one that maximizes the distance between any two samples after projection:

$$ a \in \arg\max_{\|a\|=1} \min_{j,j'} |a \cdot (x_j - x_{j'})| \quad (187) $$

and let us denote $d'_m$ the associated value: $d'_m = \min_{j,j'} |a \cdot (x_j - x_{j'})|$ for that $a$. Note that $d'_m \le \min_{j,j'} \|x_j - x_{j'}\|$ and that it depends only on the training set. The quantity $d'_m$ is likely to be also lower-bounded (over all possible datasets) by $\min_{j,j'} \|x_j - x_{j'}\|$ times a factor depending on the embedding dimension $d$ and the number of points $n$.

Now, let us sort the samples according to increasing $a \cdot x_j$, that is, let us re-index the samples such that $(a \cdot x_j)$ now grows with $j$. By definition of $a$, the difference between any two consecutive $a \cdot x_j$ is at least $d'_m$.
We now choose biases $b_j = a \cdot x_j - d'_m + \varepsilon$ for some very small $\varepsilon$. The neurons are then defined as $h_k(x) = w_k \text{ReLU}(a \cdot x_j - b_k)$. The induced activation matrix $A_{jk} = \text{ReLU}(a \cdot x_j - b_k)$ then satisfies $\forall j < k; A_{jk} = 0$ and $\forall j \ge k; A_{jk} \ge d'_m - \varepsilon$. The matrix $A$ is lower triangular with diagonal elements above $d_m := d'_m - \varepsilon$, hence invertible. Recall that $y = Aw$.

Consequently, $w = A^{-1}y$, and hence $\|w\|^2 \le \|A^{-1}\|^2 \|y\|^2$, that is,

$$ \|w\|^2 \le \frac{1}{d_m^2} \mathcal{L}(f) \qquad (188) $$

as the target $y$ is the vector $f^* - f$ in our case. Consequently, for any neuron $h_i$, one has:

$$ w_i^2 \le \frac{1}{d_m^2} \mathcal{L}(f). \qquad (189) $$

As the norm of the neuron is $\|h_i\|^2 = w_i^2 \sum_j A_{ji}^2$, one still has to bound the activities $A_{ji} = \text{ReLU}(a \cdot x_j - b_i)$. As $a$ was chosen a unit direction, the values $a \cdot x_j$ span a domain smaller than the diameter of the dataset $\mathcal{D}$: $|a \cdot (x_j - x_{j'})| \le \|x_j - x_{j'}\| \le \text{diam}(\mathcal{D}) \forall j, j'$. Hence all values $\forall i, j, |A_{ij}| = |a \cdot x_i - b_j| = |a \cdot x_i - a \cdot x_j + d_m| < d_M := \text{diam}(\mathcal{D}) + d_m$. Note that $d_M$ depends only the dataset geometry, as for $d_m$.

We now have:

$$ \|h_i\|^2 = w_i^2 \sum_j A_{ji}^2 \le n \frac{d_M^2}{d_m^2} \mathcal{L}(f) \qquad (190) $$

which ends the proof.

For higher output dimensions $d'$, one vector $w$ of output weights is estimated per dimension, independently, leading to the same bound for each dimension. The square norms of neurons are summed over all dimensions and thus multiplied by at most $d'$.

## D.6 Reaching 0 training error in $n$ neuron additions by overfitting each dataset sample in turn

If one allows updating already existing output weights at the same time as one adds new neurons, then it is possible to reach 0 training error in only $n$ steps (where $n$ is the size of the dataset) while decreasing the loss at each addition.

This scenario is closer to the one we consider with TINY, as we compute the optimal update of existing weights inside the layer, as a byproduct of new neuron estimation, and apply them.

However the existence proof here follows a very different way to create new neurons, tailored to obtain a constructive proof, and inspired by the previous section. See Appendix D.7 for another, more generic proof, applicable to a wide range of growth methods.

Here we consider the same approach as in Appendix D.5 above, but introducing neurons one by one instead of $n$ neurons at once. After computing $a$ and the biases $b_j$, thus forming the activity matrix $A$, we add only the last neuron $h_n$. The activity of this neuron is 0 for all input samples $x_j$ except for the last one, for which it is $A_{nn} > 0$. Thus, the neuron $h_n$ separates the sample $x_n$ from the rest of the dataset, and it is easy to find $w_n$ so that the loss gets to 0 on that training sample, without changing the outputs for other samples.

Similarly, one can then add neuron $h_{n-1}$, which is active only for samples $x_{n-1}$ and $x_n$. However designing $w_{n-1}$ so that the loss becomes 0 at point $x_{n-1}$ disturbs the output for point $x_n$ (and for that point only). Luckily if one allows updating $w_n$ then there exists a (unique) solution $(w_{n-1}, w_n)$ to achieve 0 loss at both points. This is done exactly as previously, by solving $y = Aw$, but considering only the last 2 lines and rows of $A$, leading to a smaller $2 \times 2$ system which is also lower-triangular with positive diagonal.

Proceeding iteratively this way adds neuron one by one in a way that sends each time one more sample to 0 loss. Thus adding $n$ neurons is sufficient to achieve 0 loss on the full training set, and this in a way that each time decreases the loss.

Note that updating existing output weights $w_i$ while adding a new neuron, to decrease optimally the loss, is actually what TINY does. However, the construction in this Appendix completely overfits each sample
in turn, by design, without being able to generalize to new test points. On the opposite, TINY exploits
correlations over the whole dataset to extract the main tendencies.

D.7 TINY reaches 0 training error in n neuron additions

We will now show that the TINY approach, as well as any other suitable greedy growth method, implemented
within the right optimization procedure, reaches 0 training error in at most *n* steps (where *n* is the size of
the dataset), almost surely.

Before stating it formally, we need to introduce the optimization protocol, growth completion and a proba-
bility measure over activation functions.

**Optimization protocol.** For this we consider the following optimization protocol conditions, that has to be applied at least during the last, *n*-th addition step:

• a full batch approach,

• when adding new neurons, also compute and add the optimal moves of already existing pa- rameters (i.e. of output weights w).

The first point is to ensure that all dataset samples will be taken into account in the loss during the *n*-th
update. Otherwise, for instance if using minibatches instead, the optimization of output weights *w* will not
be able to overfit the training loss.

The second point is to make sure that, after update, the output weights *w* will be optimal for the training loss. Note that in the mean square regression case, this is easy to do, as the loss is quadratic in *w*: the optimal move (leading to the global optimum *f*\*) can be obtained by line search over the natural gradient (which is obtained for free as a by-product of TINY's projection of *V*<sub>goal</sub>, and is proportional to *f*\* − *f*). This is precisely what we do in practice with TINY when training networks (except when comparing with other methods and using their own protocol).

**Growth completion.** For this proof to make sense, we will need the growth method to actually be able to perform *n* neuron additions, if it has not reached 0 training loss before. A counter-example would be a growth method that gets stuck at a place where the training loss is not 0 while being unable to propose new neuron to add. In the case of TINY, this can happen when no correlation between inputs *x*ᵢ and desired output variations *f*\*(*x*ᵢ) − *f*(*x*ᵢ) can be found anymore. To prevent this, one can choose any auxiliary method to add neurons in such cases, for instance random directions, solutions of higher-order expressivity bottleneck formulations using further developments of the activation function, or locally optimal neurons found by gradient descent. Some auxiliary methods are guaranteed to further decrease the loss by a neuron addition (cf. Appendices D.2, D.3, D.4), while any other one is guaranteed not to increase the loss if combined with a line search along that neuron direction.

We will name *completed-TINY* the completion of TINY by any such auxiliary method.

**Activation function.** For technical reasons, the result will stand *almost surely* only, depending on the invertibility of a certain matrix, namely, the activation matrix *A*, defined as $A_{ij} = \sigma(v_j \cdot x_i + b_j)$, indexed by samples *i* and neurons *j*.

Generally speaking, kernels induced by neurons $k_j : x \mapsto \sigma(v_j \cdot x + b_j)$ form free families, in the sense that they are linearly independent (to the notable exception of the linear kernel). This linear independency means that a linear combination of kernels cannot be equal, as a function, to another kernel with different parameters. Equality is to be understood as *for all possible points x ever*. However here we will evaluate the functions only at a finite number *n* of points (the dataset samples), therefore linear independence will be considered among the rows of the activation matrix *A*. This notion of linear dependence is much weaker: kernels might form a free family as functions but be linearly dependent once restricted to the dataset samples, by mere chance. While this is not likely (over dataset samples), this is not impossible in general (though of
measure 0), and it is difficult to express an explicit, simple condition on the activation function to be sure that the activation matrix A is always invertible (up to slight changes of parameters). Thus instead we will express results almost surely over activation functions and neuron parameters.

For most activation functions in the space of smooth functions, the activation matrix A will be invertible almost surely over all possible datasets. In the unlucky case where the matrix is not invertible, an infinitesimal move of the neurons’ parameters will be sufficient to make it invertible. For some activation functions, however, such as linear or piecewise-linear ones (e.g., ReLU), the matrix might remain non-invertible over a wide range of parameter variations (unless further assumptions are made on the neurons added by the growth process). Yet, in such cases, slight perturbations of the activation function (i.e., choosing another, smooth, activation function, arbitrarily close to the original one) will yield invertibility.

To properly define "almost surely" regarding activation functions, let us restrict the activation function $\sigma$ to belong to the space $\mathfrak{P}$ of polynomials of order at least $n^2$, that is:

$$ \sigma(x) = \sum_{k=0}^{K} \gamma_k x^k \qquad (191) $$

with $n^2 \le K < +\infty$, and non-0 highest-order amplitude $\gamma_K \ne 0$. This set $\mathfrak{P}$ is dense in the set of all continuous functions over the set $\Omega = [-r_M, r_M]^d$ which is a hypercube of sufficient radius $r_M$ to cover all samples from the given dataset. One can define probability distributions over $\mathfrak{P}$, for instance consider the density $p(\sigma) = \frac{\alpha}{K^2} \prod_{k=0}^{K} \frac{e^{-\gamma_k^2}}{\sqrt{2\pi}}$ with a factor $\alpha = \left(\frac{\pi^2}{6} - \sum_{k<n^2} \frac{1}{k^2}\right)^{-1}$ to normalize the distribution, and where K is the order of the polynomial and thus depends on $\sigma$. This density is continuous in the space of parameters $\gamma_k$ (though not continuous in the usual functional metric spaces). Note that the decomposition of any $\sigma \in \mathfrak{P}$ as a finite-order polynomial is unique, as monomials of different orders are linearly independent.

We can now state the following lemma (that we will prove later):

**Lemma D.1** (Invertibility of the activation matrix). Let $\mathcal{D} = \{x_i, 1 \le i \le n\}$ be a dataset of $n$ distinct points, and let $\sigma: \mathbb{R} \to \mathbb{R}$ be a function in $\mathfrak{P}$, that is, a polynomial of order at least $n^2$. Then with probability 1 over function and neuron parameters ($\gamma_k$), $(v_j)$ and $(b_j)$, the activity matrix $A$ defined by $A_{ij} = \sigma(v_j \cdot x_i + b_j)$ is full rank.

and the following proposition:

**Proposition D.4** (Reaching 0 training error in at most $n$ neuron additions). Under the assumptions above (polynomial activation function of order $\ge n^2$, full-batch optimization and computation of the optimal moves of already existing parameters), completed-TINY reaches 0 training error in at most $n$ neuron additions almost surely.

*Proof.* If the growth method reaches 0 training error before $n$ neuron additions, the proof is done. Otherwise, let us consider the $n$-th neuron addition. We will show in Lemma D.1 that the activity matrix $A$, defined by $A_{ij} = \sigma(v_j \cdot x_i + b_j)$, indexed by samples $i$ and neurons $j$, is invertible. Then there exists a unique $w \in \mathbb{R}^n$ such that $Aw = f^*$, i.e. $\sum_j w_j \sigma(v_j \cdot x_i + b_j) = f^*(x_i)$ for each point $x_i$ of the dataset. This vector of output parameters $w$ realizes the global minimum of the loss over already existing weights: $\inf_w \mathcal{L}(f_{v,w}) = \inf_w \|Aw - f^*\|^2$. They are also the ones found by a natural gradient step over the loss (up to a factor 2, that can easily be found by line search as the loss is convex). Then after that update the training loss is exactly 0. $\square$

Note: piecewise-linear activation functions such as ReLU are not covered by this proposition. However the result might still hold with further assumptions over the growth process. For instance, with the method in Zhang et al. (2017), the ReLU neurons are chosen in such a way that the matrix $A$ is full rank by construction.

*Proof of Lemma D.1.* Let us first show that if, unluckily, for a given activation function $\sigma$ and given parameters $(v_j, b_j)$, the matrix $A$ is not full rank, then upon infinitesimal variation of the parameters, the matrix $A$ becomes full rank.
Indeed, if all pre-activities $a_{i,j} := v_j \cdot x_i + b_j$ are not distinct for all $i, j$, then an infinitesimal variation of the vectors $v_j$ can make them distinct. For this, one can see that the set of directions $v_j$ on which any two dataset points $x_i$ and $x_{i'}$ have the same projection is finite (since it has to be the direction of $x_i - x_{i'}$, for a given pair of dataset samples $(i, i')$) and thus of measure 0. As a consequence with probability 1 over neuron parameters $v_j$ and $b_j$, all pre-activities are distinct.

Now, if the matrix $A$ is not invertible, as invertible matrices are dense in the space of matrices, one can easily find an infinitesimal change $\delta A$ to apply to $A$ to make it invertible. This corresponds to changing the activation function $\sigma$ accordingly at each of the $n^2$ distinct pre-activity values. Since $\sigma$ has more than $n^2$ parameters, this is doable. For instance, one can select the $n^2$ first parameters and search for a suitable variation $g := (\delta\gamma_k)_{0\le k<n^2}$ of them by solving the linear system $Sg = \delta A$ where the $n^2 \times n^2$ matrix $S$ is defined by $S_{ij,k} = a_{i,j}^k = (v_j \cdot x_i + b_j)^k$. This matrix $S$ is invertible because any $g$ such that $Sg = 0$ would induce:

$$ \forall i, j, \sum_{k=0}^{n^2-1} \delta\gamma_k a_{i,j}^k = 0 \qquad (192) $$

and thus the polynomial $P(x) = \sum_{k=0}^{n^2-1} \delta\gamma_k x^k$ has at least $n^2$ roots while being of order at most $n^2 - 1$. Thus $Sg = 0 \implies g = 0$ and $S$ is invertible. Note that as $\delta A$ is infinitesimal, $g = S^{-1}\delta A$ will be infinitesimal as well, and so is the change brought to the activation function $\sigma$.

Consequently we have that the set of activation functions $\sigma$ and neuron parameters $(v_j, b_j)$ for which the matrix $A$ is full rank is dense in the set of polynomials $\mathfrak{P}$ of order at least $n^2$ and of neuron parameters $\mathfrak{N}$.

Now, the function $\det : \mathfrak{P} \times \mathfrak{N} \to \mathbb{R}$, $((\gamma_k)_k, (v_j, b_j)_j) \mapsto \det A = \det(\sigma_\gamma(v_j \cdot x_i + b_j))$ is smooth as a function of its input parameters (the determinant being a polynomial function of the matrix coefficients). As this continuous function is non-0 on a dense set of its inputs, the pre-image $\det^{-1}\{0\}$ is closed and contains no open subset. This is not yet sufficient to prove that this pre-image is of measure 0 (e.g., fat Cantor set).

For a fixed order $K$, one can see this function as a polynomial of its inputs $\gamma_k$ and $v_j, b_j$, and conclude<fnref n="2" /> that the set of its roots is of measure 0. As a consequence, the probability, over coefficients $\gamma_k$ or equivalently over polynomials $\sigma$ of order $K$, that $\det A$ is non-0, is 1. As this stands for all $K$, we have that the probability that the matrix $A$ is invertible is at least the mass of polynomials of all orders $K$, i.e. $\sum_{k \ge n^2} \frac{\alpha}{k^2} = 1$. Thus $A$ is invertible with probability 1. □

# E Technical details

## E.1 Batch size to estimate the new neuron and the best update

In this section we study the variance of the matrices $M^*$ and $S^{-1/2}N$ computed using a minibatch of $n$ samples, seeing the samples as random variables, and the matrices computed as estimators of the true matrices one would obtain by considering the full distribution of samples. Those two matrices are the solutions of the multiple linear regression problems defined in (35) and in (46), as we are trying to regress the desired update noted $Y$ onto the span of the activities noted $X$. We suppose we have the following setting:

$$ Y \sim AX + \varepsilon, \quad \varepsilon \sim \mathcal{N}(0, \sigma^2), \quad \mathbb{E}[\varepsilon|X] = 0 \qquad (193) $$

where the $(X_i, Y_i)$ are i.i.d. and $A$ is the oracle for $M^*$ or matrix $S^{-1/2}N$. If $Y$ is multidimensional, the total variance of our estimator can be seen as the sum of the variances of the estimator on each dimension of $Y$.

We now suppose that $Y \in \mathbb{R}$ and note $\hat{A} := YX^T(XX^T)^+ $ the solution of 193. We first remark that $\hat{AX} = YP$ with $P = X^T(XX^T)^+X \in \mathbb{R}(n, n)$. It follows that when $n \le p$, almost surely we have $rk(P) = n$ and $YP = Y$, resulting in a zero expressivity bottleneck for that specific mini-batch, i.e. $Y = \hat{AX}$. In

<footnote n="2">²See for instance a proof by recurrence that roots of a polynomial are always of measure 0: https://math.stackexchange.com/questions/1920302/the-lebesgue-measure-of-zero-set-of-a-polynomial-function-is-zero.</footnote>
practice, we do not consider $n < p$ as the solution ($\delta W$ or $A, \Omega$) would overfit a specific mini-batch and would increase the expressivity bottleneck for the rest of the dataset.

We now suppose that $n > p$, we now have almost surely that $rk(P) = p$ and $YP \neq Y$. We now study the variance of the estimator $\hat{A} \in \mathbb{R}^p$. We have almost surely that $XX^T$ is invertible and note $(XX)^{-1}$ its inverse. Taking the expectation on variable $\epsilon$, we have $cov(\hat{A}) = \sigma^2(XX^T)^{-1}$. If $n$ is large, and if matrix $\frac{1}{n}XX^T \to Q$, with $Q$ non-singular, then, asymptotically, we have $\hat{A} \sim N(A, \sigma^2 Q^{-1})$, which is equivalent to $(\hat{A} - A)\frac{\sqrt{n}}{\sigma}Q^{1/2} \sim N(0, I)$. Then $||(\hat{A} - A)\frac{\sqrt{n}}{\sigma}Q^{1/2}||^2 \sim \chi^2(k)$ where $k$ is the dimension of $X$. It follows that $E[||(\hat{A} - A)Q^{1/2}||^2] = \frac{k\sigma^2}{n}$ and as $Q^{1/2}Q^{1/2}T$ is positive definite, we conclude that $\text{var}(\hat{A}) \le \frac{k\sigma^2}{n\lambda_{\min}(Q)}$.

In practice we aim to keep the variance of our estimators stable during architecture growth. To ensure this we can choose the batch size $n$ to make the bound constant. With the notations defined in Figure 12, we estimate a matrix of size $k \leftarrow (SW)^2$. For $n$ images, as each input sample contains $P$ quantities, and that each is a realization of the random variable $X$ (total $nP$ variables), we have in total $n \leftarrow nP$ data points for the estimation of the best neuron. Hence to add new neurons with a (asymptotically) fixed variance, we use batch size

$$n \propto \frac{(SW)^2}{P}.$$

For convolutional layers, we take $n = 0.001 \times \frac{(SW)^2}{P} \times 2^k$ (Figure 5) and $n = 0.01 \times \frac{(SW)^2}{P} \times 2^k$ (Figure 8), where $k$ is equal to $\sqrt{\frac{32 \times 32}{P}}$, and this $2^k$ factor is found empirically to somehow account for the variances of the estimators even when the same input is used multiple times, as are the $\{B_{i,j}^t\}_{j \in P}$ in Equation (55).

## E.2 Batch size for learning

We adjust the batch size for gradient descent as follows: the batch size is set to $b_{t=0} = 32$ at the beginning of each experiment, and it is scheduled to increase as the square root of the complexity of the model (i.e. number of parameters). If at time $t$ the network has complexity $C_t$ parameters, then at time $t+1$ the training batch size is equal to $b_{t+1} = b_t \times \sqrt{\frac{C_{t+1}}{C_t}}$.

## E.3 Normalization

### E.3.1 Figures 5, 6 and 16 : Usual normalization

For the GradMax method of Figures 5 and 16, before adding the new neurons to the architecture, we normalize the outgoing weight of the new neurons according to Evci et al. (2022), i.e. :

$$\alpha_k^* \leftarrow 0 \qquad (194)$$

$$\text{for Figures 5 and 6 } \omega_k^* \leftarrow \omega_k^* \times \frac{10^{-3}}{\sqrt{\| (\omega_j^*)^{n_d}_{j=1} \|_2^2 / n_d}} \qquad (195)$$

$$\text{for Figure 16 } \omega_k^* \leftarrow \omega_k^* \times \sqrt{\frac{10^{-3}}{\| (\omega_j^*)^{n_d}_{j=1} \|_2^2 / n_d}} \qquad (196)$$

For TINY method of both figures, the previous normalization process is mimicked by normalizing the in and out going weights by their norms and multiplying them by $\sqrt{10^{-3}}$, i.e. :

$$\alpha_k \leftarrow \alpha_k^* \times \sqrt{\frac{10^{-3}}{\| (\alpha_j^*)^{n_d}_{j=1} \|_2^2 / n_d}} \qquad (197)$$

$$\omega_k \leftarrow \omega_k^* \times \sqrt{\frac{10^{-3}}{\| (\omega_j^*)^{n_d}_{j=1} \|_2^2 / n_d}} \qquad (198)$$
### E.3.2 Figure 8: Amplitude Factor

For the Random and the TINY methods of Figure 8, we first normalize the parameters as:

$$ 
\begin{aligned}
\text{For the new neurons:} \\
\alpha_k^* &\leftarrow \alpha_k^* \times \frac{1}{\sqrt{\| (\alpha_j^*)^{n_d}_{j=1} \|_2^2 / n_d}} \\
\omega_k^* &\leftarrow \omega_k^* \times \frac{1}{\sqrt{\| (\omega_j^*)^{n_d}_{j=1} \|_2^2 / n_d}}
\end{aligned}
$$

$$ 
\begin{aligned}
\text{For the best update:} \\
\mathbf{W}^* &\leftarrow \mathbf{W}^* \times \frac{1}{\sqrt{\|\mathbf{W}^*\|_2^2 / n_d}}
\end{aligned}
$$

Then, we multiply them by the amplitude factor $\gamma^*$:

$$ 
\begin{aligned}
\text{For the new neurons:} \\
\alpha_k^*, \omega_k^* &\leftarrow \alpha_k^* \gamma^*, \omega_k^* \gamma^* \\
\gamma^* &:= \arg \min_{\gamma \in [-L, L]} \sum_i \mathcal{L}(f_{\theta \oplus \gamma \theta_{\leftarrow K}}(\mathbf{x}_i), \mathbf{y}_i)
\end{aligned}
$$

$$ 
\begin{aligned}
\text{For the best update:} \\
\mathbf{W}_l^* &\leftarrow \gamma^* \mathbf{W}_l \\
\gamma^* &:= \arg \min_{\gamma \in [-L, L]} \sum_i \mathcal{L}(f_{\theta + \gamma \mathbf{W}^*}(\mathbf{x}_i), \mathbf{y}_i)
\end{aligned}
$$

where the operation $\gamma \theta_{\leftarrow K}^* = (\gamma \alpha_k^*, \gamma \omega_k^*)^K$ is the concatenation of the neural network with the new neurons and $\theta + \gamma \mathbf{W}^*$ is the update of one layer with its best update. The batch on which $\gamma^*$ is computed is different from the one used to estimate the new parameters and its size is fixed to 1000 for all experiments.

## E.4 Full algorithm

In this section we describe in detail the pseudo-code to plot Figures 5, 6 and 8. The function NewNeurons($l$), in Algorithm 2, computes the new neurons defined at Proposition 3.2 for layer $l$ sorted by decreasing eigenvalues. The function BestUpdate($l$), in Algorithm 4 computes the best update at Proposition 3.1 for layer $l$.

**Algorithm 1:** Algorithm to plot Figures 5 and 8.

1. **for** each method [TINY, MethodToCompareWith] **do**
2. &nbsp;&nbsp;&nbsp;&nbsp;Start from neural network $N$ with initial structure $s \in \{1/4, 1/64\}$;
3. &nbsp;&nbsp;&nbsp;&nbsp;**while** $N$ architecture does not match ResNet18 width **do**
4. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** $d$ in $\{\text{depths to grow}\}$ **do**
5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \theta_{\leftarrow K}^* = \text{NewNeurons}(d, \text{method}) ; $$
6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \text{Normalize } \theta_{\leftarrow K}^* \text{ according to E.3} ; $$
7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \text{Add the neurons at layer } d ; $$
8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \text{Train } N \text{ for } \Delta t \text{ epochs} ; $$
9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \text{Save model } N \text{ and its performance} ; $$
10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \text{end} $$
11. &nbsp;&nbsp;&nbsp;&nbsp;$$ \text{end} $$
12. $$ \text{end} $$
**Algorithm 2: NewNeurons**

Data: $l$, method = *TINY*

Result: Best neurons at $l$

1 if method = *TINY* then

2 $M$ = BestUpdate($l$ + 1);

3 $S, N$ = MatrixSN($l-1, l+1, M = M$);

4 Compute the SVD of $S := O\Sigma O^T$;

5 Compute the SVD of

$$O\sqrt{\Sigma}^{-1}ON := A\Lambda\Omega;$$

6 Use the columns of $A$, the lines of $\Omega$ and the diagonal of $\Lambda$ to construct the new neurons of Prop. 3.2;

7 else if method = GradMax then

8 $M$ = None;

9 $\Lambda, N$ = MatrixSN($l-1, l+1, M = M$);

10 Compute the SVD of $N^T N$;

11 Use the eigenvectors to define the new out-going weights;

12 Set the new in-going weight to 0;

13 else if method = Random then

14 $\alpha_k, \omega_k \stackrel{n_d}{\sim} N(0, Id)$;

15 end

**Algorithm 3: MatrixSN**

Data: $p_1, p_2$ (layer indexes), $M = \text{None}$

Result: Construct matrices $S$ and $N$

1 Take a minibatch $X$ of size $\propto \frac{(SW)^2}{P}$;

2 Propagate and backpropagate $X$;

3 Compute $V_{goal}$ at $p_2$, i.e. $-\frac{\partial L_{tot}}{\partial A_{p_2}}$;

4 if $M \neq \text{None}$ then

5 $V_{goal} = MB_{p_1}$

6 end

7 $S, N = B_{p_1}B_{p_1}^T, B_{p_1}V_{goal}^T$;

**Algorithm 4: BestUpdate**

Data: $l$, index of a layer

Result: Best update at $l$

1 Take a minibatch $X$ of size $\propto \frac{(SW)^2}{P}$;

2 Compute $(S, N)$ with MatrixSN($l, l$);

3 $M = N^T S^{-1}$;

## E.5 Computational complexity

We estimate here the computational complexity of the above algorithm for architecture growth.

**Theoretical estimate.** We use the following notations:

* number of layers: $L$

* layer width, or number of kernels if convolutions: $W$ (assuming for simplicity that all layers have same width or kernels)

* number of pixels in the image: $P$ ($P = 1$ for fully-connected)

* kernel filter size: $S$ ($S = 1$ if fully-connected)

* minibatch size used for standard gradient descent: $M$

* minibatch size used for new neuron estimation: $M'$

* minibatch size used in the line-search to estimate amplitude factor: $M''$

* number of classical gradients steps performed between 2 addition tentatives: $T$

Complexity, estimated as the number of basic operations, cumulated over all calls of the functions:

* of the standard training part: $TMLSW^2P$

* of the computation of matrices of interest (function MatrixSN): $LM'(SW)^2P$

* of SVD computations (function NewNeurons): $L(SW)^3$

* of line-searches (function AmplitudeFactor): $L^2 M'' SW^2 P$
<figure><img src="image_20.png" /><figcaption>Figure 12: Notation and size for convolutional and linear layers</figcaption></figure>

• of weight updates (function BestUpdate): LSW

The relative added complexity w.r.t. the standard training part is thus:

$$M'S/TM + S^2W/TMP + M''L/TM + 1/WTMP.$$

**SVD cost is negligible.** The relative cost of the SVD w.r.t. the standard training part is $S^2W/TMP$. In the fully-connected network case, $S = 1$, $P = 1$, and the relative cost of the SVD is then $W/TM$. It is then negligible, as layer width $W$ is usually much smaller than $TM$, which is typically $10 \times 100$ for instance. In the convolutional case, $S = 9$ for $3 \times 3$ kernels, and $P \approx 1000$ for CIFAR, $P \approx 100000$ for ImageNet, so the SVD cost is negligible as long as layer width $W \ll 10000$ or $100000$ respectively. So one needs no worrying about SVD cost.

Likewise, the update of existing weights using the “optimal move” (already computed as a by-product) is computationally negligible, and the relative cost of the line searches is limited as long as the network is not extremely deep ($L < TM/M$).

On the opposite, the estimation of the matrices (to which SVD is applied) can be more ressource-demanding. The factor $M'S/TM$ can be large if the minibatch size $M'$ needs to be large for statistical significance reasons. One can show that an upper bound to the value required for $M'$ to ensure estimator precision (see Appendix E.1) is $(SW)^2/P$. In that case, if $W > \sqrt{TMP}/S^3$, these matrix estimations will get costly. In the fully-connected network case, this means $W > \sqrt{TM} \approx 30$ for $T = 10$ and $M = 100$. In the convolutional case, this means $W > \sqrt{TMP}/S^3 \approx 30$ for CIFAR and $\approx 300$ for ImageNet. We are working on finer variance estimation and on other types of estimators to decrease $M'$ and consequently this cost. Actually $(SW)^2/P$ is just an upper bound on the value required for $M'$, which might be much lower, depending on the rank of computed matrices.

**In practice.** In practice the cost of a full training with our architecture growth approach is similar (sometimes a bit faster, sometimes a bit slower) than a standard gradient descent training using the final architecture from scratch. This is great as the right comparison should take into account the number of different architectures to try in the classical neural architecture search approach. Therefore we get layer width hyper-optimization for free.

# F Additional experimental results and remarks

## F.1 ResNet18 on CIFAR-100

**Figures.** In all plots the black line represents the average performance over two independent runs, and the colored regions indicate the confidence interval.

**Technical details of Figures 5 and 8** The experiments were performed on 1 GPU. The optimizer is SGD($lr = 1e-2$) with the starting batch size 32 E.2. At each depth $l$ we set the number $n_l$ of neurons to be
added at this depth 2. These numbers do not depend on the starting architecture and have been chosen such that each depth will reach its final width with the same number of layer extensions. For the initial structure $s = 1/4$, resp. $1/64$, we set the number of layer extensions to 16, resp. 21, such that at depth 2 (named Conv2 in Table 3), $n_2 = (Size_2^{final} - Size_2^{start})/\text{nb of layer extensions} = (64 - 16)/16 = (64 - 1)/21 = 3$. The initial architecture is described in Table 3.

<table><caption>Table 2: Number of neurons to add per layer. The depth is identified by its name on Table 3.</caption><thead><tr><th>depth <i>l</i></th><th>Conv2</th><th>Conv3</th><th>Conv5</th><th>Conv6</th><th>Conv8</th><th>Conv9</th><th>Conv11</th><th>Conv12</th></tr></thead><tbody><tr><th><i>n</i><sub><i>l</i></sub></th><td>3</td><td>3</td><td>6</td><td>6</td><td>12</td><td>12</td><td>24</td><td>24</td></tr></tbody></table>

### F.1.1 Performance for gradient-based methods

We present in Table 5 two indicators of performance on classical visual datasets for four gradient-based methods: DART (Liu et al. (2019)), NORTH Maile et al. (2022), GradMax (Evci et al. (2022)), and TINY. We use the adjective *gradient-based* when the method uses the information from the propagation of the loss to search for an architecture. While GradMax, NORTH, and TINY increase the size of existing architectures (VGG and ResNet), DARTS uses cells to create the architecture, starting from a large graph of cells and removing what is considered unnecessary connections. We make the following remarks for the indicator *Time*, which is the time in GPU days to search for an architecture and train it, and the indicator *Acc.*, which is the accuracy on the test set:

* For NORTH, GradMax, and TINY, the accuracy on the test set is comparable, as all methods share a lot in terms of methodology, growth process, and neuron initialization (cf. B). Nonetheless, NORTH search time complexity is much larger as for each increase of architecture its strategy relies on trial-and-error methodology (going up to 1000 generations before actually increasing the architecture).

* The time search complexity of TINY will always be slightly higher than GradMax as it needs to project the desired update and compute the matrix $\mathbf{S}$ (cf B).

* Although DARTS reaches good performance, its time search complexity is always greater than one GPU as it starts from a large architecture and decreases its size by removing connections between cells. For the ImageNet dataset, the indicator *Time* does not take into account the time spent searching for the basic cells, which are then used to create the graph.
architecture growth TINY

<figure><img src="image_21.png" /><figcaption>Figure 13: Accuracy and number of parameters during architecture growth for methods TINY and GradMax as a function of the gradient step. Mean and standard deviation for four independent runs.</figcaption></figure>
<figure><img src="image_22.png" /><figcaption>Figure 14: Accuracy as a function of the number of epochs during extra training for TINY on four independent runs.</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>Figure 15: Accuracy curves as a function of the number of epochs during extra training for GradMax on four independent runs.</figcaption></figure>
<table><caption>Table 3: Initial and final architecture for the models of Figure 5. Numbers in color indicate where the methods were allowed to add neurons (middle of ResNet blocks). In blue the initial structure for the model 1/64 and in green the initial structure for the model 1/4, i.e., 1|16 indicates that the model 1/64 started with 1 neuron at this layer while the model 1/4 started with 16 neurons at the same layer.</caption><thead><tr><th colspan="4">ResNet18</th></tr><tr><th>Layer name</th><th>Output size</th><th>Initial layers (kernel=(3,3), padd.=1)</th><th>Final layers (end of Fig 5)</th></tr></thead><tbody><tr><td>Conv 1</td><td>32 × 32 × 64</td><td>[3 × 3,]</td><td>[3 × 3, 64]</td></tr><tr><td>Conv 2</td><td>32 × 32 × 64</td><td>3 × 3, 64<br>3 × 3, 1|16</td><td>3 × 3, 64<br>3 × 3, 64</td></tr><tr><td>Conv 3</td><td>32 × 32 × 64</td><td>3 × 3, 64<br>3 × 3, 1|16</td><td>3 × 3, 64<br>3 × 3, 64</td></tr><tr><td>Conv 4</td><td>16 × 16 × 64</td><td>[3 × 3, 128]</td><td>[3 × 3, 128]</td></tr><tr><td>Conv 5</td><td>16 × 16 × 128</td><td>3 × 3, 128<br>3 × 3, 2|32</td><td>3 × 3, 128<br>3 × 3, 128</td></tr><tr><td>Conv 6</td><td>16 × 16 × 128</td><td>3 × 3, 128<br>3 × 3, 2|32</td><td>3 × 3, 128<br>3 × 3, 128</td></tr><tr><td>Conv 7</td><td>8 × 8 × 256</td><td>[3 × 3, 256]</td><td>[3 × 3, 256]</td></tr><tr><td>Conv 8</td><td>8 × 8 × 256</td><td>3 × 3, 256<br>3 × 3, 4|64</td><td>3 × 3, 256<br>3 × 3, 256</td></tr><tr><td>Conv 9</td><td>8 × 8 × 256</td><td>3 × 3, 256<br>3 × 3, 4|64</td><td>3 × 3, 256<br>3 × 3, 256</td></tr><tr><td>Conv 10</td><td>4 × 4 × 512</td><td>[3 × 3, 512]</td><td>[3 × 3, 512]</td></tr><tr><td>Conv 11</td><td>4 × 4 × 512</td><td>3 × 3, 512<br>3 × 3, 8|128</td><td>3 × 3, 512<br>3 × 3, 512</td></tr><tr><td>Conv 12</td><td>4 × 4 × 512</td><td>3 × 3, 512<br>3 × 3, 8|128</td><td>3 × 3, 512<br>3 × 3, 512</td></tr><tr><td>AvgPool2d</td><td>1 × 1 × 512</td><td></td><td></td></tr><tr><td>FC 1</td><td>100</td><td>512 × 100</td><td>512 × 100</td></tr><tr><td>SoftMax</td><td>100</td><td></td><td></td></tr></tbody></table>
<figure><img src="image_24.png" /><figcaption>Figure 16: Accuracy on test split of as a function of the number of parameters during architecture growth from ResNet$_{1/64}$ to ResNet18. The normalization for GradMax is $\sqrt{10^{-3}}$.</figcaption></figure>

<table><caption>Table 4: Final accuracy on test split of ResNet18 of 16 after the 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 = 1$ the method TINY achieves 68.1 ± 0.5 on test split after its growth and it reaches 68.7 ± 0.6$^{5*}$ after $* := 5 \times 50$ epochs.</caption><thead><tr><th></th><th colspan="2">Δt = 1</th><th rowspan="2">Baseline</th></tr><tr><th></th><th>TINY</th><th>GradMax</th></tr></thead><tbody><tr><td>s = 1/64</td><td>68.1 ± 0.5<br>68.7 ± 0.6<sup>5*</sup></td><td>57.2 ± 0.3<br>57.7 ± 0.3<sup>3*</sup></td><td>72.8 ± 0.3<sup>5*</sup></td></tr></tbody></table>

<table><caption>Table 5: *Time*: GPU days spent to search for the architecture and to train it. *Acc.*: accuracy on test set (%). $+$: estimated with our implementation. For the NORTH method, we computed the average performance over their different initializations and strategies based on their Figure 4.</caption><thead><tr><th rowspan="2">Method</th><th colspan="3">Indicators</th><th rowspan="2">Dataset</th></tr><tr><th>Arch.</th><th>Time</th><th>Acc.</th></tr></thead><tbody><tr><td rowspan="2">DARTS</td><td>×</td><td>4</td><td>97.0 ± 0.1</td><td rowspan="2">CIFAR-10</td></tr><tr><td>×</td><td>6.5</td><td>97.8 ± 0.1</td></tr><tr><td rowspan="3">NORTH</td><td>×</td><td>4</td><td>73.3</td><td>ImageNet</td></tr><tr><td>VGG-11</td><td>3.3</td><td>~ 76.4</td><td rowspan="2">CIFAR-10</td></tr><tr><td>ResNet-28</td><td>0.4</td><td>~ 83.3</td></tr><tr><td></td><td>VGG-11</td><td>1.6</td><td>~ 55.7</td><td>CIFAR-100</td></tr><tr><td rowspan="2">GradMax<sup>+</sup></td><td>Δt = 0.25, s = 1/64</td><td>ResNet-18</td><td>0.12</td><td>45.0 ± 0.4</td><td rowspan="4">CIFAR-100</td></tr><tr><td>Δt = 1, s = 1/64</td><td>ResNet-18</td><td>0.26</td><td>56.8 ± 0.2</td></tr><tr><td rowspan="2">TINY<sup>+</sup></td><td>Δt = 0.25, s = 1/64</td><td>ResNet-18</td><td>0.13</td><td>65.8 ± 0.1</td></tr><tr><td>Δt = 0.1, s = 1/64</td><td>ResNet-18</td><td>0.28</td><td>68.1 ± 0.5</td></tr></tbody></table>