Gradient Descent Resists Compositionality
Authors: Yuanpeng Li
Liang Zhao
Joel Hestness
Kenneth Church
Mohamed Elhoseiny
Venue:  (2021)
Keywords: Compositionality

Abstract: In this paper, we argue that gradient descent is one of the reasons that make compositionality learning hard during neural network optimization. We find that the optimization process imposes a bias toward non-compositional solutions. This is caused by gradient descent, trying to use all available and redundant information from input, violating the conditional independence property of compositionality. Based on this finding, we suggest that compositionality learning approaches considering only model architecture design are unlikely to achieve complete compositionality. This is the first work to investigate the relation between compositional learning and gradient descent. We hope this study provides novel insights into compositional generalization, and forms a basis for new research directions to equip machine learning models with such skills for human-level intelligence.

Under review as a conference paper at ICLR 2021
GRADIENT DESCENT RESISTS COMPOSITIONALITY
Anonymous authors
Paper under double-blind review
ABSTRACT
In this paper, we argue that gradient descent is one of the reasons that make com- positionality learning hard during neural network optimization. We find that the optimization process imposes a bias toward non-compositional solutions. This is caused by gradient descent, trying use all available and redundant information from input, violating the conditional independence property of compositional- ity. Based on this finding, we suggest that compositionality learning approaches considering only model architecture design are unlikely to achieve complete com- positionality. This the first work to investigate the relation between compositional learning and gradient descent. We hope this study provides novel insights into compositional generalization, and forms basis for new research directions to equip machine learning models with such skills for human-level intelligence. The source code is included in supplementary material.
INTRODUCTION
Compositional generalization is the algebraic capacity understand and produce many novel combinations from known components Chomsky 1957: Montague 1970), and it is a key element of human intelligence (Minsky) 1986 Lake al. 2017) to recognize the world efficiently and create imagination. Broadly speaking, compositional generalization is class of out-of-distribution generalization (Bengio 2017). where the training and test distributions are different. A sample in such a setting is a combination of several components, and the generalization is enabled by recombining the seen components of the unseen combination during inference. For example, the image domain, an object is combination of multiple parts or properties. In the language domain, sentence is a combination of syntax and semantics. Each component of an output depends only on the corresponding input component, but not on other variables. We call this the conditional independence property, and will formally introduce in Section
People hope to design machine learning algorithms with compositional generalization skills. However, conventional neural network models generally lack such ability. There have been many attempts to equip models with compositionality (Fodor & Pylyshyn| 1988 Bahdanau et al., 2019), and most efforts focus on designing neural network architectures (Graves et 2014] Andreas et al. 2016
Henaff al. 2016 Shazeer al.] 2017 Li et al. 2018; Santoro et al. 2018 Kirsch et al. 2018
Rosenbaum et al., 2019 Goyal et al.) 2019). Recently, multiple approaches showed progress in specific tasks (Li al. 2019 2020 Lake 2019 Russin et al. 2019), but we still do not know why
standard approaches seldom achieve good compositionality in general.
In this paper, we argue that there is a bias to prevent parameters from reaching compositional solutions, when we use gradient descent in optimization (please see Figure for illustrations). This because gradient seeks the steepest direction, so that uses all possible and redundant input information, which contradicts to the conditional independence property of compositionality. This problem is not due to how gradient is computed, such as back propagation, but caused by the essential property of gradient. We derive theoretical relation between gradient descent and compositionality with information theory. We also provide examples and visualization to show the detailed process of how gradient resists compositionality. Based on the finding, propose that compositionality learning approaches with model structure design (manual or searching) alone are not likely to achieve complete compositionality.

---

Under review as a conference paper at ICLR 2021
X1
Yi
X1
Y1
A
A
BB
X2
Y/2
X2
VoL
Figure 1: Conceptual illustration of compositionality and the impact of gradient descent. X1, X2 are entangled input, and Y,, Y2 are entangled output. Y; aligns with X,, for = 1, (Left) Compositional solution with A (Middle) Non-compositional solution with 8g. (Right) In parameter space, gradient descent encourages parameters closer to 8g, than AA. hence resisting compositionality.
We hope this research provides new insights and forms a basis for new research directions in compositional generalization, and helps to improve machine intelligence towards human-level. The contributions this paper can be summarized as follows.
The novelty of this work is to find the relation between compositional learning and gradient descent in optimization process, i.e., gradient descent resists compositionality.
We theoretically derive the result and explain why standard approaches with architecture design alone do not address compositionality.
RELATED WORK
Compositionality Humans learn language and recognize the world in flexible way by leveraging systematic compositionality The compositional generalization is critical human cognition (Minsky 1986.
Lake et al. 2017). and it helps humans to connect limited amount of learned concepts for unseen combinations. Though deep learning has many achievements in recent years (LeCun et al.) Krizhevsky et al. 2012 Yu & Deng 2012 [He et al. 2016 Wu & et al 2016), compositional
2015
generalizationn has not been well addressed (Fodor& Pylyshyn 1988
Marcus
1998 Fodor & Lepore
2002
Marcus 2003
Calvo & Symons 2014).
There are observations that current neural network models do not learn compositionality (Bahdanau al. 2019). Most recently, multiple approaches proposed to address compositionality in neural networks (Li et al. 2019 2020 Lake 2019)] Russin et al., 2019) for specific tasks. However, we are
still not sure why compositionality hard achieve in general cases, and this work discusses about this problem from optimization perspective.
Another line of related work is independent disentangled representation learning (Higgins al. 2017. Locatello et al. 2019). Its main assumption is that the expected components are statistically independent in training data. This setting does have transferring problem in test, because all combinations have positive joint probabilities in training (please refer to Section
Compositionallity is applied in different areas such as continual learning (Jin al. 2020 2020), question answering (Andreas et al., 2016 Hudson & Manning 2019 Keysers et al. 2020) and reasoning (Talmor al. 2020).
Gradient Descent Gradient descent a powerful and general purpose optimization tool for solving
large scale problems in deep neural networks. It is usually used in stochastic way (Stochastic Gradient Descent) with mini-hatches, and has many variations such as Momentum (Rumelhart et al..
1986). averaging (Polyak & Juditsky 1992), AdaGrad (Duchi al. (201)) AdaDelta (Zeiler 2012 2 RMSProp (Tieleman & Hinton| 2012). Adam (Kingma & Ba 2014).
Most of the previous work focus on faster reduction of loss and theoretical convergence analysis of
SGD Bottou et al. 2018
Luo| 1991| Reddi et al.) 2018 Chen et al., [0188] Zhou et al. 2018 Zou &
Shen 2018 De al. 2018 Zou et al. 2018 Ward et al. 2018 Barakat & Bianchi 2019). In particular,
this work focuses on investigating why standard neural network training only achieves limited level
of compositionality by studying the relationship between gradient descent and compositionality.
2

