Title: ADAPTIVE DROPOUT WITH RADEMACHER COMPLEX-ITY REGULARIZATION

Abstract: We propose a novel framework to adaptively adjust the dropout rates for the deep neural network based on a Rademacher complexity bound. The state-of-the-art deep learning algorithms impose dropout strategy to prevent feature co-adaptation. However, choosing the dropout rates remains an art of heuristics or relies on empirical grid-search over some hyperparameter space. In this work, we show the network Rademacher complexity is bounded by a function related to the dropout rate vectors and the weight coefficient matrices. Subsequently, we impose this bound as a regularizer and provide a theoretical justified way to trade-off between model complexity and representation power. Therefore, the dropout rates and the empirical loss are unified into the same objective function, which is then optimized using the block coordinate descent algorithm. We discover that the adaptively adjusted dropout rates converge to some interesting distributions that reveal meaningful patterns. Experiments on the task of image and document classification also show our method achieves better performance compared to the state-of-the-art dropout algorithms.

1. INTRODUCTION:

Dropout training (Srivastava et al., 2014) has been proposed to regularize deep neural networks for classification tasks. It has been shown to work well in reducing co-adaptation of neurons-and hence, preventing model overfitting. The idea of dropout is to stochastically set a neuron's output to zero according to Bernoulli random variables. It has been a crucial component in the winning solution to visual object recognition on ImageNet (Krizhevsky et al., 2012) . Ever since, there have been many follow-ups on novel learning algorithms (Goodfellow et al., 2013; Baldi & Sadowski, 2013) , regularization techniques (Wager et al., 2013) , and fast approximations (Wang & Manning, 2013) .

However, the classical dropout model has a few limitations. First, the model requires to specify the retain rates, i.e., the probabilities of keeping a neuron's output, a priori to model training. Subsequently, these retain rates are kept fixed throughout the training process thereafter. It is often not clear how to choose the retain rates in an optimal way. They are usually set via grid-search over hyper-parameter space or simply according to some rule-of-thumb. Another limitation is that all neurons in the same layer share the same retain rate. This exponentially reduces the search space of hyper-parameter optimization. For example, Srivastava et al. (2014) use a fixed retain probability throughout training for all dropout variables in each layer.

In this paper, we propose a novel regularizer based on the Rademacher complexity of a neural network (Shalev-Shwartz & Ben-David, 2014) . Without loss of generality, we use multilayer perceptron with dropout as our example and prove its Rademacher complexity is bounded by a term related to the dropout probabilities. This enables us to explicitly incorporate the model complexity term as a regularizer into the objective function.

This Rademacher complexity bound regularizer provides us a lot of flexibility and advantage in modeling and optimization. First, it combines the model complexity and the loss function in an unified objective. This offers a viable way to trade-off the model complexity and representation power through the regularizer weighting coefficient. Second, since this bound is a function of dropout probabilities, we are able to incorporate them explictly into the computation graph of the optimization procedure. We can then adaptively optimize the objective and adjust the dropout probabilities throughout training in a way similar to ridge regression and the lasso (Hastie et al., 2009) . Third, our proposed regularizer assumes a neuron-wise dropout manner and models different neurons to have different retain rates during the optimization. Our empirical results demonstrate interesting trend on the changes in histograms of dropout probabilities for both hidden and input layers. We also discover that the distribution over retain rates upon model convergence reveals meaningful pattern on the input features.

To the best of our knowledge, this is the first ever effort of using the Rademacher complexity bound to adaptively adjust the dropout probabilities for the neural networks. We organize the rest of the paper as following. Section 2 reviews some past approaches well aligned with our motivation, and highlight some major difference to our proposed approach. We subsequently detail our proposed approach in Section 3. In Section 4, we present our thorough empirical evaluations on the task of image and document classification on several benchmark datasets. Finally, Section 5 concludes this paper and summarizes some possible future research ideas.

2. RELATED WORKS:

There are several prior works well aligned with our motivation and addressing similar problems, but significantly different from our method. For example, the standout network (Ba & Frey, 2013) extends dropout network into a complex network structure, by interleaving a binary belief network with a regular deep neural network. The binary belief network controls the dropout rate for each neuron, backward propagates classification error and adaptively adjust according to training data. Zhuo et al. (2015) realize the dropout training via the concept of Bayesian feature noising during neural network learning. They further extend the model to incorporate either dimension-specific or group-specific noise and propose framework to adaptively learn the dropout rates. Li et al. (2016) sample dropout from a multinomial distribution on neuron basis and establish a risk bound for stochastic optimization. They then propose the evolutional dropout model to adaptively update the sampling probabilities during training time.

In addition to these approaches, one other family of solution is via the concept of regularizer. Wang & Manning (2013) propose fast approximation methods to marginalize the dropout layer and show that the classical dropout can be approximated by a Gaussian distribution. Later, Wager et al. (2013) show that the dropout training on generalized linear models can be viewed as a form of adaptive regularization technique. Gal & Ghahramani (2016) develop a new theoretical framework casting dropout training as approximation to Bayesian inference in deep Gaussian processes. It also provides a theoretical justification and formulates dropout into a special case of Bayesian regularization. In the mean time, Maeda (2014) discusses a Bayesian perspective on dropout focusing on the binary variant, and also demonstrate encourage experimental results. Generalized dropout (Srinivas & Babu, 2016) further unifies the dropout model into a rich family of regularizers and propose a Bayesian approach to update dropout rates.

