CRITICAL PERCOLATION AS A FRAMEWORK TO ANALYZE THE TRAINING OF DEEP NETWORKS
In this paper we approach two relevant deep learning topics: i) tackling of graph structured input data and ii) a better understanding and analysis of deep networks and related learning algorithms. With this in mind we focus on the topological classification of reachability in a particular subset of planar graphs (Mazes). Doing so, we are able to model the topology of data while staying in Euclidean space, thus allowing its processing with standard CNN architectures. We suggest a suitable architecture for this problem and show that it can express a perfect solution to the classification task. The shape of the cost function around this solution is also derived and, remarkably, does not depend on the size of the maze in the large maze limit. Responsible for this behavior are rare events in the dataset which strongly regulate the shape of the cost function near this global minimum. We further identify an obstacle to learning in the form of poorly performing local minima in which the network chooses to ignore some of the inputs. We further support our claims with training experiments and numerical analysis of the cost function on networks with up to 128 layers.
This paper thoroughly analyzes an algorithmic task (determining if two points in a maze are connected, which requires BFS to solve) by constructing an explicit ConvNet solution and analytically deriving properties of the loss surface around this analytical solution. They show that their analytical solution implements a form of BFS algorithm, characterize the probability of introducing "bugs" in the algorithm as the weights move away from the optimal solution, and how this influences the error surface for different depths. This analysis is conducted by drawing on results from the field of critical percolation in physics.
Overall, I think this is a good paper and its core contribution is definitely valuable: it provides a novel analysis of an algorithmic task which sheds light on how and when the network fails to learn the algorithm, and in particular the role which initialization plays. The analysis is very thorough and the methods described may find use in analyzing other tasks. In particular, this could be a first step towards better understanding the optimization landscape of memory-augmented neural networks (Memory Networks, Neural Turing Machines, etc) which try to learn reasoning tasks or algorithms. It is well-known that these are sensitive to initialization and often require running the optimizer with multiple random seeds and picking the best one. This work actually explains the role of initialization for learning BFS and how certain types of initialization lead to poor solutions. I am curious if a similar analysis could be applied to methods evaluated on the bAbI question-answering tasks (which can be represented as graphs, like the maze task) and possibly yield better initialization or optimization schemes that would remove the need for multiple random seeds.  
With that being said, there is some work that needs to be done to make the paper clearer. In particular, many parts are quite technical and may not be accessible to a broader machine learning audience. It would be good if the authors spent more time developing intuition (through visualization for example) and move some of the more technical proofs to the appendix. Specifically:
- I think Figure 3 in the appendix should be moved to the main text, to help understand the behavior of the analytical solution. 
- Top of page 5, when you describe the checkerboard BFS: please include a visualization somewhere, it could be in the Appendix.
- Section 6: there is lots of math here, but the main results don't obviously stand out. I would suggest highlighting equations 2 and 4 in some way (for example, proposition/lemma + proof), so that the casual reader can quickly see what the main results are. Interested readers can then work through the math if they want to. Also, some plots/visualizations of the loss surface given in Equations 4 and 5 would be very helpful. 
Also, although I found their work to be interesting after finishing the paper, I was initially confused by how the authors frame their work and where the paper was heading. They claim their contribution is in the analysis of loss surfaces (true) and neural nets applied to graph-structured inputs. This second part was confusing - although the maze can be viewed as a graph, many other works apply ConvNets to maze environments [1, 2, 3], and their work has little relation to other work on graph CNNs. Here the assumptions of locality and stationarity underlying CNNs are sensible and I don't think the first paragraph in Section 3 justifying the use of the CNN on the maze environment is necessary. However, I think it would make much more sense to mention how their work relates to other neural network architectures which learn algorithms (such as the Neural Turing Machine and variants) or reasoning tasks more generally (for example, memory-augmented networks applied to the bAbI tasks). 
There are lots of small typos, please fix them. Here are a few:
- "For L=16, batch size of 20, ...": not a complete sentence. 
- Right before 6.1.1: "when the these such" -> "when such"
- Top of page 8: "it also have a" -> "it also has a", "when encountering larger dataset" -> "...datasets"
-  First sentence of 6.2: "we turn to the discuss a second" -> "we turn to the discussion of a second"
- etc. 
Quality: High
Clarity: medium-low
Originality: high
Significance: medium-high
References:
[1] https://arxiv.org/pdf/1602.02867.pdf
[2] https://arxiv.org/pdf/1612.08810.pdf
[3] https://arxiv.org/pdf/1707.03497.pdf