Pith. sign in

REVIEW 4 major objections 4 minor 60 references

On the Bounds of Function Approximations

T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that no computable procedure can approximate every continuous function exactly, and that bounded-length approximation becomes optimal whenever the search space contains the elementary functions of a Turing-complete model.

desk verdict A well-intended reformulation of NAS as function approximation, but Theorem 2 doesn't prove what it claims and the polynomial-time a-ASP result never follows—treat it as an interesting failed attempt, not a usable theory. read the letter →

arxiv 1908.09942 v1 pith:QXJOTVVK submitted 2019-08-26 cs.LG cs.CCcs.NEstat.ML

Adrian de Wynter This is my paper · ORCID
classification cs.LGcs.CCcs.NEstat.ML
keywords functionapproximationneuralarchitecturesearchspacecomputabilityTuringequivalenceinformationpotentialmachinelearningtheoryproblem
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to give automated architecture search a theoretical foundation by recasting function approximation as a search problem: given a target function $F$, a search space $S$, a length bound $n$, and sample points $\sigma$, find the sequence of functions from $S$, of length at most $n$, whose average error to $F$ is smallest. It argues that no computable procedure can solve this problem exactly for all continuous real-valued functions, but that a globally minimal error is achievable for each $F$ if $S$ contains the elementary functions of a Turing-complete model. The paper then classifies machine learning, exhaustive architecture search, and approximate architecture search as solution strategies, concluding that the first is weak, the second is optimal but intractable, and the third can in principle match the second in polynomial time. The reason to care is that these bounds would explain when automated machine learning should work at all and what a search space must contain to be provably good.

What carries the argument

The load-bearing mechanism is the representation of a model as a finite set of elementary functions $E$ together with a composition operation, so that any candidate solution is a sequence $(\varphi_{i_1},\ldots,\varphi_{i_k})$ of length $k \leq n$. The paper defines the approximation error $\varepsilon_\sigma(f,F)$ as the average distance to $F$ on a sample set $\sigma$, the information capacity $C(f)$ of a sequence as the Cartesian product of its domains, parameters, and ranges, and the information potential $U(S,n)$ as the union of $C(f)$ over all sequences of length at most $n$ in $S$. This last quantity is what lets the paper compare search spaces without fixing a target function, and it is the quantity that remains unchanged when moving from exhaustive ASP to approximate a-ASP, supporting the claim that a-ASP can match ASP if $E \subset S$.

What would settle it

Set $n=1$, let $E$ be a finite set whose one-step sequences cannot express $\sin$, and let $S$ contain $E$ but not $\sin$. The sequence $(\sin)$ has zero approximation error to $F=\sin$ and is a computable sequence of length one, yet no member of $S^{\star,1}$ attains zero error, so the optimal sequence promised by Theorem 2 does not exist unless 'computable functions of length up to $n$' is redefined as 'functions expressible from $E$ in at most $n$ steps.'

Watch

Extended reading notes

Core claim

The paper's central claim is threefold. First, the FA problem, which asks for the length-bounded sequence over a search space that minimizes the approximation error to a target, is a faithful reformulation of what automated machine-learning pipelines try to do. Second, Theorem 1 states that no computable procedure can solve FA for all continuous real-valued functions with zero error across the whole domain, because uncomputable targets can only be approximated, and deciding whether a computable target has an exact representation reduces to an undecidable halting-equivalence question. Third, Theorem 2 states that if the search space $S$ contains the finite set $E$ of elementary functions of some Turing-equivalent model, then for every $F$ there exists a sequence in $S^{\star,n}$ whose approximation error is the smallest among all computable sequences of length at most $n$. From these, the paper infers that a fixed architecture makes machine learning a weak FA solver, that exhaustive architecture search is the strongest but intractable solver, and that a pruned approximate version, a-ASP, can solve FA as well as exhaustive search in polynomial time when $E$ is included and the set-builder $B$ is chosen well.

Load-bearing premise

The optimality theorem assumes that the finite set of elementary functions $E$ can generate every computable function using no more than the fixed bound $n$ of composition steps; standard recursion theory gives no such bound, so if this premise fails the theorem's conclusion need not hold.

Editorial extensions

