Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review
---
paper_title: Learning Real and Boolean Functions: When Is Deep Better Than Shallow

paper_content:

This work was supported by the Center for Brains, Minds and Machines ::: (CBMM), funded by NSF STC award CCF 1231216. HNM was supported in ::: part by ARO Grant W911NF-15-1-0385.
---
paper_title: Notes on Hierarchical Splines, DCLNs and i-theory

paper_content:

We define an extension of classical additive splines for multivariate function approximation that we call hierarchical splines. We show that the case of hierarchical, additive, piece-wise linear splines includes present-day Deep Convolutional Learning Networks (DCLNs) with linear rectifers and pooling (sum or max). We discuss how these observations together with i-theory may provide a framework for a general theory of deep networks.
---
paper_title: I-theory on depth vs width: hierarchical function composition

paper_content:

Deep learning networks with convolution, pooling and subsampling are a special case of hierarchical architectures, which can be represented by trees (such as binary trees). Hierarchical as well as shallow networks can approximate functions of several variables, in particular those that are compositions of low dimensional functions. We show that the power of a deep network architecture with respect to a shallow network is rather independent of the specific nonlinear operations in the network and depends instead on the the behavior of the VC-dimension. A shallow network can approximate compositional functions with the same error of a deep network but at the cost of a VC-dimension that is exponential instead than quadratic in the dimensionality of the function. To complete the argument we argue that there exist visual computations that are intrinsically compositional. In particular, we prove that recognition invariant to translation cannot be computed by shallow networks in the presence of clutter. Finally, a general framework that includes the compositional case is sketched. The key condition that allows tall, thin networks to be nicer that short, fat networks is that the target input-output function must be sparse in a certain technical sense. This work was supported by the Center for Brains, Minds and Machines (CBMM), funded by NSF STC award CCF 1231216. I-theory on depth vs width: hierarchical function composition Tomaso Poggio with Fabio Anselmi and Lorenzo Rosasco
---
paper_title: Approximation properties of a multilayered feedforward artificial neural network

paper_content:

We prove that an artificial neural network with multiple hidden layers and akth-order sigmoidal response function can be used to approximate any continuous function on any compact subset of a Euclidean space so as to achieve the Jackson rate of approximation. Moreover, if the function to be approximated has an analytic extension, then a nearly geometric rate of approximation can be achieved. We also discuss the problem of approximation of a compact subset of a Euclidean space with such networks with a classical sigmoidal response function.
---
paper_title: Unsupervised learning of invariant representations with low sample complexity: the magic of sensory cortex or a new framework for machine learning?

paper_content:

This work was supported by the Center for Brains, Minds and Machines ::: (CBMM), funded by NSF STC award CCF - 1231216.
---
paper_title: The Mathematics of Learning: Dealing with Data

paper_content:

Abstract Learning is key to developing systems tailored to a broad range of data analysis and information extraction tasks. We outline the mathematical foundations of learning theory and describe a key algorithm of it.
---
paper_title: Representation Benefits of Deep Feedforward Networks

paper_content:

This note provides a family of classification problems, indexed by a positive integer $k$, where all shallow networks with fewer than exponentially (in $k$) many nodes exhibit error at least $1/6$, whereas a deep network with 2 nodes in each of $2k$ layers achieves zero error, as does a recurrent network with 3 distinct nodes iterated $k$ times. The proof is elementary, and the networks are standard feedforward networks with ReLU (Rectified Linear Unit) nonlinearities.
---
paper_title: Learning Real and Boolean Functions: When Is Deep Better Than Shallow

paper_content:

This work was supported by the Center for Brains, Minds and Machines ::: (CBMM), funded by NSF STC award CCF 1231216. HNM was supported in ::: part by ARO Grant W911NF-15-1-0385.
---
paper_title: Bridging the Gaps Between Residual Learning, Recurrent Neural Networks and Visual Cortex

paper_content:

We discuss relations between Residual Networks (ResNet), Recurrent Neural Networks (RNNs) and the primate visual cortex. We begin with the observation that a shallow RNN is exactly equivalent to a very deep ResNet with weight sharing among the layers. A direct implementation of such a RNN, although having orders of magnitude fewer parameters, leads to a performance similar to the corresponding ResNet. We propose 1) a generalization of both RNN and ResNet architectures and 2) the conjecture that a class of moderately deep RNNs is a biologically-plausible model of the ventral stream in visual cortex. We demonstrate the effectiveness of the architectures by testing them on the CIFAR-10 dataset.
---
paper_title: Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position

paper_content:

A neural network model for a mechanism of visual pattern recognition is proposed in this paper. The network is self-organized by “learning without a teacher”, and acquires an ability to recognize stimulus patterns based on the geometrical similarity (Gestalt) of their shapes without affected by their positions. This network is given a nickname “neocognitron”. After completion of self-organization, the network has a structure similar to the hierarchy model of the visual nervous system proposed by Hubel and Wiesel. The network consits of an input layer (photoreceptor array) followed by a cascade connection of a number of modular structures, each of which is composed of two layers of cells connected in a cascade. The first layer of each module consists of “S-cells”, which show characteristics similar to simple cells or lower order hypercomplex cells, and the second layer consists of “C-cells” similar to complex cells or higher order hypercomplex cells. The afferent synapses to each S-cell have plasticity and are modifiable. The network has an ability of unsupervised learning: We do not need any “teacher” during the process of self-organization, and it is only needed to present a set of stimulus patterns repeatedly to the input layer of the network. The network has been simulated on a digital computer. After repetitive presentation of a set of stimulus patterns, each stimulus pattern has become to elicit an output only from one of the C-cell of the last layer, and conversely, this C-cell has become selectively responsive only to that stimulus pattern. That is, none of the C-cells of the last layer responds to more than one stimulus pattern. The response of the C-cells of the last layer is not affected by the pattern's position at all. Neither is it affected by a small change in shape nor in size of the stimulus pattern.
---
paper_title: Neural networks for localized approximation of real functions

paper_content:

The problem of constructing universal networks capable of approximating all functions having bounded derivatives is discussed. It is demonstrated that, using standard ideas from the theory of spline approximation, it is possible to construct such networks to provide localized approximation. The networks can be used to implement multivariate analogues of the Chui-Wang wavelets (1990) and also for the simultaneous approximation of a function and its derivative. The number of neurons required to yield the desired approximation at any point does not depend upon the degree of accuracy desired. >
---
paper_title: Neural Networks for Localized Approximation

paper_content:

We prove that feedforward artificial neural networks with a single hidden layer and an ideal sigmoidal response function cannot provide localized approximation in a Euclidean space of dimension higher than one. We also show that networks with two hidden layers can be designed to provide localized approximation. Since wavelet bases are most effective for local approximation, we give a discussion of the implementation of spline wavelets using multilayered networks where the response function is a sigmoidal function of order at least two.
---
paper_title: Shallow vs. Deep Sum-Product Networks

paper_content:

We investigate the representational power of sum-product networks (computation networks analogous to neural networks, but whose individual units compute either products or weighted sums), through a theoretical analysis that compares deep (multiple hidden layers) vs. shallow (one hidden layer) architectures. We prove there exist families of functions that can be represented much more efficiently with a deep network than with a shallow one, i.e. with substantially fewer hidden units. Such results were not available until now, and contribute to motivate recent research involving learning of deep sum-product networks, and more generally motivate research in Deep Learning.
---
paper_title: On the Expressive Power of Deep Learning: A Tensor Analysis

paper_content:

It has long been conjectured that hypotheses spaces suitable for data that is compositional in nature, such as text or images, may be more efficiently represented with deep hierarchical networks than with shallow ones. Despite the vast empirical evidence supporting this belief, theoretical justifications to date are limited. In particular, they do not account for the locality, sharing and pooling constructs of convolutional networks, the most successful deep learning architecture to date. In this work we derive a deep network architecture based on arithmetic circuits that inherently employs locality, sharing and pooling. An equivalence between the networks and hierarchical tensor factorizations is established. We show that a shallow network corresponds to CP (rank-1) decomposition, whereas a deep network corresponds to Hierarchical Tucker decomposition. Using tools from measure theory and matrix algebra, we prove that besides a negligible set, all functions that can be implemented by a deep network of polynomial size, require exponential size in order to be realized (or even approximated) by a shallow network. Since log-space computation transforms our networks into SimNets, the result applies directly to a deep learning architecture demonstrating promising empirical performance. The construction and theory developed in this paper shed new light on various practices and ideas employed by the deep learning community.
---
paper_title: Notes on Hierarchical Splines, DCLNs and i-theory

paper_content:

We define an extension of classical additive splines for multivariate function approximation that we call hierarchical splines. We show that the case of hierarchical, additive, piece-wise linear splines includes present-day Deep Convolutional Learning Networks (DCLNs) with linear rectifers and pooling (sum or max). We discuss how these observations together with i-theory may provide a framework for a general theory of deep networks.
---
paper_title: Approximation theory of the MLP model in neural networks

paper_content:

In this survey we discuss various approximation-theoretic problems that arise in the multilayer feedforward perceptron (MLP) model in neural networks. The MLP model is one of the more popular and practical of the many neural network models. Mathematically it is also one of the simpler models. Nonetheless the mathematics of this model is not well understood, and many of these problems are approximation-theoretic in character. Most of the research we will discuss is of very recent vintage. We will report on what has been done and on various unanswered questions. We will not be presenting practical (algorithmic) methods. We will, however, be exploring the capabilities and limitations of this model.
---
paper_title: Limitations of the approximation capabilities of neural networks with one hidden layer

paper_content:

AbstractLets≥1 be an integer andW be the class of all functions having integrable partial derivatives on [0, 1]s. We are interested in the minimum number of neurons in a neural network with a single hidden layer required in order to provide a mean approximation order of a preassignedε>0 to each function inW. We prove that this number cannot be ::: $$\mathcal{O}( \in ^{ - s} log(1/ \in ))$$ ::: if a spline-like localization is required. This cannot be improved even if one allows different neurons to evaluate different activation functions, even depending upon the target function. Nevertheless, for anyδ>0, a network with ::: $$\mathcal{O}( \in ^{ - s - \delta } )$$ ::: neurons can be constructed to provide this order of approximation, with localization. Analogous results are also valid for otherLp norms.
---
paper_title: Hierarchical models of object recognition in cortex

paper_content:

Visual processing in cortex is classically modeled as a hierarchy of increasingly sophisticated representations, naturally extending the model of simple to complex cells of Hubel and Wiesel. Surprisingly, little quantitative modeling has been done to explore the biological feasibility of this class of models to explain aspects of higher-level visual processing such as object recognition. We describe a new hierarchical model consistent with physiological data from inferotemporal cortex that accounts for this complex visual task and makes testable predictions. The model is based on a MAX-like operation applied to inputs to certain cortical neurons that may have a general role in cortical function.
---
paper_title: Unsupervised learning of invariant representations

paper_content:

The present phase of Machine Learning is characterized by supervised learning algorithms relying on large sets of labeled examples ( n ź ∞ ). The next phase is likely to focus on algorithms capable of learning from very few labeled examples ( n ź 1 ), like humans seem able to do. We propose an approach to this problem and describe the underlying theory, based on the unsupervised, automatic learning of a "good" representation for supervised learning, characterized by small sample complexity. We consider the case of visual object recognition, though the theory also applies to other domains like speech. The starting point is the conjecture, proved in specific cases, that image representations which are invariant to translation, scaling and other transformations can considerably reduce the sample complexity of learning. We prove that an invariant and selective signature can be computed for each image or image patch: the invariance can be exact in the case of group transformations and approximate under non-group transformations. A module performing filtering and pooling, like the simple and complex cells described by Hubel and Wiesel, can compute such signature. The theory offers novel unsupervised learning algorithms for "deep" architectures for image and speech recognition. We conjecture that the main computational goal of the ventral stream of visual cortex is to provide a hierarchical representation of new objects/images which is invariant to transformations, stable, and selective for recognition-and show how this representation may be continuously learned in an unsupervised way during development and visual experience.
---
paper_title: Optimal nonlinear approximation

paper_content:

