Growing Tiny Networks: Spotting Expressivity Bottlenecks and Fixing Them Optimally

Thank you for your detailed review and remarks that we answer below.

Answers to questions

How does the proposed method perform on CIFAR100 and ImageNet?

We explain in the common reply "About experiments and architectures" why we have not performed such tests, and that we are currently running them (on CIFAR-100 with a ResNet-style architecture), to show that our approach can scale to larger architectures and larger datasets. However we do not hope for competitive accuracy with the state-of-the-art as our current implementation does not include yet batch-norm, drop-out or data augmentation, which are needed to reach good scores.

How is the matrix N on page 15 computed, since it depends on the (unknown?) $V_{goal}$?

$V_{goal}$ is actually known and easy to compute. We have rewritten the paper to make this more explicit (beginning of Section 2.2). The quantity $v_{goal}(x)$ is actually what the first step of the usual backpropagation computes, when the network has been shown sample $x$. So we get this quantity for free. We have added a detailed explanation in Appendix A.1 to show this property.

What is the runtime complexity of an update step?

In practice, running our approach takes about the same time as training from scratch with standard gradient descent the final architecture we find.

We detail the theoretical complexity in the common reply "Computational complexity". In particular, we show that the computational cost of the SVD is neglectible relatively to standard gradient descent. This is because the matrices we apply SVD to are very small compared to other computations done to run the network (their size is the number of channels in a layer, and not minibatch size, neither image size).

How do the computational requirements compare with training just a wider model from scratch once?

This comparison is performed in Appendix E.1.2 COMPARISON WITH BIG MODEL. The left figure shows the accuracy as a function of time, while middle figure plots the accuracy as a function of gradient step. We easily see a persistent gap between the two curves on the left plot. While we achieve convergence around 90% accuracy on the test after only 15 seconds, the large models do not reach this performance even after 250 seconds of training.

How does training the obtained end neural network from scratch compare to the proposed training + growing process? Is a real improvement in generalization performance observed?

This comparison is done in Appendix E.1.3 COMPARISON WITH THE SAME STRUCTURE RETRAINED FROM SCRATCH, where after obtaining an architecture with our method, we compare its performance with the same model randomly intialized and retrained from scratch. Regarding the left plot, which is a zoom of the final performances, the difference of performance is not significant (except for one model where the gap is 0.006 point of accuracy at our disadvantage). The take-away message is that we are able to obtain the same accuracy, in a single run with growing architecture, than the classical gradient descent run using an oracle to tell the best architecture, and this with similar training time. Consequently, we get architecture width tuning for free.

Answers to other remarks

The method is not very flexible in adding layers or different kind of modules. It only grows the width of a chosen architecture.

Our approach naturally extends to the addition of new layers (or nodes) in general computational graphs (any differentiable DAG), as it turns out that layer creation is the same as adding neurons to an empty layer. We discuss it briefly in the last paragraph of "About experiments and architectures".

Limitation: It appears that the number of neutrons that are added in each step is a hyper-parameter.

As we discuss it in the common reply "Neuron addition strategy", one can conceive neuron addition strategies that do really get rid of such hyper-parameters. In the paper we chose on purpose a very simple experimental setting (with fixed number of neuron additions) just to compare the quality of neurons added when using our approach or GradMax.

[About presentation]

As advised, we moved the Related Works paragraphs from Section 3 to the rest of the state of the art in the main introduction. We have put the appendix back to the end of the main paper, for links to work again. We have added a high-level description of the algorithm in the main paper, and we are adding the description of the sub-routines in the Appendix, with detailed complexity.

We hope we have answered your questions as well as adressed the weaknesses.

$\newcommand{\mM}{\mathbf{\delta W}}$ $\newcommand{\Ir}{\begin{pmatrix} I_r & 0 \\ 0 & 0\end{pmatrix}}$

Thank you for your review and your good appreciation of our paper.

To answer the questions:

How does the approach compare to NEAT based techniques? What are differences / communalities?

Both approaches have the similar goals: the optimization of the architecture of a neural network, for a given machine learning task. However they proceed very differently. NEAT is based on evolutionary techniques, with a mix of exploration (random architecture changes), selection and cross-over. On the opposite we are driven by the gradient of the task loss, which enables us to directly know which part of the architecture we should change, and how (i.e. where to add neurons, and which ones). While NEAT needs to perform many random tries (and retrain each generated architecture) to find good moves, we exploit the information from the backpropagation to directly apply the optimal move. However our moves are optimal in a first order derivative meaning, and computing these moves is costly, while NEAT estimates the real impact of each tested move (but this comes at a computational cost as well, and arguably a higher one). We expect that in a near future, neural architecture optimization techniques involving both types of approaches will arise.

