text: The authors are motivated by two problems: Inputting non-Euclidean data (such as graphs) into deep CNNs, and analyzing optimization properties of deep networks. In particular, they look at the problem of maze testing, where, given a grid of black and white pixels, the goal is to answer whether there is a path from a designated starting point to an ending point. They choose to analyze mazes because they have many nice statistical properties from percolation theory. For one, the problem is solvable with breadth first search in O(L^2) time, for an L x L maze. They show that a CNN can essentially encode a BFS, so theoretically a CNN should be able to solve the problem. Their architecture is a deep feedforward network where each layer takes as input two images: one corresponding to the original maze (a skip connection), and the output of the previous layer. Layers alternate between convolutional and sigmoidal. The authors discuss how this architecture can solve the problem exactly. The pictorial explanation for how the CNN can mimic BFS is interesting but I got a little lost in the 3 cases on page 4. For example, what is r? And what is the relation of the black/white and orange squares? I thought this could use a little more clarity. Though experiments, they show that there are two kinds of minima, depending on whether we allow negative initializations in the convolution kernels. When positive initializations are enforced, the network can more or less mimic the BFS behavior, but never when initializations can be negative. They offer a rigorous analysis into the behavior of optimization in each of these cases, concluding that there is an essential singularity in the cost function around the exact solution, yet learning succumbs to poor optima due to poor initial predictions in training. I thought this was an impressive paper that looked at theoretical properties of CNNs. The problem was very well-motivated, and the analysis was sharp and offered interesting insights into the problem of maze solving. What I thought was especially interesting is how their analysis can be extended to other graph problems; while their analysis was specific to the problem of maze solving, they offer an approach -- e.g. that of finding "bugs" when dealing with graph objects -- that can extend to other problems. I would be excited to see similar analysis of other toy problems involving graphs. One complaint I had was inconsistent clarity: while a lot was well-motivated and straightforward to understand, I got lost in some of the details (as an example, the figure on page 4 did not initially make much sense to me). Also, in the experiments, the authors mention multiple attempt with the same settings -- are these experiments differentiated only by their initialization? Finally, there were various typos throughout (one example is "neglect minimua" on page 2 should be "neglect minima"). Pros: Rigorous analysis, well motivated problem, generalizable results to deep learning theory Cons: Clarity