Dropout: Explicit Forms and Capacity Control

Introduction

Dropout is a popular algorithmic regularization technique for training deep neural networks that aims at “breaking co-adaptation” among neurons by randomly dropping them at training time (Hinton et al. 2012). Dropout has been shown effective across a wide range of machine learning tasks, from classification (Srivastava et al. 2014; Szegedy et al. 2015) to regression (Toshev & Szegedy 2014). Notably, dropout is considered an essential component in the design of AlexNet (Krizhevsky et al. 2012), which won the prominent ImageNet challenge in 2012 with a significant margin and helped transform the field of computer vision.

Dropout regularizes the empirical risk by randomly perturbing the model parameters during training. A natural first step toward understanding generalization due to dropout, therefore, is to instantiate the explicit form of the regularizer due to dropout. In linear regression, with dropout applied to the input layer (i.e., on the input features), the explicit regularizer was shown to be akin to a data-dependent ridge penalty Srivastava et al. 2014; Wager et al. 2013; Baldi & Sadowski 2013; Wang & Manning 2013. In factored models dropout yields more exotic forms of regularization. For instance, dropout induces regularizer that behaves similar to nuclear norm regularization in matrix factorization Cavazza et al. 2018, in single hidden-layer linear networks Mianjy et al. 2018, and in deep linear networks Mianjy & Arora 2019. However, none of the works above discuss how the induced regularizer provides capacity control, or equivalently, help us establish generalization bounds for dropout.

In this paper, we provide an answer to this question. We give explicit forms of the regularizers induced by dropout for the matrix sensing problem and two-layer neural networks with ReLU activations. Further, we establish capacity control due to dropout and give precise generalization bounds. Our key contributions are as follows.

In Section 2, we study dropout for matrix completion, wherein, the matrix factors are dropped randomly during training. We show that this algorithmic procedure induces a data-dependent regularizer that behaves similar to the weighted trace-norm which has been shown to yield strong generalization guarantees for matrix completion (Foygel et al. 2011).

In Section 5, we present empirical evaluations that confirm our theoretical findings for matrix completion and deep regression on real world datasets including the MovieLens data, as well as the MNIST and Fashion MNIST datasets.

Dropout was first introduced by Hinton et al. 2012 as an effective heuristic for algorithmic regularization, yielding lower test errors on the MNIST and TIMIT datasets. In a subsequent work, Srivastava et al. 2014 reported similar improvements over several tasks in computer vision (on CIFAR-10/100 and ImageNet datasets), speech recognition, text classification and genetics.

Thenceforth, dropout has been widely used in training state-of-the-art systems for several tasks including large-scale visual recognition Szegedy et al. 2015, large vocabulary continuous speech recognition Dahl et al. 2013, image question answering Yang et al. 2016, handwriting recognition Pham et al. 2014, sentiment prediction and question classification Kalchbrenner et al. 2014, dependency parsing Chen & Manning 2014, and brain tumor segmentation Havaei et al. 2017.

Following the empirical success of dropout, there have been several studies in recent years aimed at establishing theoretical underpinnings of why and how dropout helps with generalization. Early work of Baldi & Sadowski 2013 showed that for a single linear unit (and a single sigmoid unit, approximately), dropout amounts to weight decay regularization on the weights. A similar result was shown by McAllester 2013 in a PAC-Bayes setting. For generalized linear models, Wager et al. 2013 established that dropout performs an adaptive regularization which is equivalent to a data-dependent scaling of the weight decay penalty. In their follow-up work, Wager et al. 2014 show that for linear classification, under a generative assumption on the data, dropout improves the convergence rate of the generalization error. In this paper, we focus on predictors represented in a factored form and give generalization bounds for matrix learning problems and single hidden layer ReLU networks.

In a related line of work, Helmbold & Long 2015 study the structural properties of the dropout regularizer in the context of linear classification. They characterize the landscape of the dropout criterion in terms of unique minimizers and establish non-monotonic and non-convex nature of the regularizer. In a follow up work, Helmbold & Long 2017 extend their analysis to dropout in deep ReLU networks and surprisingly find that the nature of regularizer is different from that in linear classification. In particular, they show that unlike weight decay, dropout regularizer in deep networks can grow exponentially with depth and remains invariant to rescaling of inputs, outputs, and network weights. We confirm some of these findings in our theoretical analysis. However, counter to the claims of Helmbold & Long 2017, we argue that dropout does indeed prevent co-adaptation.

In a closely related approach as ours, the works of Zhai & Wang 2018, Gao & Zhou 2016, and Wan et al. 2013 bound the Rademacher complexity of deep neural networks trained using dropout. In particular, Gao & Zhou 2016 show that the Rademacher complexity of the target class decreases polynomially or exponentially, for shallow and deep networks, respectively, albeit they assume additional norm bounds on the weight vectors. Similarly, the works of Wan et al. 2013 and Zhai & Wang 2018 assume that certain norms of the weights are bounded, and show that the Rademacher complexity of the target class decreases with dropout rates. We argue in this paper that dropout alone does not directly control the norms of the weight vectors; therefore, each of the works above fail to capture the practice. We emphasize that none of the previous works provide a generalization guarantee, i.e., a bound on the gap between the population risk and the empirical risk, merely in terms of the value of the explicit regularizer due to dropout. We give a first such result for dropout in the context of matrix completion and for a single hidden layer ReLU network.