How well would your approach work on datasets with lower signal to noise ratio compared to CIFAR-10? Would you expect to see overfitting?

Definitely, yes, if the user forgot to add a regularizer to the loss to optimize. We suppose that the user provides a loss that they actually want to optimize. This is not the case though in current practice of neural networks, as architectures are selected for known good training biases, and as batteries of indirect regularizers are used (early-stopping, drop-out, batch-norm, data augmentation, etc.). In case the user forgot to add a regularizer to the loss, we could still use these indirect regularizers to fight against overfit (except for early-stopping). We also have other ways to detect of prevent overfitting, as we can estimate the statistical significance of the candidate neurons to add. If the eigenvalue associated to the candidate neuron is too low, the performance gain provided by that neuron is likely to be due to spurious correlations, so we skip it. We detail this in Appendices D.1 and D.3. We actually plan to work further on the design of statistical tests.

How do you terminate the training procedure? Is there some schedule according to which you pick which layer gets widened? Do you pick the layer with the largest (normalized) expressivity gap?

There are several possibilities to select the best layer to widen: a) as you suggest, compute the (normalized) expressivity gap for each layer and pick the largest one; b) compute also for each layer the best neurons to add, and compare the associated eigenvalues accross layers (as these eigenvalues indicate the first order variation of the loss when adding such neurons). Such a comparison might need special normalization though. c) for each layer, also perform line-search to find the best way to add the neurons, and then compare the real loss gains. As b) and c) have small computational cost compared to a), the last option is the most interesting, as it is the most reliable (being based on the real loss). This is what we have done for training the ResNet-18 architecture on CIFAR-100.

Regarding termination, we stop when both conditions are met:

1. classical gradient descent is not improving performance anymore
2. no neuron is added anymore, that is, there is no way to add a neural anywhere to the architecture that would improve the loss.

what exactly do they improve?

Could you please detail your question more?

Did you consider combination of standard gradient descent and your proposed method? How would they work out?

Yes, this is what we do in practice, for instance with the new experiment on CIFAR-100: after each neuron addition we classically train the network for a certain time. This dramatically improves the results, compared to just adding neurons. However we noticed with a previous implementation that in some cases this would come with unstabilities due to the fact that different parts of the network might need different learning rates. These unstabilities have been tempered by better distributing the amplitude factor on added neurons: we now consider $(\sqrt{\varepsilon} \alpha, \sqrt{\varepsilon} \omega)$ instead of $(\alpha, \varepsilon \omega)$, which makes future gradients more homogeneous.

Thank you for your review and questions.

About presentation

We are very sorry for the typos, we hope we have corrected all of them in the revision, which we introduce in the common reply "New version of the paper, with improved clarity". We have added a description of the main algorithm and are adding details of subroutines in an appendix. More generally we have reworked the paper to make it more clear and easier to follow.

Calculating function gradients is actually very easy, it is part of what the standard backpropagation computes. We have added details in Section 2 and in Appendix A.1 to show this theoretically. We will also release the code (open-source). Technically one just has to call usual backpropagation and intercept an auxiliary computation, for instance with a "hook" in the desired layer.

How do we add neurons to the convolutional layers? Are we structurally adding kernels or adding neurons treating them as fully connected layers?

Adding one neuron to a convolutional layer $l$ consists in adding one kernel to layer 𝑙 and consequently also one dimension to each kernel at layer $l+1$. We added a scheme, in dedicated Appendix A.6, to make this more clear.

What are the benefits of the proposed method? Are we trying to have a method that tries to get the best model among a certain size or a method that can efficiently and effectively grow a tiny network to an arbitrary size? If it is the latter one, can we have some experiments with models that people use in practice?

Our goal is to build models of the right size by iteratively growing the architecture, starting from a tiny model, instead of training large models and pruning them.

So we are interested in minimizing architecture size for a given target accuracy, or, equivalently, maximizing accuracy for a given size. We actually jointly optimize both size and accuracy.

For this we also need indeed to be able to grow models to potentially arbitrary-large sizes, in case the task at hand requires it. We are right now training a ResNet-18 model (with initially very few neurons per block), on CIFAR-100, to check hows the architecture grows (cf common reply "Experiments and architectures").

What is the computational cost of the proposed methods?

We have addressed computational complexity in the common reply "Computational complexity".

Thank you a lot for your review and the raised points, which incited us to rework some parts of the paper and to add important details to the appendix.

In particular:

Clarity of the functional view

We apologize for the notation overload. We have corrected this, notably by distinguishing the sample-loss $\ell$ from the global loss $\mathcal{L}$, and by correcting a few typos. As stated in the common reply "New version of the paper, with improved clarity", we have added Appendix A.1 to get the paper self-contained and to explain what precisely is the functional gradient, as well as how to obtain the property ${v_{goal}(x)} = -\left( \nabla_f \mathcal{L}(f) \right)(x) = -\nabla_{u} \ell(u, y(x))\big|_{u = f(x)}$ which is not trivial indeed. We hope that with the new version of the paper we have answered all of your concerns regarding the mathematical soundness of the paper.

