Balancing Gradient Frequencies Facilitates Inductive Inference in Algorithmic Reasoning

Authors: Bong Gyun Kang, Jisoo Mok, Junsung Park, Dongjin Lee, Sungroh Yoon
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: Algorithmic Reasoning, Inductive Inference, Spurious Correlation, Out-of-Distribution Generalization, Optimization

Abstract:
Inductive inference, or extrapolation of general rules from finite instances, is understood to be the foundation of human intelligence. Unfortunately, Deep Neural Networks (DNNs) struggle with inductive inference and thus fail to learn even the simplest algorithms in Algorithmic Reasoning (AR). Existing research efforts on AR with DNNs are limited to those on the architectural design for DNNs. In this study, we investigate the influence of optimization techniques on AR performance. Through toy experiments designed to understand an optimizer's susceptibility to shortcuts in AR, we reveal that Adam, the naive choice of optimization, is easily fooled by spurious correlations. To overcome this shortcoming of Adam, we propose a novel optimizer that avoids spurious correlations by balancing gradients of low- and high-frequencies (BGF). We present extensive experiments and analyses to demonstrate the broad and multifaceted advantages of BGF across various architectures and AR tasks. In particular, BGF expands the AR capability of all explored DNN models and even shows the potential to enable learning of tasks that they previously failed at. The observed success of BGF in climbing the Chomsky hierarchy underscores the importance of optimization for developing advanced artificial intelligence with DNNs.

Decision: reject
Reviewer scores: 6, 6, 8, 3

Reviews and discussion:
<thread>
creation date:
1730573230696

thread_type:
official_review

<thread_object>
creator: reviewer_xigm

<content>
summary:
This paper introduces a new optimizer for Algorithmic reasoning tasks to avoid/mitigate shortcut learning for better OOD generalizability. Especially the work looks into the frequency domain of the gradients. The work provides toy experiments and synthesized spurious correlations in Algorithmic reasoning tasks.

strengths:
•	If the claim is correct, the proposed optimizer would be simple and easy to implement, as it would be just a frequency (low/high) pass filter.

weaknesses:
•	Most of all, the definition of shortcuts is the most serious problem that I have with this paper. I cannot agree with the authors’ definition of “shortcuts” which is stated as “non-generalizing hypotheses are termed “shortcuts.” Shortcut learning happens when a model can minimize the training loss just by looking at simpler features and giving up learning more complex core features. That means if such non-generalizing features are complex enough or more complex than core features, shortcut learning may not happen. That is why the name is ““short”cut” learning. That is why “non-generalizing hypotheses” cannot be just termed shortcuts.

•	Also, the sentence over lines 191-193 “Shortcuts can be interpreted as learning non-generalizing correlations between inputs and outputs that are valid in the training distribution but do not hold in the target distribution;” is not fully true. It depends on the target distribution. If the target distribution is still in distribution, such correlations will still be valid, but such correlations just won’t be visible.

•	This paper only considered two simple forms of synthetic spurious correlations on “toy” experiments. Algorithmic reasoning tasks are a good start and are used to examine the viability of an idea to apply to real-world tasks. It is unclear how this paper’s outcome can be useful for real-world tasks, vision and language. I am not confident to believe the claims stated in this paper as a general phenomenon. Also, nobody knows if something will go different in such Algorithmic reasoning tasks and conventional vision and language tasks?

•	For experiments with spurious correlations in Fig 2, the authors only experimented with spurious correlations of which portion is over 80% (when P >= 0.8). However, when the proportion is just that high the spurious correlation is trivial and straightforward.

questions:
-	The following paper seems to have a good overlap with this submission:
“Frequency Shortcut Learning in Neural Networks,” Shunxin Wang, Raymond Veldhuis, Christoph Brune, and Nicola Strisciuglio, NeurIPS workshop on Distribution Shifts, 2022.
Hence, the novelty of this submission may be hurt.

-	For other points, please refer to the weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730640001420

thread_type:
official_review

<thread_object>
creator: reviewer_cfmm

<content>
summary:
This study examines optimization’s impact on AR performance, showing through toy experiments that Adam, a commonly used optimizer, is susceptible to spurious correlations that hinder out-of-distribution (OOD) generalization. To address this, the authors introduce a novel optimization method, Balancing Gradient Frequencies (BGF), designed to reduce shortcut learning by balancing low- and high-frequency gradients, thus promoting stronger inductive inference. Extensive experiments across varied AR tasks and DNN architectures reveal that BGF significantly improves accuracy, accelerates convergence, and smoothens the loss landscape, enabling DNNs to tackle tasks previously deemed unmanageable.

strengths:
1.	Through extensive experiments, the authors demonstrate that balancing gradient frequencies directly impacts the model’s ability to generalize beyond the training distribution. This insight is particularly valuable, as it highlights the frequency characteristics of gradients as a crucial factor in overcoming shortcut learning, a perspective that has been relatively unexplored in AR.
2.	The study documents a phenomenon termed "train-test splitting," in which DNNs achieve training accuracy early on but require additional steps to attain OOD test accuracy. This splitting behavior resembles the grokking phenomenon and is linked to changes in gradient frequency patterns. The discovery emphasizes the importance of low-frequency gradient components for OOD generalization, offering a new understanding of model behavior during training.
3.	BGF’s architecture-agnostic design is evidenced by improved performance across various DNN types, including RNNs, LSTMs, and Transformer models, on multiple AR tasks. This adaptability underscores BGF’s potential for broad application, marking it as a significant innovation in optimization for generalization across neural network architectures.