If this is right

  • No automated architecture search system can approximate every continuous function to zero error, so some nonzero error is unavoidable for any fixed finite search budget.
  • Including the elementary functions of the underlying model in the search space is a design principle that guarantees the existence of a best sequence for every target at each length bound.
  • Machine learning with a fixed architecture is inherently weak as a general solver, because a single-function search space cannot tell whether a better architecture exists.
  • Exhaustive architecture search is the strongest solver, but its exponentially growing space makes it unusable in practice.
  • Approximate architecture search can match exhaustive search in polynomial time if its search space contains the elementary functions and its pruning rule respects the information potential.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper leaves the length bound $n$ fixed; an immediate extension is to let $n$ grow with the target's complexity, which would connect the framework to resource-bounded Kolmogorov complexity and program synthesis.
  • The information potential $U(S,n)$ is a new capacity measure distinct from VC dimension; a testable extension would be to compute $U$ for standard cell-based NAS search spaces and compare it with observed search difficulty.
  • Because the paper sets aside data selection, a natural next step is to study how the sample subset $\sigma$ controls the achievable error; a minimax analysis over $\sigma$ could turn the framework into a theory of data-efficient architecture search.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper proposes a formal framework, the Function Approximation (FA) problem, in which approximating an input function F is recast as selecting a sequence of functions from a search space S of length at most n. It claims Theorem 1 (no computable FA procedure can approximate all continuous real-valued functions to zero error over their entire domain), Theorem 2 (if S contains the elementary functions E of a Turing-equivalent model, then for any input F there is an optimal sequence among all computable functions of length at most n), and it introduces ML, ASP, and a-ASP as solution strategies, claiming that a-ASP can potentially solve FA as well as an exhaustive search but in polynomial time. The paper is a theoretical analysis aiming to formalize Neural Architecture Search in a model-agnostic way.

Significance. If the claims were correct, the paper would provide a useful unifying vocabulary for NAS and automated machine learning; the reformulation of architecture search as sequence selection and the explicit connection to models of computation are attractive. The paper engages seriously with relevant literature, including no-free-lunch theorems, PAC learning, and universal approximation results, and it attempts to define search-space capacity through the information potential. However, the central theorems are not supported by the proofs as written: Theorem 1's proof is heuristic, and Theorem 2's conclusion is either trivial or rests on a false fixed-length generation premise. The a-ASP polynomial-time claim is not derived. The conceptual framework may be a seed for future work, but the paper's load-bearing formal results are not established.

major comments (4)
  1. [Section 3.2, Theorem 1] The proof does not establish the theorem. The reduction to the equivalence problem of halting Turing machines is asserted without construction: given an FA instance with particular F, S, n, and sigma, it is not shown how deciding zero-error approximability would encode equivalence of two halting TMs. The cardinality remarks about finite n, sigma, or S show only that a restricted procedure cannot cover all inputs, not that no procedure can; and the treatment of uncomputable F is not a computational lower bound, since it is unclear how an uncomputable function is presented as input. Moreover, Eq. (1) defines epsilon_sigma only as a finite average, while Theorem 1 quantifies over the entire domain, which may be infinite; the statement is therefore not well-formed for general continuous functions.
  2. [Section 3.3, Theorem 2 and Eq. (4)] Theorem 2 is not proven as stated. The premise that E can generate all possible computable functions is a statement about unbounded composition, whereas the conclusion concerns sequences of length at most a fixed finite n. For any finite n, E^{*,n} is finite, while the set of total computable functions is countably infinite, so E^{*,n} cannot contain all computable functions. If 'smallest approximation error among all possible computable functions of sequence length up to and including n' means the minimum over the finite set S^{*,n} only, then the theorem is a trivial consequence of finiteness and the condition E⊂S plays no role. If it means a global optimum over all computable functions representable in at most n steps, the premise is false. The proof's cardinality claim that E⊄S implies |S^{*,n}|<|E^{*,n}| does not imply that an optimal sequence for a given F is missing, and the paper's own limit statement in Eq. (4) only gives U(S,n)→R as n→∞. This theorem is the central result supporting the later claims about ASP and a-ASP.
  3. [Section 4.2, a-ASP] The abstract and conclusion claim that a-ASP 'can potentially solve FA as well as an exhaustive search, but in polynomial time', but no such result is proved. The set-builder function B is defined only by B(S)⊂S^{*,n}; no complexity constraint is imposed on B, and no argument shows that any B can select the optimal sequence without examining the whole space. Section 4.2 states only that a-ASP 'could have' the ability to perform as well as ASP 'by including E', and the conclusion says that existing literature 'complemented with the results from this framework' shows this ability; neither the conditions promised in the abstract nor a polynomial-time bound is stated or derived. The reference to [56] is an appeal to prior results, not a derivation within the framework.
  4. [Sections 3.1 and 3.2, Definitions 1-4] The formal apparatus is not precise enough to support the theorems. Eq. (1) defines epsilon_sigma via a sum over sigma, but sigma is later allowed to be an arbitrary subset of the domain, and Theorem 1 quantifies over the entire domain; no integral or measure is supplied for infinite sigma. The convention d(f(x),g(x))=g(x) for x not in dom(f) is inconsistent because d is required to take values in R_{\ge 0}, whereas g(x) need not be nonnegative. In Definition 3, C(f) is a Cartesian product involving domains and images that are arbitrary sets, so it is not a well-defined quantitative capacity, and the comparison U(S1,n)=U(S2,n) as set equality in Definition 4 is asserted without a metric or measure. These imprecisions make it difficult to verify the claimed bounds.
