A Selective Overview of Deep Learning

Introduction

Deep learning , in its simplest form, proposes the following compositional function class:

To get a better idea of the success of deep learning, let us take the ImageNet Challenge (also known as ILSVRC) as an example. In the classification task, one is given a training dataset consisting of 1.2 million color images with $1000$ categories, and the goal is to classify images based on the input pixels. The performance of a classifier is then evaluated on a test dataset of 100 thousand images, and in the end the top-5 errorThe algorithm makes an error if the true label is not contained in the $5$ predictions made by the algorithm. is reported. Table 1 highlights a few popular models and their corresponding performance. As can be seen, deep learning models (the second to the last rows) have a clear edge over shallow models (the first row) that fit linear models / tree-based models on handcrafted features. This significant improvement raises a foundational question:

Why is deep learning better than classical methods on tasks like image recognition?

It is widely acknowledged that two indispensable factors contribute to the success of deep learning, namely (1) huge datasets that often contain millions of samples and (2) immense computing power resulting from clusters of graphics processing units (GPUs). Admittedly, these resources are only recently available: the latter allows to train larger neural networks which reduces biases and the former enables variance reduction. However, these two alone are not sufficient to explain the mystery of deep learning due to some of its “dreadful” characteristics: (1) over-parametrization: the number of parameters in state-of-the-art deep learning models is often much larger than the sample size (see Table 1), which gives them the potential to overfit the training data, and (2) nonconvexity: even with the help of GPUs, training deep learning models is still NP-hard in the worst case due to the highly nonconvex loss function to minimize. In reality, these characteristics are far from nightmares. This sharp difference motivates us to take a closer look at the salient features of deep learning, which we single out a few below.

Deep learning expresses complicated nonlinearity through composing many nonlinear functions; see (1). The rationale for this multilayer structure is that, in many real-world datasets such as images, there are different levels of features and lower-level features are building blocks of higher-level ones. See for a visualization of trained features of convolutional neural nets; here in Figure 1, we sample and visualize weights from a pre-trained AlexNet model. This intuition is also supported by empirical results from physiology and neuroscience . The use of function composition marks a sharp difference from traditional statistical methods such as projection pursuit models and multi-index models . It is often observed that depth helps efficiently extract features that are representative of a dataset. In comparison, increasing width (e.g., number of basis functions) in a shallow model leads to less improvement. This suggests that deep learning models excel at representing a very different function space that is suitable for complex datasets.

1.2 Algorithmic regularization

The statistical performance of neural networks (e.g., test accuracy) depends heavily on the particular optimization algorithms used for training . This is very different from many classical statistical problems, where the related optimization problems are less complicated. For instance, when the associated optimization problem has a relatively simple structure (e.g., convex objective functions, linear constraints), the solution to the optimization problem can often be unambiguously computed and analyzed. However, in deep neural networks, due to over-parametrization, there are usually many local minima with different statistical performance . Nevertheless, common practice runs stochastic gradient descent with random initialization and finds model parameters with very good prediction accuracy.

1.3 Implicit prior learning

It is well observed that deep neural networks trained with only the raw inputs (e.g., pixels of images) can provide a useful representation of the data. This means that after training, the units of deep neural networks can represent features such as edges, corners, wheels, eyes, etc.; see . Importantly, the training process is automatic in the sense that no human knowledge is involved (other than hyper-parameter tuning). This is very different from traditional methods, where algorithms are designed after structural assumptions are posited. It is likely that training an over-parametrized model efficiently learns and incorporates the prior distribution p(\text{\boldmathx}) of the input, even though deep learning models are themselves discriminative models. With automatic representation of the prior distribution, deep learning typically performs well on similar datasets (but not very different ones) via transfer learning.

2 Towards theory of deep learning

Both errors can be small for deep learning (cf. Figure 2), which we explain below.

The approximation error is determined by the function class $\mathcal{F}$. Intuitively, the larger the class, the smaller the approximation error. Deep learning models use many layers of nonlinear functions (Figure 3)that can drive this error small. Indeed, in Section 5, we provide recent theoretical progress of its representation power. For example, deep models allow efficient representation of interactions among variable while shallow models cannot.

The above two points lead to the following heuristic explanation of the success of deep learning models. The large depth of deep neural nets and heavy over-parametrization lead to small or zero training errors, even when running simple algorithms with moderate number of iterations. In addition, these simple algorithms with moderate number of steps do not explore the entire function space and thus have limited complexities, which results in small generalization error with a large sample size. Thus, by combining the two aspects, it explains heuristically that the test error is also small.

