Dropout: Explicit Forms and Capacity Control
Authors: Raman Arora
Peter L. Bartlett
Poorya Mianjy
Nathan Srebro
Venue:  (2020)

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 data-dependent 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.

Under review as a conference paper at ICLR 2020
DroPouT: EXPLICIT FORMS AND CAPACITY CON- TROL
Anonymous authors Paper under double-blind review
ABSTRACT
We investigate the capacity control provided by dropout in various machine learn- ing problems. First, we study dropout for matrix sensing, where it induces a data- dependent regularizer that, in expectation, equals the weighted trace-norm of the product of the factors. In deep learning, we show that the data-dependent regular- izer due dropout directly controls the Rademacher complexity of the underly- ing 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-worle datasets, including MovieLens, Fashion MNIST, and CIFAR-10.
INTRODUCTION
Dropout is a popular regularization technique for training deep neural networks that aims at "break- ing 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 classifica- tion (Srivastava et al., 2014; Szegedy et al., 2015) to regression (Toshev & Szegedy, 2014). Notably, is considered as a major component the design of AlexNet (Krizhevsky et al., 2012), which won the prominent ImageNet challenge in 2012 with 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 lo-loss which yields state-of- the-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 offte-of-the-ar 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 data- dependent regularizer that, in expectation, equals weighted trace-norm complexity mea- sure that enjoys strong generalization guarantees (Foygel al., 20.
2. For two-layer neural networks with ReLU activation, when the input distribution is sym- metric and isotropic, we show that dropout induces the & 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 ex- pected value serves strong complexity measure for networks trained with dropout. In

---

