Rethinking Deep Thinking: Stable Learning of Algorithms using Lipschitz Constraints

Authors: jay  bear
adam  prügel-bennett
jonathon  hare
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 18:26:59

Abstract: Iterative algorithms solve problems by taking steps until a solution is reached. Models in the form of Deep Thinking (DT) networks have been demonstrated to learn iterative algorithms in a way that can scale to different sized problems at inference time using recurrent computation and convolutions. However, they are often unstable during training, and have no guarantees of convergence/termination at the solution. This paper addresses the problem of instability by analyzing the growth in intermediate representations, allowing us to build models (referred to as Deep Thinking with Lipschitz Constraints (DT-L)) with many fewer parameters and providing more reliable solutions. Additionally our DT-L formulation provides guarantees of convergence of the learned iterative procedure to a unique solution at inference time. We demonstrate DT-L is capable of robustly learning algorithms which extrapolate to harder problems than in the training set. We benchmark on the traveling salesperson problem to evaluate the capabilities of the modified system in an NP-hard problem where DT fails to learn.

Main paper: 
 introduction: 
 Iteration is a key ingredient in a vast number of important algorithms. Incremental progress towards a solution is demonstrated in many of these. Well-known examples include insertion sort, gradient descent, and the simplex method. This paper explores models that learn iterative algorithms. We ask questions including: Can deep learning models be used to learn the complex steps of algorithms similar to these? Is there a way to guarantee a solution or approximation is reached? Can we learn algorithms that extrapolate to larger or harder instances than we train on? In addressing these questions we propose a model called Deep Thinking with Lipschitz Constraints (DT-L). x ϕ (M) ϕ (m) Figure 1 : Recurrent-based model architectures for learning algorithms with input x and output y. F, G and H are convolutional networks that work on any size input. A scratchpad ϕ serves as the working memory during computation. As described in Section 2 the original DT model didn't include recall, denoted by the dotted line. The improved DT-R and our DT-L model include this connection. Some work towards answering the above questions has occurred in recent years. A key approach has been to utilize various forms of a learned recurrent function to implement a 'step' in an iterative algorithm that computes a solution to a problem. Typically these recurrent functions are combined with learned functions that pre-process the initial input, and post-process the output of the last iteration into the final solution form. Examples of such approaches are the Deep Thinking (DT) networks [18] and Deep Thinking with Recall (DT-R) networks [2] that we build upon in this work (see Figure 1 ).There are two key features to these models: firstly the use of an iteratively updated scratchpad, ϕ serving as a working memory; and secondly, the construction of the model from convolutional layers to enable it to scale to arbitrary sized problems. The latter is important because in principle it allows training on smaller problems, and then extrapolation at inference time to larger problems [2, 18] .Many challenges still remain with the existing DT and DT-R approaches however, and we aim to address these in this work. Firstly, DT-style networks are quite difficult to train and can be very unstable both during training and inference. The DT-style networks previously demonstrated in the literature are massively overparameterized -we show in Section 3 that model width is inversely related to training stability in existing models, and later demonstrate how this can be addressed (see Section 4) . Secondly, existing approaches have no guarantees on the convergence of the learned algorithm; this is important because if a solution to a problem exists, one would hope that an algorithm to solve it would terminate or reach a stable state once the solution has been reached. Section 4 details a design approach to guarantee convergence within the limits of floating point precision by considering the network in terms of a discrete dynamical system. Our contributions are:• We systematically analyze DT networks and explore why they can be unstable;• we introduce techniques grounded in theory into the DT framework which improve the stability of learning and guarantee convergence at run time. This allows the use of much smaller models to tackle the same problems, and improves extrapolation performance;• we propose our Deep Thinking with Lipschitz Constraints (DT-L) model and perform a comprehensive evaluation and ablation study; and,• we show that the approach can be applied to learn to find low-cost tours for a range of TSPs, including non-Euclidean and asymmetric instances. 
related work: 
 Deep Thinking (DT) networks [18] were designed to learn algorithms by using recurrence to induce iterative behavior in such a way they could be trained on smaller and simpler examples before extrapolating to larger tests. The networks were used to solve 'Easy-to-Hard' problems (consisting of prefix sums, mazes, and chess puzzles [17] ) and they could be trained with few iterations on easy problems in such a way that they can solve harder problems by increasing the number of iterations.DT networks were further improved by Bansal et al. [2] by means of adding 'recall' (which we refer to as DT-R networks) -a mechanism for the recurrent component to have continuous access to the original input. Recall successfully allowed DT-R networks to solve much larger tests than DT networks without recall, while also mitigating overthinking, where if after too many iterations at inference time the predicted solution becomes progressively worse. In addition to recall, Bansal et al. introduced incremental progress training (IPT), a training method which disables gradient tracking for a random number of initial iterations. This prevents the model from learning behaviors based strictly on the number of iterations and instead promotes incremental modification to the internal states.There exist alternative approaches to producing machines which can learn algorithms. One set of models are Neural Turing Machines (NTMs), which use attention in a recurrent system for reading to, and writing from, some external memory [6] . NTMs showed success in learning cell-based copying and repeating tasks which could be applied to unseen inputs. Differentiable Neural Computers (DNCs) operate similarly to NTMs, differing primarily in their method of external memory access [7] . In the NTM, like most RNNs, the amount of compute is directly tied to the input sequence length.Graves [5] proposed a method to adaptively select the compute budget in RNNs. The models studied here are different in the sense that the objective is to extrapolate beyond the training data to harder problem instances as the compute budget is increased, and the input and output is not a sequence.A second class of models exist where a specific base iterative algorithm is defined, and the parameters of the algorithm, or the problem, are learned. Examples include the reverse diffusion process learned in diffusion models [9] , and models which involve optimization using gradient descent iterations within the forward pass to generate an output with certain properties that are difficult to produce directly with a neural network, such as permutation equivariance [21] . Our work does not constrain the class of algorithm used directly, other than enforcing that we learn an iterative one.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We have discussed limitations in some detail and created a separate limitations paragraph in Section 7. The approach we develop analytically has relatively few direct limitations as the assumptions are mild. However, even on simple problems we recognise that whilst we have made significant improvements over prior approaches there are still times where the model fails to learn for example. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
