Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The present paper analyzes the learning dynamics of Node Perturbation (NP), a biologically plausible learning algorithm used to train feedforward networks. Overall, the paper states a negative result about the unstability of NP due to weights diverging through learning, grounded in analytically tractable results obtained on linear models in the student-teacher setting carefully checked against numerical experiments. This analysis leads the authors to prescribe weight normalization to prevent this phenomenon. The predicted behavior in the linear regime is empirically observed in non-linear models on two training tasks, which validates the soundness of the aforementioned analysis.

More precisely:

- Section 3 introduces the NP algorithm, recalls that the resulting weight update provides an unbiased estimate of the SGD weight update and shows that the cosine similarity between these two weight updates for a given output layer scales as the inverse of the square-root of the size of this output layer (Eq. 8), suggesting that NP and SGD updates become nearly orthogonal for wide networks. Also, by comparing the covariance matrix of the weight updates for NP and SGD (Eq. 10), they want to highlight that NP is much noisier than SGD.

- Beginning of Section 4 recalls the minimum number of training steps needed to reach an error level for NP in the linear regression setting, and introduces a “deep linear model”, consisting of two linear layers, namely $y=W_2 \cdot W_1 \cdot x$. The rationale behind this choice is to analyze separately the impact of the number of perturbed units and that of the size of the output layer. This deep linear model is studied in the student-teacher setting, whereby the target is given by a teacher network consisting of a linear transformation with some additive Gaussian noise (if this noise is non-zero then the authors say there is a “mismatch” between the student and teacher networks).

- First paragraph of Section 4 shows the analytical NP learning dynamics in terms of the error $\epsilon$ (defined as the squared distance between student and teacher model) and the input weight norm $a=||W_1||$ through time (where time unit is a batch iteration), obtained in the large hidden layer, noiseless (i.e. no mismatch) limit. All the calculations leading to these results are provided in the Appendix. This analysis unveils two main results, summarized by Eq. 14. First, the weight norm grows monotonically increases through time. Second, there are two working regimes for NP, depending on the value of the learning rate used. If the learning rate is smaller than a critical threshold, the error converges to zero, if not the error decreases until the input weight norm a reaches a threshold (corresponding to the sign inversion of $\dot{\epsilon}$) wherefrom the error rises again. Hence the “instability”, which is caused by the input weight norm crossing a threshold. This theory is successfully checked against numerical simulations (Fig 1). Also, the minimal number of training steps required to reach an error level is analytically computed (Eq. 15) and numerically verified (Fig. 2), and highlights its weak dependency with the hidden layer size. 

- Second paragraph extends the previous study to the case of mismatch (e.g. the labels given by the teacher network are noisy, $\sigma_t \neq 0$). It shows that the instability previously always happens, regardless of the learning rate value, the frontier at which it occurs is analytically derived (Eq. 16), and these results are checked numerically (Fig. 3A). There is still a “critical” learning rate threshold delimiting different scalings of the number of updates required to reach minimal error as a function of the learning rate (Fig 3B), a behavior which is in stark contrast with that of SGD (Fig 3C). Fig 4D shows that by normalizing the NP weight update, NP learning is stabilized, at the cost of a bias in the weight update which grows with the hidden layer size.

- In Section 5, the learning dynamics of NP are numerically analyzed on non-linear models on the MNIST and SARCOS training tasks. Again, the instability is observed and vanishes when normalizing the NP weight updates, suggesting that the previous analysis also holds in the non-linear setting. It is also shown that NP is up to 1000 times slower than SGD, which is partially explained by the fact that NP relies on a scalar rather than vector-valued error signal.
strengths_and_weaknesses: Strengths:
- The structure and the writing of the paper are clear. The figures are neat. 
- The mean-field model derived in the linear student-teacher setting matches very well the experiments.
- The theoretical analysis seems to lead to a simple trick to unlock NP scalability.

Weaknesses:
- The derivations in the Appendix are not easy to follow, especially because multiple approximations are sometimes used without detailed steps (I will come back to this in the questions).
- The title raises big expectations that are not met: the term “scalability” calls for complex tasks beyond MNIST. This is a major limitation of the paper.