One popular method along with these works is the variational dropout method (Kingma et al., 2015) , which provides an elegant interpretation of Gaussian dropout as a special case of Bayesian regularization. It also proposes a Bayesian inference method using a local reparameterization technique and translates uncertainty of global parameters into local noise. Hence, it allows inference on the parameterized Bayesian posteriors for dropout rates. This allows us to adaptively tune individual dropout rates on layer, neuron or even weight level in a Bayesian manner. Recently, Molchanov et al. (2017) extend the variational dropout method with a tighter approximation which subsequently produce more sparse dropout rates. However, these models are fundamentally different than our proposed approach. They directly operates on the Gaussian approximation of dropout models rather than the canonical multiplicative dropout model, whereas our proposed method directly bounds the model complexity of classical dropout model.

Meanwhile, the model complexity and the generalization capability of deep neural networks have been well studied in theoretical perspective. Wan et al. (2013) prove the generalization bound for the DropConnect neural networks-a weight-wise variant of dropout model. Later, Gao & Zhou (2016) extend the work and derive a Rademacher complexity bound for deep neural networks with dropout.

Another perspective to the model generalization is the PAC-Bayes bound proposed by McAllester (2013) . The PAC-Bayes method assumes probability measures on the hypothesis space, and gives generalization guarantee over all possible "priors". McAllester (2013) give a PAC-Bayes bound for linear predictors with dropout. In practise, the PAC-Bayes method has the potential to give a even tigher generalization bound. The bound we prove in this paper is based on traditional techniques using Rademacher complexity. It is a first step towards understanding how the dropout method works, and we would like to extend it to the PAC-Bayes paradigm in the future.

These works provide a theoretical guarantee and mathematical justification on the effectiveness of dropout method in general. However, they all assume that all input and hidden layers have the same dropout rates. Thus their bound can not be applied to our algorithm.

3. RADEMACHER COMPLEXITY REGULARIZATION:

We would like to focus on the classification problem and use multilayer perceptron as our example. However, note that the similar idea could be easily extended to general feedforward networks. Let us assume a labeled dataset S = {(x i , y i )|i ∈ {1, 2, . . . , n}, x i ∈ R d , y i ∈ {0, 1} k }, where x i is the feature of the i th sample, y i is the one-hot class label for the i th sample, and k is the number of classes in prediction. Without loss of generality, an L-layer multilayer perceptron with dropout can be modeled as a series of recursive function compositions. Let k l be the number of neurons of the l th layer. In particular, the first layer takes sample features as input, i.e., k 0 = d, and the last layer outputs the prediction, i.e., k L = k.

We denote W l ∈ R k l-1 ×k l as the linear coefficient matrix from the (l -1) th layer to the l th layer, and W l i be the i th column of W l . For dropout, we denote θ l ∈ [0, 1] k l as the vector of retain rates for the l th layer. We also define r l ∈ {0, 1} k l as a binary vector formed by concatenating k l independent Bernoulli dropout random variables, i.e., r l j ∼ Bernoulli(θ l j ). To simplify our notation, we further refer W :l = {W 1 , . . . , W l }, r :l = {r 0 , . . . , r l }, θ :l = {θ 0 , . . . , θ l }, W = W :L , r = r :(L-1) , and θ = θ :(L-1) .

For an input sample feature vector x ∈ R d , the function before the activation of the j th neuron in the l th layer f l j is f l j (x; W :l , r :l ) = t W l tj r l-1 t φ(f l-1 t (x; W :l-1 , r :l-1 )), ∀l ∈ {2, 3, . . . , L} where φ : R → R + is the rectified linear activation function (Nair & Hinton, 2010, ReLU) . In vector form, if we denote as the Hadamard product, we could write the output of the l th layer as

f l (x; W, r) = r l-1 φ(f l-1 (x; W :l-1 , r :l-1 )) W l .

Without loss of generality, we also apply Bernoulli dropout to the input layer parameter θ 0 ∈ R d , i.e., f 1 (x; W, r 0 ) = (r 0 x)W 1 . Note that the output of the neural network f L (x; W, r) ∈ R k is a random vector due to the Bernoulli random variables r. We use the expected value of f L (x; W, r) as the deterministic output

EQUATION

The final predictions are made through a softmax function, and we use the cross-entropy loss as our optimization objective. To simplify our analysis, we follow Wan et al. (2013) and reformulate the cross-entropy loss on top of the softmax into a single logistic function loss(f L (x; W, θ), y) =j y j log e f L j (x;W,θ) j e f L j (x;W,θ) .

3.1. EMPIRICAL RADEMACHER COMPLEXITY:

Definition The empirical Rademacher complexity of function class F with respect to the sample S is

R S (F) = 1 n E {σi} sup f ∈F n i=1 σ i f (s i ))

Define loss • f L as the composition of the logistic loss function loss and the neural function f L returned from the L th (last) layer, i.e., loss • f L = {(x, y) → loss(f L (x; W, θ), y)}.

Theorem 3.1. Let X ∈ R n×d be the sample matrix with the i th row x i ∈ R d , p ≥ 1,

1 p + 1 q = 1.

If the p-norm of every column of W l is bounded by a constant B l , denote W = W | max j W l j p ≤ B l , ∀l ∈ {1, 2, . . . , L} , given θ, the empirical Rademacher complexity of the loss for the dropout neural network defined above is bounded by

R S (loss • f L ) = 1 n E {σi} sup W∈W n i=1 σ i loss(f L (x i ; W, θ), y i ) ≤ k2 L 2 log(2d) n X max Π L l=1 B l θ l-1 1/q 1 ,

