Growing Tiny Networks: Spotting Expressivity Bottlenecks and Fixing Them Optimally
Authors: Manon Verbockhaven
Théo Rudkiewicz
Sylvain Chevallier
Guillaume Charpiat
Venue: Accepted by TMLR ()

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

Published in Transactions on Machine Learning Research (June/0024
Growing Tiny Networks: Spotting Expressivity Bottlenecks and Fixing Them Optimally
Manon Verbockhaven, Théo Rudkiewicz, Sylvain Chevallier, Guillaume Charpiat TAU team, LISN, Université Paris-Saclay, CNRS, Inria, 91405, Orsoy, France férs tname. name@inria.fr
Reviewed on OpenReview: https: openreview. net/ farun? id= hb tG6a6e7r
Abstract
Machine learning tasks are generally formulated as optimization problems, where one searches for an optimal function within certain functional space. In practice, parame- terized functional spaces are considered, in order to be able to perform gradient descent. Typically, a neural network architecture is chosen and fixed, and its parameters (connection weights) are optimized, yielding an architecture-dependett result. This way of proceeding however forces the evolution of the function during training to lie within the realm of what expressible with the chosen architecture, and prevents any optimization across architec- tures. Costly architectural hyper-paramcter optimization is often performed to compensate for this. Instead, we propose to adapt the architecture the fly during training, We show that the information about desirable architectural changes, due to expressivity bottlenecks when attempting to follow the functional gradient, can be extracted from backpropagation. To do this, we propose a mathematical definition of expressivity bottlenceks, which enables us to detect, quantify and solve them while training, by adding suitable neurons. Thus, while the standard approach requires large networks, in terms of number of neurons per layer, for expressivity and optimization reasons, we provide tools and properties develop an architecture starting with very small number of neurons. As proof of concept, we show results on the CIFAR dataset, matching large neural network accuracy, with competitive training time, while removing the need for standard architectural hyper-parameter search.
1 Introduction
Issues with the fixed-architecture paradigm. Universal approximation theorems such as (Hornik et al. 1989 Cybenko. 1989) are historically among the first theoretical results obtained on neural networks, stating the family of neural networks with arbitrary width as a good candidate for a parameterized space of functions to be used in machine learning. However the current common practice in neural network training consists in choosing fixed architecture, and training it, without any possible architecture modification meanwhile. This inconveniently prevents the direct application of these universal approximation theorems, as expressivity bottlenecks that might arise in a given layer during training will not be able to be fixed. There are two approaches to circumvent this in daily practice. Either one chooses a (very) large width, to be sure to avoid expressivity and optimization issues (Hanin & Rolnick 2019b) Raghu et al., 2017), to the cost of extra computational power consumption for training and applying such big models; to mitigate this cost, model often used afterwards, using pruning, tensor factorization, quantization (Louizos
reduction techniques et al. 2017) or distillation (Hinton et al., 2015). Or one tries different architectures and keeps the most suitable one (in terms of performancc-size compromise for instance), which multiplics the computational burden by the number of (rials. This latter approach relates to the unto-DeepLearning field (Liu el al., 2020), where different exploration strategies over the space of architecture hyper- parameters (among other ones) have been tested, including reinforcement learning (Baker et al. 2017 Zoph Lo] 2016)) Bayesian optimization techniques (Mendoza et al.) (0166), and evolutionary approaches (Miller al. 1989: Stanley let al. 2009. Miikkulainen al.] 2017 Bennet et al. 2021 that all rely random tries and consequently

---

Published in Transactions on Machine Learning Research (June/ 22044)
take time for exploration. Within that line, Net2Net (Chen et al., 2015), AdaptNet (Yang et al. 2018 and MorphNet (Gordon et al.) 2018) propose different strategies to explore possible variations of given architecture, possibly guided by model size constraints. Instead, we aim at providing a way to locate precisely expressivity bottlenecks in a trained network, which might speed up neural architecture search significantly. Moreover, based on such observations, we aim at modifying the architecture on the fly during training, in a single run (no re-training), using first-order derivatives only, while avoiding neuron rodundancy. Relatod work on architecture adaptation while training includes probabilistic edges (Liu et al., 2019) or sparsifying priors (Wolinski et al.) 2020). Yet the training is done on the largest architecture allowed, which is resource- consuming. On the opposite we aim at starting from the simplest architecture possible.
Optimization properties. An important reason for common practice to choose wide architectures is the associated optimization properties: sufficiently larger networks are proved thcorctically and shown empiri- cally to be better optimized than small ones (Jacot et al., 2018). Typically, small networks exhibit issues with spurious local minima, while wide ones find good nearly-global minima. One of our goals is to train small networks without suffering from such optimization difficulties.
Neural architecture growth. A related line of work consists in growing networks neuron by neuron, by iteratively estimating the best possible neurons to add, according to a certain criterion. For instance, approaches such as (Wu et al. 2019) or Firefly (Wu et al.) 2020) aim at escaping local minima by adding neurons that minimize the loss under neighborhood constraints. These neurons are found by gradient descent or by solving quadratic problems involving second-order derivatives. Other approaches (Causse et al.) 2019 Bashtova et al., 2022), including GradMax (Evci et al. 2022), seek to minimize the loss as fast as possible and involve another quadratic problem. However the neurons added by these approaches are possibly redundant with existing neurons, especially if one does not wait for training convergence to local minimum (which is time consuming) before adding neurons, therefore producing larger-Uhan-needeed architectures.
Redundancy. To our knowledge, the only approach tackling redundancy in neural architecture growth adds random ncurons that are orthogonal in some sense to the ones already present (Maile et al., 2022
More precisely, the new neurons are picked within the kernel (preimage of {0}) of an application describing already existing neurons. Two such applications are proposed, respectively the matrix of fan-in weights and the pre-activation matrix, yielding two different notions of orthogonality. The latter formulation is close to the one of GradMax, in that both study first-order loss variations and use the same pre-activation matrix, with an important difference though: GradMax optimally decreases the loss without caring about redundancy, while the other one avoids redundancy but picks random directions instead of optimal ones. In this paper we bridge the gap between these two approaches, picking optimal directions that avoid redundancy in the pre-activation space.
Notions of expressivity. Several concepts of expressivity or complexity exist in the Machine Learning literature, ranging from Vapnik-Chervoneni" complexity (Koltchinskii 2001) to the number of pieces in piecewise alfine function (as networks with ReLU activations are) (Serra et al. 2018 Hanin & Rolnick 2019a]. Bottlenecks have been also studied from the point of view of Information Theory through mutual information between the activities of different layers (Tihhyy & Zaslavsky| 2015 Dai et al. 2018); this quantity is difficult to estimate though. Also relevant and from Information Theory, the Minimum Description Length paradigm (Rissanen 1978 Grünwald & Roos,
dimension (Vapnik & Chervonenkis 1971] and Rademacher
2019) and Kolmogorov complexity (Kolmogorov 1965 Li et al.. 2008) enable to define trade-offs between
performance and model complexity.
In this article, we aim at measuring lacks of expressivity as the difference between what the backpropagation asks for and what can be done by a small parameter update (such as gradient step), that is, between the desired variation for each activation in each layer (for each sample) and the best one that can be realized by a parameter update. Intuitively, differences arise when a layer does not have sufficient expressive power to realize the desired variation. Our main contributions are that we:
adopt a functional analysis perspective on gradient descent in neural networks, advocating to follow the functional gradient. We not only optimize the weights of the current architecture but also
2

---