questions: - L.12: you haven’t yet defined “model mismatch” at this stage, I would remove it. 
- L.24: “However, it remains unclear how robust these approximate learning rules are, or how they perform on large neural networks and complex tasks”. I would downweight this a little bit since you do not go beyond the MNIST task in this paper.
- L.90-106: I’m not sure the biasedness-noise tradeoff brings much added value here. It would free some space to add some more details about the teacher-student theory in the paper.
- L.493, Eq. 27b (Appendix): please detail the computation leading to $L_k + 2\delta_{kl}$. I could check by myself going on the internet to find the moments of a multivariate Gaussian, but I wouldn’t take for granted that any reader knows them by heart.
- L.506, Eq. 33 (Appendix): why does the tensor product between $\left(\sum_l \xi_k\xi_l^Tg_l – g_k\right)x_{k-1}^T$ and $(g_lx_{l-1}^\top - \langle g_l x_{l-1}^\top \rangle)$ disappear?
- L. 510, Eq. 36a (Appendix): I am really confused here. After you swap the second and third dimension, it seems to me, from Eq. 31, that $C_{kl}^{sgd}= \langle g_k g_l^\top \otimes x_{k-1}x_{l-1}^\top\rangle$, which is the second term of Eq. (36a). However, not only you distinguish $ C_{kl}^{sgd}$ from $\langle g_k g_l^\top \otimes x_{k-1}x_{l-1}^\top\rangle$ here, but also a factor 2 appears for no reason in front of $ C_{kl}^{sgd}$. Isn’t there a typo there? My take is that by adding up $ C_{kl}^{sgd}$ and $\langle g_k g_l^\top \otimes x_{k-1}x_{l-1}^\top\rangle$ you may obtain $ 2C_{kl}^{sgd}$.
- L.143: why do you call “deep” your linear model? It’s two layers deep. If you want to refer to the *width* of your linear model (since I acknowledge you study your model in the limit of a large number of hidden units), then use “width” instead of “depth”.
- L.149, Eq. 11: for completeness, it would have been useful to include the derivation of this result in the Appendix.
- **General important remark**: please do not abusively refer to equations or Figures in the Appendix, it hinders the fluid reading of the main.
- L.152: we do not understand here what you mean by “optimal learning rate”, i.e. how $\eta^*$ is precisely defined.
- L.549, Eq. 46 (Appendix): since the quantity $E\cdot x + \sigma_t z$ appears, it goes to suggest that $E$ is defined as $A – W_2\cdot W_1$, which is opposite in sign to Eq. 43. 
- L.557 (Appendix): when you write that you “drop the higher-order terms”, I understand that you approximate the mean of a product of two quantities as the product of the means of these two quantities (at least this is how I can recover your result), is this correct? Please be more precise about it.
- L.561-567: very difficult to understand.
- While I can understand all the computations up until Eq. 57, from Eq. 58 onwards, the computations are no longer detailed. It’s very hard to follow because when you write $\approx$, you may perform two approximations at once: 1/ the mean of a product is the product of the means (eliminating “higher order terms”) 2/ the trace of a product is the product of the traces (Eq. 52).
- L.596, Eq. 71 (Appendix): please detail the computation.
- L.626, Eq. 82: with $0 < a_{init}<2/c_0$, you write $-a_{init}^3 < -(2/c_0)^3$, which is wrong ($x\to x^3$ increases on $\mathbb{R}^+$), so I am skeptical about the $\eta^*$ you obtain in Eq. 83.
- B.4 (appendix): these computations are not sufficiently detailed.
- L. 197: which saturation are you talking about? I can’t see the orange curve saturating on the Fig you refer to (Fig 2A).
- L.199-209: it’s very handwavy, and I do not understand the added value of this paragraph.
- Figure 5: this figure displays the accuracy while the others show the error. It would be easier to compare results across different figures if the same convention (all error curves, or all accuracy curves) is taken. 
limitations: My main concern is that this work,  titled "stability and **scalability** of NP learning", does not go beyond the MNIST task.

I think the most important contribution of this work is theoretical: there is an excellent match between theory and experiments as per the Figures shown in the main on linear models, which extend to non-linear models and gives a very simple insight as to how to use NP properly -- that is: by normalizing the NP weight updates. I think this simple result would have been even more compelling if for instance demonstrated on a 4-5 layers convolutional architecture trained by NP on CIFAR-10, the ideal situation being: without weight update normalization the model doesn't train, with weight update normalization it trains (even very slowly, but it does). Then, it could be concluded that the theoretical model proposed totally accounts for the unscalability of NP when normalization is not applied. As it stands, with MNIST being the most difficult task tested, it's harder to conclude the same.