analysis of deep thinking networks: 
 The main architecture used in pre-existing Deep Thinking networks [2, 18] , and our own network, is shown in Figure 1 . It takes an input problem instance x and generates a solution y. The model consists of three convolutional networks F, G and H. The function F is responsible for initially pre-processing the input x into the initial state ϕ (0) ; function G is the recurrent function that takes the current state, ϕ (m) (plus the original input x in the case of DT-R and our models), to produce the next state, ϕ (m+1) . The final state produced by G, after M iterations, is denoted ϕ (M ) . The function H takes ϕ (M ) and produces the predicted output y. FormallyEQUATIONEQUATIONEQUATIONArchitecturally these networks are recurrent neural networks. Unlike more commonly used recurrent networks such as LSTMs they are not used to tackle problems with sequential data, but rather the recurrent part is used to find a solution through an iterative process. The algorithm that the recurrent network uses, as well as the pre-and post-processing functions are learned through supervised training on example input-solution pairs for a particular problem.As the networks F, G and H are convolutional neural networks they can work with an arbitrary size input. The solution y is typically the same size as the input x. The feature of DT and DT-R that excited interest was that, not only could they solve unseen problem instances of the same size as they were trained on (which we call interpolation), but when trained on small problem instances (with relatively small M ), they were able to find low cost solutions on much larger problem instances (which we refer to as extrapolation) by increasing M at inference time. Both DT and DT-R suffer from poor stability both in training but particularly at inference time when extrapolating to larger problems. This often lead to overflow errors. This was particularly seen if the number of channels in network G is reduced, then DT and DT-R are hard to train with many runs failing to find a solution. We show the reason for this is that there is no mechanism to control the change in size of the scratchpad representation, ∥ϕ (m) ∥/∥ϕ (m-1) ∥, leading to this either overflowing or vanishing during learning.In this section we focus on DT-R as this is more stable than the original DT network. We use the spectral norm of the reshaped weights of a convolution 1 to capture the expansion or shrinkage in magnitude of the output relative to the input of a sub-network, with a value of 1 meaning that the For small w training is stable, but not all models converge; larger w has a higher chance of models reaching a small loss, but the training process has very large spikes in the loss which causes some models to explode. Each curve is measured from a different random initialization of the model throughout training, for 10 models of each width magnitude is constant. In Figure 2 , we use violin plots to show the distribution of spectral norms for the four convolutional layers that arise after training DT-R on the prefix-sum problem (see Section 5 for a description of the problem). We observe that the spectral norms are typically greater than one, which can lead to the norm of ϕ (m) growing with each iteration. In turn this can cause the model to overflow when applying the model to a larger input (the extrapolation scenario), where we increase the iteration number M in order to solve the larger instance size. The DT models as described and implemented by Bansal et al. [2] have training behavior which becomes increasingly unpredictable as the width w (number of channels in the scratchpad) is reduced. This can be seen in Figure 3 , where the variation in training loss at the end of training over different runs is larger in models of smaller width. It is also worth noting that increasing the width can result in explosive behavior in loss, including not-a-number (NaN) results, which can be seen in Figure D4 .The property of the DT networks that excited our interest was their ability to solve large instances than they were trained (that is, their extrapolative ability). This generalization to out-of-distribution examples is a key challenge for many machine learning algorithms. However, although DT-R can find models that extrapolate, very often the models that are trained extrapolate poorly. We observe models trained on few recurrences may have explosive behavior which only becomes a problem with extrapolative tasks requiring more recurrences.Both DT and DT-R network used no bias terms in their model [2, 18] . In experimenting with these networks, we found that adding bias made these models very unstable. Unfortunately, having no biases exacerbates the 'dead cell problem', where some of the convolutional filters would have a zero response to all training inputs.4 Refinement of the Architecture: Deep Thinking with Lipschitz ConstraintsIn the previous section we have identified a problem faced by DT-R, namely that there is instability in reaching a solution through the iteration in Equation (2). To overcome this difficulty we use a well known property of contraction maps. If c : V → V is a mapping of objects, v and w, in a normed vector space V, that is contractive in the sense thatEQUATIONimplying c(•) is a Lipschitz function with Lipschitz constant K < 1, then the iterationsEQUATIONwill converge to a unique solution as a consequence of the Banach fixed-point theorem [1, 3] . We can use this to refine DT-R by engineering the network G(•, x) to be a contraction mapping. Noting that in Equation (2) the input x is held constant throughout the iteration, we construct G(•, x) so that it has an approximate Lipschitz constant K less than 1.Although any Lipschitz constant less than 1 would guarantee convergence, the nature of the problem solving mechanism we seek to learn intuitively means that we do not want fast convergence. This is because the network G performs local convolutions with a limited receptive field. However, finding good quality solutions often requires a global knowledge. To accumulate such knowledge requires long distance information to accumulate in the scratchpad vector ϕ (m) over multiple iterations. To allow this to happen we choose the approximate Lipschitz constant associated with G to be less than, but close to 1.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: Sketch-proofs and the intuition behind our architectural designs of a recurrent function that converges are given in the body of the paper, with more formal proofs in the appendices (Appendix A) and are cross-referenced. All assumptions are clearly stated. Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