where k is the number of classes to predict, θ l is the k l -dimensional vector of Bernoulli parameters for the dropout random variables in the l th layer, σ i s are i.i.d. Rademacher random variables, and • max is the matrix max norm defined as The experiments are evaluated on MNIST dataset with a hidden layer of 128 ReLU units. We apply dropout on the hidden layer only, and keep the retain rates fixed throughout training. We optimize with the empirical loss Loss(S, f L (•; W, θ)), i.e., without any regularizer for 200 epochs with minibatch fo 100. All Rademacher regularizers are computed after every epoch in post-hoc manner, under the settings of p = ∞, q = 1. We plot the samples from last 20 epochs under each settings, with initial learning rate of 0.01, and decay by half every 40 epochs.

A max = max ij |A ij |.

Please refer to the appendix for the proof.

Theorem 3.1 suggests that the empirical Rademacher complexity of the dropout network specified in this paper is related to several terms in a multiplicative way: i: p-norms of the coefficients: max j W l j p . Note that in (Srivastava et al., 2014) , 2 norms of the coefficients are already used as regularizers in the experimental comparison ii: 1-norms of the retain rates θ l iii: sample related metrics: dimension of the sample d, the number of samples n, and maximum entries in the samples X iv: the number of classes in the prediction k

An the extreme case is, if the retain rates θ l for one layer are all zeros, then the upper bound above is tight, since in this case the network is simply doing random guess for predictions. Similarly when the coefficients in one layer are all zeros, the bound is also tight. In both cases the features from the samples are not even used in the prediction due to either zero retain rates or zero coefficients.

3.2. REGULARIZE WITH RADEMACHER COMPLEXITY:

We have shown that the Rademacher complexity of a neural network is bounded by a function of the dropout rates, i.e., Bernoulli parameters θ. This makes it possible to unify the dropout rates and the network coefficients W in one objective. By imposing our upper bound of Rademacher complexity to the loss function as a regularizer, we have

EQUATION

where the variable λ ∈ R + is a weighting coefficient to trade off the training loss and the generalization capability. The empirical loss Loss(S, f L (•; W, θ)) and regularizer function Reg(S, W, θ) are defined as

Loss(S, f L (•; W, θ)) = 1 n (xi,yi)∈S loss(f L (x i ; W, θ), y i ), Reg(S, W, θ) = k2 L log d n X max Π L l=1 θ l-1 1/q 1 max j W l j p ,

where W l j is the j th column of W l and θ l is the retain rate vector for the l th layer. The variable k is the number of classes to predict and X ∈ R n×d is the sample matrix.

In addition to the Rademacher regularizer Reg(S, W, θ), the empirical loss term Loss(S, f L (•; W, θ)) also depends on the dropout Bernoulli parameters θ. Intuitively, when θ becomes smaller, the loss term Loss(S, f L (•; W, θ)) becomes larger, since the model is less capable to fit the training samples (i.e., less representation power), the empirical Rademacher complexity bound becomes smaller (i.e., more generalizable), and vice versa. Figure 1 plots the cross-entropy loss and empirical Rademacher p = ∞, q = 1 regularizer upon model convergence under different settings of retain rates. In the extreme case, when all θ l j become zeros, the model always makes random guess for prediction, leading to a large fitness error Loss(S, f L (•; W, θ)), and the Rademacher complexity R S (loss • f L ) approaches 0.1 The network structures we evaluated includes 1 hidden layer with 1024 units, 2 hidden layers with 800 units each, and 3 hidden layers with 1024 units each. The regularizer weights are set to 1e -3 , 1e -4 and 1e -5 respectively. All neurons are ReLU units. Empirically, we find that optimizing the "deterministic" objective leads to similar improvements on the true "stochastic" objective as in Eqn. (2).

3.3. OPTIMIZE DROPOUT RATES:

We now incorporate the Bernoulli parameters θ into the optimization objective as in Eqn. (2), i.e., the objective is a function of both weight coefficient matrices W and retain rate vectors θ. In particular, the model parameters and the dropout rates are optimized using a block coordinate descent algorithm. We start with an initial setting of W and θ, and optimize W and θ in an alternating fashion.

For the retain rate probability θ, due to the stochastic nature of dropout framework, it is very expensive to compute the exact objective value. For each training instance, we may have to exhaustively enumerate all possible dropout configurations in a combinatorial search space and compute its expectation of all the objective functions. One possbile approximation is to iteratively taking large number of samples from Bernoulli distributions of all layers for any input data and then compute the average objective. Even though, the computational complexity can be exponential as to the number of training data. Therefore, in our case, during the optimization of θ, we use the expected value of the Bernoulli dropout variables to rescale the output from each layer, to approximate the true objective f L (x; W, θ). It significantly speeds up the forward propagation process, as we do not need to iteratively sample the dropout variables for each training example. Essentially, it makes the layer output deterministic and the underlying network operates as if without dropout, which is exactly the same as the approximation used in (Srivastava et al., 2014) during testing time.

Note that using the expected value of Bernoulli dropout random variables to rescale a layer output is an approximation to the true objective f L (x; W, θ). In practice, we find such "deterministic" approximation exhibits similar behavior during model optimization, and hence does not deviate or alter the performance, but significantly improves the running time. Figure 2 shows the true objective in "stochastic" mode and its "deterministic" approximation on the training set during optimization process under different network architectures. Empirically, we observe that the true optimization objective in stochastic mode as in Eqn. ( 2) decreases consistently if we use the expected value of the Bernoulli dropout random variable to approximate the sampling process. We apply our proposed approach with different network architectures, on the task of image and text classification using several public available benchmark datasets. All hidden neurons and convolutional filters are rectified linear units (Nair & Hinton, 2010, ReLU) . We found that our approach achieves superior performance against strong baselines on all datasets. For all datasets, we hold out 20% of the training data as validation set for parameter tuning and model selection. After then, we combine both of these two sets to train the model and report the classification error rate on test set. We optimize categorical cross-entropy loss on predicted class labels with Rademacher regularization. In the context of this paper, we specifically refer the Rademacher regularizer to the case of p = ∞, q = 1 unless stated otherwise. We update the parameters using mini-batch stochastic gradient descent with Nesterov momentum of 0.95 (Sutskever et al., 2013) .