minor comments (4)
  1. [Section 3.1] The definition S^{*,n} = {(\phi_i)_{i=1}^k | \phi_i \in S, k \le n} and the assertion 'f \in S^{*,n} \Leftrightarrow f \in R' are not meaningful without specifying the distinction between a sequence and the function it computes; this should be clarified.
  2. [Section 3.2, Definition 1] The phrase 'the approximation error of a function f to a function g is a procedure which outputs 0 if ...' conflates a numeric value with a procedure; Eq. (1) defines a value, not a procedure, so the wording should be aligned.
  3. [Section 3.1 and 3.3] The paper says it will consider continuous, real-valued functions and then, beginning in Section 3.3, only computable functions; the relationship between these restrictions should be stated explicitly, since not all continuous functions are computable.
  4. [Throughout] There are several typographical and referencing issues: the citation line contains a stray 'with', the set notation in Section 4.2 for the sequence of errors is malformed, and some references are cited only in the text without appearing in the bibliography in a consistent format.

Circularity Check

3 steps flagged · score 7.0 of 10

Theorem 2 and the a-ASP parity claim reduce to the defining property of E; only Theorem 1's impossibility result and the ML/ASP framing have independent content.

  1. self definitional [Section 3.3, Theorem 2 and proof]
    "Proof. By definition, E can generate all possible computable functions. If E ⊄ S, then |S⋆,n| < |E⋆,n|, and so there exist input functions whose sequence with the smallest approximation error, fo, is not contained in S⋆,n."

    E was defined in Section 3.1 as 'the smallest class of functions, along with their operators, of some Turing-equivalent model of computation'—i.e., as the generator of all computable functions by definition. The theorem's conclusion that some fo ∈ S^{*,n} is optimal among 'all possible computable functions of sequence length up to and including n' is obtained solely by taking that defining property and using E ⊂ S to embed E^{*,n} in S^{*,n}. No argument shows that every computable function of length ≤ n is generated by E at that same bounded length; indeed for finite n, E^{*,n} is finite while the set of total computable functions is countably infinite.

  2. self definitional [Section 3.3, Equation (4)]
    "For a given space S, as the sequence length n grows to infinity, and if the search space includes the set of elementary functions, E ⊂ S, its information potential encompasses all computable functions: lim n→∞ U(S,n) = R (4)"

    This limit is not derived; it is Definition 4 evaluated under the defining property of E. Since U(S,n) is the union of the information capacities of all sequences of length ≤ n, and E is defined as the elementary functions of a Turing-equivalent model of computation, allowing n → ∞ with E ⊂ S makes U(S,n) equal to R by construction. Equation (4) restates the classical fact that the elementary functions of a Turing-equivalent model generate all computable functions, but in the new vocabulary of information potentials. It is therefore a definitional equivalence rather than a prediction, and it is later used as the bridge from ASP to a-ASP.