constraining the lipschitz constant: 
 The primary tool we use to control the Lipschitz constant of G(•, x) is spectral normalization [15] . This is an extension of spectral norm regularization, introduced by Yoshida and Miyato [20] , but it sets the spectral norm of an operator to a fixed value rather than penalizing the norm of an operator that differs from a predefined value. The method uses a power iteration to compute an approximation of the spectral norm of an operator, updated after each gradient step. Computation of the spectral norm is a costly operation, but it only has to be done at the beginning of the iterative process.As network G consists of convolutions we divide each convolution kernel weight by the spectral norm plus a small constant ε to ensure the spectral norm is less than one; there is one exception in that the convolution applied to the recall connection x does not need normalizing -please see Appendix B for full details. In addition to using the spectral norm we need to make sure all the other transformations carried out by G are at most 1-Lipschitz. However, to avoid applying constraints to the constant recall connection, we replace DT-R's method of applying a single convolution on the concatenation ϕ (m) , x with two separate convolutional layers on ϕ (m) and x respectively whose output is combined by element-wise addition. See Appendix A for a rigorous discussion on how the Lipschitz behaviour we require is ensured.Constraining Activation Functions. To guarantee convergence under the constraints provided, any activation function used in G must be 1-Lipschitz. This includes Rectified Linear Units (ReLUs), Exponential Linear Units (ELUs) [4] , and tanh, but excludes Gaussian Error Linear Units (GELUs) [8] , which have an absolute gradient greater than 1 around x = √ 2. Results in the body of this paper use the ELU activation for DT-L networks and the ReLU for DT-R as originally defined. Additional results using ReLU for DT-L and ELU for DT-R can be found in Appendix D.2.Constraining Residual Skip Connections. DT and DT-R use element-wise addition for residual connections in recurrent blocks. The sum of two functions c : X → Y and d : X → Y applied to the same input, with Lipschitz constants K c and K d respectively results in the upper bound,EQUATIONfor all x 1 , x 2 ∈ X. In the case of a standard residual connection, one function is the identity (id(x) = x) and the other is the block of layers B contained in the span of the residual connection. Under our constraints, the identity is 1-Lipschitz and the block of layers is K B -Lipschitz, where K B ∈ [0, 1). This results in a Lipschitz upper bound for the output of 1 + K B .As a result, residual connections as addition between the identity and a block of layers can increase the Lipschitz constant of the recurrent part even if the layers themselves are 1-Lipschitz. A solution to this, which also allows more expression in the model, is to make each residual connection a parametric linear interpolation between the identity output and the block outputEQUATIONDT-L applies this interpolation to each channel, c, individually; an unconstrained learnable parameter γc exists for each channel in each residual connection, then the residual parameters are set to γ c = σ( γc ) where σ is the logistic function to ensure that 0 ≤ γ c ≤ 1.The above changes leads to a more stable network, allowing us to make additional modifications and still obtain convergent behaviour with improved performance. Without explicitly controlling the Lipschitz constant, these changes often lead to complete failure of the network to solve the problem.In our final model design we apply three extra modifications that lead to consistent improvements:1. Batch normalization layers [10] are added for the input and after each convolution, except for layers in the recurrent block and the final output layer. Empirically this improves performance.2. A bias term is added to the recall convolution (without the Lipschitz constraint) in G. The bias term is added to the recall convolution to mitigate the dead cell problem. Since this is a constant addition (along with recall) it does not disrupt the convergence constraints we have put in place (see Appendix A). A bias term is also added to the final (output) layer and, when batch normalization is not used, to F.3. Exponential Linear Unit (ELU) activations [4] are used instead of rectified linear unit (ReLU) activations. This choice is influenced by the desire to promote activations staying close to zero [4] throughout iteration, as well as mitigating the effect of the dying ReLU problem [19] where 'dead' activations increase with depth [13] . Artificially deep models like DT are therefore likely to encounter this problem. Using ReLU can also result in a rapid rate of convergence, preventing the model from learning complex algorithms for harder tasks (see Appendix D.2).Our reasoning for not applying batch normalization in the recurrent block follows from Jastrzebski et al. [11] where unsharing batch normalization statistics was necessary to avoid activations exploding.In an architecture where the maximum number of iterations is unknown it appears infeasible to unshare batch normalization statistics for every iteration.Using these modifications -creating a model we call Deep Thinking with Lipschitz Constraints (DT-L) -greatly improves the stability of training and using these networks. As we will see in Section 5, the new DT-L network allow us to solve the same problems explored by DT and DT-R, but using, in some cases, three orders of magnitude less parameters while achieving high performance and a more consistent success rate during training. The increased reliability offered by DT-L allows us to explore many other modifications enabling us to tackle more sophisticated problems. We illustrate this by attempting to find good solutions to one of the most notoriously difficult problems, namely, the traveling salesperson problem (TSP).Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: Full details of our model design is given in Appendix B, with training details provided in Appendix C. The main evaluation setup repeats that described by Bansal et al. [2] and Schwarzschild et al. [18] where we use the datasets provided by Schwarzschild et al. [17] for studying easy-to-hard generalisation. Further we provide the code for all models and experiments (as supplementary material during review, and later as a GitHub link). Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
