Title: DROPOUT: EXPLICIT FORMS AND CAPACITY CON-TROL

Abstract: We investigate the capacity control provided by dropout in various machine learning problems. First, we study dropout for matrix sensing, where it induces a datadependent regularizer that, in expectation, equals the weighted trace-norm of the product of the factors. In deep learning, we show that the data-dependent regularizer due to dropout directly controls the Rademacher complexity of the underlying class of deep neural networks. These developments enable us to give concrete generalization error bounds for the dropout algorithm in both matrix completion as well as training deep neural networks. We evaluate our theoretical findings on real-world datasets, including MovieLens, Fashion MNIST, and CIFAR-10.

1. INTRODUCTION:

Dropout is a popular 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, it is considered as a major 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.

Following the empirical success of dropout, there have been several studies in recent years that focus on understanding theoretical underpinnings of dropout (Baldi & Sadowski, 2013; Wager et al., 2013; McAllester, 2013; Van Erven et al., 2014; Helmbold & Long, 2015; Gal & Ghahramani, 2016; Gao & Zhou, 2016; Mou et al., 2018; Bank & Giryes, 2018; Cavazza et al., 2018; Mianjy et al., 2018) . However, none of these works adequately address the following basic question: how does dropout control the capacity of deep neural networks? In this paper, we provide an answer to this question. We focus on the task of deep regression using squared 2 -loss which yields state-ofthe-art results in human pose estimation (Toshev & Szegedy, 2014) , facial landmark detection, age estimation (Lathuilière et al., 2019) , and more. We give precise generalization bounds for deep regression with dropout; our bounds leverage recent results in understanding generalization in deep learning and help explain practice with meaningful bounds. Along the way we also recover the state-of-the-art bounds for matrix completion. The key contributions in this paper are as follows.

1. We introduce dropout for matrix completion, a procedure that randomly drops the columns of the factors during training. Interestingly, this algorithmic procedure induces a datadependent regularizer that, in expectation, equals weighted trace-norm -a complexity measure that enjoys strong generalization guarantees (Foygel et al., 2011) .

2. For two-layer neural networks with ReLU activation, when the input distribution is symmetric and isotropic, we show that dropout induces the 2 path-norm which has been shown to provide scale-sensitive generalization guarantees in deep neural networks (Neyshabur et al., 2015) .

3. We study deep regression, where a feed-forward neural network is trained with dropout under squared loss. With no further assumptions on the data distribution and the network architecture, we show that the dropout regularizer is a data-dependent measure whose expected value serves as a strong complexity measure for networks trained with dropout. In particular, we show that a network with a small dropout regularizer enjoys a small generalization gap. 4. We empirically evaluate our theoretical findings for matrix completion and deep regression on real world datasets MovieLens, Fashion MNIST and CIFAR-10.

1.1. NOTATION:

We denote matrices, vectors, scalar variables and sets by Roman capital letters, Roman small letters, small letters, and script letters, respectively (e.g. X, x, x, and X ). For any integer d, we represent the set {1, . . . , d} by [d] . For any vector x ∈ R d , diag(x) ∈ R d×d represents the diagonal matrix with diagonal elements equal to x, and √ x is the elementwise squared root of x. Let x represent the 2 -norm of vector x, and X , X F , and X * represent the spectral norm, the Frobenius norm, and the nuclear norm of matrix X, respectively. Similarly, given a positive definite matrix C, we denote the Mahalonobis norm as x 2 C = x Cx. The standard inner product is represented by •, • , for vectors or matrices, where X, X = Tr(X X ).

2. MATRIX SENSING:

We begin with understanding dropout for matrix sensing, a problem which arguably is an important instance of a matrix learning problem with lots of applications, and is well understood from a theoretical perspective. Here is the problem setup.

Let M * ∈ R d2×d0 be a matrix with rank r * := Rank(M * ). Let A (1) , . . . , A (n) be a set of measurement matrices of the same size as M. The goal of matrix sensing is to recover the matrix M * from n observations of the form

y i = M * , A (i) such that n d 2 d 0 .

A natural approach to solve this problem is to enforce the rank constraints implicitly using the Burer-Monteiro factorization and to solve the following empirical risk minimization problem:

min U∈R d 2 ×d 1 ,V∈R d 0 ×d 1 L(U, V) := 1 n n i=1 (y i -UV , A (i) ) 2 .

(1)

When d 1 r * , there exist many "bad" empirical minimizers, i.e., those with a large true risk. However, recently, Li et al. (2018) showed that under restricted isometry property, despite the existence of such poor ERM solutions, gradient descent with proper initialization is implicitly biased towards finding solutions with minimum nuclear norm -this is an important result which was first conjectured and empirically verified by Gunasekar et al. (2017) . However, for the most part, modern machine learning systems employ explicit regularization techniques. In fact, as we show in the experimental section, the implicit bias due to (stochastic) gradient descent does not prevent it from blatant overfitting in the matrix completion problem. We argue that in such cases, there is a need for "suitable" explicit regularization, such as trace-norm Recht et al. (2010); Candès & Recht (2009) , weighted trace-norm Foygel et al. (2011) , or max norm Srebro & Shraibman (2005) .

We propose solving the ERM problem (1) with algorithmic regularization due to dropout, where at training time, columns of U and V are dropped uniformly at random. As opposed to the implicit effect of gradient descent, this dropout heuristic 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:

EQUATION

where B ∈ R d1×d1 is a diagonal matrix whose diagonal elements are Bernoulli random variables distributed as B ii ∼ 1 1-p Ber(1 -p). In this case, it is easy to show that for any p ∈ [0, 1):

L drop (U, V) = L(U, V) + p 1 -p R(U, V), R(U, V) = d1 i=1 1 n n j=1 (u i A (j) v i ) 2

where R(U, V) is a data-dependent term that captures the explicit regularizer due to dropout (see Proposition 1 in the Appendix). Provided that the sample size n is large enough, the explicit regularizer is well concentrated around its mean (see Lemma 2 in the Appendix). Further, given that we seek a minima of L 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:

Θ(M) := min UV =M R(U, V), where R(U, V) := E A [ R(U, V)].

Surprisingly, for a wide range of random measurements, Θ(•) turns out to be a "suitable" regularizer.

Here, we instantiate two important examples (see Proposition 2 in the Appendix).

Gaussian measurements. For all j ∈ [n], let A (j) be standard Gaussian matrices. Then Θ(M) = Matrix completion. For all j ∈ [n], let 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 j-th column, respectively. Then

Θ(M) = 1 d 1 diag( √ p)UV diag( √ q) 2 *

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 with dropout in terms of the value of the explicit regularizer at the minimum of the empirical problem. Theorem 1. Without loss of generality, assume that d 2 ≥ d 0 and M * ≤ 1. Furthermore, assume that min i,j p(i)q(j) ≥ log(d2) n √ d2d0 . Let (U, V) be a minimizer of the dropout ERM objective in equation (2), and assume that max i U(i, :) 2 ≤ γ, max i V(i, :) 2 ≤ γ. Let α be such that R(U, V) ≤ α/d 1 . Then, for any δ ∈ (0, 1), the following generalization bounds holds with probability at least 1 -2δ over a sample of size n:

L(U, V) ≤ L(U, V) + C(1 + γ) αd 2 log(d 2 ) n + C (1 + γ 2 ) log(2/δ) 2n

as long as n = Ω (d 1 γ 2 /α) 2 log(2/δ) , where C, C are some absolute constants.

The proof of Theorem 1 follows from standard generalization bounds for 2 loss (Mohri et al., 2018) based on the Rademacher complexity (Bartlett & Mendelson, 2002) of the class of functions with weighted trace-norm bounded by √ α, i.e. M α := {M : diag( √ p)M diag( √ q) 2 * ≤ α}. A bound on the Rademacher complexity of this class was established by Foygel et al. (2011) . The technicalities here include showing that the explicit regularizer is well concentrated around its expected value, as well as deriving a bound on the supremum of the predictions. A few remarks are in order.

We require that the sampling distributions be non-degenerate, as specified by the condition min i,j p(i)q(j) ≥ log(d2) n √ d2d0 . This is a natural requirement for bounding the Rademacher complexity of M α , as discussed in Foygel et al. (2011) .

We note that for large enough sample size, R(U,

V) ≈ R(U, V) ≈ Θ(UV ) = 1 d1 diag( √ p)UV diag( √ q) 2 * ,

where the second approximation is due the fact that the pair (U, 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 R(U, V) ≤ α/d 1 in the statement of the corollary.

In practice, for models that are trained with dropout, the training error L(U, V) is negligible (see Figure 1 for experiments on the MovieLens dataset). Moreover, given that the sample size is large enough, the third term can be made arbitrarily small. Having said that, the second term, which is Õ(γ αd 2 /n), dominates the right hand side of generalization error bound in Theorem 6.

The assumption max i U(i, :) 2 ≤ γ, max i V(i, :) 2 ≤ γ is motivated by the practice of deep learning; such max-norm constraints are typically used with dropout, where the norm of the vector of incoming weights at each hidden unit is constrained to be bound by a constant (Srivastava et al., 2014) . In this case, if a dropout update violates this constraint, the weights of the hidden unit are projected back to the constraint norm ball. In proofs, we need this assumption to give a concentration bound for the empirical explicit regularizer, as well as bound the supremum deviation between the predictions and the true values. We remark that the value of γ also determines the complexity of the function class. On one hand, the generalization gap explicitly depends on and increases with γ. However, when γ is large, the constraints on U, V are milder, so that L(U, V) can be made smaller.

Finally, the required sample size heavily depends on the value of the explicit regularizer at the optima (α/d 1 ), and hence, on the dropout rate p. In particular, increasing the dropout rate increases the regularization parameter λ := p 1-p , thereby intensifies the penalty due to the explicit regularizer. Intuitively, a larger dropout rate p results in a smaller α, thereby a tighter generalization gap can be guaranteed. We show through experiments that that is indeed the case in practice.

3. DEEP NEURAL NETWORKS:

Next, we focus on neural networks with multiple hidden layers. Let X ⊆ R d0 and Y ⊆ R d k denote the input and output spaces, respectively. Let D denote the joint probability distribution on X × Y.

Given n examples {(x i , y i )} n i=1 ∼ D n drawn i.i.d. from the joint distribution and a loss function : Y × Y → R, the goal of learning is to find a hypothesis f w : X → Y, parameterized by w, that has a small population risk L(w)

:= E D [ (f w (x), y)].

We focus on the squared 2 loss, i.e., (y, y ) = yy 2 , and study the generalization properties of the dropout algorithm for minimizing the empirical risk L(w

) := 1 n n i=1 [ y i -f w (x i ) 2 ].

We consider the hypothesis class associated with feed-forward neural networks with k layers, i.e., functions of the form

f w (x) = W k σ(W k-1 σ(• • • W 2 σ(W 1 x) • • • )), where W i ∈ R di×di-1 , for i ∈ [k]

, is the weight matrix at i-th layer. The parameter w is the collection of weight matrices {W k , W k-1 , . . . , W 1 } and σ : R → R is an activation function applied entrywise to an input vector.

In modern machine learning systems, rather than talk about a certain network topology, we should think in terms of layer topology where each layer could have different characteristics -for example, fully connected, locally connected, or convolutional. In convolutional neural networks, it is a common practice to apply dropout only to the fully connected layers and not to the convolutional layers. Furthermore, in deep regression, it has been observed that applying dropout to only one of the hidden layers is most effective (Lathuilière et al., 2019) . In our study, dropout is applied on top of the learned representations or features, i.e. the output of the top hidden layer. In this case, dropout updates can be viewed as stochastic gradient descent iterates on the dropout objective:

L drop (w) := 1 n n i=1 E B y i -W k Bσ(W k-1 σ(• • • W 2 σ(W 1 x i ) • • • )) 2 (dropout objective)

where B is a diagonal random matrix with diagonal elements distributed identically and independently as

B ii ∼ 1 1-p Bern(1 -p), i ∈ [d k-1 ],

for some dropout rate p. We seek to understand the explicit regularizer due to dropout:

R(w) := L drop (w) -L(w) (explicit regularizer)

We denote the output of the i-th hidden node in the j-th hidden layer on an input vector x by a i,j (x) ∈ R; for example, a 1,2 (x) = σ(W 2 (1, :) σ(W 1 x)). Similarly, the vector a j (x) ∈ R dj denotes the activation of the j-th layer on input x. Using this notation, we can conveniently rewrite the dropout objective as L drop (w

) := 1 n n i=1 E B y i -W k Ba k-1 (x i ) 2 .

It is then easy to show that the explicit regularizer due to dropout is given as (see Propostion 3 in the Appendix):

R(w) = p 1 -p d k-1 j=1 W k (:, j) 2 a 2 j , where a j = 1 n n i=1 a j,k-1 (x i ) 2 .

The explicit regularizer R(w) is the summation over hidden nodes, of the product of the squared norm of the outgoing weights with the empirical second moment of the output of the corresponding neuron. For a two layer neural network with ReLU, when the input distribution is symmetric and isotropic, the expected regularizer is equal to (see Proposition 4 in the Appendix)

EQUATION

which is precisely the squared 2 path-norm of the network (Neyshabur et al., 2015) . We note that such a connection has been previously established for deep linear networks Mianjy et al. (2018) ; Mianjy & Arora (2019) ; here we have extended that result to single hidden layer ReLU networks.

Next, in order to understand the generalization properties of the dropout algorithm, we bound the Rademacher complexity of the function class with bounded expected explicit regularizer, i.e.

F α := {f : x → f w (x) : d k-1 j=1 W k (:, j) 2 a 2 j ≤ α},

where

a 2 j := E x [ a 2 j ] = E x [a j,k-1 (x) 2 ]

is the expected squared neural activation for the j-th hidden node. For simplicity, we focus on networks with one output neuron; extension to multiple output neurons is rather straightforward. Recall that the Rademacher complexity is a sample dependent measure of the capacity of a hypothesis class that bounds the generalization gap, i.e., the difference between the empirical and true risks (Bartlett & Mendelson, 2002) . Let S = {(x 1 , y 1 ), • • • , (x n , y n )} be a sample of size n. The empirical Rademacher complexity of F α with respect to S, and the expected Rademacher complexity are defined, respectively, as:

R S (F) = E σ sup f ∈F 1 n n i=1 σ i f (x i ), R n (F α ) = E x [R S (F α )].

The following lemma gives an upper bound on the expected Rademacher complexity of F α , which only depends on α and the width of the top layer d k-1 .

Lemma 1. For any sample size n and any α > 0 it holds that R n (F α ) ≤ d k-1 α n .

We would like to remark that the expected regularizer due to dropout, i.e. R(w), appears naturally when bounding the Rademacher complexity of deep neural networks. In particular, as we show in the proof of Lemma 1, the following upper bound holds for any class of neural networks F:

R n (F) ≤ 1 √ n d k-1 j=1 |W k (1, j)a j | ≤ 1 √ n d k-1 d k-1 j=1 W k (1, j) 2 a 2 j ,

where the second inequality is due to Cauchy-Schwartz. In particular, dropout directly controls the summation in the right hand side above. However, note that the second inequality above can in general be very loose for large width d k-1 , specifically if a small subset of hidden nodes J ⊂ [d k-1 ] co-adapt in a way that for all j ∈ [d k-1 ] \ J , the other hidden nodes are almost inactive, i.e. W k (1, j)a j ≈ 0. In this sense, dropout breaks "co-adaptation" between neurons by promoting solutions with (almost) equally contributing hidden neurons. For two-layer linear networks and deep linear networks with one output neuron, Mianjy et al. (2018) and Mianjy & Arora (2019) , respectively, showed that the minimum of the dropout objective is only achieved by equalized networks, for which Let R(w) ≤ α/2 be an upper bound on the explicit regularizer at w. Then, with probability at least 1 -2δ, over a sample of size n, we have that

|W k (1, j)a j | = |W k (1, j )a j |, ∀j ∈ [d k-1 ].

L(w) ≤ L(w) + C(1 + αd k-1 ) αd k-1 n + C (1 + d k-1 α) 2 log(2/δ) 2n ,

as long as n = Ω(B 2 M 2 log(2/δ)/α 2 ), where C and C are absolute constants.

In practice, modern over-parameterized deep neural networks are usually trained to zero empirical loss, i.e., if w is a minimizer of the dropout objective, then L(w) is negligible (see, e.g. Figure 2 for the empirical error of convolutional neural networks trained with dropout on Fashion MNIST and CIFAR-10). In such settings, we expect the last two terms on the right hand side to be the dominant terms -this implies that the right hand side above is in the order of O(αd k-1 log(2/δ)/n).

Interestingly, the upper bound presented in Theorem 2 has no explicit dependence on the network depth, except through the assumption that

W k F k-1 i=1 W i ≤ √ M

, which we argue is a very mild assumption and somewhat inevitable, as discussed in Golowich et al. (2018) . In particular, if the spectral norm of the weight matrices are concentrated around 1, then M is very small. On the contrary, most generalization bounds on deep networks depend on the product of the stable rank of the layers, resulting in exponential dependence on the network depth (e.g., see Bartlett et al. (2017) ; Neyshabur et al. ( 2017) and the references therein). Furthermore, there is no explicit dependence on the widths of the hidden layers, except through αd k-1 . We note that in most state-of-the-art models, d k-1 is not large, and as we discussed earlier, dropout implicitly equalizes the network in a way that αd k-1 ≈

d k-1 j=1 |W k (1, j)a j |,

which does not explicitly depend on the width. Finally, we remark that Theorem 2 is not limited to ReLU and can be extended to any Lipschitz activation function.

3.1. LINEAR REGRESSION:

We recall recent results from Mianjy et al. (2018) and Mianjy & Arora (2019) that characterize the explicit regularizer R(w) in the simpler setting of deep linear networks, where σ(•) is the identity map and the network computes a linear mapping f w : x → W k • • • W 1 x. In particular, they showed that if f is a deep linear network with one output neuron, then it holds that

ν f 2 C = min f =fw R(w),

where ν is a regularization parameter independent of the parameters w. For linear regression (i.e., for k = 1 and u = W 1 ∈ R d0 ), this result implies that least squares regression using dropout amounts to solving the following regularized problem:

min u∈R d 0 1 n n i=1 (y i -u x i ) 2 + ν u 2 C .

All the minimizers of the above problem are solutions to the following system of linear equations

(1 + ν)X Xu = X y, where X = [x 1 , • • • , x n ] ∈ R n×d0 , y = [y 1 , • • • , y n ] ∈ R n×1

are the design matrix and the response vector, respectively. Recall that if standard Tikhonov regularization with parameter ν were used instead of dropout, then the minimizer would have been the solutions to the system of linear equations (X X + νI)u = X y. The spectral augmentation due to Tikhonov regularization is helpful because it results in a well-posed problem, even if the the original (ν = 0) system was under-determined. On the contrary, the dropout regularizer manifests itself merely as a scaling of the parameters, under which the problem remains ill-posed e.g. if n < d 0 . More importantly, Tikhonov regularization discards the directions that account for small variance in data even when they exhibit good discriminability, which is a useful prior for learning in general. Dropout, however, does not seem to yield a useful inductive bias for linear regression. However, in the case of deep neural networks, as we show in the previous section, dropout does yield a useful inductive bias. In the rest of the paper, we confirm this theoretical result with an extensive empirical study. 

4. EXPERIMENTAL RESULTS:

In this section, we empirically evaluate our theoretical findings on several real world datasets1 . All results are averaged over 50 independent runs with random initialization. We report experiments for plain SGD as well as dropout with various dropout rates. For deep neural networks, the activation function is always ReLU.

4.1. MATRIX COMPLETION:

In this section, we explore the generalization properties of matrix completion with dropout algorithm on the MovieLens dataset Harper & Konstan (2016) . MovieLens is 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 standard He initialization scheme. We train the model for 100 epochs over the training data, where we use a fixed learning rate of lr = 1, and a batch size of 2000.

In our experiments, changing the learning rate or the batch size does not significantly improve the performance of any of these algorithms. We report the results for plain SGD (p = 0.0) as well as the dropout algorithm with p ∈ {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 ∈ {30, 110, 150, 190}.

It is remarkable, how even in the "simple" problem of matrix completion, plain SGD lacks a proper inductive bias. As it is clearly depicted in the middle plot, without explicit regularization -in particular early stopping or dropout in this figure -SGD suffers from gross overfitting. We further illustrate this fact 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 significantly better (> 0.01 difference in test RMSE).

In this section, we report our experimental results for training convolutional neural networks with and without dropout, on Fashion MNIST and CIFAR-10. The Fashion MNIST dataset of Zalando's article images contains 60K training examples and 10K test examples each, where each example is a 28 × 28 grayscale image, associated with a label from 10 classes. The CIFAR-10 dataset consists of 60K 32 × 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) .

For the Fashion MNIST dataset, we use a convolutional neural network with one convolutional layer and two fully connected layers. The convolutional layer has 16 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 width ∈ {2 5 , 2 6 , • • • 2 12 }. In all experiments, the linear layer weights are initialized using standard Xavier initialization, and a fixed learning rate 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 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 width ∈ {2 5 , 2 6 , . . . , 2 12 }. In all the experiments, an initial learning rate 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. We did not observe significant changes in the training/test errors by running the experiments longer.

Figure 2 shows the test error, training error, the generalization gap, and the Rademacher complexity bound in Lemma 1 as a function of the number of hidden nodes in the top hidden layer. It is not at all surprising that on all datasets, the training error of plain SGD is always the smallest, whereas dropout always enjoys a smaller generalization gap. For Fashion MNIST, which is a fairly "simple" dataset, there is no significant difference between the test performance of plain SGD and dropout; dropout performs better only when the network is highly over-parameterized. However, for CIFAR-10, dropout is always helpful in achieving better test performance. More interestingly, with dropout, the bound on the Rademacher complexity is predictive of the generalization gap, in the sense that 1) both are roughly in the same range (≈ 0.015), and 2) a smaller bound corresponds to a curve with smaller generalization gap.

5. DISCUSSION:

Motivated by the success of dropout in deep learning, we propose 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 deep neural networks, using which we give a generalization error bound in terms of the value of the regularizer. We evaluate our theoretical findings for training convolutional neural networks on real world datasets including CIFAR-10.

We leave several important questions for future work. It would be interesting to study the optimization theoretic aspects of training with dropout. In particular, the results presented in this paper is based on the assumption that dropout finds an (approximate) empirical minimizer; although this is widely supported by practice, giving precise convergence rates remains an open question. Another direction for future work is to understand the function class approximated by neural networks with dropout layer. For example, it is known that deep ReLU networks represent the class of piecewise linear functions (Arora et al., 2018) . What can we say about the function class approximated by neural networks with norm-bounded weight matrices, due to dropout.

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

L drop (U, V) = 1 n n i=1 E b [(y i -UBV , A (i) ) 2 ] = 1 n n i=1 (y i -UV , A (i) ) 2 + 1 n n i=1 p 1 -p d1 j=1 (u j A (i) v j ) 2 = L(U, V) + p 1 -p R(U, V).

which completes the proof.

Proposition 2. [Induced regularizer] The followings hold true.

1. Matrix completion. For j ∈ [n], let 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

Θ(M) = 1 d1 diag( √ p)UV diag( √ q) 2 * .

2. i.i.d. measurements. For all j ∈ [n], let the elements of A (j) be distributed i.i.d. with zero mean and unit variance. Then

Θ(M) = 1 d1 M 2 * .

Proof of Proposition 2. For any pair of factors (U, V) it holds that

R(U, V) = d1 i=1 E(u i Av i ) 2 = d1 i=1 d2 j=1 d0 k=1 p(j)q(k)(u i e j e k v i ) 2 = d1 i=1 d2 j=1 d0 k=1 p(j)q(k)U(j, i) 2 V(k, i) 2 = d1 i=1 diag( √ p)u i 2 diag( √ q)v i 2 ≥ 1 d 1 d1 i=1 diag( √ p)u i diag( √ q)v i 2 = 1 d 1 d1 i=1 diag( √ p)u i v i diag( √ q) * 2 ≥ 1 d 1 diag( √ p) d1 i=1 u i v i diag( √ q) *

We evaluate the expected dropout regularizer at UQ, VQ:

R(UQ, VQ) = d1 i=1 diag( √ p)Uq i 2 diag( √ q)Vq i 2 = d1 i=1 1 d 2 1 diag( √ p)UV diag( √ q) 2 * = 1 d 1 diag( √ p)UV diag( √ q) 2 *

≤ Θ(UV ) which completes the proof of the first part.

Similarly for the second part, we first show that any pair of factors

(U, V), R(U, V) geq 1 d1 UV 2 * : R(U, V) = d1 i=1 E(u i Av i ) 2 = d1 i=1 E( d2 j=1 d2 j=1 U ji A jk V ki ) 2 = d1 i=1 d2 j,j =1 d0 k,k =1 U ji U j i V ki V k i E[A jk A j k ] = d1 i=1 d2 j=1 d0 k=1 U 2 ji V 2 ki E[A 2 jk ] = d1 i=1 d2 j=1 d0 k=1 U 2 ji V 2 ki = d1 i=1 u i 2 v i 2 ≥ 1 d 1 d1 i=1 u i v i 2 = 1 d 1 d1 i=1 u i v i * 2 ≥ 1 d 1 d1 i=1 u i v i * 2 = 1 d 1 UV 2 *

where the first and the second inequaliteis are due to Cauchy-Schwartz and the triangle inequality, respectively. The equality right after the first inequality follows because for any pair of vectors a, b, it holds that ab * = ab = a b . Now again using Theorem 5 on (U, V), there exist a rotation matrix Q such that Uq i Vq i = 1 d1 UV * . We evaluate the expected dropout regularizer at UQ, VQ:

R(UQ, VQ) = d1 i=1 Uq i 2 Vq i 2 = d1 i=1 1 d 2 1 UV 2 * = 1 d 1 UV 2 * ≤ Θ(UV )

which completes the proof of the the second part.

Lemma 2. Assume U, V is such that max i U(i, :) 2 ≤ γ, max i V(i, :) 2 ≤ γ. Then, with probability at least 1 -δ over a sample of size n, we have that

|R(U, V) -R(U, V)| ≤ Cγ 2 log(2/δ) √ n .

C DEEP NEURAL NETWORKS:

Proposition 3 (Dropout regularizer in deep regression).

L drop (w) = L(w) + R(w), where R(w) = λ

d k-1 j=1 W k (:, j) 2 a 2 j .

where a j = 1 n n i=1 a j,k-1 (x i ) 2 and λ = p 1-p is the regularization parameter.

Proof of Proposition 3. Recall that E[B ii ] = 1 and Var(B ii ) = p 1-p . Conditioned on x, y in the current mini-batch, we have that

E B [ y -W k Ba k-1 (x) 2 ] = d k i=1 E B (y i -W k (i, :) Ba k-1 (x)) 2 .

(

EQUATION

where a j (x) ∈ R dj is the activation vector of the j-th hidden layer for input x, i.e. a j (x)[i] = a i,j (x).

The following holds by the of variance for each of the summands above:

E B (y i -W k (i, :) Ba k-1 (x)) 2 = E B [y i -W k (i, :) Ba k-1 (x)] 2 + Var(y i -W k (i, :) Ba k-1 (x))

Since E[B] = I, the first term on right hand side is equal to (y i -W k (:, i) a k-1 (x)) 2 . For the second term we have

Var(y i -W k (i, :) Ba k-1 (x)) = Var(W k (i, :) Ba k-1 (x)) = Var( d k-1 j=1 W k (i, j)B jj a j,k-1 (x)) = d k-1 j=1 (W k (i, j)a j,k-1 (x)) 2 Var(B jj ) = p 1 -p d k-1 j=1 W k (i, j) 2 a j,k-1 (x) 2

Plugging the above into Equation ( 5)

E B [ y -W k Ba k-1 (x) 2 ] = y -W k a k-1 (x) 2 + p 1 -p d k-1 j=1 W k (:, j) 2 a j,k-1 (x) 2

Now taking the empirical average with respect to x, y, we get

L drop (w) = L(w) + p 1 -p d k-1 j=1 W k (:, j) 2 a 2 j = L(w) + R(w)

which completes the proof.

Proposition 4. Consider a two layer neural network f w (•) with ReLU activation functions in the hidden layer. Furthermore, assume that the marginal input distribution P X (x) is symmetric and isotropic, i.e., P X (x) = P X (-x) and E[xx ] = I. Then the following holds for the expected explicit regularizer due to dropout:

EQUATION

Proof of Proposition 4. Using Proposition 3, we have that:

R(w) = E[ R(w)] = λ d1 j=1 W 2 (:, j) 2 E[σ(W 1 (j, :) x) 2 ]

It remains to calculate the quantity E x [σ(W 1 (j, :) x) 2 ]. By symmetry assumption, we have that P X (x) = P X (-x). As a result, for any v ∈ R d0 , we have that P(v x) = P(-v x) as well. That is, the random variable z j := W 1 (j, :) x is also symmetric about the origin. It is easy to see that

E z [σ(z) 2 ] = 1 2 E z [z 2 ]. E z [σ(z) 2 ] = ∞ -∞ σ(z) 2 dµ(z) = ∞ 0 σ(z) dµ(z) = ∞ 0 z 2 dµ(z) = 1 2 ∞ ∞ z 2 dµ(z) = 1 2 E z [z 2 ].

Plugging back the above identity in the expression of R(w), we get that

R(w) = λ d1 j=1 W 2 (:, j) 2 E[(W 1 (j, :) x) 2 ] = λ d1 j=1 W 2 (:, j) 2 W 1 (j, :) 2

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

Proof of Lemma 1. Given a dataset S, we start by bounding the empirical Rademahcer complexity:

R S (F α ) = E σ sup fw∈Fα 1 n n i=1 σ i f w (x i ) = E σ sup f ∈Fα 1 n n i=1 σ i d k-1 j=1 W k (1, j)a j,k-1 (x i ) = E σ sup fw∈Fα 1 n d k-1 j=1 W k (1, j)a j n i=1 σ i a j,k-1 (x i ) a j ≤ sup fw∈Fα d k-1 j=1 |W k (1, j)a j | • 1 n E σ sup fw∈Fα max j∈[d k-1 ] | n i=1 σ i a j,k-1 (x i ) a j |

The first term on the right hand side is bounded as:

d k-1 j=1 |W k (1, j)a j | ≤ d k-1 d k-1 j=1 W k (1, j) 2 a 2 j (Cauchy-Schwartz) ≤ d k-1 α

We now consider the function class

F := {h w : x → σ(vσ(W k-2 σ(• • • W 2 σ(W 1 x) • • • )), E x [h w(x) 2 ] = 1}

Plugging back the above and noting that a j ≥ 0, we have

R S (F α ) ≤ d k-1 α n E σ sup a 2 j =1 max j∈[d k-1 ] | n i=1 σ i a j,k-1 (x i )| ≤ d k-1 α n E σ sup hw∈ F | n i=1 σ i h w(x i )|

Let w * be the maximizer of the right hand side, i.e.

E σ | n i=1 σ i h w * (x i )| = sup hw∈ F | n i=1 σ i h w * (x i )| Then, it holds that R n (F α ) = E x [R S (F α )] ≤ d k-1 α n E x,σ | n i=1 σ i h w * (x i )| ≤ d k-1 α n E x E σ n i=1 σ i h w * (x i ) 2 = d k-1 α n n i=1 E x h w * (x i ) 2 = d k-1 α n

which completes the proof of the Lemma.

Lemma 3. Assume that W k F k-1 i=1 W i ≤ √ M , and that sup x∈X x ≤ √ B, sup y∈Y |y| ≤ 1.

Then with probability at least 1 -δ over a sample of size n, we have that

|R(w) -R(w)| ≤ CBM log(2/δ) √ n ,

where C is an absolute constant.

Proof of Lemma 3. Define X :=

d k-1 j=1 W k (:, j) 2 a j,k-1 (x ) 2 and observe that X = d k-1 j=1 W k (:, j) 2 a j,k-1 (x ) 2 = d k-1 j=1 W k (:, j) 2 σ (W k-1 (j, :)a k-1 (x )) 2 ≤ d k-1 j=1 W k (:, j) 2 (W k-1 (j, :)a k-1 (x )) 2 ≤ d k-1 j=1 W k (:, j) 2 W k-1 (j, :) 2 a k-1 (x ) 2 ≤ a k-1 (x ) 2 max i W k-1 (i, :) 2 d k-1 j=1 W k (:, j) 2 ≤ x 2 W 1 2 • • • W k-1 2 W k 2 F

≤ BM where the first inequality follows from the definition of ReLU, and the second inequality is due to Cauchy-Schwartz. Thus, X w, is a sub-Gaussian (more strongly, bounded) random variable with mean E[X ] = R(w) and sub-Gaussian norm X ψ2 ≤ BM/ ln(2). Furthermore, X -R(w) ψ2 ≤ C X ψ2 ≤ CBM , for some absolute constants C , C (Lemma 2.6.8 of Vershynin ( 2018)). Using Theorem 3, for t = CBM log 2/δ n we get that:

P R(w) -R(w) ≥ t = P 1 n n =1 X -R(w) ≥ CBM log n n ≤ δ,

which completes the proof.

Proof of Theorem 2. We use Theorem 4 to give a bound on the generalization gap. From Lemma 3, we have with probability at least 1 -δ that

R(w) ≤ R(w) + CBM log(2/δ) √ n ≤ α 2 + α 2 = α

where the second inequality holds whenever n ≥ 4C 2 B 2 M 2 log(2/δ)/α 2 . Define the class of deep neural networks with dropout regularizer bounded by √ α, i.e. F α = {f w : R(w) ≤ α}. By

Lemma 1, we have that R n (F α ) ≤ αd k-1 n . It remains to bound the supremum deviation between true labels and those predicted by networks that belong to F α : holds with probability at least 1 -2δ, which completes the proof. 

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 ∈ {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 ∈ {110, 150, 190}), they consistently outperform plain SGD as well as other dropout rates.

:

To ensure reproducibility of the results, we have uploaded the code.

= 1 d 1 diag( √ p)UV diag( √ q) 2 *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 a, b, ab * = ab = a b . Since the inequalities hold for any U, V, it implies thatΘ(UV ) ≥ 1 d 1 diag( √ p)UV diag( √ q) 2 * .Applying Theorem 5 on (diag( √ p)U, diag( √ p)V), there exist a rotation matrix Q such thatdiag( √ p)Uq i diag( √ q)Vq i = 1 d 1 diag( √ p)UV diag( √ q) *

Figures and Tables:

is the standard trace-norm regularization studied in Srebro et al. (2005); Bach (2008); Candès & Tao (2009).

Figure 2: Fashion MNIST (top) and CIFAR-10 (bottom): the training error, the generalization gap, and the Rademacher complexity bound in Lemma 1 for plain SGD and dropout with p ∈ {0.25, 0.50, 0.75} as a function of the width of the top hidden layer.

k (:, j) 2 a j,k-1 (x) 2 ≤ 1 + d k-1 αwhere the second inequality follows from the assumption sup y∈Y |y| ≤ 1, and third and the forth inequalities are due to the triangle inequality and Cauchy-Schwartz, respectively. Plugging the above results in Theorem 4 and using union bound we getL(w) ≤ L(w) + C(1 + αd k-1 ) αd 2 n + C (1 + d k-1 α) 2 log(2/δ) 2n

Figure 1: MovieLens dataset: the training error (top), the test error (middle), and the generalization gap for plain SGD as well as dropout with p ∈ {0.25, 0.50, 0.75} as a function of the number of iterates, for different sizes d1 = 30 (first column), d1 = 110 (second column), d1 = 150 (third column), and d1 = 190 (forth column).

For such equalized networks, the second inequality above holds with equality, where the value of the explicit regularizer gives a tight bound on the Rademacher complexity. Whether such equalization property extends beyond linear activations is an interesting open question which we leave for future work.

Table content: <table/>

MovieLens dataset: Test RMSE of plain SGD as well as the dropout algorithm with various dropout rates for various factorization sizes. The grey cells shows the best performance(s) in each row.

Table content: <table><tr><td>0.7 0.8 0.9 1.0</td><td/><td colspan="2">Train RMSE</td><td colspan="2">p=0.10 p=0.20 p=0.30 p=0.40 plain SGD</td><td>0.80 0.82 0.85 0.88 0.90 0.93</td><td/><td colspan="2">Test RMSE</td><td/><td/><td>0.05 0.10 0.15 0.20</td><td colspan="4">Generalization gap</td><td/></tr><tr><td>0.6</td><td>100k</td><td>200k</td><td>300k</td><td>400k</td><td>500k</td><td>0.78</td><td>100k</td><td>200k</td><td>300k</td><td>400k</td><td>500k</td><td>0.00</td><td>100k</td><td>200k</td><td>300k</td><td>400k</td><td>500k</td></tr><tr><td colspan="18">Figure 1: MovieLens dataset: the training error (left), the test error (middle), and the generalization gap</td></tr><tr><td colspan="18">(right) for plain SGD and dropout with p ∈ {0.1, 0.2, 0.3, 0.4} as a function of the number of iterations. The</td></tr><tr><td colspan="5">factorization size is d1 = 70.</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td colspan="3">plain SGD</td><td/><td/><td/><td colspan="3">dropout</td><td/><td/><td/><td/></tr><tr><td/><td/><td>width</td><td/><td colspan="12">last iterate best iterate p = 0.1 p = 0.2 p = 0.3 p = 0.4</td><td/><td/></tr><tr><td/><td/><td colspan="2">d 1 = 30</td><td colspan="2">0.8041</td><td/><td>0.7938</td><td/><td colspan="2">0.7805</td><td>0.785</td><td/><td>0.7991</td><td/><td>0.8186</td><td/><td/></tr><tr><td/><td/><td colspan="2">d 1 = 70</td><td colspan="2">0.8315</td><td/><td>0.7897</td><td/><td colspan="2">0.7899</td><td colspan="2">0.7771</td><td>0.7763</td><td/><td>0.7833</td><td/><td/></tr><tr><td/><td/><td colspan="2">d 1 = 110</td><td colspan="2">0.8431</td><td/><td>0.7873</td><td/><td colspan="2">0.7988</td><td colspan="2">0.7813</td><td>0.7742</td><td/><td>0.7743</td><td/><td/></tr><tr><td/><td/><td colspan="2">d 1 = 150</td><td colspan="2">0.8472</td><td/><td>0.7858</td><td/><td colspan="2">0.8042</td><td colspan="2">0.7852</td><td>0.7756</td><td/><td>0.7722</td><td/><td/></tr><tr><td/><td/><td colspan="2">d 1 = 190</td><td colspan="2">0.8473</td><td/><td>0.7844</td><td/><td colspan="2">0.8069</td><td colspan="2">0.7879</td><td>0.7772</td><td/><td>0.772</td><td/><td/></tr></table>

Peer review (iclr2020):
Summary: This work studies the effect of regularization through dropout on generalization bounds for Matrix Sensing and linear regression with deep neural network task. For both matrix sensing task and linear regression task, authors derive an explicit regularization term due to dropout. Authors give elegant interpretations of dropout regularizer. For matrix sensing: dropout can be thought of as the inducing trace-norm regularization when matrices are standard gaussian. For matrix completion: dropout can be thought of as weighted trace-norm regularizer. Authors then give a generalization bound for matrix completion with dropout. In the context of deep neural networks, under assumptions on the input distribution authors show that the explicit regularizer associated with dropout is exactly the squared l2 path-norm of the network. Authors give a bound on the Rademacher complexity of deep nerual networks with dropout. Using the bound on Rademacher complexity, authors derive the a generalization bound for squared error loss. I recommend rejecting this submission. Following are my concerns: 1. Authors derive the bound on the Rademacher complexity in Lemma 1 and claim that this bound holds for any neural network, but in the proof they make assumptions on the output of the neural network that are not stated clearly. Assumptions, as far as I understand, are 1) expected output under the data distribution of the jth unit is bounded by 1 and 2) the second moment is also equal to 1. I believe that this is not true for most of the neural networks with RELU nonlinearity for the output units. 2. For the proof of Theorem 2, authors derive the supremum deviation between the true labels and those predicted by the neural network. I don’t believe the 5th inequality on page 19. Authors bound the worst case output of the neural network by the expected output of the neural network which is not true. 3. I am not yet convinced by the experiments section of the paper where they evaluate the generalization gap for datasets. In particular, the theorems derived in the paper has assumptions on the sample complexity. These assumptions are not verified for the datasets used in the experiment section and I suspect that lower bound on n can be too large for the bounds to be meaningful. 4. There is no comparison to existing literature on generalization bounds due to dropout as a regularizer. Following paper derives PAC-Bayes bound for dropout procedure: McAllester, D.A. (2013). A PAC-Bayesian Tutorial with A Dropout Bound. ArXiv, abs/1307.2118.