weaknesses:
1. Although the manuscript compares BGF with optimizers like Adam, SAM, SWAD, and LPF-SGD, incorporating more recent advancements in optimization techniques that are known to enhance generalization would further strengthen the case for BGF's superiority.

2. Conduct a hyperparameter sensitivity analysis focusing on λ and other gradient-balancing factors (e.g., α and β). This experiment would provide insights into how these parameters influence BGF's ability to generalize, especially under varying data conditions.

3. To deepen insights into how BGF affects gradient dynamics, examining gradient frequencies across different layers of DNN architectures is recommended. This analysis could reveal whether specific layers benefit more from low-frequency gradients, enabling further fine-tuning of BGF for optimal performance in various model architectures.

questions:
see above
</content>
</thread_object>

</thread>
<thread>
creation date:
1730673124409

thread_type:
official_review

<thread_object>
creator: reviewer_oa4z

<content>
summary:
This paper presents Balancing Gradient Frequencies (BGF), an optimizer that enhances inductive inference and OOD generalization in deep neural networks for algorithmic reasoning tasks. Unlike traditional optimizers like Adam, which can learn spurious correlations, BGF balances low- and high-frequency gradient components to avoid shortcut learning and improve OOD generalization. Experiments across various DNN architectures and AR tasks demonstrate BGF’s superior performance and faster convergence.

strengths:
1. The method tackles improving OOD AR tasks by proposing a new optimizer, which is novel and interesting to me.

2. The empirical studies at the beginning of Section 3 are interesting and well-designed, effectively illustrating the susceptibility of standard optimizers like Adam to shortcut learning. 

3. Extensive experiments show that BGF consistently outperforms Adam across multiple architectures and tasks.

weaknesses:
1. The paper lacks formal theoretical analysis explaining why BGF outperforms traditional optimizers. While the empirical results are strong, a theoretical understanding of BGF’s benefits would enhance the contribution.

2. The study primarily compares BGF with Adam, with fewer comparisons to more recent optimizers designed to improve generalization. Including a wider range of baseline optimizers would strengthen the evaluation.

questions:
Please refer to the weaknesses section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730739985740

thread_type:
official_review

<thread_object>
creator: reviewer_pent

<content>
summary:
This paper introduces a new optimization method called BGF (Balancing Gradient Frequencies), aimed at improving length generalization in  Algorithmic Reasoning (AR) through the mitigation of shortcut learning. Building on the experimental findings regarding Adam's vulnerability to spurious correlations in AR tasks, the authors propose that BGF mitigates these correlations by balancing high- and low-frequency gradients. This approach encourages the model to learn general rules rather than relying solely on patterns present in the training data. Extensive experiments are conducted, demonstrating the effectiveness of BGF across various DNN architectures and tasks.

strengths:
Extensive experiments and analyses;

A novel approach to study the effect of optimization on generalization in AR tasks;

The results on multiple DNN architectures and tasks show that BGF effectively improves generalization on test data.

weaknesses:
The task description in the main text lacks clarity. There are too many task-related descriptions in the appendix—such as the "Modular Arithmetic," "Solve Equation," and "Bucket Sort" tasks—that interrupt the flow of the main text and affect its readability.

questions:
Since the low-pass filter is implemented using a moving average filter with a window size of \lambda, what is the basis for selecting the window size \lambda? How does \lambda value affect the results?

In Table 3 [Right], why is the result of gradient filtering with an EMA lower than that with a queue in the LSTM model?
</content>
</thread_object>

</thread>
<thread>
creation date:
1733119111006

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Overall Response

comment:
We would first like to thank all of the reviewers and the area/program chairs for their participation in reviewing of our paper. We are fully aware that the reviewers and the area chair are juggling multiple papers during the reviewing period, and are immensely thankful for taking their time to read our author response.

Here, we provide a summary of our works’s strengths recognized by the reviewers and major discussion/experiments provided in the author response.

>**Strengths**
- **Reviewers peNt, oa4Z, and cFMM** all recognized that the study of optimization methods for Algorithmic Reasoning and the proposed optimization method are novel, well-designed, and effective.
- Most of the reviewers **[peNT, oa4Z, cfMM]** agreed that our analyses on the optimization behavior of Adam and the occurrence of “train-test splitting” offer valuable insights that illustrate the susceptibility of standard optimizers like Adam to shortcut learning and highlight a perspective that has been relatively unexplored in.
- The majority of reviewers **[peNT, oa4Z, cFMM]** commended the design and extensiveness of our experiments to demonstrate the efficacy of BGF, the proposed optimizer. In particular, **Reviewers peNT and cFMM** acknowledged that the architecture-agnostic applicability of BGF allows it to improve generalization performance across various types of DNNs.