Balancing optimization and adding parameters

This is of course a very important question. We provide a detailed answer in the common reply "Neuron addition strategy", that we will also add to the paper as an appendix.

To answer the remark that the method "adds a fixed number of neurons", note that the algorithm (described in "Algorithm 1", page 9) for that experiment is actually more complex. A fixed number of candidate neurons are proposed indeed, but two selection steps take place afterwards: 1) a selection by statistical relevance based on the singular values (detection of spurious correlations, to avoid overfit), 2) a selection by performance gain (only consider neurons that do improve the loss on a validation set). Thus the number of added neurons may vary.

The number of neuron candidates is fixed in that experiment in order to compare with GradMax, but one can instead select this number in an adaptive manner based on the singular values (which are linked to expected loss improvement as stated by Proposition 3.2). A simple threshold on singular values enables indeed to make layers grow only when needed / useful. In that respect architecture growth can be not scheduled in advance but happen only on demand.

Complexity of the methods

We have addressed this point in the common reply "Computational complexity", which is being included in a dedicated appendix as well. TL;DR: SVD cost is actually low.

Definition of optimality

Thank you for noticing this. Indeed we were using the same word "optimal" for different meanings. We have added a paragraph in Section 2 to make this more clear, and this was the opportunity to better introduce the criterion considered in the next sections. A supplementary appendix (A.3) details these concepts and their intertwinement.

Misc.

Thank you for the minor points and noticing formulations leading to "overly broad claims", that we have addressed. Regarding "[adding random neurons] would not yield any guarantee regarding the impact on the system loss" however, what we mean is that our method yields the best neuron to add to decrease the loss at first order (in a sense now well defined), while a random neuron does not have this property.

Thank you also for the references, which we did not know and are very interesting and indeed related to our work. We will discuss them, in an appendix section though, as space is too limited in the main paper, especially with the imposed bibliographic citation style. Speaking of which:

I have heard the idea of "let's do gradient descent on the architecture" multiple time,

Are you referring to DARTS and to the Lottery ticket hypothesis, or to other papers? in which case, we would be delighted if you could provide references.

About neuron addition strategy

Scope of the paper

The precise strategy to add neurons (how many, how frequently, etc.) is out of the scope of this paper, in the same way that is explicitly out of the scope of the GradMax paper. We chose on purpose a naive strategy for this paper, in order to focus on the way we compute new neurons, and not on the evaluation of the strategy. This way we are able to check that even in very simple settings, step by step, GradMax produces larger architectures that ours for a similar performance gain (and this is expected, as the two approaches do not have the same goal).

Yet, some examples of strategies

However for daily use our implementation does of course include less naive strategies, when considering candidate neurons to be added, based on:

• statistical significance, as spurious correlations can trick the estimation of singular values. We therefore threshold singular values in a theoretically appropriate manner.
• a compromise between performance gain (in terms of loss variation) and added computational complexity (which is related to the number of added parameters). Before adding a neuron, we check that this ratio is above a certain threshold. This can be seen as a modification of the general loss $\mathcal{L}$, to which a criterion "$+ \mu$ Complexity" would be added, similarly to the spirit of Kolmogorov complexity or Minimum Description Length paradigm, except that this is about computational complexity. Fortunately, the hyper-parameter $\mu$ does not need to be chosen: one could start training with a very high value of it, and decrease it progressively each time the architecture growth gets stuck. This way one would obtain a kind of Pareto front between performance and complexity (with a single run!), and the user would just have to select the compromise they prefer afterwards. In this sense, our approach does get rid of all architecture hyper-parameters.

Mixing neuron addition with gradient descent

Regarding how to mix standard gradient descent with neuron addition:

• a) one extreme is to only add neurons, without any form of gradient descent (while still relying on backpropagation); surprisingly, this works not so bad;
• b) a more flexible way is train classically and sometimes add neurons (according to some schedule that itself might depend on last expressivity bottleneck estimations);
• c) an orthogonal option, that can be used with either of the above, is to make use of the optimal move (kind of natural gradient) which is a by-product of neuron estimation, hence bringing a supplementary performance boost after each neuron addition.

