Year: 2019

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.

heading: 1 INTRODUCTION
text: 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 (Lathuiliè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.

heading: 1.1 NOTATION
text: 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 ∈ Rd, diag(x) ∈ Rd×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‖2C = x>Cx. The standard inner product is represented by 〈·, ·〉, for vectors or matrices, where 〈X,X′〉 = Tr(X>X′).

heading: 2 MATRIX SENSING
text: 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∗ ∈ Rd2×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 yi = 〈M∗,A(i)〉 such that n d2d0. 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∈Rd2×d1 ,V∈Rd0×d1
L̂(U,V) := 1
n n∑ i=1 (yi − 〈UV>,A(i)〉)2. (1)
When d1 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); Candè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:
L̂drop(U,V) = 1
n n∑ j=1 EB(yj − 〈UBV>,A(j)〉)2, (2)
where B ∈ Rd1×d1 is a diagonal matrix whose diagonal elements are Bernoulli random variables distributed as Bii ∼ 11−pBer(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)vi)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) := EA[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) = 1 d1 ‖M‖2∗ is the standard trace-norm regularization studied in Srebro et al. (2005); Bach (2008); Candès & Tao (2009).
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 d1 ‖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 d2 ≥ d0 and ‖M∗‖ ≤ 1. Furthermore, assume that mini,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 maxi ‖U(i, :)‖2 ≤ γ, maxi ‖V(i, :)‖2 ≤ γ. Let α be such that R̂(U,V) ≤ α/d1. 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 + γ) √ αd2 log(d2)
n + C ′(1 + γ2)
√ log(2/δ)
2n as long as n = Ω ( (d1γ 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 mini,j p(i)q(j) ≥ log(d2)n√d2d0 . This is a natural requirement for bounding the Rademacher complexity ofMα, 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/d1. Hence the assumption R̂(U,V) ≤ α/d1 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 Õ(γ √ αd2/n), dominates the right hand side of generalization error bound in Theorem 6.
The assumption maxi ‖U(i, :)‖2 ≤ γ, maxi ‖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 (α/d1), and hence, on the dropout rate p. In particular, increasing the dropout rate increases the regularization parameter λ := p1−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.

heading: 3 DEEP NEURAL NETWORKS
text: Next, we focus on neural networks with multiple hidden layers. Let X ⊆ Rd0 and Y ⊆ Rdk denote the input and output spaces, respectively. Let D denote the joint probability distribution on X × Y . Given n examples {(xi, yi)}ni=1 ∼ Dn drawn i.i.d. from the joint distribution and a loss function ` : Y × Y → R, the goal of learning is to find a hypothesis fw : X → Y , parameterized by w, that has a small population risk L(w) := ED[`(fw(x), y)].
We focus on the squared `2 loss, i.e., `(y, y′) = ‖y − y′‖2, and study the generalization properties of the dropout algorithm for minimizing the empirical risk L̂(w) := 1n ∑n i=1[‖yi − fw(xi)‖2]. We consider the hypothesis class associated with feed-forward neural networks with k layers, i.e., functions of the form fw(x) = Wkσ(Wk−1σ(· · ·W2σ(W1x) · · · )), where Wi ∈ Rdi×di−1 , for i ∈ [k], is the weight matrix at i-th layer. The parameter w is the collection of weight matrices {Wk,Wk−1, . . . ,W1} 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 (Lathuiliè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 EB‖yi −WkBσ(Wk−1σ(· · ·W2σ(W1xi) · · · ))‖2 (dropout objective)
where B is a diagonal random matrix with diagonal elements distributed identically and independently as Bii ∼ 11−pBern(1 − p), i ∈ [dk−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 ai,j(x) ∈ R; for example, a1,2(x) = σ(W2(1, :)>σ(W1x)). Similarly, the vector aj(x) ∈ Rdj 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) := 1n ∑n i=1 EB‖yi−WkBak−1(xi)‖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 dk−1∑ j=1 ‖Wk(:, j)‖2â2j , where âj = √√√√ 1 n n∑ i=1 aj,k−1(xi)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)
R(w) := E[R̂(w)] = 1
2 d0,d1,d2∑ i0,i1,i2=1 W2(i2, i1)2W1(i1, i0)2, (3)
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 7→ fw(x) : dk−1∑ j=1 ‖Wk(:, j)‖2a2j ≤ α},
where a2j := Ex[â2j ] = Ex[aj,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 = {(x1, y1), · · · , (xn, yn)} 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:
RS(F) = Eσ sup f∈F
1
n n∑ i=1 σif(xi), Rn(Fα) = Ex[RS(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 dk−1.
Lemma 1. For any sample size n and any α > 0 it holds that Rn(Fα) ≤ √ dk−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 :
Rn(F) ≤ 1√ n dk−1∑ j=1 |Wk(1, j)aj | ≤ 1√ n √√√√dk−1 dk−1∑ j=1 Wk(1, j)2a2j ,
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 dk−1, specifically if a small subset of hidden nodes J ⊂ [dk−1] co-adapt in a way that for all j ∈ [dk−1] \ J , the other hidden nodes are almost inactive, i.e. Wk(1, j)aj ≈ 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 |Wk(1, j)aj | = |Wk(1, j′)aj′ |, ∀j ∈ [dk−1]. 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.
The main result of this section, is the following theorem that bounds the generalization gap in networks trained by dropout.
Theorem 2. Consider deep neural networks with ReLU activation functions. Let w = {Wi}ki=1 be a minimizer of the dropout objective. Assume that ‖Wk‖F ∏k−1 i=1 ‖Wi‖ ≤ √ M , and that
supx∈X ‖x‖ ≤ √ B, supy∈Y |y| ≤ 1. 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
L(w) ≤ L̂(w) + C(1 + √ αdk−1) √ αdk−1 n + C ′(1 + √ dk−1α) 2 √ log(2/δ) 2n ,
as long as n = Ω(B2M2 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(αdk−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 ‖Wk‖F ∏k−1 i=1 ‖Wi‖ ≤ √ 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 √ αdk−1. We note that in most state-of-the-art models, dk−1 is not large, and as we discussed earlier, dropout implicitly equalizes the network in a way that √ αdk−1 ≈ ∑dk−1 j=1 |Wk(1, j)aj |, 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.

heading: 3.1 LINEAR REGRESSION
text: 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 fw : x 7→ Wk · · ·W1x. 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 ∈ Rd0 ), this result implies that least squares regression using dropout amounts to solving the following regularized problem:
min u∈Rd0
1
n n∑ i=1 (yi − u>xi)2 + ν‖u‖2Ĉ.
All the minimizers of the above problem are solutions to the following system of linear equations (1 + ν)X>Xu = X>y, where X = [x1, · · · , xn]> ∈ Rn×d0 , y = [y1, · · · , yn]> ∈ Rn×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 < d0. 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.

heading: 4 EXPERIMENTAL RESULTS
text: 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.

heading: 4.1 MATRIX COMPLETION
text: 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 d1 = 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 d1 ∈ {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
1To ensure reproducibility of the results, we have uploaded the code.
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).

heading: 4.2 DEEP NEURAL NETWORKS
text: 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 ∈ {25, 26, · · · 212}. 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 ∈ {25, 26, . . . , 212}. 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 CIFAR10, 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.

heading: 5 DISCUSSION
text: 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.

heading: A AUXILIARY RESULTS
text: Theorem 3 (Hoeffding’s inequality: Theorem 2.6.2 Vershynin (2018)). Let X1, . . . , XN be independent, mean zero, sub-Gaussian random variables. Then, for every t ≥ 0, we have
P (∣∣∣∣∣ 1N N∑ i=1 Xi ∣∣∣∣∣ ≥ t ) ≤ 2e − ct2N2∑N i=1 ‖Xi‖2ψ2
Theorem 4 (Theorem 10.3 of Mohri et al. (2018)). Assume that ‖h − f‖∞ ≤ M for all h ∈ H. Then, for any δ > 0, with probability at least 1 − δ over a sample {(xi, yi), i ∈ [n]} of size n, the following inequalities holds uniformly for all h ∈ H.
E[|h(x)− f(x)|2] ≤ 1 n n∑ i=1 |h(xi)− f(xi)|2 + 4MRn(H) +M2 √ log(2/δ) 2n
Theorem 5 (Theorem 3.3 in Mianjy et al. (2018)). For any pair of matrices U ∈ Rd2×d1 ,V ∈ Rd0×d1 , there exist a rotation matrix Q ∈ SO(d1) such that rotated matrices Ũ := UQ, Ṽ := VQ satisfy ‖ũi‖‖ṽi‖ = 1d1 ‖UV >‖∗, for all i ∈ [d1].
Theorem 6 (Theorem 1 in Foygel et al. (2011)). Assume that p(i)q(j) ≥ log(d2) n √ d2d0 for all i ∈ [d2], j ∈ [d0]. For any α > 0, letMα := {M ∈ Rd2×d1 : ‖diag( √ p)M diag( √ q)‖2∗ ≤ α} be the class of
linear transformations with weighted trace-norm bounded with √ α. Then the expected Rademacher complexity ofMα is bounded as follows:
Rn(Mα) ≤ O
(√ αd2 log(d2)
n
)

heading: B MATRIX SENSING
text: Proposition 1 (Dropout regularizer in matrix sensing). The following holds for any p ∈ [0, 1):
L̂drop(U,V) = L̂(U,V) + λR̂(U,V), where R̂(U,V) = d1∑ i=1 1 n n∑ j=1 (u>i A (j)vi)2. (4)
where λ = p1−p is the regularization parameter.
Proof of Proposition 1. The following equality follows from the definition of variance: Eb[(yi − 〈UBV>,A(i)〉)2] = ( Eb[yi − 〈UBV>,A(i)〉] )2 + Var(yi − 〈UBV>,A(i)〉)
Recall that for a Bernoulli random variable Bii, we have E[Bii] = 1 and Var(Bii) = p1−p . Thus, the first term on right hand side is equal to (yi − 〈UV>,A(i)〉)2. For the second term we have
Var(yi − 〈UBV>,A(i)〉) = Var( d1∑ j=1 Bjju>j A (i)vj) = d1∑ j=1 (u>j A (i)vj)2 Var(Bjj)
= p
1− p d1∑ j=1 (u>j A (i)vj)2
Plugging the above into Equation (5) and averaging over samples we get
L̂drop(U,V) = 1
n n∑ i=1 Eb[(yi − 〈UBV>,A(i)〉)2]
= 1
n n∑ i=1 (yi − 〈UV>,A(i)〉)2 + 1 n n∑ i=1 p 1− p d1∑ j=1 (u>j A (i)vj)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) = 1d1 ‖ 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) = 1d1 ‖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 Avi)2
= d1∑ i=1 d2∑ j=1 d0∑ k=1 p(j)q(k)(u>i eje > k vi) 2
= d1∑ i=1 d2∑ j=1 d0∑ k=1 p(j)q(k)U(j, i)2V(k, i)2
= d1∑ i=1 ‖ diag(√p)ui‖2‖ diag( √ q)vi‖2
≥ 1 d1 ( d1∑ i=1 ‖ diag(√p)ui‖‖diag( √ q)vi‖ )2
= 1
d1 ( d1∑ i=1 ‖ diag(√p)uiv>i diag( √ q)‖∗ )2
≥ 1 d1
( ‖diag(√p)
d1∑ i=1 uiv>i diag( √ q)‖∗ )2 = 1
d1 ‖ 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 d1 ‖ diag(√p)UV> diag(√q)‖2∗.
Applying Theorem 5 on (diag( √ p)U,diag( √ p)V), there exist a rotation matrix Q such that
‖ diag(√p)Uqi‖‖diag( √ q)Vqi‖ = 1 d1 ‖diag(√p)UV> diag(√q)‖∗
We evaluate the expected dropout regularizer at UQ,VQ:
R(UQ,VQ) = d1∑ i=1 ‖diag(√p)Uqi‖2‖ diag( √ q)Vqi‖2
= d1∑ i=1 1 d21 ‖ diag(√p)UV> diag(√q)‖2∗
= 1 d1 ‖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 1d1 ‖UV >‖2∗:
R(U,V) = d1∑ i=1 E(u>i Avi)2
= d1∑ i=1 E( d2∑ j=1 d2∑ j=1 UjiAjkVki)2
= d1∑ i=1 d2∑ j,j′=1 d0∑ k,k′=1 UjiUj′iVkiVk′iE[AjkAj′k′ ]
= d1∑ i=1 d2∑ j=1 d0∑ k=1 U2jiV 2 kiE[A2jk]
= d1∑ i=1 d2∑ j=1 d0∑ k=1 U2jiV 2 ki
= d1∑ i=1 ‖ui‖2‖vi‖2
≥ 1 d1 ( d1∑ i=1 ‖ui‖‖vi‖ )2
= 1
d1 ( d1∑ i=1 ‖uiv>i ‖∗ )2
≥ 1 d1 ( ‖ d1∑ i=1 uiv>i ‖∗ )2 = 1 d1 ‖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 ‖Uqi‖‖Vqi‖ = 1d1 ‖UV
>‖∗. We evaluate the expected dropout regularizer at UQ,VQ:
R(UQ,VQ) = d1∑ i=1 ‖Uqi‖2‖Vqi‖2 = d1∑ i=1 1 d21 ‖UV>‖2∗ = 1 d1 ‖UV>‖2∗ ≤ Θ(UV>)
which completes the proof of the the second part.
Lemma 2. Assume U,V is such that maxi ‖U(i, :)‖2 ≤ γ, maxi ‖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 .
Proof of Lemma 2. Define X` := ∑d1 w=1(u > wA (`)vw)2 and observe that
X` = d1∑ w=1 ∑ i,j UiwVjwA (`) ij 2
= d1∑ w=1 ∑ i,i′,j,j′ UiwUi′wVjwVj′wA (`) ij A (`) i′j′
= d1∑ w=1 ∑ i,j U2iwV 2 jwA (`) ij
≤ max i,j d1∑ w=1 U2iwV 2 jw
≤ max i,j ‖U(i, :)‖2‖V(j, :)‖2 ≤ γ2
where the third equality follows because for an indicator matrix A(`), it holds that A(`)ij A (`) i′j′ = 0 if (i, j) 6= (i′, j′). Thus, Xw,` is a sub-Gaussian (more strongly, bounded) random variable with mean E[X`] = R(U,V) and sub-Gaussian norm ‖X`‖ψ2 ≤ γ2/ ln(2). Furthermore, ‖X`−R(U,V)‖ψ2 ≤ C ′‖X`‖ψ2 ≤ Cγ2, for some absolute constants C ′, C (Lemma 2.6.8 of Vershynin (2018)). Using Theorem 3, for t = Cd1 √ log 2/δ n we get that:
P (∣∣∣R̂(U,V)−R(U,V)∣∣∣ ≥ t) = P(∣∣∣∣∣ 1n n∑ `=1 X` −R(U,V) ∣∣∣∣∣ ≥ Cγ2 √ log 2/δ n ) ≤ δ
which completes the proof.
Proof of Theorem 1. We use Theorem 4 to give a bound on the generalization gap. From Lemma 2, we have with probability at least 1− δ that
1 d1 ‖ diag(√p)UV> diag(√q)‖2∗ = Θ(UV>) ≤ R(U,V) (definition of Θ(·))
≤ R̂(U,V) + Cγ2 √ log(2/δ)√ n
(Lemma 2)
≤ α 2d1 + Cγ2 √ log(2/δ)√ n
(assumption of the Theorem)
≤ α d1
(whenever n ≥ 4d21γ4C2 log(2/δ)/α2)
Define the class of predictors with weighted trace-norm bounded by √ α, i.e. Mα = {M : ‖ diag(√p)M diag(√q)‖2∗ ≤ α}. By Theorem 6, we have that Rn(Fα) ≤ √ αd2 log(d2) n . It remains to bound the supremum deviation between elements of M∗ and UV> ∈Mα:
max A |〈M∗ − UV>,A〉| = max i,j |〈M∗ − UV>, eie>j 〉|
≤ max i,j |M∗(i, j)|+ max i,j |〈UV>, eie>j 〉|
≤ ‖M∗‖+ max i,j |〈U(i, :),V(j, :)〉|
≤ 1 + max i,j ‖U(i, :)‖‖V(j, :)‖ ≤ 1 + γ
Plugging the above results in Theorem 4, we get L(U,V) ≤ L̂(U,V) + C(1 + γ) √ αd2 log(d2)
n + C ′(1 + γ2)
√ log(2/δ)
2n
which completes the proof.

heading: C DEEP NEURAL NETWORKS
text: Proposition 3 (Dropout regularizer in deep regression).
L̂drop(w) = L̂(w) + R̂(w), where R̂(w) = λ dk−1∑ j=1 ‖Wk(:, j)‖2â2j .
where âj = √ 1 n ∑n i=1 aj,k−1(xi)2 and λ = p 1−p is the regularization parameter.
Proof of Proposition 3. Recall that E[Bii] = 1 and Var(Bii) = p1−p . Conditioned on x, y in the current mini-batch, we have that
EB[‖y−WkBak−1(x)‖2] = dk∑ i=1 EB(yi −Wk(i, :)>Bak−1(x))2. (5)
where aj(x) ∈ Rdj is the activation vector of the j-th hidden layer for input x, i.e. aj(x)[i] = ai,j(x). The following holds by the definition of variance for each of the summands above:
EB(yi −Wk(i, :)>Bak−1(x))2 = ( EB[yi −Wk(i, :)>Bak−1(x)] )2 + Var(yi −Wk(i, :)>Bak−1(x))
Since E[B] = I, the first term on right hand side is equal to (yi−Wk(:, i)>ak−1(x))2. For the second term we have
Var(yi −Wk(i, :)>Bak−1(x)) = Var(Wk(i, :)>Bak−1(x))
= Var( dk−1∑ j=1 Wk(i, j)Bjjaj,k−1(x))
= dk−1∑ j=1 (Wk(i, j)aj,k−1(x))2 Var(Bjj)
= p
1− p dk−1∑ j=1 Wk(i, j)2aj,k−1(x)2
Plugging the above into Equation (5)
EB[‖y−WkBak−1(x)‖2] = ‖y−Wkak−1(x)‖2 + p
1− p dk−1∑ j=1 ‖Wk(:, j)‖2aj,k−1(x)2
Now taking the empirical average with respect to x, y, we get
L̂drop(w) = L̂(w) + p
1− p dk−1∑ j=1 ‖Wk(:, j)‖2â2j = L̂(w) + R̂(w)
which completes the proof.
Proposition 4. Consider a two layer neural network fw(·) with ReLU activation functions in the hidden layer. Furthermore, assume that the marginal input distribution PX (x) is symmetric and isotropic, i.e., PX (x) = PX (−x) and E[xx>] = I. Then the following holds for the expected explicit regularizer due to dropout:
R(w) := E[R̂(w)] = λ
2 d0,d1,d2∑ i0,i1,i2=1 W2(i2, i1)2W1(i1, i0)2, (6)
Proof of Proposition 4. Using Proposition 3, we have that:
R(w) = E[R̂(w)] = λ d1∑ j=1 ‖W2(:, j)‖2E[σ(W1(j, :)>x)2]
It remains to calculate the quantity Ex[σ(W1(j, :)>x)2]. By symmetry assumption, we have that PX (x) = PX (−x). As a result, for any v ∈ Rd0 , we have that P(v>x) = P(−v>x) as well. That is, the random variable zj := W1(j, :)>x is also symmetric about the origin. It is easy to see that Ez[σ(z)2] = 12Ez[z 2].
Ez[σ(z)2] = ∫ ∞ −∞ σ(z)2dµ(z)
= ∫ ∞ 0 σ(z)2dµ(z) = ∫ ∞ 0 z2dµ(z)
= 1
2 ∫ ∞ ∞ z2dµ(z) = 1 2 Ez[z2].
Plugging back the above identity in the expression of R(w), we get that
R(w) = λ d1∑ j=1 ‖W2(:, j)‖2E[(W1(j, :)>x)2] = λ d1∑ j=1 ‖W2(:, j)‖2‖W1(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:
RS(Fα) = Eσ sup fw∈Fα
1
n n∑ i=1 σifw(xi)
= Eσ sup f∈Fα
1
n n∑ i=1 σi dk−1∑ j=1 Wk(1, j)aj,k−1(xi)
= Eσ sup fw∈Fα
1
n dk−1∑ j=1 Wk(1, j)aj n∑ i=1 σi aj,k−1(xi) aj
≤ sup fw∈Fα dk−1∑ j=1 |Wk(1, j)aj | · 1 n Eσ sup fw∈Fα max j∈[dk−1] | n∑ i=1 σi aj,k−1(xi) aj |
The first term on the right hand side is bounded as:
dk−1∑ j=1 |Wk(1, j)aj | ≤ √ dk−1 √√√√dk−1∑ j=1 Wk(1, j)2a2j (Cauchy-Schwartz)
≤ √ dk−1α
We now consider the function class
F̃ := {hw̃ : x 7→ σ(vσ(Wk−2σ(· · ·W2σ(W1x) · · · )), Ex[hw̃(x)2] = 1}
Plugging back the above and noting that aj ≥ 0, we have RS(Fα) ≤ √ dk−1α
n Eσ sup
a2j=1
max j∈[dk−1] | n∑ i=1 σiaj,k−1(xi)|
≤ √ dk−1α
n Eσ sup hw̃∈F̃ | n∑ i=1 σihw̃(xi)|
Let w̃∗ be the maximizer of the right hand side, i.e.
Eσ| n∑ i=1 σihw̃∗(xi)| = sup hw̃∈F̃ | n∑ i=1 σihw̃∗(xi)|
Then, it holds that Rn(Fα) = Ex[RS(Fα)]
≤ √ dk−1α
n Ex,σ| n∑ i=1 σihw̃∗(xi)|
≤ √ dk−1α
n
√√√√ExEσ ( n∑ i=1 σihw̃∗(xi) )2
=
√ dk−1α
n
√√√√ n∑ i=1 Exhw̃∗(xi)2 = √ dk−1α n
which completes the proof of the Lemma. Lemma 3. Assume that ‖Wk‖F ∏k−1 i=1 ‖Wi‖ ≤ √ M , and that supx∈X ‖x‖ ≤ √ B, supy∈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` := ∑dk−1 j=1 ‖Wk(:, j)‖2aj,k−1(x`)2 and observe that
X` = dk−1∑ j=1 ‖Wk(:, j)‖2aj,k−1(x`)2
= dk−1∑ j=1 ‖Wk(:, j)‖2σ (Wk−1(j, :)ak−1(x`))2 ≤ dk−1∑ j=1 ‖Wk(:, j)‖2 (Wk−1(j, :)ak−1(x`))2 ≤ dk−1∑ j=1 ‖Wk(:, j)‖2‖Wk−1(j, :)‖2‖ak−1(x`)‖2
≤ ‖ak−1(x`)‖2 max i ‖Wk−1(i, :)‖2 dk−1∑ j=1 ‖Wk(:, j)‖2
≤ ‖x`‖2‖W1‖2 · · · ‖Wk−1‖2‖Wk‖2F ≤ BM
where the first inequality follows from the definition of ReLU, and the second inequality is due to Cauchy-Schwartz. Thus, Xw,` 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(∣∣∣∣∣ 1n 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 ≥ 4C2B2M2 log(2/δ)/α2. Define the class of deep neural networks with dropout regularizer bounded by √ α, i.e. Fα = {fw : R(w) ≤ α}. By Lemma 1, we have that Rn(Fα) ≤ √ αdk−1 n . It remains to bound the supremum deviation between true labels and those predicted by networks that belong to Fα:
sup x,y∼D, fw∈Fα ‖y− fw(x)‖ ≤ sup x,y∼D ‖y‖+ sup x,y∼D, fw∈Fα ‖fw(x)‖
≤ 1 + sup x,y∼D, fw∈Fα ‖ dk−1∑ j=1 Wk(:, j)aj,k−1(x)‖
≤ 1 + sup x,y∼D, fw∈Fα dk−1∑ j=1 ‖Wk(:, j)aj,k−1(x)‖
≤ 1 + sup x,y∼D, fw∈Fα √√√√dk−1 dk−1∑ j=1 ‖Wk(:, j)‖2aj,k−1(x)2
≤ 1 + √ dk−1α
where the second inequality follows from the assumption supy∈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 get
L(w) ≤ L̂(w) + C(1 + √ αdk−1) √ αd2 n + C ′(1 + √ dk−1α) 2 √ log(2/δ) 2n
holds with probability at least 1− 2δ, which completes the proof.
d1 = 30 d1 = 110 d1 = 150 d1 = 190

heading: D ADDITIONAL EXPERIMENTS
text: 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 d1 = 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 d1 ∈ {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 d1 = 30, the dropout with rates p = 0.3, 0.4 fail to achieve a good test performance, where as for larger factorization sizes (d1 ∈ {110, 150, 190}), they consistently outperform plain SGD as well as other dropout rates.

Review summaries:
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.