Many recent works use machine learning models to solve various complex
algorithmic problems. However, these models attempt to reach a solution without
considering the problem's required computational complexity, which can be
detrimental to their ability to solve it correctly. In this work we investigate
the effect of computational time and memory on generalization of implicit
algorithmic solvers. To do so, we focus on the Differentiable Neural Computer
(DNC), a general problem solver that also lets us reason directly about its
usage of time and memory. In this work, we argue that the number of planning
steps the model is allowed to take, which we call "planning budget", is a
constraint that can cause the model to generalize poorly and hurt its ability
to fully utilize its external memory. We evaluate our method on Graph Shortest
Path, Convex Hull, Graph MinCut and Associative Recall, and show how the
planning budget can drastically change the behavior of the learned algorithm,
in terms of learned time complexity, training time, stability and
generalization to inputs larger than those seen during training.

研究机器学习模型在解决复杂算法问题时忽视所需计算复杂度对其正确解决问题的影响，讨论了计算时间和内存对隐式算法求解器泛化的影响，通过研究不同可规划步骤数的模型，即规划预算，发现规划预算约束可能导致模型泛化能力差，且降低其对外部内存的充分利用。通过在图的最短路径、凸包、图的最小割和关联召回等方面进行评估，展示了规划预算对学习算法的行为，如学习时间复杂度、训练时间、稳定性以及对大于训练集的输入进行泛化的影响。