results on easy-to-hard problems: 
 In this section, we compare our model (DT-L) against DT-R. Note that DT-R is an improvement of DT by the same authors and has already been shown to have better performance [2] . We test on the three problem classes used by Bansal et al. [2] to evaluate DT-R, namely a prefix sum problem, a maze problem and a chess problem.We have trained and evaluated the models on a range of different Nvidia GPU accelerators from RTX2080Tis to A100s, as well as on M3-series Apple Silicon. Memory usage is insignificant compared to available GPU memory. Training time is of the order of 30 minutes for the w = 32 model on the prefix-sum problem using a single RTX8000. More details can be found in Appendix E, and code for the experiments can be found at https://github.com/Jay-Bear/ rethinking-deep-thinking.The accuracy given in this section measures the proportion of instances where the network produces the exact correct solution. Note that even if a predicted solution differs from the target by one element (e.g. 1 bit in prefix sums, 1 pixel in mazes) it is considered a failure.Prefix Sums. The prefix sum problem involves translating a string of ones and zero to a new string that counts sequences of ones (details are described by Bansal et al. [2] ). The problem is simpler than the the maze and chess problem, and considerably faster to run. As a consequence we choose this as the main problem to perform a comparative study.In our experiments we compare the DT-R model to our DT-L model. Both were trained on instances consisting of 32 bits for a maximum of 30 iterations, using IPT with α = 0.5. Both models have a width (number of channels) of w = 32 (more details about architecture can be found in Appendix B.1). We found that for this problem there is little change in performance above w = 32 for DT-L. In Figure 4 we show the solution accuracy for 30 randomly-initialized models of both DT-R and DT-L on the 512-bit test dataset versus the number of iterations (M ) to generate those solutions. We measured the performance on 10 000 randomly generated instances of each problem. The error in the mean is less than 0.5% which is approximately the width of the lines in the figure. As can be seen DT-R struggles to consistently find networks that extrapolate to larger problem settings (it only obtains greater than 90% accuracy on two out of 30 training runs). In contrast DT-L only fails to reach above 90% accuracy on two out of 30 training runs. To emphasize DT-L's performance on smaller widths, we selected w = 32 as the primary width for comparison. We perform ablations on other aspects of the model in Appendix D.2.Mazes. The mazes problem consists of drawing the correct path for a blank maze, given a starting point and an ending point. Details about the representation of mazes is given in Schwarzschild et al. [17] and Bansal et al. [2] . Our tests are performed on models trained on 17 × 17 mazes, extrapolated to 33 × 33 mazes. Results from multiple runs and an aggregate can be seen in Figure 5 .The maze models defined by Bansal et al. [2] are trained on 9 × 9 mazes. Attempting to train DT-L on mazes of this size resulted in the models often learning trivial solutions which did not extrapolate to larger mazes.Chess Puzzles. The chess puzzles problem involves identifying the next best move of the current board state. Specifically, the model must learn to classify 1s in two cells representing the piece to move and the location to move to, and 0s elsewhere. The models are trained on a train/validation split of the easiest 600,000 problems, where difficulty is based on Lichess.org rankings (see Schwarzschild et al. [17] for more detail).This problem in particular can be viewed as different to both the prefix sums and mazes problems in that the difficulty of the problem doesn't come from the size. All chess puzzles in this dataset are standard 8 × 8 chess boards. For all tests on the chess dataset [17] we follow the same number of epochs as Bansal et al. [2] . Results are shown in Figure 6 . DT-L achieves very similar performance to DT-R, seemingly hitting the same apparent ceiling on performance discussed by Bansal et al. [2] . We would like to explore the reasons for this in more detail the future, but we note that at training time the models do not reach 100% accuracy, so it should not be a surprise that they do not always extrapolate. It is possible that the issue arises from the structure of the data and the way it interacts with the model architecture. 
benchmarking on traveling salesperson: 
 To demonstrate the strength of DT-L, we have formulated the traveling salesperson problem as a differentiable optimization task for the model to solve. This is a significantly more challenging problem than those discussed in Section 5. The problem instance x is now the matrices of "distances" with additional information. For arbitrary distance matrices this is known to be NP-hard. An optimal solution corresponds to a tour (permutation of the cities) such that the sum of distances between neighboring cities is minimized, although we seek only to find a low cost tour. Constraints on the chess puzzles problem on models of two different widths, showing the mean accuracy of inference-time runs on problems ranked in increasing difficulty between 1,000,000 and 1,100,000. Aggregate of six models, each trained on the easiest 600,000 problems, where shaded areas show 95% confidence intervals.The solution vector y is a binary matrix with 1s corresponding to the edges that are used in the tour. We constructed the network so that the solution vector would correspond to a feasible solution.Unfortunately, in doing so involves an intermediate representation where the evaluation of the cost is non-trivial, which made the problem of learning an iterative solution very challenging. To overcome this, we increased the expressiveness of the scratchpad vectors ϕ (m) to learn orthogonal transforms that it applied to a part of the scratchpad vector. This considerably improved the performance of the network. Details of the modification used are given in Appendix B.1.In Table 1 we give the mean tour length for randomly generated instances from two class of problems: symmetric random tours and asymmetric random tours. The DT-L models were trained for each problem class on tours of size n = 15 with M = 45. We show both interpolative results (using a new set of tours on the same size problems) and extrapolative results where we test of problems of size n = 30 with M = 120. For comparison we provide the length of random tours, the length of tours generated by the greedy nearest neighbor (NN) algorithm, and the length of tours from a modified version of the NN algorithm which selects the lowest-cost NN tour out of all starting points instead of starting from a random point (BNN).The results in Table 1 show DT-L's ability to learn non-trivial algorithms by performing considerably better than random tours. That the results are worse than the nearest neighbor methods should not be surprising, as in the asymmetric non-Euclidean case these are amongst the best known algorithms.The models take approximately 8 hours to train on an RTX2080Ti GPU for 80,000 batches of 64 randomly generated TSPs for both symmetric and asymmetric settings with n = 15 and M = 45.Testing was performed on M3 Apple Silicon with MPS acceleration and takes 3.59ms per n = 15 problem instance for M = 45 and 23ms per n = 30 problem with M = 120.  