4. EXPERIMENTS:

For Rademacher complexity term, we perform a grid search on the regularization weight λ ∈ {0.05, 0.01, 0.005, 0.001, 1e -4 , 1e -5 }, and update the dropout rates after every I ∈ {1, 5, 10, 50, 100} minibatches. For variational dropout method (Kingma et al., 2015, VARDROP), we examine the both Type-A and Type-B variational dropout with per-layer, per-neuron or per-weight adaptive dropout rate. We found the neuron-wise adaptive regularization on Type-A variational dropout layer often reports the best performance under most cases. We also perform a grid search on the regularization noise parameter in {0.1, 0.01, 0.001, 1e -4 , 1e -5 , 1e -6 }. For sparse variational dropout method (Molchanov et al., 2017, SPARSEVARDROP) , we find the model is much more sensitive to regularization weights, and often gets diverged. We examine different regularization weight in {1e -3 , 1e -4 , 1e -5 }. We follow similar weight adjustment scheme and scale it up by 10 after first {100, 200, 300} epochs, then further scale up by 5 and 2 after same number of epoch.

Scales of Regularization:

In practice, we want to stablize regularization term within some managable variance, so its value does not vary significantly upon difference structure of the underlying neural networks. Hence, we design some heuristics to scale the regularizer to offset the multipler effects raised from network structure. For instance, recall the neural network defined in Section 3, the Rademacher complexity regularizer with p = ∞, q = 1 after scaling is

EQUATION

where W l j is the j th column of the weight coefficient matrix W l and θ l is the retain rate vector for the l th layer. The variable k is the number of classes to predict and X ∈ R n×d is the sample matrix. Similarly, we could rescale the Rademacher complexity regularizers under other settings of p = 2, q = 2. Please refer to the appendix for the scaled Rademacher complexity bound regularizers and detailed derivations.

4.1. MNIST:

MNIST dataset is a collection of 28 × 28 pixel hand-written digit images in grayscale, containing 60K for training and 10K for testing. The task is to classify the images into 10 digit classes from 0 to 9. All images are flattened into 784 dimension vectors, and all pixel values are rescaled to gray scale. We examine several different network structures, including architectures of 1 hiddel layer with 1024 units, 2 hidden layers with 800 neurons each, as well as 3 hidden layers with 1024 units each. 1 compares the performance of our proposed models against other techniques. We use a learning rate of 0.01 and decay it by 0.5 after every {300, 400, 500} epochs. We let all models run sufficiently long with 100K updates. For all models, we also explore different initialization for neuron retaining rates, including {0.8, 1.0} for input layers, {0.5, 0.8, 1.0} for hidden layers. In practice, we find initializing the retaining rates to 0.8 for input layer and 0.5 for hidden layer yields better performance for all models, except for SPARSE-VARDROP model, initializing retaining rate to 1.0 for input layer seems to give better result.

Figure 3 illustrates the changes in retain rates for both input and hidden layers under Rademacher regularization with 1e -4 regularization weight. The network contains one hidden layer of 1024 ReLU units. The retain rates were initialized to 0.8 for input layer and 0.5 for hidden layer. The learning rate is 0.01 and decayed by half after every 200 epochs. We observe the retain rates for all layers are diffused throughout training process, and finally converged towards a bimodal distribution for input layer and a unimodal distribution for hidden layer. We also notice that the retain rates for input layer upon model convergence demonstrate interesting feature pattern of the dataset. For example, the pixels in surrounding margins yield smaller retain rates, and the center pixels often have larger retain rates. This is because the digits in MNIST dataset are often centered in the image, hence all the surrounding pixels are not predictive at all when classifying an instance. This demonstrates that our proposed method is able to dynamically determine if an input signal is informational or not, and subsequently gives higher retain rate if it is, otherwise reduce the retain rate over time.

4.2. CIFAR:

CIFAR10 and CIFAR100 datasets are collections of 50K training and 10K testing RGB images from 10 and 100 different image categories. Every instance consists of 32 × 32 RGB pixels. We preprocess all images by subtracting the per-pixel mean computed over all training set, then with ZCA whitening as suggested in Srivastava et al. (2014) . No data augmentation is used. The neural network architecture we evaluate on uses three convolutional layers, each of which followed by a max-pooling layer. The convolutional layers have 96, 128, and 256 filters respectively. Each convolutional layer has a 5×5 receptive field applied with a stride of 1 pixel, and each max-pooling layer pools from 3×3 pixel region with strides of 2 pixels. These convolutional layers are followed by two fully-connected layer having 2048 hidden units each. Table 2 summarizes the performance of our proposed models against other baselines. We initialize dropout rates settings with {0.9, 1.0} for input layers, {0.75, 1.0} for convolutional layers and {0.5, 1.0} for fully-connected layers. Similary to the MNIST evaluation, we find setting the corresponding retaining probabilities for input layers, convolutional layers and fullyconnected layers to 0.9, 0.75 and 0.5 respectively yields best performance under all models. We initialize the learning rate to 0.001 and decay it exponentially every {200, 300, 400} epochs.

Model:

Figure 4 illustrates the changes in retain rates for both input and hidden layers under Rademacher regularization with 0.1 regularization weight. The network contains two convolution layers with 32 and 64 convolutional filters followed by one fully-connected layer with 1024 neurons. All hidden units use ReLU activation functions. The retain rates were initialized to 0.9 for input layer, 0.75 for convolutional layer and 0.5 for fully-connected layer. The learning rate is 0.001 and exponentially decayed by half after every 300 epochs. Similar to MNIST dataset, we observe the retain rates for all layers are diffused throughout training process, and finally converged towards a unimodal distribution. However, unlike MNIST dataset, we do not see similar pattern for retain rates of input layer. This is mainly due to the nature of dataset, such that CIFAR10 images spread over the entire range, hence all pixels are potentially informational to the classification process. This again demonstrates that the Rademacher regularizer is able to distinguish the informational pixels and retain them during training.

4.3. TEXT CLASSIFICATION:

In addition, we also compare our proposed approach on text classification datasets-SUBJ and IMDB. SUBJ is a dataset containing 10K subjective and objective sentences (Pang & Lee, 2004 ) with nearly 14.5K vocabulary after stemming. All subjective comments come from movie reviews expressing writer's opinion, whereas objective sentences are from movie plots expressing purely facts. We randomly sample 20% from the collections as test data, and use other 80% for training and validation. IMDB is a collection of movie reviews from IMDB website, with 25K for training and another 25K for test (Maas et al., 2011) , containing more than 50K vocabulary after stemming. It contains an even number of positive (i.e., with a review score of 7 or more out of a scale of 10) and negative (i.e., with a review score of 4 or less out of 10) reviews. The dataset has a good movie diversity coverage with less than 30 reviews per movie. For each sentence or document in these datasets, we normalize it into a vector of probability distribution over all vocabulary.

Table 3 summarizes the performance of our proposed models against other baselines. We initialize dropout rates settings with {0.8, 1.0} for input layers and {0.5, 1.0} for fully-connected layers. Similarly, by setting the corresponding retaining probabilities for input layers and fully-connected layers to 0.8 and 0.5 respectively, the model often yields the best performance. We use a constant learning rate of 0.001, as well as an initialization learning rate of 0.01 and decay it by half every {200, 300, 400} epochs. We notice that overall the improvement of dropout is not as significant as MNIST or CIFAR datasets. Figure 5 illustrates the changes in retain rates for both input and hidden layers under Rademacher regularization with 0.005 regularization weight on IMDB dataset. The network contains one hidden layer of 1024 ReLU units. The retain rates were initialized to 0.8 for input layer and 0.5 for hidden layer. The learning rate is 0.01 and decayed by half after every 200 epochs. Similar to other datasets, we observe the retain rates for all layers are diffused slightly upon model convergence, and in particularly the retain rates for input layer demonstrate interesting feature patterns of the data.

Recall that the task for IMDB dataset is to classify movie reviews into negative or positive labels. Generically speaking, adjectives are more expressive than nouns or verbs in this scenario, and our findings seems to be consistent with this intuition, i.e., yield high retain rates. List of the most indicative features include "wonder(ful)", "best", "love", "trash", "great", "classic", "recommend", "terribl(e)", "perfect", "uniqu(e)", ""fail", "amaz(ing)", "fine", "supris(e)", "worst", "silli(y)", "flawless", "wast(e)", "dull" and "ridicul(ous)". As discussed above, nouns or verbs are more often used to describe the movie plot, hence are less indicative, i.e., with smaller retain rates. Some of the word features with low retaining probability-hence, possibly less indicative-include "year", "young", "possibl(e)", "happen", "dead", "music", "flick", "shot", "oscar", "kill", "spent", "pretti(y)", "say", "review", "support", "anim(ation)", "actual", "call", "cut", and "role". One interesting observation is that we find the word "oscar" is also in the list of less informative features, which implies movie reviews and Academy Awards are not necessarily correlated.

In addition, we also include a list of popular and possibly unique named entities that are relevant to movie industry, including "baldwin", "niro", "spacey", "depp", "downey", "pitt", "pacino", "marilyn", "hepburn", "craig", "dench", "sammo", "clooney", "kidman", "mccarthi", "kermit", "godzilla", "nimoy", "shawshank", "yokai", "emraan", "kurosawa", "spielberg", "cameron", "pacino", "jackson", "eastwood", "allen", and "verhoeven". We also notice interesting pattern on this list. For example, some actors (e.g., "baldwin" and "kidman", etc.) and directors (e.g., "kurosawa" and "eastwood" etc.), yield high retain rates shortly after initial optimization. The retain rates of actors like "downey" or "spacey", and directors like "spielberg" or "cameron" slightly increase or remain similar over time . The word "pitt",2 however, yields a declined retain rates throughout training, which suggests a less indicative feature for review classification. Note that higher retain rate means the corresponding features are more indicative in classifying IMDB reviews into positive or negative labels, i.e., no explicit association with the label itself.

5. CONCLUSION:

Imposing regularizaiton for a better model generalization is not a new topic. However we tackle the problem for the dropout neural network regularization in a different way. The theoretical upper bound we proved on the Rademacher complexity facilitates us to directly incorporate the dropout rates into the objective function. In this way the dropout rate can be optimized by block coordinate descent procedure with one consistent objective. Our empirical evaluation demonstrates promising results and interesting patterns on adapted retain rates.