3 Roadmap of the paper

We first introduce basic deep learning models in Sections 2–4, and then examine their representation power via the lens of approximation theory in Section 5. Section 6 is devoted to training algorithms and their ability of driving the training error small. Then we sample recent theoretical progress towards demystifying the generalization power of deep learning in Section 7. Along the way, we provide our own perspectives, and at the end we identify a few interesting questions for future research in Section 8. The goal of this paper is to present suggestive methods and results, rather than giving conclusive arguments (which is currently unlikely) or a comprehensive survey. We hope that our discussion serves as a stimulus for new statistics research.

Feed-forward neural networks

From the high level, deep neural networks (DNNs) use composition of a series of simple nonlinear functions to model nonlinearity

Other choices of activation functions include leaky ReLU, $\tanh$ function and the classical sigmoid function $(1+e^{-z})^{-1}$, which is less used now.

Given an output \text{\boldmathh}^{(L)} from the final hidden layer and a label $y$, we can define a loss function to minimize. A common loss function for classification problems is the multinomial logistic loss. Using the terminology of deep learning, we say that \text{\boldmathh}^{(L)} goes through an affine transformation and then the soft-max function:

Then the loss is defined to be the cross-entropy between the label $y$ (in the form of an indicator vector) and the score vector (f_{1}(\text{\boldmathx};\text{\boldmath\theta}),\ldots,f_{K}(\text{\boldmathx};\text{\boldmath\theta}))^{\top}, which is exactly the negative log-likelihood of the multinomial logistic regression model:

2 Back-propagation in computational graphs

Training neural networks follows the empirical risk minimization paradigm that minimizes the loss (e.g., (5)) over all the training data. This minimization is usually done via stochastic gradient descent (SGD). In a way similar to gradient descent, SGD starts from a certain initial value \text{\boldmath\theta}^{0} and then iteratively updates the parameters \text{\boldmath\theta}^{t} by moving it in the direction of the negative gradient. The difference is that, in each update, a small subsample $\mathcal{B}\subset[n]$ called a mini-batch—which is typically of size 32–512—is randomly drawn and the gradient calculation is only on $\mathcal{B}$ instead of the full batch $[n]$. This saves considerably the computational cost in calculation of gradient. By the law of large numbers, this stochastic gradient should be close to the full sample one, albeit with some random fluctuations. A pass of the whole training set is called an epoch. Usually, after several or tens of epochs, the error on a validation set levels off and training is complete. See Section 6 for more details and variants on training algorithms.

Gradient computation, however, is in general nontrivial for complex models, and it is susceptible to numerical instability for a model with large depth. Here, we introduce an efficient approach, namely back-propagation, for computing gradients in neural networks.

Back-propagation in computational graphs forms the foundations of popular deep learning programming softwares, including TensorFlow and PyTorch , which allows more efficient building and training of complex neural net models.

Popular models

Moving beyond vanilla feed-forward neural networks, we introduce two other popular deep learning models, namely, the convolutional neural networks (CNNs) and the recurrent neural networks (RNNs). One important characteristic shared by the two models is weight sharing, that is some model parameters are identical across locations in CNNs or across time in RNNs. This is related to the notion of translational invariance in CNNs and stationarity in RNNs. At the end of this section, we introduce a modular thinking for constructing more flexible neural nets.

The outputs of convolutional layers are then followed by nonlinear activation functions. In the ReLU case, we have

2 Recurrent neural networks

Recurrent neural nets (RNNs) are another family of powerful models, which are designed to process time series data and other sequence data. RNNs have successful applications in speech recognition , machine translation , genome sequencing , etc. The structure of an RNN naturally forms a computational graph, and can be easily combined with other structures such as CNNs to build large computational graph models for complex tasks. Here we introduce vanilla RNNs and improved variants such as long short-term memory (LSTM).

Suppose we have general time series inputs \text{\boldmathx}_{1},\text{\boldmathx}_{2},\ldots,\text{\boldmathx}_{T}. A vanilla RNN models the “hidden state” at time $t$ by a vector \text{\boldmathh}_{t}, which is subject to the recursive formula

One-to-many: a single input with multiple outputs; see Figure 8(a). A typical application is image captioning, where the input is an image and outputs are a series of words.

Many-to-one: multiple inputs with a single output; see Figure 8(b). One application is text sentiment classification, where the input is a series of words in a sentence and the output is a label (e.g., positive vs. negative).