discussion: 
 Deep Thinking-style architectures provide a new paradigm for using machine learning for general problem solving. The key idea is to use a recurrent architecture to find a solution through multiple iterations. This paper has addressed a major drawback of the published models which is the instability that frequently arises in the iteration steps. Having addressed these problems not only are we able to obtain networks that much more reliably solve new problems, but we show that we can run much smaller networks with similar and often better performance. To illustrate the potential of this approach we have tackled a notoriously difficult problem, namely TSP.Deep Thinking approaches are attractive because they learn a general problem solving strategy that can be used to solve considerably larger instances of the problem than they were trained on. Extrapolation to problems outside the training dataset is an area where traditional machine learning struggles. Clearly, the problems these models extrapolate to are in the same problem class to the training data, but it is noteworthy that the strategies learned for the problem classes we have investigated scale in this way. Another interesting feature is that the network learns the problem solving strategy through examples (in the case of TSP it is not even shown any low cost solutions).Admittedly, for TSP we needed to construct a network that outputted tours and to get the quality of results we did we introduced a mechanism for learning orthogonal transformation which we then applied to part of the scratchpad vector. However, we did not build in any explicit rules for solving the TSP -so much so that we do not fully understand the algorithm DT-L uses to find low cost tours, particularly in the case of asymmetric non-Euclidean TSP.Broader impact. Given the ubiquity of iterative algorithms in solving problems, having a mechanism to learn such algorithms opens up a lot of possibilities. The advantage of using a recurrent mechanism over a feed-forward architecture is that to solve a larger problem we simply needed to run the recurrent loop more often; this is often desirable in the real world because it might be impossible to train on sufficient data that you can guarantee not to need to extrapolate at inference time. Clearly, models of this kind have very many potential applications -both in developing new (and potentially improved -could we learn an algorithm that is significantly faster or more energy efficient than anything currently existing?) algorithms for existing problem classes where we already have solutions, as well as in all areas of predictive modelling where we believe the input-output relationship is best captured through a potentially-deep recurrent function. Inevitably, some of the potential uses also have the potential for misuse.Limitations. This work shows theoretically and empirically that it is possible to modify an architecture to learn recurrent functions with convergence guarantees. The problems we solve are relatively simple however. The performance we obtain, for example, on TSP is far from state-of-the-art, but we believe that the contribution is significant as we are able to find a heuristic algorithm running in M = O(n log(n)) steps through trial and error, without any explicit inductive bias towards finding what we might consider to be a sensible algorithm. There are also clearly other potential issues with the approach; learnability is significantly improved over previous attempts, but there are still cases where the model fails to learn. The use of convolutions means that the only way to capture long-term (or large distance) dependencies in the data is through iteration; this is possibly a benefit, but other architectures with different structural biases might work better on certain problems. We believe, in terms of comparison to NN and BNN heuristics, this local view of the distance matrix may contribute to the disappointing appearance of the results.Outlook. This work leaves many open directions for future research. It would be interesting to explore different architectures, such as Transformers, and more diverse problem settings. It would also be fascinating to better understand what algorithms are learned by the model under different settings and whether for example the complexity of the learned algorithm can be controlled.As discussed in the main paper one of its major contribution is the observation that by making G(•, x) K-Lipschitz with K < 1, then the iterative mapping defined in Equation ( 2) is guaranteed to converge to a unique solution as a consequence of the Banach fixed-point theorem [1] . To engineer G(•, x) to be K-Lipschitz we rely on a few well known properties of functions. If C : X → Z is a composition of two Lipschitz mappings A : X → Y and B : Y → Z with Lipschitz constant K A and K B then∥C(x) -C(y)∥ = ∥B(A(x)) -B(A(y))∥ ≤ K B ∥A(x) -A(y)∥ ≤ K A K B ∥x -y∥. (A1)Thus a sufficient condition to ensure C is K-Lipschitz with K < 1 is that K A , K B < 1. This trivially generalises to any number of compositions.In the network G(ϕ, x) the input vector x is added to ϕ through a convolution. However, adding an offset vector to a mapping does not affect the Lipschitz property as if A is K-Lipschitz and c is a constant vector, then the mappingEQUATION)Since during every iteration the input vector x and the convolution filters remain unchanged, the addition of the input x (which the Deep Thinking with Recall authors termed the recall) does not change the Lipschitz property of the network.Finally, to ensure the Lipschitz behaviour of the convolutions we note that convolutions are equivalent to applying a matrix, C, to some vector, v. For a matrix norm ∥C∥ that is compatible with a vector norm ∥x∥,EQUATIONwhere there exists a vector x where the equality conditions holds. If N = ∥C∥ then, through the linearity of norms, D = (K/N ) C will have norm K/N so that the linear mappingEQUATION)This would be true for any normed vector space with an appropriate compatible matrix norm. In this paper we have used the ℓ 2 norm where the compatible matrix norm is the spectral norm (i.e. the largest singular value).To allow the algorithm being run by network G to accumulate enough information to find a good solution we want the Lipschitz constant, K, of network G to be as close to 1 as possible. If the network can find a good solution rapidly then it can find a scratchpad vector ϕ in a region where the effective Lipschitz constant is less than 1. Indeed, we observed that despite Deep Thinking with Recall most often having Lipschitz constant greater than 1, nevertheless in the few runs where a successful network was learned, the growth in the solution ϕ (m+1) / ϕ (m) could be less than 1. Being on the edge of the stable region seems to be helpful for the network to find good solutions to hard problems. Consequently, in engineering the network G we attempt to make the Lipschitz constant for most mapping layers as close to 1 as possible.In this section we describe the architecture of DT [17] , DT-R [2] and our network DT-L. For DT and DT-R the architecture is identical to that described in the original paper. We include a description here to make the comparison with DT-L clearer. The number of channels of the input, x, varies depending on the problem class. It is 1 for prefix sums, 3 for mazes, 12 for chess and 3 for TSP.Following DT and DT-R, the output vector, y, has two channels. During training this is used to compute a categorical cross-entropy loss, while at inference time this is put into a max function to obtain a binary output.In all models the convolutions are either 3 (for prefix sum) or 3 × 3 with stride 1 and padding 1. In the figures below the boxes with rounded edges represent convolutions.Deep Thinking. In Figure B1 we show the Deep Thinking (DT) model. Note in this case the input vector x is not given to the network at each iteration of G.+ + ϕ m ϕ M x ϕ m+1 G F H ϕ 0 y Figure B1:The DT architecture of Schwarzschild et al. [18] . Arrows denote flow from one function to the next with recurrent iterations are denoted by the dashed arrow. Single-lined rounded rectangles denote regular convolutions. Activation functions in square boxes are ReLU.Deep Thinking with Recall. In Figure B2 we show the architecture for the Deep Thinking with Recall (DT-R) model. In DT-R the network is fed x every iteration and it is concatenated to the recurrent connection. 7)). Rather than concatenating the recall x into the recurrent input we pre-process it with a convolution and then sum with a convolved version of the recurrent input.ϕ 0 ∥ H F G ϕ m+1 x ϕ M ϕ m + + yRecall that in TSP the input vector x corresponds to the matrices of distances2 . The solution y is a binary matrix showing which edges we used in the tour. Thus, the cost of the full tour is sum(x ⊙ y),where ⊙ denotes element-wise multiplication. This is just the sum the set of edge distances that are used in the tour. This is schematically shown below.       0.00 0.33 0.78 0.22 0.57 0.25 0.75 0.00 0.49 0.22 0.39 0.49 0.83 0.31 0.00 0.28 0.61 0.56 0.37 0.18 0.50 0.00 0.78 0.13 0.19 0.61 0.11 0.68 0.00 0.49 0.30 0.64 0.82 0.71 0.68 0.00        ⊙        0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0        =        0.00 0.00 0.00 0.22 0.00 0.00 0.00 0.00 0.00 0.00 0.39 0.00 0.00 0.31 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.13 0.00 0.00 0.11 0.00 0.00 0.00 0.30 0.00 0.00 0.00 0.00 0.00        x ⊙ yThe edge matrix y is a matrix with a 1 in each row and each column and zero elsewhere. That is, it is a permutation matrix. Unfortunately, not all permutation matrices correspond to legal tours. The only permutations that are allowed correspond to irreducible permutation (i.e. those consisting of a single cycle of length n, where n is the number of cities)-these are cyclic permutations of order n. This, arises because there are (n -1)! tours (since the starting city is arbitrary) whereas there are n! permutation matrices. The illegal permutations consist of multiple cycles (e.g. for a four city problem we might have 1 ↔ 2 and 3 ↔ 4.). It is however challenging to generate irreducible permutations. To solve this problem we use the fact that the set of permutations of order n form an equivalence class [n] and for any permutation q ∈ S n (where S n is the group of all permutations of n objects-known as the symmetric group) then if π ∈ [n] the conjugate q π q -1 ∈ [n]. This is a well known result in group theory, but it means that if we start with an irreducible representation π (e.g. the tour1 → 2 → 3 → • • • → n → 1)then for any permutation matrix q the product q π q -1 represents a legal tour. Thus we set up the networks to generate a permutation matrix q. This used a Gumbel-Sinkhorn network [14] as part of network H. Occasionally this would generate a solution with fractional edges. To avoid this we added a term to the loss function that punished solutions with fractional edges.Although this procedure guarantees that the solutions correspond to feasible tours, the quality of tours obtained when we trained the full network is poor. The problem is that the relationship between the permutations q and the matrices of edges visited y = q π q -1 is difficult to learn. To address this problem in the scratch-pad vector we learned three groups of channels ϕ = (ϕ 1 , ϕ 2 , m). The last part m is a single channel which we treat as a matrix from which we compute an orthogonal transformation. To achieve this we perform SVD to obtain usv T . We discard s to obtain an orthogonal matrix w = uv T . We use this to transform ϕ 2 . This reordering significantly improves the quality of the tours we learn. We attribute this to providing the network G with the ability to understand how altering q will change y = q π q -1 and hence the cost of a tour. We used a differentiable version of SVD from the PyTorch library [16] . Very occasionally this would fail, in which case we terminated the training and start again. Although rare this was the one source of failure of the network.For asymmetric tours we obtained improved results by making the input x have three channels. The first being the distance matrix and the second the transpose of the distance matrix and the third a matrix that have values of 1 in the upper triangle, 0 along the diagonal and -1 in the low triangle.For convenience the same input was used for symmetric instances, but obviously the transposed distance matrix is equal to the distance matrix. In addition, the scratch-pad vector learnt two matrices ϕ = (ϕ 1 , ϕ 2 , m 1 , m 2 ) from which we constructed two orthogonal matrices w i = u i v T i which we used to apply both column-wise and row-wise transformations w 1 ϕ 2 w T 2 . With these modifications we then trained DT-L on randomly generated instances of TSP using a loss function based on the mean cost of a single edge in the selected tour. The distances were normalized so the maximum edge is 1. The loss function can be stated asL tour = 1 N ij î (x ij -1) • y ξ ij ó (B5)where ξ ≥ 1 is a hyperparameter that pushes values not equal to 1 closer to zero, thus preventing solutions with fractional edges.For different widths w, we scale the channels of the convolutional layers in H (output module) as follows:EQUATIONThis ensures consistency with the w = 400 prefix sums models in [2] . For w = 32, this results in output channels of 32, 16, and 2.For different widths w, we scale the channels of the convolutional layers in H (output module) as follows:Layer Input Channels Output Channels Unless specified otherwise:• All models use the Adam optimizer [12] with a learning rate of 0.001, β 1 = 0.9, β 2 = 0.999, weight decay set to 0.0002 and only applied to unconstrained convolutional weights; • incremental progress training with α = 0.5;• exponential warmup with a warmup period of 3; • a multi-step learning rate scheduler where milestones are calculated as a 8 : 4 : 2 : 1 ratio of the total number of epochs, with learning rates multiplied by 0.1 at each milestone.As an example, prefix-sums-solving models are trained to 150 epochs. With the given ratio this produces milestones of 80, 120, and 140.For all models, the end-of-epoch state resulting in the best validation score (accuracy for non-TSP problems, loss for TSP) became the final result of training. This is standard practice in training deep learning models.Prefix-sums-solving models were trained on 32-bit prefix sums from the EasyToHard dataset [17] for 150 epochs, shuffled and split into 80% training samples, 20% validation samples. Each batch contained 500 samples.Trained models for ablation studies instead used milestones at a 4 : 2 : 1 ratio of 150 epochs instead.Models were trained with M = 30.Maze-solving models were trained on 17 × 17 mazes from the EasyToHard dataset [17] for 50 epochs, shuffled and split into 80% training samples, 20% validation samples. Each batch contained 50 samples.Models were trained with M = 30.Chess puzzles models were trained on the easiest 600,000 chess instances from the EasyToHard dataset [17] for 120 epochs, with batch sizes of 300 problem instances. Learning rate scheduling followed the same 8 : 4 : 2 : 1 milestone ratio, with a multiplier of 0.1. The dataset was shuffled and split into 80% training samples, 20% validation samples. Each batch contained 300 samples.Models were trained with M = 30.Models trained to produce tours for TSP instead use stochastic gradient descent (SGD) with a learning rate of 0.001, Nesterov momentum of 0.9, and a weight decay of 0.0002 (applied only to unconstrained convolutional weights).The model trained to perform symmetric TSP used IPT with α = 0.5, whereas the model trained to perform asymmetric TSP did not use IPT.Since there is no dataset, we chose To show the training instability in more widths w for the prefix sums DT-R models, Figure D4 shows extended results from Figure 3 . After all experiments had been completed, a modified version of the spectral normalization code was created which caches the normalized weights. This modification gives improved training times. Justification: We claim an improvement to an existing type of model known as a Deep Thinking network as a result of careful analysis of failure cases. Empirically we show that our improved Deep Thinking with Lipschitz Constraints (DT-L) model has better training and extrapolation performance. We also show a theoretical proof of why our proposed changes guarantee convergence of the learned algorithm (and why the earlier approaches did not). Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: Error bars (confidence intervals) are provided where appropriate. Because part of the objective of the paper is to demonstrate the improvement in stability of the models, in some cases we show data from multiple raw runs of the models, thus allowing different cases to be seen.Guidelines:• The answer NA means that the paper does not include experiments. Justification: We have studied the code of ethics and can confirm our research conforms to all guidelines. Our research uses no human participants, and the datasets we experiment with are created artificially to control biases. Our research does not pose any immediate security or safety issues, however in body of the paper we recognise that their are potential broader impacts from the approaches we are building. The approaches we develop in the paper are aimed at being more stable and reliable, whilst also potentially using fewer parameters. As such they are promoting positive environmental impact.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes]Justification: We have included a discussion of potential broader impacts in Section 7. Summarising, whilst this work is at the fundamental principles end of the spectrum, we see many potential applications from a learning machine that can learn iterative algorithms that extrapolate. Whilst the work does not directly have negative societal impact, it is quite conceivable that an application that does could be built using it as the basis.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The model architectures and datasets as presented offer minimal potential for misuse.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: Where we have used existing code or implementations these are properly attributed. The datasets [17] we use are referenced in the paper. The papers that develop model architectures [2, 18] we build upon are referenced in the paper. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [Yes] Justification: Our code and TSP dataset generator will be released on github, and are provided in the supplementary material during review. Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.38th Conference on Neural Information Processing Systems (NeurIPS 2024).Given a convolutional layer with weights shaped (Cout, Cin, n), where n is the number of elements (e.g. the kernel height times width in a2D convolution) we can flatten the weights into a matrix of shape Cout × Cin • n; the spectral norm is the largest singular value of this matrix.Technically these are pseudo-distances as although they are positive they are not necessarily symmetric and are not guaranteed to satisfy the triangular inequality. 
 
 Appendix:  