In the future, we would like to investigate the sparsity property of the learnt retain rates to encourage a sparse representation of the data and the neural network structure (Wen et al., 2016) , similar to the sparse Bayesian models and relevance vector machine (Tipping, 2001) . We would also like to explore the applications of deep network compression (Han et al., 2015a; Iandola et al., 2016; Ullrich et al., 2017; Molchanov et al., 2017; Louizos et al., 2017) . In addition, one other possible research direction is to dynamically adjust the architecture of the deep neural networks (Srinivas & Babu, 2015; Han et al., 2015b; Guo et al., 2016) , and hence reduce the model complexity via dropout rates. Rademacher regularization on IMDB dataset. Features include words associated with the 20 largest and smallest retain rates, as well as a collection of movie related entities, e.g., actor, director, etc. From our model, words like "love", "great", "terribl(e)", "perfect", "uniqu(e)", "fine(st)", "supris(e)", and "silli(y)" yield large retain rates and hence are indicative feature for predication (in the top half). On the other hand, words like "say", "pretti(y)", "young", "review", "role", "anim(ation)" and "actual" have near zero retain rates upon model convergence, which are less informative. For named entities that are relevant to movie industry, we also observe some interesting pattern. Some actors (e.g., "baldwin" and "kidman", etc.) and directors (e.g., "kurosawa" and "eastwood" etc.), yield high retain rates shortly after initialization. The retain rates of actors like "downey" or "spacey", and directors like "spielberg" or "cameron" slightly increase or remain similar throughout optimization. Note that higher retain rate means the corresponding features are more indicative in classifying IMDB reviews into positive or negative labels, i.e., no explicit association with the label itself.

of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine

6. APPENDIX:

6.1 PROOF OF THEOREM 3.1

Proof. In the analysis of Rademacher complexity, we treat the functions fed into the neurons of the l th layer as one function class F l = f l (x; w :l ). Here again we are using the notation w :l = {w 1 , . . . , w l }, and w = w :L . As a consequence ∀j, f l j (x; w l ) ∈ F l .

Note here f L (x; W ) used in section 3 is a vector, but f L (x; w) used in this subsection is a scalar. The connection between f L (x; W ) and f L (x; w) is that each dimension of f L (x; W ) is viewed as one instance coming from the same function classs f L (x; w). Similar ways of proof have been adopted in Wan et al. (2013) .

To simplify our analysis, we follow Wan et al. (2013) and reformulate the cross-entropy loss on top of the softmax into a single logistic function loss(f L (x; W), y) =j y j log e f L j (x;W)

j e f L j (x;W) .

The function class fed into the neurons of the l th layer f l (x; w :l ) admits a recursive expression

f l (x; w :l , r :(l-1) ) = k φ(f l-1 k (x; w :l-1 , r :l-2 ))r l-1 k w l k (4)

f l (x; w :l ; θ :(l-1) ) = E r :(l-1) f l (x; w :l , r :(l-1) )

(5)

Given the neural network function (1) and the logistic loss function l is 1 Lipschitz, by Contraction lemma (a variant of the lemma 26.9 on page 381, Chapter 26 of (Shalev-Shwartz & Ben-David, 2014) ), the empirical Rademacher complexity of the loss function is bounded by

R S (l • f L ) = 1 n E σ max w i σ i l(f L (x i ; w), y i ) ≤ k n E σ max w i σ i f L (x i ; w) = kR S (f L ) (6)

Published as a conference paper at ICLR 2018 Note the empirical Rademacher complexity of the function class of the L th layer, i.e., the last output layer, is

EQUATION

To prove the bound in a recursive way, let's also define a variant of the Rademacher complexity with absolute value inside the supremum:

EQUATION

Note here RS (f ) is not exactly the same as the Rademacher complexity defined before in this paper.

And we have

EQUATION

Now we start the recursive proof. The empirical Rademacher complexity (with absolute value inside supremum) of the function class of the l th layer is

EQUATION

Let

EQUATION

By the calculous of Rademacher complexity,

EQUATION

Now we have

EQUATION

Let g l-1 j (x; w :l-1 , θ :(l-2) ) = φ f l-1 j (x i ; w :l-1 , r :l-2 ) , then

EQUATION

According to the assumption, p ≥ 1, q = p/(p -1), and w l p ≤ B l , from equation ( 14), by Holder's inequality, we have ∀l ∈ {2, . . . , L}

EQUATION

In the last inequality above we used Jensen's inequality since q ≥ 1 as well as the fact that the dropout random variable r j is binary (so r q j = r j ). Suppose the activation function φ(•) used in the neural network is 1-Lipschitz, and φ(0) = 0 (for example, the RELU function). Then by the Ledoux-Talagrand contraction lemma, ∀l ∈ {1, . . . , L -1}, given r, RS (g l-1 (x; w :l , r :l-1 )) ≤ 2 RS (f l-1 (x; w :l-1 , r :l-2 )).

From equation ( 16) and ( 15) we have

EQUATION

For the first layer, i.e., the feature layer with dropout but without activation function, if

EQUATION

By Lemma 26.11 on page 383, Chapter 26.2 of Shalev-Shwartz & Ben-David (2014), we know the last term in ( 18) is bounded by

1 n E {σi} n i=1 σ i x i ∞ ≤ max i x i ∞ 2 log(2d)/n.

Thus we get

EQUATION

Combining the inequalities ( 6), ( 9), ( 15), ( 16), and (19), we have

EQUATION

6.2. GENERALIZATION BOUND ON THE DROPOUT NEURAL NETWORKS:

Here we need to define truncated cross entropy loss function:

EQUATION

where C l is a constant. Note with the truncation, the cross entropy loss is still 1-Lipschitz so the empirical Rademacher complexity bound still holds for the truncated loss l(f L (x; W, θ), y).