---

Under review as a conference paper at ICLR 2021
3 CONCEPTS FOR COMPOSITIONALITY AND GRADIENT DESCENT
We first formulate compositionality using the conditional independence property, and define composi- tional generalization. We then review properties of gradient for the derivation in the next section.
Conditional Independence Property for Compositionality When multiple hidden variables live in the same representation, and cannot be separated by simply splitting the representation, then these variables entangled in the representation. For example, color and shape are hidden variables and they share the same representation of image. Also, syntax and semantics are two hidden variables and they share the same representation of sentence. When we extract the hidden variables from their shared representation, we disentangle them.
We then consider prediction problem, where input X and output Y have multiple entangled components that are not labeled in data, and they are aligned. For example in machine translation, X1 imput syntax, and X₂ is input semantics. Y1 is output syntax, and Y2 is output semantics. The syntax of output Y1 depends only on the syntax of input X1, and the semantics of output Y2 depends only on the semanties of X2. We can formalize the alignments as conditional independence property: Y; depends only X₁.
: P(Y XK, Vi......... Yi-1, V41, YR) X.).
When model fits this property, we it has compasitionallit. Note that this can be understood as kind sparseness property (Bengio 2017), because restricts effective connection between input and output components.
Compositional Generalization compositional generalization, each sample either training or test is a combination of several components. A test sample has combination that does not appear in training, but each component the test sample appears in training. We need to recombine the seen components to generalize the test sample. We can define compositional generalization probabilistically as follows.
In train,
In test, P( .x) > 0,
Vi P(X,) > O, P(X , Xx) = 0,
Vi: P.Y is high.
P(Y....... Yx X1 .,....,
Xx) is predicted high.
Compositionality bridges the gap between training and test distributions to achieve compositional generalization. We first apply chain rule, and then compositionality follows.
K
P(Y YR|XI, Xx) II P(Y XK, Y, Y. = II P(Y.X.). i=1
t=1
When P(Y:(X;) are all high, their product should also be high. Therefore, model with compositionality sattiiin this conditional independence property property-addressee addresses compositional gen- cralization.
Property of Gradient For function fZ ( ... 2x). the gradient V the steepest direction to change the function's 's value. Generally, gradient descent methods estimate V using low-order local estimation. By definition, it is the vector of partial derivatives with respective to the inputs.
af
0f
vs
dz
Or
We will use the following definition in later arguments.
Definition 1 (Partial derivative). Partial derivative for input is the derivative assuming other inputs are constant.
Vi 1, .,.., K: (f(r,...... ...,,)))) df(..... .i, .K)
Ox:
dx;
3

---