There are a bunch of other works that do not fall into any of the categories above, and, in fact, are somewhat unrelated to the focus in this paper. Nonetheless, we discuss them here for completeness. For instance, Gal & Ghahramani 2016 study dropout as Bayesian approximation , Bank & Giryes 2018 draw insights from frame theory to connect the notion of equiangular tight frames with dropout training in auto-encoders. Also, some recent works have considered variants of dropout. For instance, Mou et al. 2018 consider a variant of dropout, which they call “truthful” dropout, that ensures that the output of the randomly perturbed network is unbiased. However, rather than bound generalization error, Mou et al. 2018 bound the gap between the population risk and the dropout objective, i.e., the empirical risk plus the explicit regularizer. Li et al. 2016 study a yet another variant based on multinomoal sampling (different nodes are dropped with different rates), and establish sub-optimality bounds for stochastic optimization of linear models (for convex Lipschitz loss functions).

Our study of dropout is motivated in part by recent works of Cavazza et al. 2018, Mianjy et al. 2018, and Mianjy & Arora 2019. This line of work was initiated by Cavazza et al. 2018, who studied dropout for low-rank matrix factorization without constraining the rank of the factors or adding an explicit regularizer to the objective. They show that dropout in the context of matrix factorization yields an explicit regularizer whose convex envelope is given by nuclear norm. This result is further strengthened by Mianjy et al. 2018 who show that induced regularizer is indeed nuclear norm.

To summarize, while we are motivated by Cavazza et al. 2018, the problem setup, the nature of statements in this paper, and the tools we use are different from that in Cavazza et al. 2018. Our proofs are simple and quickly verified. We do build closely on the prior work of Mianjy et al. 2018.

However, different from Mianjy et al. 2018, we rigorously argue for dropout in matrix completion by 1) showing that the induced regularizer is equal to weighted trace-norm, which as far as we know, is a novel result, 2) giving strong generalization bounds, and 3) providing extensive experimental evidence that dropout provides state of the art performance on one of the largest datasets in recommendation systems research. Beyond that we rigorously extend our results to two layer ReLU networks, describe the explicit regularizer, bound the Rademacher complexity of the hypothesis class controlled by dropout, show precise generalization bounds, and support them with empirical results.

2 Notation and Preliminaries

We are primarily interested in understanding how dropout controls the capacity of the hypothesis class when using dropout for training. To that end, we consider Rademacher complexity, a sample dependent measure of complexity of a hypothesis class that can directly bound the generalization gap (Bartlett & Mendelson 2002). Formally, let $\mathcal{S}=\{({\textrm{x}}_{1},y_{1}),\ldots,({\textrm{x}}_{n},y_{n})\}$ be a sample of size $n$. Then, the empirical Rademacher complexity of a function class $\mathcal{F}$ with respect to $\mathcal{S}$, and the expected Rademacher complexity are defined, respectively, as

where $\sigma_{i}$ are i.i.d. Rademacher random variables.

Matrix Sensing

A natural approach is to represent the matrix in terms of factors and solve the following empirical risk minimization problem:

We propose solving the ERM problem (1) using dropout, where at training time, corresponding columns of U and V are dropped uniformly at random. As opposed to an implicit effect of gradient descent, dropout explicitly regularizes the empirical objective. It is then natural to ask, in the case of matrix sensing, if dropout also biases the ERM towards certain low norm solutions. To answer this question, we begin with the observation that dropout can be viewed as an instance of SGD on the following objective Cavazza et al. 2018; Mianjy et al. 2018:

We show that the explicit regularizer concentrates around its expected value w.r.t. the data distribution (see Lemma 2 in the Appendix). Furthermore, given that we seek a minimum of $\widehat{L}_{\textrm{drop}}$, it suffices to consider the factors with the minimal value of the regularizer among all that yield the same empirical loss. This motivates studying the the following distribution-dependent induced regularizer:

For a wide range of random measurements, $\Theta(\cdot)$ turns out to be a “suitable” regularizer. Here, we instantiate two important examples (see Proposition 3 in the Appendix).

For all $j\in[n]$, let $\textrm{A}^{(j)}$ be standard Gaussian matrices. In this case, it is easy to see that $\textrm{L}(\textrm{U},\textrm{V})=\|\textrm{M}_{*}-\textrm{U}\textrm{V}^{\top}\|_{F}^{2}$ and we recover the matrix factorization problem. Furthermore, we know from Cavazza et al. 2018; Mianjy & Arora 2019 that dropout regularizer acts as trace-norm regularization, i.e., $\Theta(\textrm{M})=\frac{1}{d_{1}}\|\textrm{M}\|_{*}^{2}$.

Matrix Completion.

For all $j\in[n]$, let $\textrm{A}^{(j)}$ be an indicator matrix whose $(i,k)$-th element is selected randomly with probability $p(i)q(k)$, where $p(i)$ and $q(k)$ denote the probability of choosing the $i$-th row and the $k$-th column, respectively. Then

is the weighted trace-norm studied by Srebro & Salakhutdinov 2010 and Foygel et al. 2011.

These observations are specifically important because they connect dropout, an algorithmic heuristic in deep learning, to strong complexity measures that are empirically effective as well as theoretically well understood. To illustrate, here we give a generalization bound for matrix completion using dropout in terms of the value of the explicit regularizer at the minimizer.

Assume that $d_{2}\geq d_{0}$ and $\|\textrm{M}_{*}\|\leq 1$. Furthermore, assume that $\min_{i,k}p(i)q(k)\geq\frac{\log(d_{2})}{n\sqrt{d_{2}d_{0}}}$. Let $(\textrm{U},\textrm{V})$ be a minimizer of the dropout ERM objective in equation (3). Let $\alpha$ be such that $R(\textrm{U},\textrm{V})\leq\alpha/{d_{1}}$. Then, for any $\delta\in(0,1)$, the following generalization bounds holds with probability at least $1-\delta$ over a sample of size $n$:

We note that for large enough sample size, $\widehat{R}(\textrm{U},\textrm{V})\approx R(\textrm{U},\textrm{V})\approx\Theta(\textrm{U}\textrm{V}^{\top})=\frac{1}{d_{1}}\|\diag(\sqrt{p})\textrm{U}\textrm{V}^{\top}\diag(\sqrt{\textrm{q}})\|_{*}^{2}$, where the second approximation is due the fact that the pair $(\textrm{U},\textrm{V})$ is a minimizer. That is, compared to the weighted trace-norm, the value of the explicit regularizer at the minimizer roughly scales as $1/d_{1}$. Hence the assumption $\widehat{R}(\textrm{U},\textrm{V})\leq\alpha/{d_{1}}$ in the statement of the corollary.

Finally, the required sample size heavily depends on the value of the explicit regularizer (i.e., $\alpha/d_{1}$) at a minimizer, and hence, on the dropout rate $p$. In particular, increasing the dropout rate increases the regularization parameter $\lambda:=\frac{p}{1-p}$, thereby intensifying the penalty due to the explicit regularizer. Intuitively, a larger dropout rate $p$ results in a smaller $\alpha$, thereby a tighter generalization gap can be guaranteed. We show through experiments that that is indeed the case in practice.

Non-linear Networks

As in Section 2, we view dropout as an instance of stochastic gradient descent on the following dropout objective:

where B is a diagonal random matrix with diagonal elements distributed identically and independently as $\textrm{B}_{ii}\sim\frac{1}{1-p}\text{Bern}(1-p),\ i\in[d_{1}]$, for some dropout rate $p$. We seek to understand the explicit regularizer due to dropout:

To understand the generalization properties of dropout, we focus on the following distribution-dependent class

We argue that networks that are trained with dropout belong to the class $\mathcal{F}_{\alpha}$, for a small value of $\alpha$. In particular, by Cauchy-Schwartz inequality, it is easy to to see that $\sum_{i=1}^{d_{1}}|u_{i}|a_{i}\leq\sqrt{d_{1}R({\textrm{w}})}$. Thus, for a fixed width, dropout implicitly controls the function class $\mathcal{F}_{\alpha}$. More importantly, this inequality is loose if a small subset of hidden nodes $\mathcal{J}\subset[d_{1}]$ “co-adapt” in a way that for all $j\in[d_{1}]\setminus\mathcal{J}$, the other hidden nodes are almost inactive, i.e. $u_{j}a_{j}\approx 0$. In other words, by minimizing the expected regularizer, dropout is biased towards networks where the gap between $R({\textrm{w}})$ and $(\sum_{i=1}^{d_{1}}|u_{i}|a_{i})^{2}/d_{1}$ is small, which in turn happens if $|u_{i}|a_{i}\approx|u_{j}|a_{j},\forall i,j\in[d_{1}]$. In this sense, dropout breaks “co-adaptation” between neurons by promoting solutions with nearly equal contribution from hidden neurons.

As we mentioned in the introduction, a bound on the dropout regularizer is not sufficient to guarantee a bound on a norm-based complexity measures that are common in the deep learning literature (see, e.g. Golowich et al. 2018 and the references therein), whereas a norm bound on the weight vector would imply a bound on the explicit regularizer due to dropout. Formally, we show the following.

In other words, even though we connect the dropout regularizer to path-norm, the data-dependent nature of the regularizer prevents us from leveraging that connection in data-independent manner (i.e., for all distributions). At the same time, making strong distributional assumptions (as in Proposition 5) would be impractical. Instead, we argue for the following milder condition on the input distribution which we show as sufficient to ensure generalization.

Intuitively, what the assumption implies is that the variance (aka, the information or signal in the data) in the pre-activation at any node in the network is not quashed considerably due to the non-linearity. In fact, no reasonable training algorithm should learn weights where $\beta$ is small. However, we steer clear from algorithmic aspects of dropout training, and make the assumption above for every weight vector as we will need it when carrying out a union bound.

We now present the first main result of this section, which bounds the Rademacher complexity of $\mathcal{F}_{\alpha}$ in terms of $\alpha$, the retentiveness coefficient $\beta$, and the Mahalanobis norm of the data with respect to the pseudo-inverse of the second moment, i.e. $\|{\textrm{X}}\|_{{\textrm{C}}^{\dagger}}^{2}=\sum_{i=1}^{n}{\textrm{x}}_{i}^{\top}{\textrm{C}}^{\dagger}{\textrm{x}}_{i}$.

For any sample $S=\{({\textrm{x}}_{i},{\textrm{y}}_{i})\}_{i=1}^{n}$ of size $n$,

Furthermore, it holds for the expected Rademacher complexity that $\mathfrak{R}_{n}(\mathcal{F}_{\alpha})\leq 2\alpha\sqrt{\frac{\rank({\textrm{C}})}{\beta n}}.$

First, note that the bound depends on the quantity $\|{\textrm{X}}\|_{{\textrm{C}}^{\dagger}}$ which can be in the same order as $\|{\textrm{X}}\|_{F}$ with both scaling as $\asymp\sqrt{nd_{0}}$; the latter is more common in the literature Neyshabur et al. 2018; Bartlett et al. 2017; Neyshabur et al. 2017; Golowich et al. 2018; Neyshabur et al. 2015b. This is unfortunately unavoidable, unless one makes stronger distributional assumptions.

Second, as we discussed earlier, the dropout regularizer directly controls the value of $\alpha$, thereby controlling the Rademacher complexity in Theorem 2. This bound also gives us a bound on the Rademacher complexity of the networks trained using dropout. To see that, consider the following class of networks with bounded explicit regularizer, i.e., $\mathcal{H}_{r}:=\{h_{\textrm{w}}:{\textrm{x}}\mapsto{\textrm{u}}^{\top}\sigma(\textrm{V}^{\top}{\textrm{x}}),\ R({\textrm{u}},\textrm{V})\leq r\}$. Then, Theorem 2 yields $\mathfrak{R}_{\mathcal{S}}(\mathcal{H}_{r})\leq\frac{2\sqrt{d_{1}r}\|{\textrm{X}}\|_{{\textrm{C}}^{\dagger}}}{n\sqrt{\beta}}.$ In fact, we can show that this bound is tight up to $1/\sqrt{\beta}$ by a reduction to the linear case. Formally, we show the following.

There is a constant $c$ such that for any scalar $r>0$, $\mathfrak{R}_{\mathcal{S}}(\mathcal{H}_{r})\geq\frac{c\sqrt{d_{1}r}\|{\textrm{X}}\|_{{\textrm{C}}^{\dagger}}}{n}.$

Moreover, it is easy to give a generalization bound based on Theorem 2 that depends only on the distribution dependent quantities $\alpha$ and $\beta$. Let $g_{\textrm{w}}(\cdot):=\max\{-1,\min\{1,f_{\textrm{w}}(\cdot)\}\}$ project the network output $f_{\textrm{w}}$ onto the range $$. We have the following generalization gurantees for$g_{\textrm{w}}$.

For any ${\textrm{w}}\in\mathcal{F}_{\alpha}$, for any $\delta\in(0,1)$, the following generalization bound holds with probability at least $1-\delta$ over a sample $\mathcal{S}$ of size $n$

Given an i.i.d. sample $\mathcal{S}=\{({\textrm{x}}_{i},{\textrm{y}}_{i})\}_{i=1}^{n}$, let

Note that the population risk of the clipped predictor $g_{\textrm{w}}(\cdot):=\max\{-1,\min\{1,f_{\textrm{w}}(\cdot)\}\}$ is bounded in terms of the empirical risk on $\mathcal{S}^{\prime}$. Finally, we verify in Section 5 that symmetrization of the training set, on MNIST and FashionMNIST datasets, does not have an effect on the performance of the trained models.

Role of Parametrization

In this section, we argue that parametrization plays an important role in determining the nature of the inductive bias.

However, simply representing the hypotheses in a factored form alone is not sufficient in terms of imparting a rich inductive bias to the learning problem. Recall that in linear regression, dropout, when applied on the input features, yields ridge regularization. However, if we were to represent the linear predictor in terms of a deep linear network, then we argue that the effect of dropout is markedly different. Consider a deep linear network, $f_{\textrm{w}}:{\textrm{x}}\mapsto\textrm{W}_{k}\cdots\textrm{W}_{1}{\textrm{x}}$ with a single output neuron. In this case, Mianjy & Arora 2019 show that $\nu\|f\|_{\widehat{\textrm{C}}}^{2}=\underset{f_{\textrm{w}}=f}{\textrm{min}}\ \widehat{R}({\textrm{w}}),$ where $\nu$ is a regularization parameter independent of the parameters w. Consequently, in deep linear networks with a single output neuron, dropout reduces to solving

What we argue above may at first seem to contradict the results of Section 2 on matrix sensing, which is arguably an instance of regression with a two-layer linear network. Note though that casting matrix sensing in a factored form as a linear regression problem requires us to use a convolutional structure. This is easy to check since

where $\otimes$ is the Kronecker product, and we used the fact that $\operatorname{vec}\left(\textrm{A}\textrm{B}\right)=(\textrm{I}\otimes\textrm{A})\operatorname{vec}\left(\textrm{B}\right)$ for any pair of matrices $\textrm{A},\textrm{B}$. The expression $(\textrm{I}\otimes\textrm{V}^{\top})$ represents a fully connected convolutional layer with $d_{1}$ filters specified by columns of V. The convolutional structure in addition to dropout is what imparts the problem of matrix sensing the nuclear norm regularization. For nonlinear networks, however, a simple feed-forward structure suffices as we saw in Section 3.

Experimental Results

In this section, we report our empirical findings on real world datasets. All results are averaged over 50 independent runs with random initialization.

We evaluate dropout on the MovieLens dataset Harper & Konstan 2016, a publicly available collaborative filtering dataset that contains 10M ratings for 11K movies by 72K users of the online movie recommender service MovieLens.

We initialize the factors using the standard He initialization scheme. We train the model for 100 epochs over the training data, where we use a fixed learning rate of $\texttt{lr}=1$, and a batch size of $2000$. We report the results for plain SGD ($p=0.0$) as well as the dropout algorithm with $p\in\{0.1,0.2,0.3,0.4\}$.

Figure 1 shows the progress in terms of the training and test error as well as the gap between them as a function of the number of iterations for $d_{1}=70$. It can be seen that plain SGD is the fastest in minimizing the empirical risk. The dropout rate clearly determines the trade-off between the approximation error and the estimation error: as the dropout rate $p$ increases, the algorithm favors less complex solutions that suffer larger empirical error (left figure) but enjoy smaller generalization gap (right figure). The best trade-off here seems to be achieved by a moderate dropout rate of $p=0.3$. We observe similar behaviour for different factorization sizes; please see the Appendix for additional plots with factorization sizes $d_{1}\in\{30,110,150,190\}$.

It is remarkable, how even in the “simple” problem of matrix completion, plain SGD lacks a proper inductive bias. As seen in the middle plot, without explicit regularization, in particular, without early stopping or dropout, SGD starts overfitting. We further illustrate this in Table 1, where we compare the test root-mean-squared-error (RMSE) of plain SGD with the dropout algorithm, for various factorization sizes. To show the superiority of dropout over SGD with early stopping, we give SGD the advantage of having access to the test set (and not a separate validation set), and report the best iterate in the third column. Even with this impractical privilege, dropout performs better ($>0.01$ difference in test RMSE).

2 Neural Networks

We train 2-layer neural networks with and without dropout, on MNIST dataset of handwritten digits and Fashion MNIST dataset of Zalando’s article images, each of which contains 60K training examples and 10K test examples, where each example is a $28\times 28$ grayscale image associated with a label from $10$ classes. We extract two classes $\{4,7\}$ and label them as $\{-1,+1\}$ We observe similar results across other choices of target classes.. The learning rate in all experiments is set to $\texttt{lr}=1e-3$. We train the models for 30 epochs over the training set. We run the experiments both with and without symmetrization. Here we only report the results with symmetrization, and on the MNIST dataset. For experiments without symmetrization, and experiments on FashionMNIST, please see the Appendix. We remark that under the above experimental setting, the trained networks achieve $100\%$ training accuracy.

For any node $i\in[d_{1}]$, we define its flow as $\psi_{i}:=|u_{i}|a_{i}$ (respectively $\psi_{i}:=|u_{i}|a_{i}^{\prime}$ for symmetrized data), which measures the overall contribution of a node to the output of the network. Co-adaptation occurs when a small subset of nodes dominate the overall function of the network. We argue that $\phi({\textrm{w}})=\frac{\|\psi\|_{1}}{\sqrt{d_{1}}\|\psi\|_{2}}$ is a suitable measure of co-adaptation (or lack thereof) in a network parameterized by w. In case of high co-adaptation, only a few nodes have a high flow, which implies $\phi({\textrm{w}})\approx\frac{1}{\sqrt{d_{1}}}$. At the other end of the spectrum, all nodes are equally active, in which case $\phi({\textrm{w}})\approx 1$. Figure 2 (left) illustrates this measure as a function of the network width for several dropout rates $p\in\{0,0.25,0.5,0.75\}$. In particular, we observe that a higher dropout rate corresponds to less co-adapation. More interestingly, even plain SGD is implicitly biased towards networks with less co-adapation. Moreover, for a fixed dropout rate, the regularization effect due to dropout decreases as we increase the width. Thus, it is natural to expect more co-adaptation as the network becomes wider, which is what we observe in the plots.

The generalization gap is plotted in Figure 2 (middle). As expected, increasing dropout rate decreases the generalization gap, uniformly for all widths. In our experiments, the generalization gap increases with the width of the network. The figure on the right shows the quantity $\alpha/\sqrt{n}$ that shows up in the Rademacher complexity bounds in Section 3. We note that, the bound on the Rademacher complexity is predictive of the generalization gap, in the sense that a smaller bound corresponds to a curve with smaller generalization gap.

Conclusion

Motivated by the success of dropout in deep learning, we study a dropout algorithm for matrix sensing and show that it enjoys strong generalization guarantees as well as competitive test performance on the MovieLens dataset. We then focus on deep regression under the squared loss and show that the regularizer due to dropout serves as a strong complexity measure for the underlying class of neural networks, using which we give a generalization error bound in terms of the value of the regularizer.

Acknowledgements

This research was supported, in part, by NSF BIGDATA award IIS-1546482 and NSF CAREER award IIS-1943251. The seeds of this work were sown during the summer 2019 workshop on the Foundations of Deep Learning at the Simons Institute for the Theory of Computing. Raman Arora acknowledges the support provided by the Institute for Advanced Study, Princeton, New Jersey as part of the special year on Optimization, Statistics, and Theoretical Machine Learning.

References

Appendix A Auxiliary Results

Let $X_{1},\ldots,X_{N}$ be independent, mean zero, sub-Gaussian random variables. Then, for every $t\geq 0$, we have

Let $\mathcal{G}$ be a family of functions mapping from $\mathcal{Z}$ to $$. Then, for any$\delta>0$, with probability at least$1-\delta$over a sample$\mathcal{S}=\{\textrm{z}_{1},\ldots,\textrm{z}_{n}\}$, the following holds for all$g\in\mathcal{G}$

Assume that $\|h-f\|_{\infty}\leq M$ for all $h\in\mathcal{H}$. Then, for any $\delta>0$, with probability at least $1-\delta$ over a sample $\mathcal{S}=\{({\textrm{x}}_{i},{\textrm{y}}_{i}),\ i\in[n]\}$ of size $n$, the following inequalities holds uniformly for all $h\in\mathcal{H}$.

where $L_{*}:=\min_{f\in\mathcal{H}}{L(f)}$, and $K$ is a numeric constant derived from Srebro et al. 2010.

Appendix B Matrix Sensing

Similar statements and proofs can be found in several previous works Srivastava et al. 2014; Wang & Manning 2013; Cavazza et al. 2018; Mianjy et al. 2018. For completeness, we include a proof here. The following equality follows from the definition of variance:

Plugging the above into Equation (7) and averaging over samples we get

[Induced regularizer] For $j\in[n]$, let $\textrm{A}^{(j)}$ be an indicator matrix whose $(i,k)$-th element is selected randomly with probability $p(i)q(k)$, where $p(i)$ and $q(k)$ denote the probability of choosing the $i$-th row and the $k$-th column. Then $\Theta(\textrm{M})=\frac{1}{d_{1}}\|\diag(\sqrt{p})\textrm{U}\textrm{V}^{\top}\diag(\sqrt{q})\|_{*}^{2}$.

For any pair of factors $(\textrm{U},\textrm{V})$ it holds that

We can now lower bound the right hand side above as follows:

where the first inequality is due to Cauchy-Schwartz and the second inequality follows from the triangle inequality. The equality right after the first inequality follows from the fact that for any two vectors ${\textrm{a}},{\textrm{b}}$, $\|{\textrm{a}}{\textrm{b}}^{\top}\|_{*}=\|{\textrm{a}}{\textrm{b}}^{\top}\|=\|{\textrm{a}}\|\|{\textrm{b}}\|$. Since the inequalities hold for any $\textrm{U},\textrm{V}$, it implies that

Applying Theorem 8 on $(\diag(\sqrt{p})\textrm{U},\diag(\sqrt{p})\textrm{V})$, there exist a rotation matrix Q such that

We evaluate the expected dropout regularizer at $\textrm{U}\textrm{Q},\textrm{V}\textrm{Q}$:

which completes the proof of the first part. ∎

We use Theorem 6 to bound the population risk in terms of the Rademacher complexity of the target class. Define the class of predictors with weighted trace-norm bounded by $\sqrt{\alpha}$, i.e.

In particular dropout empirical risk minimizers $\textrm{U},\textrm{V}$ belong to this class:

where the first inequality holds by definition of the induced regularizer, and the second inequality follows from the assumption of the theorem. Since $g$ is a contraction, by Talagrand’s lemma and Theorem 9, we have that $\mathfrak{R}_{n}(g\circ\mathcal{M}_{\alpha})\leq\mathfrak{R}_{n}(\mathcal{M}_{\alpha})\leq\sqrt{\frac{\alpha d_{2}\log(d_{2})}{n}}$. To obtain the maximum deviation parameter $M$ in Theorem 6, we note that the assumption $\|\textrm{M}_{*}\|\leq 1$ implies that $|\textrm{M}_{*}(i,j)|\leq 1$ for all $i,j$, so that $g(\textrm{M}_{*})=\textrm{M}_{*}$. We have that:

where the second inequality holds since $\widehat{L}(g(\textrm{U},\textrm{V}))\leq\widehat{L}(\textrm{U},\textrm{V})$. ∎

Assume that $d_{2}\geq d_{0}$ and $\|\textrm{M}_{*}\|\leq 1$. Furthermore, assume that $\min_{i,k}p(i)q(k)\geq\frac{\log(d_{2})}{n\sqrt{d_{2}d_{0}}}$. Let $(\textrm{U},\textrm{V})$ be a minimizer of the dropout ERM objective in equation (3). Let $\alpha$ be such that $\max\{R(\textrm{U},\textrm{V}),\Theta(\textrm{M}_{*})\}\leq\alpha/{d_{1}}$. Then, for any $\delta\in(0,1)$, the following generalization bounds holds with probability at least $1-\delta$ over a sample of size $n$:

We use Theorem 7 to bound the population risk in terms of the Rademacher complexity of the target class. Define the class of predictors with weighted trace-norm bounded by $\sqrt{\alpha}$, i.e.

In particular dropout empirical risk minimizers $\textrm{U},\textrm{V}$ belong to this class:

where the first inequality holds by definition of the induced regularizer, and the second inequality follows from the assumption of the theorem. Moreover, by assumption $\Theta(\textrm{M}_{*})\leq\alpha$, we have that $\textrm{M}_{*}\in\mathcal{M}_{\alpha}$. With this, we get that

Since $g$ is a contraction, by Talagrand’s lemma and Theorem 9, we have that $\mathfrak{R}_{n}(g\circ\mathcal{M}_{\alpha})\leq\mathfrak{R}_{n}(\mathcal{M}_{\alpha})\leq\sqrt{\frac{\alpha d_{2}\log(d_{2})}{n}}$. Plugging the above in Theorem 6, we get

Appendix C Non-linear Neural Networks

Thus, conditioned on the sample $({\textrm{x}},{\textrm{y}})$, we have that

Now taking the empirical average with respect to ${\textrm{x}},{\textrm{y}}$, we get

Plugging back the above identity in the expression of $R({\textrm{w}})$, we get that

where the second equality follows from the assumption that the distribution is isotropic. ∎

For $\delta\in(0,\frac{1}{2})$, consider the following random variable:

where we used the fact that the supremum of product of positive functions is upperbounded by the product of the supremums. By definition of $\mathcal{F}_{\alpha}$, the first term on the right hand side is bounded by $\alpha$. To bound the second term in the right hand side, we note that the maximum over rows of $\textrm{V}^{\top}$ can be absorbed into the supremum.

Let ${\textrm{C}}^{\dagger}$ be the pseudo-inverse of C. We perform the following change the variable: ${\textrm{w}}\leftarrow{\textrm{C}}^{-\dagger/2}{\textrm{v}}$.

where the last inequality holds due to Jensen’s inequality. To bound the expected Rademacher complexity, we take the expected value of both sides with respected to sample $\mathcal{S}$, which gives the following:

For simplicity, assume that the width of the hidden layer is even. Consider the linear function class:

Furthermore, it holds for the explicit regularizer that

Thus, we have that $\mathcal{G}_{r}\subset\mathcal{H}_{r}$, and the following inequalities follow.

where the last inequality follows from Khintchine-Kahane inequality in Lemma 1. ∎

Next, we define some function classes that will be used frequently in the proofs.

Let $\mathcal{W}_{\alpha},\mathcal{F}_{\alpha},\mathcal{G}_{\alpha},\mathcal{L}_{\alpha}$ be as defined in Definition 1. Then the following holds true:

$\mathfrak{R}_{\mathcal{S}}(\mathcal{G}_{\alpha})\leq\mathfrak{R}_{\mathcal{S}}(\mathcal{F}_{\alpha})$.

If $\mathcal{Y}=\{-1,+1\}$ (binary classification), then it holds that $\mathfrak{R}_{\mathcal{S}}(\mathcal{L}_{\alpha})\leq 2\mathfrak{R}_{\mathcal{S}}(\mathcal{G}_{\alpha})$.

Since $\Pi_{}(\cdot)$ is 1-Lipschitz, by Talagrand’s contraction lemma, we have that $\mathfrak{R}_{\mathcal{S}}(\mathcal{G}_{\alpha})\leq\mathfrak{R}_{\mathcal{S}}(\mathcal{F}_{\alpha})$. The second claim follows from

where the first inequality follows from Talagrand’s contraction lemma due to the fact that $h(z)=(1-z)^{2}$ is 2-Lipschitz for $z\in$, and the penultimate holds true since for any fixed $(y_{i})_{i=1}^{n}\in\{-1,+1\}^{n}$, the distribution of $(\zeta_{1}y_{1},\ldots,\zeta_{n}y_{n})$ is the same as that of $(\zeta_{1},\ldots,\zeta_{n})$. ∎

We use the standard generalization bound in Theorem 6 for class $\mathcal{G}_{\alpha}$:

where second inequality follows because the maximum deviation parameter $M$ in Theorem 6 is bounded as

Moreover, since $\mathcal{D}^{\prime}$ is centrally symmetric, Assumption 1 holds with $\beta=\frac{1}{2}$. The proof of Corollary 2 follows by doubling the right hand side of inequalities in Corollary 1, and substituting $\beta=\frac{1}{2}$. ∎

Although in the main text we only focus on the task of regression with squared loss, it is not hard to extend the results to binary classification. In particular, the following two Corollaries bound the miss-classification error in terms of the training error and the Rademacher complexity of the target class, with and without symmetrization.

Consider a binary classification setting where $\mathcal{Y}=\{-1,+1\}$. For any ${\textrm{w}}\in\mathcal{F}_{\alpha}$, for any $\delta\in(0,1)$, the following generalization bound holds with probability at least $1-\delta$ over $\mathcal{S}=\{({\textrm{x}}_{i},y_{i})\}_{i=1}^{n}\sim{\mathcal{D}}^{n}$:

where $g_{\textrm{w}}(\cdot)=\max\{-1,\min\{1,f_{\textrm{w}}(\cdot)\}\}$ projects the network output onto the range $$.

We use Theorem 5 for class $\frac{1}{4}\mathcal{L}_{\alpha}$ to get the generalization bound as follows:

Consider a binary classification setting where $\mathcal{Y}=\{-1,+1\}$. For any ${\textrm{w}}\in\mathcal{F}^{\prime}_{\alpha}$, for any $\delta\in(0,1)$, the following generalization bound holds with probability at least $1-\delta$ over a sample of size $n$ and the randomization in symmetrization

Akin to proof of Corollary 2, we have that $L_{\mathcal{D}}(f)\leq 2L_{\mathcal{D}^{\prime}}(f)$, and the marginal distribution is $\frac{1}{2}$-retentive. Proof of Corollary 4 follows by doubling the right hand side of inequalities in Corollary 3, and substituting $\beta=\frac{1}{2}$. ∎

Appendix D Additional Experiments

In this section, we include additional plots which was not reported in the main paper due to the space limitations.

Figure 1 in the main paper shows comparisons between plain SGD and the dropout algorithm on the MovieLens dataset for a factorization size of $d_{1}=70$. The observation that we make with regard to those plots is not at all limited to the specific choice of the factorization size. In Figure 1 here, we report similar experiments with factorization sizes $d_{1}\in\{30,110,150,190\}$. It can be seen that the overall behaviour of plain SGD and dropout are very similar in all experiments. In particular, plain SGD always achieves the best training error but it has the largest generalization gap. Furthermore, increasing the dropout rate increases the training error but results in a tighter generalization gap.

It can be seen that an appropriate choice of the dropout rate always perform better than the plain SGD in terms of the test error. For instance, a dropout rate of $p=0.2$ seems to always outperform plain SGD. Moreover, as the factorization size increases, the function class becomes more complex, and a larger value of the dropout rate is more helpful. For example, when $d_{1}=30$, the dropout with rates $p=0.3,0.4$ fail to achieve a good test performance, where as for larger factorization sizes ($d_{1}\in\{110,150,190\}$), they consistently outperform plain SGD as well as other dropout rates.

D.2 Shallow Neural Networks

In Figure 2, we plot the co-adaptation measure, the generalization gap, as well as the complexity measure $\alpha/\sqrt{n}$ as a function of width of the network, for FashionMNIST with symmetrization, and for MNIST without symmetrization.

The co-adaptation plot is very similar to Figure 2 in the main text. In particular, 1) increasing the dropout rate results in less co-adaptation; 2) even plain SGD is biased towards networks with less co-adapation; and 3) as the networks becomes wider, the co-adaptation curves corresponding to plain SGD converge to those of dropout. We also make similar observations for the generalization gap as well as the complexity term $\alpha/\sqrt{n}$. In particular, 1) a higher dropout rate corresponds to a lower generalization gap, uniformly for all widths; 2) the generalization gap is higher for wider networks; and 3) curves with smaller complexity terms in the right plot correspond to curves with smaller generalization gaps in the middle plot.

D.3 Deep Neural Networks

We train convolutional neural networks with and without dropout, on MNIST, Fashion MNIST, and CIFAR-10. The CIFAR-10 dataset consists of 60K $32\times 32$ color images in 10 classes, with 6k images per class, divided into a training set and a test set of sizes 50K and 10K respectively Krizhevsky et al. 2009. We do not perform symmetrization in these experiments. In contrast with the experiments in the previous section, here we run the experiments on full datasets, representing each of the ten classes as a one-hot target vector.

For MNIST and Fashion MNIST datasets, we use a convolutional neural network with one convolutional layer and two fully connected layers. The convolutional layer has 16 convolutional filters, padding and stride of 2, and kernel size of 5. We report experiments on networks with the width of the top hidden layer chosen from $\texttt{width}\in\{2^{6},2^{7},2^{8},2^{9},2^{10},2^{11}\}$. In all the experiments, a fixed learning rate $\texttt{lr}=0.5$ and a mini-batch of size 256 is used to perform the updates. We train the models for 30 epochs over the whole training set.

For CIFAR-10, we use an AlexNet Krizhevsky et al. 2012, where the layers are modified accordingly to match the dataset. The only difference here is that we apply dropout to the top hidden layer, whereas in Krizhevsky et al. 2012, dropout is used on top of the second and the third hidden layers from the top. We report experiments on networks with the width of the top hidden layer chosen from $\texttt{width}\in\{2^{5},2^{6},2^{7},2^{8},2^{9},2^{10},2^{11},2^{12}\}$. In all the experiments, an initial learning rate $\texttt{lr}=5$ and a mini-batch of size 256 is used to perform the updates. We train the models for 100 epochs over the whole training set. We decay the learning rate by a factor of 10 every 30 epochs.