Published in Transactions on Machine Learning Research (June/ (2044)
dynamically adjust the architecture itself to progress towards suitable parameterized functional space. This approach mitigates optimization challenges like local minima that are due to thin architectures;
properly define and quantify the concept of expressivity bottlenecks, both globally at the neural network output and locally at individual layers, in computationally accessible manner. This methodology enables to localize expressivity bottlenecks within neural network;
formally define a quadratic problem the best possible neurons to add to given layer to decrease lacks of expressivity solve it and compute the associated expressivity gain;
use a naive strategy on the basis of our approach to expand a neural network while maintaining competitive computational complexity and performance compared large and well-known model or other NAS search methods.
2 Main concepts
2.1 Notations
Let F be a functional space, e.g. L2(R + Rd), and a loss function L F RR+ defined on it, the form L(f) E( [(f(z)) v) where the per-sample loss, assumed be differentiable, and where D is the sample distribution, from which the dataset ((11,1)),..... (NN, UN)) is sampled, with æ, Rp and y: Rdd.
For the sake of simplicity we consider feedforward neural network fo R² + R2 with L hidden layers, each of which consisting of an affine layer with weights W; followed by a differentiable activation function or which satisfics (0) = O. The network parameters are then = (Wi)l=1.... The network iteratively computes:
b
(1)
x
01
bu(x))
0
ar(w)
Wi bibi1((2)
E []
ba(r)) (1((a((0))
W
1
fo(æ)) = (a(a)()))
Figure Notations
To any vector-valued function noted t(x) and any batch of inputs X == [EI, ... ænJ, we associate the concatenated matrix T(X) == (t(æ1) t(æx)) e Rlo))x. The matrices of pre-activation and post- activation activities at layer over minibatch X are thus respectively. A((X) (ai(x1) ai(z,)) and Bi X)= (br(wr) br(x))).
NB: convolutions also be considered, with appropriate representations (ef matria (f(x)) in C.1
2.2 Approach
Functional gradient descent. We take functional perspective on the use of neural networks. Idcally in machine learning task, one would search for a function f R2 Rd that minimizes the loss L by gradient descent: 8f [f)(() for some metric on the functional space F (typically, T2( - Rd)), where Vy denotes the functional gradient and denotes the evolution time of the gradient descent. The descent direction Ugoal = - L(f( is function of the same type as f and whose value at x is easily computable as Ugoal (2) - (V,(()) (x) = V,,(u,, y(x)) (=)(() (see Appendix A.1 for more details). This direction Ugoal is the best infinitesimal variation in to add to the output (u = f(x) to decrease the loss L, regardless of the parametrization of
3

---

Published in Transactions on Machine Learning Research (June/ 22044)
Parametric gradient descent reminder. However in practice, to represent functions and to compute gradients, the infiite-ddmmnsiionel functional space F has to be replaced with a finite-dimensioned parametric space of functions, which is usually done by choosing particular neural network architecture A with weights E A4- The associated parametric search space FA then consists of all possible functions fo that can be represented with such nelwork for any parameter value 0. Under standard weak assumptions (see Appendix
A.2 the gradient descent of the form:
00
= VoL(ff) = E
Vol(fo(x),
(1)
(œ.
Using the chain rule (on 2/e then on Vol(Jo(a)) y)), these parameter updates yield a functional evolution: oi
VGD == Ofa
0.
00
f
Ofe T 0e
=
E (m.
(x) Ugoal (z))
(2)
Ot
00
Ot
09
which significantly differs from the original functional gradient descent. We will aim to augment the neural network architecture that the parametric gradient descent can get closer to the functional one.
Optimal move direction. We name T(" or just TA, the langent space of JA at Ja, that is, the set of all possible infinitesimal variations around so under small parameter variations:
expressivity bottleneck
gool
T 00
0fe 60 00
80 E ox
Ta
Projyz Projiallannd (goat)
This linear functiona(] space is first-order approxima- tion of the neighborhood of fo within Fx. The direction UGD obtained above by gradient descent is actually not the best one to consider within TA- Indeed, the best move would be the orthogonal projection of the desired di- rection ggoal == 5 ((fo) onto T4. This projection what (generalization of the notion of) natural gradient would compute (Ollivier 2017
FA
Figure 2: Expressivity bottleneck
Indeed, the parameter variation 50" associated to the functional variation xz a 50" is the gradi- de
ent [(fo of L o fo w.r.t. parameters A when considering the Lg metric on functional variations de 50 (0))),(T>); not to be confused with the usual gradient VoL(fo), based on the L2 metric on parame- ter variations ( This can be seen in proximal formulation as:
0" arg min |/u
Ugoal 1 = arg min
+ +
(3)
TETa
vETa
where is the directional derivative (see details Appendix
A.3
or equivalently as:
Ofo 00
Ofo
50 [|] =: -VTA 00
80* = arg min
60 Ugoal
arg min 60E@A
DoC(fo)(80) +
Lack of expressivity. When Ogaa does not belong the reachable subspace TA there a lack of expressivity, that is, the parametric space A is not rich enough to follow the ideal functional gradient descent. This happens frequently with small neural networks (see Appendix A.4 for an example). The expressivity bottleneck is then quantified as the distance ||00 Ugoall between the functional gradient &gaal and the optimal functional move 8* given the architecture A (in the sense of Eq.
0le 00
Rd
8fa(2)

---

Published in Transactions on Machine Learning Research (June/ /2044)
2.3 Generalizing to all layers
Ideal updates. The same reasoning can be applied to the pre-activations de at each layer 1, seen functions a; : x E Rº + ar(x) E E defined over the input space of the neural network. The optimal parameter update for given layer 1 then follows the projection of the desired update- ((o) of the pre-activation functions a₁ onto the linear subspace T of pre-activation variations that are possible with the architecture, as we will detail now.
Given sample (æ. y) (Var (x) - Vul (o ((fo())) y) with respect to the pre-activations u a (x) of each layer. This is usually performed in order to compute the gradients w.r.t. model parameters Wi, as (w:((G((2r,,)) = (a;(m)
D, standard backpropagation already iteratively computes ga)) :=
... (u))), ())=))()))> which is the derivative of the loss
aw, (a,((f((z),))
(x) (Va, (fo)) (x) indicates the direction in which would like to change the layer pre- activations (x)x) in order to decrease the loss at point However, given minibatch of points (æ;), most of the time no paramcter move 50 is able to induce this progression for cach z; simultancously, because the 0-parameterized lamily of functions aj is not expressive enough.
Activity update resulting from a parameter change. Given a subset of parameters Ô (such as the ones specific to a layer: 0 Wi), and an incremental direction 60 update these parameters (e.g. the one resulting from a gradient descent: 80 Σ (an Emiinibattt Vgl(fo(az), y) ), the impact of the parameter update 760
the pre-activations a₁ layer at order 1 in 7, where y an amplitude factor, as v' v'(z, (2,) = y (a)(2)) 80. The factor is the analogue of the learning rate and is considered to be small.
80
3 Expressivity bottlenecks
We now quantify expressivity bottlenecks at any layer as the distance between the desired activity update u (ooa)( and the best realizable one v' (.) (cf. Figure 2
Definition 3.1 (Lack of expressivity). For a neural network fo and a minibatch of points X ((r,,))) we define. the lack of expressivity at layer as how far the desired activity update Vi (w (0)o(((1)) v) 22))( from the closest possible activity update V = (x1( o'(2)),.... realiz- able by parameter change 50:
v
min
1 Σ (l(())))
ol ogu (2:)]l (gom(())))
min 1 |I =
Vilal [I)
(4)
wl w'ETA
where ||-II stands for the L2 norm, 11-I/ry for the Frobenius norm, and ()(X500) is the activity update resulting from parameter change d0 as defined in previous section. In the two following parts we the minibatch X and simplify notations accordingly by removing the dependency on X. Proofs of this section are deferred to Appendix
3.1 Best move without modifying the architecture of the network
Let SW; be the solution of Equation when the parameter variation d0 restricted to involve only layer parameters, i.e. Wi. This move is sub-optimal in that does not result from an update of all architecture parameters but only of the current layer ones. In this case the activity update simplifies v'(W)) = 8W, B and the problem becomes:
SW. = arg min 1 [I - 11
(5)
sw
Proposition 3.1. The solution of Problem equation denotes the pseudoincerse of matrix P.
is: SW.
Vi B B )+ where P+ yool
B(_,)
This update oW? is not equivalent to the usual gradient descent update, whose form is dW & Vi B In fact the associated activity variation, SW, B is the projection of Vt the post-activation matrix
5

---

Published in Transactions on Machine Learning Research (June/2024)
6
T a bz)
dat 2
+
(1-(
af(a)
(22 bz-1(1)
output from the init structure
output from the added structure
added structure
init structure
Figure 3: Adding one neuron to layer cyan (K 1), with connections in cyan. Here, RER and E
Figure 4: Sum of functional moves
of layer / - 1, that is to say onto the span of all possible post-activation directions, through the projector 1 B B:- Bi-1. To increase expressivity if needed, will aim at increasing this span with the most useful directions to close the gap between this best update and the desired one. Note that the update ow consists of standard gradient (V B followed by a change of metric in the pre-activation space as an application of ( B[ a structure which is reminiscent of the natural gradient.
3.2 Reducing expressivity bottleneck by modifying the architecture
To get as close possible to goal and to increase the expressive power of the current neural network, we modify each layer of its structure. At layer I 1-1, we add neurons fi,-., with input weights
a1...., Og and output weights Wi,..., WK (ef. Figure 3 We have the following expansions by concatenation: ag) and W, < (Wi W1 + f 0K where @ is the concatenation sign and 8K == (a), are the K added neurons.
W (W Q1
wK). We note this architecture modification
The added neurons could be chosen randomly, as in usual neural network initialization, but this would not yield any guarantee regarding the impact on the system loss. Another possibility would be set either input weights (a or output weights (wx) to O, that the function fo(-) would not be modified, while its gradient w.r.t. 0 would be enriched from the new parameters. Another option is to solve optimization problem as in the previous section with the modified structure + 0 a o and jointly search for both the optimal new parameters 0K and the optimal variation oW of the old ones:
arg min
V'W @ BB)
V 11
(6)
@k 5W
As shown Figure 4 the displacement V at layer is actually a sum of the moves induced by the neurons already present (8W) and by the added neurons (0K). Our problem rewrites as
arg min 1 || v'(WW) -vl qoalllet 6w n
with 0z(2 = ΣK We (b--(xx)Tar ax)) (see A.5 We choose ow as the best move of already-existing
parameters as defined in Proposition 3.1 and we note solution (<*KK*) of the optimization problem:
Vi
Vi
goal V'(W*). We are looking for the
goalpras
1 ('
arg min K, ok
goal proy
(8)
One should note that Problems This quadratic optimization problem be solved thanks to the low-rank matrix approximation theorem
7 and B are generally not equivalent, though similar (cf. C.4

---

Published in Transactions on Machine Learning Research (uune/222/)
and S = 1. B As S is positive [Eckart & Young. 1936), using matrices N := B goal praj)
r
semi-definite, let its SVD be S OΣσ", and define S OVE 0"" with the convention that the inverse of 0 cigenvalues is O. Finally, consider the SVD of matrix S N Ek= Aaans where R is the rank of the matrix 5 N. Then:
Proposition 3.2. The solution of Problem is:
optimal number of neurons: K* R
their optimal weights: OK = ( w (VA.S-bus Suz V K
Moreover for any number of neurons K & R, and associated optimal weights 0%*² consisting of the first K neurons of 0% the expressivity goin can be quantified very simply as function of the singular values 2
T 00p K.
V//
(9)
where W' is the expressivity bottleneck (defined in Eq. For convolutional layers instead of callecconnetted ones, Equation
g becomes an inequality (E).
In practice before adding new neurons w), multiply them by amplitude factor y found by simple line search (see Appendix E.3), i.e. we add (v7a, vww. The addition of each neuron & has an impact on the bottleneck of the order of 7 provided is small. We observe the same phenomenon with the loss stated in the next proposition:
Proposition 3.3. For 7 > 0, solving (8) using ygoolproj = - is equivalent to minimizing the loss L at order in vV. Furthermore, performing an architecture update with yoW and neuron addition with y0K 3.2) has on impact on the loss at first order in as
[( [(Saaro%
{Soorr (x.)) = L(fo) - (0)-10))A + Aow.) + +(7))
(10)
n2
with
A Agg=
1 ( vi goalpros v'(OR())
Σ
x
(11)
km
1 Asw- = (Vylas v'(ow")) > 0.
(12)
The ds could be used in a selection criterion realizing a trade-off with computational complexity. A selec- tion based on statistical significance of singular values can also be performed. The full algorithm and its complexity are detailed in Appendices E.4 and E.5 We finish this section by some additional propositions and remarks.
Proposition 3.4. IfS S is positive definite, then solving is equivalent to laking we Nox and finding the K first eigenveclors Os associaled to the K largest eigenvalues X of the generulized eigenvalue problem: NN ag S
Corollary 1. For all integers m, m,m' m' such that m + m' R, at order one in V, adding m + m' neurons simaltancously according to the previous method is equivalent to adding m neurons then m' newrons by applying successively the previous method twice.
One should also note that the family ((t.)((K of pre-activity variations induced by adding the neurons gk. is orthogonal for the trace scalar product. We could say that the added neurons are orthogonal each other (and the already-present ones) in that sense. Interestingly, the GradMax method (Evci et al. 2 also aims at minimizing the loss 10 but without avoiding redundancy (see Appendix B.1 for more details).

---

Published in Transactions on Machine Learning Research (June/2024
4 About greedy growth sufficiency and TINY convergence
One might wonder whether greedy approach on layer growth might get stuck in non-optimal state. By greedy we mean that every neuron added has to decrease the loss. Since in this work we add neurons layer per layer independently, we study here the case 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 Σ fx))]
(13)
MED
where [(x) is the output of the neural network and D is the training set. Proofs and supplementary propositions are deferred to Appendix [ in particular D.4 and [.7]
First, if one allows only adding neurons but modification of already existing ones:
Proposition 4.1 (Exponential convergence to 0 training crror by ReLU neuron additions). It is possible to decrease the loss exponentially fast with the number L of added neurons, i.e. as I(),,, lowards 0 training loss, and this in a greedy way, that is, such that each added neuron decreases the loss. The factor 7 is dm
2 ? = d das where dm and das are quantities solely dependent on the dataset geometry, d' is the output dimension of the network, and n is the dataset size.
In particular, there exists no situation where one would need to add many neurons simultaneously to decrease the loss: it is always feasible with a single ncuron.
TINY might get stuck when no correlation between inputs x; and desired output variations f'(z,) f(x;) can be found anymore. To prevent this, one can choose an auxiliary method to add neurons in such cases, for instance random neurons (with line search over their amplitude, cf. Appendix D.3), locally-optimal neurons found by gradient descent, or solutions of higher-order expressivily bot tleneck formulations using further developments of the activation function. We will name completed Y TINY the completion of TINY by any such auxiliary method.
Now, if we also update already existing weights when adding new neurons, we get a stronger result:
Proposition 4.2 (Completed-TINY reaches training error in at most n neuron additions). Under cerlain assumptions (full batch optimization, updating already eristing parameters, and, more technically; polynomial activation function of order 2 n²), completed-TTl. TINY reaches training ervor in at most neuron additions almost surely.
Hence we see the importance of updating existing parameters on the convergence speed. This optimization protocol is actually the one we follow in practice when training neural networks with TINY (except when comparing with other methods using their protocol).
Note that our approach shares similarity with gradient boosting Friedman 2001 somehow, as we grow the architecture basod on the gradient of the loss. Note also that finding the optimal ncuron to add actually NP-hard (Bach 2017), but that we do not need new neuron optimality to converge to 0 training error.
5 Results
5.1
Comparison with GradMax on CIFAR-100
The closest growing method to TINY is GradMax (Evci et al. (2022) ), it solves quadratic problem similar to By construction, the objective of GradMax is to decrease the loss as fast as possible considering an infinitesimal increment of new neurons. The main difference is that GradMax does not take into account the expressivity of the current architecture as TINY does in S by projecting Ugoal- In-depth details about the difference between the GradMax and TINY are provided in Appendix B.1
In this section, we show on the CIFAR-100 dataset that solving 88] instead of 23 (defined by GradMax) to grow network using a naive strategy allows better final performance and almost full expressive power.
8

---

Published in Transactions on Machine Learning Research (June/202)
starting architecture
starting architecture 1/64
0.8
0.8
TIYY
GradMax
0.7
At 0.25 epoch
Accuracy test
0.4
0.4
0.3
0.3
0.2
0.4
0.6
0.8
1.0
122
0.2
0.4
0.6
0.8
1.0
1.2
0.7
0.7
At 1 epoch
Accuracy test
0.6
0.6
0.5
0.5
0.-
0.1
0.1
0.0
1.0
0.2
0.6
1.0
nbr parameters
1e7
nbr parameters
1e7
Figure 5: Test accuracy as function of the number of parameters during architecture growth from ResNet, to ResNet18. The starting architecture in the left (resp. right) column is ResNet1/1 (resp. ResNet 1/61). The amount of training time At between consccutive neuron additions in the upper (resp. lower) row is 0.25 (resp. 1) epoch. Statisties over 4 runs are performed for each setting.
To do so, we have re-implemented the GradMax method and mimicked its growing process which consists in increasing the architecture of thin ResNet18 until reaches the architecture of the usual ResNet18. This process is described in the pseudo code where two parameters of the starting architecture, w.r.t. the usual ResNet18 architecturr (s 1/4 or 1/64, cf. Table 3 and the amount of training time between consecutive neuron additions (At = 1 or At = 0.25 epochs). Then the number of parameters and the performance of the growing network are evaluated at regular intervals to plot Figure 5) We note that both methods reach their final accuracy within less than one GPU day, outperforming by far other NAS search methods their category (ef. Table 5
be chosen the relative thinness
Once the models have reached the final architecture ResNet18, they are trained for 250 more epochs (or 500 epochs if they have not converged yet) on the training set. We have summarized the final performance in Table 1 We also added the column Reference, which gives the performance of a ResNet18 trained from scratch by usual gradient descent with all its neurons. We do not expect TINY or GradMax to achieve the performance of the reference as its architecture and optimisation process have been optimised for years. The column Small references corresponds to the training of the architecture ResNet18, for s = 1/4 and = 1/64 using standard gradient descent without any increase architecture.
The details of the protocol can be found in the annexes dynamic of the training batch size E.2 the normalization of the neurons E.3 the number of examples used to estimate and solve the expressivity bottleneck E. and the complexity of the algorithms E.5 For both
as well as other technical details such as the
methods, all the latter apply so that the main differences between GradMax and TINY in this experiment is the mathematical definition of the new neurons.
For 1/64, we observe a significant difference in performance between TINY and GradMax mothods. While TINY models almost achieve the reference's performance, GradMax remains stuck 10 points below. This suggests that the framework proposed by GradMax not sufficient to be able to start with an archi-
9

---

Published in Transactions on Machine Learning Research (June/ (2044)
starting architecture 1/64
=t 1
TINY
1e7
GradMax
1e7
1.0
1.0
train
1.2
train test
12
test
0.8
1.0 0.8
1.0
nor parameter
Accuracy
0.8
0.6
0.6
0.4
0.4
0.2
0.2
nbr parameters
nbr_ parrmmterrrss
0.0
0.0
20000 30000 40000 50000
10000 20000 30000 40000 50000
gradient steps
gradient steps
Figure 6: Evolution of accuracy and number parameters as a function of gradient steps for the setting
At 1, s 1/64, for TINY and GradMax. Mean and standard deviations are estimated over four runs. Results with other settings can be found in Fig. 13 in the appendix.
Starting architecture 1/64
TINY
At = 1
GradMax
1.0
0.9
Accuracy
0.8
0.8
0.7
0.7
train
test
0
50
100
150
200
250
0
100
200
300
400
500
epochs
epachs
Figure 7: Evolution of accuracy as a function of epochs for the setting A/ = s 1/64 during extra training for TINY and GradMax. Mean and standard deviations are estimated over four runs. Results with other settings can be found in Figures and in the appendix.
10

---

Published in Transactions on Machine Learning Research (June/ /2024)
TINY
GradMax
Small references
Refe-
A
0.25
1
0.25
1
rence
1/4
67.2 +: 0.1
70.4 + 0.2
65.1 + 0.2
68.6 + 0.1
68.6 0.4 5+
72.8
1/4
70.3 = 0.2 5+
70.9 = 0.2 5+
67.0 = 0.2 5+
69.0 = 0.2 5
+
1/64
65.8 + 0.1
68.1 + 0.5
45.0 + 0.4
56.8 + 0.2
63.4 0.3 5+
0.3 5+
1/64
69.5 + 0.2 5x
68.7 + 0.6 S*
57.0 + 0.4 10x
58.4 + 0.2 10+
Table 1: Final accuracy on test set of ResNet18 after architecture growth (grey) and after convergence (blue). The number of stars indicates the multiple of 50 epochs needed to achieve convergence. With the starting architecture ResNet,yed and At = 0.25, the method TINY achieves 65.8 4 0.1 on test set after its growth and it reaches 69.5 5 0.2 ** *ffter 5* == x 50 additional epochs (examples of training curves for the extra training can be found in Figure 14h. Means and standard deviations are performed on 4 runs for each setting.
tecture far from full expressivity, i.e. ResNet1/64 /644 while TINY is able to handle it. As for the setting = 1/4, both methods seem equivalent in terms of final performance and achieve full expressivity.
The curves on Figure G which are extracted from Figure 13 in the appendix, show that TINY models have converged the end of the growing process, while GradMax ones have not. This latter effect contrasts with GradMax formulation which is to accelerate the gradient descent as fast as possible by adding neurons. Furthermore GradMax needs extra training to achieve full expressivily: for the particular setting 8 /64, A = 1, the extra training time required by GradMax is twice as high as TINY's, as shown in Figure 7 This need for extra training also appears for all settings in Table [ In particular for = 1/64, At = 0.25, the difference in performance after and before extra training goes up to 20 % above the initial performance while only of 6% for TINY.
5.2 Comparison with Random on CIFAR-100 initialisation impact
In this section, we focus on the impact of the new neurons' initialization. To do so, we consider as a baseline the Random method, which initializes the new neurons according to a Gaussian distribution: (at, = No Ia) or uniform distribution 1]] Also, when adding new neurons, we now search for the best scaling using a line-search on the loss. Thus, we perform the operation 0K +- -- with the amplitude factor y IR defined as:
arg min EeSoorrog (2.)). y:)
with 70 (y y
(14)
with positive constant. More details can be found in Appendix F.3.2 and in Algorithm T With such an amplitude factor, one can measure the quality of the directions generated by TINY and Random by quantifying the maximal decrease of loss in these directions.
To better measure the impact of the initialisation method, and to distinguish it from the optimization process, we do not perform any gradient descent. This contrasts with the previous section where long training time after architecture growth was modifying the direction of the added neurons, dampening initialization impact with training time, especially as they were added with a small amplitude factor (ef Section F.3.1
With these two modifications to the protocol of previous section, we obtain Figure S We see the crucial impact of TINY initialization compared to the Random one. Indeed, TINY reaches more than 17% accuracy just by adding neurons (without any further update), which accounts for about one quarter of the total accuracy with the full method (69% in Table [ using in plus gradient descent). On the opposite, the Random initialization does not contribute to the accuracy through the growing process (just about 1%); this can be explained and quantified as follows. To study the random setting, we can model v(X) and Ugoal (X) as independent variables where Ugoal ~ A (0., 1 (Ta) and e either -V (0a, dTa) or Ul uI 2. ål. d being the dimension of Ugoal and v. From Equation (10). the scalar product (V(X). Voaa). := 1 E, (2,) Te)))) (xx;) is proxy for the expected decrease of loss alter each architecture growth. This quantity can be approximated
11

---

Published in Transactions on Machine Learning Research (June/ /2044)
starting architecture 1/64
TINY
Unifarm
0.1
=t epoch
Accuracy test
0.00
0.2
nbr parameters
167
Figure 8: Test accuracy a function of the number of parameters during pure architecture growth (no gradient steps performed, only neuron addition with given initialization) from ResNet1/64 to ResNet18: averaged over four independent runs.
by its standard deviation, ie Vnd' which makes the expected relative gain of loss (for gradient step) of the order magnitude of 1 for the first layer and V512 for the last layer when compared to the true gradient, and consequently when compared to TINY. Furthermore, one can take into account the effect of a line scarch over the random direction: in that case the expected relative loss gain is quadratic in the angle between the directions and therefore of the order of magnitude of 1 or 512 respectively (see Appendix D.3.
v6i
64
Note that the scarch interval of Equation 14] can be shrunk [0, L] with TINY initialization, as the first order development of the loss in Equation 10 is positive. This properly is the direct consequence of the definition of V the minimizer of the expressivity bottleneck (Eq. (8)) One also note that do not include GradMax in Figure g because its protocol initializes the on-going weights to zero (at 0) and imposes small norm on its out-going weights (||w|] = E). Those two aspects make the amplitude factor y meaningless less and the impact of the new neurons initialization invisible without gradient descent.
The code is available at http://ggttta....iii...../t/eeee
6 Conclusion
We provided the thcoretical principles of TINY, a method to grow the architecture a neural net while training it; starting from very thin architecture, TINY adds neurons where needed and yields fully trained architecture the end. Our method relics on the functional gradient to find new directions that tackle the expressivity bottleneck, even for small networks, by expanding their space of parameters. This way, combine in the same framework gradient descent and neural architecture search, that is, optimizing the network parameters and its architecture at the same time, and this, in way that guarantees convergence to training error, thus escaping expressivity bottlenecks indeed.
While transfer learning works well on ordinary tasks, for it to succeed, it needs to fine-tune and use large architectures deployment in order extract and manipulate common knowledge. Our method has the advantage of being generic and could also produce smaller models as it adapts the architecture a single task.
12

---

Published in Transactions on Machine Learning Research (June/ /2044)
It is already instantiated for linear and convolutional layers extension to self-attention mechanisms (trans- formers) is part of future works. Although common architectures consist of succession of layers, research direction is to develop tools handling general computational graphs (such as U-net, Inception, Dense-Net), which offers the possibility to let the architecture graph grow and bypass manual design.
Another possible development would be to study the statistical reliability of the TINY method, for instance using tools borrowed from random matrix theory, Indeed statistical tests can be applied the intermediate computations from which the new neurons obtained. An intercsting byproduct of this approach would be to define threshold to select neurons found by Prop. 3.2 based on statistical significance.
7 Acknowledgments
The authors address their deepest thanks to Stella Douka, Andrei Pantea, Stéphane Rivaud & François Landes for the exchanges and discussions on this project.
This work was supported by grants ALNR-22-CE33-0015 Sylvain Chevallier and by ANR-20-CF:2330022 operated by Inria to Guillaume Charpiat. This work was also funded by the European Union under GA no. 101135782 (MANOLO project).
and ANR-17-CONV-OON operated by LISN to
Numerical computation
enabled by the scientific Python ecosystem: Matplotlib Hunter 2007
Numpy Harris et al. (2020). Scipy Virtanen et al. 2020 pandas pandas development team 2020 Py-
Torch Paszke et al. (2019)
References
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, :8(1):629 681, 2017.
Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar. Designing neural network archilectures using reinforcement learning. In International Conference on Learning Representations, 2017. URL https:
Kateryna Bashtova, Mathieu Causse, Cameron James, Florent Masmoudi, Mohamed Masmoudi, Houcine Turki, and Joshua Wolff. Application of the topological gradient to parsimonious neural networks. In Compulational Sciences and Artificial Intelligence in Industry, pp. 47 61. Springer, 2022.
Pauline Bennet, Carola Doerr, Antoine Moreau, Jeremy Rapin, Fabien Teytaud, and Olivier Teytaud. Nev- ergrad: black-box optimization platform. ACM SIGEVOlution, 14(1):8-13 2021.
Mathicu Causse, Cameron James, Mohamed Slim Masmoudi, and Houcine Turki. Parsimonious neural networks. In Cesar Conference, 2019. BRLLhttp:://www www.weeeaarcooereneee.e. http://rw..cceeee.e.oooooooo/ona
2019/10/s5_p1_211 2330. pdf
Tianqi Chen, Ian Goodfellow, and Jonathon Shlens. Net2net: Accelerating learning via knowledge transfer. arXiv preprint 1rxi::511.00644 2015.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathemalics of control, signals and systems, 2(4):303 014430331,,,0 1989.
Bin Dai, Chen Zhu, Baining Guo, and David Wipf. Compressing neural networks using the variational information bottleneck. In International Conference Machine Learning, pp. 1135-1144 PMLR, 2018.
Carl Eekart and Gale Young. The approximation of one matrix by another of lower rank. Psychometriku. 1(3):211 218, September 1936. ISSN 1860-0980. doi: 10.1007/1BF02288366 URL https://doi.org: 1007/BF02288367
Utku Evci, Bart van Merrienboer, Thomas Unterthiner, Fabian Podregosa, and Max Vladymyrov. Gradmax: Growing neural networks using gradient information. In International Conference on Learning Represen- lalions, 2022. URL httpps://peereevier.. wttp://wwwweeeeeeeeoooeeo//aaaae wwUD
13

---

Published in Transactions on Machine Learning Research (June/ (2044)
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Training pruned neural networks. CoRR, abs/1803.03635, 2018. URL http://arxxv..or//bbb///// 03635
Jerome H Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics, pp- 1189 1232, 2001.
Ariel Gordon, Elad Eban, Ofir Nachum, Bo Chen, Hao Wu, Tien-Ju Yang, and Edward Choi. Morphnet: Fast & simple ressurce-consttaiined structure learning of deep ner In Proceedings of the IEEE conference computer vision and pottern recognition, pp. 1586-1595, 2018.
Peter Grünwald and Teemu Roos. Minimum description length revisited. International Journal of Math- ematics for Industry, 11901):193001,, 2019. doi: 10.1442/52661333221330000 URL https://doi.oon org/ 10. 00.112//226133221900010
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In Kamalika Chaudhuri and Ruslan Salakhutdinor (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2696-2604. PMLR, 09-15 Jun 2019a. URL https://proceeddnggs mlr. ppress/v9//hanin1S00 html
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few aclivation patterns. In H. Wallach, H. Tarochelle, A. Beygelzimer, F. d' d'Alch-BBuc, E. Fox, and R. Garnett (eds.), Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019b. URL https: Paper.aprpppppp pdf
/pproceeding..ennte www.sss.erriip.coooeoooooo http://www........ooooooooooaaaa
C.R. Harris, K.J. Millman, S.J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, J. Taylor, S. Berg, N.J. Smith, R. Kern, M. Picus, S. Hoyer, M.H. van Kerkwijk, M. Brett, A. Haldane, J. Fernández del Río, M. Wiebe, P. Peterson, P. G' D'erard-Marchant, K. Sheppard, T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and T.E. Oliphant. Array programming with NumPy. Nature, 585(7825):357 362, 2020.
GeofTrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge a neural network. arxio preprinl arXiv:1509. 02591, 2015.
K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks universal approximators. Newral Networks, 2(5):359 366, 1989.
J.D. Hunter. Matplotlib: A 2D graphics environment. Computing in science & engineering, 9(3):90-95, 2007.
Arthur Jacol, Franck Gabriel, and Clement Hongler. Neural langent. kernel: Convergence and generalization in neural networks. In S. Bengio, Н. Wallach, Н. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Newrol Information Processing Systems, vol- ume 31. Curran Associates, Inc., 2018. URL https://proceedings wwwpeiiiiinnnnnnunnreee. nwwrips.cccc.ooooo cc/papprr2018/filee ba2bectf44600bbb66663551561111.3
.pdf.
Andrei Kolmogorov. Three approaches to the quantitative definition ofinformation. Problems of informa- tion transmission, 1(1):1-7, 1965.
IEEE Transactions on Vladimir Koltchinskii. Rademacher penaltics and structural risk minimization. Informalion Theory, 47(55:1902-199) 1914, 2001.
Jean-François Le Gall. Intégration, Probabilités et Processus Aléatoires. 2006.
Ming Li, Paul Vitányi, et al. An introduction to Kolmogorov complezity and its applications, volume 3. Springer, 2008.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture scarch. In In-
ternational Conference on Learning Representations, 2019. URL httpss//opparrrree.nefffoooooosp
S1eYHoC5FX
14

---

Published in Transactions on Machine Learning Research (June/ /2044)
Zhengying Liu, Zhen Xu, Shangeth Rajaa, Meysam Madadi, Julio CS Jacques Junior, Sergio Escalera, Adrien Pavao, Sebastien Treguer, Wei- Wei Tu, and Tsabelle Guyon. Towards automated deep learning: Analysis of the autodl challenge series 2019. In NeurIPS 2019 Competition and Demonstration Track, pp. 242 252. PMLR, 2020.
Christos Louizos, Karen Ullrich, and Max Welling. Bayesian compression for deep learning. Advances in neural informalion processing systems, 30, 2017.
Kaitlin Maile, Emmanuel Rachelson, Hervé Luga, and Dennis George Wilson. When, where, and how add new neurons to ANNs. In First Conference on Aulomaled Machine Learving (Main Track), 2022. URL
https://openreevie net//forur//ddsSig--rrg..
Hector Mendoza, Aaron Klein, Matthias Feurer, Jost Tobias Springenberg, and Frank Hutter. To- wards automatically-tuned neural networks. In Frank Hutter, Lars Kotthoff, and Joaquin Vanschoren (eds.). Proceedings of the Workshop on Automatic Machine Learning, volume 64 of Proceedings of Ma- chine Tearning Research, pp. 58 65, New York, New York, USA, 24 Jun 2016. PMLR. URL https: //proceedings. mlr, wwtp:p/////////oooaaaaaaaaaa towarrss 2oridds_2oie__e 2016.html
Risto Miikkulainen, Jason Zhi Liang, Elliot Meyerson, Aditya Rawal, Daniel Fink, Olivier Francon, Bala Raju, Hormoz Shahrzad, Arshak Navruzyan, Nigel Duffy, and Babak Hodjat. Evolving deep neural networks. CoRR, abs/ Abs/1703.005488, 2017. URL http:://axxiv.org/abbbtee
00548
Geoffrey F. Miller, Peter M. Todd, and Shailesh U. Hegde. Designing neural networks using genetic algo- rithms. In ICGA, 1989.
Yann Ollivier. True asymplotic natural gradient optimization, 2017.
The pandas development team. pandas-dey/pandar Pandas, February 2020. URL https://doi.org//
5281/zenodo.c 3509134
A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. PyTorch: An Imperative Style, High-Performance Deep Learning Library. Advances in Neural Information Processing Systems (NeurIPS), pp. 6024-8035. Curran Associates, Inc., 2019.
Allan Pinkus. Approximation theory of the mlp model in neural networks. ACTA NUMERICA, 8:143-195 1999.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, PMIRR, 06-11 Aug 2017. https::::::/ /tttpp::/prroeeee http:////ccceenn..e/ee/ mlr httpaiigs..m..reereeeeeeeeeeee pwwps/resse... arrass//70/raguuu7a.. wttp//aghhuaaaaaaaa
pp.
J. Rissanen. Modeling by shortest data description. Aulomalicn, doi: https://dooiorr/11...000 100p:/i..o00000000000010000000 1016 110001/00000000000 1000550098(())90005--
1978. ISSN 0005-1098.
URL http:://wwwwscieneeeeieceec wttppttttcocccccccceeeeeeeeeeeee
att:cCle//11/0055107889055
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In Jemnifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Reseorch, pp. 4558 4566. PMLR, 10-15 Jul 2018. URL httpss:/ppocceeddng/ mlr. press/ wwwppssse/e///eep vw0///rraab...b...// html]
Kenneth O Stanley, David B D'Ambrosio, and Jason Gauci. A hypercube-based encoding for evolving large-scale neural networks. Artificial life, 15(2):185 212, 2009.
Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. CoRR, abs/ 1500.022406, 2015. URL http://dbll... wwaabbl..uni-riiii. uni-trier de//a//juuuratt/////rrr........ html# TishbyZ15
15

---

Published in Transactions on Machine Learning Research (June/ 22044)
N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and ils Applicalions, 16(2):264-26) 280, 1971. doi: 10.1137/1110025, URL http://link.att wttppiiiiiiii...............pp.a org/ / www.i///////////22
P. Virtanen, R. Gommers, T.E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Pe- terson, W. Weekesser, J. Bright, S.J. van der Walt, M. Brett, J. Wilson, J.K. Millman, N. Mayorov, A.R.J. Nelson, E. Jones, R. Kern, E. Larson, C.J. Carcy, I. Polat, Y. Feng, E.W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E.A. Quintero, C.R. Harris, A.M. Archibald, A.H. Ribeiro, F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261 272,, 2020.
P. Wolinski, G. Charpiat, and O. Ollivier. Asymmetrical scaling layers for stable network pruning. OpenRe- view Archive, 2020.
Lemeng Wu, Dilin Wang, and Qiang Liu. Splitting steepest descent for growing neural architectures. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'AlchéBBuc, E. Fox, and R. Garnett (eds.), Aduances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https:// proceedings neurips. wttpsatpr...pccpeeeeee/aaaa
pdf
Lemeng Wu, Bo Liu, Peter Stone, and Qiang Liu. Firefly neural architecture descent: a gen- eral approach for growing neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Bal- can, and H. Lin (ods.), Advances in Neural Information Processing Systems, volume 33, pp. 22373- 22383. Curran Associates, Inc., 2020. URL
pdf.
Tien-Ju Yang, Andrew Howard, Bo Chen, Xiao Zhang, Alec Go, Mark Sandler, Vivienne Sze, and Hartwig Adam. Netadapt: Platform-aware neural network adaptation for mobile applications. Proceedings of the European Conference on Computer Vision (ECCV), pp. 185-300, 2018.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep
learning requires rethinking generalization. In International Conference on Learning Representations, 2017. URL
net net/forum?id-SyygdB30
Barret Zoph and Quoc V. Lc. Neural architecture scarch with reinforcement learning, 2016. URL http: waaxxi..org/bb///eee
cite
Appendix outline
Appendix A details the theoretical approach of TINY.
Appendix reformulates related works with common theoretical framework and compares those approaches.
Appendix proves the propositions of Section 3
Appendix D
details the proofs regarding the convergence (related to Section
Appendix h provides the hyper parameters for learning.
Appendix gives additional graphics associated to the result part.
For Appendices and we use the trace scalar product and associated norm. We note (.. == (., )
and || : Tr- One should remark that ||- || 112-
16

---

Published in Transactions on Machine Learning Research (lune/2024)
A Theoretical details for part 2
A.1 Functional gradient
The functional loss L is a functional that takes as input a function f E F and outputs a real score:
L: JEFEFM L()
E (a.
[e([(z); y) E R
The function space F can typically be chosen to be L2(R" + R²), which is a Hilbert space. The directional derivative (or Gateaux derivative, or Fréchet derivative) of functional C at function f in direction v is defined as:
L( + ev) C()
(C(
lim -0+
E
if it exists. Here v denotes any function in the Hilbert space F and stands for the direction in which we would like to update/ f, following an infinitesimal step (of size s), resulting in function f + Ev.
If this directional derivative exists in all possible directions E F and moreover is continuous in e, then the Riesz representation theorem implies that there exists a unique direction v= E F such that:
E DC()(v) = (v",))
This direction 8" is named the gradient of the functional L function f and is denoted by VyC(f).
Note that while the inner product (: considered is usually the L2 one, it is possible to consider other ones, such as Sobolev ones (e.g,, H²). The gradient VyF(F) depends on the chosen inner product and should consequently rather be denoted by Vf [()) for instance.
Note that contimous functions from Iº to R as well as C functions, are dense in L2(PP + Rd).
Let us now study propertics specific to our loss design: L(f) E (f)(),), v)]. Assuming sufficient f-loss differentiability and integrability, we gel, for any function update direction v F and infinitesimal step size E R: C(F + Ev) - -(S) (a.D)~
E [e(f(x) + =v((), v) - ((f(x),)))
E V Vull(u, y) (=/(=) =v(()) O (e [1x)))])
(a.
using the usual gradient of function point (u f(x), y) w.r.t. its first argument u, with the standard Euclidean dot product- in R Then the directional derivative is:
DC()(v)
E (=
Vul(u, v) u=)(=)) v(x)
E E anD yn-Daa
Vul(u, 4) )))== v(w)
and thus the functional gradient for the inner product (v, v')E = ELND lu(x) - o'(x)] the function:
v=c(f)= E y~D
Vullu. 8) 1)l==
which simplifies into:
VJC() : # Vul(u, y(x)) (u)))))
if there is no ambiguity in the dataset, i.e. for each æ there is a unique y(x)
Note that by considering the (R(" Rd) inner product f v of instead, one would respectively get:
v(zl() (a())) E D-D
Vul(u, v) -
and
v(2((): x ( Vul(u, (xx)))
instead, where Pp (x) is the density of the dataset distribution at point æ. In practice one estimates such gradients using minibatch of samples (æ, y). obtained by picking uniformly at random within finite dataset, and thus the formulas for the two inner products coincide (up to constant factor).
17

---

Published in Transactions on Machine Learning Research (June/ (2044)
A.2 Differentiation under the integral sign
Let X be an open subset of R, and Ω be measure space. Suppose J X x $2 + R satisfies the following conditions:
f(x w) Lnbesgueeinteerable function of for cach X.
For almost all w E Ω the partial derivative oz of according to exists for all a E X.
There is an integrable function 0 Ω + R such that oe (a, w] < ((w) for all X and almost every a E Ω.
Then, for all e X,
0 2 dx J wl =/0
f(a,w) du
(15)
Ox
See proof and details: Le Gall 2006
A.3 Gradients and proximal point of view
Gradients with respect to standard variables such as vectors are defined in the same way as functional gradients above: given a sufficiently smooth loss C e θ사 + [()) = L(fe) E R, and an inner product in the space O4 of parameters 0, the gradient VoC(O) is the unique vector t E θ사 such that:
V50 E OA, T Doī(0)(80)
where (g is the directional derivative of E at point 0 in the direction 59, defined in the previous section. This gradient depends on the inner product chosen, which can be highlighted by the following property. The opposite -VC((0) of the gradient is the unique solution of the problem:
arg min { D= + |001 60E
where ||p is the norm associated to the chosen inner product. Changing the inner product changes the way candidate directions 50 are penalized, leading to different gradients. This proximal formulation can be obtained follows. For any 50, its distance to the gradient descent direction is:
60 (-važ(0) = -1801 + 220 Voï(O) + | \o
22 ||801|2 ()E())(60) K
where K does not depend 50. For the above to hold, the inner product used has to be the one from which the norm is derived. By minimizing this expression with respect to 60, one obtains the desired property.
In our case of study, for the norm over the space e^ of parameter variations, we consider a norm in the space of associated functional variations, i.c.:
Ofe 00
||0|| ==
89
which makes more sense from physical point of view, as it is more intrinsic to the task to solve and depends as little as possible on the parameterization (i.e. on the architecture chosen). This results a functional move that the projection of the functional one to the set of possible moves given the architecture. On the opposite, the standard gradient. (using Fuclidean parameter norm ||50|| in parameter space) yields
18

---

Published in Transactions on Machine Learning Research (June/ (2044)
functional move obtained not only by projecting the functional gradient but also by multiplying it by fe Ofa" T 00 30
matrix
which can be seen as a strong architecture bias over optimization directions.
We consider here that the loss C to be minimized the real loss that the user wants to optimize, possibly including regularizers to avoid overfitting, and since the architecture evolving during training, possibly to architectures far from usual manual design and never tested before, one cannot assume architecture bias to be desirable. We aim at getting rid of it in order to follow the functional gradient descent as closely possible.
Searching for
= arg min | "goaill 1|? = arg min DC(N))) + |1011?? M
(16)
DETA
or equivalently for:
0ʃa 00
1
05
2
50 = arg min
60
1 goaal
=
arg min DoL((o)(50)
+
50
(17)
6
60E@t
2
00
then appears as a natural goal.
A.4 Example of expressivity bottleneck
Example. Suppose one tries to estimate the function y = Sumo = 2sin(x) + x with a linear model fpredic((z) = ar + b. Consider (a, = (1,0) and the square loss L For the dataset of inputs (To, T2, - (0, 2, n in), there exists no parameter update (ōa, 8b) that would improve prediction at zo, 21, 22 and 23 simultaneously, as the space of linear functions {f : + az + b a, E R} is not expressive enough. To improve the prediction at Zo. 21, 22 and I3, one should look for another, more expressive functional space such that for == 0, 2, the functional update Ax(x) := fa+1 fx;) - (x()) direction as the functional gradient Ugoal = ( (f(x))))) -2(f(z,) - y:) where y; (I;)
target
prediction
5-
goes into the same
Figure 9: Linear interpolation
A.5 Problem formulation and choice of pre-activities
There are several ways to design the problem of adding neurons, which we discuss now, in order explain our choice of the pre-activities to express expressivity bottlenecks.
Suppose one wishes to add K neurons 0K (ax, w to layer (- 1, which impacts the activities aj at the next layer, in order to improve its expressivity. These neurons could be chosen to have only null weights, null input weights ag and non-null output weights W,, or the opposite, or both non-null weights. Searching for the best neurons to add for each of these cases will produce different optimization problems.
Let us remind first that adding such K neurons with weights 0% = (oos, W changes the activities a of the (next) layer by
K
da
We (a b1=(()))
(18)
Small weight approximation Under the hypothesis of small input weights ag,, and assuming smooth activation function at 0, the activity variation can be approximated by:
K
o'(0)
w (xx)
(19)
19

---

Published in Transactions on Machine Learning Research (June/ /2044)
at first order in ||as||- We will drop the constant (0) in the sequel.
This quantity is linear both in ag and Wk, therefore the first-order parameter- activity variations are easy to compute:
dai(a)
e' (z. (a)) O( (ax) (at)
(axs) =
Σ w w 2<xt)" oo
k=1
Dai(æ)
r' (x, (wx) = O( (w)) I
(wx) K =
Σ
wab. 2 axx
(ww)) =0
k=1
so with a slight abuse of notation we have:
K o' (z. 6k)
Σ bI
Note also that technically the quantity above is first-order in ag and in We but second-order in the joint variable 0K (ax; wk).
Adding neurons with 0 weights (both input and output weights). In that case, one increases the number of neurons in the layer, but without changing the function (since only mull quantities are added) and also without changing the gradient with respect to the parameters, thus not improving expressivity, Indeed,
the added quantity (Eq. 18) involves 0 0 multiplications, and consequently the derivative (a.(a)
w.r.l.
l0g -0
these new parameters, that is, 2 og w.r.t. We and WA b(_2(x)" w.r.t. ag is O, as both a and W/ are 0.
Adding neurons with non-O input weights and output weights or the opposite. In these cases, the addition of neurons will not change the function (because of multiplications by 0), but just the gradient. One of the 2 gradients (w.r.t. ag w.r.t wx) will be non-O, as the variable that is 0 has non-O derivatives.
The question is then how to pick the best non-null variable, (as or wx) such that the added gradient will be the most useful. The problem can then be formulated similarly as what is done in the paper.
Adding neurons with small yet non-O weights. In this case, both the function and its gradient will change when adding the neurons. Fortunately, Proposition 3.2 states that the best neurons to add in terms of expressivity (to get the gradient closer to the variation desired by the backpropagation) are also the best neurons to add to decrease the loss, i.c. the function change they will imply goes into the right direction.
For each family (Wi) the langent space in a restricted to the family (ow) dee. T =
{
da: (Bla)E= ((a)) ()aa)) (aa E (RIb)
k) varies with the family (w)) Lec T =
T ((w)) ). Optimizing w.r.t. the WE is equivalent to search for the best tangent space for the au: while symmetrically optimizing w.r.t. the ag is equivalent to find the best projection on the tangent space defined by the We (Figure 10
Pre-activities vs. post-activities. The space of pre-activities a; is natural space for this framework, they are formed with linear operations and compute first-order variation quantities. Considering the space of post-activitics b, = ((a)) is also possible, though computing variations will be more complex. Indeed, without first-order approxination, the obtained problem is not manageable, because of the non- linear activation function a added in front of all quantities (while in the cases of pre-activations, quantity [8 is lincar in We and thus does not require approximation in Wy, which allow considering large wx), and, with first-order approximation, would add the derivative of the activation function, taken at various locations a' a'(a:) (while in the previous case the derivatives of the activation function were always taken at 0).
20

---

Published in Transactions on Machine Learning Research (June/ 22044)
expressivity
gool
expressivity boctleneck
hot tleneck
goal
Ta((w)))=))
Tallw ke kmm)
Proita P ggaai
fe
2
ProjT
(2) (goat)
FA
FA
Figure 10: Changing the tangent space with different values of (wx K
k=1'
A.6 Adding convolutional neurons
To add convolutional neuron layer / -- 1, one should add kernel at layer | -- 1 and expand one dimension to all the kernels in layer to match the new dimension of the post-activity, see Figure 11
L
b1 (x)
b2(x)
internal representation
added neuron
kernels
added channel
Figure 11: Adding one convolutional neuron at layer one for an input with tree channels.
B Theoretical comparison with other approaches
B.1 GradMax method
To facilitate reading we remove the layer index of each quantity, í.e. b:= b, B Bi Vgoal and ygoalpproj == Vraal
gooal
The thcoretical approach of GradMax is add neurons with zero fan-in weights and choose the fan-out weights that would decrease the loss as much possible after one gradient step. We note the fan-out weights of such neurons and perform the addition at layer I- at time After gradient step, i.e. t - 4+1,
21

---

Published in Transactions on Machine Learning Research (June/2024)
and considering learning rate equal to 1, the decrease of loss is
L = C (VoL, + (V 822)
(20)
Taking the direction of the usual gradient descent, ic 50 = - veL and 652 = - VaL, we have
C x V | - 2
(21)
The output weights of the new neurons as formulated in the original paper Evei et al. 2022 at eq (11) are the solution of:
wk) = .2 arg max |n
s.t. ||01|3
(22)
we remark that:
2
n =
Σ b(xx,) Ugoal 7 (xx) 52
BV goal
'22
N 2
goal N := BV
T
It follows that the fan-out of the neurons computed by GradMax are the solution of the problem
Ω arg max
NΩ
s.t. ||||
(23)
To compare this optimization problem with TINY, we use the following proposition: Proposition B.1. VD E RP.9 B Rhg
AcER. R s.l. arg min
D 2B arg (D,
HER
H. HB (560
The proof can be found in B.1
Taking V goal as D and RATB B as HB, we can reformulate TINY optimization problem
A A Ω
arg max (AA, 2), V ggal pros)
s.l. (A,
(24)
A.
We remark that
V(A,S), V Vgoal pros)
= Q2A B, V yg proj
=Tr(B² AΩ V goal proj)
=Tr(A V proop B
=(QAA, V goal proj
BT
With the definition N = BV goat proj"
(V,,, V gualp (AST", .N)
(25)
For the constrain on ((),2), we perform the change variable A: S A, it follows that
() ||22A
TT(AA 2A S)
= B
|| A)T
-||22AT|
22

---

Published in Transactions on Machine Learning Research (lune/2024
With the same change of variable, the initial scalar product Equation 25 is
(V pray) (S2ATS- N,) (SAA ' -- = S N
(26)
TINY optimization problem now equivalent to
A 2 = arg max AS , S-AN)
8.1. ||AT|| &c
(27)
A.
To maximize the scalar product, we choose An S 2 N. A solution for (A, is the (left, right) eigenvectors of the matrix S N. implies that :
Ω == arg max
S 2 N
s.t. |.t. &
(28)
One can note three differences between GradMax optimization problem and the last formulation of TINY (Fquation 28
(+1 First, the matrix Ñ is not defined using the projection the desired update Vgoal proj" As a consequence, GradMax does not take into account redundancy, and on the opposite will actually Iry to add new neurons that as redundant possible with the part of the goal updale that is already feasible with already-existing neurons.
Second, the constraint lics in the weight space for GradMax method while lies in the pre-activation space our case. The difference that GradMax relies on the Euclidean metric in the space of parameters, which arguably offers less meaning that the Euclidean metric in the space of activities. Essentially this is the same difference between the standard L2 gradient w.r.t. parameters and the natural gradient, which takes care of parameter redundancy and measures all quantities in the output space in order to be independent from the parameterization. In practice we do observe that the "natural' gradient direction improves the loss better than the usual L2 gradient.
Third, our fan-in weights are not set to 0 but directly to their optimal values (at first order).
We now prove the proposition B.1
Proof. Indeed
arg min
D 2B| = arg min
[HB - 2(D,
(29)
HB HB
arg min
HB 2 HB||
D,
(30)
arg min |HB||
h - 22-2N
(31)
MU,
U= HB
(32)
We note U" arg max (D,U) which depends on B and D but does not depend on h. Then
HB HH
arg min
D HB
arg min - (D.U")
(33)
H
hU h 20 h U*
(34)
With the convention that [o 0.
23

---

Published in Transactions on Machine Learning Research (June/ 2004))
B.2 NORTH Preactivation
In paper Maile el al. (2022): lan-out weights are initialized to 0 while fan-in weights are initialized
a; = S B1-2VAi-1 r; where r; is random vector and Vz E R (er]/err(A] all is matrix consisting of orthogonal vectors of the kernel of pre-activations A!-1 In our paper fan-in weights are initialized T
a; S- 2 projjjj th S- Bi-2 P ker(B:-1) Vggal" I Vi, where (Ker(B:-1) Rua is the projector the kernel of the linear application B and v, the right eigenvectors of the matrix S
The main difference is thus that we use the backpropagation to find the best v2 directly, while the NORTH approach tries random directions vi to explore the space of possible neuron additions.
C Proofs of Part
C.1 Proposition 3.1
Denoting by M the generalized (usendo-)inverse of M, we have:
1 SW7 V goal B
B
and V Vggall B n
(
1 Bi- B( ) BI-1.
n
Proof. Fully connected layers
Consider the function
s(8W) Vgoul
8W B
(35)
P
then:
g(öW + H) = || - B HB:-111
(36)
s(oW) - 2 (Vranl -.WB... H1,HH, HB: (((HH))
(37)
g(oW) - 2 (eV(Vooo (Vgoal= -8WB SWBB-1) B B H + o(l H
(38)
By identification Vawg(öW) (Vront 8W B:BB.I B and thus:
V Vawg(oW) = Veoal B = OW B
Using that is convex and the definition of the generalized inverse, we get:
ow, 1
goal B 11
(- (BBLI
as one solution.
Convolutional layers
For convolutional layers we aim to solve (where we dropped the index ( 1 for readability):
min IV
goal Convsw(B)llz
(39)
SW
We convert this in linear regression by transforming the convolution a matrix multiplication. First we reshape and permute:
24

---

Published in Transactions on Machine Learning Research (June/ 2004))
sw e (CI+)),,, is transformed in dWF E (C[+]],C(++]]]++)
goal (n, ([+1], W[+1]) is transformed in Vooa e (m][(=]][[+1))(+-
(n, Cd[+1]d(+1]] [[1) and its reshaped version B E that satisfies that B (n#[ is a reshaped version of Convaw(B; (B can be easily computed using torch. nn. Unfold.)
Then we can define B [d]
Hence Equation 39 becomes:
arg min 5wr
V
B
(40)
Using the same reasoning that for fully connected layers, get optimal solution:
(SW;)* = ((B$)* BT) (Bi) goal
(41)
7
C.2
Proposition 3.2
We define the matrices N = 1 Bi-2 (Vena and S = BB-2Bf-2 Let us denote its SVD by S
T
OΣΟΟ, and note S = OVE 0" and consider the SVD of the matrix S = E A with A > > AR 2 O, where R is the rank of the matrix N. Then:
Proposition C.1 3.2
The solution of equation can be wrillen as:
optimal namber of neurons: K*
their optimal weights: (or, w (VAgS-2us vλRus) for 1: I,..., R.
Moreover for any number of neurons K R, and associated scaled weights 0k;², the expressivity gain and the first order in n of the loss improvement due to the addition of these K neurons are equal and be quantified very simply function of the eigenvalues Ak:
K
y B. = V
for fully-cormecled layers, with an inequality instead (E) for convolutional layers.
Proof.
To facilitate reading we remove the layer index of each quantity, ic B Bi-2, (' = V(A and Vgontyroj == pralp We fix n and æI,..., Rn on which we solve the expressivity bottleneck formula.
To solve this problem, we consider the input the incoming connections and the desired change in the output of the outgoing connections Vgoalpraj" Hence if we note L(A) and L(2) the additional connoctions of the expanded representation and the non linearity, we optimize the following proxy problem:
arg min 1 o .o L(A)) - Vggalprojj A.
(42)
We solve this problem first order by linearizing the non-linearity σ. We denote (in(o, the fully connected layer with input size a, output size b and weight matrix W. We also note C[+1] and C[-1] the
25

---

Published in Transactions on Machine Learning Research (June/ (2044)
layer width at layer 1+1 1 and 1-1 with the convention that C[O] is the dimension of the imput With those notations, for fully connected layers, we have for the additions of K neurons:
arg min A. n
Vgoal proj
Vgoalprro
(43)
With the same notations, for convolutional layers, we have for the additions of K intermediate channels:
1
ggoal ygoalpros ||
arg min [Canrcchia((D/CCCoooooooaa]a))]
(44)
A n
If we note (2) the result of B after applying the layers parametrized by and 52, in both cases we aim to optimize:
arg min A.
V(A, 92)
V
goal proj Ir
(45)
First we will transform the resolution of the problem solving the following optimization problem:
mig
St AΩ -S-
(46)
A.
where S depends of B and N of B and proj"
If we note OAOT the SVD of S, we define the square root of S as St OVÃOT and S := T with the convention 0-1 O.
C.2.1 Fully connected layers
For a fully connected layer, we have
V(A R) (ino = Q
(47)
Lemma C.1. Let Y E R(I, n), X (()
We define:
1
S -X -x E R(s,s)
(48)
N = x E e((s)))
(49)
CX 2 cst - NT 2 S- 1 N -1
(50)
Proof in 2.2.9
Hence using Lemma C.5 with C' + QAT Y + V Vgoalproj and B &- X, we have:
goal proj
1 RA B Vgoalproj
(51)
n
Tt -
ss N |
1 + n
V Vgcal proj
26

---

Published in Transactions on Machine Learning Research (June/ 2004))
With:
S = BB" ER(CI-1),C|-)
(52)
BV goal proj E E((CI-1,,C(+1)
(53)
C.2.2 Convolutional connected layers
We have A R(K, C[-1],d,d) and Ω e R[C[+1], d[+1]] d(+]) where d, d[{[+1] is the kernel size at 1 and 1. We note AF the flatten and transposed version of A of shape (CI-1]dd, K) and a₁ == AF k] E (CI-1]dd,1), 1). We will now consider with the last order flatten ie. E [RC + K, d[+]] We also
w m
note Wk.m = 12m, E (d[+]]d[+1].I). Using this we define l1m]r ==
E (K, (K,[(+]d((+1)) and
Km
0p= = (8[1)r
Q(m]r) E (K, [[]](+++([+]]]((++))
We define the tensor T such that for a pixel of the output of the convolutional layer, T₃ a lincar application that select the pixels of the input of the convolutional layer that are used to compute the pixel j of the output in flatten version image (flatten only the space not the channels). T e [[H[-]]W [+1], d[++]d[++]] HW) where I and W are the height and width of the intermediate image and H[+1] and W[+1] are the height and width of the output image.
As previously, we have B the unfolded version of B such that B E C(-]dd, HW) satisfying Conv is equal with the correct reshape to AB.
In addition, we use j as an index on the space of pixels instead of having a couple h, for height and width. With those notations have:
((,,
Conv (c[+1),)) (CCCCH/LAA(((CCCCCCCCCCA(AA//0/ mm.
(54)
Σ
T w (B.)) as
(55)
In the following for simplicity, we note B == TT( To find the best neurons to add we solve the expressivity bottleneck as
arg min ΣΣΣ
V
goalprojj
(J.m)
Σ w m
B Oz
(56)
A. n
3
(57)
27

---

Published in Transactions on Machine Learning Research (June/ /2044)
Using the properties of the trace, it follows that
Σ
Vgoalprojs
(.m)
Σ
W m,k
Bi
ak
Σ
Vgoalprojj
(i:)
Σ
Tr (Bi, axwm
(58)
f.jm
1m
i.j.m
h
Fi
gooalproj
(F.m) - TT
B
ayw
m,k
(59)
J.
k
V
ygoulprojj proje
(dim). flat( (B flat(Fr)
(60)
k.
ggoal (5) - flaa((
(61)
(62)
With F := (flat(Fi) ... flat(Fo
We remark that V(A, is linear function of the matrix F which implies that the solution of 56 is the same as the one for linear layer. Replacing ΩA by F in 47 and following the same reasoning as for linear layer, follows that 56
equivalent
- S
arg min
(63)
with = E.E flatt and N : Vsoal a flat
However, we remark that the dimension of S E R(C]-1]((+1]dd, c1-1jd(+1}(d+) is quite large and that computing the SVD of such matrix is costly. To avoid expensive computation, we approximate(56jby defining
the matrix S and N as 998 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 min B shope), we define:
#++1
r
Σ
(BL)) E (00--i)ddC[-1iddd
(64)
n
n.
N =
Σ
goal j.m
gond
(B,))² T E (C[-1)dd, d[+1]d(+1])
(65)
N = (N1 NCH11) E [[---ddd.C(++]](((udd+)))))
(66)
We have:
(AA V yoolspros
2 < - S-iN||
- 1 - - -=
2 +
V
gool gool proj
(67)
Proof in C.2.2
Lemma C.3. For SER, E R(
R(K,t)
We note UAV the singulor value decomposition of S and UK the first K columns of U, Vx the first K. lines of V, Ag the first K singular vatues of A and AK+1: the other singular values of A.
We define:
= Ω = V VK
(68)
(69)
28

---

Published in Transactions on Machine Learning Research (June/ /204))
Then:
||
goosp | - || 2 1
min (2)
V goutpros
< ((A",)))
S2)
Vgoalpros
(70)
with equality in the linear case. Using expressicity boltlenecks nolations, this rewriles:
K
V 0ooo
< V
x
(71)
k=1
Proof. Using Lemma C.5 and Lemma C.7
((A
Vgoal proj
<
st AΩ -S-
|
+ 1
yooalproj
(72)
n
Hence we minimize the second term of the right term, that
arg min A.
s AΩ -
(73)
As we suppose that is invertible, we can use the change of variable À =S S A thus we have:
min A.
A - -S-i
min a.
Án - N/
(74)
The solution of such problems is given by the paper Eckart & Young 1936 and is:
A' UKVAK
(75)
O VAKVK
(76)
To recover A simply have to multiply by S the left side of A'. By definition of the SVD and the construction of (A*,2") we have:
s A -S S
- -||s -- 1 2 = 1|
||A112 -
(77)
Using this and Equation 72 we immediately get the desired Equation 70 this with the bottleneck expression:
To conclude, we can also rewrite
1 V(A,Ω) V
T BOoK == min
goul
<
k
(78)
A.
We now prove all the lemmas.
Lemma C.4. For e R)s,s), C (R(tt).
If N = St N, have:
- - s² - sstt |
(79)
29

---

Published in Transactions on Machine Learning Research (June/ (2044)
Proof.
For the first term we have:
(C", = (c", sist.r)
(80)
(81)
s |
(82)
For the second term we have:
(N,
(tts N N ca
(83)
=($
(84)
Hence we have that:
(C", - 2( | 2 2
(5S5AN,5 N, N.
s à N 2
(85)
- - -- :N12 - | n/
(86)
Lemma C.5. Let Y Rt,, X R(s,n), Ce R(t(,s))
We define:
S 1 xxx E R(s,s)
(87)
: = XY E((s))
(88)
1
Cx
-Cx-Y11- Y| | cst
N 1 |
s N//
1
(89)
Proof. By developing the scalar product we get:
1 |
1
+ 1 |
|Ix 2
2
Y
CX
(90)
7
n
1
|8
-
Y 1
CX
(CX,
(91)
n
1
||Y1|
Y
1
(CX)")
T
+ + ==(((x)))) ((xx)",(cx))))
(92)
n
1
|al|
1
XYT cTT)
",",,xx'00"
(93)
n
n
We now use the two following lemma:
Lemma C.6. Let Y R(t, X E n)) and S X E R(s,s).
s X
(94)
Proof. Let decompose Y on Im(X (T) +1 ker X): y = XT K K.
XY - - XK Xx SI
Hence XYT (m(S)) hence Im()) is invertible, we have: S A XYT.
7
30

---

Published in Transactions on Machine Learning Research (June/2024
Contimuing the demonstration from Equation
93 by applying Lemma
C.4
have
CX Y11
Y 2 2 (N. C*) + (C" SC
(95)
|Y| + S -
S N
(96)
n
|r + cst N
S N
(97)
n
Lemma C.7. Let = min( (.n(B,..shape) we define:
[++1
S Σ
Σ
(BI,) (CI-I]dd,
(98)
11
==1
n. [ []][+]]
Nm.
grofprrfi. (Bi,)) (C[-1]dd, d[+1]d[++1)
(99)
7
N (N1 NotH1)
(100)
We have:
- 3 N (A) grotppos |2 < " - --
2 +
v yoaaspros |
(101)
Proof. We have:
1 n
(A) Vgoal prof || = || 2111 -VVA.8)j-22(((A.)) (V( V Veaal pros) )
2
+ goal proj
(102)
We will now simplify the first two terms separately.
Norm simplification
Lemma C.8. For any square matric A R((n)) Tr(A)² & rank(A)]]A[))
Proof- Using the truncated SVD have A USV with Σ diagonal and U R(n.ran((A)), V E ((ran((A),)) truncated orthonormal matrices.
We have:
2r = THUEV)?
(103)
Tr(VUE)2
(104)
(VU, Σ)²
(105)
(Cauchy-Swarz) & /
(106)
As U, V are truncated orthonormal matrices, we have:
||V - Tr(Trank(A)) rank(A)
Hence:
Tr(A)² < <rank(A) |
(107)
31

---

Published in Transactions on Machine Learning Research (June/ 2204))
As U, V are truncated orthonormal matrices, we have:
|||| Tr(=²E) = T((VUU)U = A) = =||A|²
We conclude that:
Tr(A)² < raak(A)) (ank(A)||A|) |A|]
(108)
Lemma C.9. For M E (m, (ux) (m)* (EN]AE][K]] E (n)* and with W = EkETKT oask (n, m) we have:
E
Σ KEIK]
u Muk
-MM))
(109)
Proof. Let i T:
Σ
vut T Muk
Σ
ui Mok
I
(110)
AEIK]
AELK]
=Ir
Σ KE[K]
us M
(111)
2
Tr
M
Σ
vaui T
(112)
kE[K]
Tr (MW)2
(113)
Lemma C.10. For (M.)e (m, such that vi (.raak(,W... & H and with W E (n, we have:
Σ 1E1
Tr(,M <
W, H
MT M.W
(114)
NE1
Proof. Let I:
Using Lemma C.8 with A + M,W
Tr 22 & rank (Mn) [M
(115)
H M|I
H == min (ainMMsshaap)
(116)
Hence we have:
Σ
u M
< H
|M,
(117)
RET
kE|K]
iET
H Σ
(MWW M.W
(118)
IEI
= . Σ
( M M.W
(119)
iET
H
W. Σ
M M,W
(120)
1E
32

---

Published in Transactions on Machine Learning Research (lune/2224
Using first Lemma C.9
with up t Wkmm + ax and M t Bij we have:
n.H. (11[((+
K
VVA S2)1 = T
Σ
Σ
Σ
wh (Bi
(121)
C1+1
n. [1]11++
K kgw k.m
Σ
Σ
Tr B
(122)
C1+1] H
Σ
Tr A
(123)
Using Lemma C.10
with 4 (i.j), M, + Big and W + Apsimmpp:
c1+1
n. 1|[[[]]
Ar
(B.)
(124)
C[+1]
Σ
(A+S2(m) SA)()(
(125)
m
SA
(126)
Scalar product simplification
Lemma C.11. For M E (m, n), u E (m), v E (n) we have:
- Mu = (vu",M²)
(127)
Proof.
u Mu (u MU)T
(128)
V" M
(129)
(v, M (vu", M
(130)
(131)
We have:
C[+1]
n.
2
V(A,2), Vgeal pros
Σ
Σ
Σ
w WTm Bijaa on Vgonl prodi
(132)
n
71
C[+1 K
n.H[+1][[-1]
(V (Vgaalprojt...om
( = Σ
w
(B i. gold Vgoul proji,,.. )ok
(133)
k.m n
m
b
33

---

Published in Transactions on Machine Learning Research (June/ (2044)
Using Lemma C.11 with M Eis
1o.H(+10
[++|][++1]
V goal goalprols....m profs.j.m
(B
C[+1]
n. n.H(+1[((1))
Σ
Σ a2 k,m
Σ
ga proj i.m.
(B²,))
(134)
72
m
C[+1]
Σ
(ApS[[m]F, Nm)
(135)
N)
(136)
Conclusion In total, we get:
1 ((A Yeealpras || (ArQ,, -A - (A= N)
V
Vgoslproj
(137)
If we suppose that S is invertible, we can apply Lemma
C.4 and get the result.
Proposition C.2. Solving is equivalent minimizing the loss L al order one in V Furthermore performing an update of architecture with 7oW* 5) and neuron addition with 70 3.2 has an impact on the loss at forst order in &
[(fegok) = C(fo) - (0) + Aow.) + +(7))
(138)
with
K Σ>n
A A = 1 Vl
= gool v'(0(()))
2
(139)
km
1 (Vil
Asw-
v'(oW")) 70
(140)
goats
n
To prove such proposition use the following lemma. Lemma C.12. We note V(A, Ω2) the result of B after applying the layers parameterized by A and Ω. Let
consider V(A",Sr) where A and o are defined in 3.2 Then:
1
Vooal V(A", (A))))) = ||Ax|1
(141)
Proof. Starting from Lemma C.3
1
V(A", 22) Vgoal projp |2 =1 + 1 V
goalproj
(142)
Hence by developing the norm, have:
(A', 20111 2 (V(AA, V Vguulproj) - 11
(143)
Morcover by construction we have (V ( ||Ax|1 and therefore we get:
2 (VAA".2" Yeoalproo) ) - - -||
(144)
which concludes the proof.
34

---

Published in Transactions on Machine Learning Research (June/ /2044)
We prove the main proposition. Suppose that each quantity is added to the architecture with amplitude factor i.e. the best update is then 7 o and the new neurons are (Vra, /7w, hi-
Using the Fréchet derivative on we have the following:
C(a' +7 - L(a')) + (VaiL,yda") + o(7)
(145)
On one hand, performing an update of architecture, ic W + W + + "oW, changes the activation function
a' by 7 oā : V(y8W"> Then, as explained in Appendix A.5 changes the activation function a' by:
adding neurons (A", ,2*) at layer - 1
óa = d0) V(A", +
(146)
We now suppose da!, day and perform first order development in 7. Then combining Equations 145 and (146), have
L(A (2) L+ (V (oa', + 5a')) + d(7)
(147)
Using that Ugoal (2;) Vol ((x;) and that
1 n E: (xx;), follows that
C(A' 22) = L (Vgual: (5a', + saa)) + o(7)
(148)
C 1 (Vgoal, 00²)) + (Vgoal - V(70W*), 50')) +7 ( sa')) + o(7)
(149)
Using C.12
have
C(A' = =L --7 d' Σ 2 (V (Vgoal,
Vgoaa..da.) da².)
+ o(7)
(150)
Note on the approximation for convolutional layer. By developing the expression | V goal proj |13 we remark that minimizing V 2| over V equivalent to maximizing (V, Vgoelpraj? with a constraint the norm of V. This constraint fies in the functional space of the activities and can be reformulated in the parameter space with the matrix S as || |V By changing the matrix S for another positive semi-definite matrix Specudo: we modify the metric on V and obtain pseudo-solution S-1
psendo N.
C.3 Proposition 3.4 and Corollary 3.2
Proposition C.3. 3.4 Suppose S semi definite, we note S = stst. Solving equation equivalent to fond the K first eigenveclors 0g associated to the K largest eigenvalues X of the generulized eigenvalue problem:
NN az X SSak
(151)
Corollary 2. 3.2 For all integers m, m' such that m + m' & R, al order one in n, adding m + m' neurons simultaneously according to the previous method equivalent to adding m neurons then m' neurons by applying successively the previous method vwice.
Proof
To prove 3.4 we show that the solution of 151 and the formula of 3.2 are collinear.
35

---

Published in Transactions on Machine Learning Research (June/ (2044)
Solving 151 is equivalent to maximizing the following generalized Rayleigh quotient (which is solvable by the LOBPCG technique):
α N
α' arg max
(152)
α Sa
a
P'S S NNNNS S-ip
p arg max
(153)
p² p
p=S1/2a
p arg max ||||=1
NN Epll
(154)
a" = SS +p"
(155)
Considering the SVD of S E e,, then S Σ - X² + - e, 0 and f fj 0. Hence maximizing the first quantity is equivalent pk fu, then
because
a& = S = fx, which matches the formula Proposition 3.2 The same reasoning can be applied to wi.
We prove second corollary 3.2 by induction. Note that v0O x) o(r), then for m' = 1:
ai(z)(+1 = (x()))' + v(t x) + o(7)
(156)
Remark that (x)) is a function of ax))). i.e. (g)) = (x)). Then suppose that ((f(x), y)) is
twice differentiable in ax()). follows that ((ar(x)) is differentiable and
goal (z) g(a/(()) (001," x))
(157)
((aa(x)) V Valla) (m)) 0(0 , + o(1²)
(158)
0 ((fo(())))) v) v00 (04"')) x) =((1))
Uggall (x=) + f (a)2
(159)
Ugool Ugral((x) + a())
(160)
Adding the second neuron obtain the minimization problem:
arg min |/goal' V(a2, w2)l + o(n)
(161)
0rg 440g
C.4 About equivalence of quadratic problems
Problems and are generally not equivalent, but might be very close, depending on layer sizes and number of samples. The difference between the two problems that in one case one minimizes the quadratic quantity:
| + V'(M) Vguall
w.r.t. M and 0% jointly, while in the other case the problem is first minimized w.r.t. M and then w.r.t. gK. 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 the spirit of improving upon a standard gradient descent: 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'MM) = ów; Bi-1 while ('(0X) = Ek= wy The rank of B min(ng, 14-1) where ng is the number of samples and n the number of neurons (post-activitics) min(ns, n2-2) where n4-2 the number of neurons (post-activities) in layer 1-2. Note also that the number of degrees of freedom in the optimization variables oW; and 0% (Wk, o.k) is much larger than these ranks.
layer 1, while the rank of B is
36

---

Published in Transactions on Machine Learning Research (June/ 22044)
Small sample case. If the number ng of samples is lower than the mumber of neurons n4-1 and R4-2 (which is potentially problematie, see Section F. then it is possible to find suitable variables oW; and o to form any desired ('M) and v'(0)). In particular, if ns & R4-1 & n1-2, one can choose v'(0k) to be Vgoal' - (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 very large (compared to the number of neurons 74-1 and n(-2), then the lines of matrices Bi-1 and Bi-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 ('MM) and v'(ok) become orthogonal, and proceeding greedily does not affect the result, the two problems are asymptoticall equivalent.
In the general case, matrices B and Bi-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 greedy approach layer growth might get stuck in 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 Σ -f
(162)
FED
where [(x is the output of the neural network and 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 Scction D.4 to show that one keep adding neurons to network (without modifying already existing weights) to make it converge exponentially fast towards the optimal function. Then in Section D.6 we present 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 necessary) will reach training error in at most neuron additions.
D.1 Possibility of greedy growth
Proposition D.1 (Greody completion of an existing network). If f is not f yet, there erists a set of neurons to add the hidden layer such that the new function f' will have 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 compact set w, for any desired precision and for any activation function a provided it is not a polynomial, then there exists a neural network with one hidden layer (possibly quite large when y is small) and with this activation function o, such that
Vx, [1((x)
(x))l Yn
(163)
37

---

Published in Transactions on Machine Learning Research (June/ /2024)
We apply this theorem to the case where g" - which is continuous f is continuous, and I is a shallow neural network and as such is a composition of linear functions and of the function 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 concalenate the networks obtained for each output independently). We choose 7 = _े l - fllzz, where [alb) = d Snew ((x) dæ. This way we obtain one-hidden-layer neural network g with activation function or and we write a(x)= = g(x) (x) the error term, it follows that:
[w]
Vx w, -7 g(x) gg((a) <
(164)
Vx E w, g(z)= = fx) f(x) + a(x)
(165)
with Vo E w. la(x)) <
Then:
Yx w, (2)) + g(())) -a(x)) Vx Ew, (z) - (z())
(166)
(167)
with h being the function corresponding to neural network consisting of concatenating the hidden layer neurons of and g, and consequently summing their outputs.
I1 N12 = ||a|22
(168)
|f If-- < 100! 11f-=ffff fl2
1
(169)
and consequently the loss is reduced indeed (by factor of 100 in this construction).
The same holds in expectation or sum over a training set, by choosing 7 = tov ((ED - (x))
as Equation 1677 then yields:
E ((()) [d)()) 1 (())))
(170)
100
RED
xED
RED
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 such that the n-th order derivatives (())(,,) are not O. Then, by considering appropriate values arbitrarily close to Cu, one can approximate the n-th derivative of a at en and consoquently the polynomial c of order n. This standard proof then concludes by density of polynomials in continuous functions.
Provided the activation function o is not polynomial, these values cn 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 neuron to add to the hidden layer such that the new function f' will have 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 selling of L 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) in the case of the I regression). That is, denoting by a.a (Wa(W, (W. x:) these N neurons:
N
Σ
a x) gg
= K <0
(171)
17
38

---

Published in Transactions on Machine Learning Research (June/ 22044)
i...
(a x)1 11 K <0
(172)
We have:
1 N N
1
02 > K
(a x) g) min (a x)1 (1gg)
(173)
N
Then necessarily at least one of the N neurons satisfics
(a,o(w; : x) 9) < N <0
(174)
and thus decreases the loss when added to the hidden layer of the neural network representing f. Moreover 1 of the loss decrease resulting from the addition of all neurons. this decrease is at least N
As consequence, there exists no situaatoon where one would need to add many neurons simultaneously decrease the loss: is always feasible with a single ncuron. Note that finding the optimal ncuron 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 arbilrurily small input weights.
Proof. This straightforward, as, following a previous remark, the neurons found to collectively decrease the loss can be supposed to all have arbitrarily small input weights.
This detail is important in that 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 ncuron 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 layer and desired output variations. It might happen that the loss is not minimized yet but there is such correlation to exploit anymore. In that case the optimization problem (8) will not find neurons to add. Yet following Prop. D33 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 e on all of its imput weights), for instance ()) ~ (0) o' (0)=a-x=+ (0)=))"((aa))))) +)²+0(E()))) Though the linear term a. x might be uncorrelated over the datasct with desired output variation v(x), i.c. EawD(æ u(x)] = O, the quadratic term (e)=) 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 (a 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 bottle- necks 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 + 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 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).
39

---

Published in Transactions on Machine Learning Research (June/ 2024))
D.2 Loss decreases with line search on quadratic energy
Let L be a quadratic loss over Rd and be vector in R The loss L can be writlen as:
L(g) = g= Qg + - g+
(175)
where Q a matrix that will suppose to be symmetric positive definite. This is to ensure that all eigenvalues of are positive, hence modeling a local minimum without saddle point. is vector in Rd and K is real constant.
For instance, the mean square loss ELED a target function, and S is a symmetric positive definite matrix used as a metric, fits these hypotheses, considering (f(2) a vector. Indeed this loss rewrites as
(x)]] where D is finite dataset of N samples, f
Σsw)s)(()) (T. K g0Q9 v K
(176)
by flattening and concatenating the vectors f(r:)) and considering Q = S & S S the tensor product of N times the same matrix S, i.c. a diagonal-block matrix with N identical blocks S. Note that for the standard regression with the 1 metric, this matrix Q is just the Identily.
Starting from point g, and given direction h E Rd, the question is to perform a line search in that direction, i.e. optimize the factor À R in order to minimize Cly + Xh).
Developing that expression, we get:
C(g - Xh) = (g + Ah) Q (g + Ah) + (g Xh) = X + A(2h" Qg + + - ((g) (177)
which is a second-order polynomial in with a positive quadratic coefficient. Note that the linear coefficient is hT VVV(())) where Vg((g) 2Qg to is the gradient of L at point g. The unique minimum of the polynomial
in À is then:
1 1n'V,
X
(178)
2 hTQh
which leads to
min Cig+ Ah) xT Qh + X V v((()) ((g)
(179)
= [(g) 4 hTQh
(180)
h
C(g) |
V9 49 ((g)
(181)
Thus the loss gain obtained by a line search direction quadratic the angle between that direction and the gradient of the loss, in the sense of the Q norm (and it also quadratic in the norm of the gradient). Note that inner products with the gradient do not depend the metric, in the sense that (h) V VV(())) = (hl v (())) vh for any metric S, i.e. any symmetric definite positive matrix S associated to the norm [| 3/3 = hT Sh and to the gradient (() = S-'v!? L(g). In the case of a standard 2 regression this boils down to:
min llg + Ah 2r llall
(182)
|/|
1.2
i.e. considering C()) = EZED [1[(x)) (-)))
h
2
E
1( k]
min L(F + Xh) = L(F) -
fr 8-
L())
FED
(183)
||b||
E ZED
|1/11
1.2
A result that is useful in the next sections.
40

---

Published in Transactions on Machine Learning Research (June/ 2024))
D.3 Expected loss gain with line search in random direction
Using Appendix D.2 above, the loss gain when performing a line search quadratic loss is quadratic in the angle a
V(X)
(X)a
between the random search direction V(X) and the gradient Vgoa(()
[VIII
[X)Il
1 This angle has average 0 and is of standard deviation nd: described in Section 5.2 The loss gain is thus of the order of magnitude of 1 in the best case (single-sample minibatch). d
D.4 Exponential convergence to training error
Cousidering regression to 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 reach loss by an addition of n neurons (hi) with is the dataset size, using Zhang et al. (2017). Unfortunately there is 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 least 1/n. While one could consequently hope for a loss gain O one has see that this decrease would be the one of a gradient step, which is multiplied by step size 77, and asks for multiple steps to be done. Instead in our approach 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 yj 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 L(f) EZED [15(()) (x)) where D is finite training dataset of N samples. Its functional gradient VL(J) at point f is 2( f"), which is proportional to the optimal change to add to f, that is, f--f. f. The n neurons (hi)igign to be added to f following Zhang et al. (211)) satisfy Σ; h4 = f - = = - VCC(). Thus
Σ h4 f
1-11-fl12 C(f).
(184)
17
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 neuron hy that satisfies:
(hel f f) > C(f)nn
(185)
By applying Appendix D.2 one obtains that the new loss after line search into the direction of h yields:
min C(f + Aha) = L(f) (hi f - < C(f) x (1- 1211//4113
L(f)
(186)
|/
From the particular construction in Zhang et al. 2017 it is possible to bound the square norm of the neuron [| 2 by d' dar
dm L(f), where dar is related to the maximum distance between points in the datasot, dm is another geometric quantity related to the minimum distance, and d' is the network output dimension. To ease the reading of this proof, defer the construction of this bound to the next section, Appendix D.5
Then the loss at each neuron addition decreases by factor which is at least ==1--
Jे dad
1. This
factor is constant, it is a bound that depends only on the geometry of the dataset (not f).
41

---

Published in Transactions on Machine Learning Research (June/ /2024)
Thus it is possible to decrease the loss exponentially fast with the mumber t of added neurons, i... C(fe) & 7 [()), towards 0 training loss, and this in 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 Equation 187
The number of neuron additions expected to reach good performance according to this bound is in the order of magnitude of n², which is to be compared to (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 t than Zhang et al. (2017), though with this proof the bound cannot be better than n² (supposing ||a/] 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 higher that the number of points) can casily in turn be perfectly predicted (0 loss) by just one neuron addition each (without changing the outputs for the other points), by choosing hyperplane that separates the current convex hull point from the rest of the datasct, and setting 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. (0017) can be chosen so as to bound the square norm of any neuron || by nd ddx
L(f), where dı is related to the maximum distance between 2 points in the dataset, and dm 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 == (e..) the target function (here ( f' at each æ.)), A is the matrix given by Ayx- ReLU(a xy - bby, representing neuron activations, and is any vector that separates the dataset points, i.c. 22 # a my Vj # j', that is, could be almost any vector in Rd (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:
E arg max min la (zj- - x,2)]
(187)
||l|=l 35
and let us denote d'm the associated value: d' = minjo' la (ry - æyr) for that a. Note that d'm < min,,, |ly - =I 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 ming, [|2 zy times factor depending on the embod- ding dimension d and the number of points n.
Now, let us sort the samples according to increasing a Ty, that is, let us re-index the samples such that (a-2,) now grows with j. By definition of a, the difference between any two consccutive a a-x, is at least d'n.
We now choose biases by- = a a; d'm + e for some very small e. The neurons are then defined as hx(a)) = wyRReLU(a - x - bg). The induced activation matrix Ayk = ReLU(( æy by) then satisfies Vj < k; Afe = 0 and Vj > k; Aÿk 2 d' s. The matrix is lower triangular with diagonal elements above dm := d'm E, hence invertible. Recall that y= Aw.
Consequently, A and hence || < |||A~"||1 11 that is,
||l|| < J2
L()
(188)
as the target y is the vector f"- o in our case. Consequently, for any neuron h, one has:
< de
L(f)
(189)
42

---

Published in Transactions on Machine Learning Research (June/ (2044)
As the norm of the neuron is ||A,1| = w Σ, AJ., one still has to bound the activities A₁, = ReLU(a.x, b,). As was chosen a unit direction, the values æj span domain smaller than the diameter of the dataset D: la (x) - z & 1 zzyll & diam(D) vj.j'. Hence all values Vi [Aigl = la-r; - byl = |a 22 a a. + dml < du == (D) + dm- Note that dı depends only the dataset geometry, as for dm-
We now have:
By d
|//12 = /n DA
E n2
(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 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 obtain a constructive proof, and inspired by the previous section. See Appendix D.7 for another, more generic proof, applicable to 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 bj. thus forming the activity matrix A, we add only the last neuron hn The activity of this neuron is 0 for all input samples zy except for the last one, for which it is Ann. 0. Thus, the neuron hn separates the sample zn from the rest of the dataset, and is easy find wa so that the loss gets to 0 on that training sample, without changing the outputs for other samples.
Similarly, one can then add neuron hx-1, which is active only for samples In-1 and In. However designing #x-1 so that the loss becomes 0 at point _n-1 disturbs the output for point In (and for that point only). Luckily if one allows updating wi then there exists a (unique) solution (wa-1, w.) to achieve 0 loss at both points. This is done exactly as previously, by solving y = Aw, but considering only the last lines and rows of A, leading to a smaller 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 0 loss. Thus adding n neurons is sufficient to achieve 0 loss the full training sct, and this in way that each time decreases the loss.
Note that updating existing output weights while adding new neuron, to decrease optimally the loss, is actually what TINY docs. 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 extract the main tendencies.
D.7 TINY reaches 0 training error in 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.
43

---

Published in Transactions on Machine Learning Research (June/ (2044)
Optimization protocol. For this consider the following optimization protocol conditions, that has to be applied at least during the last, n-th addition step:
full batch approach,
when adding 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 casy 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 Ygaal, and is proportional to - 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-cxample 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 z; and desired output variations (xx) fxx,) can be found anymore. To prevent this, one can choose any auxiliary method to add neurons in such cascs, 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 guarantced not to increase the loss 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 the invertibility of a certain matrix, namely, the activation matrix A, defined as Aij o00 + bj), indexed by samples i and neurons j.
Gencrally speaking, kernels induced by neurons ky x + (By x + by) form free families, in the sense that they are linearly independent (to the notable exception of the linear kernel). This linear independency means that linear combination of kernels cannot be equal, a function, to another kernel with different parameters. Equality is to be understood as for all possible points æ ever. However here will evaluato the functions only at finite number 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 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 instcad 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 datascts. 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.
44

---

Published in Transactions on Machine Learning Research (June/ 20044)
To properly define "almost surely' regarding activation functions, let restrict the activation function or to belong to the space Q of polynomials of order at least n², that is:
K 7k x
(()
(191)
with n² & K < +00, and non-O highest-order amplitude γk # O. This set P is dense in the set of all continuous functions over the set Q = [-TM, which is a hypercube of sufficient radius I' to cover all samples from the given dataset. One can define probability distributions over P, for instance consider o the density p(a) = 인 II v2n with a factor a = - E
to normalize the distribution, and where K is the order of the polynomial and thus depends o. This density is continuous in the space of parameters 7' (though not continuous in the usual functional metric spaces). Note that the decomposition of any a E B as a finitc-order polynomial is unique, as monomials of different orders are lincarly independent.
We can now state the following lemma (that we will prove later):
Lemma D.1 (Invertibility of the activation matrix). Let D = (z,, 1 n be a dataset of n distinct points, and let a R + R be a function in Q, that is, a polynomial of order at least n². Then with probability over function and neuron porameters (7x), (w,) and (by), the activity matriz A defined by Aij = o(u, x, bb,) is full rank.
and the following proposition:
Proposition D.4 (Reaching O training error in at most n neuron additions). Under the assumptions above (polymomial activation function of order > n², full-batch optimization and computation of the optimal moves of already existing paramelers), completed- TINY reaches 0 training ervor al most n. neuron additions almost surely.
Proof. If the growth mothod 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.] that the activity matrix A, defined by A. = ( z; + by), indexed by samples and neurons j, is invertible. Then there exists a unique w E F" such that Aw f", i.e. Σj (,, æ; by) = fa((x,) for each point æ; of the dataset. This vector of output parameters realizes the global minimum of the loss over already existing weights: inf [(fo,w) inf | 11 They are also the ones found by 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.
Note: piccewise-lincar 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 ReLUU 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 and given param- eters by), 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 0g 0y x. + by are not distinct for all i,j, then an infinitesimal variation of the vectors Uy can make them distinct. For this, one can see that the set of directions vy on which any two dataset points æ; and By have the same projection is finite (since has to be the direction of æ; wy for a given pair of dataset samples (i,)') and thus of measure O. As consequence with probability 1 over neuron parameters By and bj. 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 5A to apply to A to make invertible. This corresponds to changing the activation function accordingly at each of the n² distinct pre-activity values. Since has more than n² parameters, this is doable. For instance, one can select the n² first parameters and search for a suitable variation g (ork)o of them by solving the linear system Sg 8A where the n² x n² matrix S is
45

---

Published in Transactions on Machine Learning Research (lune/2024
defined by Siy.k = oi. = (vy z, + b,)a This matrix S is invertible because any g such that Sg 0 would induce:
Vi,
87 at. =0
(192)
and thus the polynomial P(x) 21 -k=0 8yk x has at least n² roots while being of order at most n² 1. Thus gg 0 = g == 0 and S is invertible. Note that as AA is infinitesimal, g S 5A will be infinitesimal as well, and so is the change brought to the activation function o.
Consequently we have that the set of activation functions a and neuron parameters (wy, by) for which the matrix is full rank is dense the set of polynomials & of order at least n² and of neuron parameters n.
Now, the function det: #x x 97 IR, ((T+)R; (vj, + det A det (ay(w) xz + bz)) is smooth as a function of its imput parameters (the determinant being polynomial function of the matrix coefficients). As this continuous function is non-O open subset. This is not yet sufficient to prove that this pre-image is of measure 0 (e.g., fat Cantor set).
dense set of its inputs, the pre-image det is closed and contains no
For a fixed order K, one can see this function as a polynomial of its inputs "kk and vy. bj, and conclude that the set its roots is of measure O. As a consequence, the probability, over coefficients 7kk or equivalently over polynomials a of order K, that det 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, L.e. Exyne F 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 ''dnd S-1/2N computed using 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 onto the span of the activities noted X. We suppose we have the following setting:
Y ~ AX+ E~~(0,00) E|s|X] 0
(193)
where the (X,, Yi) are i.i.d. and A is the oracle for M or matrix S-1/2N. If Y is multidimensional, the total variance of our estimator can be seen as the sum of the variances of the estimator on cach dimension of
We now suppose that Y e R and note A: (XX") the solution of 193 We first remark that Ax YP with P P= X x E R(m,n). It follows that when < 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 Ax. In practice, we do not consider < p as the solution (&W or A, 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)= = and YP Y. We now study the variance of the estimator A E RR. We have almost surely that XXT is invertible and note (XX)-1 its inverse. Taking the expectation on variable E, we have cov(A) = o² ( If is large, and matrix T + Q, with Q non-singular, then, asymptotically, we have À ~ (VAA 20-) which is equivalent to (Á- - A) va Q1/2 ~ T). Then [I(Á A) th 11/2112 ~ (k) where k is the dimension of X. It follows that E [I(Á 111 ko? and as 1//2Q1/2" is positive definite, we conclude that var(Á) < m (Q)
kg
2 See for instance proof by recurrence that roots of a polynomial are always of measure https: http:///ast.sttckkeccanngg com/ htt//uussioon//19220////// thee-eeesgue lebeesue-measure- measure- of-zero- setrro-setoo-ssee w-w.-ooooaoollaaaa-loooao funciitioo--------- is-zero
46

---

Published in Transactions on Machine Learning Research (June/ 2024))
In practice we aim 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 T2 we estimate matrix of size k + (SW)². For n images, as each input sample contains P quantities, and that each is a realization of the random variable (total nP variables), we have total n +- nP data points for the estimation of the best neuron. Hence lo add new neurons with a (asymptotically) fixed variance, we use batch size
(SW)2 P
n X
For convolutional layers, take 0.001 (SW) 2 (Figure 50 and 0.01 (SW)² 2 (Figure
P
where & is equal to / 32xx32, and this 2 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 BBeh in Equation 55
P
E.2 Batch size for learning
We adjust the batch size for gradient descent as follows: the batch size is set to b;=0 = 32 at the beginning of each experiment, and it is schoduled to increase as the square root of the complexity of the model (í.e. number of parameters). If at time the network has complexity C₁ parameters, then at time I +++ 1 the training batch size is equal to b411 b,
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 Evei et al. (2022), i.e.
a 0
(194)
10-3
for Figures and
w +- wt
(195)
[[(3)
1/ 113/nd
10-3
for Figure 16
W +- w x
(196)
[[(]] د 12/na
For TINY method of both figures, the previous normalization process is mimicked by normalizing the and out going weights by their norms and multiplying them by v10- i..
10-3
Ok f- or x
(197)
[Ma;))=111
ndd
10-3
Wh + wi x
(198)
Maw
E.3.2
Figure 8 Amplitude Factor
For the Random and the TINY methods of Figure g we first normalize the parameters as
For the new neurons
For the best update
03 ox
W
W x
1//d
w wh
/ /1(w7) 1B/ma
47

---

Published in Transactions on Machine Learning Research (June/ /2044)
Then, we multiply them by the amplitude factor 7
For the new neurons
For the best update
wi t ajj"" wiT"
Wi 7
>" = arg min
Σ [ioorog (z.). y:)
7" = arg min 7E L.I..
[(fot-w-(az))
7El [.]-
where the operation -0 (ro TwEh is the concatenation of the neural network with the new newrons and 0 v is the update of one layer with its best update. The batch on which y 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 and 8 The function New.Neurons()),
in Algorithm 2 computes the new neurons defined at Proposition 3.2 for layer sorted by decrcasing cigen-
values. The function BestUpdate(l), in Algorithu computes the best update at Proposition 3.1 for layer L.
A Algorithm 1: Algorithm to plot Figures and
for each method [TINY, Method'ooComprr With do Start from neural network N with initial structure s (1/4, 1/64); while N architecture does not match ResNet18 width do for in {depths to grow) do gx" NewNNeuonss(d method) Normalize 8% according to E.3
6
7
Add the neurons layer d Train N for At epochs:
Save model N and its performance;
10
end
11
end
12 end
48

---

Published in Transactions on Machine Learning Research (June/ /2044)
Algorithm 2: NewNeurons
Algorithm 3: MatrixSN
Data: 1, method TINY
Data: P1.P2 (layer indexes), M = None
Result: Best neurons
Result: Construct matrices S and N
if method TINY then
Take a minibatch X of size x P
(SW)?
M BestUpdateel + 1);
Propagate and backpropagate X:
S,N = MatrixSN(1 1,/ 1, M);
Compute V goul at P2, i.c. ac
Compute the SVD of S OΣO%; Compute the SVD of
dApz
if M + None then V gool MBp. p1
OVE ON AAΩ2 Use the columns of A, the lines of Z and the diagonal of A to construct the new neurons of Prop. 3.2
end
S.N Bp, Bp T Bp goal T
else if method GrodMaz then
M = None
Algorithm 4: BestUpdate
N = MatrixSN(1 1,1 1, M)
Data: I, index layer
10
Compute the SVD of NTN;
Result: Best update at
11
Use the eigenvectors to define the new out-going weights;
Take minibatch X of size (sW), Compute (S,N) with MatrixSN(,, l);
12
Set the new in-going weight to 0;
M = S-1;
13
else if method = Random then
14
(oe, wk) Ra ~ Id,
15 end
E.5
Computational complexity
We estimate here the computational complexity of the above algorithm for architecture growth.
Thcoretical 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 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: TMLSW2P
of the computation of matrices of interest (function MatrixSN); LSW(SW))PP
of SVD computations (function NewNeurons): L(SW)3
of Tine-searches (function AmplitudeFacctor:: SW22
49

---

Published in Transactions on Machine Learning Research (June/ 2004))
P = 1 4
W
W
W
P
Figure 12: Notation and size for convolutional and linear layers
of weight updates (function Best LSW
The relative added complexity w.r.t. the standard training part thus:
M'S /M + SW/TMM + M TM + 1/WTMP.
SVD cost is negligible. The relative cost of the SVD w...t. the standard training part is S /TMP. In the fully-connected network case, S =, P= and the relative cost of the SVD then W/TM. is then negligible, as layer width W is usually much smaller than TM, which is typically 10 x 100 for instance. In the convolutional case, the SVD cost is negligible long as layer width W 10000 or 000 000 respectively. So one needs no worrying about SVD cost.
for 3 kernels, and 1000 for CIFAR, P v 100000 for ImageNet, so
Likewise, the update of existing weights using the "optimal move' (already computed as 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 more ressource-demandingg The factor M' S/TM can be large if the minibatch size M' needs be large for statistical significance reasons. One can show that an upper bound the value required for M' to ensure estimator precision (see Appendix E.1 is (P. In that case, if W /TMP/S3 these matrix estimations will get costly. In the fully- connected network case, this mcans W > VTM = 30 for T this means W > /TMP/53 30 for CIFAR and ss 300 for ImageNet. We are working on finer variance estimation and other types of estimators to decrease M' and consequently this cost. Actually (SW) is just an upper bound on the value required for M', which might be much lower, depending on the rank of computed matrices.
and M 100. In the convolutional case,
In practice. In practice the cost of full training with our architecture growth approach is similar (some- times bit faster, sometimes a bit slower) than a slandard gradient descent training using the final ar- chitecture from scratch. This great as the right comparison should take into account the number of different architectures try in the classical neural architecture search approach. Therefore we get layer width hyper-oplimization 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 g The experiments were performed on 1 GPU. The optimizer is At each depth we set the number ny of neurons to be
SCD(Ir le- with the starting batch size 32
2
50

---

Published in Transactions on Machine Learning Research (June/ 22044)
2 These numbers do not depend 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 == 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 n2 (Size) final Sizestart) of layer extensions = (64 16)/16 (64 - 1) 21 3. The
added this depth
initial architecture is described in Table 3
depth
Conv2
Conv3
Conv5
Conv6
Conv8
Conv9
Conv11
Conv12
14
12
12
24
24
Table 2: Number of neurons to add per layer. The depth is identified by its name on 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 [Lu et al. (2019) ) NORTH Maile et al. (2022) GradMax (Evci et al. (022 )) and TINY. We use the adjective grudient-bused when the method uses the information from the propagation of the loss 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 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 lot terms of methodology, growth process, and neuron initialization (cf. B). Nonetheless, NORTH search time complexity is much larger for each increase of architecture its strategy relies trial-and-error methodology (going up 1000 generations before actually increasing the architecture).
The time search complexity of TINY will always be slightly higher than GradMax as needs project the desired update and compute the matrix S (cf
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 create the graph.
51

---

Published in Transactions on Machine Learning Research (June/ 2204))
architecture growth TINY
starting architecture 1/4
starting architecture: 1/64
1.0
1.0
train
test
test
At = epoch
0.0
10
parameten
Accuracy
0.8
0.6
0.6
0.4
0.4
02-
nbr parameterss
nbr har_parameters
0.0
0.0
2500
5000
7500
10000
12500
15000
17500
2000
4000
6000
8000
10000
12000
14000
167
167
12
train
test
0.8
0.8
10
= epoch
nbr 0
Accuracy
0.8
0.6
0.4
0.2
02
perrperrmeterss
0.4
rbr_perrmmters
10000 20000
50000 60000 7000
20000
30000
40000
50000
gradient steps
gradient steps
architecture growth GradMax
starting architecture 1/4
starting architecture 1/64
107
167
train
1.0
train
12
= 0.25 epoch
0.8
0.8
10
nbr carameten
Accuracy
0.8
0.8
0.6
0.4
0.4
0.6
02
nbr parameters
0.0
0.0
15000 17500
12000
24000
1.0
sast
12
1.0
train
test
12
At 1 epoch
Accuracy
0.6
0.6
0.8
0.8
0.6
0.
0.2
0.2
02
nbr pou_parrmeters
nbr shr_parameters
0.0
0 10000 20000 30000 40000 50000 60000 70000
10000
20000
30000
43000
50000
gradient steps
gradient steps
Figure 13: Accuracy and number of parameters during architecture growth for methods TINY and GradMax function of the gradient step. Mean and standard deviation for four independent runs.
52

---

Published in Transactions on Machine Learning Research (June/2024)
Extra Training TINY
Starting architecture 1/4
Starting architecture 1/64
1.0
1.0
=t 0.25
Accuracy
0.8
0.6
0.6
train
test
0.4
0.4
100
200
100
1.0
1.0
=t= Accuracy
0.8
0.8
0.6
0.6
0.4
0.4
0
100
200
0
100
200
epochs
epochs
Figure 14: Accuracy as a function of the number of epochs during extra training for TINY on four independent runs.
Extra Training GradMax
Starting architecture 1/4
Starting architecture 1/64
1.0
1.0
=t 0.25 Accuracy
0.8
0.8
0.6
train
0.6
test
100
200
200
400
1.0
=t=1 Accuracy
0.8
0.8
0.6
0.6
0
100
200
0
200
400
epochs
epochs
Figure 15: Accuracy curves as a function of the number of epochs during extra training for GradMax on four independent runs.
53

---

Published in Transactions on Machine Learning Research (June/2024)
Table 3: Initial and final architecture for the models of Figure 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 indicates that the model 1/64 started with 1 neuron at this layer while the model 1/4 started with 16 ncurons at the same layer.
ResNet18
Layer
Output size
Initial layers (kernel=(3.3), padd.=1)
Final layers (end of Fig 5
Conv 1
32 32 64
xx 3,
3, 64
x 3, 64
x 3, 1/16
3 x 3,64
3, 64
Conv 2
32 x 32 64
3 x 3, 1
x 3, 64
3 x
3 3,
3,6 64
3 x 3, 1/16
3 x 3,64 64
3 x 3,64
Conv 3
32 x 32 x 64
3 x 3, 1
x 3, 64
3 x 3, 64
3 3, 64
Conv 4
16 x 16 64
128
128
128
3 x 3, 2|32
3 x 3, 128
x 3, 128
Conv 5
16 x 16 128
3 x 3, 2/32
3 3, 128
3 x 3, 128
3 x 3, 128
3 x 3, 128
3 x 3, 2|32
3 X 3, 128
x 3, 128
Conv 6
16 16 128
3 x 3, 2
3 3, 128
3 x 3, 128
x 3, 128
Conv 7
8 x x 256
3 x 3, 256
3 x 3, 256
3 x 3, 256
3 x 3, 4/64
3 x 3, 256
x 3, 256
Conv 8
8 256
3 x 3, 4/64
3 x 256
3 x 3, 256
x 3, 256
x 3, 256
x 3, 4/64
3 x 3, 256
x 3, 256
Conv 9
8 x 256
3 x 3, 4|64
256
3 x 3, 256
3, 256
Conv 10
4 512
x 3, 512
x 3, 512
x 512
3 x 3, 128
3 x 3122
x 3, 512
Conv 11
4 4 x 512
3 828
3 3, 512
3 512
3, 512
3,51 512
3 3, 8128
3 3,512
512
Conv 12
4 x x 512
3 x 328 128
3 x 3, 512
3 x 512
X 3, 512
AvgPool2d
1 x x 512
FC
100
512 x 100
512 x 100
SoftMax
100
54

---

Published in Transactions on Machine Learning Research (June/2024)
starting architecture: 1/64
0.70
TINY
GradMax
0.60
Delta t = 1 epoch
Accuracy test
0.50
0.45
0.35
0.2
0.4
0.6
0.8
1.0
1.2
nbr parameters
1e7
Figure 16: Accuracy on test split as function of the number of parameters during architecture growth from Res to ResNet18. The normalization for GradMax is v10-3.
At =1
Baseline
TINY
GradMax
68.1 + 0.5
57.2 1: 0.3
s 1/64
72.84 0.3 5x
68.7 + 0.6 3*
57.7 0.3 3+
Table 4: Final accuracy Lest 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 /04 and At = the method TINY achieves 68.1 0.5 on test split after its growth and it reaches 68.7 + 0.6 5 after * == 5 x 50 epochs.
Indicators
Method
Dataset
Arch.
Time
Acc.
97.0
CIFAR-10
X
6.5
97.8 + 0.1
DARTS
4
73.3
ImageNet
VGG-11
3.3
76.4
CIFAR-10
NORTH
ResNet-25 28
0.4
83.3
VGG-11
1.6
~ 55.7
CIFAR-100
Al = 0.25, 1/64
ResNel-18
0.12
45.0 + 0.4
GradMaxt
At 1, 1/64
ResNet-18
0.26
56.8 + 0.2
CIFAR-100
Al = 0.25, & 1/64
ResNet-18
0.13
65.8 +
T
At 0.1, s = 1/64
ResNet-18
0.28
68.1 + 0.5
Table 5: Time: GPU days spent to search for the architecture and to train it. Acc.: accuracy 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.
55


Reviews:
[{"review_id": "yg4jhMx7uU", "reviewer": "Reviewer_VRpd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The paper is well written. The paper does a good job of explaining the difference between $\\mathcal{v}$ and $\\mathcal{v}_{\\text{goal}}$ (shown in Figure 2).\n* The paper includes appendices for details like functional gradient descent, parametric gradient descent, expressivity bottleneck examples, and extensions of their proposed method to convolutional layers.\n\nWeaknesses:\n* The experiments do not do a good job of demonstrating the method. The paper talks about being able to adapt architecture on the fly during training and the importance of searching architecture hyperparameters but in the experiments TINY is used to grow a ResNet-18 from 1/4 and 1/64 the width to the full size. The experiments don’t demonstrate the ability for the method to find an optimal architecture.\n* In the abstract, introduction, and contributions, the authors talk about the importance of training time and computational resources. However, there is no comparison of training times or computational resources in the main paper. \n* Another weakness related to training time and computational resources is the lack of discussion of alternative methods. Using TINY to grow a ResNet-18 achieves similar performance to a ResNet-18 trained from scratch on CIFAR-100 but practitioners with limited compute looking to achieve high performance on CIFAR-100 would likely reach for a pre-trained model and use methods from transfer learning like linear probing or fine-tuning to achieve high performance at little cost.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new method for growing neural networks. The proposed method, TINY, includes a mathematical definition of expressivity bottlenecks, which enables an optimal solution by adding neurons. The authors take a functional perspective of training neural networks which allows them to present a mathematical definition of expressivity bottlenecks. The expressivity bottleneck (shown in Figure 2) is the L2 norm of the parametric gradient $\\mathcal{v}(x) = -(\\nabla_\\theta \\mathcal{L}(f_\\theta))(x)$ minus the functional gradient $\\mathcal{v}\\_{\\text{goal}}(x) = -(\\nabla_f \\mathcal{L}(f))(x)$. On CIFAR-100, the proposed method achieves better performance and converges faster (when starting with smaller architectures) than GradMax (Evci et al., 2022), a baseline for growing neural networks most comparable with TINY.\n\nUtku Evci, Bart van Merrienboer, Thomas Unterthiner, Fabian Pedregosa, and Max Vladymyrov. GradMax: Growing Neural Networks using Gradient Information. In *International Conference on Learning Representations* (ICLR), 2022.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* See weakness.\n* It would be nice to see a comparison with Xavier initialization (Glorot and Bengio, 2010) in Figure 8. Also should $d$ in the Gaussian distribution for initializing new neurons be a subscript? This seems like a large variance to be initializing neurons with.\n\nXavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In *Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics (AISTATS)*, 2010.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "v1tG2GpncA", "reviewer": "Reviewer_jtZt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n - The way of formulating expressivity bottlenecks, based on the functional gradient, is an interesting perspective and could potentially be useful for other works studying related questions.\n - The proposed method outperforms the baseline of GradMax.\n\nQuestions:\n - In practice with neural networks, how often is there a nonzero expressivity bottleneck?  If we have a  hidden layer with dimension $h$, and there are $n$ data points in a minibatch, then the functional gradient is just a vector of size $h n$, and if the layer has more than this number of parameters, shouldn't there be zero expressivity bottleneck?  If my math is wrong, is there a different dimension-counting argument that one could use to reason about when we expect to see an expressivity bottleneck?\n - The paper needs to more clearly state, in the main paper (rather than the appendix), what is the overall algorithm being used to train the network.   Section 3.2 tells us how to add a specified number of neurons to a specified layer, but it is left unclear how to leverage this to train a network.  Do we keep looping over the layers, from first to last, over and over again?  How do we know how many neurons to add to each layer?  In addition to pseudocode in the appendix, there should be a description of the overall training algorithm in English in the main paper.\n - in section 3.2, given that $\\delta \\mathbf{W}$ is ultimately taken to be the best move of the already-existing parameters, is there a good  reason to initially say that your goal is to _jointly_ optimize  $\\delta \\mathbf{W}$ and $\\theta^K_\\leftrightarrow$, as in equations (6), (7)?\n - I did not understand section 5.2, starting with the first sentence: \"in this section, we focus on the impact of the new neurons' initialization\".  What is meant by \"initialization\"?  Aren't we tuning the neurons as we add them?\n\nMinor issues:\n  - the second-to-last paragraph on page 2, beginning with \"In this article\", is very confusing to read.  One improvement would be to take away \"aim at\" => \"In this article, we measure lack of expressivity...\".  But the sentence should probably be split up into several smaller ones.\n - top of page 3 has a typo - \"enables the localize expressivity bottlenecks\"\n - in page 4, it would be good to state explicitly that $T_\\mathcal{A}^{f_\\theta}$ is a set of functions.  In general, it would be better throughout this section to consistently clarify the 'types' of all the symbols, provided that this can be done without using excessive notation.\n - in page 5, \"the solution of 4\" should be \"the solution of (4)\"\n\nSuggestions (feel free to ignore): \n - I think the paper would be considerably improved if section 1 were split into separate introduction and related work sections.  The paper currently spends a lot of time talking about loosely related prior works before it mentions its actual contributions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies how to grow neural networks by adding neurons.  The paper first formalizes the notion of an 'expressivity bottleneck' -- a layer that is currently not expressive enough to represent the desired function.  It then proposes a method for adding neurons so as to fix expressivity bottlenecks.  The paper proves that an instantiation of this method provably yields global convergence of the training objective   Finally, it is shown that the algorithm improves over the baseline GradMax in the narrow-width regime.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "please see questions above", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "smrj6GhoXX", "reviewer": "Reviewer_pEe5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nDespite the existence of prior work on growing neural network, the paper's proposed method is novel. Notably, the theoretical analysis of the method is comprehensive, and one of the paper's biggest strengths. The experiments are also thorough and adequate to validate the theory.\n\nThe paper is quite well written. Concepts are gradually presented and well motivated, and explanations and notations are thorough. The authors make great use of text coloring throughout the paper.\n\n**Weaknesses**\n\nIn my view, the paper has few weaknesses. The main one in my view is that the experiments only test on one dataset, CIFAR-100. I would encourage the authors to include results on a more complex dataset as well, such as ImageNet. It would also be helpful to include an additional baseline, in addition to GradMax.\n\nMinor comments:\n- In some experiments, mean and std are only computed over two runs; please increase to at least four\n- Please use booktabs style tables", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a novel method of growing neural networks. The method aims to add parameters to a network so as to move the network in the direction of the functional gradient. The authors demonstrate theoretically that their method can eventually interpolate the training set with sufficiently many parameters added. Experiments demonstrate that the proposed method outperforms a baseline on CIFAR-100.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Would strengthen**\n- Please add another dataset such as ImageNet\n- Please compare with an additional baseline method\n- In some experiments, mean and std are only computed over two runs; please increase to at least four\n- Please use booktabs style tables", "broader_impact_concerns": "No broader impact concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers were unanimous in their recommendation that the paper be accepted.  Certain critiques were raised, and the authors addressed many of them during the discussion.  One point which remains is the breadth of experimentation---the committee felt that for a paper claiming to contribute to computational efficiency of neural network training, larger scale experiments are in order.  I encourage the authors to pursue this route in follow up work.
Decision: Accept (poster)