1 more flagged steps
  1. other [Section 4.2, final paragraph]
    "It can be seen that these design choices are not necessarily problem-dependent, and, from the results of Theorem 2, they can be done in a theoretically motivated manner. Specifically, we note that the information potential of the search space remains unchanged between a-ASP and ASP, and so, by including E, a-ASP could have the ability to perform as well as ASP."

    This is the abstract's advertised prediction—that a-ASP can solve FA as well as exhaustive search—and its justification is 'from the results of Theorem 2' together with an asserted invariance of U(S,n). Both premises are the definitional moves flagged above: the invariance is asserted by inspection (and is not reconciled with Definition 7, where the search is over B(S_{ASP}) ⊂ S^{*,n}), and Theorem 2's optimality is just E's defining property. The conditions promised in the abstract are never enumerated; the only sufficient condition offered is 'by including E', which already encodes the ability to represent all computable functions. Thus the parity claim adds no independent content beyond the definition of E and an unproved assumption about the set-builder B.

full rationale

This is a theoretical paper with no fitted parameters or external benchmarks, and it contains no self-citations, so the self-citation and fitted-input patterns are not applicable. Theorem 1 is an independent result: it uses the standard undecidability of equivalence of halting Turing machines to show that no procedure solves FA with zero error for all functions; that part does not reduce to the paper's definitions. The ML-as-singleton-search-space analysis is also a legitimate reformulation. However, the paper's central optimality claim, Theorem 2, is self-definitional: E is defined as the generator of all computable functions, and the proof simply invokes that definition to assert the existence of an optimal sequence in S^{*,n}. The later claim that a-ASP can match ASP 'by including E' inherits this definitional move and is additionally asserted rather than derived—the promised conditions are never stated. I therefore flag the derivation chain as substantially circular, while acknowledging that the paper does contain an independent impossibility theorem and a coherent reformulation exercise. The score of 7 reflects a central result forced by definition, with partial independent content remaining elsewhere.

Assumptions & free parameters 0 free parameters · 5 assumptions · 2 invented entities

The central claims rest on a small set of definitions and external theorems. No free parameters are fitted to data. The main hidden assumption is the treatment of the elementary functions E as generating all computable functions within a bounded sequence length, which is not true in standard recursion theory.

assumptions (5)
  • standard math ZFC set theory
    The paper explicitly states it works in Zermelo-Fraenkel set theory with the Axiom of Choice (Section 3.1).
  • ad hoc to paper There exists a finite set of elementary functions E that generates all computable functions
    Defined in Section 3.1 as the smallest class of functions of some Turing-equivalent model; used in Theorem 2 as though generation within a bounded length is guaranteed, which is not standard.
  • domain assumption The analysis is restricted to continuous, real-valued, and eventually computable functions
    Stated in Sections 3.1 and 3.3; limits the scope of the theorems.
  • standard math Equivalence of two halting Turing machines is undecidable
    Used to prove Theorem 1; a classical result.
  • standard math No-free-lunch and coevolutionary free-lunch results of Wolpert and Macready
    Cited as external justification for the behavior of set builder functions in a-ASP (Sections 2 and 4.2).
invented entities (2)
  • Set builder function B
    purpose: Selects a nonempty subset of the search space to make a-ASP computationally tractable
    No construction or conditions for B are given; the claim that it can let a-ASP match exhaustive search is unsupported.
  • Information potential U(S,n)
    purpose: Measures the expressiveness of a search space across sequences of length n
    A new measure introduced in the paper; the claimed limit towards R is asserted without a rigorous proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Bounds of Function Approximations." pith.science (2026). https://pith.science/paper/QXJOTVVK

@misc{pith2026190809942,
  author       = {Pith},
  title        = {Pith review of: On the Bounds of Function Approximations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QXJOTVVK}},
  note         = {Machine review of arXiv:1908.09942}
}
read the original abstract

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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

