Learning with Algorithmic Supervision via Continuous Relaxations
Authors: Felix Petersen
Christian Borgelt
Hilde Kuehne
Oliver Deussen
Venue: NeurIPS 2021 Poster (2021)
Keywords: differentiable algorithms
algorithmic supervision
continuous relaxation
weakly supervised
perturbed
smooth
sorting
differentiable rendering

Abstract: The integration of algorithmic components into neural architectures has gained increased attention recently, as it allows training neural networks with new forms of supervision such as ordering constraints or silhouettes instead of using ground truth labels. Many approaches in the field focus on the continuous relaxation of a specific task and show promising results in this context. But the focus on single tasks also limits the applicability of the proposed concepts to a narrow range of applications. In this work, we build on those ideas to propose an approach that allows to integrate algorithms into end-to-end trainable neural network architectures based on a general approximation of discrete conditions. To this end, we relax these conditions in control structures such as conditional statements, loops, and indexing, so that resulting algorithms are smoothly differentiable. To obtain meaningful gradients, each relevant variable is perturbed via logistic distributions and the expectation value under this perturbation is approximated. We evaluate the proposed continuous relaxation model on four challenging tasks and show that it can keep up with relaxations specifically designed for each individual task.

Learning with Algorithmic Supervision via Continuous Relaxations
Felix Petersen
Christian Borgelt University of Salzburg christian@borgell net
University of Konstanz felix. pew.ix..ttersenuui...
Hilde Kuehne
Oliver Deussen University of Konstanz oliver siiver.deussen@ui kn
University of Frankfurt
MIT-IBM Watson AI Lab
kuehne@un cattnee@ni-ffratii wfaniifurrauuuuu....o
Abstract
The integration of algorithmic components into neural architectures has gained increased attention recently, as it allows training neural networks with new forms supervision such as ordering constraints silhouettes instead of using ground truth labels. Many approaches in the field focus on the continuous relaxation of a specific task and show promising results in this context. But the focus single tasks also limits the applicability of the proposed concepts to narrow range of applications. In this work, build those ideas to propose approach that allows to integrate algorithms into end-to-end trainable neural network architectures based on a general approximation of discrete conditions. To this end, relax these conditions in control structures such as conditional statements, loops, and indexing, so that resulting algorithms are smoothly differentiable. To obtain meaningful gradients, each relevant variable is perturbed via logistic distributions and the expectation value under this perturbation approximated. We evaluate the proposed continuous relaxation model on four challenging tasks and show that it can keep up with relaxations specifically designed for each individual task.
Introduction
Artificial Neural Networks have shown their ability to solve various problems, ranging from classical tasks in computer science such as machine translation [1] and object detection [2] to many other topics in science such as, e.g., protein folding [3. Simultaneously. classical algorithms exist, which typically solve predefined tasks based a given input and predefined control structure such as, e.g., sorting, shortest-patl computation and many more. Recently, research has started to combine both elements by integrating algorithmic concepts into neural network architectures. Those approaches allow training neural networks with alternative supervision strategies, such as learning 3D representations via differentiable renderer [4), (5) or training neural networks with ordering information (6), (7). We unify these alternative supervision strategies, which integrate algorithms into the training objective, as algorithmic supervision:
Definition 1 (Algorithmic Supervision). In algorithmiic supervision, algorithm is applied to the predictions of a model and the outputs of the algorithm are supervised. In contrast, in direct supervision, the predictions of a model are directly supervised. This is illustrated in Figure
In general, to allow for end-to-ent training of neural architectures with integrated algorithms, the challenge is estimate the gradients of respective algorithm, e.g., by differentiable approximation.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

meaningful
Input
Model
Output
Input
Model
Algorithm
Output
embedding
(supervised)
(supervised)
Figure I: Direct supervision (on the left) in comparison to algorithmic supervision (on the right),
Here, most solutions are tailored to specific problems like, e.g., differentiable sorting rendering.
But also more general frameworks have recently been proposed, which estimate gradients for combi- natorial optimizers. Examples for such approaches are the differentiation of black box combinatorial solvers as proposed by Vlastelica et al. [8] and the differentiation of optimizers by stochastically perturbing their input proposed by Berthet et al. (9]. Both approaches focus the problem that is necessary to estimate the gradients of an algorithm to allow for an end-to-end training of neural architectures including it. To address this issue, Vlastelica et al. (8) estimate the gradients of an optimizer by one-step linearization method that takes the gradients with respect to the optimizer's output into account, which allows to integrate any off-the-shelf combinatorial optimizer. Berthet et al. [ estimate the gradients by perturbing the input to a discrete solver by random noise.
In this context, we propose approach for making algorithms differentiable and estimating their gradients. Specifically, we propose continuous relaxations of different algorithmic concepts such comparators, conditional statements, bounded and unbounded loops, and indexing. For this, perturb those variables in a discrete algorithm by logistic distributions, for which we want to compute gradient. This allows us estimate the expected value of algorithm's 's output sampling-free and in closed form, e.g., compared to methods approximating the distributions via Monte- Carlo sampling methods (e.g.. (9). To keep the computation feasible, we approximate the expectation value by merging computation paths after each conditional block in sequences of conditional blocks. For nested conditional blocks, we compute the exact expectation value without merging conditional cases. This trade-off allows merging paths in regular intervals, and thus alleviates the need to keep track of all possible path combinations. As we model perturbations of variables when they accessed, all distributions are independent, which contrasts the case of modeling input perturbations, where all computation paths would have to be handled separately.
To demonstrate the practical aspects, we apply the proposed approach in the context of four tasks, that make use of algorithmic supervision to train neural network, namely sorting supervision [6].
77. (10], shortest-path supervision [8] [9, silhouette supervision (differentiable rendering) [4].
[). [ and finally Levenshtein distance supervision. While the first three setups are based on
existing benchmarks in the field, we introduce the fourth experiment to show the application of this idea to new algorithmic task in the field of differentiable dynamic programming. In the latter, the Levenshtein distance between two concatenated character sequences from the EMNIST data set [12] is supervised while the individual letters remain unsupervised. We show that the proposed system is able to outperform current state-of-the-e methods on sorting supervision, while it performs comparable on shortest path supervision and silhouette supervision.
2 Related Work
We cover the field of training networks with algorithmic supervision. While some of these works
cover single algorithmic concepts, e.g., sorting (6. (7). [13] or rendering ( (5), [14). others have
covered wider areas such as dynamic programming [5]. (16) or gradient estimation for general
optimizers (8). (9), (17). (8]. Paulus et al. (19] employ the Gumbel-Softmax (20) distribution to
estimate gradients for concepts such as subset selection. Xie et al. [2] and Blondel et al. [13 employ
differentiable sorting methods for top-k classification. Cuturi et al. 22 and Blondel et al. 23 present
approaches for differentiable dynamic time warping. In machine translation, Bahdanau et al. [24)
investigate soft alignments, while Collobert et al. [25] present a fully differentiable beam sorting algorithm. In speech recognition, Bahdanau et al. [26] propose differentiable surrogate task losses for sequence prediction tasks. Shen al. (27) propose a differentiable neural parsing networks using the stick breaking process. Dasgupta et al. (28) model box parameters with Gumbel distributions to obtain soft differentiable box embeddings.
In the following, we focus on those works that provide relaxations for tasks considered in this work. We close the overview with review of some early works smooth program interpretation.

---

Sorting Supervision The task of training neural networks with sorting supervision has been first proposed by Grover al. [6]. In this case, a set four-digit numbers based on concatenated MNIST digits [29] is given, and the task is to find an order- prder-preserving mapping from the images to scalars. Here, a CNN should predict a scalar for each of four-digit numbers such that their order preserved among the predicted scalars. For training, only sorting supervision in the form of the ground truth order of input images is given, while their absolute values remain unsupervised. Grover et al. [6] address this task by relaxing the permutation matrices to double stochastic matrices. Cuturi et al. [ pick up this on benchmark and propose a differentiable proxy by approximating the sorting problem with regularizing optimal transport algorithm.
Silhouette Supervision A line of work in computer vision is differentiable renderers for 3D- unsupervised 30-rrcconttruction. Here, recent approaches have proposed differentiable renderers for 3D mesh reconstruction with only 2D silhouette supervision (4. [5] on 13 classes of the ShapeNet data set (30]. Kato et al. (5) propose renderer where surrogate gradients of rasterization are approximated to perform 3D mesh reconstruction via silhouette supervision as well as 3D style transfer. Liu et al. [4] propose a differentiable renderer without surrogate gradients by using differentiable aggregating process and apply it to 3D mesh reconstruction as well as pose/ shape optimization.
Shortest-Path Supervision Two works, proposed by Vlastelica et al. (8] and Berthet et al. [9] presented methods for estimating gradients for off-the-shelf optimizers. In this context, Vlastelica el al. [8] proposed an experiment of shortest-path supervision, where an image of terrain is given with different costs for each type of terrain, and the task is to predict the shortest path from the tep-left to the opposite corner. Integrating shortest-path algorithm into neural architecture lets the neural network produce a cost embedding of the terrain which the shortest- -aats algorithm uses for predicting the shortest path. Vlastelica et al. [8] tackle this task by finding linearization of the Dijkstra algorithm (31) which they can differentiate. Berthet er al. (9] take up this problem and produce gradient estimates for the Dijkstra algorithm by stochastically perturbing the inputs to the shortest-path optimization problem.
Smooth Interpretation In another line of work, in the field of computer-aided verification, Chaud- huri et al. [32. (3) propose program smoothing method based on randomly perturbing the inputs of program by Gaussian distribution. Here, an initial Gaussian perturbation is propagated through program transformations, and a final distribution over perturbed outputs is approximated via a mixture of Gaussians. The smooth function is then optimized using the gradient-free Nelder-Mead optimiza- tion method. The main differences to our method are that we perturb all relevant variables (and not the inputs) with logistic distributions and use this for gradient based optimization.
Method
To continuously relax algorithms and, thus, make them differentiable, we relax all values with respect to which we want to differentiate into logistic distributions. We choose the logistic distribution as provides two distinctive properties that make it especially suited for the task at hand: (1) logistic distributions have heavier tails than normal distribution, which allows for larger probability mass and thus larger gradients when two compared values are further away from each other. (2) the cumulative density function (CDF) of the logistic distribution is the logistic sigmoid function, which can be computed analytically, and its gradient is easily computable. This contrasts the CDF of the normal distribution, which has no closed form and is commonly approximated via polynomial (34].
Specifically, we relax any value x, for which we want compute gradients, by perturbing it into logistic random variable ā ~ Logistic(r; 1/3), where 3 is the inverse temperature parameter such that for 3 + oc: 5 xr Based this, we can relax discrete conditional statement, e.g., based on the condition x < c with constant E R. as follows:
y if 5 < C else 2| = L
+ f fiog (1; 1/3) z dt
fio x1 1/3) y dt
(1)
Jc
Fiog (c; xx 1/B) y
+ (1 - Fiog (c; 1/3))
(2)
alc- x:)
+ (1-o x))
(3)
3

---

where o is the logistic (sigmoid) function (xx) 1/(1 + te- -==))) In this example, as increases, the result smoothly transitions from y to 2. Thus, the derivative of the result wrt. x defined as
a dr yy if i<c else 2| dr
(y a(e - z) + (1-o(c x)))
(4)
= (z y) alc - x) (1-0 - o(c-)))
(5)
Hence, the gradient descent method can influence the condition ( < c) to hold if the if case reduces the loss, or influence the condition to fail if the else case reduces the loss function.
In this example, y and may not only be scalar values but also results of algorithms parts of an algorithm themselves. This introduces a recursive formalism of relaxed program flow, where parts of an algorithm are combined via convex combination:
(f()) if a < else g(t)] =\t a(b -16-00 a) (()) - ol-o -ob--o(ba))))) a)) g(s)
(6)
where I and denote functions, algorithms, or sequences of statements that operate on the set of all variables s via call-by-value and return the set of all variables s. The result of this may either overwrite the set of all variables (s == (...) or be used in nested conditional statement.
After introducing if elee statements above, we extend the idea to loops, which extends the formal- ism of relaxed program flow to Turing-completeness. In fixed loops, i.e., loops with a predefined number of iterations, since there only a single computation path, no relaxation is necessary, and, thus, fixed loops can be handled by unrolling.
The more complex case is conditional unbounded loops, i..., While loops, which are executed as long as a condition holds. For that, let (si)seN be the sequence of all variables after applying i times the content of loop. That is, so for initial set of all variables s, and 8; f(s;-1), where f is the content of a loop, i.e., a function, an algorithm, or sequence of statements. Let a, b denote accessing variables of s, i.e., s[a], s(6], respectively. By recursively applying the rule for if fels statements, we obtain the following rule for unbounded loops:
while b do = [())]
Σ 2=0
(o(b aU)) (1 abbi+ a++1))
(a)
Here, (a) is the probability that the ith iteration is reached and (b) is the probability that there are no more than iterations. Together, (a) and (b) is the probability that there are exactly i iterations weighing the state of all variables after applying times f. which is 8,. Computationally. we evaluate the infinite series until the probability of execution (a) becomes numerically negligible or predefined maximum number of iterations has been reached. Again, the result may either overwrite the set of all variables (s : [...] or be used in a nested conditional statement.
Complexity and Merging of Paths To compute the exact expectation value of an algorithm under logistic perturbation of its variables, all computation paths would have to be evaluated separately to account for dependencies. However, this would result in an exponential complexity. Therefore, we compute the exact expectation value for nested conditional blocks, but for sequential conditional blocks we merge the computation paths at the end of each block. This allows for a linear complexity in the number of sequential conditional blocks and an exponential complexity only in the largest depth of nested conditional blocks. Note that the number of sequential conditional blocks is usually much larger than the depth of conditional blocks, e.g., hundreds or thousands of sequential blocks and a maximum depth of just 2 - 5 in our experiments. An example for a dependency is the expression la = (f()) if < else g(x)); b := (0 a else d²)]] which contains a dependence between the two sequential conditional blocks, which introduces the error in our approximation. In general, our formalism also supports modeling dependencies between sequential conditional blocks, however practically, it might become intractable for entire algorithms. Also, it is possible to consider relevant dependencies explicitly an algorithm relies on specific dependencies.
Perturbations of Variables vs. Perturbations of Inputs Note that modeling the perturbation of variables different from modeling the perturbation of the inputs. A condition, where the difference becomes clear, is, e.g., (ā < x). When modeling input perturbations, the condition would have strong implicit conditional dependency and evaluate to a 0% probability. However, in this work, we do not model perturbations of the inputs, but instead model perturbations of variables each time