In the bioplausible deep learning literature, the MNIST task alone as a benchmark to claim scalability is unsufficient to my eyes. However, it might be that the sole theoretical contribution of this work and MNIST benchmark abide by the standards of another community (e.g. statistical physics x ML) I may not be aware of, so my judgement might be biased by the fact I come from the bioplausible deep learning literature. Also, I think that the theoretical contributions should be better highlighted in the main. 

I would recommend accept if:

1 - The authors ran a CIFAR-10 experiment with a 5 layers-deep convolutional architecture, observed the same kind of behavior as on MNIST and SARCOS.

2 - Computations in the appendix are more detailed than they are now -- see the questions section above.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers the dynamics of training deep networks with node perturbation. The authors provide a detailed theoretical analysis of learning dynamics of node perturbation vs. SGD in linear networks with one hidden layer in the limit of infinite width. The analysis reveals that the input weight norm determines whether the loss increases or decreases during training with node perturbation, with large weight norm corresponding to unstable training. This motivates using weight normalization for node perturbation. Empircally, on linear and nonlinear networks, weight normalization stabilizes training with node perturbation.
strengths_and_weaknesses:  **Originality**
The work is original. The analysis on deep linear networks is novel and the insights from the experimental and theoretical results are not previously explored. To my knowledge, this paper is the first to provide a theoretical explanation for why weight normalization is useful for node perturbation.


**Quality**
The contributions are high quality. The theoretical analysis appears sound and the experiments are comprehensive. One potential drawback is that the experiments mainly consider simple datasets (SARCOS and MNIST) and mostly consider only one hidden layer networks (although a few experiments consider multilayer nonlinear networks). Investigating the performance of node perturbation in more challenging settings and more complex architectures could help justify the usefulness of the linear network analysis. However, this is not strictly necessary given that many of the main contributions of the paper are theoretical.


**Clarity**
The paper is well written. The mathematical notation is clear and the figures are well illustrated. However, many of the key and interesting theoretical results of the paper are in the supplementary material (particularly the mean-field dynamics of NP). It may help to provide a brief sketch of these results in the main paper.


**Significance**
The paper may have significance to researchers specifically studying node perturbation as a learning rule. However, its applicability to the field of biologically plausible learning appears more limited especially given that node perturbation does not appear to be empirically as effective as other biologically-plausible alternative learning rules. Moreover, the experimental results are limited to simple datasets and architectures. The significance of the paper could be significantly enhanced by exploring more complex settings and showing, for example, significantly improved performance of node perturbation when it is combined with weight normalization.
questions: How does node perturbation with weight normalization perform in more complex datasets and architectures?

How might neuron-wise weight normalization be implemented biologically? Is there biological evidence for such a normalization?

Why is node perturbation a relevant model of biological learning to consider compared to other proposed biologically-plausible learning rules?
limitations: The authors address the limitations of their work in the discussion section. As they note, the utility of node perturbation is limited in the supervised setting, although its utility is more clear in a reinforcement learning setting. The authors may also want to comment on the potential applicability of their linear analysis to other settings; as they empirically find, the qualitative observations of the linear network extend to certain nonlinear networks. The authors may wish to specify in which settings these observations may not apply.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors present a neat analysis of the scalability and stability of the node perturbation algorithm, which is one of the popular bio-plausible credit assignment algorithms, for deep networks. Based on their analysis and inferences, they introduce a weight normalization trick that seems to alleviate the issues with the algorithm, albeit at the cost of adding a bias to the gradient estimates. In the first part of the paper, the authors use analytical tools to dissociate the effect of number of output nodes of the network from the number of perturbed nodes of the network to claim that node perturbation is scalable for deep linear networks. However, they demonstrate that the dynamics entails an instability in the weight norm. They validate these analytical results empirically in deep nonlinear networks and therefore establish a key result in training networks using node perturbation. They also show that the instablity is worse when there is noise in the labels (i.e. teacher noise). Finally, they demonstrate that the weight normalization trick can help stabilize the algorithm, albeit hurt performance by introducing a bias in the algorithm -- as evidenced by lower performance on the SARCOS and MNIST tasks.
strengths_and_weaknesses: Strength:
1. The paper is well motivated and tackles an important problem in the field. The analytical methods used in the paper are an important contribution towards understanding how node perturbation algorithms can be used to develop bio-plausible learning rules in deep networks.
2. The paper is theoretically strong and demonstrates via simulations how the analytical results hold in practice, as well as when nonlinearity is introduced in the network.
3. The weight normalization solution is a smart solution and a good integration of the inferences from the analytical framework. Furthermore, it also fits well with the homeostasis viewpoint wherein weights of a neuron are thought to conserve some quantity over time.

