Why and when can deep-but not shallow-networks avoid the curse of dimensionality: A review
Open accessAbstract
The paper reviews and extends an emerging body of theoretical results on deep learning including the conditions under which it can be exponentially better than shallow learning. A class of deep convolutional networks represent an important special case of these conditions, though weight sharing is not the main reason for their exponential advantage. Implications of a few key theorems are discussed, together with new results, open problems and conjectures.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Deep learning models can handle the curse of dimensionality by leveraging different degrees of smoothness in compositional function and parallel computations of GPUs.
“The multivariate evaluation shows another benefit of deep learning models, which is the ability to handle the curse of dimensionality (Bellman, 2010; Keogh and Mueen, 2017) by leveraging different degrees of smoothness in compositional function (Poggio et al., 2017) as well as the parallel computations of the GPUs (Lu et al., 2015).”
From Deep learning for time series classification: a review (2019) · cites this paper as Poggio et al., 2017
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Adam: A Method for Stochastic Optimization
Kingma, D. P., & Ba, J. (2014) · arXiv · doi:10.48550/arxiv.1412.6980 · Cited by 98,946 · see citing works
LeCun, Y., Bengio, Y., & Hinton, G. (2015) · Nature · doi:10.1038/nature14539 · Cited by 84,126 · see citing works
TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G. S., Davis, A., Dean, J., Devin, M., et al. (2016) · arXiv · doi:10.48550/arxiv.1603.04467 · Cited by 9,408 · see citing works
(2012) · Cited by 8,009 · see citing works
Fukushima, K. (1980) · Biological Cybernetics · doi:10.1007/bf00344251 · Cited by 5,759 · see citing works
Hierarchical models of object recognition in cortex
Riesenhuber, M., & Poggio, T. (1999) · Nature Neuroscience · doi:10.1038/14819 · Cited by 3,309 · see citing works
Self-citationPerceptrons: An Introduction to Computational Geometry
Minsky, M., & Papert, S. A. (1969) · Cited by 3,273 · see citing works
Understanding Machine Learning: From Theory to Algorithms
Shalev-Shwartz, S., & Ben-David, S. (2014) · doi:10.1017/cbo9781107298019 · Cited by 3,115 · see citing works
(2015) · Cited by 2,857 · see citing works
Human-level concept learning through probabilistic program induction
Lake, B. M., Salakhutdinov, R., & Tenenbaum, J. B. (2015) · Science · doi:10.1126/science.aab3050 · Cited by 2,817 · see citing works
Approximation theory of the MLP model in neural networks
Pinkus, A. M. (1999) · Acta Numerica · doi:10.1017/s0962492900002919 · Cited by 1,542 · see citing works
Notices of the American Mathematical Society
American Mathematical Society (2012) · Notices of the American Mathematical Society · doi:10.1090/noti · Cited by 1,339 · see citing works
Neural network learning theoretical foundations
Anthony, M., & Bartlett, P. L. (2009) · Cited by 1,310 · see citing works
(2007) · Cited by 937 · see citing works
On the Number of Linear Regions of Deep Neural Networks
Montúfar, G., Pascanu, R., Cho, K., & Bengio, Y. (2014) · arXiv · doi:10.48550/arxiv.1402.1869 · Cited by 840 · see citing works
Constant depth circuits, Fourier transform, and learnability
Linial, N., Mansour, Y., & Nisan, N. (1993) · Journal of the ACM · doi:10.1145/174130.174138 · Cited by 567 · see citing works
(2007) · The MIT Press eBooks · doi:10.7551/mitpress/7496.001.0001 · Cited by 539 · see citing works
Why Does Deep and Cheap Learning Work So Well?Preprint
Lin, H. W., Tegmark, M., & Rolnick, D. (2017) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 538 · see citing works
Hierarchical Singular Value Decomposition of Tensors
Grasedyck, L. (2010) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/090764189 · Cited by 525 · see citing works
Breaking the Curse of Dimensionality with Convex Neural NetworksPreprint
Bach, F. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1412.8690 · Cited by 457 · see citing works
Computational limitations of small-depth circuits
Håstad, J. (1987) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 452 · see citing works
(2016) · Conference on Learning Theory · Cited by 443 · see citing works
The Mathematics of Learning: Dealing With Data
Smale, S. (2005) · International Conference on Neural Networks and Brain · doi:10.1109/icnnb.2005.1614860 · Cited by 399 · see citing works
Deep vs. shallow networks: An approximation theory perspective
Mhaskar, H. N., & Poggio, T. (2016) · Analysis and Applications · doi:10.1142/s0219530516400042 · Cited by 344 · see citing works
Self-citationNeural Networks for Optimal Approximation of Smooth and Analytic Functions
Mhaskar, H. N. (1996) · Neural Computation · doi:10.1162/neco.1996.8.1.164 · Cited by 332 · see citing works
Self-citationOn the Expressive Power of Deep Learning: A Tensor AnalysisPreprint
Cohen, N., Sharir, O., & Shashua, A. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1509.05009 · Cited by 312 · see citing works
Shallow vs. Deep Sum-Product Networks
Delalleau, O., & Bengio, Y. (2011) · Cited by 248 · see citing works
Optimal nonlinear approximation
DeVore, R., Howard, R., & Micchelli, C. A. (1989) · manuscripta mathematica · doi:10.1007/bf01171759 · Cited by 231 · see citing works
The Power of Depth for Feedforward Neural NetworksPreprint
Eldan, R., & Shamir, O. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1512.03965 · Cited by 208 · see citing works
Approximation properties of a multilayered feedforward artificial neural network
Mhaskar, H. N. (1993) · Advances in Computational Mathematics · doi:10.1007/bf02070821 · Cited by 157 · see citing works
Self-citationLearning Boolean Functions via the Fourier Transform
Mansour, Y. (1994) · Springer eBooks · doi:10.1007/978-1-4615-2696-4_11 · Cited by 148 · see citing works
Bounds for Linear Multi-Task Learning
Maurer, A. (2006) · Cited by 138 · see citing works
Representation Benefits of Deep Feedforward NetworksPreprint
Telgarsky, M. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1509.08101 · Cited by 126 · see citing works
Unsupervised learning of invariant representations
Anselmi, F., Leibo, J. Z., Rosasco, L., Mutch, J., Tacchetti, A., & Poggio, T. (2016) · Theoretical Computer Science · doi:10.1016/j.tcs.2015.06.048 · Cited by 88 · see citing works
Self-citationLimitations of the approximation capabilities of neural networks with one hidden layer
Chui, C. K., Li, X., & Mhaskar, H. N. (1996) · Advances in Computational Mathematics · doi:10.1007/bf02124745 · Cited by 82 · see citing works
Self-citationNeural networks for localized approximation
Chui, C. K., Li, X., & Mhaskar, H. N. (1994) · Mathematics of Computation · doi:10.1090/s0025-5718-1994-1240656-2 · Cited by 79 · see citing works
Self-citationNeural Networks for Localized Approximation
Chui, C. K., Li, X., & Mhaskar, H. N. (1994) · Mathematics of Computation · doi:10.2307/2153285 · Cited by 74 · see citing works
Self-citationOn the tractability of multivariate integration and approximation by neural networks
Mhaskar, H. N. (2004) · Journal of Complexity · doi:10.1016/j.jco.2003.11.004 · Cited by 66 · see citing works
Self-citationVisual Cortex and Deep Networks: Learning Invariant Representations
Poggio, T., & Anselmi, F. (2016) · Cited by 50 · see citing works
Self-citationVisual Cortex and Deep Networks
Poggio, T., & Anselmi, F. (2016) · The MIT Press eBooks · doi:10.7551/mitpress/10177.001.0001 · Cited by 50 · see citing works
Self-citationLearning Real and Boolean Functions: When Is Deep Better Than Shallow
Mhaskar, H. N., Liao, Q., & Poggio, T. (2016) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 38 · see citing works
Self-citationDeep Convolutional Networks are Hierarchical Kernel MachinesPreprint
Anselmi, F., Rosasco, L., Tan, C., et al. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1508.01084 · Cited by 26 · see citing works
Self-citationOn the representation of multi-input systems: Computational properties of polynomial algorithms
Poggio, T., & Reichardt, W. (1980) · Biological Cybernetics · doi:10.1007/bf00355455 · Cited by 26 · see citing works
Self-citationI-theory on depth vs width: hierarchical function composition
Poggio, T., Anselmi, F., & Rosasco, L. (2015) · CINECA IRIS Institutial Research Information System (University of Genoa) · Cited by 26 · see citing works
Self-citationNeural networks for localized approximation of real functions
Mhaskar, H. N. (2002) · doi:10.1109/nnsp.1993.471870 · Cited by 24 · see citing works
Self-citationRepresentation properties of multilayer feedforward networks
Moore, B., & Poggio, T. (1988) · Neural Networks · doi:10.1016/0893-6080(88)90240-7 · Cited by 23 · see citing works
Self-citationNeural Network Learning: Theoretical Foundations
Shawe-Taylor, J. S. (2001) · AI Magazine · doi:10.1609/aimag.v22i2.1564 · Cited by 23 · see citing works
Anselmi, F., Leibo, J. Z., Rosasco, L., Mutch, J., Tacchetti, A., & Poggio, T. (2014) · Cited by 19 · see citing works
Self-citationA Provably Efficient Algorithm for Training Deep NetworksPreprint
Livni, R., Shalev‐Shwartz, S., & Shamir, O. (2013) · arXiv (Cornell University) · Cited by 17 · see citing works
Notes on Hierarchical Splines, DCLNs and i-theory
Poggio, T., Rosasco, L., Shashua, A., Cohen, N., & Anselmi, F. (2015) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 16 · see citing works
Self-citationDepth Separation in ReLU Networks for Approximating Smooth Non-Linear Functions.Preprint
Safran, I., & Shamir, O. (2016) · arXiv (Cornell University) · Cited by 11 · see citing works
Comment on "Why does deep and cheap learning work so well?" [arXiv:1608.08225]Preprint
Schwab, D. J., & Mehta, P. D. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1609.03541 · Cited by 9 · see citing works
Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of DimensionalityPreprint
Poggio, T., Mhaskar, H. N., Rosasco, L., et al. (2016) · arXiv (Cornell University) · Cited by 6 · see citing works
Self-citationCondiciones para que una función infinitamente derivable sea un polinomio
Corominas, E., & Balaguer, F. S. (1954) · Revista matemática hispanoamericana · Cited by 5 · see citing works
Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a ReviewPreprint
Poggio, T., Mhaskar, H. N., Rosasco, L., et al. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1611.00740 · Cited by 5 · see citing works
Self-citation
Flagged first, then by citations
Research works printed but not linked: 3
- D. L. Donoho. High-dimensional data analysis: The curses and blessings of dimensionality. Lecture -Math Challenges of Century, vol. 13, pp. 178-183, 2000.
- E. Corominas, F. S. Balaguer. Conditions for an in- finitely differentiable function to be a polynomial. Revista Matemática Hispanoamericana vol. 14, no. 1-2, pp. 26-43, 1954. (in Spanish)
- R. A. DeVore, R. Howard C. A. Micchelli. Optimal non- linear approximation. Manuscripta Mathematica, vol. 63, no. 4, pp. 469-478, 1989.
Cited by
Sorted by citations
Deep learning for time series classification: a review
Ismail Fawaz, H., Forestier, G., Weber, J., Idoumghar, L., & Muller, P.-A. (2019) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-019-00619-1 · Cited by 3,342 · see citing works
“…benefit of deep learning models, which is the ability to handle the curse of dimensionality (Bellman, 2010; Keogh and Mueen, 2017) by leveraging different degrees of smoothness in compositional function (Poggio et al., 2017) as well as the parallel computations of the GPUs (Lu et al., 2015).”
BackgroundSupervised Machine Learning for Population Genetics: A New Paradigm
Schrider, D. R., & Kern, A. D. (2018) · Trends in Genetics · doi:10.1016/j.tig.2017.12.005 · Cited by 453 · see citing works
Expert and non-expert opinion about technological unemployment
Walsh, T. (2018) · International Journal of Automation and Computing · doi:10.1007/s11633-018-1127-x · Cited by 122 · see citing works
Breaking the curse of dimensionality to identify causal variants in Breeding 4
Ramstein, G. P., Jensen, S. E., & Buckler, E. S. (2019) · Theoretical and Applied Genetics · doi:10.1007/s00122-018-3267-3 · Cited by 87 · see citing works
Accessory pathway analysis using a multimodal deep learning model
Nishimori, M., Kiuchi, K., Nishimura, K., Kusano, K., Yoshida, A., Adachi, K., Hirayama, Y., Miyazaki, Y., Fujiwara, R., Sommer, P., et al. (2021) · Scientific Reports · doi:10.1038/s41598-021-87631-y · Cited by 36 · see citing works
Low dimensional subject representation based transfer learning in eeg decoding
Jeng, P.-Y., Wei, C.-S., Jung, T.-P., & Wang, L.-C. (2021) · IEEE Journal of Biomedical and Health Informatics · doi:10.1109/jbhi.2020.3025865 · Cited by 35 · see citing works
- Authors
- Poggio, T., Mhaskar, H., Rosasco, L., Miranda, B., & Liao, Q.
- Affiliations
- McGovern Institute for Brain Research (US)
- California Institute of Technology (US)
- Corresponding author
- Poggio, Tomaso
- Venue
- International Journal of Automation and Computing
- Published
- 2017-03-14
- Volume
- 14
- Issue
- 5
- Pages
- 503-519
- ISSN
- 1476-8186 (ISSN-L)
- 1751-8520
- OpenAlex
- W2550848904
- Cited by
- 559
- References
- 56
- Citations by year
- 2026: 34 · 2025: 50 · 2024: 48 · 2023: 70 · 2022: 74 · 2021: 89 · 2020: 80 · 2019: 58 · 2018: 37 · 2017: 17 · 2016: 2
- FWCI
- 31.34
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Locations
- Machine Intelligence Research (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- CINECA IRIS Institutial Research Information System (University of Genoa) (submittedVersion, cc-by)
- CaltechAUTHORS (California Institute of Technology) (submittedVersion, cc-by)
- DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc-sa)
- CINECA IRIS Institutial Research Information System (University of Genoa) (submittedVersion, other-oa)
- arXiv (Cornell University)
- Springer US
- Funders
- National Science Foundation (1231216)
- Companhia Brasileira de Metalurgia e Mineração
- Army Research Office (W911NF-15-1-0385, W911NF-15-1-, W911NF, W911NF-15)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Neural Networks and Applications
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Keywords
- curse of dimensionality, deep learning, shallow learning, deep convolutional neural networks, parameter sharing, neural network approximation
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