Decision: **Summary:** This paper presents an enhancement to Deep Thinking networks by introducing Lipschitz constraints, leading to the development of the DT-L model. The key contribution is the imposition of a sub-Lipschitz-1 constraint, which guarantees convergence to a unique solution and addresses stability issues that have plagued previous DT models. The authors demonstrate the robustness of DT-L across several tasks, including the Traveling Salesperson Problem, and provide theoretical and empirical support for their claims.

**Strengths:**
- The paper tackles a significant issue in DT networks—training instability—by proposing a theoretically grounded solution in the form of Lipschitz constraints. This addition provides stability and guarantees convergence, addressing a fundamental problem in iterative algorithm learning.
- The authors conduct thorough experiments across various tasks, including TSP, prefix sums, and maze-solving, demonstrating the versatility and robustness of DT-L.
- The paper is well-written, with a clear narrative that connects the identification of the problem to the proposed solution and its validation through experiments.

**Weaknesses:**
- Technical Contribution: Some reviewers noted that while the application of Lipschitz constraints is effective, it may be seen as a straightforward application of well-known control theory concepts. This perception could limit the perceived novelty of the contribution.
- Performance on TSP: The results on the TSP benchmark are not as impressive as expected, with DT-L performing worse than some baseline methods. The authors provided an explanation, but the performance gap remains a concern.
- Evaluation and Generalization: Although the paper includes several experiments, there are concerns about the generalizability of the results. The tasks tested are somewhat toy-like, and it is unclear how DT-L would perform on more complex real-world tasks.