Many-to-many: multiple inputs and outputs; see Figure 8(c). This is adopted in machine translation, where inputs are words of a source language (say Chinese) and outputs are words of a target language (say English).

As the case with feed-forward neural nets, we minimize a loss function using back-propagation, where the loss is typically

2.2 GRUs and LSTM

There are two improved variants that alleviate the above issue: gated recurrent units (GRUs) and long short-term memory (LSTM) .

A GRU refines the recursive formula (13) by introducing gates, which are vectors of the same length as \text{\boldmathh}_{t}. The gates, which take values in $$elementwise, multiply with$\text{\boldmath$h$}_{t-1}$ elementwise and determine how much they keep the old hidden states.

Here we only discuss LSTM in detail. Denote by $\odot$ the element-wise multiplication. We have a recursive formula in replace of (13):

2.3 Multilayer RNNs

Multilayer RNNs are generalization of the one-hidden-layer RNN discussed above. Figure 9 shows a vanilla RNN with two hidden layers. In place of (13), the recursive formula for an RNN with $L$ hidden layers now reads

Note that a multilayer RNN has two dimensions: the sequence length $T$ and depth $L$. Two special cases are the feed-forward neural nets (where $T=1$) introduced in Section 2, and RNNs with one hidden layer (where $L=1$). Multilayer RNNs usually do not have very large depth (e.g., $2$–$5$), since $T$ is already very large.

Finally, we remark that CNNs, RNNs, and other neural nets can be easily combined to tackle tasks that involve different sources of input data. For example, in image captioning, the images are first processed through a CNN, and then the high-level features are fed into an RNN as inputs. Theses neural nets combined together form a large computational graph, so they can be trained using back-propagation. This generic training method provides much flexibility in various applications.

3 Modules

Deep neural nets are essentially composition of many nonlinear functions. A component function may be designed to have specific properties in a given task, and it can be itself resulted from composing a few simpler functions. In LSTM, we have seen that the building block consists of several intermediate variables, including cell states and forget gates that can capture long-term dependency and alleviate numerical issues.

This leads to the idea of designing modules for building more complex neural net models. Desirable modules usually have low computational costs, alleviate numerical issues in training, and lead to good statistical accuracy. Since modules and the resulting neural net models form computational graphs, training follows the same principle briefly described in Section 2.

Here, we use the examples of Inception and skip connections to illustrate the ideas behind modules. Figure 10(a) is an example of “Inception” modules used in GoogleNet . As before, all the convolutional layers are followed by the ReLU activation function. The concatenation of information from filters with different sizes give the model great flexibility to capture spatial information. Note that $1\times 1$ filters is an $1\times 1\times d_{3}$ tensor (where $d_{3}$ is the number of feature maps), so its convolutional operation does not interact with other spatial coordinates, only serving to aggregate information from different feature maps at the same coordinate. This reduces the number of parameters and speeds up the computation. Similar ideas appear in other work .

Another module, usually called skip connections, is widely used to alleviate numerical issues in very deep neural nets, with additional benefits in optimization efficiency and statistical accuracy. Training very deep neural nets are generally more difficult, but the introduction of skip connections in residual networks has greatly eased the task.

Deep unsupervised learning

Here, for simplicity, we assume that the intercept/bias terms for $f$ and $g$ are zero. Then, PCA amounts to minimizing the quadratic loss function

Sparse autoencoders. One may believe that the dimension $k$ of the hidden code \text{\boldmathh}_{i} is larger than the input dimension $d$, and that \text{\boldmathh}_{i} admits a sparse representation. As with LASSO or SCAD , one may add a regularization term to the reconstruction loss $\mathcal{L}$ in (16) to encourage sparsity . A sparse autoencoder solves

This is similar to dictionary learning, where one aims at finding a sparse representation of input data on an overcomplete basis. Due to the imposed sparsity, the model can potentially learn useful features of the data.

2 Generative adversarial networks

Suppose the data $\{\bm{x}_{i}\}_{1\leq i\leq n}$ at hand are all real images, and we want to generate new natural images. With this goal in mind, GAN models a zero-sum game between two players, namely, the generator $\mathcal{G}$ and the discriminator $\mathcal{D}$. The generator $\mathcal{G}$ tries to generate fake images akin to the true images $\{\bm{x}_{i}\}_{1\leq i\leq n}$ while the discriminator $\mathcal{D}$ aims at differentiating the fake ones from the true ones. Intuitively, one hopes to learn a generator $\mathcal{G}$ to generate images where the best discriminator $\mathcal{D}$ cannot distinguish. Therefore the payoff is higher for the generator $\mathcal{G}$ if the probability of the discriminator $\mathcal{D}$ getting wrong is higher, and correspondingly the payoff for the discriminator correlates positively with its ability to tell wrong from truth.