We introduce a definition of nonlinear n-widths and then determine the n-widths of the unit ball of the Sobolev spaceW p r inLq. We prove that in the sense of these widths the manifold of splines of fixed degree with n free knots is optimal for approximating functions in these Sobolev spaces.
---
paper_title: Learning Real and Boolean Functions: When Is Deep Better Than Shallow

paper_content:

This work was supported by the Center for Brains, Minds and Machines ::: (CBMM), funded by NSF STC award CCF 1231216. HNM was supported in ::: part by ARO Grant W911NF-15-1-0385.
---
paper_title: Learning Real and Boolean Functions: When Is Deep Better Than Shallow

paper_content:

This work was supported by the Center for Brains, Minds and Machines ::: (CBMM), funded by NSF STC award CCF 1231216. HNM was supported in ::: part by ARO Grant W911NF-15-1-0385.
---
paper_title: Notes on Hierarchical Splines, DCLNs and i-theory

paper_content:

We define an extension of classical additive splines for multivariate function approximation that we call hierarchical splines. We show that the case of hierarchical, additive, piece-wise linear splines includes present-day Deep Convolutional Learning Networks (DCLNs) with linear rectifers and pooling (sum or max). We discuss how these observations together with i-theory may provide a framework for a general theory of deep networks.
---
paper_title: I-theory on depth vs width: hierarchical function composition

paper_content:

Deep learning networks with convolution, pooling and subsampling are a special case of hierarchical architectures, which can be represented by trees (such as binary trees). Hierarchical as well as shallow networks can approximate functions of several variables, in particular those that are compositions of low dimensional functions. We show that the power of a deep network architecture with respect to a shallow network is rather independent of the specific nonlinear operations in the network and depends instead on the the behavior of the VC-dimension. A shallow network can approximate compositional functions with the same error of a deep network but at the cost of a VC-dimension that is exponential instead than quadratic in the dimensionality of the function. To complete the argument we argue that there exist visual computations that are intrinsically compositional. In particular, we prove that recognition invariant to translation cannot be computed by shallow networks in the presence of clutter. Finally, a general framework that includes the compositional case is sketched. The key condition that allows tall, thin networks to be nicer that short, fat networks is that the target input-output function must be sparse in a certain technical sense. This work was supported by the Center for Brains, Minds and Machines (CBMM), funded by NSF STC award CCF 1231216. I-theory on depth vs width: hierarchical function composition Tomaso Poggio with Fabio Anselmi and Lorenzo Rosasco
---
paper_title: Adam: A Method for Stochastic Optimization

paper_content:

We introduce Adam, an algorithm for first-order gradient-based optimization of stochastic objective functions, based on adaptive estimates of lower-order moments. The method is straightforward to implement, is computationally efficient, has little memory requirements, is invariant to diagonal rescaling of the gradients, and is well suited for problems that are large in terms of data and/or parameters. The method is also appropriate for non-stationary objectives and problems with very noisy and/or sparse gradients. The hyper-parameters have intuitive interpretations and typically require little tuning. Some connections to related algorithms, on which Adam was inspired, are discussed. We also analyze the theoretical convergence properties of the algorithm and provide a regret bound on the convergence rate that is comparable to the best known results under the online convex optimization framework. Empirical results demonstrate that Adam works well in practice and compares favorably to other stochastic optimization methods. Finally, we discuss AdaMax, a variant of Adam based on the infinity norm.
---
paper_title: Breaking the Curse of Dimensionality with Convex Neural Networks

paper_content:

We consider neural networks with a single hidden layer and non-decreasing homogeneous activa-tion functions like the rectified linear units. By letting the number of hidden units grow unbounded and using classical non-Euclidean regularization tools on the output weights, we provide a detailed theoretical analysis of their generalization performance, with a study of both the approximation and the estimation errors. We show in particular that they are adaptive to unknown underlying linear structures, such as the dependence on the projection of the input variables onto a low-dimensional subspace. Moreover, when using sparsity-inducing norms on the input weights, we show that high-dimensional non-linear variable selection may be achieved, without any strong assumption regarding the data and with a total number of variables potentially exponential in the number of ob-servations. In addition, we provide a simple geometric interpretation to the non-convex problem of addition of a new unit, which is the core potentially hard computational element in the framework of learning from continuously many basis functions. We provide simple conditions for convex relaxations to achieve the same generalization error bounds, even when constant-factor approxi-mations cannot be found (e.g., because it is NP-hard such as for the zero-homogeneous activation function). We were not able to find strong enough convex relaxations and leave open the existence or non-existence of polynomial-time algorithms.
---
paper_title: Approximation theory of the MLP model in neural networks

paper_content:

In this survey we discuss various approximation-theoretic problems that arise in the multilayer feedforward perceptron (MLP) model in neural networks. The MLP model is one of the more popular and practical of the many neural network models. Mathematically it is also one of the simpler models. Nonetheless the mathematics of this model is not well understood, and many of these problems are approximation-theoretic in character. Most of the research we will discuss is of very recent vintage. We will report on what has been done and on various unanswered questions. We will not be presenting practical (algorithmic) methods. We will, however, be exploring the capabilities and limitations of this model.
---
paper_title: Random search for hyper-parameter optimization

paper_content:

Grid search and manual search are the most widely used strategies for hyper-parameter optimization. This paper shows empirically and theoretically that randomly chosen trials are more efficient for hyper-parameter optimization than trials on a grid. Empirical evidence comes from a comparison with a large previous study that used grid search and manual search to configure neural networks and deep belief networks. Compared with neural networks configured by a pure grid search, we find that random search over the same domain is able to find models that are as good or better within a small fraction of the computation time. Granting random search the same computational budget, random search finds better models by effectively searching a larger, less promising configuration space. Compared with deep belief networks configured by a thoughtful combination of manual search and grid search, purely random search over the same 32-dimensional configuration space found statistically equal performance on four of seven data sets, and superior performance on one of seven. A Gaussian process analysis of the function from hyper-parameters to validation set performance reveals that for most data sets only a few of the hyper-parameters really matter, but that different hyper-parameters are important on different data sets. This phenomenon makes grid search a poor choice for configuring algorithms for new data sets. Our analysis casts some light on why recent "High Throughput" methods achieve surprising success--they appear to search through a large number of hyper-parameters because most hyper-parameters do not matter much. We anticipate that growing interest in large hierarchical models will place an increasing burden on techniques for hyper-parameter optimization; this work shows that random search is a natural baseline against which to judge progress in the development of adaptive (sequential) hyper-parameter optimization algorithms.
---
paper_title: On the tractability of multivariate integration and approximation by neural networks