Theorem 6.1. For the dropout neural network defined in section (3), if truncated cross entropy loss l (21) is used, then ∀δ ≥ 0, with probability at least 1 -2δ, ∀ l • f L : E (x,y)∼D ( l(f L (x; W, θ), y) ≤

1 n i l(f L (x i ; W, θ), y i ) + R S ( l • f L ) + 3C l 1/(2nδ) (22)

Note here the empirical Rademacher complexity for the bounded loss function R S ( l • f L ) admits the same bound as the empirical Rademacher complexity for the unbounded cross entropy loss R S (l • f L ).

6.3. TOWARDS AN UNIFIED VIEW OVER RADEMACHER REGULARIZATION:

In fact, adding a Rademacher related regularizer, though not investigated much, is not new at least for linear functions.

It is well known (Shalev-Shwartz & Ben-David, 2014 ) that the empirical Rademacher complexity of the linear class

H 2 = {x → w, x : w 2 ≤ B 2 } is bounded by R S ≤ max i x i 2 B 2 / √ n.

Note the l 2 loss function is 2-Lipschtz. In this way, we may interpret the regularizer in the ridge regression related an upper bound for the empirical Rademacher complexity of the linear function class.

Similarly for the linear class

H 1 = {x → w, x : w 1 ≤ B 1 },

the empirical Rademacher complexity is bounded by

R S ≤ max i x i ∞ B 1 2 log(2d) n .

So the lasso problem can also be viewed as adding a Rademacher-related regularization to the empirical loss minimization objective.

6.4. SCALES OF REGULARIZATION:

In application we do not want the regularization term to vary too much when the neural network has different number of internal neurons. To overcome that we design some heuristics to add to the regularizer. Note here all the scales mentioned in this section are added in a heuristic fashion. It is purely empirical.

When p = q = 2, the regularizer is bounded by

EQUATION

)

Note that the content in Section 6.3 and 6.4 is based purely on heuristics, and derived on an ad hoc basis.

where W l j ∈ R k l-1 is the j-th column of W l . Suppose we use i.i.d. uniform random variable to initialize W l such that ∀l w l ij ∼ U [-6/(k l + k l+1 ), 6/(k l + k l+1 )]. Considering the scales of the maximum among the 2-norms of W l j , we use a scaled regularizer instead:

k2 L log d n max i x i ∞   Π L l=1 max j W l j 2 θ l-1 1/2 1 k l k l + k l-1 log k l   .

Similarly, when p = ∞ and q = 1, the scaled regularizer we used is

k2 L log d n max i x i ∞ Π L l=1 W l max θ l-1 1 √ k l + k l-1 k l .

6.5. STABILITY OF THE DROPOUT RATES CONVERGENCE:

In this sub-section we demonstrate the dropout rates convergence acrross multiple runs. We use a neural network with one hidden layer of 1024 ReLU units to illustrate, and feed it with MNIST dataset. We train the network for 10 different runs, with same configurations and empirical settings, except different initializations on the network weight coefficients. Figure 6 shows the histogram of hidden layer retain rates upon model convergence under different runs. We observe similar dropout behavior and distribution among multiple runs upon model convergence, i.e., the histograms of the retain rates do not diverge much across different runs in regards to different model weight initializations. 

:

To balance out the regularizer and the loss function so that they scale similarly as the sample size and internal layer nodes grow, we add some scaling factors to λ, which is discussed in Section 4.

Note that the word "pitt" is not necessarily associated with the actor, but also short for Pittsburg.

Figures and Tables:

Figure1: Empirical cross-entropy loss (left) and Rademacher regularizer (right) as a function of retain rates. We observe that the empirical loss and Rademacher regularizer change roughly in a monotonic way as a function of retain rates on training data. The experiments are evaluated on MNIST dataset with a hidden layer of 128 ReLU units. We apply dropout on the hidden layer only, and keep the retain rates fixed throughout training. We optimize with the empirical loss Loss(S, f L (•; W, θ)), i.e., without any regularizer for 200 epochs with minibatch fo 100. All Rademacher regularizers are computed after every epoch in post-hoc manner, under the settings of p = ∞, q = 1. We plot the samples from last 20 epochs under each settings, with initial learning rate of 0.01, and decay by half every 40 epochs.

Figure2: Changes in the true objectives in "stochastic" mode and their "deterministic" approximations against training epochs under different network architectures. The optimization objectives are reported on the training set of MNIST dataset, with Rademacher regularizer. We use minibatch size of 100, initial learning rate of 0.01, and decay it by half every 200 epochs. The network structures we evaluated includes 1 hidden layer with 1024 units, 2 hidden layers with 800 units each, and 3 hidden layers with 1024 units each. The regularizer weights are set to 1e -3 , 1e -4 and 1e -5 respectively. All neurons are ReLU units. Empirically, we find that optimizing the "deterministic" objective leads to similar improvements on the true "stochastic" objective as in Eqn. (2).

Figure 3: Changes in retain rates with Rademacher regularization on MNIST dataset. Top-Left: changes in retain rate histograms for input layer (784 gray scale pixels) through training. The retain rates get diffused over time, and only a handful of pixels have retain rates close to 1. Top-Right: changes in retain rate histograms for hidden layer (1024 ReLU units) through training process.Bottom-Left: sample images from MNIST dataset. Bottom-Right: retain rates for corresponding input pixels upon model convergence. The surrounding pixels of input image yield smaller retain rates (corresponds to the dark background area), and the center ones have significantly larger retain rates (corresponds to the number pixels).

Figure 4: Changes in retain rates with Rademacher regularization on CIFAR10 dataset. Top-Left: changes in retain rate histograms for input layer (32 × 32 × 3 RGB pixels) through training. Top-Middle: changes in retain rate histograms for first convolutional layer (32 × 15 × 15 units) through training process. Top-Right: changes in retain rate histograms for second convolutional layer (64 × 7 × 7 units) through training process. Bottom-Left: changes in retain rate histograms for fullyconnected layer (1024 ReLU units) through training process. Bottom-Middle: sample images from CIFAR10 dataset. Bottom-Right: retain rates for corresponding input pixels in both superposition and individual RGB channels upon model convergence. Unlike MNIST datasets, there is no clear pattern from the retain rates out of these channel pixels, since they are all informational towards prediction.