**Unresolved Issues:**
- Comparison with Baselines: The performance of DT-L on TSP was below expectations, and the authors’ explanation, while reasonable, does not fully resolve the concern. A more thorough comparison with DT and DT-R on TSP would strengthen the evaluation.
- Broader Impact: The paper’s focus on stability and convergence is valuable, but the broader impact on more diverse and real-world tasks is not fully explored. Further exploration in future work could address this limitation.

**Conclusion:** The paper provides a significant contribution to the field of iterative algorithm learning by enhancing the stability and convergence of DT networks through Lipschitz constraints. Despite some concerns about the novelty and generalization of the approach, the theoretical guarantees and robust empirical results make this a valuable addition to the literature. The paper is recommended for acceptance, with the expectation that future work will address the unresolved issues and explore broader applications of the proposed method.

Reviews: review: paper_summary: paper_summary: The paper introduces Deep Thinking with Lipschitz Constraints (DT-L), an improved version of the Deep Thinking (DT) networks, designed to enhance the stability and performance of iterative algorithm learning models. The authors address the instability issues inherent in DT networks by analyzing intermediate representation growth and applying Lipschitz constraints. The DT-L model guarantees convergence to a unique solution and demonstrates robustness in learning algorithms that extrapolate to more complex problems. The paper furthermore benchmarks DT-L on the Traveling Salesperson Problem (TSP) as well other than the datasets used in the Deep Thinking models. It compares its performance against existing DT models.
strength_weakness: strength_weakness: - The modifications and theoretical underpinnings of the DT-L model, such as the Lipschitz constraints and orthogonal transformations, add complexity to the model, which might hinder its adoption and understanding by a broader audience.
- While the DT-L model shows improvement, its performance on the TSP is not impressive, indicating room for further optimization and refinement.
questions: questions: - How does the introduction of Lipschitz constraints impact the computational complexity and training time of the DT-L model compared to traditional DT models?
- Can the proposed DT-L model be extended to other types of iterative algorithms beyond the ones tested in this paper? If so, what modifications would be necessary?
- Can this applied for transformer architectures like looped transformers?
- Can the insights gained from this work be applied to improve the interpretability of the learned algorithms, making the decision-making process of the DT-L model more transparent?
limitations: limitations: None
paper_summary: paper_summary: The paper addresses the positive feedback issue in the so called Deep Thinking networks, where the inference computation may involve more recurrent computations than encountered in training.  The proposed solution is to normalise the state vector that undergoes the recurrence, i.e. make the mapping contractive, i.e. ensure negative (but just) feedback.
strength_weakness: strength_weakness: As far as I can tell, it is pretty straight forward control theory stuff for addressing positive feedback.  Nothing wrong with the proposed solution, but I would assume this is such a fundamentally well known issue in any recurrent/feedback system that we can leave this to be addressed by the designer at implementation time with any choice of normalisation.  It is somewhat disappointing that with the proposed method there is still the need for batch normalisation.
questions: questions: Does batch normalisation alone not do a good job of stabilising the feedback?
limitations: limitations: If I understand this correctly, the proposed normalisation creates vanishing gradient problem, but authors seem to be aware of this and address it by keeping the spectral norm close to 1.
paper_summary: paper_summary: This paper identifies and rectifies an issue with a particular type of iterative neural network called Deep Thinking Networks. The problem arises in exploding latent representations and unstable training routines. The authors of this work propose an update to the architecture where they add Lipschitz constraints to the model. They show three major benefits: (I) The models train more stably/predictably; (II) the inference-time behavior is better as the latent representations converge with iterations of the recurrent model; and (III) this new approach can learn how to solve NP-Hard problems where the old methods fail.
strength_weakness: strength_weakness: 1. Clarity: A couple things could be more clear.  
  i. I think IPT stands for Incremental Progress Training, but I don't see the acronym defined anywhere.  
  ii. Table 1 the units are unclear. I gather there are tour lengths, but that isn't stated in the table or the caption.  
  iii. The violin plot in Figure 2 is hard to parse (no harder than any other violin plot). This type of graphic does look nice, but offers little quantitative context. For example, there is no indication of the units/scale of the width of each violin. This is not the right type of plot for a conference paper.