paper_content:

Let q ≥ 1 be an integer, Q be a Borel subset of the Euclidean space Rq, µ be a probability measure on Q, and F be a class of real valued, µ-integrable functions on Q. The complexity problem of approximating ∫ f dµ using quasi-Monte Carlo methods is to estimate en(F,µ)=x1,.....xn∈Q sup f ∈F|∫ f dµ-1/n Σk=1nf(xk)|. The problem is said to be tractable if there exist constants c,α,β independent of q (but possibly dependent on µ and F) such that en(F,µ)≤cqαn-β. We explore different regions (including manifolds), function classes, and measures for which this problem is tractable. Our results include tractability theorems for integration with respect to non-tensor product measures, and over unbounded and/or non-tensor product subsets, including the unit spheres of Rq with respect to various norms. We discuss applications to approximation capabilities of neural and radial basis function networks.
---
paper_title: Representation Benefits of Deep Feedforward Networks

paper_content:

This note provides a family of classification problems, indexed by a positive integer $k$, where all shallow networks with fewer than exponentially (in $k$) many nodes exhibit error at least $1/6$, whereas a deep network with 2 nodes in each of $2k$ layers achieves zero error, as does a recurrent network with 3 distinct nodes iterated $k$ times. The proof is elementary, and the networks are standard feedforward networks with ReLU (Rectified Linear Unit) nonlinearities.
---
paper_title: Why does deep and cheap learning work so well?

paper_content:

We show how the success of deep learning could depend not only on mathematics but also on physics: although well-known mathematical theorems guarantee that neural networks can approximate arbitrary functions well, the class of functions of practical interest can frequently be approximated through"cheap learning"with exponentially fewer parameters than generic ones. We explore how properties frequently encountered in physics such as symmetry, locality, compositionality, and polynomial log-probability translate into exceptionally simple neural networks. We further argue that when the statistical process generating the data is of a certain hierarchical form prevalent in physics and machine-learning, a deep neural network can be more efficient than a shallow one. We formalize these claims using information theory and discuss the relation to the renormalization group. We prove various"no-flattening theorems"showing when efficient linear deep networks cannot be accurately approximated by shallow ones without efficiency loss, for example, we show that $n$ variables cannot be multiplied using fewer than 2^n neurons in a single hidden layer.
---
paper_title: Neural Networks for Localized Approximation

paper_content:

We prove that feedforward artificial neural networks with a single hidden layer and an ideal sigmoidal response function cannot provide localized approximation in a Euclidean space of dimension higher than one. We also show that networks with two hidden layers can be designed to provide localized approximation. Since wavelet bases are most effective for local approximation, we give a discussion of the implementation of spline wavelets using multilayered networks where the response function is a sigmoidal function of order at least two.
---
paper_title: Approximation theory of the MLP model in neural networks

paper_content:

In this survey we discuss various approximation-theoretic problems that arise in the multilayer feedforward perceptron (MLP) model in neural networks. The MLP model is one of the more popular and practical of the many neural network models. Mathematically it is also one of the simpler models. Nonetheless the mathematics of this model is not well understood, and many of these problems are approximation-theoretic in character. Most of the research we will discuss is of very recent vintage. We will report on what has been done and on various unanswered questions. We will not be presenting practical (algorithmic) methods. We will, however, be exploring the capabilities and limitations of this model.
---
paper_title: Limitations of the approximation capabilities of neural networks with one hidden layer

paper_content:

AbstractLets≥1 be an integer andW be the class of all functions having integrable partial derivatives on [0, 1]s. We are interested in the minimum number of neurons in a neural network with a single hidden layer required in order to provide a mean approximation order of a preassignedε>0 to each function inW. We prove that this number cannot be ::: $$\mathcal{O}( \in ^{ - s} log(1/ \in ))$$ ::: if a spline-like localization is required. This cannot be improved even if one allows different neurons to evaluate different activation functions, even depending upon the target function. Nevertheless, for anyδ>0, a network with ::: $$\mathcal{O}( \in ^{ - s - \delta } )$$ ::: neurons can be constructed to provide this order of approximation, with localization. Analogous results are also valid for otherLp norms.
---
paper_title: The Power of Depth for Feedforward Neural Networks

paper_content:

We show that there is a simple (approximately radial) function on $\reals^d$, expressible by a small 3-layer feedforward neural networks, which cannot be approximated by any 2-layer network, to more than a certain constant accuracy, unless its width is exponential in the dimension. The result holds for virtually all known activation functions, including rectified linear units, sigmoids and thresholds, and formally demonstrates that depth -- even if increased by 1 -- can be exponentially more valuable than width for standard feedforward neural networks. Moreover, compared to related results in the context of Boolean functions, our result requires fewer assumptions, and the proof techniques and construction are very different.
---
paper_title: Constant depth circuits, Fourier transform, and learnability

paper_content:

Boolean functions in AC/sup O/ are studied using the harmonic analysis of the cube. The main result is that an AC/sup O/ Boolean function has almost all of its power spectrum on the low-order coefficients. This result implies the following properties of functions in AC/sup O/: functions in AC/sup O/ have low average sensitivity; they can be approximated well be a real polynomial of low degree; they cannot be pseudorandom function generators and their correlation with any polylog-wide independent probability distribution is small. An O(n/sup polylog(/ /sup sup)/ /sup (n)/)-time algorithm for learning functions in AC/sup O/ is obtained. The algorithm observed the behavior of an AC/sup O/ function on O(n/sup polylog/ /sup (n)/) randomly chosen inputs and derives a good approximation for the Fourier transform of the function. This allows it to predict with high probability the value of the function on other randomly chosen inputs. >
---
paper_title: Steps Towards a Theory of Visual Information: Active Perception, Signal-to-Symbol Conversion and the Interplay Between Sensing and Control

paper_content:

This manuscript describes the elements of a theory of information tailored to control and decision tasks and specifically to visual data. The concept of Actionable Information is described, that relates to a notion of information championed by J. Gibson, and a notion of "complete information" that relates to the minimal sufficient statistics of a complete representation. It is shown that the "actionable information gap" between the two can be reduced by exercising control on the sensing process. Thus, senging, control and information are inextricably tied. This has consequences in the so-called "signal-to-symbol barrier" problem, as well as in the analysis and design of active sensing systems. It has ramifications in vision-based control, navigation, 3-D reconstruction and rendering, as well as detection, localization, recognition and categorization of objects and scenes in live video. ::: This manuscript has been developed from a set of lecture notes for a summer course at the First International Computer Vision Summer School (ICVSS) in Scicli, Italy, in July of 2008. They were later expanded and amended for subsequent lectures in the same School in July 2009. Starting on November 1, 2009, they were further expanded for a special topics course, CS269, taught at UCLA in the Spring term of 2010.
---
paper_title: Unsupervised learning of invariant representations

paper_content:

The present phase of Machine Learning is characterized by supervised learning algorithms relying on large sets of labeled examples ( n ź ∞ ). The next phase is likely to focus on algorithms capable of learning from very few labeled examples ( n ź 1 ), like humans seem able to do. We propose an approach to this problem and describe the underlying theory, based on the unsupervised, automatic learning of a "good" representation for supervised learning, characterized by small sample complexity. We consider the case of visual object recognition, though the theory also applies to other domains like speech. The starting point is the conjecture, proved in specific cases, that image representations which are invariant to translation, scaling and other transformations can considerably reduce the sample complexity of learning. We prove that an invariant and selective signature can be computed for each image or image patch: the invariance can be exact in the case of group transformations and approximate under non-group transformations. A module performing filtering and pooling, like the simple and complex cells described by Hubel and Wiesel, can compute such signature. The theory offers novel unsupervised learning algorithms for "deep" architectures for image and speech recognition. We conjecture that the main computational goal of the ventral stream of visual cortex is to provide a hierarchical representation of new objects/images which is invariant to transformations, stable, and selective for recognition-and show how this representation may be continuously learned in an unsupervised way during development and visual experience.
---
paper_title: On the Expressive Power of Deep Learning: A Tensor Analysis

paper_content:

It has long been conjectured that hypotheses spaces suitable for data that is compositional in nature, such as text or images, may be more efficiently represented with deep hierarchical networks than with shallow ones. Despite the vast empirical evidence supporting this belief, theoretical justifications to date are limited. In particular, they do not account for the locality, sharing and pooling constructs of convolutional networks, the most successful deep learning architecture to date. In this work we derive a deep network architecture based on arithmetic circuits that inherently employs locality, sharing and pooling. An equivalence between the networks and hierarchical tensor factorizations is established. We show that a shallow network corresponds to CP (rank-1) decomposition, whereas a deep network corresponds to Hierarchical Tucker decomposition. Using tools from measure theory and matrix algebra, we prove that besides a negligible set, all functions that can be implemented by a deep network of polynomial size, require exponential size in order to be realized (or even approximated) by a shallow network. Since log-space computation transforms our networks into SimNets, the result applies directly to a deep learning architecture demonstrating promising empirical performance. The construction and theory developed in this paper shed new light on various practices and ideas employed by the deep learning community.
---
paper_title: Hierarchical Singular Value Decomposition of Tensors

paper_content:

We define the hierarchical singular value decomposition (SVD) for tensors of order $d\geq2$. This hierarchical SVD has properties like the matrix SVD (and collapses to the SVD in $d=2$), and we prove these. In particular, one can find low rank (almost) best approximations in a hierarchical format ($\mathcal{H}$-Tucker) which requires only $\mathcal{O}((d-1)k^3+dnk)$ parameters, where $d$ is the order of the tensor, $n$ the size of the modes, and $k$ the (hierarchical) rank. The $\mathcal{H}$-Tucker format is a specialization of the Tucker format and it contains as a special case all (canonical) rank $k$ tensors. Based on this new concept of a hierarchical SVD we present algorithms for hierarchical tensor calculations allowing for a rigorous error analysis. The complexity of the truncation (finding lower rank approximations to hierarchical rank $k$ tensors) is in $\mathcal{O}((d-1)k^4+dnk^2)$ and the attainable accuracy is just 2-3 digits less than machine precision.
---
paper_title: Human-level concept learning through probabilistic program induction

paper_content:

People learning new concepts can often generalize successfully from just a single example, yet machine learning algorithms typically require tens or hundreds of examples to perform with similar accuracy. People can also use learned concepts in richer ways than conventional algorithms—for action, imagination, and explanation. We present a computational model that captures these human learning abilities for a large class of simple visual concepts: handwritten characters from the world’s alphabets. The model represents concepts as simple programs that best explain observed examples under a Bayesian criterion. On a challenging one-shot classification task, the model achieves human-level performance while outperforming recent deep learning approaches. We also present several “visual Turing tests” probing the model’s creative generalization abilities, which in many cases are indistinguishable from human behavior.
---
paper_title: Bounds for linear multi-task learning

paper_content:

We give dimension-free and data-dependent bounds for linear multi-task learning where a common linear operator is chosen to preprocess data for a vector of task specific linear-thresholding classifiers. The complexity penalty of multi-task learning is bounded by a simple expression involving the margins of the task-specific classifiers, the Hilbert-Schmidt norm of the selected preprocessor and the Hilbert-Schmidt norm of the covariance operator for the total mixture of all task distributions, or, alternatively, the Frobenius norm of the total Gramian matrix for the data-dependent version. The results can be compared to state-of-the-art results on linear single-task learning.
---
paper_title: Deep Convolutional Networks are Hierarchical Kernel Machines

paper_content:

In i-theory a typical layer of a hierarchical architecture consists of HW modules pooling the dot products of the inputs to the layer with the transformations of a few templates under a group. Such layers include as special cases the convolutional layers of Deep Convolutional Networks (DCNs) as well as the non-convolutional layers (when the group contains only the identity). Rectifying nonlinearities -- which are used by present-day DCNs -- are one of the several nonlinearities admitted by i-theory for the HW module. We discuss here the equivalence between group averages of linear combinations of rectifying nonlinearities and an associated kernel. This property implies that present-day DCNs can be exactly equivalent to a hierarchy of kernel machines with pooling and non-pooling layers. Finally, we describe a conjecture for theoretically understanding hierarchies of such modules. A main consequence of the conjecture is that hierarchies of trained HW modules minimize memory requirements while computing a selective and invariant representation.
---
paper_title: Perceptrons: An Introduction to Computational Geometry

