Algorithm Design for Learned Algorithms

1. The paper primarily focuses on the empirical study of an existing approach. While this is an interesting direction in general and the finding that the hyperparameter μ can be used to control the accuracy vs. efficiency tradeoff is indeed valuable, in my opinion, I believe the amount of analysis performed is a little bit low and leaves room for deeper analysis. One could answer many more interesting questions even when only considering the μ hyperparameter. For instance, does it exert varying degrees of influence on different problems? How does it need to be configured to achieve a certain threshold of performance? Moreover, it would be interesting to investigate whether there exists an upper limit beyond which the algorithm's performance does not improve further but merely demands additional computational resources. If such a limit exists, how can it be identified?

2. The experiments mainly focus on relatively simple problems like prefix sums and mazes as test cases. While the experiment on SAT problems shows the adaptability of learned algorithms to NP-Hard problems, the scalability and efficiency of these methods on larger, more complex instances should be thoroughly discussed. Additionally, the number of problems studied could be expanded to achieve a more comprehensive understanding.

3. The paper does only provide very superficial comparisons with existing traditional algorithms for the problems considered. Understanding in more detail how the learned algorithms perform relative to traditional methods would provide more context for their utility. In particular, one could conduct comprehensive quantitative comparisons between the algorithms learned by DT networks and traditional algorithms. Evaluating performance metrics such as execution time, solution quality, and resource usage across various problem instances would help in objectively assessing the strengths and weaknesses of the learned algorithms. Furthermore, it would be possible to perform a qualitative analysis to compare the behavioral patterns of DT network-learned algorithms with those of existing algorithms. Investigating the possibility of using the μ hyperparameter to transition between different existing algorithms would also be interesting.

4. In the abstract and introduction, the authors state that they explore how hyperparameters influence the behavior of the algorithms. However, in practice, only the influence of one single hyperparameter is explored. It would be interesting for the reader how other hyperparameters were set, as well as how they influence the accuracy vs. efficiency tradeoff. Furthermore, it would be interesting to study the importances of hyperparameters, e.g. utilizing fAVONA [Hutter et al., 2014] or Local Parameter Importance [Biedenkapp et al., 2018], as well as the dependencies between hyperparameters. The authors should at least clarify that they only analyze a single hyperparameter.

5. Limitations of the experimental setup and resulting findings are not discussed.

Overall, all of the weaknesses above can be summarized under the umbrella that the amount of analysis performed is not enough for such a paper from my perspective.

[Hutter et al., 2014] Hutter, F., H. Hoos, and K. Leyton-Brown (2014). “An Efficient Approach for Assessing Hyperparameter Importance”. In: Proc. of ICML’14, pp. 754–762. [Biedenkapp et al., 2018] A. Biedenkapp, J. Marben, M. Lindauer, and F. Hutter. CAVE: Configuration assessment, visualization and evaluation. In R. Battiti, M. Brunato, I. Kotsireas, and P. Pardalos, editors, Proceedings of the International Conference on Learning and Intelligent Optimization (LION), Lecture Notes in Computer Science. Springer, 2018.