Weaknesses:
1. The presentation of the paper can be improved, particularly how the analytical results are presented. I felt a lot of the details of how the results were derived were buried in the appendix with limited reference to these considerations/assumptions in the main text. The authors could consider rewriting certain sections of the paper to better reflect the derivations of their theorems and in doing so, allow the reader to appreciate the contribution that this paper makes. 
2. The weight normalization strategy could be better introduced, particularly how in adding a weight normalization step introduces bias in the weight update. It would be great if the authors could add elaborate on this bias and how a bigger hidden layer size contributes to a higher bias. 
3. The metrics used in the paper make sense while analyzing the instablity of the node perturbation algorithm. However, it would be nice to report the accuracy/performance metrics on SARCOS and MNIST for SGD and weight-normalized NP. I feel this would be more complete and lay the foundation for further researchers (who could use weight-normalized NP as a baseline method).
4. The discussion about representation similarity is a bit sudden and lack compact presentation. Given that the merits of the paper lie in the stability analysis of the NP algorithm and proposing a possible workaround to that, I would suggest either cutting down on analyzing learned representations (although it is very important and an interesting direction) or fleshing it out more to convey the inferences better.

Overall, I feel that the paper presents a very thorough analysis of the NP algorithm and demonstrates a key feature in the dynamics. If the authors could improve the writing a bit, this work would appeal to a larger audience and could make a significant impact in the field.
questions: 1. What is the dimensionality of $g_l$? I initially assumed that you used the numerator notation while writing vector calculus and therefore $g_l \in \mathcal{R}^{1 \times L_l}$, where $L_l$ is the dimensionality of $h_l$ or the number of neurons in $l^{th}$ layer. But from my understanding after reading the appendix, you assumed $g_l$ to be a column vector and therefore derived: $\frac{1}{\sigma}l(\tilde{x_K},x_0) - l(x_K,x_0) = \frac{1}{\sigma} \frac{\partial l}{\partial x_K} (\tilde{x_K} - x_K) = \sum_l \frac{\partial l}{\partial x_K} \frac{\partial x_K}{\partial h_l} \xi_l = \sum_l g_l^T \xi_l$. Is that correct? Perhaps add the dimensionality of the quantities in the appendix for clarity?
2. What does it mean to have lower linear dimensionality in the representations? Does the lower dimensionality underlie poor performance? This link was not clear from your description.
3. Re the weigh normalization scheme: Is it applied such that the weight normalization is the same at initialization? Can it be applied intermittently or as a regularizer? You mentioned why weight decay is not a solution to the instability problem but it wasn't clear if explicit weight normalization where the weights are allowed to grow from the initialization case could be a potential solution to the instability problem.
limitations: I think the authors do a commendable job in stating the limitations of their proposal but I feel it could be elaborated in the discussions. Specifically, how does the weight normalization introduce bias and its effect on the performance.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors study a stochastic gradient-free learning rule for deep feed forward neural networks, node perturbation. The learning rule in brief is to perturb the activity of each neuron by a Gaussian and then update the corresponding weights in proportion to the sampled difference in the loss function.

The authors develop a mean field theory for a two-layered linear network whose target function is given by a linear transformation with additive Gaussian noise. This allows them to solve for a critical learning rate in which the learning process is as fast as possible. They find that even with the critical learning rate, node perturbation is slower than stochastic gradient descent. In particular, it is asymptotically slower by approximately a factor of the output size. In addition, their theoretical results reveal an instability in the error dynamics once a certain threshold is crossed, and the authors introduce weight regularization to remedy this.