paper_content:

Cambridge, Mass.: MIT Press, 1972. 2nd. ed. The book's aim is to seek general results from the close study of abstract version of devices known as perceptrons
---
paper_title: On the representation of multi-input systems: Computational properties of polynomial algorithms

paper_content:

This paper introduces a theoretical framework for characterizing and classifying simple parallel algorithms and systems with many inputs, for example an array of photoreceptors. The polynomial representation (Taylor series development) of a large class of operators is introduced and its range of validity discussed. The problems involved in the polynomial approximation of systems are also briefly reviewed. Symmetry properties of the input-output map and their implications for the system structure (i.e. its kernels) are studied. Finally, the computational properties of polynomial mappings are characterized.
---
paper_title: Why does deep and cheap learning work so well?

paper_content:

We show how the success of deep learning could depend not only on mathematics but also on physics: although well-known mathematical theorems guarantee that neural networks can approximate arbitrary functions well, the class of functions of practical interest can frequently be approximated through"cheap learning"with exponentially fewer parameters than generic ones. We explore how properties frequently encountered in physics such as symmetry, locality, compositionality, and polynomial log-probability translate into exceptionally simple neural networks. We further argue that when the statistical process generating the data is of a certain hierarchical form prevalent in physics and machine-learning, a deep neural network can be more efficient than a shallow one. We formalize these claims using information theory and discuss the relation to the renormalization group. We prove various"no-flattening theorems"showing when efficient linear deep networks cannot be accurately approximated by shallow ones without efficiency loss, for example, we show that $n$ variables cannot be multiplied using fewer than 2^n neurons in a single hidden layer.
---
paper_title: Origins of scaling in natural images

paper_content:

Abstract One of the most robust qualities of our visual world is the scale invariance of natural images. Not only has scaling been found in different visual environments, but the phenomenon also appears to be calibration-independent. This paper proposes a simple property of natural images which explains this robustness they are collages of regions corresponding to statistically independent “objects”. Evidence is provided for these objects having a power-law distribution of sizes within images, from which follows scaling in natural images. It is commonly suggested that scaling instead results from edges, each with power spectrum 1k/2 . This hypothesis is refuted by example.
---
paper_title: Notes on Hierarchical Splines, DCLNs and i-theory

paper_content:

We define an extension of classical additive splines for multivariate function approximation that we call hierarchical splines. We show that the case of hierarchical, additive, piece-wise linear splines includes present-day Deep Convolutional Learning Networks (DCLNs) with linear rectifers and pooling (sum or max). We discuss how these observations together with i-theory may provide a framework for a general theory of deep networks.
---
paper_title: I-theory on depth vs width: hierarchical function composition

paper_content:

Deep learning networks with convolution, pooling and subsampling are a special case of hierarchical architectures, which can be represented by trees (such as binary trees). Hierarchical as well as shallow networks can approximate functions of several variables, in particular those that are compositions of low dimensional functions. We show that the power of a deep network architecture with respect to a shallow network is rather independent of the specific nonlinear operations in the network and depends instead on the the behavior of the VC-dimension. A shallow network can approximate compositional functions with the same error of a deep network but at the cost of a VC-dimension that is exponential instead than quadratic in the dimensionality of the function. To complete the argument we argue that there exist visual computations that are intrinsically compositional. In particular, we prove that recognition invariant to translation cannot be computed by shallow networks in the presence of clutter. Finally, a general framework that includes the compositional case is sketched. The key condition that allows tall, thin networks to be nicer that short, fat networks is that the target input-output function must be sparse in a certain technical sense. This work was supported by the Center for Brains, Minds and Machines (CBMM), funded by NSF STC award CCF 1231216. I-theory on depth vs width: hierarchical function composition Tomaso Poggio with Fabio Anselmi and Lorenzo Rosasco
---
paper_title: Why does deep and cheap learning work so well?

paper_content:

We show how the success of deep learning could depend not only on mathematics but also on physics: although well-known mathematical theorems guarantee that neural networks can approximate arbitrary functions well, the class of functions of practical interest can frequently be approximated through"cheap learning"with exponentially fewer parameters than generic ones. We explore how properties frequently encountered in physics such as symmetry, locality, compositionality, and polynomial log-probability translate into exceptionally simple neural networks. We further argue that when the statistical process generating the data is of a certain hierarchical form prevalent in physics and machine-learning, a deep neural network can be more efficient than a shallow one. We formalize these claims using information theory and discuss the relation to the renormalization group. We prove various"no-flattening theorems"showing when efficient linear deep networks cannot be accurately approximated by shallow ones without efficiency loss, for example, we show that $n$ variables cannot be multiplied using fewer than 2^n neurons in a single hidden layer.
---
paper_title: Notes on Hierarchical Splines, DCLNs and i-theory

paper_content:

We define an extension of classical additive splines for multivariate function approximation that we call hierarchical splines. We show that the case of hierarchical, additive, piece-wise linear splines includes present-day Deep Convolutional Learning Networks (DCLNs) with linear rectifers and pooling (sum or max). We discuss how these observations together with i-theory may provide a framework for a general theory of deep networks.
---
paper_title: Regularization Theory and Neural Networks Architectures

paper_content:

We had previously shown that regularization principles lead to approximation schemes that are equivalent to networks with one layer of hidden units, called regularization networks . In particular, standard smoothness functionals lead to a subclass of regularization networks, the well known radial basis functions approximation schemes. This paper shows that regularization networks encompass a much broader range of approximation schemes, including many of the popular general additive models and some of the neural networks. In particular, we introduce new classes of smoothness functionals that lead to different classes of basis functions. Additive splines as well as some tensor product splines can be obtained from appropriate classes of smoothness functionals. Furthermore, the same generalization that extends radial basis functions (RBF) to hyper basis functions (HBF) also leads from additive models to ridge approximation models, containing as special cases Breiman's hinge functions, some forms of projection pursuit regression, and several types of neural networks. We propose to use the term generalized regularization networks for this broad class of approximation schemes that follow from an extension of regularization. In the probabilistic interpretation of regularization, the different classes of basis functions correspond to different classes of prior probabilities on the approximating function spaces, and therefore to different types of smoothness assumptions. In summary, different multilayer networks with one hidden layer, which we collectively call generalized regularization networks, correspond to different classes of priors and associated smoothness functionals in a classical regularization principle. Three broad classes are (1) radial basis functions that can be generalized to hyper basis functions, (2) some tensor product splines, and (3) additive splines that can be generalized to schemes of the type of ridge approximation, hinge functions, and several perceptron-like neural networks with one hidden layer.
---
paper_title: Regularization Theory and Neural Networks Architectures

paper_content:

We had previously shown that regularization principles lead to approximation schemes that are equivalent to networks with one layer of hidden units, called regularization networks . In particular, standard smoothness functionals lead to a subclass of regularization networks, the well known radial basis functions approximation schemes. This paper shows that regularization networks encompass a much broader range of approximation schemes, including many of the popular general additive models and some of the neural networks. In particular, we introduce new classes of smoothness functionals that lead to different classes of basis functions. Additive splines as well as some tensor product splines can be obtained from appropriate classes of smoothness functionals. Furthermore, the same generalization that extends radial basis functions (RBF) to hyper basis functions (HBF) also leads from additive models to ridge approximation models, containing as special cases Breiman's hinge functions, some forms of projection pursuit regression, and several types of neural networks. We propose to use the term generalized regularization networks for this broad class of approximation schemes that follow from an extension of regularization. In the probabilistic interpretation of regularization, the different classes of basis functions correspond to different classes of prior probabilities on the approximating function spaces, and therefore to different types of smoothness assumptions. In summary, different multilayer networks with one hidden layer, which we collectively call generalized regularization networks, correspond to different classes of priors and associated smoothness functionals in a classical regularization principle. Three broad classes are (1) radial basis functions that can be generalized to hyper basis functions, (2) some tensor product splines, and (3) additive splines that can be generalized to schemes of the type of ridge approximation, hinge functions, and several perceptron-like neural networks with one hidden layer.
---
paper_title: Regularization Theory and Neural Networks Architectures

paper_content:

We had previously shown that regularization principles lead to approximation schemes that are equivalent to networks with one layer of hidden units, called regularization networks . In particular, standard smoothness functionals lead to a subclass of regularization networks, the well known radial basis functions approximation schemes. This paper shows that regularization networks encompass a much broader range of approximation schemes, including many of the popular general additive models and some of the neural networks. In particular, we introduce new classes of smoothness functionals that lead to different classes of basis functions. Additive splines as well as some tensor product splines can be obtained from appropriate classes of smoothness functionals. Furthermore, the same generalization that extends radial basis functions (RBF) to hyper basis functions (HBF) also leads from additive models to ridge approximation models, containing as special cases Breiman's hinge functions, some forms of projection pursuit regression, and several types of neural networks. We propose to use the term generalized regularization networks for this broad class of approximation schemes that follow from an extension of regularization. In the probabilistic interpretation of regularization, the different classes of basis functions correspond to different classes of prior probabilities on the approximating function spaces, and therefore to different types of smoothness assumptions. In summary, different multilayer networks with one hidden layer, which we collectively call generalized regularization networks, correspond to different classes of priors and associated smoothness functionals in a classical regularization principle. Three broad classes are (1) radial basis functions that can be generalized to hyper basis functions, (2) some tensor product splines, and (3) additive splines that can be generalized to schemes of the type of ridge approximation, hinge functions, and several perceptron-like neural networks with one hidden layer.
---
paper_title: Approximation theory of the MLP model in neural networks

paper_content:

In this survey we discuss various approximation-theoretic problems that arise in the multilayer feedforward perceptron (MLP) model in neural networks. The MLP model is one of the more popular and practical of the many neural network models. Mathematically it is also one of the simpler models. Nonetheless the mathematics of this model is not well understood, and many of these problems are approximation-theoretic in character. Most of the research we will discuss is of very recent vintage. We will report on what has been done and on various unanswered questions. We will not be presenting practical (algorithmic) methods. We will, however, be exploring the capabilities and limitations of this model.
---
paper_title: Approximation theory of the MLP model in neural networks

paper_content:

In this survey we discuss various approximation-theoretic problems that arise in the multilayer feedforward perceptron (MLP) model in neural networks. The MLP model is one of the more popular and practical of the many neural network models. Mathematically it is also one of the simpler models. Nonetheless the mathematics of this model is not well understood, and many of these problems are approximation-theoretic in character. Most of the research we will discuss is of very recent vintage. We will report on what has been done and on various unanswered questions. We will not be presenting practical (algorithmic) methods. We will, however, be exploring the capabilities and limitations of this model.
---
paper_title: I-theory on depth vs width: hierarchical function composition

paper_content:

Deep learning networks with convolution, pooling and subsampling are a special case of hierarchical architectures, which can be represented by trees (such as binary trees). Hierarchical as well as shallow networks can approximate functions of several variables, in particular those that are compositions of low dimensional functions. We show that the power of a deep network architecture with respect to a shallow network is rather independent of the specific nonlinear operations in the network and depends instead on the the behavior of the VC-dimension. A shallow network can approximate compositional functions with the same error of a deep network but at the cost of a VC-dimension that is exponential instead than quadratic in the dimensionality of the function. To complete the argument we argue that there exist visual computations that are intrinsically compositional. In particular, we prove that recognition invariant to translation cannot be computed by shallow networks in the presence of clutter. Finally, a general framework that includes the compositional case is sketched. The key condition that allows tall, thin networks to be nicer that short, fat networks is that the target input-output function must be sparse in a certain technical sense. This work was supported by the Center for Brains, Minds and Machines (CBMM), funded by NSF STC award CCF 1231216. I-theory on depth vs width: hierarchical function composition Tomaso Poggio with Fabio Anselmi and Lorenzo Rosasco
---
paper_title: Networks and the best approximation property

paper_content:

Networks can be considered as approximation schemes. Multilayer networks of the perceptron type can approximate arbitrarily well continuous functions (Cybenko 1988, 1989; Funahashi 1989; Stinchcombe and White 1989). We prove that networks derived from regularization theory and including Radial Basis Functions (Poggio and Girosi 1989), have a similar property. From the point of view of approximation theory, however, the property of approximating continuous functions arbitrarily well is not sufficient for characterizing good approximation schemes. More critical is the property ofbest approximation. The main result of this paper is that multilayer perceptron networks, of the type used in backpropagation, do not have the best approximation property. For regularization networks (in particular Radial Basis Function networks) we prove existence and uniqueness of best approximation.
---
paper_title: Representation Properties of Networks: Kolmogorov's Theorem Is Irrelevant

paper_content:

Many neural networks can be regarded as attempting to approximate a multivariate function in terms of one-input one-output units. This note considers the problem of an exact representation of nonlinear mappings in terms of simpler functions of fewer variables. We review Kolmogorov's theorem on the representation of functions of several variables in terms of functions of one variable and show that it is irrelevant in the context of networks for learning.
---
paper_title: Neural Network Learning: Theoretical Foundations

paper_content:

This important work describes recent theoretical advances in the study of artificial neural networks. It explores probabilistic models of supervised learning problems, and addresses the key statistical and computational questions. Chapters survey research on pattern classification with binary-output networks, including a discussion of the relevance of the Vapnik Chervonenkis dimension, and of estimates of the dimension for several neural network models. In addition, Anthony and Bartlett develop a model of classification by real-output networks, and demonstrate the usefulness of classification with a "large margin." The authors explain the role of scale-sensitive versions of the Vapnik Chervonenkis dimension in large margin classification, and in real prediction. Key chapters also discuss the computational complexity of neural network learning, describing a variety of hardness results, and outlining two efficient, constructive learning algorithms. The book is self-contained and accessible to researchers and graduate students in computer science, engineering, and mathematics.
---
paper_title: Adam: A Method for Stochastic Optimization

paper_content:

We introduce Adam, an algorithm for first-order gradient-based optimization of stochastic objective functions, based on adaptive estimates of lower-order moments. The method is straightforward to implement, is computationally efficient, has little memory requirements, is invariant to diagonal rescaling of the gradients, and is well suited for problems that are large in terms of data and/or parameters. The method is also appropriate for non-stationary objectives and problems with very noisy and/or sparse gradients. The hyper-parameters have intuitive interpretations and typically require little tuning. Some connections to related algorithms, on which Adam was inspired, are discussed. We also analyze the theoretical convergence properties of the algorithm and provide a regret bound on the convergence rate that is comparable to the best known results under the online convex optimization framework. Empirical results demonstrate that Adam works well in practice and compares favorably to other stochastic optimization methods. Finally, we discuss AdaMax, a variant of Adam based on the infinity norm.
---
paper_title: Random search for hyper-parameter optimization

paper_content:

Grid search and manual search are the most widely used strategies for hyper-parameter optimization. This paper shows empirically and theoretically that randomly chosen trials are more efficient for hyper-parameter optimization than trials on a grid. Empirical evidence comes from a comparison with a large previous study that used grid search and manual search to configure neural networks and deep belief networks. Compared with neural networks configured by a pure grid search, we find that random search over the same domain is able to find models that are as good or better within a small fraction of the computation time. Granting random search the same computational budget, random search finds better models by effectively searching a larger, less promising configuration space. Compared with deep belief networks configured by a thoughtful combination of manual search and grid search, purely random search over the same 32-dimensional configuration space found statistically equal performance on four of seven data sets, and superior performance on one of seven. A Gaussian process analysis of the function from hyper-parameters to validation set performance reveals that for most data sets only a few of the hyper-parameters really matter, but that different hyper-parameters are important on different data sets. This phenomenon makes grid search a poor choice for configuring algorithms for new data sets. Our analysis casts some light on why recent "High Throughput" methods achieve surprising success--they appear to search through a large number of hyper-parameters because most hyper-parameters do not matter much. We anticipate that growing interest in large hierarchical models will place an increasing burden on techniques for hyper-parameter optimization; this work shows that random search is a natural baseline against which to judge progress in the development of adaptive (sequential) hyper-parameter optimization algorithms.
---

Title: Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review

Section 1: A theory of deep learning
Description 1: Describe the three main theoretical questions about Deep Neural Networks, focusing especially on the power of the architecture and the conditions under which deep networks can avoid the curse of dimensionality.

Section 2: Previous theoretical work
Description 2: Review historical and recent theoretical works related to deep learning, including comparisons between shallow and deep networks and discussions of compositional functions and hierarchical models.

Section 3: Function approximation by deep networks
Description 3: Present theorems about the approximation properties of shallow and deep networks and conduct a comparison between the two.

Section 4: Degree of approximation
Description 4: Explain the general paradigm for determining network complexity required for approximating an unknown target function up to a given accuracy.

Section 5: Shallow and deep networks
Description 5: Characterize the conditions under which deep networks outperform shallow networks in approximating functions, with examples and visual representations.

Section 6: Shallow networks
Description 6: Provide theoretical results and bounds on the approximation properties of shallow networks.

Section 7: Deep hierarchically local networks
Description 7: Discuss the approximation capabilities of deep networks with hierarchical, local compositional architectures, presenting the main theorem and corollaries.

Section 8: Approximation results for shallow and deep networks with (non-smooth) ReLUs
Description 8: Extend the approximation results to networks with non-smooth ReLU activation functions, comparing them to those with smooth activations.

Section 9: Lower bounds and gaps
Description 9: Explore examples that illustrate the limitations of shallow networks in approximating compositional functions compared to deep networks, backed by formal proofs and lower bounds.

Section 10: Messy graphs and densely connected deep networks
Description 10: Analyze how deep networks do not need exact prior knowledge of the function structure and can still exploit compositionality even when not perfectly matching the graph of the function to be learned.

Section 11: Connections with the theory of Boolean functions
Description 11: Discuss the connections between deep networks and the theory of Boolean functions, including depth-breadth tradeoffs in circuit design.

Section 12: Notes on a theory of compositional computation
Description 12: Provide comments and conjectures on the implications and practical relevance of the theory of compositionality in deep networks.