questions: questions: 1. Can the authors make the clarifications needed to address my first two points in the Weaknesses section?
1. Have the authors looked at transformer architectures at all? I'm not asking for results to be added to the paper, but I'm curious about how these techniques, which are independent from the parameterization of any given layer in some ways, might apply to modern large model architectures.
limitations: limitations: Yes, the limitations are adequately addressed.
paper_summary: paper_summary: To solve the stability of Deep Thinking models, this paper proposes to constrain activation functions to be Lipshitz-1 functions. The original DT and DT-R models have training stability problem, basically because of scale explosion or vanishing. The authors revealed the stability problem, attribute the problem to Lipschitz constants, proposed ways to ensure Lipschitz smoothness, and show the effectiveness of their approach through a few examples used in the original DT paper, as well as include the traveling salesman problem.
strength_weakness: strength_weakness: * The idea is quite straight-forward (may not be a bad thing, but make technical contributions smaller)
* In the TSP problems, DT-L's results seem worse than NN Tours and BNN Tours. At least some explanation is warranted. 
* I'm not fully convinced by the significance of this paper. The examples shown in the paper are quite toy. Are there more examples you expect DT-L would work?
* I'd appreciate more visualizations that can intuitively show the benefits of DT-L over DT/DT-R? Maybe some Figures like in the original DT paper. 
* The title is not very informative. Might be better to mention Lipschitz smoothness in the title.
questions: questions: * In Line 141-142, I don't quite get this comment "Although any Lipschitz constant less than 1 would guarantee convergence, the nature of the problem solving mechanism we seek to learn intuitively means that we do not want fast convergence." Why don't we want faster convergence.
* In Figure 6 left, it looks like DT-L is worse than DT-R? Why is that? More stability leads to worse performance?
* What about DT and DT-R for TSP?
limitations: limitations: The authors cleraly addresses limitations.

Comments: title: Response to authors
Response to authors
comment: Thank you for addressing my points. I'll maintain my score.
Thanks for answering my questions, and the clarification of where batch norm fits in the proposed solution.  And as a result I grant that this work should be judged more on the way it tackles the straight forward/obvious approach (so that the model is stable and still capable of learning) as opposed to the fact that it uses the obvious approach...  and so I am raising my score to 6.
Thanks for addressing my concerns, I'll raise my score to 6.