Method c) brings flexibility to a), in that old neurons can be updated. If one adds new neurons after a line search on amplitude factor (as in the paper), then each neuron addition brings a significant change in the network, and combinations involving b) have the potential issue that several different learning rates might be needed at the same time by different parts of the network (as some are nearly converged and some are disturbed by recent neuron additions), in which case one has to be careful with learning rates. Method c) does not have this issue, as an amplitude factor line search is performed on these optimal updates as well. On the opposite if one adds neurons with 0 output weights (or 0 input weights), then the point of using a)+b) is mostly to know when and where to add neurons: the difference between various ways to choose neuron input (or output, resp.) weights, such as random initialization, GradMax, or ours, is much less noticeable, as it will be quickly overwritten by standard gradient descent.

About overfit

We assume that the loss $\mathcal{L}$ to be minimized is the real loss that the user wants to optimize, possibly including regularizers to avoid overfitting. In the absence of regularizer indeed, our method applied without safeguards (such as thresholds depending on statistical significance and/or added computational complexity vs. performance gain) should fully optimize the loss and as such completely overfit. Our safeguards are expected to prevent strong overfitting as they actually are regularizers.

About experiments and architectures

We agree that the experiments in the paper may seem to be limited, in that the datasets are relatively small (MNIST, CIFAR-10) and the architectures are not very deep. This said, a 6-layer network, with 4 convolutional layers and 2 fully-connected ones, trained on CIFAR-10 (which is much more varied than MNIST), starts being a good proof of concept (it is not just a 1- or 2-hidden layer MLP as in many theoretical articles), and is sufficient to see a significant difference between our approach and GradMax in terms of performance/complexity ratio.

To show that our approach can scale up, we are currently trying to train a ResNet-18 architecture on CIFAR-10 and on CIFAR-100, as advised by several reviewers. However for this we first need to adapt our code. Besides, though there is no theoretical difficulty, we have not yet implemented our approach for layers such as batch-norm or drop-out, and we are training with a standard setting, without data augmentation or transfer learning for instance, and will have no time till the deadline for standard hyper-parameter tuning (such as learning rate, learning schedule, momentum, etc.). Given that context, we do not expect to meet top ResNet accuracies that can be found in the literature. We can still compare with GradMax in the same setting as ours. We expect same final accuracy, slightly slower training (as GradMax is precisely designed to learn as fast as possible, and both approaches have similar computational complexity), and smaller final architecture (since our approach is designed to avoid redundancy while GradMax is not). Thus we expect a similar Pareto front as in Figure 5. It will be interesting to compare the number of parameters at same accuracy and we are eager to check how much we are able to reduce computational complexity for a same accuracy performance.

The reason why we have not performed such large-scale experiments before is that intensive experimental validation of the current approach does not match our line of research in that it is too early. Indeed, we have been working on extending our approach to the addition of new layers (or nodes) in general computational graphs (any differentiable DAG), as it turns out that layer creation is the same as adding neurons to an empty layer. The theoretical extension is straightforward but the implementation is more tricky, and graph algorithmics have to be considered. We feel that it makes more sense to spend time on experiments once the whole architecture can evolve freely rather than when it is constrained as it is now to a fixed graph (with only layer growth). The paper submitted here is more about the mathematical foundations of the approach (quantifying expressivity bottlenecks, solving them, etc.).

About Computational complexity

The algorithm for architecture growing, when considering a naive strategy of the type a)+b)+c), is:

For a certain number of times (typically, number of epochs/T):
  Train classically for T gradient descent steps, using minibatches of size M;
  For each layer:
    Compute the first K neurons to add at that layer, using a minibatch of size M' (1);
    Select the neurons with significant eigenvalue ;
    Compute the amplitude factor for the new neuron, using another minibatch, of size M" (2);
  Add the best neurons of the best layer;
  For each layer:
    Update its weights using the optimal move (3);

using in plus the following notations:

• number of layers: $L$
• layer width: $W$ (assuming for simplicity that all layers have same width), number of kernels if convolutions
• number of pixels in the image: $P$ ($P=1$ for fully-connected)
• kernel filter size: $S$ ($S=1$ if fully-connected)

Complexity:

• of the standard training part: $T M L W^2 S P$
• of step (1):
  • computation of matrices of interest: $LM' (SW)^2 P$
  • SVD cost: $L (SW)^3$
• of step (2): $L^2 M'' W^2 S P$
• of step (3): $L S W$

The relative added complexity w.r.t. the standard training part is thus: $M'S/TM +S^2W/TMP + M''L/TM + 1/WTMP$.

SVD cost is neglectible

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

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

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

In practice

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

We have added:

• Appendix D.1 about how to pick a suitable minibatch size for estimating matrices of interest, based on estimator variance
• Appendix D.5 with the full algorithm and subroutines
• Appendix D.6 about computational complexity
• Appendix E.3 about experiments with ResNet-18 on CIFAR-100. Our method learns slightly faster than GradMax (which is a surprise, as neuron addition in GradMax is designed to learn as fast as possible), and this with final architectures that are significantly thinner (-30%). This shows that our method does succeed in avoiding redundancy.