Pith. sign in

REVIEW 2 major objections 6 minor 75 references

Position: A Theory of Deep Learning Must Include Compositional Sparsity

T0 review · 2 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read This paper proves every efficiently Turing-computable function is compositionally sparse, and argues this is why deep networks beat the curse of dimensionality.

desk verdict A readable position paper that proves a classical Boolean circuit fact and builds a plausible research agenda on it, but the central real-valued claim rests on a deferred proof. read the letter →

arxiv 2507.02550 v1 pith:VFYWKNVU submitted 2025-07-03 cs.LG cs.AI

David A. Danhofer , Davide D'Ascenzo , Rafael Dubach , Tomaso Poggio This is my paper · ORCID
classification cs.LGcs.AI MSC 68T0768Q1568Q0568Q32
keywords compositionalsparsitycurseofdimensionalitydeeplearningtheoryefficientTuringcomputabilityBooleancircuitsapproximationchain-of-thoughtuniversal
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

Deep networks succeed in high dimensions, the paper argues, because the functions they are asked to learn are compositionally sparse: composed of polynomially many simple constituent functions, each depending on only a few inputs. The paper proves Theorem 3.2, that every efficiently Turing-computable function has this property, and combines it with an earlier approximation result to conclude that any such function can be approximated to accuracy $\varepsilon$ by a deep sparse network with complexity polynomial in the dimension $d$ and in $\varepsilon^{-1}$. This would mean deep networks are universal approximators for all practically computable functions without the curse of dimensionality, while shallow networks are provably exponentially worse. The stakes for a reader: if this is right, the central open problem in deep learning theory is no longer approximation but how networks discover the right compositional decomposition from data.

What carries the argument

The central object is compositional sparsity: a function $f: X^d \to X$ is compositionally sparse if it is the composition of at most $O(\mathrm{poly}\, d)$ constituent functions, each depending on at most a small constant number $c$ of input variables, visualized as a directed acyclic graph of bounded in-degree. The argument's load-bearing step is the classical circuitization of deterministic polynomial-time computation: a Turing machine running in time $O(\mathrm{poly}(n))$ becomes a Boolean circuit of polynomial size, and replacing every unbounded fan-in gate by a binary tree of bounded fan-in preserves polynomial size, so the resulting DAG encodes the target function as compositionally sparse. This converts a statement about the complexity class FP into a statement about function structure, and the earlier approximation theorem then converts that structure into explicit parameter counts for deep versus shallow networks.

What would settle it

Exhibit a function $f \in \mathrm{FP}$ whose every compositional sparse decomposition requires superpolynomially many constituents, or a target function certified to lie outside FP that a deep network nevertheless learns with polynomial parameters and samples; either would break the chain from Theorem 3.2 to Corollary 3.4.

Watch

Extended reading notes

Core claim

The paper's central claim is that the defining structural property behind deep learning's success is compositional sparsity. A function is compositionally sparse when it can be written as at most polynomially many sparse constituent functions, each depending on a small constant number of inputs. Theorem 3.2 asserts that every efficiently Turing-computable function — every function in the complexity class FP — is compositionally sparse: a polynomial-time Turing machine expands into a polynomial-size Boolean circuit, and rebinarizing all high-fan-in gates yields a fan-in-2 DAG with only polynomial overhead. Combined with the known result that deep networks can approximate such functions with $O(d\varepsilon^{-2})$ parameters while shallow networks require $O(\varepsilon^{-d})$, the paper derives Corollary 3.4: any efficiently Turing-computable function, Boolean or real-valued, is approximable by a deep sparse network with polynomial complexity, avoiding the curse of dimensionality.

Load-bearing premise

The argument rests on the assumption that real-world deep learning targets are, or are well-approximated by, polynomial-time Turing-computable functions, and that the real-valued version of the compositionality theorem holds as stated.

Editorial extensions

If this is right

  • Deep networks become universal approximators for every practically computable function: for any efficiently Turing-computable target and any accuracy $\varepsilon > 0$, a deep sparse network of complexity polynomial in $d$ and $\varepsilon^{-1}$ exists.
  • The representational side of the curse of dimensionality is closed for functions in FP; what remains open is optimization and learning, not whether a good approximation exists.
  • Autoregressive next-token predictors are universal learners for efficiently Turing-computable functions, because sparse Boolean constituents are learnable when given training sets for each constituent.
  • Chain-of-thought reasoning works by breaking a dense one-shot problem into sparse, individually learnable subproblems, which is why intermediate reasoning steps improve performance.
  • Learning arbitrary compositionally sparse functions from input-output pairs alone is worst-case computationally hard under standard cryptographic assumptions, so supervision or architectural priors are needed in general.

