Spotting Expressivity Bottlenecks and Fixing Them Optimally 
Authors: Manon Verbockhaven
Guillaume Charpiat
Venue: Submitted to ICLR 2023 (2023)
Keywords: neural network
expressivity
optimization
quadratic programming
layer growth
tangent space
gradient

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 possible 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 the back-propagation.  To do this, we propose a new mathematically well-grounded method to detect expressivity bottlenecks on the fly and solve them by adding suitable neurons when and where needed. Thus, while the standard approach requires large networks, in terms of number of neurons per layer, for expressivity and optimization reasons, we are able to start with  very small neural networks and let them grow appropriately.  As a proof of concept, we show convincing results on the MNIST dataset, matching large neural network accuracy, with competitive training time, while removing the need for standard architectural hyper-parameter optimization.


Under review as a conference paper at ICLR 2023
SPOTTING EXPRESSIVITY BOTTLENECKS AND FIXING THEM OPTIMALLY
Anonymous authors Paper under double-blind review
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 possible 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 the backpropagation. To do this, we propose grounded method to detect expressivity bottlenecks on the fly and solve them by adding suitable neurons when and where needed. Thus, while the standard approach requires large networks, in terms of number of neurons per layer, for expressivity and optimization reasons, we are able to start with very small neural networks and let them grow appropriately. As proof of concept, we show results on the MNIST dataset, matching large neural network accuracy, with competitive training time, while removing the need for standard architectural hyper-paramete search.
mathematically well-
INTRODUCTION
Issues with the fixed-architecture paradigm. Universal approximation theorems such as Hornik al.) (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 parameterized space of functions to be used 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, expressivity bottlenecks that might arise in given layer during training will not be able to be fixed. There are two approaches to circumvent this in daily practice. Either one chooses (very) large width, to be sure to avoid expressivity issues (Hanin & Rolnick] 2019b Raghu et al. 2017), but then consumes extra computational power to train such big models, and often needs to reduce the model afterwards, possibly using probabilistic edges (Liu al. 2019). Or one tries different architectures and keeps the most suitable one (in terms of performance-size compromise for instance). which multiplies the computational power by the number of trials. This latter approach relates to the Metto-DDeeLaaammtene space of architecture hyper- pyper-parameters (among other ones) have been tested, including reinforcement learning (Baker et al. 2016), and evolutionary approaches (Miller et al. 1989) (Miikkulainen et al. 2017). that rely on random tries and consequently take time for exploration. Within that line, Net2Net (Chen et al. 2015), AdaptNet (Yang et al. 2018) and MorphNet (Gordon et al. 2018) propose different strategies to explore possible variations of 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,
field, where different exploration strategies over the
Zoph & Le 2016). Bayesian optimization techniques (Mendoza et al.)

---

Under review as a conference paper at ICLR 2023
aim modifying the architecture the fly during training, in single run (no re-training), using first-order derivatives only, while avoiding neuron redundancy.
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, Wu al. (2019) and 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 by solving quadratic problems involving second-order derivatives. Another example is GradMax (Evci et al. 2022), which seeks to minimize the loss as fast as possible and involves another quadratic problem. However the neurons added by these approaches are possibly redundant with existing neurons, in particular if one does not wait for training convergence to local minimum (which is time consuming) before adding neurons, therefore producing larger-than- teedded architectures. On the opposite we will explicitly take redundancy into account in our growing criterion.
Optimization properties. An important reason for common practice to choose wide architectures the associated optimization properties: sufficiently larger networks are proved theoretically and shown empirically to be better optimizers than small ones Jacot et al. (2018). Typical, small networks exhibit issues with spurious local minima, while wide ones usually find good nearly-global minima. One of our goals is to train small networks without suffering from such optimization difficulties.
ones|acot
Notions of expressivity. Several concepts of expressivity or complexity exist in the Machine Learning literature, ranging from Sapnik-Chervonenkee dimension and Rademacher complexity to the number of pieces in a piecewise affine function (as networks with ReLU activations are) |Serra al. (2018): Hanin & Rolnick (2019)). Bottlenecks have been also studied from the point of view of Information Theory, through mutual information between the activities of different layers Tishby & Zaslavsky 2015); this quantity is difficult to estimate though. Also relevant and from Information Theory, the Minimum Description Length paradigm and Kolmogorov complexity enable to search for compromise between performance and model complexity.
In this article, we aim at measuring lacks of expressivity as the difference between what the back- propagation asks for and what be done by a small parameter update (such gradient step), that is, between the desired variation for each activation in each layer (for each sample) and the best one that can be realized by a parameter update. Intuitively, differences arise when a layer does not have sufficient expressive power to realize the desired variation. Our main contributions are that we:
take a functional analysis viewpoint over gradient descent on neural networks, suggesting to attempt to follow the functional gradient. We optimize not only the weights of the current architecture, but also the architecture itself on the fly, order to progressively move towards more suitable parameterized functional spaces.
properly define and quantify the notion of expressivity bottlenecks, globally at the neural network output as well as at each layer. and this in an easily computionable way. This allows to localize the expressivity bottelenecks, by spotting layers with great lacks of expressivity;
mathematically define the best possible neurons to add to a given layer to decrease lacks of expressivity quadratic problem; compute them and their associated expressivity gain;
check that adding these best neurons is better indeed than adding random ones;
are able to train a neural network without gradient descent (yet still relying on backpropaga- tion) by just adding such best neurons, without parameter update;
naturally obtain series of compromises between performance and number of neurons, in a single run, thus removing the need for layer width hyper-optimizzttonn. and this in competitive computational complexity with respect to classically training large model just once. One could define a target accuracy and stop adding neurons when it is reached.
2 NOTATIONS AND DEFINITIONS
2.1 NOTATIONS
We consider feedforward neural network with 7. hidden layers, fo : RP - RRd. where the parameters
2

---