---

p
P
b
-4
2
4
2
Figure 2: Left: Hard decision boundary (cyan) and probability under logistic perturbation (magenta). Right: Hard equality (cyan), relaxed equality (magenta), and relaxed inequality (light magenta).
they are accessed such that accessing a variable twice is independently identically distributed (iid). Therefore, (#t < 2) evaluates to 50% probability. To minimize the approximation error of the relaxation, only those variables should be relaxed for which a gradient is required.
3.1 Relaxed Comparators
So far, have only considered the comparator
follows by swapping the arguments:
P b = =bb
P
b = aaa b) >
(8)
Relaxed Equality For the equality operator we consider two distributions à ~ Logistic(a, 1/3) and b ~ Logistic(6, 1/8), which want to check for similarity / equality. Given value a, compute the likelihood that is sample from i rather than ä. If a is equally likely to be drawn from and b, and b are equal. If is unlikely be drawn from b, and are unequal. To compute whether it is equally likely for be drawn from à and b, we take the ratio between the probability that from b (fog(e (a; 1)3) and the probability that a is from (foo (a; a, 1/8)):
flog (a; 1/3) (ag a, 1/B) flog 6; b, 1/3)
flog (b; a, 1/5) sech? ( b
P a = b]
2/3
These relaxed comparators are displayed in Fig. To compute probabilities of conjunction (i.e., and) or of disjunction (i.e., or), we use the product probabilistic sum, respectively. This corresponds to an intersection union independent events. An alternative derivation for Eq. 9 is the normalized conjunction of (aa < b) and -(a b).
Relaxed Maximum To compare more than two elements and relax the arg max function, we use the multinomial logistic distribution, which is also known the softmax distribution.
N.8
P(i arg max X,)
(10)
E, ex,
To relax the max operation, we use the product of arg max / softmax and the respective vector.
Comparing Categorical Variables compare categorical probability distribution X [0, 1 with a categorical probability distribution Y. we consider two scenarios: Y E (0, 1)" i.c.. Y one-hot, we can use the inner product X and Y to obtain their joint probability. However, Y & {0. 1"", f i.e., Y is not one-hot, even if X = Y the inner product can not be 1, but probability of would be desirable if X product, which corresponds to the cosine similarity. An example for the application of comparing categorical probability distributions is shown in the Levenshtein distance experiments Section 4.4
Therefore, we (I22) normalize and before taking the inner
3.2 Relaxed Indexing
As vectors, arrays, and tensors are essential for algorithms and machine learning, we also formalize relaxed indexing. For this, we introduce real-valued indexing and categorical indexing.
Real-Valee Valued Indexing In relaxed algorithm, indices may be drawn from the set of real numbers as they may be a convex combination computations or real-valued input. This poses a challenge since it requires interpolating between multiple values. The direct approach would be grid sampling
5

---

with bilinear or bicubic interpolation to interpolate values. For example, Neural Turing Machines use lin- ear interpolation for real-valued indexing [35]. How- ever, in bilinear or bicubic interpolation, relationships exceeding the direct (or next) neighbors in the array are not modeled, and they also do not model logistic perturbations. Therefore, we index an n-dimensional tensor A with values i E IR" via logistic perturbation by applying convolution with logistic filter g and obtain the result as (g * A) (t). The convolution of a tensor A with logistic filter g (not to be confused with discrete-discres yields a function that is evaluated point i E IR".
Figure 3: Real-valued indexing: the gray- value represents the extent to which each value is used for indexing. Left: ID integer- valued hard indexing compared to real-valued indexiig. Right: 2D real-valued indexing.
convolution in neural networks)
We choose the logistic filter over bilinear and bicubic filters because we model logistic perturbation, and additionally because bilinear and bicubic filters only have compact support whereas the logistic filter provides infinite support. This allows modeling relationships beyond the next neighbors and is more flexible as the inverse temperature 3 can be tuned for the respective application. For stability, we normalize the coefficients used to interpolate the respective indexed values such that they sum up to one: instead of computing (g ()) Σj ز A), we compute Σj g (", g(j -() where j are all valid indices for the tensor A. To prevent optimization algorithms from exploiting aliasing effects, we divide the coefficients by their sum only in the forward pass, but ignore this during the backward pass (computation of the gradient). Real-valued indexing is displayed in Fig. 3 which compares it to hard indexiin.
Relaxed Categorical Indexing If a categorical probability distribution over indices is given, e.g.. computed by argmax or its relaxation max, categorical indexing can be used. Here, the marginal categorical distribution is used as weights for indexing tensor.
Note that valued indexing assumes that the indexed array follows a semantic order such as time series, an image, or the position in grid. If, in contrast, the array contains categorical information such as the nodes of graphs, values should be indexed with categorical indexing as their neighborhood is arbitrary.
3.3 Complexity and Runtime Considerations
In terms of runtime, one has note that runtime optimized algorithms (e.g., Dijkstra) usually do not improve the runtime for the relaxation, because for the proposed continuous relaxations all cases in an algorithm have to be executed. Thus, an additional condition to reduce the computational cost does not improve runtime because both (all) cases are executed. Instead, it becomes beneficial if an algorithm solves a problem in a rather fixed execution order. On the other hand, optimizing an algorithm with respect to runtime leads to interpolations between the fastest execution paths. This optimization cannot improve the gradients but rather degrades them as it is an additional approximation and produces gradients with respect to runtime heuristics. For example, when relaxing the Dijkstra shortest-path algorithm, there is an interpolation between different orders of visiting nodes, which the heuristic that makes Dijkstra fast. However, if we have to follow all paths anyway (to compute the relaxation), it can lead to a combinatorial explosion. In addition, by interpolating between those alternative orders, large amount of uncertainty is introduced, and the gradients will also depend on the orders of visiting nodes, both of which are undesirable. Further, algorithms with rather strict execution can be executed in parallel on GPUs such that they can be faster than runtime-optimized sequential algorithms on CPUs. Therefore, we prefer simple algorithms with a largely fixed execution structure and without runtime optimizations from both runtime and gradient quality perspective.
4 Experiments
We evaluate the proposed approach on various algorithmic supervision experiments, an overview of which is depicted in Fig. For each experiment, we first briefly describe the task and the respective input data as well as the relaxed algorithm that is used. To allow an application to various tasks, we need to find a suitable inverse temperature 3 for each algorithm. As a heuristic, we start with 8 = Vi where & is the number of occurrences of relaxed variables in the algorithm, which is balance between

---

CKS
Shoctoot
375
CNN
Pith
ONN
Surting Algotitla
Silhrrttt
Losuadadi
CNX
3D Mesh
Distano Alpectho
Algociitir
Figure 4: Overview of our algorithmic supervision experiments: Sorting Supervision (left), Shortest- Path Supervision (top), Silhouette Supervision (bottom), and Editing Distance Supervision (right).
a good approximation and sufficient relaxation for good gradient estimates. For each task, we tune this parameter on a validation set. Pseudo-code for all algorithms as well as additional information on the relaxation and the inverse temperature parameter can be found in the supplementary material. The implementation of this work including high-level PyTorch (36] library for automatic continuous relaxation of algorithms is openly available at github.com/Felix gighuulcom//liiss/eearrr//gggggo
4.1 Sorting Supervision
In the sorting supervision experiment, a set of four-digit numbers based on concatenated MNIST digits (29] is given, and the task is to find an order-pressee preserving mapping from the images to scalars. CNN learns to predict scalar for each of n four-digit numbers such that their order is preserved among the predicted scalars. For this, only sorting supervision in form of the ground truth order of
input images is given, while their absolute values remain unsupervised. This follows the protocol of
Grover et al. [6 and Cuturi et al. (7]. An example for a concatenated MNIST image is 8 7
Using our method, we relax the well established stable sorting algorithm Bubble sort [37], which works by iteratively going through a list and swapping any two adjacent elements if they are not in the correct order until there are no more swap operations one iteration. We include variable that keeps track of whether the input sequence is in the correct order by setting it to true if a swap operation occurs. Due to the relaxation, this variable is a floating-poni point number between 0 and corresponding to the probability that the predictions are sorted correctly (under perturbation of variables). We use this probability as the loss function. This variable equals the probability that no swap operation was necessary, and thus L that, the training objective becomes for the input sequence to be sorted and, thus, that the scores predicted by the neural network correspond to the supervised partial order. In fact, the number of swaps in bubble sort corresponds to the Kendall's t coefficient, which indicates to which degree sequence is sorted. Note that, e.g., QuickSort does not have this property as performs swaps even the sequence is already sorted.
[I (1 p) for probabilities of each potential swap p E P. By
We emphasize that the task of the trained neural network is not to sort sequence but instead to predict a score for each element such that the ordering / ranking corresponds to the supervised ordering / ranking. While the relaxed algorithm can sort the inputs correctly, at evaluation time, following the setup of [6] and (7) we use an argsort method to test whether the outputs produced by the neural network are accordance with the ground truth partial order. We use the same network architecture as [6) and (7). Here, we only optimize the inverse temperature for n 5, resulting in / = 8, and fix this for all other n. For training. we use the Adam optimizer [38 with a learning rate of 10-4 4 for between 1.5 10 and 1.5. 10t iterations.
We evaluate our method against state-of-the-art hand-crafted re- laxations of the sorting opera- tion using the same network ar- chitecture and evaluation met- rics as Grover et al. (6) and Cu- turi et al. [7]. As displayed in Tab. []] our general formula- tion outperforms state-of-the-art hand-crafted relaxations of the sorting operation for sorting su- pervision.
Table I: Results for the 4-digit MNIST sorting task, averaged over 10 runs. Baselines as reported by Cuturi et al. (7). Trained and evaluated on sets of n elements, the displayed metries are exact matches (and element-wise correct ranks).
Method
Ya 3
T
n1 7
Stoch. NeuralSort 6
0.920 (0.946) 0.790 (0.907)
0.636 (0.873)
Det. NeuralSort 6
0.919 (0.945)
0.777 (0.901)
0.610 (6.)
Optimal Transport
0.928 (0.950)
0.811 (0.917) 0.656 (0.882)
Relaxed Bubble Sort
0.944 (0.961)
0.842 (0.930)
0.707 (0.898)
7

---

Inpur
Hadden Costs
Shortest Path
Our (5:m):))
Berther et (em. (.)))
Durs -251
berthet at (am2)
Figure 5: (From left right.) Example input image of the Warcraft terrain data set with the hidden cost matrix and the resulting shortest path. Shortest paths relaxed with the proposed method for [1.5, 0.25], which correspond the perturbed paths by Berthet al. [9] with E {0.5, 2.0}.
4.2 Shortest-Path Supervision
For shortest-path supervision on 2D terrains, we follow the setup by Vlastelica et al. [8] and Berthet et al. [9] and use the data set of 10000 patches of Warcraft terrains of size 96 96 representing terrain grids of size 12 x 12. Given an image of terrain (e.g.. Fig. 5 first), the goal is to predict the shortest path (e.g., Fig. F (hird)) according to hidden cost matrix (e.g., Fig. {econdd) For this, 12 x 12 binary matrices of the shortest-pali are supervised, while the hidden cost matrix is used only to determine the shortest path. In their works, Vlastelica et al. (8) and Berthet et al. (9] show that integrating and differentiating shortest-palt algorithm can improve the results by allowing the neural network to predict a cost matrix from which the shortest path can be computed via the algorithm. This performs significantly better than ResNet baseline where the shortest paths have be predicted by the neural network alone (see Tab. 2
For this task, we relax the Bellman-Ford algo- rithm (39) with 8-neighborhood, node weights, and path reconstruction, details on which are given in the supplementary material. For the loss between the supervised shortest paths and the paths produced by the relaxed Bellman-Foon Ford algorithm, we use the E loss. To illustrate the shortest paths created by our method and to com- pare them to those created through the Perturbed Optimizers by Berthet et al. [9]. we display ex- amples of back traced shortest paths for two inverse temperatures in Fig. 5 (center to right).
Table 2: Results for the Wareraft shortest-path task using shortest-path supervision, averaged over 10 runs. Reported the ratio between the cost of the predicted path and the cost of the optimal shortest path.
exact matches (EM) well as
Method
EM
cost ratio
ResNet Baseline
g
40.2%
1.01530
Black-Box Loss
86.6%
1.00026
Perturbed Opt.
91.7%
1.00042
Relaxed Shortest-Pare Path
88,4%
1.00014
We use the same ResNet network architecture
as Vlastelica et al. (8) and Berthet et al. (9) and also train for 50 epochs with batch size of 70, We use an inverse temperature of 3 25.
As shown in Tab. [] our relaxation outperforms all baselines on the cost ratio of the predicted the optimal shortest path and achieves the second- -est result on the shortest path exact match accuracy after the perturbed optimizers [9].
4.3 Silhouette Supervision
Reconstructing 3D model from single 2D image is an important task in computer vision. Recent
works 4., (5) have employed differentiable renderers to train a 3I) reconstruction network by giving
feedback on whether the silhouettes of a reconstruction match the input image. Specifically, recent works have been benchmarked (4). (5), [IT] on data set of 13 object classes from ShapeNet [30] that have been rendered from 24 azimuths
resolution of 64 x 64 (5). For learning with silhouette supervision, a single image is processed by neural network, which returns a 3D mesh. The silhouette of this mesh is rendered from two view-poims by a differentiable renderer and the intersection- over-- union between the rendered and predicted meshes is used as training objective to update the neural network [4) 5]. For training, we also use the same neural network architecture as Kato et al. (5) as well as Liu et al. (4). Note that, while renderers can be able to render full RGB image, in these experiments, only the silhouette used for supervision of the 3D geometry reconstruction. Specifically, public implementations of 5 only use silhouette supervision.

