How to Guess a Gradient

Thank you for taking the time to review our submission and providing thoughtful feedback. We appreciate you highlighting the strengths of our work. We also agree with your assessment that this work is not intended to be immediately practical, but rather a step forward.

Error bars: We have added the error bars for Table 2. Specifically, we report mean and standard deviation over 5 runs. We will soon add error bars for Table 1 as well.

Training/Testing curves: We have added a figure in the supplementary section depicting the train accuracy and test accuracy curves for each model in Table 2. Each plotted curve is the mean of 5 runs, with translucent bands around it indicating standard deviation.

Code: We will share our code and model checkpoints along with the camera-ready draft for transparency and reproducibility. If you have any specific questions about the code, we can answer those as well.

MLP-Mixer: We have added train/test curves and more experiments isolating the reason for the increase in accuracy (see figure 8 and explanation below). The result is repeatable, and we will add error bars in Table 1 soon.

Why is the method better than backprop on the Mixer architecture?: Please note that Ren et al’s [1] Mixer model (using their local losses and activation perturbation) also achieves higher test accuracy than backprop. We only replace the activation perturbation with W^T, which results in a further 1.5% boost in test accuracy. The core factors behind this sudden improvement are twofold: (1) The local losses used by Ren et al provide much more supervision and help the model train to a high accuracy; (2) Their Mixer architecture seems to overfit with backprop.

To isolate local losses as the factor, we ran the same experiment without local losses and plotted the results in Figure 8. We see that the overall accuracy for each model is much lower without local losses, and the gap between W^T and activation perturbation is even larger (since variance reduction matters more when the overall variance is larger).

We also plot train vs. test accuracy, showing that backprop gets better train accuracy (as expected) but generalizes worse. It is not in the scope of our work to speculate why Mixer architecture overfits with backprop, but this could be interesting follow-up work since gradient approximations traditionally overfit more [2].

“Are gradient guesses on MLP mixer unbiased?”: The efficacy of MLP mixers in achieving high accuracy doesn’t necessarily imply unbiased gradients. This complexity is highlighted in our self-sharpening experiments, where significant bias accompanied high cosine similarity and training accuracy. Additionally, the unique dynamics of MLP mixers add another layer of complexity. For instance, the absence of gradient flow between blocks in MLP mixers reduces the potential for positive feedback loops. While bias clearly impacts MLP experiments, its interaction with the model dynamics is still not well understood. Our ongoing research aims to understand these complexities. Along these lines, we have also added further analyses to the supplementary section (Figure 7).

“MLP Mixer experiments/analysis feel incomplete”: We appreciate your feedback, and would like to improve the experiments/analysis. Based on our reply so far, which additional experiment/analysis would you recommend?

“Two Regimes”: In our understanding, the cosine similarity changes as the model trains, and the largest effects of that are seen right at initialization (and immediately after). As mentioned in the paper, our reported cosine similarity and 1-step effectiveness (now with error bars) are computed after each epoch and averaged over 50 epochs. Thus, we largely average over the second regime. This can also be seen by visually comparing the cosine similarity in the plot against the reported mean.

Writing quality and references: We really appreciate the suggestions. We have incorporated several of these already and will follow all of them for the camera-ready draft. Our goal is to make the paper approachable and easy to read.

Proposed methods are heuristic; limited to MLP+ReLU: The observation that our methods are primarily demonstrated using MLP+ReLU models is valid and appreciated. However, it's important to note that our research, while using MLPs with ReLU activations as a foundational model, actually delves into a broader principle. The concept of partial backpropagation, utilizing locally available Jacobian information, is not confined to this specific architecture. In fact, this approach has the potential to be adapted to various architectures. The insights and findings presented in our paper, therefore, serve as specific instances of a more universally applicable principle. We believe this flexibility and adaptability are significant strengths of our proposed methods.

Thank you for the review! Here are the answers to your questions:

Our largest models for MLP experiments: Our largest MLP has 6 layers of width 1024, and operates on 32x32x3 images (for CIFAR10). Thus, it has 7.3 million parameters. Specifically:

3x128 MLP: 411k 3x1024 MLP: 4.2M 6x128 MLP: 460k 6x1024: 7.3 M

Our model for Mixer architecture (table 1): 918k parameters