Reading between the lines

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

  • A direct test of the position: take a suite of synthetic compositionally sparse functions with known DAGs and compare measured parameter scaling to the predicted $O(d\varepsilon^{-2})$ for deep networks versus $O(\varepsilon^{-d})$ for shallow ones.
  • If the paper is right, architecture design can be guided by the principle that the goal is to induce or discover bounded-fan-in DAG structure; attention's input-dependent token selection is a natural dynamic mechanism for this, while convolution is only one static instance.
  • A boundary case worth probing: functions that are efficiently computable in principle but whose only known decompositions use huge intermediate fan-in or many constituents should be hard for DNNs despite being in FP; finding such functions and measuring DNN performance would separate the compositional-sparsity explanation from alternatives like the manifold or multi-index models.
  • The paper's real-valued conclusion leans on an extension of Theorem 3.2 deferred to another reference; if that extension fails for some natural notion of real-valued computability, the universality claim would narrow to Boolean functions and would need revision.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 6 minor

Summary. This position paper argues that compositional sparsity is the key structural property that lets deep networks avoid the curse of dimensionality. The paper defines compositionally sparse functions, proves in Appendix A that every function in FP has a polynomial-size fan-in-2 Boolean circuit and is therefore compositionally sparse (Theorem 3.2), and combines this with an approximation theorem of Poggio et al. (2017) to conclude (Corollary 3.4) that every efficiently Turing-computable Boolean or real-valued function can be approximated by a deep sparse network with polynomial complexity in dimension and inverse accuracy. The remainder of the paper discusses implications for learnability, architecture design, and chain-of-thought prompting, reviews manifold and multi-index alternatives, and lists open questions.

Significance. If the central claim were fully established, the paper would offer a broad and appealing explanation for why deep networks succeed on high-dimensional tasks. The Boolean part of Theorem 3.2 is proved in a self-contained way in Appendix A using standard circuit-complexity arguments, and that proof is checkable independently of the authors' prior work. The paper is also honest about the gap between approximation and learnability (Section 4), presents the chain-of-thought claim as a conjecture, and gives concrete references to alternative frameworks. The main limitation is that the paper's headline claim about real-world continuous deep learning rests on a bridge from Boolean circuits to real-valued functions that is asserted rather than proved in this manuscript.

major comments (2)
  1. [Section 3, Corollary 3.4] Corollary 3.4 asserts that any efficiently Turing-computable function, Boolean or real-valued, can be approximated by a deep sparse network with polynomial complexity in d and epsilon^{-1}, but the proof of Theorem 3.2 in Appendix A only establishes the Boolean case. The proof converts a polynomial-time DTM into a polynomial-size fan-in-2 Boolean circuit, which is a statement about functions on finite binary strings. A real-valued function f: R^d -> R is not an element of FP under the standard definition, and the paper does not specify an encoding of real inputs, a function space, or the regularity conditions needed to pass from a discrete Boolean circuit to a continuous deep network. Without those ingredients, Theorem 3.3 cannot be invoked for the real-valued case, and the claim that DNNs avoid the curse of dimensionality for real-world continuous targets is not supported by the proof in this manuscript. This is not a cosmetic issue: functions such as parity are in FP, but their Boolean circuit representations are discontinuous, so the O(d epsilon^{-2}) approximation bound does not follow from the fan-in-2 decomposition alone. The corollary should either be restricted to Boolean functions or supplied with the full real-valued argument, or the conditions under which the Poggio and Fraser (2024) extension applies should be stated and proved.
  2. [Section 4.3, Corollary 4.3] Corollary 4.3 is stated as a consequence of Theorem 3.2 and Mansour (1994), but no proof is given. Theorem 3.2 guarantees the existence of a decomposition into constituent functions; it does not provide the DAG or the identity of the constituents. The assumption that training sets are available for each of the sparse constituent functions in one of its decompositions presupposes access to supervision that is not part of the standard learning problem, and even with such supervision the composition of the learned constituents into the full function must be specified. Mansour's results concern specific classes of Boolean functions under specific distributional or representation assumptions and do not automatically imply learnability of arbitrary circuits from constituent training sets. The paper should either prove this statement with explicit assumptions or clearly label it as a conjecture or heuristic rather than a corollary.