---

Table 3: Single-view 3D reconstruction results using silhouette supervision. Reported is the 3D IoU.
Method
Airplane Bench Dresser
Car
Chair
Display
Lamp Speaker
Rille
Sola
Table
Phone
Vessel
Mean
With batch size of 64
Yan et al. []
(retrieaa)
0.5564
0,4875 0,5713 0.6519 0,3512
0.3958
0.2900
0,4600
0.5133 0.5314 0.3097 0.6696 0,4078 0,4766
Yan
(voxel)
0.5556
0.4924 0.6823 0.7123 0,4494 0.5395
0.4223
0.5868
0.5987 0.6221 0,4938 0,7504 0.5507 0.5736
Kato et al
(NMR)
0.6172
0.4998
0.7143 0.7095 0.4990
0.5831
0.4126
0.6536
0.6322 0.6735 0.4829 0.7177 0.56-15 0.6015
Liu al.
[SottRas)
0,6419
0.5080
0.7116
0.7697
0.5270
0.6156
0.4628
0.6654
0.6811
0.6878 0,4487 0.7895 0.5953 0.6234
With batch size of
Lin et al. [4] (SoftRas)
0.5741
0.3746
0.8373
0.6989
0.4220
0.5168
0.4001
0.0088
0.6026
0.5922 0.371 12 0.7464 0.5534 0.5455
Relaxed Sar. Three Tdges
0.5418
0.36657
0.6626 0.6546
0.3899
0.4105
0.6252
0.5639
0.3580 0.6609 0.5279 0.5256
Relaxed Sil. via Faclid. Dist
0.5399
0.3698
0.00003
0.6024
0.4044
0.5261
0.4247 0.6225 0.5723
0.5643
0.3829
0.7265 0.5180 0.5349
For this task, we relax two silhouette rendering algorithms. The algorithms rasterize 3D mesh as follows: For each pixel and for each triangle of the mesh, if a pixel lies inside triangle, the value of the pixel in the output image is set to 1. The condition of whether a pixel lies inside a triangle is checked in two alternative fashions: (1) by three nested if conditions that check on which side of each edge the pixel lies. (2) by checking whether the directed euclidean distance between a pixel and triangle is positive. Note that, by relaxing these algorithms using framework,
obtain differentiable renderers very close to Pix2Vex (40) for (1) and SoftRas (4) for (2). Examples of
relaxed silhouette renderings and example image from the data set are displayed in Fig. 6
As the simple silhouette renderer does not have any optimizations, such as discarding pixels that are far away from a triangle or triangles that are occluded by others, it is not very efficient. Thus, due to limited resources, we are only able to train with a maximum batch size of 2 while previous works used a batch size of 64. Therefore, we reproduce the recent best performing work by Liu et al. [4] on batch size of only 2 to allow for fair comparison. For directed Euclidean distance, use inverse temperature of / = 2 000; for three edges, B = 10 000.
Input Image
g 200
8 8=50
Figure 6: An input image from the data set (left). Silhouette of prediction rendered with directed Eu- clidean distance approach for two different inverse temperatures 3 {200, 50}.
We report the average as well as class-wise 3D IoU results in Tab. 3 Our relaxations outperform the retrieval baseline by Yan el al. (TT] even though we use a batch size of only In direct comparison to the SoftRas renderer at batch size of 2, our relaxations achieve the best accuracy for 5 out of 13 object classes. However, on average, our methods, although they do not outperform SoftRas, show a comparable performance with drop of only 1%. It is notable that the directed Euclidean distance approach performs better than the three edges approach. The three edges approach is faster by a factor of 3 because computing the directed Euclidean distance is more expensive than three nested if clauses (even in the relaxed case.)
4.4 Levenshtein Distance Supervision
In the Levenshtein distance supervision experiment, we supervise classifier for handwritten EMNIST letters [12] by supervising the editing distance between two handwritten strings of length 32 only. As editing distance, we use the Levenshtein distance LD which is defined as LD(a, b) LD |alj (a, 6):
i 0
i
j = 0
(D,
LD, - (a, +1
(11)
else.
min
I.D
+1
LD,-15-1(a,b)) + + (a: 17)
We relax the Levenshtein distance using its classic dynamic programming algorithm. An example Levenshtein distance matrix and its relaxation are displayed in Fig. 7

---

Table 4: EMNIST classification results with Levenshtein distance supervision averaged over 10 runs.
Method
AB
BC
CD
IL
0X
ACGT
DSXL
Top-1 acc.
.616
.651
.768
.701
.550
.893
.403
.48
Baseline
Fl-score
.811
.629
.759
.711
.674
.490
.890
.36
.84
Top-1 acc.
.671
.807
.816
.833
.847
.570
.960
.377
.487
Relaxed L.D
Fl-score
.666
.805
.815
.831
.845
.539
.960
.367
.404
For learning, pairs of strings of images of 32 handwritten characters a, b as well as the ground truth Levenshtein distance LD(y.: Yt) are given. We sample pairs of strings a, from an alphabet of 2 or 4 characters. For sampling the second string given the first one, we uni- formly choose between two and four insertion and deletion operations. Thus, the average edit- ing distance for strings, which use two different characters, is 4.25 and for four characters is 5. We process each letter, using a CNN, which returns categorical distribution over letters, which is then fed the algorithm. An example for a pair of strings based on {A, C. G, T) is
0.0
1.0
2.0
3.0
4.0
A
1
10
0.8
1.5
2.7
3.7
3.0
1.6
2.8
h)
Figure 7: Levenshtein distance matrix. Left: hard matrix and alignment path. Right: relaxed matrix with inverse temperature 3 = 1.5.
Gt TTaco (ww.4469449999440000 ATTAAAATTTTGGCCCCAE
and Our training objective is minimizing the 22 loss between the predicted distance and the ground truth distance:
T & AACC 9040 A
C = LD (CCN((a)))))).s)) (CNN(6)))
LD(YY.
(12)
For training,
inverse temperature of and Adam (1= 10-1) for 128 512 iterations.
For evaluation, we use Hungarian matching with Top-I accuracy as well as the Fl-score. We compare it against baseline, which uses the L distance between encodings instead of the editing distance:
L -=I|| (CNN(()))) (CNN():))
(13)
Tab. shows that our method consistently outperforms the baseline on both metrics all cases. The character combinations AB, BC, CD, DE, and EF canonical choice for random combinations. The characters IL represent are the hardest combination of two letters as they even get frequently confused by supervised neural networks [12) and can also be indistinguishable for humans. The easiest case as supervised classifiers can perfectly distinguish them on test dataset [1]. For two letter combinations,
characters OX represent
achieve Top-1 accuracies between 57% (IL) and 96% (OX). Even for four letter combinations (ACGT and OSXL), we achieve Top-1 accuracies of up to 48. 7%. Note that, statements are relaxed.
use strings of length 32, in the Levenshtein algorithm, more than 100
5 Conclusion
We proposed an approach for continuous relaxations of algorithms that allows their integration into end-to-end trainable neural network architectures. For that, we use convex combinations of execution paths of algorithms that are parameterized by smooth functions. We show that our proposed general framework can compete with SOTA continuous relaxations of specific algorithms as well as gradient estimation methods on a variety of algorithmic supervision tasks. Moreover, we show that our formulation successfully relaxes even complex algorithms such as shortest-path algorithm or renderer. We hope inspire the research community to build on our framework to further explore the potential of algorithmic supervision and algorithmically enhanced neural network architectures.
10