2.2 Density estimation view of GANs

Observe that the inner maximization problem is solved by the likelihood ratio, i.e.

where $\text{JS}(\cdot\|\cdot)$ denotes the Jensen–Shannon divergence between two distributions

Representation power: approximation theory

Having seen the building blocks of deep learning models in the previous sections, it is natural to ask: what is the benefits of composing multiple layers of nonlinear functions. In this section, we address this question from a approximation theoretical point of view. Mathematically, letting $\mathcal{H}$ be the space of functions representable by neural nets (NNs), how well can a function $f$ (with certain properties) be approximated by functions in $\mathcal{H}$. We first revisit universal approximation theories, which are mostly developed for shallow neural nets (neural nets with a single hidden layer), and then provide recent results that demonstrate the benefits of depth in neural nets. Other notable works include Kolmogorov-Arnold superposition theorem , and circuit complexity for neural nets .

The universal approximation theories study the approximation of $f$ in a space $\mathcal{F}$ by a function represented by a one-hidden-layer neural net

First, as $N\to\infty$, any continuous function $f$ can be approximated by some $g$ under mild conditions. Loosely speaking, this is because each component \sigma_{*}(\text{\boldmathw}_{j}^{\top}\text{\boldmathx}-b_{j}) behaves like a basis function and functions in a suitable space $\mathcal{F}$ admits a basis expansion. Given the above heuristics, the next natural question is: what is the rate of approximation for a finite $N$?

where $C_{d,m,p}$ is independent of $N$, the number of hidden units.

In the above theorem, the condition on $\sigma_{*}(\cdot)$ is mainly technical. This upper bound is useful when the dimension $d$ is not large. It clearly implies that the one-hidden-layer neural net is able to approximate any smooth function with enough hidden units. However, it is unclear how to find a good approximator $g$; nor do we have control over the magnitude of the parameters (huge weights are impractical). While increasing the number of hidden units $N$ leads to better approximation, the exponent $-m/d$ suggests the presence of the curse of dimensionality. The following (nearly) matching lower bound is stated in .

Let $p\geq 1$, $m\geq 1$ and $N\geq 2$. If the activation function is the standard sigmoid function $\sigma(t)=(1+e^{-t})^{-1}$, then

where $C^{\prime}_{d,m,p}$ is independent of $N$.

Results for other activation functions are also obtained by . Moreover, the term $\log N$ can be removed if we assume an additional continuity condition .

uncovers the following dimension-free approximation guarantee.

Moreover, the coefficients of $g$ may be restricted to satisfy $\sum_{j=1}^{N}|c_{j}|\leq 2C$.

2 Approximation theory for multi-layer NNs

The approximation theory for multilayer neural nets is less understood compared with neural nets with one hidden layer. Driven by the success of deep learning, there are many recent papers focusing on expressivity of deep neural nets. As studied by , deep neural nets excel at representing composition of functions. This is perhaps not surprising, since deep neural nets are themselves defined by composing layers of functions. Nevertheless, it points to a new territory rarely studied in statistics before. Below we present a result based on .

Let p(\text{\boldmathx}) be a monomial $x_{1}^{r_{1}}x_{2}^{r_{2}}\cdots x_{d}^{r_{d}}$ with $q=\sum_{j=1}^{d}r_{j}$. Suppose that $\sigma_{*}$ has derivatives of order $2q$ at the origin, and that they are nonzero. Then, (i) $m_{1}(p)=\prod_{j=1}^{d}(r_{j}+1)$; (ii) $\min_{k}m_{k}(p)\leq\sum_{j=1}^{d}\left(7\lceil\log_{2}(r_{j})\rceil+4\right)$.

This theorem reveals a sharp distinction between shallow networks (one hidden layer) and deep networks. To represent a monomial function, a shallow network requires exponentially many neurons in terms of the dimension $d$, whereas linearly many neurons suffice for a deep network (with bounded $r_{j}$). The exponential dependence on $d$, as shown in Theorem 4(i), is resonant with the curse of dimensionality widely seen in many fields; see . One may ask: how does depth help? Depth circumvents this issue, at least for certain functions, by allowing us to represent function composition efficiently. Indeed, Theorem 4(ii) offers a nice result with clear intuitions: it is known that the product of two scalar inputs can be represented using $4$ neurons , so by composing multiple products, we can express monomials with $O(d)$ neurons.