minor comments (6)
  1. [Section 3, paragraph 1] Equating 'efficiently Turing-computable' with FP is nonstandard for real-valued functions; please clarify the intended formalization (e.g., computable analysis, bit-encoding with an accuracy parameter) or explicitly state that the paper only treats Boolean functions in the theorem and treats the real-valued case as a conjecture.
  2. [Definition 3.1] The domain X is left ambiguous. Make explicit whether X is {0,1}, R, or a general space, and state how the dimension parameter d in Definition 3.1 relates to the input length n of the Turing machine in Theorem 3.2.
  3. [Section 4.3, Equation (5)] The nested expression for chain-of-thought prediction has mismatched brackets; the notation should be cleaned up so that the recursive application of f_theta is unambiguous.
  4. [Section 4.2, first paragraph] The statement that CNNs address compositional sparsity 'not because of translational invariance' is too categorical; local filters, sparse Toeplitz structure, and equivariance are closely related, so the claim deserves qualification.
  5. [Section 3.1, Theorem 3.2] The text says 'We prove this conjecture from Poggio & Fraser 2024' immediately after calling the statement a theorem; use consistent terminology to avoid confusion.
  6. [Section 4.1, Theorem 4.1] The citation to Goldreich et al. (1986) is terse for a substantive learning-hardness claim; please cite the precise theorem or a standard textbook treatment so the reader can verify the exact statement.

Circularity Check

1 steps flagged · score 4.0 of 10

The Boolean part of the central theorem is independently derived from classical circuit complexity, but the real-valued clause that carries the practical claim is deferred to the authors' own prior work.

  1. self citation load bearing [Section 3.2, Corollary 3.4; Section 3, paragraph on real-valued computability; Appendix A]
    "Corollary 3.4 (cf. Poggio & Fraser (2024)). Any efficiently Turing-computable function (Boolean or real-valued) may be approximated to an accuracy of ϵ>0 with a deep, sparse network of polynomial complexity in d and ϵ−1."

    The paper's own derivation in Appendix A proves only the Boolean/string case: an f in FP yields a polynomial-size fan-in-2 Boolean circuit, which is then relabeled 'compositionally sparse'. The real-valued clause of Corollary 3.4 is not derived in the paper; it is supported only by the cross-reference to Poggio & Fraser (2024), a prior publication sharing author Poggio. Section 3 equates 'efficiently Turing-computable' with FP, a class of finite-string functions, so the real-valued extension is an additional load-bearing assumption whose cited warrant is the authors' own earlier work. The continuous-domain 'avoiding the curse of dimensionality' conclusion therefore rests on that self-citation rather than on the appended Boolean proof.

full rationale

The derivation chain is largely self-contained for Boolean/finite-string functions: Theorem 3.2 is proved in Appendix A from the standard DTM-to-circuit construction (Arora & Barak 2009), and the definition of compositional sparsity is essentially a bounded-fan-in polynomial-size DAG, so this part is a known circuit-complexity result rather than a circular prediction. The approximation half (Theorem 3.3) is imported from prior work (Poggio et al. 2017), but it is a separate approximation theorem and is not fitted to the present data. The main circularity-adjacent defect is the real-valued clause of Corollary 3.4: the paper proves only the Boolean case and defers the continuous case to Poggio & Fraser (2024), a prior publication by the same group. That clause is load-bearing because the broader thesis concerns real-world continuous deep learning. Since the Boolean theorem and the approximation theory retain independent content, the paper scores a moderate 4 rather than a higher circularity score.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claims rest on standard complexity-theory facts (DTM-to-circuit conversion), a stated domain assumption about the relevance of FP to real-world learning targets, a deferred real-valued extension from cited prior work, and an imported approximation theorem from earlier papers by the same research group.

