Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: This paper presents a framework, dubbed algorithmic alignment, based on PAC learning and sample complexity, with the aim to explain generalization on reasoning tasks for different neural architectures. The framework roughly states that in order for the model to be able to learn and successfully generalize on a reasoning task, it needs to be able to easily learn (to approximate) steps of the reasoning tasks. The authors use this framework to propose an increasingly difficult set of tasks, designed to showcase the type of models that would be fit or unfit to solve them. The resulting experiments corroborate the theory, showing the limits of MLPs, Deep Sets, and consequently Graph Neural Networks. The final claim that an NP-hard task needs an enumerative architecture, and then experimental validation of that claim is nice and fits into the theory.
The added benefit of the paper is that the authors show as a side-effect that visual question answering and intuitive physics

Overall, the paper presents a meaningful contribution to the theory of learning, formalizing the means of quantifying the capabilities of architectures to solve tasks of certain complexity. The paper, though dense, is well well written, and carries an interesting conclusion that better algorithmic alignment brings the sample complexity down, i.e. models with better algorithmic alignment to the task (function they want to approximate) should generalize better.
The formalization presented in the paper, though remarkably intuitive, might be difficult to practically use for more elaborate models and it is not clear whether it can be numerically computed. The paper (i.e. the reader) would certainly benefit from more examples of algorithmic alignment comparison of different models, such as one done in Corollary 3.7.

Question:
- difference to Kolmogorov complexity is that any algorithmic alignment that yields decent sample complexity is good enough - how do you define decent?
- You state: “in Section 4, we will show that we can usually derive a near-optimal alignment by avoiding as many “for loops” in algorithm steps as possible.” yet I did not see that there. Was that effectively shown in Corollary 3.7?

Slightly related work: On the Turing Completeness of Modern Neural Network Architectures
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: This work seeks theoretical and empirical proof of the reasoning capacity of neural networks. The authors build on a body of research that demonstrates the usefulness of different neural network architectures for different reasoning problems. For example, Deep Sets have been proposed to answer questions about sets (e.g., a summary statistic), and GNNs about graph related problems, such as shortest path.

I anticipate that readers would be very satisfied with the intuition behind the main result: neural networks that “align” with known algorithmic solutions are better able to learn the solutions. Many architectures have been proposed over the years, often with a high-level justification for the architecture’s form. For example, Relation Networks noted the difficulty with learning n^2 relations using an MLP, which is an observation reflected in this work’s explanation of the difficulty with learning a for loop. 

Provided here is a justification for these high-level design decisions. The authors provide some theory and experimental results to demonstrate their proposed notion of alignment, and show that NNs that align with known algorithmic solution do well, while those that do not align do not do well. In particular, I appreciate both the positive and negative evidence, since demonstrating lack of alignment (and poor performance) is a necessary condition to show alongside alignment (and good performance).

I’d like to caution the authors regarding their main conclusion, which is stated a few times in the paper:

“This perspective suggests that whether a neural network can learn a reasoning task depends on whether there exists an algorithmic solution that the network aligns with”.

I think this logic is not precisely correct, and I would modify this to:

“If the structure of a neural network aligns with a known algorithmic solution, then it can more easily learn a reasoning task than a neural network does not align”. 

This is a subtle but important difference. In particular, the original logic does not capture situations where an algorithmic solution is not known, but a neural network can otherwise still learn a solution (consider object classification). I think even the corrected logic as I’ve spelled it out above might not be quite right either, since it does not consider situations where the algorithmic solution exists, but it obtuse. Would a neural network easily learn such a task? 

Overall I think the paper is clearly written, and the experiments are adequate. Unfortunately I am not well-versed in the theoretical literature on this topic, so my assessment of the proofs is limited, and I will need to defer to the other reviewers on these matters. My surface level assessment of them is that the logic seems generally sound, but I cannot make any strong statements placing them in the context of previous work, nor can I properly evaluate the nuances. Nonetheless, as a whole, I think this is a strong contribution and a nicely put together piece of work.

review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: The paper proposes a measure of classes of algorithmic alignment that measure how "close" neural networks are to known algorithms, e.g. dynamic programming (DP). The measure is based on the number of samples needed such that the expected generalization error is less than epsilon with 1-delta probability, where epsilon and delta are free parameters.

The paper proves the link between several classes of known algorithms and neural network architectures by showing how their sample complexity varies. For instance the paper shows that Graph Neural Network (GNN), can approximate any DP algorithm in a sample efficient manner, whereas MLP and deep sets (permutation invariant NN) can't. The paper empirically verifies their claims on 4 toy datasets, each representing an increasingly complex algorithm needed to solve the problem. 

I recommend this paper be accepted, since I think it's an important direction of research, and it formalizes a lot of intuition about neural network architectures.

It would be very interesting if the authors could actually compute the number of samples, M, for different NN architectures on the toy datasets, and show how it matches empirical findings. This could be a powerful tool if it could be made easy to use for the common practitioner.
review_title: Official Blind Review #3

Meta-review: This paper proposes a framework which qualifies how well given neural architectures can perform on reasoning tasks. From this, they show a number of interesting empirical results, including the ability of graph neural network architectures for learn dynamic programming.

This substantial theoretical and empirical study impressed the reviewers, who strongly lean towards acceptance. My view is that this is exactly the sort of work we should be show-casing at the conference, both in terms of focus, and of quality. I am happy to recommend this for acceptance.
Decision: Accept (Spotlight)