Recent advances in nonparametric regressions also support the idea that deep neural nets excel at representing composition of functions . In particular, considered the nonparametric regression setting where we want to estimate a function \hat{f}_{n}(\text{\boldmathx}) from i.i.d. data \mathcal{D}_{n}=\{(y_{i},\text{\boldmathx}_{i})\}_{1\leq i\leq n}. If the true regression function f(\text{\boldmathx}) has certain hierarchical structure with intrinsic dimensionalityRoughly speaking, the true regression function can be represented by a tree where each node has at most $d^{*}$ children. See for the precise definition. $d^{*}$, then the error

has an optimal minimax convergence rate $O(n^{-\frac{2q}{2q+d^{*}}})$, rather than the usual rate $O(n^{-\frac{2q}{2q+d}})$ that depends on the ambient dimension $d$. Here $q$ is the smoothness parameter. This provides another justification for deep neural nets: if data are truly hierarchical, then the quality of approximators by deep neural nets depends on the intrinsic dimensionality, which avoids the curse of dimensionality.

We point out that the approximation theory for deep learning is far from complete. For example, in Theorem 4, the condition on $\sigma_{*}$ excludes the widely used ReLU activation function, there are no constraints on the magnitude of the weights (so they can be unreasonably large).

Training deep neural nets

The existence of a good function approximator in the NN function class does not explain why in practice we can easily find them. In this section, we introduce standard methods, namely stochastic gradient descent (SGD) and its variants, to train deep neural networks (or to find such a good approximator). As with many statistical machine learning tasks, training DNNs follows the empirical risk minimization (ERM) paradigm which solves the following optimization problem

Numerical stability. With a large number of layers in DNNs, the magnitudes of the hidden nodes can be drastically different, which may result in the “exploding gradients” or “vanishing gradients” issue during the training process. This is because the recursive relations across layers often lead to exponentially increasing / decreasing values in both forward passes and backward passes.

In the following three subsections, we discuss practical solutions / proposals to address these challenges.

Stochastic gradient descent (SGD) is by far the most popular optimization algorithm to solve ERM (26) for large-scale problems. It has the following simple update rule:

Asymptotic normality. It is proved by that for robust linear regression with fixed dimension $p$, under the choice $\eta_{t}=t^{-1}$, \sqrt{t}\,(\text{\boldmath\theta}^{t}-\text{\boldmath\theta}^{*}) is asymptotically normal under some regularity conditions (but \text{\boldmath\theta}^{t} is not asymptotically efficient in general). Moreover, by averaging the iterates of SGD, proved that even with a larger step size $\eta_{t}\propto t^{-\alpha},\alpha\in(1/2,1)$, the averaged iterate \bar{\text{\boldmath\theta}}^{t}=t^{-1}\sum_{s=1}^{t}\text{\boldmath\theta}^{s} is asymptotic efficient for robust linear regression. These strong results show that SGD with averaging performs as well as the MLE asymptotically, in addition to its computational efficiency.

Let $\{(y_{i},\bm{x}_{i})\}_{1\leq i\leq n}$ be a training set satisfying $\min_{i,j:i\neq j}\|\bm{x}_{i}-\bm{x}_{j}\|_{2}\geq\delta>0$. Consider fitting the data using a feed-forward neural network (1) with ReLU activations. Denote by $L$ (resp. $W$) the depth (resp. width) of the network. Suppose that the neural network is sufficiently over-parametrized, i.e.,

There are certainly other challenges for vanilla SGD to train deep neural nets: (1) training algorithms are often implemented in GPUs, and therefore it is important to tailor the algorithm to the infrastructure, (2) the vanilla SGD might converge very slowly for deep neural networks, albeit good theoretical guarantees for well-behaved problems, and (3) the learning rates $\{\eta_{t}\}$ can be difficult to tune in practice. To address the aforementioned challenges, three important variants of SGD, namely mini-batch SGD, momentum-based SGD, and SGD with adaptive learning rates are introduced.

Modern computational infrastructures (e.g., GPUs) can evaluate the gradient on a number (say 64) of examples as efficiently as evaluating that on a single example. To utilize this advantage, mini-batch SGD with batch size $K\geq 1$ forms the stochastic gradient through $K$ random samples:

where for each $1\leq k\leq K$, $i_{t}^{k}$ is sampled uniformly from $\{1,2,\cdots,n\}$. Mini-batch SGD, which is an “interpolation” between gradient descent and stochastic gradient descent, achieves the best of both worlds: (1) using $1\ll K\ll n$ samples to estimate the gradient, one effectively reduces the variance and hence accelerates the convergence, and (2) by taking the batch size $K$ appropriately (say 64 or 128), the stochastic gradient $G(\bm{\theta}^{t})$ can be efficiently computed using the matrix computation toolboxes on GPUs.

1.2 Momentum-based SGD

Here $\bm{v}^{0}=G(\bm{\theta}^{0})$ and for $t=1,2,\cdots$

with $0<\rho<1$. A typical choice of $\rho$ is 0.9. Notice that $\rho=0$ recovers the mini-batch SGD (30), where no past information of gradients is used. A simple unrolling of $\bm{v}^{t}$ reveals that $\bm{v}^{t}$ is actually an exponential averaging of the past gradients, i.e., $\bm{v}^{t}=\sum_{j=0}^{t}\rho^{t-j}G(\bm{\theta}^{j}).$ Compared with vanilla mini-batch SGD, the inclusion of the momentum “smoothes” the oscillation direction and accumulates the persistent descent direction. We want to emphasize that theoretical justifications of momentum in the stochastic setting is not fully understood .

1.3 SGD with adaptive learning rates

In optimization, preconditioning is often used to accelerate first-order optimization algorithms. In principle, one can apply this to SGD, which yields the following update rule:

Since we only require the diagonal part, this preconditioner (and its inverse) can be efficiently computed in practice. In addition, investigating (32) and (33), one can see that AdaGrad adapts to the importance of each coordinate of the parameters by setting smaller learning rates for frequent features, whereas larger learning rates for those infrequent ones. In practice, one adds a small quantity $\delta>0$ (say $10^{-8}$) to the diagonal entries to avoid singularity (numerical underflow). A notable drawback of AdaGrad is that the effective learning rate vanishes quickly along the learning process. This is because the historical sum of the gradients can only increase with time. RMSProp is a popular remedy for this problem which incorporates the idea of exponential averaging:

Again, the decaying parameter $\rho$ is usually set to be $0.9$. Later, Adam combines the momentum method and adaptive learning rate and becomes the default training algorithms in many deep learning applications.

2 Easing numerical instability

For very deep neural networks or RNNs with long dependencies, training difficulties often arise when the values of nodes have different magnitudes or when the gradients “vanish” or “explode” during back-propagation. Here we discuss three partial solutions to alleviate this problem.

One useful characteristic of the ReLU function is that its derivative is either or $1$, and the derivative remains $1$ even for a large input. This is in sharp contrast with the standard sigmoid function $(1+e^{-t})^{-1}$ which results in a very small derivative when inputs have large magnitude. The consequence of small derivatives across many layers is that gradients tend to be “killed”, which means that gradients become approximately zero in deep nets.

The popularity of the ReLU activation function and its variants (e.g., leaky ReLU) is largely attributable to the above reason. It has been well observed that the ReLU activation function has superior training performance over the sigmoid function .

2.2 Skip connections

We have introduced skip connections in Section 3.3. Why are skip connections helpful for reducing numerical instability? This structure does not introduce a larger function space, since the identity map can be also represented with ReLU activations: \text{\boldmathx}=\bm{\sigma}(\text{\boldmathx})-\bm{\sigma}(-\text{\boldmathx}).

2.3 Batch normalization

3 Regularization techniques

So far we have focused on training techniques to drive the empirical loss (26) small efficiently. Here we proceed to discuss common practice to improve the generalization power of trained neural nets.

3.2 Dropout

3.3 Data augmentation

Data augmentation is a technique of enlarging the dataset when we have knowledge about invariance structure of data. It implicitly increases the sample size and usually regularizes the model effectively. For example, in image classification, we have strong prior knowledge about what invariance properties a good classifier should possess. The label of an image should not be affected by translation, rotation, flipping, and even crops of the image. Hence one can augment the dataset by randomly translating, rotating and cropping the images in the original dataset.

Generalization power

Section 6 has focused on the in-sample / training error obtained via SGD, but this alone does not guarantee good performance with respect to the out-of-sample / test error. The gap between the in-sample error and the out-of-sample error, namely the generalization gap, has been the focus of statistical learning theory since its birth; see for an excellent introduction to this topic.

