Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper tries to integrate algorithms into end-to-end trainable neural networks.
Its main ingredient is `general approximation of discrete conditions` so that the conditions in control structures can be made differentiable. The relaxation is mostly done by perturbation from logistic distributions.

The authors evaluate the proposed method on four tasks.
1. Sorting concatenated MNIST images
2. Finding the shortest path
3. Reconstructing voxels from silhouettes
4. Computing Levenshtein distance
main_review: > This submission is out of my expertise. I suppose it came to me regarding weak supervision but I am not familiar with differentiable algorithms. I asked the AC to remove me from the reviewers but.. no response. Anyway, I will try to review this submission to my understanding.

originality:
- The authors propose continuous relaxations of different algorithmic concepts: comparators, conditional statements, loops, and indexing.
  - The proposed method estimates expectation by sampling-free closed form solution.
- I cannot consider originality due to my lack of expertise.

quality:
- Eq. 1-5 supports choosing logistic distributions for relaxation.
- Relaxed comparators are reasonable (Eq. 8-10).
- Relaxed indexing is somewhat vague because not every array has semantic relationship between neighboring elements (L227-229).
  - The latter case should be covered in the experiments or the reason for not covering should be described.

clarity:
- Most parts are clear to understand.

significance:
- Although the proposed method has some pitfalls (e.g., x<x evaluates to 50% and the relaxed indexing is meaningful only if the array is ordered), I suppose providing sampling-free closed form solution is an important contribution to the literature.

limitations_and_societal_impact: Corner cases where the proposed method cannot handle should be mentioned.