---

Acknowledgments and Disclosure of Funding
This work was supported by the IBM-MIT Watson AI Lab, the DFG in the SFB Transregio 161 "Quantitative Methods for Visual Computing" (Project-II 251654672), the DFG in the Cluster of Excellence EXC 2117 "Centre for the Advanced Study of Collective Behaviour" (Project-ID 390829875), and the Land Salzburg within the WISS 2025 project IDA-Lab (20102-F1901166 and 202244-W16//225/17720019
References
[1] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, "Attention is all you need," in Proc. Neural Information Processing Systems (NeurIPS), 2017.
[2] J. Redmon. S. Divvala, R. Girshick, and A. Farhadi, "You only look once: Unified, real-time object detection," in Proc. International Conference Computer Vision and Puttern Recognition (CVPR). 2016.
[3] A. W. Senior, R. Evans, J. Jumper, J. Kirkpatrick. L. Sifre. T. Green, C. Qin, A. Zidek, A. W. R. Nelson, A. Bridgland. Penedones. Petersen, Simonyan, Crossan, P. Kohli, D. T. Jones, D. Silver. K. Kavukcuoglu, and D. Hassabis, "Improved protein structure prediction using potentials from deep learning"' Nature, 2020.
[4] S. Liu, T. Li, W. Chen, and H. Li, "Soft Rasterizer: A Differentiable Renderer for Image-based 3D Reasoning," in Proc. International Conference on Computer Vision (ICCV). 2019.
[5] H. Kato, Y. Ushiku, and T. Harada, "Neural 3D mesh renderer," in Proc. International Conference on Computer Vision and Pattern Recognition (CVPR), 2018
[6] A. Grover, E. Wang, A. Zweig, and S. Ermon, "Stochastic Optimization of Sorting Networks via Continuous Relaxations," in International Conference Learning Representations (ICLR), 2019.
[7] M. Cuturi, O. Teboul, and J.-P. Vert, "Differentiable ranking and sorting using optimal transport," in Proc. Neural Information Processing Systems (NeurIPS). 2019.
[8] M. Vlastelica, A. Paulus, V. Musil, G. Martius, and M. Rolinek, "Differentiation of blackbox combinato- rial solvers," International Conference Learning Representations (ICLR), 2020.
[9] Q. Berthet, M. Blondel, O. Teboul, M. Cuturi, J.-P. Vert, and F. Bach, "Learning with Differentiable Perturbed Optimizers," " Proc. Neural Information Processing Systems (NeurIPS). 2020.
[10] G. Mena, D. Belanger, S. Linderman, and J. Snoek, "Learning latent permutations with gumbel-sinkhom networks," International Conference on Learning Representations (ICLR), 2018.
[11] X. Yan, Yang, Yumer, Guo, and Lee, "Perspeetive transformer nets: Learning single-view
3D object reconstruction without 3D supervision," Proc. Neural Information Processing Systems (NeurIPS), 2016.
[12] G. Cohen, S. Afshar, J. Tapson, and A. van Schaik, "EMNIST: an extension of MNIST to handwritten letters," arXiv preprint arXiv: peeXiv:/70...0 072705333, 2017.
[13] M. Blondel, O. Teboul, Q. Berthet, and J. Djolonga, "Fast Differentiable Sorting and Ranking," in International Conference on Machine Learning (ICML).2000
[14] W. Chen, J. Gao, H. Ling, E. J. Smith, J. Lehtinen, A. Jacobson, and S. Fidler, "Learning to predict 3D objects with an interpolation-bbssed differentiable renderer," in Proc. Neural Information Processing Systems (NeurIPS), 2019.
[15] A. Mensch and M. Blondel, "Differentiable Dynamic Programming for Structured Prediction and Attention," " International Conference on Machine Learning (ICML., Jul. 2018.
[16] C. Corro and Titov, "Differentiable perturb-and-parr variational autoencoder," in International Conference on Learning Representations (ICLR), 2019.
Semi-supervised parsing with a structured
[17] M. Rolinek, V. Musil, Paulus, M. Vlastelica, C. Michaelis, and G. Martius, "Optimizing rank-based metrics with blackbox differentiation"" Proc. International Conference on Computer Vision and Puttern Recognition ( (CVPR), 2020.
[18] S. Shirohokav, V. Belavin, M. Kagan, Ustyuzhanin, and A. G. Baydin, "Black-box optimization with local generative surrogates," in Workshop on Real World Experiment Design and Active Learning at International Conference on Machine Leurning (ICML), 2020.
[19] M. B. Paulus, D. Choi, D. Tarlow, A. Krause, and C. J. Maddison, "Gradient estimation with stochastic softmax tricks," in Proc. Neural Information Processing Systems (NeurIPS), 2020.
[20] E. Jang, S. Gu, and B. Poole, "Categorical reparameterization with gumbel-softmax." in International Conference Learning Representations (ICLR), 2016.
[21] Y. Xie, H. Dai, M. Chen, B. Dai. T. Zhao, H. Zha, W. Wei, and T. Pfister, "Differentiable top-k with optimal transport," " in Proc. Neural Information Processing Systems (NeurIPS), 2020.
11

---

[22] M. Cuturi and M. Blondel, "Soft-DTW: A Differentiable Loss Function for TemeeSeries." in International Conference on Machine Learning (ICML).2017.
[23] M. Blondel, A. Mensch, and J.-P. Vert, "Differentiable divergences hetween time series," arXiv preprint arXiv:2010.08354, 2020.
[24] D. Bahdanau, K. Cho, and Y. Bengio, "Neural machine translation by jointly learning to align and translate," International Conference on Learning Representations (ICLR), 2015.
[25] R. Collobert, A. Hanmun, and G. Synnaeve, "A fully differentiable beam search decoder," in International Conference on Machine Learning (ICML), Jul. 2019.
[26] D. Bahdanau, D. Serdyuk, P. Brakel, N. R. Ke, Chorowski, A. Courville, and Y. Bengio, "Task loss estimation for sequence prediction." " ICLR Workshop track, 2016.
[27] Shen, Lin, C.-W. Huang, and A. Courville, "Neural language modeling by jointly learning syntax and lexicon," in International Conference on Learning Representations (ICLR), 2018.
[28] S. S. Dasgupta, M. Boratko, Zhang. L. Vilmis, L. Li, and A. McCallum, "Improving local identifi- ability in probabilistic box embeddings," in Proc. Neural Information Processing Systems (NeurIPS), 2020.
[29] Y. LeCun, C. Cortes, and C. Burges, "Mnist handwritten digit database," " ATT Labs, vol. 2, 2010. [Online] Available: /tttp://yann... lecun. com/ exmbb/nit///
[30] A. X. Chang. T. Funkhouser, L. Guibas, P. Hanrahan, Q. Huang, Z. Li, S. Savarese, M. Savva, S. Song, H.
Su, J. Xiao, L. Yi, and F. Yu, "ShapeNet: An information-rich 3D model repository," Computing Research Repository (CoRR) in arXiv, 2015. [Online]. Available: http::://ttttt/// arxiv. org/ ha//abb//11111 03012 [31] E. W. Dijkstra et al., "A note two problems in connexion with graphs." Numerische mathematik, vol. 1,
no. pp. 269-271, 1959.
[32] S. Chaudhuri and A. Solar-Lezama "Smooth interpretation." in Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation, ser. PLD1 '10 Association for Computing Machinery, 2010.
[33]
"Smoothing a program soundly and robustly." in Proceedings of the 23rd International Conference on Computer Aided Verification, ser. CAV" Springer- Verlag, 2011.
[34]
W. J. Cody, "Rational Chebyshev approximations for the error function," Mathematics of Computation, vol. 23, no. 107, pp. 631 631-637, 1969.
[35]
A. Graves, G. Wayne, and I. Danihelka, "Neural turing machines," arXiv preprint arXiv: 2014.
[36]
A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, "Pytorch: An imperative style. high-performance deep learning library," " in Proc. Neural Information Processing Systems (NeurIPS). 2019.
[37] O. Astrachan, "Bubble sort: An archacological algorithmic analysis," " ACM Sigese Bulletin, vol. 35, no. 1, pp. 1-5, 2003.
[38]
Kingma and "Adam: method for stochastic optimization," in International Conference on Learning Representations (ICLR), 2015.
[39] R. Bellman, "On a routing problem." Quarterly of applied mathematics, vol. 16, no. 1. pp. 87-90, 1958. Reconstruction
[40] F. Petersen, A. H. Bermano, O. Deussen, and D. Cohen-Or, "Pix2Vex: using a Smooth Differentiable Renderer," arXiv preprint arXiv: 11149, 2019.
[41] V. I. Levenshtein, "Binary codes capable of correcting deletions, insertions, and reversals," in Soviet physics doklady, vol. 10, 1966, pp. 707-710.
12


Reviews:
[{"review_id": "mysEcdDup3N", "reviewer": "Reviewer_YtiF", "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.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have following comments.\n1. Why the proposed method is inferior to Perturbed Opt? It is better to explain this in detail.\n2. It is better to estimate the scalability of the proposed theoretically.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "RomgUBuZaT", "reviewer": "Reviewer_GwAs", "summary": "This paper tries to integrate algorithms into end-to-end trainable neural networks.\nIts 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.\n\nThe authors evaluate the proposed method on four tasks.\n1. Sorting concatenated MNIST images\n2. Finding the shortest path\n3. Reconstructing voxels from silhouettes\n4. Computing Levenshtein distance", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\noriginality:\n- The authors propose continuous relaxations of different algorithmic concepts: comparators, conditional statements, loops, and indexing.\n  - The proposed method estimates expectation by sampling-free closed form solution.\n- I cannot consider originality due to my lack of expertise.\n\nquality:\n- Eq. 1-5 supports choosing logistic distributions for relaxation.\n- Relaxed comparators are reasonable (Eq. 8-10).\n- Relaxed indexing is somewhat vague because not every array has semantic relationship between neighboring elements (L227-229).\n  - The latter case should be covered in the experiments or the reason for not covering should be described.\n\nclarity:\n- Most parts are clear to understand.\n\nsignificance:\n- 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Corner cases where the proposed method cannot handle should be mentioned.\n\nSocietal impact: n/a", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "2FG8d3IbF0X", "reviewer": "Reviewer_nw3A", "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.\nThis paper aims to formalise some of these operations in a more general framework.\n\nThe 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)\n\nSimilar 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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Method and related work\n\nThe 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. \nHowever, 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.\n\nAn example would be the Neural Turing Machine, and the various gating systems could be reframed as if-else conditions. \n\nSome references of this nature:\nIf-else:\nGraves, Alex, Greg Wayne, and Ivo Danihelka. \"Neural turing machines.\"\nShen, Yikang, et al. \"Ordered memory.\"\n\nStick-breaking while loop\n\n- Yogatama, Dani, et al. \"Memory architectures in recurrent neural network language models.\"\n- Shen, Yikang, et al. \"Neural language modeling by jointly learning syntax and lexicon.\" \n- Graves, Alex. \"Adaptive computation time for recurrent neural networks.\"\n- Joulin, Armand, and Tomas Mikolov. \"Inferring algorithmic patterns with stack-augmented recurrent nets.\"\n\nIndexing:\n- Graves, Alex, Greg Wayne, and Ivo Danihelka. \"Neural turing machines.\"\n- Graves, Alex, et al. \"A novel connectionist system for unconstrained handwriting recognition.\"\n(attention system over image)\n\nThis work also has some connections to other work that deal with relaxation of known algorithms.\nAnother paper that creates a framework for relaxations of certain structure-based algorithms is:\n- Mensch, Arthur, and Mathieu Blondel. \"Differentiable dynamic programming for structured prediction and attention.\" \n\nSpecifically for the Eisner algorithm:\n- Corro, Caio, and Ivan Titov. \"Differentiable perturb-and-parse: Semi-supervised parsing with a structured variational autoencoder.\"\n\nExperiments\n\nMNIST Sorting Very surprising that relaxed bubble sort works better than the sinkhorn based method.\n\nWarcraft shortest-path: Do you un-relax the algorithm during test time? Using the cost computed with the relaxed approach might result in lower costs.\n\nMight 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, ...)\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\nThe authors have addressed one particular limitation of such relaxations, which is in combining separate branches. \n", "review_text": "", "extra_scores": {"ethical_concerns": "N/A: Work is largely theoretical", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "1ypD3JrTLRx", "reviewer": "Reviewer_1ez2", "summary": "\nThis 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).\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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.\n\nIn 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.\n\nThe 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.\n\nSimilarly, 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.\n\nAnother 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.\n\nThe 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.\n\nHowever, 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.\n\nThe 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.\n\nSome 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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\nNo. 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.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)