assumptions (4)
  • standard math A deterministic Turing machine running in time T(n) can be converted into a Boolean circuit of size O(T(n) log T(n)) with bounded fan-in.
    Invoked in Appendix A to prove Theorem 3.2; standard result from Arora & Barak (2009).
  • domain assumption The class FP consists of functions computed by deterministic polynomial-time Turing machines, and 'efficiently Turing-computable' is equated with FP.
    Stated in Section 3, this identification is a modeling choice that underlies the paper's scope. It excludes functions computable in polynomial time with real-valued outputs unless approximated.
  • domain assumption Real-valued efficiently Turing-computable functions are compositionally sparse.
    Used in Corollary 3.4 but not proved in this paper; deferred to Poggio & Fraser (2024). The Boolean proof only covers finite-precision outputs.
  • standard math Deep networks mimicking the DAG of a compositionally sparse function require O(d epsilon^-2) parameters to approximate to accuracy epsilon (Theorem 3.3, restated from Poggio et al. 2017).
    This cited theorem is the bridge from compositional sparsity to the claim that DNNs avoid the curse of dimensionality; it is not proved in this paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Position: A Theory of Deep Learning Must Include Compositional Sparsity." pith.science (2026). https://pith.science/paper/VFYWKNVU

@misc{pith2026250702550,
  author       = {Pith},
  title        = {Pith review of: Position: A Theory of Deep Learning Must Include Compositional Sparsity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VFYWKNVU}},
  note         = {Machine review of arXiv:2507.02550}
}
read the original abstract

Overparametrized Deep Neural Networks (DNNs) have demonstrated remarkable success in a wide variety of domains too high-dimensional for classical shallow networks subject to the curse of dimensionality. However, open questions about fundamental principles, that govern the learning dynamics of DNNs, remain. In this position paper we argue that it is the ability of DNNs to exploit the compositionally sparse structure of the target function driving their success. As such, DNNs can leverage the property that most practically relevant functions can be composed from a small set of constituent functions, each of which relies only on a low-dimensional subset of all inputs. We show that this property is shared by all efficiently Turing-computable functions and is therefore highly likely present in all current learning problems. While some promising theoretical insights on questions concerned with approximation and generalization exist in the setting of compositionally sparse functions, several important questions on the learnability and optimization of DNNs remain. Completing the picture of the role of compositional sparsity in deep learning is essential to a comprehensive theory of artificial, and even general, intelligence.

Figures

Figures reproduced from arXiv: 2507.02550 by the authors.

Figure 1
Figure 1. A DAG representing a compositionally sparse function. The green diamonds denote the d = 5 input variables, the red dots constituent functions and the blue square the final output. Each function depends on at most 3 = c ≪ d variables. 3.1. Compositionally Sparse Functions Definition 3.1 (Compositionally Sparse Function). A func￾tion f : X d → X is compositionally sparse if it can be represented as the composition of … view at source ↗
Figure 2
Figure 2. Is Socrates mortal? CoT-style intermediate solving steps can simplify this famous question to a sequence of general reason￾ing steps of less complexity than the specific question at hand. problems, each one of which can be learned. As such, it overcomes the complexity of one-shot learning. The following sketch shows how CoT fits into the compo￾sitional sparsity framework. Let fθ : T d → T be a token￾to-token predict… view at source ↗
Figure 3
Figure 3. for an example visualization). • Since k in the original circuit is bounded by O(T(n)) = O(poly(n)), transforming C into a cir￾cuit with fan-in 2 increases the circuit size by at most a polynomial factor. Thus, the final circuit has still polynomial size. The final circuit is a Boolean circuit of O(poly(n)) gates with fan-in 2. Since this circuit does not contain any cycles by construction, it can be translated into… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