While understanding the generalization power of deep neural nets is difficult , we sample recent endeavors in this section. From a high level point of view, these approaches can be divided into two categories, namely algorithm-independent controls and algorithm-dependent controls. More specifically, algorithm-independent controls focus solely on bounding the complexity of the function class represented by certain deep neural networks. In contrast, algorithm-dependent controls take into account the algorithm (e.g., SGD) used to train the neural network.

The key to algorithm-independent controls is the notion of complexity of the function class parametrized by certain neural networks. Informally, as long as the complexity is not too large, the generalization gap of any function in the function class is well-controlled. However, the standard complexity measure (e.g., VC dimension ) is at least proportional to the number of weights in a neural network , which fails to explain the practical success of deep learning. The caveat here is that the function class under consideration is all the functions realized by certain neural networks, with no restrictions on the size of the weights at all. On the other hand, for the class of linear functions with bounded norm, i.e., $\{\bm{x}\mapsto\bm{w}^{\top}\bm{x}\,|\,\|\bm{w}\|_{2}\leq M\}$, it is well understood that the complexity of this function class (measured in terms of the empirical Rademacher complexity) with respect to a random sample $\{\bm{x}_{i}\}_{1\leq i\leq n}$ is upper bounded by $\max_{i}\|\bm{x}_{i}\|_{2}M/\sqrt{n}$, which is independent of the number of parameters in $\bm{w}$. This motivates researchers to investigate the complexity of norm-controlled deep neural networksSuch attempts have been made in the seminal work . . Setting the stage, we introduce a few necessary notations and facts. The key object under study is the function class parametrized by the following fully-connected neural network with depth $L$:

The empirical Rademacher complexity of a function class $\mathcal{F}$ w.r.t. a dataset $S\triangleq\{\bm{x}_{i}\}_{1\leq i\leq n}$ is defined as

In words, Rademacher complexity measures the ability of the function class to fit the random noise represented by $\bm{\varepsilon}$. Intuitively, a function class with a larger Rademacher complexity is more prone to overfitting. We now formalize the connection between the empirical Rademacher complexity and the out-of-sample error; see Chapter 24 in .

In English, the generalization gap of any function $f$ that lies in $\mathcal{F}$ is well-controlled as long as the Rademacher complexity of $\mathcal{F}$ is not too large. With this connection in place, we single out the following complexity bound.

2 Algorithm-dependent controls

In this subsection, we bring computational thinking into statistics and investigate the role of algorithms in the generalization power of deep learning. The consideration of algorithms is quite natural and well motivated: (1) local/global minima reached by different algorithms can exhibit totally different generalization behaviors due to extreme nonconvexity, which marks a huge difference from traditional models, (2) the effective capacity of neural nets is possibly not large, since a particular algorithm does not explore the entire parameter space.

These demonstrate the fact that on top of the complexity of the function class, the inherent property of the algorithm we use plays an important role in the generalization ability of deep learning. In what follows, we survey three different ways to obtain upper bounds on the generalization errors by exploiting properties of the algorithms.

As we have emphasized, modern deep learning models are highly over-parametrized. A line of work approximates the ensemble of weights by an asymptotic limit as the number of hidden units tends to infinity, so that the dynamics of SGD can be studied via certain partial different equations.

where $\varepsilon>0$ is an proxy for the step size of SGD and $\rho_{k\varepsilon}$ is the distribution of the gradient flow at time $k\varepsilon$. In words, the out-of-sample error under \text{\boldmath\theta}^{k} generated by SGD is well-approximated by that of $\rho_{k\varepsilon}$. Viewing the optimization problem from the distributional aspect greatly simplifies the problem conceptually, as the complicated optimization problem is now passed into its limit version—for this reason, this analytical approach is called the mean field perspective. In particular, further demonstrated that in some simple settings, the out-of-sample error $R(\rho_{k\varepsilon})$ of the distributional limit can be fully characterized. Nevertheless, how well does $R(\rho_{k\varepsilon})$ perform and how fast it converges remain largely open for general problems.

2.2 Stability

A second way to understand the generalization ability of deep learning is through the stability of SGD. An algorithm is considered stable if a slight change of the input does not alter the output much. It has long been observed that a stable algorithm has a small generalization gap; examples include $k$ nearest neighbors , bagging , etc. The precise connection between stability and generalization gap is stated by . In what follows, we formalize the idea of stability and its connection with the generalization gap. Let $\mathcal{A}$ denote an algorithm (possibly randomized) which takes a sample $S\triangleq\{(y_{i},\bm{x}_{i})\}_{1\leq i\leq n}$ of size $n$ and returns an estimated parameter $\hat{\bm{\theta}}\triangleq\mathcal{A}(S)$. Following , we have the following definition for stability.