Under review as a conference paper at ICLR 2021
X1
y
h
X
YK
Figure 2: Extended neural network structure. Middle part is original model structure (one input and output). Extending with X, .1,...: Xx (left) corresponds entangled input. Extending with Y, Vi...., YK (right) corresponds entangled output.
GRADIENT DESCENT RESISTS COMPOSITIONALITY
We focus on the early phase of training to show that gradient descent causes a model to use the redundant information to compute output when it has information to reduce the loss. We develop the arguments step by step. We first analyze the influence of the input on an output variable. We then consider the case of entangled inputs and one output. Finally, discuss the case with entangled inputs and entangled outputs.
The gradient is used to reduce loss, so aim relate loss reduction and the influence from input to output. To do that, we use mutual information to describe the influence, and use knowledge from information theory (Definition 2 Theorem [ and Theorem 2). We also study the impact of gradient
descent to the influence, so we relate mutual information with gradient with Proposition [
Definition 2 (Markov chain (Cover 1999) p.34). Random variables X, Y, Z are said to form a Markov chain in that order (denoted by X + Z) the conditional distribution of depends only on Y
and is conditionally independent of X.
Theorem (Data-processing inequality I(X;2)
(Cover 1999) p.34). If Y Z, then 1(XYY) Z
Theorem 2 (Chain rule for information (Cover 1999) p.24). I(X, Y; Z)
For random variables X, Y, Z.
+ [(X; Z).
@Y Proposition 1. When ax is defined, ((X;Y) 0
@Y 0x
Proof. T(X;Y) > 0 means X and Y are not independent, which means Y is not invariant to X.
4.1 ONE INPUT AND ONE OUTPUT
We first consider a basic setting that the data has a single input and output Y. model f with parameters 0 has input and output ÿ (Figure middle). We optimize a loss function L. Applying the gradient V.C(Y, Y) reduces L(Y,Ý) bringing Y and Ý closer. Since Y changes according to X, Y is encouraged to change according to X. We look into details as follows.
In the common supervised learning setting, given X, the ground truth Y does depend on prediction Y, which means they form Markov chain - + We not require specific form of the loss function, L. but we assume that when it is reduced, Y moves closer to Y, and increases the mutual information I(Y, Y). Many widely used loss functions encourage increased mutual information between model output and dataset labels. Also, training algorithms are designed to reduce loss when the input has information to do so. These assumptions likely hold especially in the early part of training. We also use local linear approximation when discussing gradients, i.e. de = Ar. We derive the proof by studying relations between random variables, and show that gradient descent increases the lower bound of mutual information between model input and output, hence the output is dependent on the input.
Proposition 2. Ifa small change of parameters AO increases I(Y; YY)) then 1(X; Yo- is positive with parameters 0 A0. 4A0: AT(Y; Yo) > 0 = T(X; T(X; Yo+ 0.
4

---

Under review as a conference paper at ICLR 2021
Proof. Since Y and y are conditionally independent given X, ie., y + X Y, with data- processing inequality (Theorem 1. I(Y;)) X) 2 I(Y;)) So (Y;Yo+a0) ) is lower bound of [(X; Yo+s)))))) By definition, AT(; Yo) I(Y; ((Y;Y++49) I(Y;Yo), so that I(Y; Yo+2o) T(Y;Y) + AT(Y;);)) Vo). We also have T(V; Vo) 2 by definition. Therefore T(Y; (Y;;)) O.
I(X;Yo+se) 2 ; Yotso) ) - I(:; Yo) + AI(Y; >0
Proposition If X has information to reduce loss C(Y,Y), OY ax + 0 for updated parameters.
Proof. Since training algorithm reduces loss, with local linear approximation, gradient descent reduces loss. This increases mutual information, so that Proposition 2 applies. So we have
[(X; Yotao) > O. With Proposition
|
we have ař ax * for the updated parameters 0 0 A0.
O
4.2 ENTANGLED INPUT AND ONE OUTPUT
Then, we study the case where input X is entanglement of multiple hidden input components XI,..,,K: and output is single variable Y that depends only on X,, We hope to make Y invariant Xj. Vj + i. For example, in a parsing task (Li & Eisner 2019). output parse tree Y depends only on the input syntax X1, but not on input semantics X2.
For the convenience analysis, we assume we have fixed differentiable oracle encoder network and decoder network 9 9 maps X to XI...., XK. and g maps them back.
X gX1, (X1,.... Xk)
X1
XK = g (X)
We extend the model structure with g and g and use the input to g as model input (Figure left and middle).
Φ lo
This model is exactly the same as the original one, because there is additional trainable parameters, and g g does not change X.
Proposition If & has information to reduce loss L(Y, 8), oy Ox,
# for updated parameters.
Proof. With the property of gradient (Definition we can regard X Vj A i as constant values when computing the gradient w.r.t. X₃. So, with linear approximation, Proposition Ba applies. C
4.3 ENTANGLED INPUT AND ENTANGLED OUTPUT
We then discuss the case that output Y is also the entanglement of Yı,..., Yx. . Y; depends only on X; for all i 1,.... K. This corresponds the example of machine translation.
We assume we have fixed diffcrentiable oracle encoder network h and decoder network h h-1, takes Y input and produce K outputs ...... YK hYY). and h maps them back. We extend the model structure with h and h-1 (Figure
Ý = S-hoh-la f
This model is the same as the original one, because there is no additional trainable parameters and h o h1 does not change Ý. We derive proof with this extended model. The intuitive idea is that the reduction of loss will make each Y, contain more information of Y, and for each Y,, we can apply previous discussion. We denote Y = Vi,...,Y,_, Yomt...., YK.
BY: Proposition If X, has information to reduce loss L(Y, Y) through the change V, then Ox 0, Vj 4 ifror updated parameters.
+
Proof. We first use chain rule of gradient to separate the gradient to sum of K terms, each correspond- ing to V;: ac
ΣK
BÝ, 8C We look at term for a6; ac Y are constant when computing 36 BY,
00
Di=1 08 BY,
5

---

Under review as a conference paper at ICLR 2021
100
Train
80
30
Train B
Accuracy (%)
Accuracy (%)
Test B
60
20
40
Train
10
20
Train
0
Test B
0
50
100
150
200
20
40
50
Steps
Steps
(a) Image classification experiment.
(b) Language learning experiment.
Figure 3: Results for both the first (Train/Test A) and second (Train/Test B) settings. In the first setting, the training performance increases rapidly (blue), but the test performance (cyan) is not close to the training one. the second setting, the training (red) and test (brown) performances are close. This means that the gradient descent uses the second input accelerate training, but it lacks compositionality.
ac (Definition and Yze are not included in aY: ØY:
50 so that we can treat Ye as constant for this term.
We then look at the conditional mutual information T(Y: YIKşs) for this term. With chain rule for information (Theorem 2). have I(Ý; Y) I(x; Y( + I(L Y). Since Y and Eςu are both fixed, (( Y) is fixed. So the change of [(Y; equals to the change of I iÝ{;; Y (Ez)). Therefore, the reduction of loss L increases the mutual information for the component. We can then apply Proposition 4 With linear approximation, the change of parameters (λ0) computed with gradient descent is the sum of changes of parameters (AO,) for each term, i.e., AO = Σ Ad,. It is unlikely that A6, can be cancelled by the sum of other 20,, * because each component corresponds to different underlying factors, and they are not contradictory. Hence, this proposition holds.
L
In Proposition 4 and Proposition 5 the gradient is not zero, so an output depends on redundant input (Proposition 2 both cases. Therefore, gradient descent resists conditional independence property of compositionalliy.
5 EXAMPLES
In this section, we show example cases to emphasize that the theoretical result occurs practically. We focus on the conditional independence property, and we design the experiments in the following way. To test the compositionality, we use different training and test distributions, and the test prediction requires compositional generalization. We measure training and test accuracy to evaluate the ability for compositional generalization.
We use two settings in each experiment. In the first setting (A), we use both X1 and X2 as input to the model. In the second setting (B), only use X1, and remove information of X2 by setting to a random input. The model architecture and other settings are the same. By comparing the test performance in the two settings, show that model can be trained faster with X2, but it does not hold compositionality. We run experiments for 5 times, and plot the mean and variance at each training step.
5.1 IMAGE CLASSIHICATION
We use MNIST dataset (LeCun et al. 1998 in this experiment. The dataset contains pairs of input image and output label. An image is gray scale with fixed size, and label is in the set of ten possible values f0, 1, ......9),, 9). We two original samples (X1, Y1), (X2, Y2) to make sample (X, Y). X is the horizontal concatenation of X, and X2, and Y,. Note that generated sample does not directly use the label of the second sample Yz.
.1....99

---

Under review as a conference paper at ICLR 2021
jump
JUMP
walk before run left
WALK LTURN RUN
look left twice and run opposite right
LTURN LOOK LTURN LOOK RTURN RTURN RUN JUMP JUMP WALK
jump twice before walk
turn right after jump twice jump left twice after jump right
JUMP JUMP RTURN
RTURN JUMP LTURN JUMP LTURN JUMP
Table 1: SCAN input commands (left) and output action sequences (right) for Jump task. Upper section for training. and lower section for testing. In training, "jump" only appears as a single command. In test, it appears with other words.
We have two different settings in the experiment. In the first setting, we have the following data distribution. In training, the data are generated from the original training dataset. The samples are chosen uniformly random in the corresponding conditions. Y1 is chosen from all possible labels, and X1 with the label is chosen. Y2 is chosen from {Y, + 1} (we use modular for labels), and X2 with the label is chosen. In test, the data are generated from the original test dataset. Y1, X1 are chosen in the same way as in training, but Y2 is chosen from the other eight classes + +3...... Y...,,+9)) +9), and then X2 with the label is chosen. This means, in training, X2 contains part of information for Y. and X1 contain all information for Y. This is because Y2 is Y with half chance, and Y1 is always Y. We hope the model trained make Y not dependent on X2.
The second setting has the same test distribution as the first setting, but the training distributions are different. training of the second setting, Y2 chosen from all possible labels, so that X₂ does not have information for Y.
For both the first and second settings, we use a standard convolutional neural network model with three convolution layers and two fully-connected layers. The details of model design and optimization can be found in Appendix A
The results are shown in Figure 3a The training accuracy improves faster in the first setting than in the second one, indicating that X2 helps to train the model quickly. y. In the first setting, the gap training and test accuracy is significantly larger than that in the second setting, meaning the model does not learn compositionality in the first setting. Therefore, this experiment shows that the redundant information Xº is used to help training model quickly, but the model does not learn compositionality.
5.2 LANGUAGE LEARNING
We also run an experiment of instruction language learning with SCAN dataset (Lake & Baroni 2018). We focus on Jump task, the most difficult task in the dataset. The input is command instruction, and the output is corresponding action sequence. The training data include a one-word command "jump", but other training data do not contain the word. In test data, the word "jump" appears in multiple-words sentence with other words. Please see Table for examples.
In this task, syntax and semantics are two entangled components, and it requires compositional generalization to new combinations. Syntax is the way the actions are organized, and semantic is the mapping from word to action. We also design two settings in this experiment. In the first setting, we use the original training and test data, which are from different distributions. In the second setting, we remove the dependency of input semantics to output syntax by using action words uniformly at random, but still keep the correspondence between input words and output actions.
We use a standard sequence-lo-sequeece model with LSTM and attention. More details can be found in Appendix B Following previous works on SCAN dataset, we use sentence accuracy as the evaluation metric. The results are shown in Figure 3b We can observe that the training accuracy increases faster during the early training (steps 10-25) in the first setting than in the second setting. Also, the gap of training and test accuracy is significantly larger in the first setting than in the second setting, so the model does not learn compositionality in the first setting.
7

---

Under review as a conference paper at ICLR 2021
0.5
0.5
0
-0.5
-0.5
-0.5
0
-0.5
0.5
(a) Training
(b) Test
Figure 4: Data distribution for binary classification problem for Y1 output. Horizontal axis X1 and vertical axis is X2. Blue circle points are positive samples (Y₁ 1). Orange triangle points are negative samples (Yi = 0).
DISCUSSION
We use simple case to visualize the process for better understanding. We consider two random variables Y1, Y2 E {0, 1). In training, their joint distribution uniform on combinations (Y₁ Y2) E {(0, 0), (0, 1), (1, 0)}, and zero on (1, 1). In test, (Y₁, Y2) (1, We uniform noises with
range of 1, by subtracting them from the values (Figure
x Y1 U[ 1]
X2 U[0
We study prediction problem with two inputs X1, X2 and one output Yi. This problem has property that X₁ contains entire information of Y1. but X₂ only contains part of information of Y1- Y1 can be predicted from X1 alone, and X2 is redundant for Y1. We want to train a model f with parameters f has X1, X2 as input and ý as output: y = f
This problem requires compositional generalization, and the model needs to have compositionality. The model has three fully-connected hidden layers with ReLU activations, and each hidden layer has eight nodes. More details can be found in Appendix C
2
4
16
32
1024
Figure 5: Change decision boundary for each training step in a binary classification task. In the first training step, X₂ (vertical) is helpful for training (step 0), that the model is updated cover a part of upper right region as negative (step 1). In the following steps, the loss signals do not completely remove the negative cover this region, so that the influence remains in the trained model.
Figure ( shows the decision boundary for each training step. We see that the initialized parameters at step 0 output wrong predictions for samples in the upper left area, that the samples in this area useful to reduce loss, and they push the updated boundary in step to the middle of upper right area. In the following steps. the loss is low and do not change much, so that the boundary remains stable. Therefore, the trained model does not have good compositionality. Note that there can be different solutions for this problem. We use different random seeds, and show that the trained model do not have compositionality (6)
This visualization shows an example of process for how the gradient descent makes the model to be non-compositional.
7 CONCLUSIONS
In this paper, we investigate why standard neural network training seldom achieves compositional generalization by studying the relation hetween compositionality learning and gradient descent during
8

---

Under review as a conference paper at ICLR 2021
(a)
(b)
(c)
(d)
Figure 6: Decision boundaries after 1024 training steps with different random seeds.
training. We find that the optimization process poses a bias towards non-compositional solutions, and this is caused by gradient descent. It tends use possible and redundant information from imput. so that it violates conditional independence property of compositionality. Based on this study, we suggest that if only model structure design is considered in compositionality learning. is hard to achieve good compositionality. We hope this finding provides new understanding of compositional generalization mechanisms and helps to improve machine learning algorithms for higher level of artificial intelligence.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, lan Goodfellow, Andrew Harp, Geoffrey Irving. Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fermanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg. Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. URL http:: /wwwwwwwww.///////////// www.seensooffooooo org/ Software available from tensorflow.org.
Olah,
Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. In IEEE Conference on Computer Vision and Puttern Recognition (CVPR), 2016.
Dzmitry Bahdanau, Shikhar Murty, Michael Noukhovitch, Thien Huu Nguyen, Harm de Vries, and Aaron Courville. Systematic generalization: What required and can it be learned? In International Conference on Learning Representations, 2019, URL https: bettps://openreviee
net Pust/Eosee Eorum 2id HkezXnA9YX
Anas Barakat and Pascal Bianchi. Convergence analysis of a momentum algorithm with adaptive step size for convex optimization. arXiv preprint wrXiv:/911.07590/ 2019.
Yoshua Bengio. The consciousness prior. arXiv preprint arXiv: arXiv:1709.0000 170900866, 2017.
Leon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223- 311, 2018.
Paco Calvo and John Symons. The Architecture of Cognition: Rethinking Fodor and Pylyshyn's Systematicity Challenge. MIT Press, 2014.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. arXiv preprint arXiv: (ttp:://880044444 2018.
Noam Chomsky, Syntactic structures. Walter de Gruyter, 1957.
Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
Soham De, Anirbit Mukherjee, and Enayat Ullah. Convergence guarantees for rmsprop and adam in non-convex optimization and empirical comparison nesterov acceleration. arXiv preprint arXiv 2018.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. JMLR, 12:2121-2152 2011.
Jerry A Fodor and Ernest Lepore. The compositionality papers. Oxford University Press, 2002.
Jerry A Fodor and Zenon W Pylyshyn. Connectionism and cognitive architecture: A critical analysis. Cognition, 28(1-2):3-71, 1988.
Anirudh Goyal, Alex Lamb, Jordan Hoffmann, Shagun Sodhani, Sergey Levine, Yoshua Bengio, and Bernhard Schölkopf. Recurrent independent mechanisms. arXiv preprint arXiv:/909. 10893v2,, 2019.
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. 1rXiv:1410.5401, 2014.
arXiv preprint
K. He, X. Zhang, Ren, and J. Sun. Deep residual learning for image recognition. In CVPR, 2016.
Mikael Henaff, Jason Weston, Arthur Szlam, Antoine Bordes, and Yann LeCun. Tracking the world state with recurrent entity networks. arXiv preprint 16Xiv:16/2.03366 2016.
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. 3-vae: Learning basic visual concepts with con- strained variational framework. In International Conference on Learning Representations (ICLR), 2017.
10

---

Under review as a conference paper at ICLR 2021
Drew A Hudson and Christopher D Manning. Gqa: A new dataset for worldw visual reasoning and compositional question answering. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5700-6709, 2019.
Xisen Jin, Junyi Du, and Xiang Ren. Visually grounded continual learning of compositional semantics. arXiv preprint wrXiv:2005.007550 2020.
Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang. Mare van Zee, and Olivier Bousquet. Measuring compositional generalization: A comprehensive method on realistic data. In International Conferencee on Learning Representations, 2020. URL https:/ http::://ppeereeeeeee net http://oummmddyyycccae
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Louis Kirsch, Julius Kunze, and David Barber. Modular networks: Learning to decompose neural computation. In Advances in Neural Information Processing Systems, pp. 2408-2418, 2018.
A. Krizhevsky, I. Sutskever. and G.E. Hinton. Imagenet classification with deep convolutional neural networks. In NIPS, 2012.
Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to--sequeee recurrent networks. In International Conference on Machine Learning, pp. 2873-288222 2018.
Brenden M Lake. Compositional generalization through meta wwweenee----sequenee learning. In Advances in Neural Information Processing Systems, pp. 9788-9798, 2019.
Brenden M Lake, Tomer D Ullman, Joshua B Tenenbaum, and Samuel Gershman. Building machines that learn and think like people. Behavioral and Brain Sciences, 40, 2017.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (1:2)))-2222222 1998.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521 (21(333)) 2015.
Shuai Li, Wanqing Li, Chris Cook, Ce Zhu, and Yanbo Gao. Independently recurrent neural network (indrnn): Building a longer and deeper rnn. In the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5457-54665 2018.
Xiang Lisa Li and Jason Eisner. Specializing word embeddings (for parsing) by information bottleneck. In Proceedings of the 2019 Conference on Empirical Methods in Natural Lan- guage Processing and 9th International Joint Conference on Natural Language Processing, pp. 2744 2754, Hong Kong, November 2019, http://:://c. juu. wwwp////a//opppeeeeeeeeeeeeeeeee #li ei sner 2019
Best Paper Award.
Yuanpeng Li, Liang Zhao, Jianyu Wang, and Joel Hestness. Compositional generalization for primitive substitutions. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 4284 4293, 2019.
Yuanpeng Li, Liang Zhao, Kenneth Church, and Mohamed Elhoseiny, Compositional continual language learning, In International Conference on Learning Representations, 2020.
Francesco Locatello, Stefan Bauer, Mario Lucic, Gunnar Raetsch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem. Challenging common assumptions in the unsupervised learning of dis- entangled representations. In International Conference on Machine Learning, pp. 41 4124, 2019.
Zhi-Quan Luo. On the convergence of the lms algorithm with adaptive learning rate for linear feedforward networks. Neural Computation, 3(2):226-24 1991.
Gary F Marcus. Rethinking eliminative connectionism. Cognitive psychology, 37(3):243 1998.

---

Under review as a conference paper at ICLR 2021
Gary F Marcus. The algebraic mind: Integrating connectionism and cognitive science. MIT press, 2003.
Marvin Minsky, Society of mind. Simon and Schuster, 1986.
Richard Montague. Universal grammar. Theoria, 36(3):373-398, 1970.
Boris T. Polyak and Anatoli B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM Control Optim., (0(4):8388855 1992.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence adam and beyond. In ICLR, 2018.
Clemens Rosenbaum, Ignacio Cases, Matthew Riemer, and Tim Klinger. Routing networks and the challenges of modular and compositional computation. arXiv preprint arXiv: 127794444.777,, 2019.
David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by back-propagating errors. nature, (608))) 1986.
Jake Russin, Jason Jo, and Randall C O' D'Reilly. Compositional generalization in a deep seq2seq model by separating syntax and semantics. arXiv preprint UrXiv:1904009008 2019.
Adam Santoro, Ryan Faulkner, David Raposo, Jack W. Rae, Mike Chrzanowski, Theophane Weber, Daan Wierstra, Oriol Vinyals, Razvan Pascanu, and Timothy P. Lillicrap. Relational recurrent neural networks. arXiv preprint arXiv:1806.011 088222 2018.
Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. arXiv preprint arXiv: 006538,, 2017.
Daniel Smilkov and Shan Carter. Deep playground. online demo, 2016. URL https://githt:t Conn/tensorrllw//ppaaao
Alon Talmor, Oyvind Tafjord, Peter Clark, Yoav Goldberg, and Jonathan Berant. Teaching pre-trained models to systematically reason over implicit knowledge. arXiv preprint 1rXiv:2006006600 2020.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-mmppro:: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence nonconvex landscapes, from any initialization. arXiv preprint arXiv:1806.018: 2018.
Y. Wu and et al. Google's neural machine translation system: Bridging the gap between human and machine translation. In 16X.v:1609.0814 2016.
D. Yu and Deng. Automatic Speech Recognition. Springer, 2012.
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv:1212.5701 2012.
Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arxiv: 05671, 2018.
Fangyu Zou and Li Shen. On the convergence of adagrad with momentum for training deep neural networks. arXiv preprint arXiv: 1808. 03408, 2018
Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. A subgradientcient condition for convergences of adam and rmsprop. arXiv preprint
2018.
12

---

Under review as a conference paper at ICLR 2021
A IMAGE CLASSIFICATION
The model a convolutional neural network with the following layers. The input gray scale image with width 56 (two times of the original width) and height 28. The first hidden layer a two dimensional convolutional layer with kernel size x 3, depth 32, and ReLU activation. The second hidden layer is two dimensional max pooling layer with kernel size 2 x 2. The third hidden layer two dimensional convolutional layer with kernel size 3 x 3, depth 64 and ReLU activation. Then the representation flatten to a one vector. The fourth hidden layer is fully connected layer with 64 nodes and ReLU activation. The Fifth hidden layer is another fully connected layer with 64 nodes and ReI.U activation. The output layer fully connected layer with 10 nodes and linear activation.
We use mini-batch size of 64, and we run 200 steps in training. We use hinge loss, Adam opti- mizer (Kingma & Ba 2014) with learning rate of 0.001. We use TensorFlow (Abadi et al. 2015) for implementation.
B LANGUAGE LEARNING
We use standard sequence to sequence architecture. It has embedding layer, bidirectional LSTM encoder, and unidirectional LSTM with attention decoder. The first and last states of encoder are concatenated initial state of decoder. The embedding size is 32. The state size is 16 for encoder, and 64 for decoder. We run experiment on Jump task in SCAN dataset. The task contains 14,670 training and 7,706 test samples. In the first setting, we changed 'jump' to other action word and corresponding output symbol uniformly at random.
the original dataset. In the second setting,
We Adam for optimization, with cross entropy loss. We 2,000 training steps. Each step has mini-batch of 256 samples randomly and uniformly selected from training data with replacement. Initial learning rate is 0.01 and it exponentially decays by factor of 0.96 every 100 steps. We use TensorFlow for implementation.
C VISUALIZATION
The model is a fully-connected neural network, with two input nodes and two output nodes. It has three hidden layers with ReLU activations, and each hidden layer has eight nodes. We use mini-batch size of 10, and we run 1024 steps in training with learning rate 0.1. Please see the original work (Smilkov & Carter 2016) for more information.
13


Reviews:
[{"review_id": "sUWjKTjpSbQ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work analyzes the effect of gradient descent training on the compositionality of the learned model. It is shown that the gradient descent would use all the available information, even when it is redundant to learn the mapping from input to the output. It is then argued that the gradient descent training has the bias against compostionality despite the model architecture. Experiments are conducted on three simple benchmarks to demonstrate that when gradient descent trained model would use redundant information and not generalize compositionally. \n\nStrength:\n\n1. This work takes a new perspective to analyze the lack of compostionality in the neural network models and focuses on how gradient descent training violates the conditional independence of the inputs. \n\nWeakness:\n\n1.  The theorem doesn't seem to add too much new information since the conclusion that gradient descent leverages redundant information seems quite straightforward given it is taking the partial derivative w.r.t to each input. It would perhaps help to highlight the *new* insights from the proofs. \n\n2. It is not convincing that the gradient descent alone is the sufficient reason for violating conditional independence and causing lack of compositionality. As a simple example, given input with feature X1 and another redundant feature X2, if the model is linear with sparsity encouraging regularization such as L1, the model would probably learn to use only X1 even when trained with gradient descent. The experiments do show that the trained model is not able to neglect the redundant information, and the redundant information makes the training faster, but it doesn't support the claim that model architecture design couldn't help or achieve compostionality if trained by gradient descent. In fact, there are recent works trained by gradient descent that achieved perfect generalization on datasets like SCAN (Chen et al, 2020) by leveraging a better model design. \n\nChen, Xinyun, et al. \"Compositional Generalization via Neural-Symbolic Stack Machines.\" arXiv preprint arXiv:2008.06662 (2020).", "extra_scores": {}, "extra_text": {}}, {"review_id": "k4LmsCHVohi", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "review:\nThis paper addresses the effects of gradient descent methods onto compositionality and compositional generalization of models. The authors claim that the optimization process imposes the models to deviate compositionality, which is defined with conditional independence among random variables of input, predicted output and the ground-truth. Since compositionality is one of important features of human intelligence, it has been interested widely in the field of AI/ML such as vision, language, neuro-symbolic approaches, common sense reasoning, disentangled representation, and the emergence conditions of compositionality. As it has been not much focused on the relationship with optimizers, it is fresh and interesting. However, it is not easy to figure out the position of this paper from two reasons: (1) the definitions on compositionality in this paper are not so compatible with recent related works, which mostly consider certain structures in models [ICLR19, JAIR20] or representative problems such as visual reasoning [CVPR17] and Raven progressive matrices [PNAS17]. (2) The authors do not consider quantitative approaches such as compositionality [ICLR19] or compositional generalization [ICLR20]. \n\nIn this paper, the main claim is very broad argument. To verify this claim, the authors provide supports of both theoretical and experimental aspects. Theoretically, they try to show that reducing loss values in the optimization process induces utilizing other input variables including useful information based on mutual information. Experimentally, they show the gaps between several settings of accuracy curves with the MNIST dataset (vision) and the SCAN dataset (language). With both aspects, theoretical steps are vague and weak, and the experimental results are little persuasive and convincing.\nSome steps in theoretical derivation seem to be wrong.\nI recommend ‘trivial and wrong’ for this paper.\n\nPros:\nThey deal with the relationship among compositionality, compositional generalization and gradient descent. It is interesting and novel question as far as I know.\n\nConcerns:\n-\tIt is not clear the assumptions on models is covered in the main claim. Some arguments have readers guess the claim only on neural networks. Currently, it is not explicit. What if a model is naïve Bayes classifier which assumes conditional independence? Does it have compositional generalization? If the classifier is trained with gradient descent, the key argument of the paper has counterexamples, which becomes wrong.\n-\tTheorem 1 should show more clearly Markov chain structure among X, Y and Z. X -> Y -> Z (as written in Cover 1999 p.34)\n-\tWhat is the relationship between Y and X in Proposition 1? \n-\tThe proof in Proposition 2 seems not valid. Is the Markov chain among Y hat, X, and Y still valid? Without any constraints of X and Y, the equation in the middle of Proposition 2 seems not an identity (consider joint probability models with discrete values), and the derivation process is not trivial. The validity of this result is a factor that also affects subsequent verification.\n-\tThere is no quantitative analysis with measurable cases as mentioned above.\n\n\n[CVPR17] Johnson et al., CLEVR: A diagnostic dataset for compositional language and elementary visual reasoning, CVPR 2017.\n\n[PNAS17] Duncan et al., Complexity and compositionality in fluid intelligence, PNAS 2018.\n\n[ICLR19] Jacob Andreas, Measuring compositionality in representation learning, ICLR 2019.\n\n[ICLR20] Keysers et al., Measuring compositional generalization: a comprehensive method on realistic data, ICLR 2020.\n\n[JAIR20] Hupkes et al., Compositionality decomposed: how do neural networks generalise?], JAIR 2020.", "extra_scores": {}, "extra_text": {}}, {"review_id": "N-G-ZroBWO", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies if gradient descent will affect the compositionality generalization. It attempts to prove the results by information theory and demonstrated several experimental results. Unfortunately, I think the proof has mistakes, and the conclusion doesn't hold.\n\nThe major claim of the paper is that the gradient descent tries to use all available and redundant information from input. This is not true. Let's assume that we have two input $x_0$, and $x_1$, and the ground truth is the identity function $f(x_0, x_1)=(x_0,x_1)=(y_0,y_1)$. Now we assume the neural network be a simple linear transformation $f_{\\phi}(x_0,x_1)=(a_0x_0+a_1x_1,b_0x_0+b_1x_1)$, and we initialize it with the optimal solution $a_0=b_1=1,a_1=b_0=0$. The partial gradient is then $\\frac{\\partial y_0}{\\partial x_0}=\\frac{\\partial y_1}{\\partial x_1}=1; \\frac{\\partial y_1}{\\partial x_0}=\\frac{\\partial y_0}{\\partial x_1}=0$. The gradient descent will not use any redundant information. As for random initialization case, simple experiments show that the neural network can learn the identity mapping with enough data under the MSE loss (this is obvious as linear regression is a convex problem..). The neural network will have good compositional generalization.\n\nThe mistake might be in section 4.3. In the proof, the authors assume the output $\\hat{Y}_j$ for any $j\\neq i$ is fixed given that $X_j$ has information to reduce the loss. However. if $X_j$ correlates with $\\hat{Y}_j$, one can't fix $\\hat{Y}_j$ as it may change according to $X_j$. $X_j$ can reduce the loss $\\mathcal{L}(Y,\\hat{Y})$ by changing $\\hat{Y}_j$, then $\\frac{\\partial \\hat{Y}_i}{\\partial \\hat{X}_j}$ can be zero. \n\nSo, I think it's a clear rejection.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ah4YHsG6Pc", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: the paper investigates what neural networks learn when trained with gradient descent, in case parts of the inputs are only partially relevant to the output. The main claim is that GD is what prevents compositionality. In a set of synthetic experiments it is shown that indeed GD learns to use all information in the input, which results in poor generalization ood when only a subset of it was relevant.\n\nMy main concerns are the following:\n\n1) It seems to me that compositionality is not really the main aspect of the paper and it is not being tested.\nThe examples that the authors make earlier in the paper (e.g. shape and colour being entangled in the image), do not reflect the data used later in the experiments. For example, in the case of MNIST there seems to be only 1 factor that is relevant (the digit on the left side), and 1 factor that is spurious (the digit on the right). The test data does not require any compositionality to be solved, but only finding the invariance instead.\nSo my impression is that the paper in its current form is much more about finding invariances than learning compositionality. Nothing needs to be combined in order to solve the test set, the invariant mechanism is what’s needed.\n\n2) The paper is purely of “descriptive” nature, i.e. not “prescriptive” at all. While describing a novel problem can be already sufficiently interesting in general, I am under the impression that the general problem of learning invariances in neural nets as described in the paper has already been identified before [e.g., Heinze-Deml et al., 2018; Arjovsky et al., 2019].\nMost papers on the topic are now of a prescriptive nature, in the sense that they also investigate potential solutions to the problem.\n\n\n\nMinor:\n- By the time Figure 1 is mentioned, the caption mentioned “entangled”, but it’s unclear what that means in this context (and as a consequence it’s hard to interpret the figure).\n\n- P6: “Y2 is chosen from {Y, Y + 1}” : do you mean $Y_i$ for both instead of $Y$? (And again later two lines below?)\n\n(Not affecting the score, but the paper should be carefully proof-read for English syntax before publication.)\n\nC. Heinze-Deml, J. Peters, and N. Meinshausen. Invariant causal prediction for nonlinear models. Journal of Causal Inference, 6(2), 2018.\n\nM. Arjovsky, L. Bottou, I. Gulrajani, and D. Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv:1907.02893, 2019.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear Authors,

Thank you very much for submitting this very interesting paper.

This work analyzes the effect of gradient descent training on the compositionality of the learned model. Their main argument is that GD tries to use the redundant information in the data and, as a result, it doesn't generalize well. The paper then tries to show that theoretically and empirically with some simple experiments.

There is a general consensus among all the reviewers that this paper is not suitable for publication at ICLR. The authors do not entirely address most of the concerns raised by the reviewers during the rebuttal. 

If the authors improve the clarity of the paper, making some of the propositions and theories more concrete and grounded in experiments as well, I would recommend them to resubmit this paper to a different venue since the premise of the paper is important and interesting.

Some of the reasons:

- The paper claims that the gradient descent can not ignore the redundant information without providing sufficient empirical results. Though the part that is not clear to me whether if it is a credit assignment or an optimization problem. I agree with R1 that it is not clear what type of new insights from the proofs.

- As R1 mentions, this paper's claim seems too strong and not supported by experiments.

- R2 finds part of the paper unclear and thinks that some of the paper's propositions and theories are either trivial or wrong. The rebuttal doesn't seem to be doing a good job in terms of addressing those concerns.

- R4 also is confused with the paper thinks that some of the theories are incorrect.



Decision: Reject