Finally, the authors numerically test the performance of the regularized node perturbation algorithm on the supervised learning tasks MNIST and SARCOS, and show that the algorithm is indeed capable of learning these tasks.
strengths_and_weaknesses: The authors provide original theoretical and numerical results about a particular learning algorithm which are clear and straightforward to understand. From a machine learning perspective, the main drawback of the paper is that they are mostly showing weaknesses of an existing algorithm instead of introducing something new and performant. That said, the weight regularization does successfully stabilize the learning process and it is somewhat interesting that the algorithm is able to learn MNIST and SARCOS with the regularization in place.

One problem I have with the SARCOS figures is that there is no benchmark shown; everyone knows that an accuracy of 98% on MNIST is acceptable, but since I'm not intimately familiar with the SARCOS task I would like to see either a SoTA MSE taken from the literature, or at least the MSE of the SGD-trained models alongside the NP-trained models for comparison. It is explained in the text that the target error was 5.0, but it is still not clear to me whether or not this is a good value in the grand scheme of algorithms which solve this task. Another way to make the error values easier to interpret would be to report $R^2$ instead of MSE, but either way some kind of benchmark should be shown.

The central justification for the lacking performance of the algorithm is its biological plausibility. This makes sense, but I did not get a very clear message from the authors as to whether or not they really believe this algorithm is used somewhere in the brain. I agree with the author's statement "an algorithm is biologically implausible if it takes an inordinately long time to reach good performance." However, I did not understand the citation of Figures 4E and 5B when they said "its [NP's] performance deficit is smaller when compared to
a reinforcement learning rule using the error backpropagation." From what I understood, these figures show that it takes longer to train NP than reinforcement learning or SGD, especially as depth increases. If I understood correctly, it seems this would be in contradiction to what is said in the discussion, and then it is difficult to rationalize the use of NP in the brain. There should be some clarification either in the figures or in the discussion.

I also think its worth noting that inverse problems (including SARCOS) are often solved innately by the brain. When a calf (or any quadruped) is born, they don't spend any number of epochs learning what torques are required to move their hooves from one place to the other, walking occurs immediately, suggesting that the capability was genetically encoded into the architecture, not learned. The authors could, of course, defend the claim that NP is used for learning more complex motor tasks, such as those performed by humans, but then it would also have to be clear whether or not the algorithm is really fast enough for this.

I understand the motivation of using SARCOS to test the capability of the algorithm to solve a motor task. However, since the paper's story has biology at the center, I think it would be much more convincing if the authors also took one of the tasks from one of their biological citations and replicated it with their algorithms. Even including the purely model-based task from Fiete et al, 2007 would make the argument that NP aids in songbird learning more than a passing remark.

Overall, I think a more clear story would be greatly beneficial to the paper and better determine its significance. If a central argument is that the brain *probably* does use regularized NP for motor learning, I would be skeptical and would be interested in further discussion of the biological literature; the citations Kornfeld et al, 2020 and possibly Bouvier et al, 2018 might support this line of argument if the results were better reflected upon in the paper. On the other hand, the story could be that the slowness of the algorithm, even in an idealized setting, demonstrates that the brain cannot be using it except as an auxiliary tool to a more powerful learning method.
questions: My most central and concrete question is whether NP is slower or faster than the reinforcement algorithm. I got mixed messages from the figures and from the discussion section.

In the abstract of Fiete et al, 2007, the authors state that their version of node perturbation "learns in a reasonable amount of time" and "Varying the number of neurons in HVC and RA has little effect on learning time." Do these 2007 results agree or disagree with the present results and why?
limitations: Societal impact is not very relevant; the results of the paper are far too theoretical for negative societal impact to be speculated upon. Performance limitations were adequately reflected upon.
review_title: null

Meta-review: metareview: Authors theoretically analyze and numerically verified statistical properties of node perturbation which is one of the more biologically plausible but slower learning rule. Authors show both the benefits and limitations of the naive node perturbation in terms of learning trajectory. In particular, node perturbation is unstable under practical regimes. They propose a biologically plausible weight normalization scheme which overcomes some of the limitations of the naive version (but introduces some bias). This work advances the theoretical understanding with significant contribution to the neuroscience of learning. The expert reviewers agree that the work is original, clear, and of high quality. I suggest revising the title to indicate both the negative and positive sides of the analysis, perhaps "On the stability and scalability of Node Perturbation Learning" would be better.
confidence: Certain
Decision: Accept