>**Summary of Author Response**

During the author-reviewer discussion period, Reviewers peNT and oa4Z commented that our response enhanced the quality of our work and addressed their major concerns. In summary, our author response included following discussions and experiments:
- Extended hyperparameter search to study the effect of changing the window size of BGF ($\lambda$) and gradient balancing factors ($\alpha$ and $\beta$);
- More comparison with recent optimization methods for promoting generalization (Marg-Ctrl Loss and Friendly-SAM optimizer);
- Additional experiments on the decoder-only transformer / real-world composition task to verify BGF’s effectiveness on more complex architectures for solving real-world reasoning tasks;
- Gradient analysis on a deeper recurrent model and decoder-only transformer;
- Extended toy experiments on lower degrees of spurious correlation (P <80%); and
- Detailed task descriptions (in the Revised paper) and clarification on the definition of shortcuts.
    
Thanks to all the reviewers, all of the above material provided importance guidance to improve our paper.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This is an interesting paper combining gradient analysis and neural algorithmic reasoning. To the best of my knowledge, this is the first time such a combination is studied; generally speaking, backward-pass analyses are rare in AR, which is a mistake considering how important learning dynamics can be to OOD generalisation. The Authors' analysis of gradient frequencies directly motivates a solution to balance them, mainly through a low-pass filtering procedure on the gradients observed by Adam.

I would say that in spite of its promising premises, three main challenges remain to the paper's acceptance:

* [xigM] Debate over whether the term "shortcut learning" is appropriately used;
* [oa4Z] The lack of rigorous motivation behind the proposed BGF method;
* [xigM] The downstream applicability of the results, as they are mainly performed over toy / synthetic tasks.

I'd like to make a note that the paper _does not_ need to satisfy all three of these to qualify as a successful ICLR paper, in my opinion. That being said, I would hope to see robust efforts being made to address at least two of them.

**On the treatment of shortcuts**

The key issue in the outstanding discussions seems to be on whether the concept of a shortcut must imply that the discovered solution is _simpler_ than the target solution. On this, I agree with _both_ the Authors and the Reviewer:

* Algorithmic Reasoning is a field where the term 'shortcut' has emerged and become commonplace, and I did not notice a clear requirement there that shortcut solutions need be simpler.
* The Reviewer calls out an important point: the term is commonly used outside of AR to imply something subtly but importantly different. Further, no clear definition of shortcuts is used jointly throughout prior AR papers, meaning it is not trivial to simply call upon prior work without discussing its nuances.

The right course of action would be to _modify the related work section_ to properly contextualise not only what the Authors' definition is, but _how it differs from previous instances where such a term is defined_.

It appears that the Authors made some proposals during the Rebuttal period but did not make any tangible attempts to modify the paper in this direction during revisions. Further, no deeper discussion of various AR definitions of shortcuts was proposed. Sadly, I cannot conclude with certainty that there have been robust steps towards reconciling and contrasting the definition against previous works.

**On rigorous motivations for BGF**

I acknowledge the Authors attempted to respond to this concern by Reviewer oa4Z by noting shortcomings in existing theoretical foundations of AR, through passages as follows:

* _"... research on theoretical frameworks for analyzing the properties of AR remains to be done"._
* _"... lack of theoretical tools for studying AR..."_

However, while the Reviewer acknowledged this, in my opinion the connection between gradient frequencies and shortcuts is currently tenuous at best: the argument is made on the basis of correlating gradient frequencies with a phase of "pure train" and "pure test" performance improvements. But I am unconvinced that there is a 1:1 correspondence between "pure test improvement" regime and "no shortcuts being learnt". Any test set, even if OOD, still only evaluates a particular distribution, and the model could be shortcutting for that particular distribution while neglecting other OOD splits.

For this reason, a stronger theoretical analysis linking gradient frequencies / BGF to shortcuts more thoroughly would have been very welcome.

Further, I'm afraid it is not true that theoretical AR research does not exist. Googling "Algorithmic reasoning" surfaces a Gradient blog post (https://thegradient.pub/neural-algorithmic-reasoning/) which has comprehensive references, many of them presenting theoretical frameworks:

[2] Xu et al. What Can Neural Networks Reason About?. ICLR’20.
[10] Xu et al. How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks. ICLR’21.
[20] Bevilacqua et al. Size-invariant graph representations for graph classification extrapolations. ICML’21.
[22] Dudzik and Veličković. Graph Neural Networks are Dynamic Programmers. NeurIPS’22.

In particular, [10] should be relevant as it studies extrapolation capabilities of neural nets in the NTK regime.

I'm not saying the Authors could have directly applied any of these works, but at least discussing them and why they _wouldn't_ be applicable would have been valuable.

Overall, I see no signs of clear improvement on this front either.

Coupled with the fact no detailed experimentation was performed outside of AR-style synthetic tasks or tasks where specialised pre-training is performed, especially considering that BGF should be easily deployable on _any_ generic text fine-tuning dataset, lead to a recommendation of _rejection_ for this paper in its current form; none of the Reviewers opted to champion the paper.