Under review as a conference paper at ICLR 2020
particular, show that network with small dropout regularizer enjoys small general- ization 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 set (1,..., d} by id]. For any vector x E R2, (xia E RRddd represents the diagonal matrix with diagonal elements equal to and /x is the elementwise squared root of x. Let ||x|| represent the fg-norm of vector x, and ||X]], [| F. and |||||= represent the spectral norm, the Frobenius norm, and the nuclear norm of matrix X, respectively. Similarly, given positive definite matrix C, we denote the Mahalonobis norm as ||x|2 = x Cx. The standard inner product is represented by (s,'), for vectors matrices, where (X,X') x').
represent the
2 MATRIX SENSING
We begin with understanding dropout for matrix sensing, problem which arguably is an impor- tant 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, E ddd be matrix with rank r, Rank(M.)). Let A ...... A be set of measure- ment 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; = (M,, A such that n < d2dg- A natural approach to solve this problem is enforce the rank constraints implicitly using the Burer-Monteiro factorization and to solve the following empirical risk minimization problem:
min
İ(U, V)
Σ U1 ( (UVT, (0)2
UE X VERdo xdy
12
When d1 r., there exist many "bad" empirical minimizers, i.e., those with large true risk. However, recently, Li et al. (2018) showed that under restricted isometry property, despite the ex- istence 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, mod- em machine learning systems employ explicit regularization techniques. In fact, as we show in the experimental section, the implicut bias due to (stochastic) gradient descent does not prevent from blatant overfitting in the matrix completion problem. We argue that in such cases, there is 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 implicir effect of gradient descent, this dropout heuristic explicitly regularizes the empirical objective. It is then natural ask, in the case of matrix sensing, if dropout also biases the ERM towards certain low norm solutions. To answer this question, we hegin with the observation that dropout can be viewed instance of SGD the following objective:
1 Σ EB - (UBVT, AAD1))
Larop(U (U V)
(2)
where E Rd xdi is a diagonal matrix whose diagonal elements are Bernoulli random variables distributed as B;; I-p Ber(1 p). In this case, it is easy to show that for any p 10;
Edrop (Un V) -[(U.V) P MU, R(U, _
Σ
Σ
u A v))2
2

---

Under review as a conference paper at ICLR 2020
where R(U, V) is 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 reg- ularizer is well concentrated around its mean (see Lemma 2 in the Appendix). Further, given that seek a minima of Ldrop it suffices to consider the factors with the minimal value of the reg- ularizer among all that yield the same empirical loss. This motivates studying the the following purribttiondeppendend induced regularizer:
θ (M) := min R(U, V), where R(U, V) := EA [R v)J.
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 A be standard Gaussian matrices. Then (M) 1
di | is the standard trace-norm regularization studied in Srebro et al. (2005); Bach (2008);
Candès & Tao (2009).
Matrix completion. For all j [n], let A be an indicator matrix whose (i. k)-th element is selected randomly with probability (k)) where p(i) and ((k) denote the probability of choosing the i-th row and the j-th column, respectively. Then
(M) = - d[ddig diag(VQ)))
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 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 2 do and ||M S 1. Furthermore, as- log(d2)
sume that min,,, p(i)q()) 2 av/dzdo" Let (U, V) be a minimizer of the dropout ERM objective
in equation (2), and assume that max; [|U(i,:)) :)] 2 < 7, max; [V(,,))]l < 7. Let be such that R(U, V) S a/d1, Then, for any 8 E (0, 1). the following generalization bounds holds with proba- bility at least 1 - 26 over sample of size n::
od2 log(d2) + c((1+
log (2/8)
v s ((U. $ + C(1 (((+))) V L(U,
n
2n
as long as n Ω ((d1>//a)) log(/))) where C, C' are some absolute constants.
The proof of Theorem follows from standard generalization bounds for Eg loss (Mohri et al., 2018) based on the Rademacher complexity (Bartlett & Mendelson, 2002) of the class of functions with weighted trace-norm bounded by /a, i.e. .M.- == {M || diag( / M diag( /q)11 < a). A bound on the Rademacher complexity of this class was established by Foygel et al. (2011). The technicali- ties 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, specified by the condition min;,; (()) Z logida)
ny/dzdo This is a natural requirement for bounding the Rademacher complexity of Mo. as discussed in Foygel et al. (2011).
We note that for large enough sample size. A(U.V) ~ R(U.V) ~ @(UV 1 di diag(v/)UU' diag( (9)11, 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 1/d,. Hence the assumption R(U, V) S a/d, in the statement of the corollary.
In practice, for models that are trained with dropout, the training error Ī(U, V) is negligible (see Figure for experiments on the Moviel.ens dataset). Moreover, given that the sample size is large
3

---

Under review as a conference paper at ICLR 2020
enough, the third term can be made arbitrarily small. Having said that, the second term, which is D(rv/d2// dominates the right hand side of generalization error bound in Theorem 6.
The assumption max; ||U(i, : < 7, max; [V( < 7 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 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 y also determines the complexity of the function class. On one hand, the generalization gap explicitly depends on and increases with y. However, when y is large, the constraints on U, V are milder, so that LU, V) can be made smaller.
Finally, the required sample size heavily depends on the value of the explicit regularizer at the optima (a/d1), 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 y results in a smaller at 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 C Rd and y S Rd denote the input and output spaces, respectively. Let D denote the joint probability distribution on X' x Y. Given n examples (x),)))) ~ DD drawn i.i.d. from the joint distribution and a loss function É +:V x y + I., the goal of learning is to find a hypothesis fw X + Y) parameterized by w, that has a small population risk L(w)- == ED [x)
We focus on the squared &g loss, i.e., y(y. y' and study the generalization proper- ties of the dropout algorithm for minimizing the empirical risk I(w) := + Σ. IIlly; ff [+.] We consider the hypothesis class associated with feed-forward neural networks with & layers, i.c., functions of the form (x) = Woor(We-10f
-
(Wx))...)) where W, E R4 xd, for i E [K]. is the weight matrix at i-th layer. The parameter is the collection of weight matrices (WA; W W and o IR- + R is an activation function applied entrywise to an input vector.
In modern machine learning systems, rather than talk about certain network topology, we should think in terms of layer topology where each layer could have different characteristies - for exam- plc, 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, deep regression, 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:
Lamop (w) = Σ
Eslly, Wo (W ..1)
(dropout objective)
where diagonal random matrix with diagonal elements distributed identically and indepen- dently as B, T-p Bem((1 p), i E [dk-1], for some dropout rate p. We seek to understand the explicit regularizer due to dropout:
R(w) := Larop (w) [(w)
(explicit regularizer)
We denote the output of the i-th hidden node in the j-th hidden layer on input vector x by (x) E R: for example, 2x. = (W2(1,;) (W([))). Similarly, the vector ay (x) E Rd denotes the activation of the j-th layer on input Using this notation, we can conveniently rewrite the dropout objective as Larop (w) == n. E Ep lyy Ba (xx)]l2, It is then easy to show that the explicit regularizer due to dropout is given as (see Propostion 3 in the Appendix):
R(()= = p de=
1
where ā.
ajja-1 (x;))
1=1
4

---

Under review as a conference paper at ICLR 2020
The explicit regularizer R(w) is the summation over hidden nodes, of the product of the squared norm the outgoing weights with the empirical second moment of the output of the corresponding neuron. For two layer neural network with ReLU, when the input distribution is symmetric and isotropic, the expected regularizer is equal to (see Proposition in the Appendix)
1 do
R(w) B[R(w)]]
Σ
W2(62, 21 do)
which is precisely the squared & path-norm of the network (Neyshabur et al., 2015). We note that such connection has been previously established for deep linear networks Mianjy 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, bound the Rademacher complexity of the function class with bounded expected explicit regularizer, i.e.
=a -.=Uxx+-(0)) Σ (W sa)
Ex is the expected squared neural activation for the j-th hid- where a? := E,
den node. For simplicity, we focus on networks with one output neuron; extension to multi- ple output neurons is rather straightforward. Recall that the Rademacher complexity is sam- ple dependent measure of the capacity of hypothesis class that bounds the generalization gap, i... the difference between the empirical and true risks (Bartlett & Mendelson, 2002). Let
S = [(11,
(Xa, Bn)} be a sample of size The empirical Rademacher complexity of Fa with respect to S, and the expected Rademacher complexity are defined, respectively, as:
1 Σ ox,(),) R.. = E,
Rs(F) Eg sup JEF n
The following lemma gives upper bound the expected Rademacher complexity of Fa, which only depends on a and the width of the top layer d
Lemma 1. For any sample size and any a 0 it holds that (Fa) S de-ja
12
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. particular, as we show in the proof of Lemma 1, the following upper bound holds for any class of neural networks F:
d
dx-1
(F) Vn
1
Σ 1=1
W S
1 Vn
Σ Ws(11,)Paa. J=1
where the second inequality is due to Cauchy-Schwarde In particular, dropout directly controls the summation in the right hand side above. However, note that the second inequality above can in gen- eral be very loose for large width d4-1. specifically if small subset of hidden nodes J [dx-1] co-adapt in a way that for all j E [d J. the other hidden nodes are almost inactive, i.e. Wx(1,) (),j))a O. In this sense, dropout breaks "co-adaptation" between neurons by promoting lutions 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), respec- tively, showed that the minimum of the dropout objective is only achieved by equalized networks, [W&(1, Vj E [dg-1]. For such equalized networks, the second
for which (1. equality above holds with equality, where the value of the explicit regularizer gives 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 net- works trained by dropout.
Theorem 2. Consider deep neural networks with ReLU activation functions. Let w = = be minimizer of the dropout objective. Assume that ||W|]rr I |[all S VM, and that
5

---

Under review as a conference paper at ICLR 2020
supxex ||x|| VB, sup lyl 1. Let R(w) I a.2 be upper bound on the explicit regu-
larizer at w. Then, with probability at least 1 - 26, over a sample size n, we have that
T(w)= S T(w) + C(1 + Voda-1) odk-1
log (2/5)
C²(1 + V di 1a)
2n
as long as ( where C' and C' are absolute constants.
In practice, modern over pacrpaaraeteri deep neural networks are usually trained to zero empirical loss, i.c. if w is a minimizer of the dropout objective, then L(w) is negligible (see, c.g. Figure 2 for the empirical error of convolutional neural networks trained with dropout on Fashion MNIST and CIFAR-101 10). In such settings, we expect the last two terms on the right hand side to be the domi- nant terms this implies that the right hand side above is in the order of O(odk-1 v (2g((/6)/ Interestingly, the upper bound presented in Theorem has no explicit dependence on the network depth, except through the assumption that [[&llle II [|W:ll I vM, 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 (c.g.. see Bartlett et al. (2017); Neyshabur al. (2017) and the references therein). Furthermore, there is no explicit dependence on the widths of the hidden layers, except through Vod=-1- We note that in most state-of sate-oo-thee the--rt models, dx-1 is not large, and as we discussed earlier, dropout implicitly equalizes the network in -1 [Wx(1,j)aj) which does not explicitly depend on the width. Finally,
way that / /adk-11 Žド= 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 linear mapping fw -> W.... W1x. In particular, they showed that if f is a deep linear network with one output neuron, then it holds that
v llf = min A(w),
f=f=
where v is a regularization parameter independent of the parameters w. For linear regression (i.e., for h: = and u = W E TR,,), this result implies that least squares regression using dropout amounts solving the following regularized problem:
x Σ(u (v: LT x;) + vilual
min uc DER n
All the minimizers of the above problem are solutions to the following system of linear equations (1 + v)X Xu = X y. where X = "..,..., ......,,,,
E Raxdo, [V1.... yn, E TRax1 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 Tx+x+ + vl)u xTy y. The spectral augmentation due to Tikhonov regularization is helpful because it results in a well- well-posed problem, even if the the original (v 0) system was under-determined On the contrary, the dropout regularizer manifests itself merely as scaling of the parameters, under which the problem remains ill-posed e.g. if n dg- More impor- tantly, Tikhonov regularization discards the directions that account for small variance in data even when they exhibit good discriminability. which useful prior for learning in general. Dropout, however, does not seem to yield useful inductive bias for lincar 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.

---

Under review as a conference paper at ICLR 2020
Train RMSE
Test RMSE
Generalization
plain SGD
1.0
p-0.10
0.2020
0.3
0.15
0.3
9.00
0.32
0.30
0.9
0.78
0.00
Figure 1: MovieLens dataset: the training error (left), the test error (middle). and the generalization gap (right) for plain SGD and dropout with p {0.1, 0.3, 0.4) function of the number of iterations. The factorization size is di- 70.
plain SGD
dropout
width
last iterate
best iterate
0.1
== 0.2
p 0.3
0.4
d1 30
0.8041
0.7938
0.7805
0.785
0.7991
0.8186
d1 70
0.8315
0.7897
0.7899
0.7771
0.7763
0.7833
d1 110
0.8431
0.7873
0.7988
0.7813
0.7742
0.7743
d1 150
0.8472
0.7858
0,8042
0.7852
0.7756
0.7722
d1 190
0.8473
0.7844
0.8069
0.7879
0.7772
0.772
Table I: 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.
EXPERIMENTAL RESULTS
In this section, we empirically evaluate our theoretical findings several real world datasets'. All results are averaged over independent runs with random initialization. We report experiments for plain SGD well dropout with various dropout rates. For deep neural networks, the activation function is always ReLU.
4.1 MATRIX COMPLETION
In this section, explore the generalization properties of matrix completion with dropout algorithm on the MovieLens dataset Harper & Konstan (2016). MovieLens is a publicly available collabora- tive 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 1r = 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.43.
Figure 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 dN 70. 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 E {30, 110, 150, 190).
It is remarkable, how in the "simple" problem of matrix completion, plain SGD lacks proper inductive bias. As it is clearly depicted in the middle plot, without explicit regularization in particular early stopping dropout in this figure SGD suffers from gross overfitting. We further illustrate this fact in Table 1, where we compare the test -aa-mean--quarrd-emrr (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
To ensure reproducibility of the results, we have uploaded the code.

---

Under review as a conference paper at ICLR 2020
Training
Generalitation ghp
Upper bound Lemma
0430
2181 522
07214
0,303
0.001
0..5
04305
0030
0.24
0.00
0.00
0534
0233
644
3X 18C
1397 JB0 2007 2019 2:00 A0W
307 200 D.
2007 250
302 15 250 20N 200 4007
307 U8 250 28 250 X00 353
Training werter
Test wirrr
Ceneralization
Uppar boundd Lamnnne 1
23
034
0.450
642
0.00
6112
2.540
0.99
143 Who 2he
300 z0a uho
02:6
1
0221
1250 19a
Figure 2: Fashion MNIST (top) and CIFAR-IO (bottom): the training error, the generalization gap, and the Rademacher complexity bound Lemma for plain SGD and dropout with p E {0.25, 0.50, 0.75) as a function of the width of the top hidden layer.
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).
4.2 DEEP NEURAL NETWORKS
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 x 28 grayscale image, associated with 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 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 the top hidden layer chosen from widt width E {25, 2 ... 2 In all experiments, the linear layer weights standard Xavier initialization, and a fixed learning rate ir = 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.
initialized using
For CIFAR-10, 10, we use an AlexNet (Krizhevsky et al., 2012), where the layers are modified accord- ingly 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 E (25, 26, ..... 212). In all the experiments, an initial learning rate 1r = 5 and a mini-batch of size 256 is used to perform the updates. We train the models for 100 epochs over the whole train- ing 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 eтror, training error, the generalization gap, and the Rademacher complexity bound in Lemma 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- wer--paameterized. 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) smaller bound corresponds to a curve with smaller generalization gap.
8

---

Under review as a conference paper at ICLR 2020
5 DISCUSSION
Motivated by the success of dropout in deep learning, propose dropout algorithm for matrix sensing and show that it enjoys strong generalization guarantees as well as competitive test perfor- mance on the MovieLens dataset. We then focus deep regression under the squared loss and show that the regularizer due to dropout serves as strong complexity measure for the underlying class of deep neural networks, using which we give 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 optimiza- tion theoretic aspects of training with dropout. 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 known that deep ReLU networks represent the class piecewise linear functions (Arora et al., 2018). What neural networks with norm-bounded weight matrices, due to dropout.
say about the function class approximated by
REFERENCES
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Representations (ICLR), 2018. htwpttsss///atte
abs www.aasaaa /111/111.... .1191.
Francis R Bach. Consistency of trace norm minimization. Journal of Machine Learning Research, 901m))1019-1048, 2008
Pierre Baldi and Peter Sadowski. Understanding dropout. In Advances in Neural Information Processing Systems (NIPS), pp. 2814-2822, 2013.
Dor Bank and Raja Giryes. On the relationship between dropout and equiangular tight frames. arXiv preprint arXiv:I810.000 180006644, 2018
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normaaizze margin bounds for neural networks. In Advances in Newral Information Processing Systems, pp. 6240-6249, 2017.
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foun-
dations of Computational mathematics, 96))717, 2009.
Emmanuel J Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix com- pletion. arXiv preprint arXiv:0903. 1476, 2009.
Jacopo Cavazza, Benjamin D. Haeffele, Connor Lane, Pietro Morerio, Vittorio Murino, and Rene Vidal. Dropout as a low-rank regularizer for matrix factorization. Int. Conf. on Artificial Intelli- gence and Statistics (AISTATS), 2018.
Rina Foygel, Ohad Shamir, Nati Srebro, and Ruslan R Salakhutdinov. Learning with the weighted trace-norm under arbitrary sampling distributions. In Advances in Neural Information Processing Systems, pp. 2133-2141, 2011.
Yarin Gal and Zoubin Ghahramani. Dropout as bayesian approximation: Representing model uncertainty in deep learning. In Int. Conf. Machine Learning (ICML), 2016.
Wei Gao and Hhi-Hua Zhou. Dropout rademacher complexity of deep neural networks. Science China Information Sciences, 59(7):072104, 2016.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size- Size-independent sample complexity of neural networks. In Conference On Learning Theory, pp. 297-299, 2018.

---

Under review as a conference paper at ICLR 2020
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pp. 6151-6159, 2017.
F Maxwell Harper and Joseph Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis), 5(4):19, 2016.
David P Helmbold and Philip M Long. On the inductive bias of dropout. Journal of Machine Learning Research (JMLR), 16:3403-3454, 2015.
Geoffrey E Hinton, Nitish Srivastava, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdi- nov. Improving neural networks by preventing co-adaptation of feature detectors. arXiv preprint arXiv:1207.0580, 2012.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Alex Krizhevsky, Ily Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Stéphane Lathuilière, Pablo Mesejo, Xavier Alameda-Pineda, and Radu Horaud. A comprehensive analysis of deep regression. IEEE transactions on pattern analysis and machine intelligence, 2019.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over-parameterizee matrix sensing and neural networks with quadratic activations. In Conference On Leurning The- ory, pp. 2-47, 2018.
David McAllester. A pac-bayesian tutorial with dropout bound. arXiv preprint arXiv:1307.2116 2013.
Poorya Mianjy and Raman Arora. On dropout and nuclear norm regularization. In International Conference on Machine Learning, 2019.
Poorya Mianjy, Raman Arora, and Rene Vidal. On the implicit bias of dropout. In International Conference Machine Learning, pp. 3537-3545, 2018.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning- MIT press, 2018.
Wenlong Mou, Yuchen Zhou, Jun Gao, and Liwei Wang. Dropout training, data-dependent reg- ularization, and generalization bounds. In International Conference on Machine Learning, pp- 3642-3650, 2018.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to
spectrally-normmaized margin bounds for neural networks. arXiv preprint arXiv:1707.09564 2017.
Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471-501 2010.
Nathan Srebro and Ruslan R Salakhutdinov. Collaborative filtering in a non-uniform world: Learn- ing with the weighted trace norm. In Advances Neural Information Processing Systems, pp. 2056-2064, 2010.
Nathan Srebro and Adi Shraibman. Rank, trace-norm and max-norm. In International Conference on Computational Learning Theory, pp. 545-560. Springer, 2005.
Nathan Srebro, Jason Rennie, and Tommi S Jaakkola. Maximum-maane margin matrix factorization. In Advances in Neural Information Processing Systems (NIPS), 2005.
10

---

Under review as a conference paper at ICLR 2020
Nitish Srivastava, Geoffrey E Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting, Journal of Machine Learning Research (JMLR), 15(1), 2014.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Du- mitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1-9, 2015.
Alexander Toshev and Christian Szegedy. Deeppose: Human pose estimation via deep neural net- works. In The IEEE Conference Computer Vision and Puttern Recognition (CVPR), June 2014.
Tim Van Erven, Wojciech Kotlowski, and Manfred K Warmuth. Follow the leader with dropout perturbations. In Conference Learning Theory, pp. 949-974, 2014.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge University Press, 2018.
Stefan Wager, Sida Wang, and Percy S Liang. Dropout training as adaptive regularization. In Advances in Neural Information Processing Systems (NIPS), 2013.

---

Under review as a conference paper at ICLR 2020
Supplementary Materials for "Dropout: Explicit Forms and Capacity Control"
A AUXILIARY RESULTS
Theorem 3 (Hoeffding's incquality: Theorem 2.6.2 Vershynin (2018)). Let , be inde- pendent, mean zero, sub-Gaussian random variables. Then, for every t 2 0, we have
2 1X,
Σ
X;
21
S
2e
EF
Theorem 4 (Theorem 10.3 of Mohri al. (2018)). Assume that ||h flo S for all H.
Then, for any 5 >> O, with probability at least 1 over sample {(x,,,e), i E [n]} of size n, the following inequalities holds uniformly for all h E H.
1 Σ (h(x,) f(x:)1 + 4MR (H) + M² TO
log(2/6)
El(h(x) f(x)
2n
Theorem 5 (Theorem 3.3 in Mianjy al. (2018)). For any pair of matrices U E Rd2xd1 V
Rdoxds, there exist a rotation matrix Q E SO(di) such that rotated matrices Ü = UQ, V VQ satisfy || ||||:11== 2, |UV for all i [d1]
Theorem (Theorem 1 Foygel al. (2011)), Assume that p(i)g(5) 2 log(dz) nydddo
for all i i
(do). For any let M. (M Rddxdd || diag( diag(v/) S a) be the class of
linear transformations with weighted trace-norm bounded with va. Then the expected Rademacher complexity of M. is bounded as follows:
(Maa) S0
oodz [ddzlo((d)) log(d2)
72
B MATRIX SENSING
Proposition 1 (Dropout regularizer in matrix sensing). The following holds for any E [0, 1):
di
L. (U. i AR(U,V) where R(U.V) = Σ > (n, p..
(4)
where À - the regularization parameter.
Proof of Proposition I. The following equality follows from the definition of variance:
Eg (UBVT, A(9))= (Enlys (UBVT, A11))) + Var(y, - (UBVT ,A0)))
Recall that for a Bernoulli random variable Bys, we have E = 1 and Var(B,)) = r Thus, the
first term on right hand side is equal to (y: (UVT, A ( For the second term we have
4 (uJ v, Var(B),)
Var(H: (UBVT, AA0)) = Var
B B T A ( (0,,)
Σ 1=1
di
p
( vo)))
1
j=1
12

---

Under review as a conference paper at ICLR 2020
Plugging the above into Equation (5) and averaging samples get
(U, Edtop (U, V)
Eb - (UBVT, ((
17
(y (UVT, )
Σ
U A v2)
P
L(U, V)
P 1-p
R(..
which completes the proof.
Proposition 2. [Induced regularizer] The followings hold true.
1. Matrix completion. For [n]. let A be indicator matrix whose (i, k)-th element is selected randomly with probability (ki) where p(i) and q(k) denote the probability of choosing the i-th row and the k-th column. Then ( ă (p) diag( (1)l.
2. i..d. measurements. For all j E [n], let the elements of A be distributed i.i.d. with zero mean and unit variance. Then (M)) d, M
Proof of Proposition 2. For any pair of factors (U, V) it holds that
d2 Av.)²
R(U, V)
Σ
E(u
d1
d2
do
1=1
d,
d2
|diag( vp)u diag( vvv
(diag(//)u;ll) diag(vV)v.ll)
|dag( (Baag(/D).v diag(vV)ll
1 ||ag (vD) u.v, dill(V/)l.
diag( UV 2
d1
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 b, ||ab |]. ||ab ||a||/b/|- Since the inequalities hold for any U, V, it implies that
(UVV)) 2 T [diag UUV diag(v@)12.
Applying Theorem on (diag( (diag(V/)U,, diag( (V)) there exist rotation matrix such that
1
diag(v/) diag(v/)
||dia((V))UT diag(
d1
13

---

Under review as a conference paper at ICLR 2020
We evaluate the expected dropout regularizer UQ, VQ:
R(UQ, vQ)
diag( vD) |2 diag(v/)
di
d' || diag( (VP)UV diag( V
diiag(VpJUV' (
S @(UVT)
which completes the proof of the first part.
Similarly for the second part, we first show that any pair of factors (U, V). RIU, V) geg | I1::
R(U, V) = Σ Blu Av:)²
d2 de
Σ
j=
Σ Σ
i= 1-1j-= 1
||. lival?
di
1
2
(u./lllval)
d1
di
2
|
11
dj
d
2
2
u.v.
||.
LUV 11
d
di
where the first and the second inequaliteis are due 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 T ||a|||/b]| Now again using Theorem 5 on (U, V), there exist a rotation matrix Q such that [|Uqq l1 = 2, |UV Il.. We evaluate the expected dropout
regularizer at UQ VQ:
d1
R(UQ. VQ
Σ
||q
Σ d
UVV JVV 12 = / - I I )(UVT)
1=1
which completes the proof of the the second part.
Lemma 2. Assume U, V is such that max, [|U :I12 < max, [( < v. Then, with proba- bility at least 1 over a sample of size n, we have that
|R(U, V) - R(U, Ox (2/()
Vn
14

---

Under review as a conference paper at ICLR 2020
Proof of Lemma 2. Define X
E
(u (0 v.)? and observe that
dj
X
Σ
inn V VinAA
dg
Uno 12 V V A
b, 'hd"
di
U
V2
A
(0)
jm
U2 v2
max
yic
max 1
where the third equality follows because for indicator matrix A (0) it holds that A A. (i, * (i',"). Thus, Xw., is sub- Gaussinn (more strongly, bounded) random variable with mean B[Xa] R(U, V) and Sub-Gaussian norm [|eel /2/In(2). Furthermore, EXx-RRUU V) S C' Ch2 for some absolute constants C², C' (Lemma 2.6.8 of Vershynin (2018)). Using
(6 (0) 0 if
Log 2/6
Theorem 3, for = Cd1
we get that:
(( - R(U, v\ 2 21) =IP
_ 1-1
log 2/5
X. - R(U,V) R(U,V))
2 202
2
which completes the proof.
Proof of Theorem I. We use Theorem 4 to give a bound on the generalization gap. From Lemma 2, have with probability least 1 that
1 diag(vP)UV diag( 11 ((UVT) R(U.V) di
(definition of +(-))
R(U, V) C22 (log(200
(Lemma 2)
vn
C2² Vlo((//5
a
$ +
(assumption of the Theorem)
2d1
Vn
a
(whenever n 2
di
Define the class of predictors with weighted trace-nom norm bounded by Vo, i.c. Ma {M adz logida)
diagg M 1 a). By Theorem 6, have that Rr (Fa)
It
mains to bound the supremum deviation between elements of M, and UV M,2 max (M. UVT A) = max (M, - UVT e A
1.3
I max
M. (i,j) + max (UVT e..e.)
i.
M. + max (U(i.:), V(i-)))
< 1 + max
|U(i [U(,:))l <
Plugging the above results in Theorem 4, we get
adg log(dz)
log(2/8)
L(U,V) < i(u, + C(1 + +
+ C²(1 + +
n
2n
which completes the proof.
15

---

Under review as a conference paper at ICLR 2020
C DEEP NEURAL NETWORKS
Proposition 3 (Dropout regularizer in deep regression).
Ledpp( (w) [(w) R(w), where R(w) (w)...)
j=1
where aj / Ei= (,,)=1(x;)² and X T-p is the regularization parameter.
Proof of Proposition 3. Recall that B[Ba] = 1 and Var(B.:) = I Conditioned on x, y in the current mini-batch, we have that
Eallyy (a = de
Bp(u: - T Bax-1(x))
(5)
where (x) E I the activation vector of the j-th hidden layer for input x, i.e. ax(x)(t] = (x)
The following holds by the definition of variance for each of the summands above:
EB (3/s (x( (x))²
(Enlys :....:) Bag 1 (x))) + Var(w: Wx((,:) (x)=
Since [B] the first term right hand side is equal to (ye ()(::)) ax)1 For the second
term we have
Var(y Wa((,;) Bag (x)) = (Bar(((())BBBaa
1
du-1
Var( Wold.))B,,(,x-((3))
j=1
5=
da-1
p
We(i,j)2a,
Plugging the above into Equation (5)
dx-1
En flly - We Wx)) = W + 1-P
W ( ax
Now taking the empirical average with respect to x, y, we get
Datoup (w) - L(w))
[W((,))) I(w) R(w))
which completes the proof.
Proposition Consider a two layer neural network fw(()) with ReLU activation functions in the hidden layer. Furthermore, assume that the marginal input distribution TP Pxx(x) is symmetric and
isotropic, iee. (x(x)= = Px(-x) and E[xx" I. Then the following holds for the expected explicis
regularizer due to dropout:
A da d2
R(w) = [[[(w))]
Σ
(2(22.11)2 (1,,
(6)
2
fg.
Proof of Proposition 4. Using Proposition 3, we have that:
R(w) = -[((() = = Σ |w.ch)))PP
16

---

Under review as a conference paper at ICLR 2020
It remains to calculate the quantity (x(x) = (x(-x). As a result, for any v E R we have that P(v x) = PP(-v x) as well. That is, the random variable 2j = (i.) is also symmetric about the origin. It is easy to that [= [x²)
By symmetry assumption, have that
E.(o(z) = dp2)2
(2))d)(22) = 1o0 dd(x(
0 ddp(() J00 2 [2
Plugging back the above identity in the expression R((w), we get that
R(w)= Σ (WW.
Σ
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:
1 (x))
(sFF E, sup f.eF. ni
de
= E, sup feT
Wx (11,)))a,.--((z)
i=1
de-1
(xxi-
E, sup
Wx(L,j)a,
5.
F.FFa n1
aj
1=1
de-1
0j.k 1 (x;)
< sup f.ef.
Σ
(L,l))a
E. sup max n f.EF, jE|da-1l
aj
1=1
==1
The first term on the right hand side bounded as:
dy
W&(L,j)az1
d
Wi(.,,))aa3
Cauchy-Schwarlte
Sd da
We now consider the function class
F:= (hw x + (W W20 ...)) E, (x)3((x) = 1}
Plugging back the above and noting that 2 0. we have
dd-1aa
Rs(Fa)
E, sup max
Σ xxx))
n
JE(1)E(do-1) t=1
dd 1a
E, sup ha h
Σ (x))
n
Let w. be the maximizer of the right hand side, i.c.
E oeha, (xx) = sup
Σ ogha, (x+)
hoef
17

---

Under review as a conference paper at ICLR 2020
Then, it holds that
RA RA, (Fa) = E, (is (Fa))
dx
12
Ex,al
Jyhi (xi)
11
d2 1
ExEo Σ ochin (xi)
V dk - 1a
7
ddk-1a /
Bxhw. (xi)2 =
T
71
which completes the proof of the Lemma.
Lemma 3. Assume that |W&lle I || S /M, and that supsex ||||| I VB, susyp ly| S 1.
Then with probability at least 1 - over sample of size n, we have that
CBM log(2/8)
R(w) R(w)]
where C is an absolute constant.
Proof of Lemma 3. Define
Xx Σド=1 [W and observe that
d2-1
X1
Σ
Σ (W)
de-1
< Σ [
< 11
da-1
< [x))1(X))]1= max
max
1
/=1
< ||xe| [ [ |
< BM
where the first inequality follows from the definition of ReLU, and the second inequality is due to Cauchy-Schwanl
Thus, Xw.t is a sub-Gaussian (more strongly. bounded) random vari- able with mean [[]]] R(w) and sub-Gaussian norm [eell
BM/ In(2). Furthermore,
||X, - R(w) ll & C' (e < CBM, for some absolute constants C", C' (Lemma 2.6.8 of Ver-
2/5
shynin (2018)). Using Theorem 3, for CBM
we get that:
IP (((()) - R(w)) 21) =P
Σ X. RR(w) > CBM
log n
S 6,
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
CBM /Tog(2/0///
R(w) R((w)
Vn
2
18

---

Under review as a conference paper at ICLR 2020
where the second inequality holds whenever n 2 4C² log(2/6)/a² Define the class of deep
neural networks with dropout regularizer bounded by va, i... Fa = {fw : R(w) S a}. By
Lemma 1, we have that (FF.) true labels and those predicted by networks that belong Fa:
adg-1 It remains to bound the supremum deviation between
sup
Ily [x(x) z
sup ||yl| + xy-D
sup KyyD, IuEFa
(x)(ll
x.yDD, J.CF.
de
$ +1
sup
X,yDD, JoEFa
j=1
de-1 [Wa(t.))a,.8-1((]1
<1+
sup
Σ
X,yDD, JoEF.
j=1
du Σ
11
sup x,yD,, JoEF.
di-1
1 d
where the second inequality follows from the assumption supyey lvl < 1, and third and the forth inequalities are due to the triangle inequality and results in Theorem 4 and using union bound we get
respectively. Plugging the above
ad2
C² + vdk- log(2/0)
I(w)= - [(w) + C(1 + v
2n
holds with probability at least 1 - 25, which completes the proof.
19

---

Under review as a conference paper at ICLR 2020
d1 30
dp 110
d1 150
190
p=0.30
0.9
p=0.40
0.0
0.7
0.5
0.5
1.05
1.15
1.00
3.02
0.35
95
0.95
0.50
0.32
0.45
0.85
6.82
0.60
1.54
302k
120k
310k
176
2006
0.12
0.30
0.30
0.35
0.30
0.25
6.30
0.15
0.20
0.25
0.15
0.20
6.34
0.10
0.00
0:22
0.65
6.38
0.00
130c
1306
1006
Figure 1: MovieLens dataset: the training error (top), the test error (middle), the generalization gap for plain SGD as well as dropout with p (0.25, 0.50, 0.75] as function of the number of iterates, for different factorization sizes dj = 30 (first columm), dj 110 (second column), dj 150 (third column), and dj 190 (forth column).
D ADDITIONAL EXPERIMENTS
In this section, we include additional plots which was not reported in the main paper due to the space limitations. Figure/ the main paper shows comparisons between plain SGD and the dropout algorithm the MovieLens dataset for factorization size of d1 70. The observation that make with regard to those plots is not at all limited to the specific choice of the factorization size. In Figure I here, report similar experiments with factorization sizes di (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 emrr but it has the largest generalization gap. Furthermore, increasing the dropout rate increases the training error but results in a tighter generalization gap.
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 larger value of the dropout rate more helpful. For example, when d, 30, the dropout with rates = 0.3, 0.4 fail to achieve good test performance, where as for larger factorization sizes (d, {110, 150, 190)), they consistently outperform plain SGD well as other dropout rates.
20


Reviews:
[{"review_id": "ryeOFjNadB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors prove bounds on the generalization of models produced using dropout.  They conduct experiments showing that dropout improves over SGD without dropout, and plotting generalization gaps and their bounds.\n\nMuch of the technical leverage exploited in this paper comes from earlier work.  Their acknowledgement of these contributions is somewhat uneven.  For example, results a lot like Proposition 2 can be found in [1].  In their treatment\nof deep networks, because only the last layer is dropped out, dropout is essentially applied to a linear model,\nand Proposition 3 of this paper  follows from (10) of [2], which was pointed out 12 lines below (10) in that paper.  \n\nThe statement of Theorem 1 does not appear to be\nrigorous to me.  For random data, the probability\nthat any minimizer of the dropout ERM objective\nsatisfies their bounds on the lengths of the\nrows of U and V could be less than 1 - 2 delta, in which case in some\ncases where the displayed equation in Theorem 1\nis said to apply, there is no U and V to apply it to.  \n(The parameter gamma is not quantified in the statement \nof that theorem.  It is conceivable to me that if gamma is\nconstrained to be large, possibly relative to d_0, d_1 and d_2,\nthen the statement of the theorem could make sense.)\n\nTheorem 2 has a similar issue.  How is M quantified?  \nHow do we know that a minimizer that satisfies the constraints\non M exists with probability at least 1 - 2 delta?\n\nThe authors' claim that \"changing the learning rate or the batch size does not significantly improve the\nperformance of any of these algorithms\" is a little hard to believe.  My impression is that these choices\naffect the implicit regularization of SGD (along with the initialization).  Some more detail about what\nthey tried would be helpful.  \n\nThere is some interesting new content in the paper, even if, on the whole, it is a bit conceptually and technically\nincremental. \n\n(This review has been edited in light of the response.)\n\n\n[1] Cavazza, Jacopo, et al. \"Dropout as a Low-Rank Regularizer for Matrix Factorization.\" International Conference on Artificial Intelligence and Statistics. 2018.\n\n[2] Wager, Stefan, Sida Wang, and Percy S. Liang. \"Dropout training as adaptive regularization.\" Advances in neural information processing systems. 2013.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rJgHz8Xy9B", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Post Discussion Update: \n\nThe authors vehemently disagree with my critiques about discussion of / attribution to prior work.  They seem to think that the differences from Cavazza et al. [AIStats 2018] would be obvious to \"even someone who has taken a basic course in machine learning.\"  However, both Reviewer #2 and Reviewer #3 mentioned the same issues, saying \"much of the technical leverage exploited in this paper comes from earlier work...results a lot like Proposition 2 can be found in [Cavazza et al.]\" (#2), and \"I am surprised that [Cavazza et al.] is not cited with its due credit in the writing. I hope to see some concrete statement about the difference between the authors' contribution and the existing literature\" (#3).  Since 3 out of 4 reviewers did not recognize a clear distinction, it is fair to say the differences to which the authors refer in their rebuttal should be discussed at length in the paper.  However, the authors have not posted a revised draft or any sample text , leaving me to keep my recommendation at 'reject.'\n\n______________________________________________________________________________________________________________________________________\nSummary:  This paper studies (Bernoulli) Dropout regularization in the context of matrix sensing and neural networks (when dropout is applied to only the last hidden layer).  The paper first focuses on matrix sensing, showing an explicit regularizer with connections to trace norm regularization and proving a generalization bound.  The paper then moves to neural networks, first showing an explicit regularizer in the case of a squared loss and dropout on the last hidden layer only.  When the input distribution is symmetric and isotropic, the explicit regularizer is shown to have connections to path norm regularization.  From this explicit regularizer, the authors then derive an upper bound on the generalization gap (Theorem 2).  Experiments are reported that show (#1) (stochastic) dropout does improve generalization in a matrix completion task and (#2) the theoretical results do predict generalization as tested on MNIST and CIFAR-10.          \n\nPros:  Extending dropout to other tasks and understanding its general method of action is an important problem, thus making the paper well motivated.  Moreover, the approach of deriving explicit regularizers from the stochastic objective is a commendable strategy that could improve the stability and speed of converge.  Furthermore, understanding the generalization properties of neural networks is important, and as dropout seems to be a well-established tool for improving generalization, the paper’s approach is sensible.  \n\nCons:  I find this paper to severely over-claim its contributions---in particular #1 and #3 from the introduction...\n\n(#1) Dropout for matrix completion:  Claimed contribution #1 is incremental as it merely adapts the dropout strategy of Cavazza et al. [AIStats 2018] to matrix sensing.  Cavazza et al. [AIStats 2018]’s procedure “drop[s] columns of the factors” (a quote from their abstract), and this is exactly what is done in this paper: “...a procedure that randomly drops the columns of the factors during training” (p 1).  I find it suspicious that the only time Cavazza et al. [AIStats 2018]’s work is mentioned is in the Introduction’s long list of citations of previous dropout work.  In effect, this equates Cavazza et al. [AIStats 2018]’s work with much less related work (e.g. Bayesian interpretations).  The Cavazza et al. [AIStats 2018] work should surely be cited in the vicinity of Equation 2.  Furthermore, Cavazza et al. also discuss connections to trace norm regularization (Section 4) and should also be included in the paper’s discussion on page 3.  \n\n(#3) Dropout in NNs: The explicit regularizer derived in Prop 3 was previously derived by Wang & Manning [ICML 2013]; see their Section 3.1.  This work is not cited---another significant oversight.  However, the resulting complexity bounds derived from Wang & Manning [ICML 2013]’s explicit regularizer are original, to the best of my knowledge.  \n\nIn general, the paper makes several claims that are at best ungenerous to previous work.  For instance, the Introduction claims “none of these [previous] works adequately address the following basic question: how does dropout control the capacity of deep neural networks?” (p 1).  This is an unsubstantiated claim given that the paper contains no Related Work section, which is needed since there have been dozens of papers written on dropout.  Moreover, this work considers only the case in which dropout is applied to the last hidden layer, not to the full network (which is a valid and sensible restriction).  Yet this essentially reduces the results to a study of dropout in linear models (except perhaps in Prop 4) and therefore I don’t see how one could claim the previous work of Wager et al. [NeurIPS 2013], which also studies dropout for linear models, doesn't address similar questions.  For another example, the paper claims on page 3: “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.”  I agree that the connections are important, but similar connections have already been established by (at least) Cavazza et al. [AIStats 2018], Wang & Manning [ICML 2013], and Wager et al. [NeurIPS 2013].  Such connections are not unique to this paper, as the text implies.  \n\nAs for experiments, the matrix completion results to not validate any of the results in Section 2.  A comparison of training under the stochastic objective vs with the explicit regularizer is never performed (as is done in Cavazza et al. [AIStats 2018]).  Similarly, the generalization bounds are not shown to be useful.  The only thing that is shown is that the stochastic objective (again, which is a minor adaptation from Cavazza et al. [AIStats 2018]) does improve generalization.  \n\nMinor comments:\n\n> ERM is never defined as an initialism for “empirical risk minimization” \n\n> While the assumptions of an isotropic and symmetric input distribution in Prop 4 are unrealistic in general, such conditions would be satisfied by hybrid architectures defined by making the early layers of the network a (isotropic Gaussian) normalizing flow [Nalisnick et al., ICML 2019].\n\nFinal Evaluation:  I find the paper's only original and validated contribution to be using Wang & Manning [ICML 2013]’s explicit regularizer to derive the complexity upper bound in Lemma 1.  Due to the paper's lack of discussion and, at times, mischaracterization of previous work, the text needs to be significantly revised before it can be accepted.  A proper Related Work section must be added to discussion the previous literature on understanding dropout.        \n\n\n\n__References__\n\nNalisnick, Eric, et al. \"Hybrid Models with Deep and Invertible Features.\" International Conference on Machine Learning. 2019.\n\nWang, Sida, and Christopher Manning. \"Fast dropout training.\" International Conference on Machine Learning. 2013.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1lxhcqd9r", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis 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.\nAuthors then give a generalization bound for matrix completion with dropout.\nIn 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.\nAuthors 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.\n\nI recommend rejecting this submission. Following are my concerns:\n\n1. 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.\n\n2. 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.\n\n3. 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.\n\n4. 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:\n\tMcAllester, D.A. (2013). A PAC-Bayesian Tutorial with A Dropout Bound. ArXiv, abs/1307.2118. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BJeqs6mSiH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper is well written, but severely overestimates the core contributions embedded in section 3.\n\nFirstly, the idea of using drop out for matrix sensing seems to be a somewhat trivial extension of the work on dropout for matrix factorization -- http://proceedings.mlr.press/v84/cavazza18a/cavazza18a.pdf.  I am surprised that this work is not cited with its due credit in the writing. I hope to see some concrete statement about the difference between the authors' contribution and the existing literature. It is fine to propose an incremental improvement as long as the original work receives the required credit.\n\nDropout has been an extensive area of theoretical research for the past few years. The overly simplistic statement about the limitation of our understanding of how dropout works are a little disappointing, particularly so when the authors themselves list this literature in the related work section. That dropout training can be perceived as an adaptive regularization is also very well known and researched. These arguments weaken the second and third contribution of the paper. I do understand though that extending the results of deep linear networks to a single hidden layer RELU network is non-trivial. The derivations also suggest so and the authors deserve credit for attempting these derivations.\n\nI am also quite doubtful about the setting of the experiments in section 4.1. That changing the batch-size or learning rate does not significantly influence the eventual performance is very counter-intuitive. \n\nOverall, the paper appeared quite promising in the beginning, but the claims in the introduction are not well supported through the rest of the paper. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors study dropout for matrix sensing and deep learning, and show that dropout induces a data-dependent regularizer in both cases. In both cases, dropout controls quantities that yield generalization bounds. 

Reviewers raised several concerns, and several of these were vehemently rebutted. The rhetoric of the back and forth slid into unfortunate territory, in my opinion, and I'd prefer not to see this sort of thing happen. On the one hand, I can sympathize with the reviewers trying to argue that (un)related work is not related work. On the other hand, it's best to be generous, or you run into this sort of mess.

In the end, even the expert reviewers were unswayed. I suspect the next version of this paper may land more smoothly.

While many of the technical issues are rebutted, one that caught my attention pertained to the empirical work. Reviewer #4 noticed that the empirical evaluations do not meet the sample complexity requirements for the bounds to be valid (nevermind loose). The response suggests this is simply a fact of making the bounds looser, but I suspect it may also change their form in this regime, potentially erasing the empirical findings. I suggest the authors carefully consider whether all assumptions are met, and relay this more carefully to readers.
Decision: Reject