Figure5: Changes in retain rates for different word features upon model convergence with Rademacher regularization on IMDB dataset. Features include words associated with the 20 largest and smallest retain rates, as well as a collection of movie related entities, e.g., actor, director, etc. From our model, words like "love", "great", "terribl(e)", "perfect", "uniqu(e)", "fine(st)", "supris(e)", and "silli(y)" yield large retain rates and hence are indicative feature for predication (in the top half). On the other hand, words like "say", "pretti(y)", "young", "review", "role", "anim(ation)" and "actual" have near zero retain rates upon model convergence, which are less informative. For named entities that are relevant to movie industry, we also observe some interesting pattern. Some actors (e.g., "baldwin" and "kidman", etc.) and directors (e.g., "kurosawa" and "eastwood" etc.), yield high retain rates shortly after initialization. The retain rates of actors like "downey" or "spacey", and directors like "spielberg" or "cameron" slightly increase or remain similar throughout optimization. Note that higher retain rate means the corresponding features are more indicative in classifying IMDB reviews into positive or negative labels, i.e., no explicit association with the label itself.

Figure6: Histograms of the hidden layer dropout retain rates upon model convergence on 10 different runs under different Rademacher p = ∞, q = 1 regularization settings. The neural network contains one hidden layer of 1024 ReLU units, and is trained on MNIST dataset with different regularizer weight of 1e -3 (Left) and 1e -4 (Right). We train the neural network for 200 epochs, with a minibatch size of 100, initial learning rate of 0.01, and decay it by half every 40 epochs. The experiments are run with same configurations and experimental settings, except different initializations on the network weight coefficients.

Classification error on MNIST dataset.

Table content: <table><tr><td>Model</td><td colspan="3">1024 800 × 2 1024 × 3</td></tr><tr><td colspan="2">Multilayer Perceptron 1.69</td><td>1.62</td><td>1.61</td></tr><tr><td>+ Dropout</td><td>1.22</td><td>1.28</td><td>1.25</td></tr><tr><td>+ VARDROP</td><td>1.20</td><td>1.16</td><td>1.07</td></tr><tr><td colspan="2">+ SPARSEVARDROP 1.34</td><td>1.30</td><td>1.27</td></tr><tr><td>+ Rademacher</td><td>1.11</td><td>1.08</td><td>0.95</td></tr></table>

Classification error on CIFAR datasets.

Table content: <table><tr><td/><td>CIFAR10</td><td>CIFAR100</td></tr><tr><td>Convolutional neural network</td><td>18.01</td><td>50.28</td></tr><tr><td>+ Dropout in fully-connected</td><td>17.05</td><td>45.81</td></tr><tr><td>+ VARDROP</td><td>16.85</td><td>45.47</td></tr><tr><td>+ SPARSEVARDROP</td><td>17.87</td><td>45.74</td></tr><tr><td>+ Rademacher</td><td>16.89</td><td>45.35</td></tr><tr><td>+ Dropout in all layers</td><td>15.16</td><td>41.00</td></tr><tr><td>+ VARDROP</td><td>15.03</td><td>39.15</td></tr><tr><td>+ SPARSEVARDROP</td><td>15.87</td><td>42.67</td></tr><tr><td>+ Rademacher</td><td>13.81</td><td>38.63</td></tr></table>

Classification error on text dataset.

Table content: <table><tr><td/><td>SUBJ IMDB</td></tr><tr><td colspan="2">Multi-layer Perceptron 11.50 12.18</td></tr><tr><td>+ Dropout</td><td>10.95 12.02</td></tr><tr><td>+ VARDROP</td><td>10.45 11.82</td></tr><tr><td>+ SPARSEVARDROP</td><td>10.35 11.97</td></tr><tr><td>+ Rademacher</td><td>10.15 11.83</td></tr></table>

Peer review (iclr2018):
 An important contribution. The paper is well written. Some questions that needs to be better answered are listed here. 1. The theorem is difficult to decipher. Some remarks needs to be included explaining the terms on the right and what they mean with respect to learnability or complexity. 2. How does the regularization term in eq (2) relate to the existing (currently used) norm based regularizers in deep network learning? It may be straight forward but some small simulation/plots explaining this is important. 3. Apart from the accuracy results, the change in computational time for working with eq (2), rather than using existing state-of-the-art deep network optimization needs to be reported? How does this change vary with respect to dataset and network size (beyond the description of scaled regularization in section 4)? 4. Confidence intervals needs to be computed for the retain-rates (reported as a function of epoch). This is critical both to evaluate the stability of regularizers as well as whether the bound from theorem is strong. 5. Did the evaluations show some patterns on the retain rates across different layers? It seems from Figure 3,4 that retain rates in lower layers are more closer to 1 and they decrease to 0.5 as depth increases. Is this a general pattern? 6. It has been long known that dropout relates to non-negative weighted averaging of partially learned neural networks and dropout rate of 0.5 provides best dymanics. The evaluations say that clearly 0.5 for all units/layers us not correct. What does this mean in terms of network architecture? Is it that some layers are easy to average (nothing is learned there, so dropped networks have small variance), while some other layers are sensitive? 7. What are some simple guidelines for choosing the values of p and q? Again it appears p=q=2 is the best, but need confidence intervals here to say anything substantial.