Under review as a conference paper at ICLR 2023
8 = (W1,..., W2) organized into affine layers followed by activation functions dy. We denote the dataset by D == {(11, y1), .... (æ yN)}, with X RP and y; R", and the loss function by L. We will assume that is differentiable at 0 and that L is differentiable on R and that oz 0. Except Part 3.4 the dataset 'D is fixed. The network iteratively computes:
b1
al
bj
bu(x)) - (41) (1(2)) = (ib)-1(at) bi(0)) = [7 (o((a())))
(())(((()()
0
with fo(z) σ (a)(()))) To any vector function noted t(x) and any batch of inputs X == [a.,..., Enl. we associate the concatenated matrix ( == (t(x1)
t(x,)). The matrices of pre-activation and post-activation activities at layer over mini- batch X are thus respectively (x = (a)( (1(2,))
W1
and (X) (br(wr1) baan))
Figure
Notations
2.2 APPROACH
We take a functional perspective on the use of neural networks. Ideally in machine learning task, would search for function f R² - Red that minimizes the loss by gradient descent: 0f v for some metric the functional space F (typically, I2). where V, denotes the function of decrease the loss.
functional gradient. For a chosen > 0, the descent direction Ugeal == V ((f) is
the same type as f. indicating the best infinitesimal variation add
In practice, to compute the gradient, a finite-dimensioned parametric space of functions is considered
by choosing particular neural network architecture with weights 0 O The associated parametric search space FA then consists of all possible functions fe that can represented with such network for any parameter value 6.
Gradient descent reminder. For the sake of simplicity, let us consider loss of the form L(J) ((yy)>D [()())),) v) Under standard weak assumptions AA and up to multiplicative learning rate, the gradient descent then of the form:
00 = VoC(f) = (2.9)~
VoL(fo(z). v)
0t
Using the chain rule, this yields a function change
Ofe 0fe 00 ff
Ofe 00
VGD = 17 Ot 00 Ot
(x)
yg (x)
de
(a.D)
Optimal move. We name 5o or just TA the tangent space of Fu at fe, that is, the set of possible infinitesimal variations around fo under small parameter variations: TH == d6 d0 s.t. 50 E θ}. This linear space is first order approximation of the neighborhood fo within Fx.
Functional gradient
expressivityy bottlensok
1 gual
fo
Projir, (Upaa)
TA
optimal with the current architecture
The direction VoD obtained above by gradi- ent descent actually not the best one to consider within TA- Indeed, the best move v² would be the orthogonal projection of the desired direction Ugaal ; -n ((fe) onto TA. This projection depends on the chosen metric and is what (generalization of the notion of) natural gradient computes (Ollivier 2017).
FE
Figure 2: The expressivity bottleneck is measured the difference between the optimal functional move v" given the architecture A and the func- tional gradient gooal- The former the projection of the latter onto the tangent space TA-
3

---

Under review as a conference paper at ICLR 2023
Lack of expressivity. When ,, does not belong to the reachable subspace TA, there is 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.
Example. Suppose
tries to estimate the function y ftrue (z)
2 sin(2) + x with a linear model fpedicr(()) = az + Consider (a, b) (1, O) and the square loss C. For the dataset of inputs (Io, 2 22, 2z) (0, 1.5, и, 4.5), there exists no parameter update (õa, 8b) that would im- prove prediction at 20, 21, 22 and Iy simultaneously, the space of linear functions {f x or +
a, E IR is not expressive enough. To im- prove the prediction æo, 2 32 and I3,, one should look for another, more expressive functional space such that for i = 0, 1, 2, 3 the functional update goes into the same direction as mi- nus the functional gradient Ugoal (I;) == V (p, [[ (I:), Vi) -1 (fredii - yii where y/ = Jime((ra))
A frrdiie (z4) := predice Sprodicr
Figure 3: Linear inter- polation
2.3 UPDATING LAYER ACTIVITIES
Ideal updates. The same reasoning can applied to the pre-activations a, seen as func- tions defined over the input space of the neural network. The optimal update of the weights of the different layers is then the projection of the desired update direction of pre-activation functions, i.c V, aV,,((f)) C(f)), obtained by back lack-propagation onto the linear subspace TA of pos- sible variations within the architecture, Training a neural network is usually done by gradient descent, which consists in updating the weight matrices Wi recursively using back-propagation. More precisely, the gradient of the loss w.r.t. WI,, is the product of the backpropagation from the loss L till layer preactivations ai(x) and of the layer-specific derivative from these preactivations till the weight in question: (x)(x) aW?
will detail now just like in the intuition part.
(x)) The opposite of the second term times v the positive real number, (x) == n) (.
Vul (oL
= (a))) indicates the desired update direction for (x)) Mathematically speaking, if at time t any activity update were possible at each layer we would choose + the pre-activation function updates such that for all samples i == I,...,th
(a,( (x;) - (x,)) -n a, a, (W
y) (a,, y) (xx, y:) (1)
Unfortunately, most of the time no parameter move 50 is able to induce this progression for each æ; at the same time, because the 0-parameterized family of functions is not expressive enough. Intuitively the ideal update above does not result from a parameter update but from an update of the pre-activation functions in their functional spaces. Following this ideal update rather than the classical gradient descent would optimally decrease the loss, with an order-1 effect in r) provided the gradient is non-O. Unlike this ideal update, the classical gradient descent decreases the global loss first order in y but does not necessarily improve the prediction for all æ;-
For the rest of the paper we will note oyoal (x:) == 1/ a ((F(())))))) (z.
Activity update resulting from parameter change. Given subset of parameters 0, an incre- mental direction 50 to update 0, and amplitude n7 0, the impact of the parameter update 50 on the are-aitivity a; at layer at order in 80 is v oa(x,, 60) = da 80.
a0
Remark 1. We could have choose to study the desired update for b, our choice for a; is explained in section A.2
3 EXPRESSIVITY BOTTLENECKS
We now define expressivity bottlenecks based on the activity updates, both actual ef (.) and desired vl yyoal (-) ones (cf Figure
4

---

This update OW; is not equivalent the usual gradient descent update, whose form is dWWGD x V! B In fact V is the projection of VL on the post-activation matrix of layer / that is say onto the span of all possible directions from post-activation, through the projec- 1 BT_ ( B B ) B To increase expressivity needed, we will aim at increasing this span with the most useful directions close the gap between this best update and the desired one. goul B and of a (kind of) natural Under review as a conference paper at ICLR 2023
Definition 3.1 (Lack of expressivity). For neural network fo and a minibatch of points {aa,, y:) we define the lack of expressivity at layer I as how far the desired activity update gool from the closest possible activity update realizable by a parameter change 80:
min
10' - (x;0
min 66
[| 60) Vidaa (X)
(2)
where ||-I] stands for the L2 norm and I1 for the Frobenius norm.
In the two following parts we fix a minibatch {(x,, y:) Hi)HE i.e. subset of the full dataset D.
As X
V 1 Ii..... Øi] is then fixed, we simplify the notation: Ar == Ai(X), B == Bi(X),
V
3.1 BEST MOVE WITHOUT MODIFYING THE ARCHITECTURE OF THE NETWORK
Let oW, be the solution of 2 when the parameter variation d0 is restricted to involve only layer I parameters, i.e. Wi. This move sub-optimal that it does not result from an update of all architecture parameters but only of the current layer ones:
SW
arg min (NE
(
V goal
I
(3)
where (M: I) the set of matrices of size k i.e. here of the size of Wi. We denote by Vo the associated activity variation:
Vo = 8W,
(x,) Sw, (x;)
Proposition 3.1. The solution o and its associated activity variation are:
swi
1 vil nI
goul BT (
where P- denotes the generalized inverse of matrix P.
tor a
Note that the update OW, consists of standard gradient (Vil
gradient only for the last part (projector).
3.2 REDUCING EXPRESSIVITY BOTTLENECK BY MODIEYING THE ARCHITECTURE
To get as close as possible to V-+1 and to increase the expressive power of the current neural network, modify each layer of its structure. At layer we add K neurons 7i 11,..., 1k with input weights a1...., ag and output weights Wi...., WK (cf Figure 4). We have the following change W1
goal
W," - (WT a1
αk) and WI+1 (W1+) 1+1
wx).
We note this modification architecture 0 + 0 e 0 (est+1 where @ is the concatenation sign and 0K 0 = (ars, ) are the added neurons.
The added neurons could be chosen randomly, in usual neural network initialisation, but this would not yield any guarantee regarding the impact on the system loss. Another possibility would be to set either input weights (ox) or output weights (w 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 f + @ 0 0 and jointly search for both the optimal new parameters 0KK 0 and the optimal variation ò W, of the old ones.
O, so that the function f.(.)) would not be
Veoal H+1 - vi+ ((4, 015 0
arg min 0 1:.14
5W:
5

---

Under review as a conference paper at ICLR 2023
af(z)
b1(
0141(x)
W1
[++
byt siae
b 11013)
+o |all [|ll
irit
( ue)
the init structure
nstput from the added structure
added structure
Figure 4: Adding two neurons layer in purple (K 2), with connections in purple. We have 0; E R et w; E R for 1,2.
As the displacement Vi+1 at layer I + actually a sum of the moves induced by the neurons already present (d)) and by the added neurons (0 (ff))+ 1). our problem rewrites as:
arg min V Vogull
V (8W) V (0 1)
10 1 WW:
With w/+1 (xr, o (e-t41)= Σ We (z)) oxs.. Refering to the definition of v'+1(x)) this choice
Zj=1
have be explained because the partial derivative with respect (ax,, w&) is actually 0 (See A.2
We solve this problem in two steps. Let us fix for the moment SW; E M(Uggal (=x()))) [b, (z)
standing for an update of the matrix W4+1, and search for the best new parameters 0
We note V gual Tooaappro
1+1
(+1 (oW)) V gool [+1
Vi+ (74+1(A7 (oW)). We looking for the following
quantity:
(( (f K*):=
arg min
111 ||V
good proj
Vl+1
(0tk
(0fest+1) 1
(5)
gooll We define the matrices N = LB gool (ta)) ) and S = 1 B B Note that N depends on
oW. Using the low-rank matrix approximation theorem |Eckart & Young 1936 we can solve this quadratic optimization problem as follows.
As S is semi-por comitposiiive definite, let denote its Cholesky decomposition by S = S1/2 and
consider the SVD of the matrix S1/2-1 N = -R Maanee oî with A₁ 2 2 AR 2 0, where is
the rank of the matrix N. Then:
Proposition 3.2. The solution of can be written as:
optimal number of neurons: K" R
their optimal weights: (ar ())) (511/2
Uk, Ux) for 1,.... R.
Moreover for any number of neurons K & R, and associated scaled weights 6K. 04 the expressivity gain and the first order in of the loss improvement due to the addition of these K neurons are equal and can be quantified very simply as a function of the eigenvalues As:
V 1+1 goal proj
yl+1(00K
-
goal god
1+1
1
B
A=
(0)
[U (x:),y:)
Σ ((oo 9i)
Σ x
+
a
01100/0-111
R

---

Under review as a conference paper at ICLR 2023
Proposition 3.3. If is positive definite, then solving (5) is equivalent taking wy Nax and finding the K first eigenvectors ag associated to the K largest eigenvalues of the generalized eigenvalue problem:
NN ag = =S
This formulation is useful when dimensions of N and S are large. Considering LOBPCG method (Peter Benner 29 Apr 2020) allows not to invert the matrix and to compute the Cholesky factorization
in proposition 3.2. In practice the matrix S is positive definite except for | - 1 = 0, and even in this last case it is possible to define the Cholesky decomposition of S (cf Appendix).
Corollary. The matrix &Wi which minimizes (6) (through its impact on Vgog)) or equivalently minimizes the sum of orders wero and one in 1i of (7) is given by öW in Proposition 3.1.
Corollary. For all inlegers m, mn such that m m' & R, order one ij it is equivalent add m + m' neurons simultaneously according to the previous method or to add m neurons then m' neurons by applying successively the previous method twice.
Minimizing the distance (6), ic the distance between goal (&W)) and V++ (01-+11),, is equivalent to minimize the loss C at order one in y, and it is directly due to the following development:
L( ) ((fe) (f -
(0) (ggoal 1+1 (SW,,, Vl+ ((
(0te4+1))) (
17
When solving (6), we notice that the family (V++1((as. { of pre-activity variations induced by adding the neurons 1 is orthogonal for the trace scalar product. We could say that the added neurons are orthogonal to each other in that sense. The addition of each neuron k has an impact on
the order of Ak. which can be used define criterion to decide whether the neuron k should be
added the layer not, i.e. only if (ffo) т. We name the operation A 0 @ fest+1 the K-update of the network at layer l.
3.3 CHOOSING THE AMPLITUDE FACTOR 7 WHEN ADDING NEURONS
Let us consider the |+ 1-th layer of the network. Having the best update for linear layer [+1, 8W and the best neurons to add accordingly to layer I, (áī, wi k= we estimate the best factors % and y to multiply the new neurons with, in order to speed up the learning. Defining the updates go(l+1)(7)) (W1,-.. WH1 To SW i+11-... ..., W2) and 0 (7) = (1) we apply
(est+1
line search algorithm to find a local minimum the loss function:
To = arg min
[((sst+)(o))X) (X.),
(6)
1 LUgattu (G) (X.), Y)
2 arg min TEV(U)
where V00) is positive neighbourhood of zero.
Remark: the amplitude factor can also be defined differently, for example by choosing a different amplitude factor for the input and output parameters, ie (YT1kk v22ww))
3.4 VARIANCE THE ESTIMATOR
Noting the number of neurons already in layer before the K-update, we discuss the variance of our estimate 00k::;,, for = 1, ...., I. - 1, as function of the minibatch. At layer / + 1, the solution of (5) is an estimator of 0 = (a w which is the minimizer of:
K
27
10441 == arg min E
Ogual
i+1 (X,)
(X+)
(8)
a.w
where the expectation is taken over all possible random samples X, D. The variance of the directions (á k= grows in vp where p max(n4-1, R4+1) and decreases in VN where N is the minibatch size used for the estimation of ( In practice we will start with N = 100 and increase N with the architecture growth.
7

---

Under review as a conference paper at ICLR 2023
4 EXPERIMENTAL RESULTS
In Figures 5 and 6, we run an experiment on the MNIST dataset ((eeCun et al. 1998)), with CPUs, repeated 20 times. All models are trained for 50 seconds with Adamn(r = 0.0001, 0) with constant mini-batch of size 100. The activation functions are aj = selu if = 1, and T3 Softmaz. We plot accuracy mean and standard deviation on test set for our approach with architecture growth and for standard training with fixed architecture. For our approach, we start with feedforward model with 2 hidden layers of widths [1, 1], initialized with Kaiming normal. Every 0.05 seconds (with Adam(Ir = 0.0001)), )), we extend the two hidden layers according to our method. We compare the performance of method with classical training of large models (Fig. [ or of models with the same final architecture as ours (Fig. 6). to check performance when one already knows the correct architecture. Classic models initialized with Kaiming normal. More graphics can be found in Appendix C We note that large models take more computational time to train, and that architecture growth yields better or similar performance while avoiding layer width tuning.
1.0
0.9
0.8
0.6
0.6
0.2
method, 12000. 1200)
0.5
0.2
metnomt (374, 93]
timetsec)
timelsecl
Figure 5: All graphics represent the same experiment but from a different perspective. Left : after partitioning computational time intervals of size 0.1 seconds, compute a linear interpolation for the accuracy value. Middle the accuracy value against number epochs, where the time needed compute the optimal neurons is not noticeable. Right: accuracy against computational time, where durations due to Cholesky decompositions and their happening instants are averaged over experiments, for better visualisation purposes.
0.9
0.9625
0.9600
0.7
0.8575
0.6
0.9550
0.5
clessi, Nice 12.
size 189, 41]
0.9525
0.4
classic s220 (222, 71]
0.9500
aize [69, 41]
0.9475
0.2
size [222. 721
Figure 6: Left we plot the interpolation of accuracy on intervals of size 0.1 second. Middle zoom of the top left plot. Right: the accuracy value against number of epochs, unlike middle plot in graphic 5 our method trained on fewer epochs compared classic model, indeed with equal architecture our method spends time computing the best neurons while the classic method continues its training.
ABOUT GREEDY GROWTH SUFFICIENCY
One might wonder whether greedy approach layer growth might get stuck in non-optimal state. We derive the following series of propositions this regard. Since in this work we add neurons layer per layer independently, we study here the of single hidden layer network, 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 Σ l1f(x) f (2 f
RED
8

---

Under review as a conference paper at ICLR 2023
where (z) is the output of the neural network and D is the training set. Proposition 5.1 (Greedy completion of an existing network). If f is not f yet, then there exists set of neurons to add to the hidden layer such that the new function f' will have a lower loss than f-
One can choose the added neurons such that the loss is arbitrarily well minimized. Furthermore: Proposition 5.2 (Greedy completion by one single neuron). If f is not I yet, there exists a neuron to add to the hidden layer such that the new function f' will have a lower loss than f.
As consequence, there exists situation where one would need to add many neurons simultancously to decrease the loss: it is always feasible with a single neuron. One can express a lower bound on how much the loss has improved (for the best such neuron), but it is not very good bound without further assumptions on f.
Proposition 5.3 (Greedy completion by one infinitesimal neuron). The neuron in the previous proposition can be chosen to have arbitrarily small input weights.
This detail is important in that our approach is based on the tangent space of the function f and consequently manipulates infinitesimal quantities. Though perform line search in second step and consequently add non-infinitesimal neurons, our first optimization problem relies on the linearization of the activation function by requiring the added neuron 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 matter of fact, our approach exploits linear correlations between inputs of a layer and desired output variations. It might happen that the loss is not minimized yet but there is no such correlation to exploit anymore. In that case the optimization problem (5) will not find neurons to add. Yet following Prop. 5.3 there does exist a neuron with arbitrarily small input weights that can reduce the loss. This paradox can be explained by pushing further the Taylor expansion of that neuron output in terms of weight amplitude (single factor on all of its input weights), for instance (sax . x) ~ (0) + o' (0)sa - x + (a)(0)= x²)² + O(=*). Though the linear term a x might be uncorrelated over the dataset with desired output variation, i.e D (or æ] = 0, the quadratic term (z)=)) ,, or higher-order ones otherwise, might be correlated. Finding neurons with such higher-order correlations can be done by increasing accordingly the power of (a x) in the optimization problem (4). Note that one could consider other function bases that the polynomials from Taylor expansion. In all cases, one does not need to solve such problems exactly but just to find an approximate solution, i.e. a neuron improving the loss.
Adding random neurons. Another possibility to suggest additional neurons, when expressivity bottlenecks are detected but no correlation (up to order p) can be exploited anymore, is to add random neurons. The first p order Taylor expansions will show 0 correlation with desired output variation, hence no loss improvement nor worsening, but the correlation of the p + 1-th order will be non-O, with probability 1, in the spirit of random projections. The loss can then be improved, all the more with line search to optimize the neuron amplitude.
However, such random neurons also contribute to other directions in the functional space than the desired one. This hinders the loss improvement expectable from them, as the line search will need to find a compromise with the loss changes brought by these other directions. This is confirmed experimentally in Appendix C.4] To alleviate this, in the spirit of common neural network training practice, one could consider brute force combinatorics by adding many random neurons and hoping that one will be close enough to the desired direction. The difference with standard training is that we would perform such computationalll-costty searches only when and where relevant, exploiting all simple information (linear correlations in each layer) first.
6 CONCLUSION
We have properly defined lacks of expressivity, and their minimization has allowed us to optimize the architecture on the fly, to better follow the functional gradient, enabling architecture growth. Apart from straightforward extension to other types of layers (such as convolutions) and to the addition of new layers, future work will pay attention to overfit possibilities (which have not have not observed so far, thanks to the optimally small number of parameters) and to neuron addition strategies.

---

Under review as a conference paper at ICLR 2023
REFERENCES
URL
https://en wwwppaa.........................
integral BtgegggrauullleMMMsssss. rulefMeasure
Eheory statement
Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar.
Designing neural network archi-
tectures using reinforcement learning. In International Conference on Learning Representations, 2017.
Slcccveee
Tianqi Chen, lan Goodfellow, and Jonathon Shlens. Net2net: Accelerating learning via knowledge transfer. arXiv preprint (51.://111..041,,,
Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psy- chometriku, 13):2111221, September 1936. ISSN 1860-0980. doi: 10.1007/BF02228837. URL
https: wtt.:/oo...gg...1 1ttp://0001000/022228000
Utku Evci, Bart van Merrienboer, Thomas Unterthiner, Fabian Pedregosa, and Max Vladymyrov. Gradmax: Growing neural networks using gradient information. In International Conference on Learning Representations, 2022. URL htttps::/oppereee//
wwU0
Ariel Gordon, Elad Eban, Ofir Nachum, Bo Chen, Hao Wu, Tien-Ju Yang. and Edward Choi. Morphnet: Fast & simple resource-constrainee structure learning of deep networks. In Proceedings of the IEEE conference on computer vision and puttern recognition, pp. 1586-1595, 2018.
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2596-2604. PMLR, 09-15 Jun 2019a. URL httppss:/pppocecinnnsi....cceeee
html
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation pat- terns. In H. Wallach, Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019b. URL 9766527f2b55 6655777755eee56444433fftt77oo630
pdd
K. Homik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approxi- mators. Neural Networks, (()):359-666 1989.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and general- ization in neural networks. S. Bengio, H. Wallach, Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran As-
sociates, Inc., 2018. URL httpttpppp/pprocceeiiiioo wwwriigg...euurppp. httpa//ipp..ccpppp////////////// 5a4be e 2eleeee2225aaaee5000022222555502
pdd
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86(1 (6(11))2278-222) 1998.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations, 2019. URL [tll/attts://pprrriiie
Hector Mendoza, Aaron Klein, Matthias Feurer, Jost Tobias Springenberg, and Frank Hutter. Towards automatically-tuned neural networks. In Frank Hutter, Lars Kotthoff, and Joaquin Vanschoren (eds.), Proceedings of the Workshop on Automatic Machine Learning, volume 64 of Proceedings of Machine Learning Research, pp. 58 65, New York, New York, USA, 24 Jun 2016. PMLR. URL ngs m prwss/ v
https///////mmmmoaaaaaaaoo http//eendnaatcaeee towa rós 2012 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//103.00 703.00548, 2017. URL http:://t///... //wrivar.vvvv/// wtq/abs///0/
00548
10

---

Under review as a conference paper at ICLR 2023
Geoffrey F. Miller, Peter M. Todd, and Shailesh U. Hegde. Designing neural networks using genetic algorithms. In ICGA, 1989.
Yann Ollivier. True asymptotic natural gradient optimization, 2017. httpt::s//aaaxvvooo
abs 171211000 08449
Xin Liang Peter Benner. Convergence analysis of extended lobpeg for computing extreme eigenvalues. 29 Apr 2020.
Allan Pinkus. Approximation theory of the mip model in neural networks. ACTA NUMERICA, 8: 143-195, 1999.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 2847-2854. PMLR, 06-11 Aug 2017. URL
mlr. wwwsspeessvv.... / wttps///vorraahulll 7a html
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4558-4566 PMLR, 10-15 Jul 2018. URL https:tt/////mm hattps://proceedinngg
mlr. www.ppressww////.. w html
Naftali Tishby and Noga Zaslavsky.
Deep learning and the information bottleneck princi- plc. CoRR, abs/ 0bb//1503.0240. 2015. httphtt::///bll wwwp:piii.tiiiiiioomooeo dw/dd/////////e// httjoo/nals///////o//o////..m.//
corr/corr1503. htw. htt.s..mmmtmmiiht..m
Lemeng Wu, Dilin Wang, and Qiang Liu. Splitting steepest descent for growing neural archi- tectures. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32, Curran Asso- httpss/ccppppp..///ie.e./. pdf
ciates, Inc., 2019. URL httpp::/ppoceeeinnng
Lemeng Wu, Bo Liu, Peter Stone, and Qiang Liu. Firefly neural architecture descent: a general approach for growing neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Bal- can, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 22373-22383. Curran Associates, Inc., 2020. hwR/ittppss//rrceeeiin..... paper
cc/
Tien-Ju Yang, Andrew Howard, Bo Chen, Xiao Zhang, Alec Go, Mark Sandler, Vivienne Sze, and Hartwig Adam. Netadapt: Platform-aware neural network adaptation for mobile applications. In Proceedings of the European Conference Computer Vision (ECCV), pp. 285-300, 2018.
Barret Zoph and Quoc V. Le. Neural architecture search with reinforcement learning, 2016. URL httt:://arxlv.org/bbbbb 01578 cite arxiv: 1.01578.

---

Under review as a conference paper at ICLR 2023
A ASSUMPTIONS
A.1 MEASURE THEORY STATEMENT
Let X be an open subset of R, and Q be measure space. Suppose f : X Q R satisfies the following conditions:
f (a, w) is a Lebesgue-integrabbe function of w for each x E X.
For almost all E Ω the partial derivative fa or f accordinf to x exists for all E X.
There an integrable function 0 R such that [x, s ((w) for all æ e X and almost every w E Q.
Then, for all x E X,
de 1 f(x, dw I fo (o( du
d
See proof and details mea
A.2 REMARKS
When increasing the size of layer with o test+1 (ar, w2) starting with (arg, wg w the outcome for (xe, (f4)44)) is 0 because gradient with respect to (ats, We )= is in (ar, O. In mathematical terms:
(x, 0f == (a)+1(x)
0 = 0
(9)
00k
1++1+1 10
The impact of this modification of structure has be seen differently. The first point of view is say that we choose (wx)k=z then compute v/+1 (x, (= as a function of the family (wx) We have then:
0a (x)
K Σ
alt (x, ofe = o (x, (aw)
(ax) K
0( (axx )
as
(())
This is equivalent say that for each family (w)) the tangent space a1+1 restricted move in (ow)
0ai+1 the family (ow)& ie Ta441 = (
(R)b- K varies
((ow)
with the family (wx) ie Thi+i Tott! ( Optimizing over the wy. is equivalent to search for the better tangent space while optimizing on the ag is equivalent to find the better projection the tangent space defined by the Wy.
Note that making the derivative according to the a% ease the problem by removing the non- linearity in σr, When reversing the roles of the on and of the Wx. fixing the or and compute / (xx, (wa) ( ) ). makes the problem harder to solve because the non linearity in remains in the optimisation problem.
Taking an other point of view, you can consider the second order of (x) in (oxs wk) in 0 to recover the same expression. Indeed taking the Taylor expansion in (oo,, w
K
(x) = a141 (o)
+
Σ w
(2t) as + +((l((a)) + { kk (1))))
[TODO] A faire
12

---

Under review as a conference paper at ICLR 2023
expressivity
gool
expressivity boctleneck
hot tleneck
goal
Ta((ww))
Tallw ke
Proita P (goai)
fe
2
ProjT
(1) (ggot))
FA
FA
Figure 7: changing the tangent space with different values for the family (wy, K
k=1
B PROOFS
B. PROPOSITION 3.1
Define dW,+ + the generalized inverse of (W then
8W; n goal B (- BB-IIBB.+* and Vú = n
goal B
(- (-B.B Bi-1
B n
Proof
Consider the function g(oW:) Vgnall OW, B; 11 then
g(oW: H) ||Va 8W, HB:-1
g((W,) 2(V ((Vaaa'' BW, HH, B1Bi1) + o H|)
9(8W)) 2T (Vggaa' 1-8. -..B. H B[-1) + o(I H[]
9(WW) 2T (Bt-1 (Vgnal B H) + o( H[)
g(8W)) 2((V goal - S.W B H 1/- + H[(
By identification V Vow.((WW)
2(V goal
BW.B.-1)
Vow.g(WW)) =
Vgoal B = dW
Using the definition of the generalized inverse of :
1 V Vgoal B B (-BI,I
8 SW.
n
B.2 PROPOSITION 3.2
If S' is positive definite, consider the Cholesky decomposition S = 51/2 note R the rank
of the matrix N and the SVD of the matrix S1/2 N ER A Aa with S \ ... 5
AR then the solution of (4) is written K = R and (ái, wg)) (51/2T ur vx) for k
R Moreover for all K < R and @K l41411 = (& 2 k and for 7 positive, 0
13

---

Under review as a conference paper at ICLR 2023
(yarg ()) we have that:
K
H+1 V
goal proj
VI+1 (0 1)
V
goaa proy
pros!
11
Σ
(10)
71
k=1
[foodk (-14, (1) (2:), (2))..))
1
L(fo(z,). - 0'(0)
2
X
+ o(7)
(11)
17 k=
Proof
1
arg mill
-
s00ll proj
[+1
vl+
arg min 0fa
Vgoal
1+1
/1.
+
0 ff
1
arg min - =g(0
0 0
We note
-
Σ
Σ
1+1 Ugaal pros
(x:)) T
a 1 wh
&
1
a b( Jusk w/ (af b(-1
n
K
T'
b
(I; Ugoa) 1+1 (xx;)² wi
Ugoalpros
k
Σ
1 waw
(0:
+
n
"
2 Σ
T Nw
wh w Saj
a
1 n
with N
Σ
b
i11 (zx))²
Bi- (Vsoa (+1)7
proj
n
n
1
S
b (2,))0;-1(00))
B B
14

---

Under review as a conference paper at ICLR 2023
Suppose S is semi definite positive and note S S1/251/22 7k 51/27 an and S1/2-1 N 1t
Σx v the SVD of matrix 81/2-1 N.
K
Nwk = Σ The S//2222 Nwk
Yk X U,
T
d u.))) wk)
Tr
Tr Σ Xpai o
Tr Σ whiT Σ )rere,))
Σ
nwwk EnNoeeT
with (A, B) = Trace(A" B)
K
Σ
w w Soy
w
TT wj) (g5 mm)
kj
Kjj
Tr
(wF w/)77 7ks
AJ
TT(
nwwt w
Σ
Yk
l avec ||A||T (A))e
Σ
mowk 1/1r
Then we have
K Noo! 11
arg min
- g(wwww)
arg min
1/2 N ||S ||-1//2
K K.
K.a=S 1/2
Then the solution is giving by the paper Bekart & Young 1936) chosing K rank(S-1/22) and EK= "wo = ΣK ef Choosing K = R is the best option. We now consider the matrix M. The minimization gives also the following properties at the optimum
for l # know, N30 )2r =
1/21/2 Σ
Nowk 1122 =
Σ
X
rm 1+1
-15-1/22
Σ
m T
1l+
15

---

Under review as a conference paper at ICLR 2023
Furthermore:
1 - 1+1 goal proj
V(0 (0(0s441)11f
1 ||
V| proy)
li 11(55113) -N Σ nw 11(5 -1 Ml
7
71
n
X
goal goal proj 1r - 11(51/2) -1 N 1
y= K+1
1+1 V
goal proj
Tr
Before looking at the impact the Loss let's prove the corollary 3.2 We looking for the matrix
5 minimizing the last equality. Consider the span of matrix S Wi N:BiooWmaarriy and P the matrix projection on span S:
arg min DES,6
V
1+1 goal
D 1l+
V++1 (0)
arg min
PV
gool
I+1
-D
DES
+ arg min
[[ - P)
1+1
V(0)
goal
Then OW Bi at proposition 3.1 minimize the first norm and the orthogonal projection of Vgaal on span S.
(Id P)
1+1
Vival 1+1
SW B
goal
We also have that:
VI+ VWW( V4+ (0
And by definition of the orthogonal projection on linear span:
(vi+ (0
(0 Vgoal I+1 / -vv't (
ppo (8Wi+2)
We note V 1+1 (WWi))) gooa
1+1 Venalpros
The impact the global loss is
C
(a41 ((fo(az) yi). (x,, (0 7o (n (owiii)))
+ o(max(y):)))
((f((z)) _- n [00] v (0 (0um141) Vooal +1) n n =0)()) yl
11 -
( (8>0 Wi+1). Vgoal (+1)
T
+ +0mmar(7)%0)
(fe(z,)) -1 - (100)(v+((00f.- (0/t)+1), Vgontpro) Tr
7o ((())
v (oWi))))))) Vgual (+2)
n
+ o(max(7,
16

---

Under review as a conference paper at ICLR 2023
We also have the following property:
1+1
y (0
arg 8 14444
godl proj
arg min H20
arg min V++1 (8 (0 TH
proj
++1
v 1ili-1,.W::. &Wi+1)liis
8K 1ett1
aarg min
arg min V++ (f 1
{
2
V
goal praj
1+1
(s
v (0 (0/t)142))
+ + [1
1
H20
8% 1
n
Tt
arg arrginn min
arg min V++ (f TH
2
1+1 V
good proj'
V (0 (0(tz142)
+
[1a]
1
1120
1
Tt
n
-arg min
arg min V
{ H
H(
1+1
Vl+
(0
+ 2 !12)
1220
(0
Lort1 11m==1
With V (0 )" the solution of the second arg min (ie for H = 1).
Then the norm minimizing the first argmin is given by
H
V
gool pros
1+1
V (0k (0(ts1+)''
/ TT
(Vooll |+1
v (0+1(0/(444)) )*) >,1=-
Furthermore
k
min
V
goal proj
1+1
- v1+1 11+ (1+1++1)11 21 =
2 +
V
proj
goal proj
1+1
1ir
1est+1
r=1
min
prop
i+1
V
(0/K (0(+2+1)1l1n
H
1
V
Vgonl gou IT+
1+1
n
n
n
K
H = ((VVVVa 1+1
1 (8(6)(41)*)
Σ r=1
X2 x Vn
TI
vl+ ((+(00001111 = H H ( (0frs4z)*
[+1 (vit)(0 yooal
H' x
(Vooa 1+1 Vl+ 1 (0/k ) -H-2
where the last equality is given by the optimisation of D|SS-/// - Ek unw 11.y. So minimizing
the scalar product- - gond 1+1 (6Wi1)) Vi+ ( (0(x(4))*) Tt (0k 11)
prof
setting the norm of V Vl+ (0k (0fe)41) is
equivalent to minimizing the norm
[Vgoal proj (oW
2+1
C Uotn (inngW Wio,) "o ()) (2:),
L(fo(z)), 20((0) x2 To 1
Σ
(((0 !+1 (Wi+1), (WWi)))))))))) Vgonl (1)) + (mmaa(() 70))
n
17
B.3 CHOLESKY DECOMPOSITION FOR S POSITIVE SEMI-DEFINITE
When matrix S is not positive definite, the following trick can be apply. Consider S = UTVT the svd of S. As S is symmetric U VT, Perform the QRdecoopooiition of matrix VEUT QR. Q an orthogonal matrix and R an upper triangular matrix. Defining p+ the pseudo inverse of P. one can remark that R R = U / ( Q --=T"QQ UUTT.T As Q is orthogonal R R UEUT = UEVT S.
17

---

Under review as a conference paper at ICLR 2023
B.4 PROPOSITION 3.3
Suppose S is semi definite, we note S = 51/2 Solving (7) is equivalent to taking we N on and find the K first eigenveetoss wP associated to the largest eigenvalues of the generalized eigenvalue problem:
NN an = ASo*
Proof The LOBPCG problem is equivalent maximise the generalized Rayleigh quotient which is
a NNN &
a' marT a Sa
pz S
NN S1/2
p" max p= mar
p'p
| p' = max [p|l=1 1I.IIINNS 81/2-17
pll
a' = S1/2 15
p
And considering the SVD of S1/2 N E u, o, then 51/2"1 NN 81/2-12 Σ uu because j o =
u 0 and vi Vj = 0. So maximise the first formula is equivalent to P ug then Og 11/ ug And N au N Us A
We prove second corollary 3.2 by induction. For m m'
a1+1(x) ++1 = (2)) + V (1: x) + o(7)
2 Uguoal 1+1,0+1 (xx)
ggaal (+)) V Va, ((x) ((fo(z)) y) 10 o(7)
Adding the second neuron we obtain the minimization problem:
arg min
V 1-1,6
goal
V
(2) (a2, d())
Or2.4/2
B.5 SECTION Theory behind Greedy Growth WITH PROOFS
One might wonder whether greedy approach on layer growth might get stuck in a non-optimal state. We derive the following series of propositions this regard. Since in this work we add neurons layer per layer independently, we study here the case of 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 compact set. That is, we aim at minimizing the loss:
inf Σ 11f(z) (z)
RED
where fxx) is the output of the neural network and D is the training set. Proposition B.1 (Greedy completion of an existing network). If f is not f yet, there exists a set of neurons to add to the hidden layer such that the new function f' will have a lower loss than f.
One can even choose the added neurons such that the loss arbitrarily well minimized.
Proof. The classic universal approximation theorem about neural networks with one hidden layer Pinkus (1999) states that for any continuous function defined on a compact set w, for any desired precision y, and for any activation function provided it is not a polynomial, then there exists neural network ÿ with one hidden layer (possibly quite large when is small) and with this activation function a, such that
Vx, (l((z) - g" (z:) <
We apply this theorem to the case where 9" = f - which is continuous as f* is continuous, and is shallow neural network and as such is composition of linear functions and of the function that we will suppose to be continuous for the sake simplicity. We will suppose that f is real-valued for the sake of simplicity well, but the result is trivially extendable to vector-valued functions (just
18

---

Under review as a conference paper at ICLR 2023
concatenate the networks obtained for each output independently). We choose 1f f2 L2. where (al 6) 1.2 w IeEw a(x) b(x:) dr. This way obtain one-hidden-layer neural network, with activation function such that:
Va w, -7 -7 -
Vo Ew [())
with Vor E w. |a(x)] E
Then:
Vo Now (f(=) = -a(z)
Frew, h(z)) =
(12)
with h being the function corresponding neural network consisting in concatenating the hidden layer neurons of f and and consequently summing their outputs.
If h1122 |a1|22
1f" - 111 < -/ 100-fll fl22
100
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 y =
t / EzED (lf(z) (+) as Equation (12) then yields:
M())) Σ (x)
<
Σ FED
(f -()))
100
ZED
FED
which proves the proposition as stated.
For more general losses, network that is close to (the opposite of) the gradient of the loss.
consider order-1 (linear) developpment of the loss and ask for
Proof of the additional remark. The proof in Pinkus (1999) relies the existence of real values oa such that the n-th order derivatives (c))(cn) not O. Then, by considering appropriate values arbitrarily close to Ca. one can approximate the n-th derivative of at c, and consequently the polynomial e" of order This standard proof then concludes by density of polynomials in continuous functions.
Provided the activation function is not polynomial, these values C, can actually be chosen arbitrarily, in particular arbitrarily close to O. This corresponds to choosing neuron input weights arbitrarily close to O.
Proposition B.2 (Greedy completion by one single neuron). If f not f yet, there exists a neuron to add to the hidden layer such that the new function f' will have a lower loss than f.
Proof. From the previous proposition, there exists a finite set of neurons to add such that the loss will decreased. In this particular setting of L2 regression, or for more general losses if considering small function moves, this means that the function represented by this set of neurons has strictly negative component over the gradient g of the loss (g 2( - f) in the case the regression). That is, denoting by a, W; x) these N neurons:
a, x)) 9) K<0 <0
i...
N
Σ
(a x)1 g) = <0
19

---

Under review as a conference paper at ICLR 2023
Now, by contradiction, if there existed no neuron i among these ones such that
(ajo(w, x)) g) L2 & N
then we would have:
1 K Vi [1, (a:a(w; x)) g) L2 N
N
(a x) 9) > K
hence contradiction. Then necessarily at least one of the N neurons satisfies
(a.o(w: x)) 92 K
and thus decreases the loss when added to the hidden layer of the neural network representing Moreover this decrease is at least N of the loss decrease resulting from the addition of all neurons.
As consequence, greedy approach will not get stuck in a situation where one would need to add many neurons simultaneously to decrease the loss: it is always feasible by a single neuron. On can express lower bound how much the loss has improved (for the best such neuron), but it not very good one without further assumptions on f.
Proposition B.3 (Greedy completion by one infinitesimal neuron). The neuron in the previous proposition can be chosen to have arbitrarily small input weights.
Proof. This is straightforward, as, following 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 the tangent space of the function f and consequently manipulates infinitesimal quantities. Though we perform line search in a second step and consequently add non-infinitesmmal neurons, first optimization problem relies the linearization of the activation function by requiring the added neuron to have infinitely small input weights, without which would be much harder solve, This proposition confirms that such neuron does exist indeed.
20

---

Under review as a conference paper at ICLR 2023
C ADDITIONAL EXPERIMENTAL RESULTS
All the experiements are performed 20 times on MNIST Dataset and the models are trained with Alam(Ir = 0.0001, /r O, batchsize 100) with CPU. For the classic model, neurons initialized with Kaiming Normal. For our approach, we always start with a model of size [1, initialized with Kaiming Normal and we expand its architecture using 3.2 every 0.05 seconds. The batch-size, nmmb. for estimating ((7)tes++17)) and 0W is n 100 at first step and for every layer. After applying method every layers, 7mmb is updated as n'mb f n X / /mar (nuroonuu neursnsss where neurons indicates the amount of neurons at layer /. In the following section, we modify the value for the training time between architecture growth 8 and architecture growth TO The y aris accuracy on test set.
C.I CHANGING TRAINING TIME BETWEEN EACH ARCHITECTURE EXPANSION STEP
In this part modify the training time between each architecture growth. We apply 8 times method on each hidden layer, the final architecture [222, 71]
1.0
0.962
0.8
0.8
0.958
0.4
0.956
our growth 0.05
0.4
0.2
our, growth
0.954
47.5
time(sec)
timetseci
opoch
Figure 8: The different shades of red correspond to different training time between each architectures growth seconds.
C.2 SMALL ARCHITECTURE
Same plot as but with others architecture.
0.965
0.8
0.960
0.8
3
0.6
0.955
mathod. 4)
method 117. 231
desii meihod (59. 111
method
4]
Sur methoo. size 117, 213
0.2
Our methoel size 869, 413
10
20
30
40
35
40
45
50
10
20
30
time(sec)
time[sec)
spochs
Figure 9: Right interpolation on interval of size 0.01. Middle accuracy function of mini-batches Right: accuracy plotted as a function the mean time in each category classic training and our approach.
C.3 EIGENVALUES
In this section we apply our method 15 times on each layer. After applying times our method, the accuracy of the system does not increase significantly. We have that Er,,y=D [x)) for every
21

---

Under review as a conference paper at ICLR 2023
vector explained in part
Looking at the eigenvalues for the first and second hidden layers and
0.8
0.8
0.6
0.6
0.5
0.4
0.3
0.3
cleesic methos, size 13000, 1503]
0.2
100
methos, size (922, 2/11
20
30
40
50
0.1
0.00
0.25
0.50
0.75 epoch
1.00
1.25
0.1
timessic)
timelsec)
Figure 10: Comparison between the classic training of architecture [1000, 1000] and our approach of architecture [929, 141]. All models are trained for 20 seconds we plot here mean and standard deviation for accuracy on test set. For our method trained the model for 0.05 seconds between each architecture growth. Right interpolation on interval of size 0.01. Middle accuracy function of epochs. Right: accuracy plotted as function of the mean of time in each category classic training and our approach.
estimate decrease for the loss, ie Σn X
35000
30000
0.4
mean: laver
25000
maan. layer
15000
0.2
10000
0.1
3000
0.0
2.5
5.0
7.5
10.0
12.5
15.0
17.5
0.0
2.5
5.0
7.5
10,0
12.5
15.0
17.5
number of architecture growth
number of architecture growth
Figure 11: mean and standard deviation for Σx X for first and second hidden layers as function of the number of architecture growths
300
250
200
max kgyer
150
100
50
0.
0.0
growth
growth
Figure 12: mean and standard deviation for max(AA) for first and second hidden layers as a function of the number of architecture growths
22

---

Under review as a conference paper at ICLR 2023
C.4 RANDOM VS OPTIMIZATION
When performing the quadratic optimization 5 we obtain the optimal direction for (áz o is also possible generate randomly the neurons and compute the amplitude factors. This second option have the benefit being less time consuming, but it would project the desired direction on those random vectors and would affect the accuracy score compared optimal solution defined in 3.
0.8
best
0.6
0.6
0.4
0.4
0.2
0.2
100
200
300
400
500
minibatch
time (sec)
6000
loss, Lestt
6000
our method Init model alla neurons
4000
4000
2000
200 300
500
(soc)
Figure 13: Experiment performed 20 times on the MNIST dataset: starting model in black [1, 1] is initialized according to normal Kaiming, then duplicated to give the red and the green model. The structure of the red model is modified by method to reach the structure [110, 51] while the green model is extended with random neurons. Then all models are trained for 5 seconds. The white space for the red model corresponds to the quadratic optimisation and the computation of the amplitude factor while for the green model it corresponds only to the computation the amplitude factor.
23


Reviews:
[{"review_id": "n7BXecRDkAg", "reviewer": "Reviewer_ae2U", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes a method for growing neural networks during training. The authors formulate the problem as an optimization problem. Specifically, when the network lacks expressivity, there will be no gradient updates in the weight space that will lead to a change in the outputs that align with the desired functional gradient, i.e., $v_{goal}$. To mitigate this issue, the authors propose to expand the network by adding extra neurons and assigning the weights by solving an optimization problem detailed in section 3. Empirically, the authors conduct preliminary experiments on MNIST datasets.\n", "summary_of_the_review": "Overall, I think the problem studied in this paper is interesting and important. The motivation is clear and well-justified. However, my major concern is that the authors missed many related literatures and hence failed to make a comparisons with them. The position of the paper is unclear. Detailed comments can be found in Strength And Weaknesses section.\n", "strength_and_weaknesses": "Strength:\n- First of all, I think the problem of growing neural networks on the fly is very interesting and important, especially putting it under continual/lifelong learning scenarios. \n- In terms of the methodology of this paper, I enjoyed reading the motivation and the derivation of the method, which I feel is pretty natural. In particular, I like the toy example for illustrating the issue of lacking expressivity. \n\nWeakness:\n- The most critical weakness of this paper is that the authors seem to miss many important related kinds of literature, and failed to make a comparison with them. To my knowledge, the problem of growing neural networks on the fly is not new. There have already been many works. \n - - For example, the work by Wu et al., 2019, is very similar to your idea. The high-level idea is that adding more neurons will turn local optima in the small neural networks to be a saddle point. They derive a simple criterion for deciding the best subset of neurons to split and a splitting gradient for optimally updating the off-springs, which is a second-order functional steepest descent for escaping saddle points in an $\\infty$-Wasserstein metric space. There are also follow-up works by Wu et al., 2020 and Wang et al., 2019. \n- - The work by Chen et al., 2015, is a bit more empirical but is also very relevant. In their work, they add new neurons with carefully designed weights that don't change the computed function. The only difference is that they need to manually decide when to add neurons.\nTherefore, I believe a detailed discussion and comprehensive comparisons of these methods are necessary.\n\nThere are also a couple of additional concerns:\n- The derivation in the paper is only about one layer. How can it generalize to multiple layers?\n- How do you decide the number of neurons be added? Or do you need to enumerate all the possibilities? \n- The experiments are quite lacking. I would suggest the author follow the experiment setup in [1-4].\n\n\nReferences:\n\n[1] Wu, Lemeng, Dilin Wang, and Qiang Liu. \"Splitting steepest descent for growing neural architectures.\" Advances in neural information processing systems 32 (2019).\n\n[2] Wu, Lemeng, Mao Ye, Qi Lei, Jason D. Lee, and Qiang Liu. \"Steepest descent neural architecture optimization: Escaping local optimum with signed neural splitting.\" arXiv preprint arXiv:2003.10392 (2020).\n\n[3] Wang, D., Li, M., Wu, L., Chandra, V., & Liu, Q. (2019). Energy-aware neural architecture optimization with fast splitting steepest descent. arXiv preprint arXiv:1910.03103.\n\n[4] Chen, Tianqi, Ian Goodfellow, and Jonathon Shlens. \"Net2net: Accelerating learning via knowledge transfer.\" ICLR 2016.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "bwczyOl5Osc", "reviewer": "Reviewer_fbfu", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes a method to learn the optimal architecture via back propagation. ", "summary_of_the_review": "Due to concerns on presentation and experimental strengths I recommend rejection. ", "strength_and_weaknesses": "Strenghts:\n\n1. Interesting Idea and compelling problem statement\n\nWeaknesses:\n\n1. I do not think the quality of the paper is upto ICLR standards. The writing is shabby at places with multiple typos and is difficult to follow. The way it is presented, the algorithm the authors propose is incredible hard to decipher.\n\n2. Experimental evaluation is weak. I would expect to see results on other datasets beyond MNIST. Even for MNIST where even simple 2-layer networks get 96-97% accuracy, the plots for the classical method (standard training with fixed architecture) seems too poor for a baseline.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "V-v7lD0KYx", "reviewer": "Reviewer_vKnn", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper suggests a novel approach to extend neural networks during training using the functional gradient. The approach starts with an impoverished network and iteratively adds neurons to the network making sure to follow the true gradient direction. The authors mathematically derive an optimal technique to grow the architecture in the manner proposed. They also present experiments on MNIST showing that their approach performs better than classically trained networks with similar architectural constraints and networks extended by randomly adding neurons.", "summary_of_the_review": "While the contributions of this paper are novel to my knowledge and the math describing the motivations and details of the approach is extensive. The hypothesis of this paper remains experimentally unverified in my opinion (See weaknesses section). As a result, without more experiments, I don't think this paper is ready for publication in its current form.", "strength_and_weaknesses": "# Strengths\n- The paper is very thorough and clearly describes all the math involved in their approach.\n- To my knowledge, the paper presents a novel approach for extending neural networks using functional gradient information.\n- The suggested method for extending neural networks seems very powerful if works as claimed and could have a large impact on the way we train networks.\n\n# Weaknesses\n- One hypothesis why Deep Learning works so well is that the fixed architecture provides an implicit regularization that ensures the network doesn't overfit while SGD and variants optimize the training loss. The approach presented in this paper removes this form of implicit regularization. \nWhile this approach may work, the generalization of this method needs to be validated through experiments. \nThe only experiments conducted in this paper are small-scale experiments on MNIST using impoverished networks.\nMNIST is too small of a dataset to suffer the actual generalization consequences that may come from using this method. I would like to see experiments on larger datasets like CIFAR-10 with larger overparameterized baselines as suggested by most of the contemporary deep learning literature.\n- Most contemporary deep learning models are overparameterized, meaning they are able to achieve 100 train accuracy without needing to add any more parameters. While there may be an expressivity gap at each training step for these models, there does not seem to be any expressivity gap for the actual task since the models can easily overfit on the training set. This suggests that the key assumption made in this paper regarding the expressivity gap is flawed.\n- I would like to see other experiments comparing this method to alternative methods like pruning that also attempt to identify \"lottery ticket\" architectures. If the method proposed here achieves a similar generalization metric to those methods, I would be more convinced of the claims made by the paper.\n- This approach is analogous to taking a low-degree polynomial and increasing its order to fit the data. While the approach considered is novel considering the way the network is extended using the gradient information, the final success of this approach will lie entirely on its ultimate generalization performance for which the current experiments are not convincing enough.\n- It's unclear why the experiments use time on the x-axis.\n- Primarily my objections boil down to the limitations of using MNIST to evaluate an architectural search problem and the use of small networks that do not express the interpolation regime behavior to which we attribute the success of deep learning models.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Hh2OFJoWt6", "reviewer": "Reviewer_9tpv", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new approach to widen layers of a neural network during training. The method is motivated by the functional gradient and looking at the desired activations for a given data input. Proof-of-concept experiments on MNIST are used to compare the method to conventional training.", "summary_of_the_review": "See 'strengths and weaknesses' for more details.\n\nThe idea seems promising, and I suggest the authors to further investigate it through more rigorous experiments. Unfortunately it's hard to evaluate a growing method -- whose goal is to ultimately save training time by starting from a small network and growing it through training -- on a dataset as small and easy as MNIST. CIFAR-10 and ImageNet experiments are the most commonly-adopted ones when evaluating and comparing growing methods. A discussion on related works that also focus on growing networks would also be extremely valuable.", "strength_and_weaknesses": "The idea is well explained and motivated, and the designed approach seems promising and novel.\n\nThe main weakness is the lack of empirical results to properly evaluate the method and test its practical implications.\n\nTo be more specific, there are previous works whose goal is to grow a network -- i.e. start from a small network and sequentially add neurons / filters / layers -- in order to save training time. These methods are typically evaluated on CIFAR-10 and ImageNet, and MNIST is too much of an easy dataset to properly evaluate these methods: the required network size to perform well on MNIST is very small. Some examples of growing methods are: MorphNet, NetAdapt, FireFly, and Net2Net.\n\nAnother concern is whether solving the quadratic problem is feasible for larger networks of different families, like CNNs.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject