The paper: https://arxiv.org/abs/2110.11309, makes the following claim at the end of page 3:
The gradient of loss $L$ with respect to weights $W_l$ of an MLP is a rank-1 matrix for each of B batch elements $\nabla_{w_l}L = \sum_{i=1}^B \delta_{l+1}^i {u_l^i}^T$, where $\delta_{l+1}^i$ is the gradient of the loss for batch element $i$ with respect to the preactivations at layer $l + 1$, and ${u_l^i}^T$ are the inputs to layer $l$ for batch element i.
Suppose that we have an MLP with $k$ hidden layers (every hidden layer is followed by an activation function). Then the weight matrices will be $W_1, W_2, \dots, W_k$ (plus the biases, but they are irrelevant for now), and their sizes will be $(D_1, D), (D_2, D_1), \dots (D_k, D_{k-1})$ correspondingly, where $D$ is the number of input features.
Therefore, hidden layer $l$ has a weight matrix $W_l$ of size $(D_l, D_{l-1})$. Its gradient wrt the loss (for 1 batch element), $\frac{\partial L}{\partial W_l}$, will also be a matrix of size $(D_l, D_{l-1})$.
So if I understand correctly, the authors of the paper are claiming that $\frac{\partial L}{\partial W_l}$ is a rank-1 matrix? That is, every row (or column) can be expressed as a linear combination of 1 only row (or column)? If yes, why? How?
Best Answer
There is an explanation of this identity in the newly-added Appendix D of the updated paper on OpenReview. I've reproduced it here with minor modifications.
Appendix D: Rank-1 Gradient for MLPs
Disclaimer: I'm the first author of the linked paper.