60 extracted references · 39 canonical work pages

  1. [56]

    IEEE Transactions on Evolutionary Computation 9, 721–735 (2005)

    Wolpert, D.H., Macready, W.G.: Coevolutionary free lun ches. IEEE Transactions on Evolutionary Computation 9, 721–735 (2005). https://doi.org/10.1109/TEVC.2005.856205

    work page arXiv 2005

  2. [1]

    Angeline, P.J., Saunders, G.M., Pollack, J.B.: An evolut ionary algorithm that constructs recurrent neural networks. Trans. Neur. Netw. 5(1), 54–65 (1994). https://doi.org/10.1109/72.265960

    work page doi:10.1109/72.265960 1994

  3. [2]

    In: Proceedings of the 4th European Conference on Computational Learning Theory

    Bartlett, P.L., Ben-David, S.: Hardness results for neur al network approximation problems. In: Proceedings of the 4th European Conference on Computational Learning Theory. pp. 50–62. EuroCOLT ’99, Springer-Verlag , London, UK, UK (1999). https://doi.org/10.1016/S0304-3975(01)00057-3

    work page doi:10.1016/s0304-3975(01)00057-3 1999

  4. [3]

    Journal of Artificial Intelligence Research 12, 149–198 (2000)

    Baxter, J.: A model of inductive bias learning. Journal of Artificial Intelligence Research 12, 149–198 (2000). https://doi.org/10.1613/jair.731

    doi:10.1613/jair.731 2000

  5. [4]

    A learning problem that is independent of the set theory ZFC axioms

    Ben-David, S., Hrubes, P., Moran, S., Shpilka, A., Yehuda yoff, A.: A learning prob- lem that is independent of the set theory ZFC axioms. CoRR abs/1711.05195 (2017), http://arxiv.org/abs/1711.05195

    work page Pith review arXiv 2017

  6. [5]

    Foundati ons and Trends in Machine Learning 2(1), 1–127 (2009)

    Bengio, Y.: Learning deep architectures for ai. Foundati ons and Trends in Machine Learning 2(1), 1–127 (2009). https://doi.org/10.1561/2200000006

    doi:10.1561/2200000006 2009

  7. [6]

    Journal of the ACM 14(2), 322336 (1967)

    Blum, M.: A machine-independent theory of the complexity of recursive functions. Journal of the ACM 14(2), 322336 (1967). https://doi.org/10.1145/321386.321 395

    work page doi:10.1145/321386.321 1967

  8. [7]

    : Learnability and the vapnik-chervonenkis dimension

    Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.K. : Learnability and the vapnik-chervonenkis dimension. Journal of the Associatio n for Computing Machin- ery 36, 929–965 (1989). https://doi.org/10.1145/76359.76371

    arXiv 1989