75 extracted references · 56 canonical work pages

  1. [1]

    Abbe, E., Boix-Adser \`a , E., Brennan, M., Bresler, G., and Nagaraj, D. M. The staircase property: How hierarchical structure can guide deep learning. ArXiv, abs/2108.10573, 2021

    work page Pith review arXiv 2021

  2. [2]

    B., and Misiakiewicz, T

    Abbe, E., Adsera, E. B., and Misiakiewicz, T. The merged-staircase property: A necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. In Conference on Learning Theory , pp.\ 4782--4887. PMLR, 2022. ISBN 2640-3498

    work page 2022

  3. [3]

    Sgd learning on neural networks: leap complexity and saddle-to-saddle dynamics

    Abbe, E., Boix-Adser \`a , E., and Misiakiewicz, T. Sgd learning on neural networks: leap complexity and saddle-to-saddle dynamics. ArXiv, abs/2302.11055, 2023

    arXiv 2023

  4. [4]

    J., Bambrick, J., Bodenstein, S

    Abramson, J., Adler, J., Dunger, J., Evans, R., Green, T., Pritzel, A., Ronneberger, O., Willmore, L., Ballard, A. J., Bambrick, J., Bodenstein, S. W., Evans, D. A., Hung, C.-C., O’Neill, M., Reiman, D., Tunyasuvunakool, K., Wu, Z., Žemgulytė, A., Arvaniti, E., Beattie, C., Bertolli, O., Bridgland, A., Cherepanov, A., Congreve, M., Cowen-Rivers, A. I., Co...

    2024

  5. [5]

    Online Learning and Information Exponents : On The Importance of Batch size, and Time / Complexity Tradeoffs , June 2024 a

    Arnaboldi, L., Dandi, Y., Krzakala, F., Loureiro, B., Pesce, L., and Stephan, L. Online Learning and Information Exponents : On The Importance of Batch size, and Time / Complexity Tradeoffs , June 2024 a

    work page 2024

  6. [6]

    Repetita Iuvant : Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions , May 2024 b

    Arnaboldi, L., Dandi, Y., Krzakala, F., Pesce, L., and Stephan, L. Repetita Iuvant : Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions , May 2024 b

    work page 2024

  7. [7]

    and Barak, B

    Arora, S. and Barak, B. Computational Complexity: A Modern Approach. Cambridge University Press, 2009

    work page 2009

  8. [8]

    B., Gheissari, R., and Jagannath, A

    Arous, G. B., Gheissari, R., and Jagannath, A. Online stochastic gradient descent on non-convex losses from high-dimensional inference. Journal of Machine Learning Research, 22 0 (106): 0 1--51, 2021. ISSN 1533-7928

    work page 2021

Show all 75 references
  1. [9]

    and Kohler, M

    Bauer, B. and Kohler, M. On deep learning as a remedy for the curse of dimensionality in nonparametric regression. The Annals of Statistics, 47 0 (4): 0 2261--2285, August 2019. ISSN 0090-5364, 2168-8966

    2019

  2. [10]

    and Wattenhofer, R

    Belcak, P. and Wattenhofer, R. Fast feedforward networks. arXiv preprint arXiv:2308.14711, 2023

    2023 arXiv

  3. [11]

    Deep neural network approximation theory for high-dimensional functions, 2021

    Beneventano, P., Cheridito, P., Graeber, R., Jentzen, A., and Kuckuck, B. Deep neural network approximation theory for high-dimensional functions, 2021

    2021

  4. [12]

    Beneventano, P., Pinto, A., and Poggio, T. A. How neural networks learn the support is an implicit regularization effect of sgd. ArXiv, abs/2406.11110, 2024

    2024 arXiv

  5. [13]

    Bickel, P. J. and Doksum, K. A. An Analysis of Transformations Revisited . Journal of the american statistical association, 76 0 (374): 0 296--311, 1981. ISSN 0162-1459

    1981

  6. [14]

    Box, G. E. and Cox, D. R. An analysis of transformations. Journal of the Royal Statistical Society Series B: Statistical Methodology, 26 0 (2): 0 211--243, 1964. ISSN 1369-7412

    1964

  7. [15]

    and Gerstner, W

    Brea, J. and Gerstner, W. Weight space symmetry in deep networks gives rise to permutation saddles, connected by error valleys of non-interfering solutions, 2019

    2019

  8. [16]

    Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litw...

    1901

  9. [17]

    and Hsu, D

    Bruna, J. and Hsu, D. Survey on Algorithms for multi-index models, April 2025

    2025

  10. [18]

    A., Horvitz, E., Kamar, E., Lee, P., Lee, Y

    Bubeck, S., Chandrasekaran, V., Eldan, R., Gehrke, J. A., Horvitz, E., Kamar, E., Lee, P., Lee, Y. T., Li, Y.-F., Lundberg, S. M., Nori, H., Palangi, H., Ribeiro, M. T., and Zhang, Y. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint, 2023

    2023

  11. [19]

    M., Favero, A., and Wyart, M

    Cagnetta, F., Petrini, L., Tomasini, U. M., Favero, A., and Wyart, M. How Deep Neural Networks Learn Compositional Data : The Random Hierarchy Model . Physical Review X, 14 0 (3): 0 031001, July 2024. ISSN 2160-3308. doi:10.1103/PhysRevX.14.031001

    2024 doi

  12. [20]

    Superposition of many models into one

    Cheung, B., Terekhov, A., Chen, Y., Agrawal, P., and Olshausen, B. Superposition of many models into one. Advances in neural information processing systems, 32, 2019

    2019

  13. [21]

    M., Khosla, A., Pantazis, D., Torralba, A., and Oliva, A

    Cichy, R. M., Khosla, A., Pantazis, D., Torralba, A., and Oliva, A. Comparison of deep neural networks to spatio-temporal cortical dynamics of human visual object recognition reveals hierarchical correspondence. Scientific Reports, 6, 2016

    2016

  14. [22]

    Compositional Sparsity , Approximation Classes , and Parametric Transport Equations , June 2023

    Dahmen, W. Compositional Sparsity , Approximation Classes , and Parametric Transport Equations , June 2023. arXiv:2207.06128

    2023 arXiv

  15. [23]

    F., Gou, Z., Shao, Z., Li, Z., Gao, Z., Liu, A., ..., and Zhang, Z

    DeepSeek-AI, Guo, D., Yang, D., Zhang, H., Song, J., Zhang, R., Xu, R., Zhu, Q., Ma, S., Wang, P., Bi, X., Zhang, X., Yu, X., Wu, Y., Wu, Z. F., Gou, Z., Shao, Z., Li, Z., Gao, Z., Liu, A., ..., and Zhang, Z. Deepseek-r1: Incentivizing reasoning capability in llms via reinforc...

    2025

  16. [24]

    Seeing it all: Convolutional network layers map the function of the human visual system

    Eickenberg, M., Gramfort, A., Varoquaux, G., and Thirion, B. Seeing it all: Convolutional network layers map the function of the human visual system. NeuroImage, 152: 0 184--194, 2017

    2017

  17. [25]

    A., and Malach, E

    Gan, Y., Galanti, T., Poggio, T. A., and Malach, E. On the power of decision trees in auto-regressive language modeling. ArXiv, abs/2409.19150, 2024

    2024 arXiv

  18. [26]

    The implicit bias of depth: How incremental learning drives generalization

    Gissin, D., Shalev-Shwartz, S., and Daniely, A. The implicit bias of depth: How incremental learning drives generalization. ArXiv, abs/1909.12051, 2019

    1909 arXiv

  19. [27]

    How to construct random functions

    Goldreich, O., Goldwasser, S., and Micali, S. How to construct random functions. J. ACM, 33 0 (4): 0 792–807, August 1986. ISSN 0004-5411. doi:10.1145/6490.6503

    1986

  20. [28]

    In-context learning of large language models explained as kernel regression

    Han, C., Wang, Z., Zhao, H., and Ji, H. In-context learning of large language models explained as kernel regression. arXiv preprint, 2023

    2023

  21. [29]

    The Elements of Statistical Learning

    Hastie, T., Tibshirani, R., and Friedman, J. The Elements of Statistical Learning. Springer, 2009

    2009

  22. [30]

    A., and Lenat, D

    Hayes-Roth, F., Waterman, D. A., and Lenat, D. B. Building expert systems. Addison-Wesley Longman Publishing Co., Inc., USA, 1983. ISBN 9780201106862

    1983

  23. [31]

    Deep residual learning for image recognition

    He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp.\ 770--778, 2015

    2016

  24. [32]

    Introduction to manifold learning

    Izenman, A. Introduction to manifold learning. Wiley Interdisciplinary Reviews: Computational Statistics, 4, 09 2012. doi:10.1002/wics.1222

    2012 doi

  25. [33]

    An Introduction to Statistical Learning (2nd Ed.)

    James, G., Witten, D., Hastie, T., and Tibshirani, R. An Introduction to Statistical Learning (2nd Ed.). Springer, 2023

    2023

  26. [34]

    Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Ronneberger, O., Tunyasuvunakool, K., Bates, R., Žídek, A., Potapenko, A., Bridgland, A., Meyer, C., Kohl, S. A. A., Ballard, A. J., Cowie, A., Romera-Paredes, B., Nikolov, S., Jain, R., Adler, J., Back, T., Petersen...

    2021

  27. [35]

    Deep learning without poor local minima

    Kawaguchi, K. Deep learning without poor local minima. Advances in Neural Information Processing Systems (NeurIPS), 2016

    2016

  28. [36]

    T., Wang, J., and Weber, M

    Kiani, B. T., Wang, J., and Weber, M. Hardness of learning neural networks under the manifold hypothesis, 2024

    2024

  29. [37]

    and Langer, S

    Kohler, M. and Langer, S. On the rate of convergence of fully connected deep neural network regression estimates. The Annals of Statistics, 2021

    2021

  30. [38]

    Krizhevsky, A., Sutskever, I., and Hinton, G. E. Imagenet classification with deep convolutional neural networks. Communications of the ACM, 60: 0 84 -- 90, 2012

    2012

  31. [39]

    D., Oko, K., Suzuki, T., and Wu, D

    Lee, J. D., Oko, K., Suzuki, T., and Wu, D. Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit, June 2024

    2024

  32. [40]

    How diffusion models learn to factorize and compose

    Liang, Q., Liu, Z., Ostrow, M., and Fiete, I. How diffusion models learn to factorize and compose. arXiv preprint arXiv:2408.13256, 2024

    2024 arXiv

  33. [41]

    Lindsey, J., Gurnee, W., Ameisen, E., Chen, B., Pearce, A., Turner, N. L., Citro, C., Abrahams, D., Carter, S., Hosmer, B., Marcus, J., Sklar, M., Templeton, A., Bricken, T., McDougall, C., Cunningham, H., Henighan, T., Jermyn, A., Jones, A., Persic, A., Qi, Z., Thompson, T. B...

    2025

  34. [42]

    T., Goel, S., Krishnamurthy, A., and Zhang, C

    Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C. Transformers learn shortcuts to automata. arXiv preprint arXiv:2210.10749, 2022

    2022 arXiv

  35. [43]

    Auto-regressive next-token predictors are universal learners

    Malach, E. Auto-regressive next-token predictors are universal learners. ArXiv, abs/2309.06979, 2023

    2023 arXiv

  36. [44]

    Learning Boolean Functions via the Fourier Transform, pp.\ 391--424

    Mansour, Y. Learning Boolean Functions via the Fourier Transform, pp.\ 391--424. Springer US, Boston, MA, 1994. ISBN 978-1-4615-2696-4. doi:10.1007/978-1-4615-2696-4_11

    1994 doi

  37. [45]

    and Zhang, H

    Meilă, M. and Zhang, H. Manifold learning: what, how, and why, 2023

    2023

  38. [46]

    Learning real and boolean functions: When is deep better than shallow? CBMM Memo \#45, arXiv preprint, 2016

    Mhaskar, H., Liao, Q., and Poggio, T. Learning real and boolean functions: When is deep better than shallow? CBMM Memo \#45, arXiv preprint, 2016

    2016

  39. [47]

    Murty, S., Sharma, P., Andreas, J., and Manning, C. D. Characterizing intrinsic compositionality in transformers with tree projections. arXiv preprint arXiv:2211.01288, 2022

    2022 arXiv

  40. [48]

    Negahban, S. N. and Shah, D. Learning sparse boolean polynomials. 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp.\ 2032--2036, 2012

    2012

  41. [49]

    and Simon, H

    Newell, A. and Simon, H. A. Computer science as empirical inquiry: symbols and search. Commun. ACM, 19 0 (3): 0 113–126, March 1976. ISSN 0001-0782. doi:10.1145/360018.360022

    1976

  42. [50]

    Nguyen, Q. N. and Hein, M. Optimization landscape and expressivity of deep cnns. In International Conference on Machine Learning, 2017

    2017

  43. [51]

    Gpt-4 technical report

    OpenAI (2023) . Gpt-4 technical report. 2023

    2023

  44. [52]

    The impact of depth on compositional generalization in transformer language models

    Petty, J., van Steenkiste, S., Dasgupta, I., Sha, F., Garrette, D., and Linzen, T. The impact of depth on compositional generalization in transformer language models. In North American Chapter of the Association for Computational Linguistics, 2023

    2023

  45. [53]

    On efficiently computable functions, deep networks and sparse compositionality

    Poggio, T. On efficiently computable functions, deep networks and sparse compositionality. CBMM Memo \#156, arXiv preprint, 2025

    2025

  46. [54]

    and Fraser, M

    Poggio, T. and Fraser, M. Compositional sparsity of learnable functions. Bulletin of the American Mathematical Society, 61 0 (3): 0 438--456, 2024. doi:10.1090/bull/1820

    2024 doi

  47. [55]

    Why and when can deep-but not shallow-networks avoid the curse of dimensionality: A review

    Poggio, T., Mhaskar, H., Rosasco, L., Miranda, B., and Liao, Q. Why and when can deep-but not shallow-networks avoid the curse of dimensionality: A review. International Journal of Automation and Computing, 14 0 (5): 0 503--519, October 2017. ISSN 1751-8520

    2017

  48. [56]

    Poggio, T. A. How deep sparse networks avoid the curse of dimensionality: Efficiently computable functions are compositionally sparse. 2023

    2023

  49. [57]

    Language models are unsupervised multitask learners

    Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et al. Language models are unsupervised multitask learners. OpenAI blog, 1 0 (8): 0 9, 2019

    2019

  50. [58]

    Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. J. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21 0 (140): 0 1--67, 2020

    2020

  51. [59]

    P., Dupont, E., Ruiz, F

    Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, F. J. R., Ellenberg, J. S., Wang, P., Fawzi, O., Kohli, P., Fawzi, A., Grochow, J., Lodi, A., Mouret, J.-B., Ringer, T., and Yu, T. Mathematical discoveries from program search with lar...

    2023

  52. [60]

    Nonparametric regression using deep neural networks with ReLU activation function

    Schmidt-Hieber, J. Nonparametric regression using deep neural networks with ReLU activation function. The Annals of Statistics, 48 0 (4): 0 1875--1897, August 2020. ISSN 0090-5364, 2168-8966

    2020

  53. [61]

    J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nand, D., et al

    Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nand, D., et al. Mastering the game of go with deep neural networks and tree search. Nature, 529 0 (...

    2016

  54. [62]

    Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., a...

    2016 doi

  55. [63]

    A general reinforcement learning algorithm that masters chess, shogi, and go through self-play

    Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., Lillicrap, T., Simonyan, K., and Hassabis, D. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science...

    2018 doi

  56. [64]

    How sparse attention approximates exact attention?your attention is naturally \ n c\ -sparse

    Song, Z., Xiong, J., and Yang, C. How sparse attention approximates exact attention?your attention is naturally \ n c\ -sparse. In Sparsity in LLMs (SLLM): Deep Dive into Mixture of Experts, Quantization, Hardware, and Inference, 2025

    2025

  57. [65]

    and Krause, A

    Stobbe, P. and Krause, A. Learning fourier sparse set functions. In International Conference on Artificial Intelligence and Statistics, 2012

    2012

  58. [66]

    H., Wu, Y., Le, Q

    Trinh, T. H., Wu, Y., Le, Q. V., He, H., and Luong, T. Solving olympiad geometry without human demonstrations. Nature, 625 0 (7995): 0 476--482, January 2024. ISSN 1476-4687. doi:10.1038/s41586-023-06747-5

    2024 doi

  59. [67]

    van der Ouderaa , T. F. and van der Wilk , M. Learning invariant weights in neural networks. In Uncertainty in Artificial Intelligence , pp.\ 1992--2001. PMLR, 2022. ISBN 2640-3498

    1992

  60. [68]

    Vapnik, V. N. The Nature of Statistical Learning Theory. Springer, 2013

    2013

  61. [69]

    M., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A

    Vaswani, A., Shazeer, N. M., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need. In Neural Information Processing Systems, 2017

    2017

  62. [70]

    and Belinkov, Y

    Vig, J. and Belinkov, Y. Analyzing the structure of attention in a transformer language model. In BlackboxNLP@ACL, 2019

    2019

  63. [71]

    H., Xia, F., Le, Q., and Zhou, D

    Wei, J., Wang, X., Schuurmans, D., Bosma, M., Chi, E. H., Xia, F., Le, Q., and Zhou, D. Chain-of-thought prompting elicits reasoning in large language models. arXiv preprint, 2022

    2022

  64. [72]

    Xu, M., Rangamani, A., Banburski, A., Liao, Q., Tomer, Galanti, and Poggio, T. A. Dynamics in deep classifiers trained with the square loss: Normalization, low rank, neural collapse, and generalization bounds. Research, 6, 2023

    2023

  65. [73]

    F., Solomon, E

    Yamins, D., Hong, H., Cadieu, C. F., Solomon, E. A., Seibert, D., and DiCarlo, J. J. Performance-optimized hierarchical models predict neural responses in higher visual cortex. Proceedings of the National Academy of Sciences, 111: 0 8619 -- 8624, 2014

    2014

  66. [74]

    L., Cao, Y., and Narasimhan, K

    Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T. L., Cao, Y., and Narasimhan, K. Tree of thoughts: Deliberate problem solving with large language models. arXiv preprint, 2023

    2023

  67. [75]

    Symmetry induces structure and constraint of learning

    Ziyin, L. Symmetry induces structure and constraint of learning. In Proceedings of the 41st International Conference on Machine Learning, ICML'24. JMLR.org, 2024

    2024

Pith tools

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