An algorithm (possibly randomized) $\mathcal{A}$ is $\varepsilon$-uniformly stable with respect to the loss function $\mathcal{L}(\cdot,\cdot)$ if for all datasets $S,S^{\prime}$ of size $n$ which differ in at most one example, one has

Here the expectation is taken w.r.t. the randomness in the algorithm $\mathcal{A}$ and $\varepsilon$ might depend on $n$. The loss function $\mathcal{L}(\cdot,\cdot)$ takes an example (say $(\bm{x},y)$) and the estimated parameter (say $\mathcal{A}(S)$) as inputs and outputs a real value.

Surprisingly, an $\varepsilon$-uniformly stable algorithm incurs small generalization gap in expectation, which is stated in the following lemma.

Let $\mathcal{A}$ be $\varepsilon$-uniformly stable. Then the expected generalization gap is no larger than $\varepsilon$, i.e.,

With Lemma 1 in hand, it suffices to prove stability bound on specific algorithms. It turns out that SGD introduced in Section 6 is uniformly stable when solving smooth nonconvex functions.

Assume that for any fixed $(y,\bm{x})$, the loss function \mathcal{L}(f(x;\text{\boldmath\theta}),y), viewed as a function of $\theta$, is $L$-Lipschitz and $\beta$-smooth. Consider running SGD on the empirical loss function with decaying step size $\alpha_{t}\leq c/t$, where $c$ is some small absolute constant. Then SGD is uniformly stable with

where we have ignored the dependency on $\beta,c$ and $L$.

2.3 Implicit regularization

Consider the logistic regression (40) with separable data. If we run GD

where $\hat{\bm{\theta}}$ is the solution to the hard margin support vector machine:

Moving beyond logistic regression, which can be viewed as a one-layer neural net, the theoretical understanding of implicit regularization in deeper neural networks is still limited; see for an illustration in deep linear convolutional neural networks.

Discussion

Due to space limitations, we have omitted several important deep learning models; notable examples include deep reinforcement learning , deep probabilistic graphical models , variational autoencoders , transfer learning , etc. Apart from the modeling aspect, interesting theories on generative adversarial networks , recurrent neural networks , connections with kernel methods are also emerging. We have also omitted the inverse-problem view of deep learning where the data are assumed to be generated from a certain neural net and the goal is to recover the weights in the NN with as few examples as possible. Various algorithms (e.g., GD with spectral initialization) have been shown to recover the weights successfully in some simplified settings .

In the end, we identify a few important directions for future research.

New characterization of data distributions. The success of deep learning relies on its power of efficiently representing complex functions relevant to real data. Comparatively, classical methods often have optimal guarantee if a problem has a certain known structure, such as smoothness, sparsity, and low-rankness , but they are insufficient for complex data such as images. How to characterize the high-dimensional real data that can free us from known barriers, such as the curse of dimensionality is an interesting open question?

Understanding various computational algorithms for deep learning. As we have emphasized throughout this survey, computational algorithms (e.g., variants of SGD) play a vital role in the success of deep learning. They allow fast training of deep neural nets and probably contribute towards the good generalization behavior of deep learning in practice. Understanding these computational algorithms and devising better ones are crucial components in understanding deep learning.

Robustness. It has been well documented that DNNs are sensitive to small adversarial perturbations that are indistinguishable to humans . This raises serious safety issues once if deploy deep learning models in applications such as self-driving cars, healthcare, etc. It is therefore crucial to refine current training practice to enhance robustness in a principled way .

Low SNRs. Arguably, for image data and audio data where the signal-to-noise ratio (SNR) is high, deep learning has achieved great success. In many other statistical problems, the SNR may be very low. For example, in financial applications, the firm characteristic and covariates may only explain a small part of the financial returns; in healthcare systems, the uncertainty of an illness may not be predicted well from a patient’s medical history. How to adapt deep learning models to excel at such tasks is an interesting direction to pursue?

Acknowledgements

J. Fan is supported in part by the NSF grants DMS-1712591 and DMS-1662139, the NIH grant R01-GM072611 and the ONR grant N00014-19-1-2120. We thank Ruying Bao, Yuxin Chen, Chenxi Liu, Weijie Su, Qingcan Wang and Pengkun Yang for helpful comments and discussions.

References