Crucially, we note that our method can train much larger models than directional descent, and in some cases, achieves comparable test accuracy to backprop (i.e. 77% test accuracy on CIFAR10 with Mixer architecture). This is a direct result of our gradient estimates’ cosine similarity being hundreds of times higher than a random guess.

Applying to CNNs/Transformers: Our method can be applied to CNNs and transformers, but the current formulation does not utilize their architecture/structure. As a result, even though our method performs well on the Mixer architecture, it currently underperforms on CNNs. We hope to close this gap in follow-up work.

Please let us know if you have any other questions or comments

Thank you for the review!

Related work: We completely agree, and will include a formal related work section in the camera-ready draft. We hope to create an approachable and complete summary of the developments in this subfield.

Likelihood ratio approach: The likelihood ratio approach is especially interesting as it seems to be compatible with many different distributions. Since our guesses follow the multivariate normal distribution, this seems like a good match. Furthermore, the probabilistic formulation also naturally supports techniques like importance sampling which could help us reduce the bias significantly.

Confusing line in intro: Thanks for pointing out the confusion. That line refers to local losses used by Ren et al. We have re-written that line to make it more clear.

Relu derivative: ∂ReLU(si)/∂si refers to the jacobian of relu activations with respect to the inputs to relu (pre-activations). Since the input and the outputs to ReLU are both vectors, the jacobian is a square matrix, and since each input controls one and only one output, it is a diagonal matrix. We have edited that section of the draft to explain this a bit better.

Sparsity: Thank you for the correction. It is true that the ReLU activations may not be too sparse, and it depends on many factors. For example, at initialization, close to 1/2 of the units are active. While this is still useful for reducing the guess space, we have clarified this statement in the revised draft. For reference, gere is a plot of observed sparsity fractions in practice for a 1024x6 MLP on CIFAR-10:

Sparsity fraction: https://imgur.com/a/IsGUE3j

W^T low rank: Thank you for pointing this out. Here is previous work showing the claim 1, and we have also added this to the draft.

Activation Perturbation baseline: This baseline refers to an isotropic random guess in activation space rather than weight space. This method is also used by Ren et al. We have added this clarification in the revised draft.

Self-Sharpening: This is an unexpected phenomenon we observe during some of our guessing methods where the space of guesses becomes more narrow or ‘sharpens’, and this improves the cosine similarity to the exact gradient. The reason we call it ‘self’ sharpening is because this narrowing is caused by a feedback loop of decreasing rank of downstream weights. This decreasing rank narrows the guess space, which makes updates less diverse and further lowers the rank. We have updated the explanation in the draft, and will further improve it for the camera-ready draft.

Reporting all methods: Could you please clarify what experiment combinations we should include for Table 2? We can add them to our revised draft for completeness. Related to Table 2, we have also added the corresponding training/testing curves. This covers our proposed methods and relevant baselines (directional descent, backprop, activation perturbation) for various MLP sizes.

Writing quality: Thank you for the feedback. We will focus on writing quality and clarity for the camera-ready draft.

Thank you for the review. We deeply appreciate your interest and suggestions. We have fixed the writing as you suggested, and will address your questions and mentioned weaknesses below:

1-step effectiveness: This metric uses only 1 step rather than multiple training steps, but we average that metric over the entire dataset. Mathematically, we are computing:

Drop_method = loss_original - loss(w - eta * estimated grad) Drop_backprop = loss_original - loss(w - eta * true grad) Effectiveness(method, eta) = drop_method/max(drop_method, drop_backprop) Highest_effectiveness(method) = max_{eta \in [1e-6, 1e-5, … 1e-1]} Effectiveness(method, eta)

That is, we are computing how much the loss goes down with the estimated gradient compared to the true gradient. Unlike cosine similarity, this metric relies on the local curvature of the loss landscape too. This makes it more useful than simple cosine similarity since some errors/biases may not be relevant to the loss (e.g. flat directions in the loss landscape). We average this metric over the entire dataset and report its mean and standard deviation.

