On the Bounds of Function Approximations
This work addresses the computational challenges in NAS for machine learning researchers, offering a theoretical foundation to guide more efficient search strategies, though it is incremental as it builds on existing NAS concepts.
The paper tackles the computational intractability of Neural Architecture Search (NAS) by establishing a formal framework to understand its computational bounds relative to the search space, showing that solving the Function Approximation problem exactly is infeasible but minimal error is achievable with specific function classes, and proposing a polynomial-time approach called a-ASP that can match exhaustive search under certain conditions.
Within machine learning, the subfield of Neural Architecture Search (NAS) has recently garnered research attention due to its ability to improve upon human-designed models. However, the computational requirements for finding an exact solution to this problem are often intractable, and the design of the search space still requires manual intervention. In this paper we attempt to establish a formalized framework from which we can better understand the computational bounds of NAS in relation to its search space. For this, we first reformulate the function approximation problem in terms of sequences of functions, and we call it the Function Approximation (FA) problem; then we show that it is computationally infeasible to devise a procedure that solves FA for all functions to zero error, regardless of the search space. We show also that such error will be minimal if a specific class of functions is present in the search space. Subsequently, we show that machine learning as a mathematical problem is a solution strategy for FA, albeit not an effective one, and further describe a stronger version of this approach: the Approximate Architectural Search Problem (a-ASP), which is the mathematical equivalent of NAS. We leverage the framework from this paper and results from the literature to describe the conditions under which a-ASP can potentially solve FA as well as an exhaustive search, but in polynomial time.