Show all 60 references
  1. [8]

    In: Pro- ceedings of the Thirtieth Annual ACM Symposium on Theory of C om- puting

    Bshouty, N.H.: A new composition theorem for learning alg orithms. In: Pro- ceedings of the Thirtieth Annual ACM Symposium on Theory of C om- puting. pp. 583–589. STOC ’98, ACM, New York, NY, USA (1998). https://doi.org/10.1145/258533.258614

    1998

  2. [9]

    Com- puter Vision, Graphics and Image Processing 37, 54–115 (1987)

    Carpenter, G.A., Grossberg, S.: A massively parallel arc hitec- ture for a self-organizing neural pattern recognition mach ine. Com- puter Vision, Graphics and Image Processing 37, 54–115 (1987). https://doi.org/10.1016/S0734-189X(87)80014-2

    1987 doi

  3. [10]

    Neural Comput

    Carvalho, A.R., Ramos, F.M., Chaves, A.A.: Metaheurist ics for the feedforward artificial neural network (ann) architecture optimization problem. Neural Comput. & Aplic. (2010). https://doi.org/10.1007/s00521-010-05 04-3

    2010 doi

  4. [11]

    American Jour- nal of Mathematics 58, 345–363 (1936)

    Church, A.: An unsolvable problem of elementary number t heory. American Jour- nal of Mathematics 58, 345–363 (1936)

    1936

  5. [12]

    Mathematics of Control, Singals, and Systems 2, 303–314 (1989)

    Cybenko, G.: Approximation by superpositions of a sigmo idal func- tion. Mathematics of Control, Singals, and Systems 2, 303–314 (1989). https://doi.org/10.1007/BF02551274

    1989 doi

  6. [13]

    In: Proceedings of the EURASIP Workshop 1990 on Neural Netwo rks

    Cybenko, G.: Complexity theory of neural networks and cl assification problems. In: Proceedings of the EURASIP Workshop 1990 on Neural Netwo rks. pp. 26–44. Springer-Verlag (1990). https://doi.org/10.1007/3-540 -52255-7 25

    1990 doi

  7. [14]

    https://doi.org/10.1007/978-3-030-05318-5 3

    Elsken, T., Metzen, J.H., Hutter, F.: Neural architectu re search: A survey (2019). https://doi.org/10.1007/978-3-030-05318-5 3

    2019 doi

  8. [15]

    In: Cortes, C., Lawrence, N.D., Lee, D.D., Sugiyama, M., Garnett, R

    Feurer, M., Klein, A., Eggensperger, K., Springenberg, J., Blum, M., Hutter, F.: Efficient and robust automated machine learning. In: Cortes, C., Lawrence, N.D., Lee, D.D., Sugiyama, M., Garnett, R. (eds.) Advances in Neur al Information Pro- cessing Systems 28, pp. 2962–2970. C...

    2015

  9. [16]

    Neural Networks 2, 183–192 (1989)

    Funahashi, K.: On the approximate realization of contin uous map- pings by neural networks. Neural Networks 2, 183–192 (1989). https://doi.org/10.1016/0893-6080(89)90003-8 14 A. de Wynter

    1989 doi

  10. [17]

    Neural Computation 7, 219–269 (1995)

    Girosi, F., Jones, M., Poggio, T.: Regularization theor y and neu- ral networks architectures. Neural Computation 7, 219–269 (1995). https://doi.org/10.1162/neco.1995.7.2.219

    1995 doi

  11. [18]

    https://doi.org/10.1145/3097983.3098043

    Golovin, D., Solnik, B., Moitra, S., Kochanski, G., Karr o, J., Scul- ley, D.: Google vizier: A service for black-box optimizatio n (2017). https://doi.org/10.1145/3097983.3098043

    2017

  12. [19]

    MIT Press, Cambridge, MA (2016), http://www.deeplearningbook.org

    Goodfellow, I., Bengio, Y., Courville, A.: Deep Learnin g. MIT Press, Cambridge, MA (2016), http://www.deeplearningbook.org

    2016

  13. [20]

    In: Procee dings of the European Conference on Computer Vision (ECCV)

    He, Y., Lin, J., Liu, Z., Wang, H., Li, L.J., Han, S.: Amc: A utoml for model compression and acceleration on mobile devices. In: Procee dings of the European Conference on Computer Vision (ECCV). pp. 784–800 (2018)

    2018

  14. [21]

    Neural Networks 4, 251–257 (1991)

    Hornik, K.: Approximation capabilities of multilayer f eedforward networks. Neural Networks 4, 251–257 (1991). https://doi.org/10.1016/0893-6080(91 )90009-T

    1991 doi

  15. [22]

    Neural Networks 2, 359–366 (1989)

    Hornik, K., Stinchcombe, M., White, H.: Multilayer feed forward net- works are universal approximators. Neural Networks 2, 359–366 (1989). https://doi.org/10.1016/0893-6080(89)90020-8

    1989 doi

  16. [23]

    Jin, H., Song, Q., Hu, X.: Auto-keras: Efficient neural arc hitecture search with network morphism (2018)

    2018

  17. [24]

    Kolmogorov, A.N.: On the representation of continuous f unctions of several vari- ables by superposition of continuous function of one variab le and addition. Dokl. Akad. Nauk SSSR 114, 953–956 (1957)

    1957

  18. [25]

    Neural Networks 6, 861–867 (1993)

    Leshno, M., Lin, V.Y., Pinkus, A., Shocken, S.: Multilay er feedforward networks with a nonpolynomial activation function can approximate a ny function. Neural Networks 6, 861–867 (1993). https://doi.org/10.1016/S0893-6080(0 5)80131-5

    1993 doi

  19. [26]

    International Conference on Learning Represe ntations (2018)

    Liu, H., Simonyan, K., Yang, Y.: Hierarchical represent ations for efficient architec- ture search. International Conference on Learning Represe ntations (2018)

    2018

  20. [27]

    Inter- national Conference on Learning Representations (2019)

    Liu, H., Simonyan, K., Yang, Y.: Darts: Differentiable ar chitecture search. Inter- national Conference on Learning Representations (2019)

    2019

  21. [28]

    CoRR abs/1905.12600 (2019), https://arxiv.org/pdf/1905.12600v1.pdf

    Long, P.M., Sedghi, H.: Size-free generalization bound s for con- volutional neural networks. CoRR abs/1905.12600 (2019), https://arxiv.org/pdf/1905.12600v1.pdf

    2019 arXiv

  22. [29]

    In: NeurIPS (2018)

    Luo, R., Tian, F., Qin, T., Liu, T.Y.: Neural architectur e optimization. In: NeurIPS (2018)

    2018

  23. [30]

    Miller, G.F., Todd, P.M., Hegde, S.U.: Designing neural networks using genetic algorithms. Proc. 3rd Intl. Conf. Genetic Algorithms and Th eir Applications pp. 379–384 (1989)

    1989

  24. [31]

    S.: Turing universality of neural nets (revisited)

    Neto, J.P., Siegelmann, H.T., Costa, J.F., Araujo, C.P. S.: Turing universality of neural nets (revisited). In: Pichler, F., Moreno-D ´ ıaz, R.(eds.) Computer Aided Sys- tems Theory — EUROCAST’97. pp. 361–366. Springer Berlin Hei delberg, Berlin, Heidelberg (1997). https://doi...

    1997 doi

  25. [32]

    Ojha, V.K., Abraham, A., Sn´ aˇ sel, V.: Metaheuristic de sign of feedforward neural networks: A review of two decades of research. Eng. Appl. Art if. Intell. 60(C), 97–116 (2017). https://doi.org/10.1016/j.engappai.201 7.01.013

    2017 doi

  26. [33]

    Nordic J

    Orponen, P.: Computational complexity of neural networ ks: A survey. Nordic J. of Computing 1(1), 94–110 (1994)

    1994

  27. [34]

    Bulletin of the American Mathematical Society 71, 619622 (1965)

    Ostrand, P.A.: Dimension of metric spaces and hilbert’s problem 13. Bulletin of the American Mathematical Society 71, 619622 (1965). https://doi.org/10.1090/S0002-9904-1965-11363-5

    1965 doi

  28. [35]

    Neural Computation 3, 246–257 (1991)

    Park, J., Sandberg, I.W.: Universal approximation usin g radial- basis-function networks. Neural Computation 3, 246–257 (1991). https://doi.org/10.1162/neco.1991.3.2.246 On the Bounds of Function Approximations 15

    1991 doi

  29. [36]

    In: Dy, J., Krause, A

    Pham, H., Guan, M., Zoph, B., Le, Q., Dean, J.: Efficient neu ral architecture search via parameters sharing. In: Dy, J., Krause, A. (eds.) Proceedings of the 35th International Conference on Machine Learning. Proceeding s of Machine Learning Research, vol. 80, pp. 4095–4104. PM...

    2018

  30. [37]

    Poggio, T., Girosi, F.: A theory of networks for approxim ation and learning. A.I. Memo No. 1140 (1989)

    1989

  31. [38]

    Proceedings of the IEEE 78(9) (1990)

    Poggio, T., Girosi, F.: Networks for approximation and l earning. Proceedings of the IEEE 78(9) (1990). https://doi.org/10.1109/5.58326

    1990 doi

  32. [39]

    Rabin, M.O.: Computable algebra, general theory and the ory of computable fields. Trans. Amer. Math. Soc. 95, 341–360 (1960). https://doi.org/10.1090/S0002-9947-1960-0113807-4

    1960 doi

  33. [40]

    In: Proceeding s of the 34 th International Conference on Machine Learning (2017)

    Real, E., Moore, S., Selle, A., Saxena, S., Suematsu, Y.L ., Le, Q.V., Kurakin, A.: Large-scale evolution of image classifiers. In: Proceeding s of the 34 th International Conference on Machine Learning (2017)

    2017

  34. [41]

    MIT Press, Cambridge, MA (1987)

    Rogers, Jr., H.: The Theory of Recursive Functions and Eff ective Computability. MIT Press, Cambridge, MA (1987)

    1987

  35. [42]

    In: Proceedings of the 16 th International Conference on Artificial Neu- ral Networks - Volume Part I

    Sch¨ afer, A.M., Zimmermann, H.G.: Recurrent neural net works are universal ap- proximators. In: Proceedings of the 16 th International Conference on Artificial Neu- ral Networks - Volume Part I. ICANN’06, vol. 27, pp. 632–640. Springer-Verlag, Berlin, Heidelberg (2006). https:...

    2006 doi

  36. [43]

    Physics D 42(244-248) (1990)

    Schaffer, J.D., Caruana, R.A., Eshelman, L.J.: Using gen etic search to ex- ploit the emergent behavior of neural networks. Physics D 42(244-248) (1990). https://doi.org/10.1016/0167-2789(90)90078-4

    1990 doi

  37. [44]

    arXiv e-prints arXiv:1904.02311 (2019)

    Siegel, J.W., Xu, J.: On the approximation properties of neural networks. arXiv e-prints arXiv:1904.02311 (2019)

    2019 arXiv

  38. [45]

    Siegelmann, H.T., Sontag, E.D.: Turing computability w ith neural nets. vol. 4, pp. 77–80 (1991). https://doi.org/10.1016/0893-9659(91)90 080-F

    1991 doi

  39. [46]

    Siegelmann, H.T., Sontag, E.D.: On the computational po wer of neural nets. J. Comput. Syst. Sci. 50, 132–150 (1995). https://doi.org/10.1006/jcss.1995.10 13

    1995 doi

  40. [47]

    Neural Ne tworks and Machine Learning p

    Sontag, E.D.: Vc dimension of neural networks. Neural Ne tworks and Machine Learning p. 6995 (1998)

    1998

  41. [48]

    Nature Machine Intellig ence 1, 2435 (2019)

    Stanley, K.O., Clune, J., Lehman, J., Miikkulainen, R.: Designing neural networks through evolutionary algorithms. Nature Machine Intellig ence 1, 2435 (2019)

    2019

  42. [49]

    Stanley, K.O., Miikkulainen, R.: Evolving neural netwo rks through augmenting topologies. Evol. Comput. 10(2), 99–127 (Jun 2002). https://doi.org/10.1162/106365602320169811

    2002 doi

  43. [50]

    IEEE Transactions on Evoluti onary Computation 23, 89–103 (2019)

    Sun, Y., Yen, G.G., Yi, Z.: Evolving unsupervised deep ne ural networks for learning meaningful representations. IEEE Transactions on Evoluti onary Computation 23, 89–103 (2019). https://doi.org/10.1109/TEVC.2018.2808 689

    2019

  44. [51]

    In: Touretzky, D.S

    Tenorio, M.F., Lee, W.T.: Self organizing neural networ ks for the identification problem. In: Touretzky, D.S. (ed.) Advances in Neural Infor mation Processing Systems 1, pp. 57–64. Morgan-Kaufmann (1989)

    1989

  45. [52]

    Valiant, L.G.: A theory of the learnable. Commun. ACM 27, 1134–1142 (1984). https://doi.org/10.1145/1968.1972

    1984

  46. [53]

    Theory of Probability and Its Applications 16, 264– 280 (1971)

    Vapnik, V., Chervonenkis, A.Y.: On the uniform converge nce of relative frequencies of events to their probabilities. Theory of Probability and Its Applications 16, 264– 280 (1971). https://doi.org/10.1007/978-3-319-21852-6 3, translated by B. Seckler

    1971 doi

  47. [54]

    Vitushkin, A.: Some properties of linear superposition s of smooth functions. Dokl. Akad. Nauk SSSR 156, 1258–1261 (1964) 16 A. de Wynter

    1964

  48. [55]

    IEEE Transactions on Evolutionary Computation 1(1), 67–87 (1997)

    Wolpert, D.H., Macready, W.G.: No free lunch theorems fo r optimiza- tion. IEEE Transactions on Evolutionary Computation 1(1), 67–87 (1997). https://doi.org/10.1109/4235.585893

    1997

  49. [57]

    In: Proceedings of the 32Nd International Conference on Neural Information Processing Systems

    Wong, C., Houlsby, N., Lu, Y., Gesmundo, A.: Transfer lea rning with neural au- toml. In: Proceedings of the 32Nd International Conference on Neural Information Processing Systems. pp. 8366–8375. NIPS’18 (2018)

    2018

  50. [58]

    Proceedings of the 10 th International Symposium on Experimental Algorithms 6630, 21–32 (2011)

    Yang, X.S.: Metaheuristic optimization: Algorithm ana lysis and open problems. Proceedings of the 10 th International Symposium on Experimental Algorithms 6630, 21–32 (2011). https://doi.org/10.1007/978-3-642-2066 2-7 2

    2011 doi

  51. [59]

    Proceedin gs of the IEEE 87(9) (1999)

    Yao, X.: Evolving artificial neural networks. Proceedin gs of the IEEE 87(9) (1999). https://doi.org/10.1109/5.784219

    1999 doi

  52. [60]

    Zoph, B., Le, Q.V.: Neural architecture search with rein forcement learning. CoRR abs/1611.01578 (2016) Appendices A PAC Is a Solver for F A PAC learning, as defined by Valiant [52], is a slightly different problem th an F A, as it concerns itself with whether a concept class C ...

    2016 arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.