• Significance. The work focuses entirely on one specific instantiation of a recurrent architecture, the deep thinking network, rather than studying (or even acknowledging) the existence of a far larger class of recurrent models that share very similar design principles, such as (e.g. deep equilibrium networks [1,2]). Are any of the observations presented in this paper generalizable to these closely related class of models? Is there something specific in the architecture/training of DTN that elicits any of behavior shown in the work? As it stands, the research community targeted by this paper looks rather narrow.
• Even beside this concern, the paper essentially focuses on the number of recurrence steps during training, which has been studied before in various settings (e.g. rate of convergence). These studies should be at the very least mentioned, and the authors should clearly explain what is their work adding to literature.
• Closely related to this, there is only one task (SAT) that has not been addressed before, limiting the originality of the work.
• Clarity. Although the storytelling of this work is compelling, the quantity and quality of the details is lacking. This lack of essential details makes it difficult to assess the rigorousness of the work and to move past anecdotal examples. Here's a few precise points on this line:
  • The model/ learning algorithm under analysis is not precisely explained. What is the functional form of the model? What is the learning algorithm? Is the model trained with a fixed-point algorithm, with iterative differentiation, Neumann series, ... ? Are there any constraints in the model output (such as maze path should be connected)? For me this a general requirement, but considering that the DTN is not a widely adopted architecture, it is even more pressing.
  • The single tasks are not well explained. What are the models optimized for in the three settings? What is a formal description of the task? I find especially the one of cumulative sum particularly hard to interpret (how should I read he figures? Is this binary cumulative sum?). Even if the reader can guess, I think the exposition and quality of work would greatly benefit from a more precise introduction of each task, including expected behavior and description of the known algorithms for each task.
  • Caption around figures is lacking. For instance, do Fig 5 to 8 and Fig 10 show behavior of a specific test point, average over test set, ...? Note that for all three presented tasks, in principle it seems to me that it makes sense to define an "inter-example accuracy" (i.e. what's the correct portion of the maze found up to that iteration. If these plots are showing averages (or some other statistics) computed over an entire test set, then I would suggest the authors to report also a measure of spread (e.g. standard deviation, min-max intervals or confidence intervals).
• The work does not disentangle the effect of the architecture and the learning algorithm.
• Claims regarding interpretability are not well supported. For instance, in the maze task, I do not recognize (visually) any particular behavior from the images in Fig 1/2/3. What should the reader looking for? Can the authors present or attempt to sketch a more formal proof of the behavior (dead-end filling) that they claim the model is implementing? This also includes formalizing the 'dead-end filling' "target" algorithm.
• The work misses a discussion of the limitation of the study.

Typo: Caption fig 4. repeated prefix sums

References [1] Bai, S., Kolter, J. Z., and Koltun, V. Deep equilibrium models. In Advances in Neural Information Processing Systems, pp. 688–699, 2019. [2] Grazzi, Riccardo, et al. "On the iteration complexity of hypergradient computation." International Conference on Machine Learning. PMLR, 2020.

This paper is incomplete

The paper lacks rigor and the entirety of section 2 feels hand wavy. I don't understand why I should be convinced that the model learns dead-end filling by observing just three figures. Also, what do to the authors mean by "search algorithm" in this section? The authors claim that the models are extremely interpretable, yet they are forced to use a vague and general name like "search algorithm" to describe what the model is doing?

In Section 3.1 What is the Prefix Sum algorithm? What are you'll trying to solve? What is the model trained on? Prefix sums of what?

Also the result is trivial? For instance. If it takes $\Omega(N)$ to solve a problem, but you give your algorithm only $\O(1)$ steps to solve it, naturally the accuracy of the algorithm will be lower?

The output format of the SAT problem is not described in Section 4.

Lack of Rigorous Comparison with State-of-the-Art Methods The paper's most glaring weakness is its absence of rigorous comparative analyses with state-of-the-art methods, especially those that solve NP-Hard problems like SAT. Without such a comparison, it is challenging to gauge the true efficacy and novelty of the Deep Thinking Networks (DT-Nets) introduced. The paper mentions existing works like those of Selsam (2019) and Wang et al. (2019a, 2019b, 2021), but does not benchmark the performance of DT-Nets against these or other contemporary models, neither in terms of speed nor accuracy.

Lack of Mathematical Formalism For a paper that delves into algorithmic reasoning and neural networks' ability to approximate solvers for complex problems, there is a surprising lack of mathematical rigor. While the paper does describe the architecture and training routines, it does not provide the underlying mathematical model or theorems that could prove the DT-Nets' efficacy or limitations. Given the problem's complexity, a robust mathematical foundation would have strengthened the paper's claims.

Unclear Definition and Utility of Hyperparameter μ The paper discusses the impact of the hyperparameter μ extensively, but it does not sufficiently explain its mathematical or algorithmic significance. While the authors argue that μ allows for a trade-off between speed and accuracy, no empirical evidence supports this claim. There are no clear guidelines or proofs to suggest how μ should be optimally set for different problems or why it is effective.

Limited Variation in Hyperparameters: The paper seems to focus predominantly on the impact of the hyperparameter μ in the SAT models. Although μ is indeed an important factor, other hyperparameters such as learning rate, batch size, and width have been given limited attention. This lack of comprehensive hyperparameter tuning could limit the generalizability of the results.

Unaddressed Multicollinearity: The paper does not discuss the potential interplay between μ and other hyperparameters. This could introduce multicollinearity into the analysis, which would complicate the interpretation of the results.

Incomplete Analysis on "Overthinking" The paper introduces the concept of "overthinking" but does not delve deep into its theoretical implications or causes. While it is an interesting observation that the model's accuracy declines after a certain point, a more in-depth analysis or mathematical model to capture this phenomenon would have been beneficial.

Limited Scope of Tested Problems The paper primarily focuses on prefix sums and maze-solving for experimentation. Although these are computationally interesting problems, they are not sufficiently complex to substantiate the paper’s claims about DT-Nets’ applicability to NP-Hard problems. A broader range of test cases would have provided more robust validation of the proposed approach.

Generalizability and Scalability The paper claims that the lessons learned from simpler problems like prefix sums and maze-solving can be applied to more complex problems like SAT. However, it does not provide sufficient empirical evidence to substantiate this claim. The scalability of DT-Nets to more complex or larger problems remains unclear.

Ambiguity in Algorithmic Framework: The paper discusses "Deep Thinking models" and their application to SAT problems but fails to provide a clear mathematical formulation or algorithmic outline for these models.

Over-Reliance on Figures: The paper heavily relies on visual representations, such as Figures 10, 11, and 12, for justifying its claims. However, these figures are not accompanied by statistical tests to validate their significance.

Clarity and Precision: Figures like 15, 16, and 17 could benefit from more explicit annotations or captions to aid in understanding what specifically the reader should deduce from them.

Limited Scope: The discussion section is quite generic and does not delve into specific limitations or practical challenges that might arise when applying the Deep Thinking framework to SAT or other NP-Hard problems.

Lack of Novelty: While the paper discusses the potential of Deep Thinking models for SAT problems, it does not articulate how this approach is significantly better or different from existing methods in terms of computational complexity or accuracy. Lack of Comparative Analysis: The paper does not compare its methodology with state-of-the-art approaches in any metric, making it difficult to assess its contribution objectively.

Silence on Computational Overheads: While the paper discusses the neural algorithmic space for NP-Hard problems, it fails to address the computational overheads involved, which is crucial for comparison with existing algorithms.