Societal impact: n/a
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: 
This paper proposes to integrate discrete algorithmic components into a deep network, or its learning objective, by continuous relaxations of the discrete operations. It also proposes to consider independently the relaxation of each operation and their combinations (what's referred to as "variable perturbations"), which avoids the combinatorial explosion of having to consider all possible paths (which would model higher-order interactions between variables, which are ignored here).

main_review: Although there are many attempts in the literature to propose discrete relaxations for deep networks, these are usually fairly ad-hoc and problem-specific. This proposal focuses on generic strategies for relaxation based on a single core element, the logistic distribution. This means that it is somewhat more formally satisfying than previous proposals. There's also a great focus on avoiding Monte Carlo sampling, which should be very impactful in practice, although this is not explored fully. Thus, I believe that this is a very well-crafted and novel solution to a very general problem.

The writing is of good quality, although there are instances that could be more clear, and especially a few where a formula would help make things more concrete. The related work section is relatively thorough and descriptive (except for one omission), and the experiments are well described and cover a wide array of areas, although each experiment in isolation is a bit small-scale. I did not identify any problems with the formulation, which was easy enough to follow.

In the related work, one glaring omission (unless I missed it) is the probabilistic programming literature. They also focus on creating programming primitives that are end-to-end differentiable and propagate distributions, similarly to the propagation of the logistic distribution here. I would expect at least some mention of the core languages, e.g. Church and other works, and how they are distinguished from the present proposal.

The section that is the least polished is between lines 150 and 191 ("Complexity and Merging of Paths"). Many parts were hard to follow, although in the end they made sense. It seems that a diagram illustrating the branching, nesting and merging of paths, annotated with example probabilities or logistic function visualizations, would aid understanding -- the text should make these concepts as concrete as possible. The 2nd paragraph frames the issue as one of perturbing inputs vs perturbing intermediate variables, which is one aspect, but another side of it is modeling *dependencies* between variables vs considering them as independent (as in the example of "x < x" where x is sampled twice). The proposal is to model variables' distributions independently, rather than their joint distribution through a collection of path traces as is common in other works / Monte Carlo approaches. A parallel to independent models such as Naive Bayes is appropriate. I did not understand the argument in line 177 about optimizing an algorithm w.r.t. runtime leading to interpolations.

Similarly, the comparison of categorical probability distributions in lines 195-201 is also not well justified; it's also not clear where exactly it is used in experiments. Lines 217-222 would benefit from a formula to make the convolution and normalization process unambiguous; in general this description is too high level. The point about aliasing effects, for example, was not clear. Finally, the convolution with a logistic filter is presented as a major difference w.r.t. other interpolation strategies -- however, the mentioned strategies (bilinear and bicubic) also correspond to well-defined convolution filters (e.g. triangular for bilinear). This needs to be highlighted -- the similarities, not the differences. The main difference would be that the logistic filter has longer tails and has potentially infinite support, while the other two filters are compact, so will not propagate gradients for far away cells. All of this should be discussed more thoroughly.

Another part where words were used instead of a formula, creating unnecessary ambiguity, is in line 251; the description of "we use this variable as a loss function" is puzzling.

The proposal for the equality operator (Eq. 9), based on a probability ratio, jumps out as not following from the initial assumptions and comes across as a bit more heuristic. What is the justification for this ratio? This squared hyperbolic secant function is actually the logistic distribution's PDF, so there may be some support there if this is fleshed out.

However, the authors could simply compose the tools they already developed to express equality. Since a==b is equivalent to a<=b & a>=b and so to not(a<b)&not(a<b), the probability of equality under the logistic distribution would be simply sigma(b-a)*sigma(a-b). This should have a similar shape to Eq. 9, but does not invoke new assumptions; it just reuses existing machinery.

The experiments are adequate, well executed and have some variety; but at least one large-scale experiment would be appreciated to show that this strategy can cope with more realistic scenarios. For example, training a RNN (e.g. on a NLP task) with a stopping criterion would represent a simple application of the conditional branching, which is less complex than the tested algorithms, but at the same time it would showcase its integration with a much larger-scale model and dataset. Another missing aspect is timing -- by avoiding expanding all paths, the proposal should do better than MC-based alternatives; this should be demonstrated with a fair time comparison.

Some technical questions: In Eq. 7, how are infinite loops dealt with? The probability of looping could never vanish (e.g. for a constant condition). Have the authors considered automatically tuning beta, for example setting it such that the gradients have a minimum absolute magnitude?
limitations_and_societal_impact: 
No. The authors could mention cases where they expect their strategy to fail (such as some concrete examples where they expect high-order interactions between variables to play a large role). Since this proposal is fairly application-agnostic, societal impact does not seem to be a primary concern.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes an approach for continuous relaxations of algorithms that allows their integration into end-to-end trainable neural network architectures. It shows that the general approach can compete with SOTA continuous relaxations and could relaxes for complex algorithms, e.g., shortest-path algorithm or a renderer. Some experiments show the effectiveness.  
main_review: The paper is well-written. It includes the probabilistic interpretation in Section 3. The two experiments, i.e., shortest-path and rendering are complex, which may testify to the  scalability of the proposed method.
limitations_and_societal_impact: I have following comments.
1. Why the proposed method is inferior to Perturbed Opt? It is better to explain this in detail.
2. It is better to estimate the scalability of the proposed theoretically.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The continuous relaxation of certain elements of certain programming primitives have been used in deep learning to incorporate constraints or logic into architectures. Attention, for example, has been viewed as a key-value dictionary lookup operation.
This paper aims to formalise some of these operations in a more general framework.

The main aspect that is considered is the if-else construct in programming. Rewriting the if-else conditionals as an integral over the logistic, they arrive at the classic gating function we often use in deep learning (e.g. GRUs, LSTM). This is extended to while loops, which are repeated applications of the if-else conditional. This particular equation looks like an expectation over the stick-breaking process (https://en.wikipedia.org/wiki/Dirichlet_process#The_stick-breaking_process)

Similar relaxations are then proposed for the equals comparator, with interesting initial assumptions that lead to the use of sech. Relaxed indexing also accounts for cases where the indexing is ordinal.

main_review: Method and related work

The explanation of their approach to relaxation of these if-else constructs is clear. I am unsure if this has been done before, but I like the generalised framework their approach provides. 
However, I think this paper would go over better if it made connections to prior work, and how they are specific cases of the framework provided in this paper. This allows readers who are unfamiliar with the more abstract aspect of the work to ground it in something they may have encountered before, and be able to see it more clearly as a generalisation of something they already know.

An example would be the Neural Turing Machine, and the various gating systems could be reframed as if-else conditions. 

Some references of this nature:
If-else:
Graves, Alex, Greg Wayne, and Ivo Danihelka. "Neural turing machines."
Shen, Yikang, et al. "Ordered memory."

Stick-breaking while loop

- Yogatama, Dani, et al. "Memory architectures in recurrent neural network language models."
- Shen, Yikang, et al. "Neural language modeling by jointly learning syntax and lexicon." 
- Graves, Alex. "Adaptive computation time for recurrent neural networks."
- Joulin, Armand, and Tomas Mikolov. "Inferring algorithmic patterns with stack-augmented recurrent nets."

Indexing:
- Graves, Alex, Greg Wayne, and Ivo Danihelka. "Neural turing machines."
- Graves, Alex, et al. "A novel connectionist system for unconstrained handwriting recognition."
(attention system over image)

This work also has some connections to other work that deal with relaxation of known algorithms.
Another paper that creates a framework for relaxations of certain structure-based algorithms is:
- Mensch, Arthur, and Mathieu Blondel. "Differentiable dynamic programming for structured prediction and attention." 

Specifically for the Eisner algorithm:
- Corro, Caio, and Ivan Titov. "Differentiable perturb-and-parse: Semi-supervised parsing with a structured variational autoencoder."

Experiments

MNIST Sorting Very surprising that relaxed bubble sort works better than the sinkhorn based method.

Warcraft shortest-path: Do you un-relax the algorithm during test time? Using the cost computed with the relaxed approach might result in lower costs.

Might be interesting to check how well do the methods generalise to untrained input sizes (e.g. longer lengths for MNIST, larger maps for shortest-path, ...)

limitations_and_societal_impact: 
The authors have addressed one particular limitation of such relaxations, which is in combining separate branches.
review_title: null

Meta-review: In this paper, the authors propose an approach for smoothing algorithms. While existing works were typically specialised for specific tasks, this works attempts to be more general by smoothing low-level operations such as if-else branches, while loops, and array indexing. The authors successfully demonstrate their approach on four diverse algorithms : bubble sort, shortest path, rendering and levenshtein.

The paper received an average score of 6.25, which is slightly above acceptance and one of the reviewers is ready to back up the paper.

While the paper would benefit from more polishing, it is overall well written and we would therefore like to recommend acceptance, assuming that the the authors will comply to the following requests, to further improve the paper:

- While the authors did a pretty good with citing the relevant literature, one reviewer mentioned additional references on stick breaking processes and array indexing. It is important to add these references.

- The authors should discuss more the pros and cons of Monte-Carlo approaches vs. the proposed approach. Monte-Carlo approaches, such as the one of Berthet et al, can run the original program unmodified, which is a key benefit.

- Limitations: most importantly, the authors should add a section on limitations of the approach. Indeed, while the approach is general at first glance, it has restrictions. First, the authors should discuss computational cost in more depth. Because of the local averaging, structures like trees would take exponential time to evaluate since they need to be fully expanded. Second, it is not clear for what class of programs the proposed approach is gonna work. All implemented applications (bubble sort, shortest path, rendering and levenshtein) seem to essentially have a fixed computational graph. Algorithms like Dijkstra or Quick sort wouldn't work with the proposed approach because these algorithms have inherently boolean decision steps, and making these decisions probabilistic would break the algorithm. The authors should try to delineate what program characteristics are needed for the proposed approach to work. This will help people who want to use the proposed framework know the operations they can and can't do. Lastly, when a program includes smoothed while loops, it's not clear if the program is even guaranteed to halt. Some further clarifications are needed.
Decision: Accept (Poster)