Adaptive Neural Compilation
This paper proposes an adaptive neural-compilation framework to address the problem of learning efficient programs. Traditional code optimisation strategies used in compilers are based on applying pre-specified set of transformations that make the code faster to execute without changing its semantics. In contrast, our work involves adapting programs to make them more efficient while considering correctness only on a target input distribution. Our approach is inspired by the recent works on differentiable representations of programs. We show that it is possible to compile programs written in a low-level language to a differentiable representation. We also show how programs in this representation can be optimised to make them efficient on a target input distribution. Experimental results demonstrate that our approach enables learning specifically-tuned algorithms for given data distributions with a high success rate.
The paper explores a scheme where a low-level program is compiled into a differentiable representation, and the result is used as a starting point for a learning process optimizing a program for run-time efficiency on a selected distribution of inputs with the correctness constraints also applied only on the same distribution of inputs.  In a number of cases a classical optimized program is recoverable from the differentiable representation found by the learning process, but not always. In some other cases the result of learning gives better performance than the optimal performance possible for a classical program (in those cases, obviously, a classical program is not recoverable from the continuous representation obtained).
Recently we have seen re-emergence of research into neural models of classical software. This line of research is now rapidly accelerating. For many of us, the single paper most associated with the starting point of this re-emergence was "Neural Turing Machines" by Graves et al., and the development was very rapid since then. It is important to explore various angles and viewpoints on this rapidly evolving research topic.  The research presented in the paper under review is of interest on its own, but for many readers the key value will be provided by a new interesting angle of view this paper provides into differentiable models of classical software. This is where the most value from this paper for NIPS readership would probably come from.  I liked the way the paper is written overall, and I benefited from reading it in its current form, but I found some aspects of it confusing and more difficult to the reader than they should be. Some of those confusing aspects are, unfortunately, close to the central part of technical presentation. I hope the authors will be able to improve the paper in those aspects, some of which I list below.  It is not immediately obvious what the convex combination of registers is (formula 1, line 130). The natural interpretation is that it is a convex combination of delta-function probability distributions (distributions on the set of registers where a single register is taken with probability 1). But one also wonders whether it might be a convex combination of the values of registers (resulting in real values, rather than integers, and then using extension of operations listed in Figure 1b onto reals). In any case, if it is a convex combination of delta-function distributions, the paper should say so explicitly. If it is more subtle than that, the need for explanation is even higher.  The formula 2, line 132 is just not interpretable for a reader, even after looking into the supplement. What those double indexes mean for "out" and for "arg" is just too difficult to guess correctly. A verbal explanation of what's going on in this formula is necessary.  The role of soft-write and softmax in all this is not well explained (the reader can guess some of it from looking at the supplement). I think a much crisper explanation of those central aspects I've listed so far is necessary, preferably in the paper itself, rather than in the supplement.  I am going to also list a few less significant aspects where improvement would be desirable.  The term "instruction register (IR)" is somewhat confusing. First the reader might think, is this register going to actually store the machine command? Then the reader eventually realizes that this register is used simply as "program counter (PC)" (acceptable alternatives for this term seem to be "instruction pointer (IP)", "instruction address register (IAR)", or "instruction counter (IC)"). But the wording in line 104-105 does not say that the controller simply uses the "instruction register" to fetch the command from memory using the value of that counter and then parses the resulting command (which is what seems to actually be going on). Instead a wording is more general, and says that the controller computes the components of the command in some unspecified way. So the authors might have meant something else in mind in addition to the straightforward classical schema which they did end up implementing, and "instruction register" terminology might be hinting at those alternatives. In any case, it took some labor to understand that this was used as straightforward program counter, a pointer into the memory tape from which the command is fetched.   In the differentiable version (Section 3.2) the authors seem to rely on the range of accessible interger values being the same as the size of the memory tape M. This range, which is the same as indices into M, should then be from 0 to M-1, line 97 nonwithstanding (because the paper relies on having 0, so indices for m's in line 97 should be adjusted for that). I understand that this is a convenient convention at the early stage of this research (one then can worry less about values of indices which don't point anywhere into the memory, etc), but is it really necessary? It does feel like a very artificial requirement.  There are some minor problems with Figure 2c. The matrix (iv) is missing one row. In the matrix (i) "DEC" is not where it should be according to the order of Figure 1b. Finally the columns look OK on screen, but when I print, the first columns of matrices (1) and (iii) are only half-width, and the last columns of those matrices are one-and-a-half width.  Reference [7] is missing the last name of the second author, Jimmy Ba. Instead, the first word of the paper title, "Adam", has migrated to the position of the second author's last name.  Finally, "efficient program learning" on line 2 is quite ambiguous. The first interpretation which jumps into reader's mind is "efficient process of program learning". Only then one realizes that the authors has meant "learning the efficient programs" instead.   I hope this would help to improve the text.