Self-sharpening phenomenon: We find self-sharpening to be an unexpected and potentially useful phenomenon (in the context of narrowing guess space) that emerges from the guess bias. We opted to simply report this phenomenon and did not try to control/regulate it in our experiments, and it causes the model to overfit when completely unregulated. However, our singular value experiments show that the rate of self-sharpening can be finely controlled (Figure 5), and we hope to exploit controlled self-sharpening in follow-up work to get fast convergence and less collapse/overfitting.

Fournier et al: Thank you for sharing this reference. We will add this to the related work section in the camera-ready version. Their thorough experimental analysis is also a useful template for our evaluations, and combining the two methods might produce interesting results. Although we cannot compare against this work in the time frame of this rebuttal, we hope to do a larger scale comparison on multiple architectures in follow-up work.

90% test accuracy with backprop: We agree that a higher accuracy model is important to understand this method’s effectiveness fully. For reference, our highest accuracy on CIFAR10 (77.4% test, 90% train) is on the Mixer architecture/losses used by Ren et al. This architecture/loss fails to achieve 90%+ test accuracy with backprop, at least for the model sizes described in the paper (0.9M, 76.4% test accuracy).

We tried to get higher test accuracy with backprop by varying the numbers of blocks and groups, augmentations, and training schedules for the Mixer architecture. However, we were unable to achieve 90%+ test accuracy. To our knowledge, popular MLP-Mixer implementations rely on pre-training and/or significant data augmentation like CutMix to excel at vision datasets like CIFAR10 [1,2].

Thus, we also evaluated our method on VGG16 without batch-norm or dropout. We also added random image cropping (padding=4), horizontal flipping, and mixup augmentation. Although this architecture is not an ideal fit for our method, it gets 90% test accuracy with backprop. The preliminary results are:

W^T currently underperforms in this setting because the current implementation does not exploit any CNN structure or benefit from local losses like in Ren et al. We also have not done any hyperparameter tuning. We are working on those and will keep you updated.

I thank the authors for their reply. Here is my response:

1-step effectiveness: I thank the authors for providing a formal definition of the formula used to compute their effectiveness score, and particularly for emphasizing its superior relevance over cosine similarity.

Self-sharpening phenomenon: I completely understand that the authors discovered an interesting phenomenon in the training dynamics of forward gradient methods, and reported it for further investigations. I am not asking if the authors claim that it is a desirable phenomenon. I am rather asking if, at the time the authors are submitting the article, given the combined experimental results of the activation mixing experiments where the self-sharpening phenomenon revealed itself, and the experiments where the singular value distribution of the matrix $W^\top$ are artificially manipulated, does this phenomenon seem desirable or not? It is not clear from the manuscript. My understanding is that it is not, since it seems to drive the model towards an optimization path where the effective rank of the operator $W^\top$ collapses and thus loses statistical capacity. Again, I am not asking the author to provide a definitive answer to this research question, but rather to summarize the conclusion they can draw from the experiments conducted so far, and if possible, guidelines on what should be the next research step.

Fournier et al: It would be particularly interesting to combine both methods and ablate the contribution of each individual trick, especially since the reported figures are quite high and the inductive bias (greedy optimization) of their method is the main limiting factor, preventing their gradient guess space to cover the true gradient space, hence resulting in poor cosine similarities.

90% test accuracy with backprop: These results are very interesting even though not in favor of the proposed method yet. I do not have much experience with MLP architectures on small-scale datasets, but I know they are avoided in practical applications because of their overfitting tendency. As a first workaround, the authors could use an MLP-mixer pre-trained on ImageNet, albeit there might be some dimensionality issues to handle.

It is however surprising that VGG16 performs so poorly with your method and simple directional descent. I would actually expect something closer to 40-50% with directional descent alone, whether activation or weight perturbation is used. I think the author should have run the VGG-16bn version which contains batch-norm as it is known to greatly stabilize training, allowing a wider range of learning rates without numerical issues. Likewise, I would also suggest making experiments including dropout since you could only perturb the units that are not set to zero, in a spirit similar to how ReLU activations are being handled. Preventing overfitting does solve the fact that the training accuracy remains very low. But the fact that batch-normalization stabilizes training might be explained by a smoother loss landscape, which would make optimization less challenging, thus yielding performances favorable to your method. It would also be interesting to know if the self-sharpening phenomenon remains in such a setting, thus emphasizing a consistent artifact of the proposed training dynamics.