arXiv:1602.04484v5 [cs.LG] 19 Apr 2017

Surprising properties of dropout
in deep networks
David P. Helmbold
Department of Computer Science
University of California, Santa Cruz
Santa Cruz, CA 95064, USA
dph@soe.ucsc.edu

Philip M. Long
Google
plong@google.com

April 21, 2017
Abstract
We analyze dropout in deep networks with rectified linear units and the quadratic loss. Our results
expose surprising differences between the behavior of dropout and more traditional regularizers like weight
decay. For example, on some simple data sets dropout training produces negative weights even though the
output is the sum of the inputs. This provides a counterpoint to the suggestion that dropout discourages
co-adaptation of weights. We also show that the dropout penalty can grow exponentially in the depth of
the network while the weight-decay penalty remains essentially linear, and that dropout is insensitive to
various re-scalings of the input features, outputs, and network weights. This last insensitivity implies that
there are no isolated local minima of the dropout training criterion. Our work uncovers new properties
of dropout, extends our understanding of why dropout succeeds, and lays the foundation for further
progress.

1

Introduction

The 2012 ImageNet Large Scale Visual Recognition challenge was won by the University of Toronto team by
a surprisingly large margin. In an invited talk at NIPS, Hinton [15] credited the dropout training technique
for much of their success. Dropout training is a variant of stochastic gradient descent (SGD) where, as each
example is processed, the network is temporarily perturbed by randomly “dropping out” nodes of the network.
The gradient calculation and weight updates are performed on the reduced network, and the dropped out
nodes are then restored before the next SGD iteration. Since the ImageNet competition, dropout has been
successfully applied to a variety of domains [8, 10, 9, 17, 7], and is widely used [21, 13, 23]; for example, it
is incorporated into popular packages such at Torch [25], Caffe [6] and TensorFlow [24]. It is intriguing that
crippling the network during training often leads to such dramatically improved results, and dropout has
also sparked substantial research on related methods (e.g. [12, 29]).
In this work, we examine the effect of dropout on the inductive bias of the learning algorithm. A match
between dropout’s inductive bias and some important applications could explain the success of dropout, and
its popularity also motivates the study of its unusual properties.
Weight decay training optimizes the empirical error plus an L2 regularization term, λ2 ||w||22 , so we call
λ
2
2 ||w||2 the L2 penalty of w since it is the difference between training criterion evaluated at w and the
empirical loss of w. By analogy, we define the dropout penalty of w to be the difference between the dropout
training criterion and the empirical loss of w (see Section 2). Dropout penalties measure how much dropout
discriminates against weight vectors, so they are key to understanding dropout’s inductive bias.
Even in one-layer networks, conclusions drawn from (typically quadratic) approximations of the dropout
penalty can be misleading [14]. Therefore we focus on exact formal analysis of dropout in multi-layer
1

networks. Theoretical analysis of deep networks is notoriously difficult, so we might expect that a thorough
understanding of dropout in deep networks must be achieved in stages. In this paper we further the process
by exposing some of the surprising ways that the inductive bias of dropout differs from L2 and other standard
regularizers. These include the following:
• We show that dropout training can lead to negative weights even when the output is a positive multiple
of the the inputs. Arguably, such use of negative weights constitutes co-adaptation – this adds a
counterpoint to previous analyses showing that dropout discourages co-adaptation [22, 14].
• Unlike weight decay and other p-norm regularizers, dropout training is insensitive to the rescaling of
input features, and largely insensitive to rescaling of the outputs; this may play a role in dropout’s
practical success. Dropout is also unaffected if the weights in one layer are scaled up by a constant
c, and the weights of another layer are scaled down by c; this implies that dropout training does not
have isolated local minima.
• The dropout penalty grows exponentially in the depth of the network in cases where the L2 regularizer
grows linearly. This may enable dropout to penalize the complexity of the network in a way that more
meaningfully reflects the richness of the network’s behaviors. (The exponential growth with d of the
dropout penalty is reminiscent of some regularizers for deep networks studied by Neyshabur, et al [20].)
• Dropout in deep networks has a variety of other behaviors different from standard regularizers. In particular: the dropout penalty for a set of weights can be negative; the dropout penalty of a set of weights
depends on both the training instances and the labels; and although the dropout probability intuitively
measures the strength of dropout regularization, the dropout penalties are often non-monotonic in the
dropout probability. In contrast, Wager, et al [28] show that when dropout is applied to generalized
linear models, the dropout penalty is always non-negative and does not depend on the labels.
Our analysis is for multilayer neural networks with the square loss at the output node. The hidden layers
use the popular rectified linear units [19] outputting σ(a) = max(0, a) where a is the node’s activation (the
weighted sum of its inputs). We study the minimizers of a criterion that may be viewed as the objective
function when using dropout. This abstracts away sampling and optimization issues to focus on the inductive
bias, as in [5, 30, 4, 18, 14]. See Section 2 for a complete explanation.

Related work
A number of possible explanations have been suggested for dropout’s success. Hinton, et al [16] suggest
that dropout controls network complexity by restricting the ability to co-adapt weights and illustrate how
it appears to learn simpler functions at the second layer. Others [3, 1] view dropout as an ensemble method
combining the different network topologies resulting from the random deletion of nodes. Wager, et al [27]
observe that in 1-layer networks dropout essentially forces learning on a more challenging distribution akin
to ‘altitude training’ of athletes.
Most formal analysis of the inductive bias of dropout has concentrated on the single-layer setting, where
a single neuron combines the (potentially dropped-out) inputs. Wager, et al [28] considered the case that
the distribution of label y given feature vector x is a member of the exponential family, and the log-loss
is used to evaluate models. They pointed out that, in this situation, the criterion optimized by dropout
can be decomposed into the original loss and a term that does not depend on the labels. They then gave
approximations to this dropout regularizer and discussed its relationship with other regularizers. As we have
seen, many aspects of the behavior of dropout and its relationship to other regularizers are qualitatively
different when there are hidden units.
Wager, et al [27] considered dropout for learning topics modeled by a Poisson generative process. They
exploited the conditional independence assumptions of the generative process to show that the excess risk of
dropout training due to training set variation has a term that decays more rapidly than the straightforward
empirical risk minimization, but also has a second additive term related to document length. They also
discussed situations where the model learned by dropout has small bias.
2

Baldi and Sadowski [2] analyzed dropout in linear networks, and showed how dropout can be approximated by normalized geometric means of subnetworks in the nonlinear case. Gal and Ghahramani [11]
described an interpretation of dropout as an approximation to a deep Gaussian process.
The impact of dropout (and its relative dropconnect) on generalization (roughly, how much dropout
restricts the search space of the learner) was studied in [29].
In the on-line learning with experts setting, Van Erven, et al [26] showed that applying dropout in on-line
trials leads to algorithms that automatically adapt to the input sequence without requiring doubling or other
parameter-tuning techniques.
The rest of the paper is organized as follows. Section 2 introduces our notation and formally defines
the dropout model. We prove that dropout enjoys several scaling invariances that weight-decay doesn’t in
Section 3, and that dropout requires negative weights even in very simple situations in Section 4. Section 5
uncovers various properties of the dropout penalty function. Section 6 describes some simulation experiments.
We provide some concluding remarks in Section 7.

2

Preliminaries

Throughout, we will analyze fully connected layered networks with K inputs, one output, d layers (counting
the output, but not the inputs), and n nodes in each hidden layer. We assume that n is a positive multiple
of K and that K is an even perfect square and a power of two to avoid unilluminating floor/ceiling clutter
in the analysis. We will call this the standard architecture. We use W to denote a particular setting of the
weights and biases in the network and W(x) to denote the network’s output on input x using W. The hidden
nodes are ReLUs, and the output node is linear. W can be decomposed as (W1 , b1 , ..., Wd−1 , bd−1 , w, b),
where each Wj is the matrix of weights on connections from the j − 1st into the jth hidden layer, each bj
is the vector of bias inputs into the jth hidden layer, w are the weights into the output node, and b is the
bias into the output node.
We will refer to a joint probability distribution over examples (x, y) as an example distribution. We focus
on square loss, so the loss of W on example (x, y) is (W(x) − y)2 . The risk is the expected loss with respect

def
to an example distribution P , we denote the risk of W as RP (W) = E(x,y)∼P (W(x) − y)2 . The subscript
will often be omitted when P is clear from the context.
The goal of L2 training is to find weights and biases minimizing the L2 criterion with regularization
def

strength λ: J2 (W) = R(W) + λ2 ||W||2 . Here and throughout, we use ||W||2 to denote the sum of the squares
of the weights of W. (As usual, the biases are not penalized.) We use WL2 to denote a minimizer of this
criterion. The L2 penalty, λ2 ||W||2 , is non-negative. This is useful, for example, to bound the risk of a
minimizer WL2 of J2 , since R(W) ≤ J2 (W).
Dropout training independently removes nodes in the network. In our analysis each non-output node is
dropped out with the same probability q, so p = 1 − q is the probability that a node is kept. (The output
node is always kept; dropping it out has the effect of cancelling the training iteration.) When a node is
dropped out, the node’s output is set to 0. To compensate for this reduction, the values of the kept nodes
are multiplied by 1/p. With this compensation, the dropout can be viewed as injecting zero-mean additive
noise at each non-output node [28]. 1
The dropout process is the collection of random choices, for each node in the network, of whether the
node is kept or dropped out. A realization of the dropout process is a dropout pattern, which is a boolean
vector indicating the kept nodes. For a network W, an input x, and dropout pattern R, let D(W, x, R)
be the output of W when nodes are dropped out or not following R (including the 1/p rescaling of kept
nodes’ outputs). The goal of dropout training on an example distribution P is to find weights and biases
minimizing the dropout criterion for a given dropout probability:

def
JD (W) = ER E(x,y)∼P (D(W, x, R) − y)2 .

1 Some authors use a similar adjustment where the weights are scaled down at prediction time instead of inflating the kept
nodes’ outputs at training time.

3

output
1

1
1

1

1

1
1

-1

x1

x2

Figure 1: A network where the dropout penalty is negative.
This criterion is equivalent to the expected risk of the dropout-modified network, and we use WD to denote
a minimizer of it. Since the selection of dropout pattern and example from P are independent, the order of
the two expectations can be swapped, yielding

(1)
JD (W) = E(x,y)∼P ER (D(W, x, R) − y)2 .

Equation (1) is a key property of the dropout criterion. It indicates when something is true about the dropout
criterion for a family of distributions concentrated on single examples, then (usually) the same thing will be
true for any mixture of these single-example distributions.
Consider now the example network in Figure 1. The weight parameters W1 and w are all-1’s, and all of
the biases are 0. W(1, −1) = 0 as each hidden node computes 0. Each dropout pattern indicates the subset
of the four lower nodes to be kept, and when q = p = 1/2 each subset is equally likely to be kept. If R is
the dropout pattern where input x2 is dropped and the other nodes are kept, then the network computes
D(W, (1, −1), R) = 8 (recall that when p = 1/2 the values of non-dropped out nodes are doubled). Only
three dropout patterns produce a non-zero output, so if P is concentrated on the example x = (1, −1), y = 8
the dropout criterion is:

2
13
1
(8 − 8)2 + (4 − 8)2 + (0 − 8)2 = 54.
(2)
16
16
16
As mentioned in the introduction, the dropout penalty of a weight vector for a given example distribution
and dropout probability is the amount that the dropout criterion exceeds the risk, JD (W) − R(W). Wager,
et al [28] show that for 1-layer generalized linear models, the dropout penalty is non-negative.
Since W(1, −1) = 0, we have R(W) = 64, and the dropout penalty is negative in our example. This is
because the variance in the output due to dropout causes the network to better fit the data (on average) than
the network’s non-dropout evaluation. In Section 5.2, we give a necessary condition for this variance to be
beneficial. As with the dropout criterion, the dropout penalty decomposes into an expectation of penalties
over single examples:


JD (W) − R(W) = E(x,y)∼P ER (D(W, x, R) − y)2 − (W(x) − y)2 .
JD (W) =

Definition 1 Define P(x,y) as the distribution with half of its weight on example (x, y) and half of its weight
on example (0, 0).

Unless indicated otherwise, we assume p = q = 1/2 for simplicity, although this is not crucial for our
results.

3
3.1

Scaling inputs, weights and outputs
Dropout is scale-free

Here we prove that dropout regularizes deep networks in a manner that is independent of the scale of the
input features. In other words, training under dropout regularization does not penalize the use of large
4

weights when needed to compensate for small input values.
Definition 2 For any example distribution P , define the dropout aversion with P to be the maximum, over
minimizers WD of the dropout risk JD (WD ), of RP (WD ) − inf W RP (W).
The dropout aversion of P measures the extent to which P is incompatible with the inductive bias
of dropout, measured by the risk gap between the true risk minimizer and the optimizers of the dropout
criterion.
Definition 3 For example distribution P and square matrix A, denote by A ◦ P the distribution obtained by
sampling (x, y) from P , and outputting (Ax, y).
When A is diagonal and has full rank, then A ◦ P is a rescaling of the inputs, like changing one input
from minutes to seconds and another from feet to meters.
Theorem 4 For any example distribution P , and any diagonal full-rank K × K matrix A, the dropout
aversion of P equals the dropout aversion of A ◦ P .
Proof: Choose a network W = (W1 , b1 , ..., Wd−1 , bd−1 , w, b). Let W ′ = (W1 A−1 , b1 ..., Wd−1 , bd−1 , w, b).
For any x, W(x) = W ′ (Ax), as A−1 undoes the effect of A before it gets to the rest of the network, which
is unchanged. Furthermore, for any dropout pattern R, we have D(W, x, R) = D(W ′ , Ax, R). Once again
A−1 undoes the effects of A on kept nodes (since A is diagonal), and the rest of the network W ′ is modified
by R an a manner paralleling W. Thus, there is bijection between networks W and networks W ′ with
JD (W ′ ) = JD (W) and R(W ′ ) = R(W), yielding the theorem.
Theorem 4 indicates that some common normalizations of the input features (e.g. to have unit variance)
do not affect the quality of the dropout criterion minimizers, but normalization might change the speed
of convergence and which minimizer is reached. Centering the features has slightly different properties.
Although it is easy to use the biases to define a W ′ that “undoes” the centering in the non-dropout computation, different W ′ appear to be required for different dropout patterns, breaking the bijection exploited in
Theorem 4.
As we will see in Section 3.4, weight decay does not enjoy such scale-free status.

3.2

Dropout’s invariance to parameter scaling

Next, we describe an equivalence relation among parameterizations for dropout networks of depth d ≥
2. Basically, scaling the parameters at a level creates a corresponding scaling of the output. (A similar
observation was made in a somewhat different context by Neyshabur, et al [20].)
Theorem 5 For any input x, dropout pattern R, any network W = (W1 , b1 , ..., Wd−1 , bd−1 , w, b), and any
positive c1 , ..., cd , if


 


d−1
d
Y
Y
W ′ = c1 W1 , c1 b1 , c2 W2 , c1 c2 b2 , ..., cd−1 Wd−1 , 
cj  bd−1 , cd w, 
cj  b  ,
(3)
j=1

then D(W ′ , x, R) =

Q

d
j=1 cj

′



D(W, x, R). In particular, if

Qd

j=1 cj

j=1

= 1, then for any example distribution

P , networks W and W have the same dropout criterion, dropout penalty, and expected loss.

Note that the re-scaling of the biases at layer j depends not only on the rescaling of the connection
weights at layer j, but also the re-scalings at lower layers.
Proof: Choose an input x and a dropout pattern R. Define W ′ as in (3). For each hidden layer j,
let (hj1 , ..., hjn ) be the jth hidden layer when applying W to x with
QR, and let (h̃j1 , ..., h̃jn ) be the jth
′
hidden layer when applying W instead. By induction, for all i, h̃ji =
ℓ≤j cℓ hji ; the key step is that the
5

pre-rectified value used to compute h̃ji has the same sign as for hji , since
Q rescaling by cj preserves
Qthe sign.
Thus the same units are zeroed out in W and W ′ and D(W, x, R) = ( j cj )D(W ′ , x, R). When j cj = 1,
this implies D(W, x, R) = D(W ′ , x, R). Since this is true for all x and R, we have JD (W) = JD (W ′ ). Since,
similarly, W(x) = W ′ (x) for all x, so R(W) = R(W ′ ), the dropout penalities for W and W ′ are also the
same.
Theorem 5 implies that the dropout criterion never has isolated minimizers, since one can continuously
up-scale the weights on one layer with a compensating down-scaling at another layer to get a contiguous
family of networks computing the same function and having the same dropout criterion. It may be possible to
exploit the parameterization equivalence of Theorem 5 in training by using canonical forms for the equivalent
networks or switching to an equivalent networks whose gradients have better properties. We leave this
question for future work.

3.3

Output scaling with dropout

Scaling the output values of an example distribution P does affect the aversion, but in a very simple and
natural way.
Theorem 6 For any example distribution P , if P ′ is obtained from P by scaling the outputs of P by a
positive constant c, the dropout aversion of P ′ is c2 times the dropout aversion of P .
Proof: If a network W minimizes the dropout criterion for P , then the network W ′ obtained by scaling up
the weights and bias for the output unit by c minimizes the dropout criterion for P ′ , and for any x, y, and
dropout pattern R, (D(W, x, R) − y)2 = (D(W ′ , x, R) − cy)2 /c2 .

3.4

Scaling properties of weight decay

Weight decay does not have the same scaling properties as dropout. Define the weight-decay aversion
analogously to the dropout aversion.
We analyze the L2 criterion for depth-2 networks in Appendix B, resulting in the following theorem. Our
proof shows that, despite the non-convexity of the L2 criterion, it is still possible to identify a closed form
for one of its optimizers.
Theorem 7 Choose an arbitrary number n of hidden nodes, and λ > 0.
λ2
).
The weight-decay aversion of P(x,1) is min( 41 , x·x
Theorem 7 shows that, unlike dropout, the weight decay aversion does depend on the scaling of the input
features.
√
Furthermore, when 2λ > x · x, the weight-decay criterion for P(x,1) has only a single isolated optimum
weight setting2 – all weights set to zero and bias 1/2 at the output node. This means that weight-decay
in 2-layer networks can completely regularize away significant signal in the sample even when λ is finite,
contrasting starkly with weight-decay’s behavior in 1-layer networks.
The “vertical” flexibility to rescale weights between layers enjoyed by dropout (Theorem 5) does not hold
for L2 : one can always drive the L2 penalty to infinity by scaling one layer up by a large enough positive
c, even while scaling another down by c. On the other hand, the proof of Theorem 7 shows that the L2
criterion has an alternative “horizontal” flexibility involving the rescaling of weights across nodes on the
hidden layer (under the theorem’s assumptions). Lemma 32 shows that at the optimizers each hidden node’s
contributions to the output are a constant (depending on the input) times their contribution to the the L2
penalty. Shifting the magnitudes of these contributions between hidden nodes leads to alternative weights
2 Since the output node puts weight 0 on each hidden node and the biases are unregularized, this optimum actually represents
a class of networks differing only in the irrelevant biases at the hidden nodes. One can easily construct other cases when weightdecay has isolated minima in this sense, for example when n = 2 and there is equal probability on x and −x, both with label
1.

6

that compute the same value and have the same weight decay penalty. This is a more general observation
than the permutation symmetry between hidden nodes because any portion of a hidden node’s contribution
can be shifted to another hidden node.

4

Negative weights for monotone functions

If the weights of a unit are non-negative, then the unit computes a monotone function, in the sense that
increasing any input while keeping the others fixed increases the output. The bias does not affect a node’s
monotonicity. A network of monotone units is also monotone.
We first present our theoretical results for many features (Section 4.1) and few features (Section 4.2),
and then discuss the implication of these results in Section 4.3.

4.1

The basic case – many features

In this section, we analyze the simple distribution P(1,1) that assigns probability 1/2 to the example
(0, ..., 0), 0, and probability 1/2 to the example (1, ..., 1), 1. This is arguably the simplest monotone function. Nevertheless, we prove that dropout uses negative weights to fit this data.
The key intuition is that optimizing the dropout criterion requires controlling the variance. Negative
weights at the hidden nodes can be used to control the variance due to dropout at the input layer. When
there are enough hidden nodes this becomes so beneficial that every minimizer of the dropout criterion uses
such negative weights.
Theorem 8 For the standard architecture, if K > 18 and n is large enough relative to K and d, every
optimizer of the dropout criterion for P(1,1) uses at least one negative weight.
To prove Theorem 8, we first calculate JD (Wneg ) for a network Wneg that uses negative weights, and
then prove a lower bound greater than this value that holds for all networks using only non-negative weights.
All of the biases in Wneg are 0.
A key building block in the definition of Wneg is a block of hidden units that we call the first-one gadget.
Each such block has K hidden nodes, and takes its input from the K input nodes. The ith hidden node
in the block takes the value 1 if the Kth input node is 1, and all inputs xi′ for i′ < i are 0. This can be
accomplished with a weight vector w with wi′ = −1 for i′ < i, with wi = 1, and with wi′ = 0 for i′ > i. The
first hidden layer of Wneg comprises n/K copies of the first-one gadget.
Informally, this construction removes most of the variance in the number of 1′ s in the input, as recorded
in the following lemma.
Lemma 9 On any input x ∈ {0, 1}n except (0, 0, ..., 0), the sum of the values on the first hidden layer of
Wneg is exactly n/K.
The weights into the remaining hidden layers of Wneg are all 1, and all the weights into the output
def

layer take a value c =

K2
,
1 d−2
2nd−1 (1+ K
n )(1+ n )

following lemma analyzes Wneg .

1
Lemma 10 JD (Wneg ) = 2 1 −

chosen to minimize the dropout criterion for the network. The

(1−2−K )
d−2

(1+ Kn )(1+ n1 )



.


d−2
1 + n1
denominator in Lemma 10 approaches 1, so
When n is large relative to K and d, the 1 + K
n
JD (Wneg ) approaches 2−K /2 in this case. Lemma 16 below gives a larger lower bound for any network with
all positive weights. In the concrete case when d = 2 and n = K 3 , then Lemma 10 implies JD (Wneg ) < 1/K 2 .

Proof (of Lemma 10): Consider a computation of Wneg (1, 1, ..., 1) under dropout and let ŷ be the
(random) output. Let k0 be the number of input nodes kept, and, for each j ≥ 2, let kj be the number of
7

nodes in the jth hidden layer kept. Call the node in each first-one gadget that computes 1 a key node, and
if no node in the gadget computes 1 because the input is all dropped, arbitrarily make the gadget’s first
hidden node the key node. This ensures there is exactly one key node per gadget, and every non-key node
computes 0. Let k1 be the number
kept key nodes on the first hidden layer. If k0 = 0, the output ŷ of the
Qof
d−1
network is 0. Otherwise, ŷ = c2d j=1 kj .
Note that k0 is zero with probability 2−K . Whenever k0 ≥ 1, k1 is distributed as B(n/K, 1/2). Each
other kj is distributed as B(n, 1/2), and k1 , k2 , ..., kd−1 are independent of one another.
E(ŷ) = Pr(k0 ≥ 1)c2d E[k1 |k0 ≥ 1]

d−1
Y
j=2

E[kj ] = (1 − 2−K )c2d

 n   n d−2 2c
= (1 − 2−K )nd−1 .
2K
2
K

Using the value of the second moment of the binomial, we get

2 
d−1
 n  n

Y


kj   = 4c2 (1 − 2−K )
E(ŷ 2 ) = E 1k0 ≥1 c2d
+ 1 nd−2 (n + 1)d−2
K
K
j=1
=


d−2

4c2 (1 − 2−K ) 2(d−1)
1
K
1
+
1
+
.
n
K2
n
n

Thus,

1
1 − 2E(ŷ) + E(ŷ 2 )
2

d−2 !

2
−K
4c
4c
(1
−
2
)
1
1
K
1 − (1 − 2−K )nd−1 +
n2(d−1) 1 +
=
1+
2
K
K2
n
n
!
(1 − 2−K )
1
1−
=

d−2 ,
2
1+ K 1+ 1

JD (Wneg ) =

n

since c =

K

d−2

1
2nd−1 (1+ K
n )(1+ n )

n

, completing the proof.

Next we prove a lower bound on JD for networks with nonnegative weights. Let W be an arbitrary such
network.
Our lower bound will use a property of the function computed by W that we now define.
Definition 11 A function φ : RK → R is supermodular if for all x, δ 1 , δ 2 ∈ RK where δ 1 , δ 2 ≥ 0
φ(x) + φ(x + δ 1 + δ 2 ) ≥ φ(x + δ 1 ) + φ(x + δ 2 ),
or equivalently:
φ(x + δ 1 + δ 2 ) − φ(x + δ 2 ) ≥ φ(x + δ 1 ) − φ(x)
The latter indicates that adding δ 1 to the bigger input x + δ 2 has at least as large an effect as adding it to
the smaller input x.
Since W has all non-negative weights, it computes a supermodular function of its inputs. (This fact may
be of independent interest.)
Lemma 12 If a network has non-negative weights and its activation functions σ(·) are convex, continuous,
non-decreasing, and differentiable except on a finite set, then the network computes a supermodular function
of its input x.

8

Proof: We will prove by induction over the layers that, for any unit h in the network, if h(x) is the output
of unit h when x is the input to W, then h(·) is a supermodular function of its input.
The base case holds since each input node h outputs the corresponding component of the input, and
(x + δ 1 ) − x = (x + δ 1 + δ 2 ) − (x + δ 2 ).
Now, for the inductive step, let w be the weight vector for node h, let b be its bias, and σ(·) be its
activation function. Let I(x), I(x + δ 1 ), I(x + δ 2 ), and I(x + δ 1 + δ 2 ) be the inputs to node h when the
inputs to the network are x, x + δ 1 , x + δ 2 and x + δ 1 + δ 2 respectively.
By induction, these inputs to node h (componentwise) satisfy
I(x + δ 1 ) − I(x) ≤ I(x + δ 1 + δ 2 ) − I(x + δ 2 ).
Therefore, since w, δ 1 , and δ 2 are non-negative, the interval [w · I(x + δ 2 ) + b, w · I(x + δ 1 + δ 2 ) + b] is at
least as long and starts at least as high as the interval [w · I(x) + b, w · I(x + δ 1 ) + b]. Since σ is continuous
and differentiable except on a finite set, we have
Z w·I(x+δ1 )+b
h(I(x + δ 1 )) − h(I(x)) =
σ ′ (z)dz
w·I(x)+b

≤

Z

w·I(x+δ 1 +δ 2 )+b

σ ′ (z)dz (since σ ′ is non-decreasing)

w·I(x+δ 2 )+b

= h(I(x + δ 1 + δ 2 )) − h(I(x + δ 2 )).
Definition 13 Let r0 ∈ {0, 1}K be the dropout pattern concerning the input layer, and let R′ be the dropout
pattern concerning the rest of the network, so that the dropout pattern R = (r0 , R′ ).
For each ℓ ∈ {0, ..., K}, let ψW (ℓ) be the average output of W under dropout when ℓ of the inputs are
kept: i.e.,


X
r0j = ℓ .
ψW (ℓ) = E D(W, 1K , (r0 , R′ ))
j

Lemma 14 For any ℓ ∈ {1, ..., K − 1, },

ψW (ℓ + 1) − ψW (ℓ) ≥ ψW (ℓ) − ψW (ℓ − 1).
Proof: Generate u, i and j randomly by, first choosing u uniformly at random from among bit vectors with
ℓ ones, then choosing i uniformly from the 0-components of u, and j uniformly from the 1-components of u.
By Lemma 12,
W(u + ei ) − W(u) ≥ W(u − ej + ei ) − W(u − ej )
(4)

always holds. Furthermore, u + ei is uniformly distributed among bit vectors with ℓ + 1 ones, u − ej is
uniformly distributed among bit vectors with ℓ − 1 ones, and u + ei − ej is uniformly distributed among bit
vectors with ℓ ones. This is true for W, but it is also true for any network obtained by dropping out some
of the hidden nodes of W. Thus
ψW (ℓ + 1) − ψW (ℓ)

= E(D(W, 1K , (r0 , R′ )|

= E(D(W, r0 , (1K , R′ )|
≥ E(D(W, r0 , (1K , R′ )|
= ψW (ℓ) − ψW (ℓ − 1),

X
j

X
j

X
j

r0j = ℓ + 1)) − E(D(W, 1K , (r0 , R′ )|
r0j = ℓ + 1)) − E(D(W, r0 , (1K , R′ )|
r0j = ℓ)) − E(D(W, r0 , (1K , R′ )|

9

X
j

X

r0j = ℓ))

j

X

r0j = ℓ))

j

r0j = ℓ − 1)) (by (4))

completing the proof.
We will use the following lower bound on the tail of the binomial. (Many similar lower bounds are
known.)
Lemma 15 If X is distributed according to Bin(n, 1/2), then
√
√
Pr(X < n/2 − n/4) = Pr(X > n/2 + n/4) ≥ 1/4.
√
√
Proof: Using √
the fact that, for any i, Pr(X = i) ≤ 1/ n, we get Pr(|X − n/2| < n/4) ≤ 1/2, so
Pr(X < n/2 − n/4) ≥ 1/4.
Now we are ready for the lower bound on JD (W).

1
Lemma 16 If K > 18 and the weights in W are non-negative, then JD (W) ≥ 36K
.
q
1
1
Proof: Assume to the contrary that JD (W) < 36K
. First, note that ψW (0) ≤ 18K
, or else the contribution

1
. Applying Lemma 15, we have
to JD (W) due to the (0, 0), 0 example is at least 36K
r
r
√
√
2
2
ψW (K/2 − K/4) > 1 −
and ψW (K/2 + K/4) < 1 +
9K
9K

(5)

1
for the (1, . . . , 1), 1 example.
as otherwise the contribution of one of the tails to JD (W) will be at least 36K
√
We will contradict this small variation of ψW (ℓ) around K/2. The bounds on ψW (0) and ψ(K/2 − K/4)
and Lemma 14 imply that ψW (ℓ) grows rapidly when ℓ is around K/2, in particular:
q
q
2
1
1 − 9K
− 18K
√
√
1
√
ψ(K/2 − K/4 + 1) − ψ(K/2 − K/4) ≥
> p
,
K/2 − K/4
9/32K

since K > 18. Now using Lemma 14 repeatedly shows that
√
√
ψ(K/2 + K/4) − ψ(K/2 − K/4) >

which contradicts (5), completing the proof.

√

1
K
×p
=2
2
9/32K

r

2
,
9K

Putting together Lemmas 10 and 16 immediately proves Theorem 8, since for K > 18 and large enough
n, the criterion for Wneg must be less than the criterion for any network with all non-negative weights.

4.2

The case when K = 2

Theorem 8 uses the assumption that K > 18 and n is large enough; is the lower bound on K really necessary?
Here we show that it is not, by treating the case that K = 2.
Theorem 17 For the standard architecture, if K = 2, for any fixed d and large enough n, every optimizer
of the dropout criterion for P(1,1),1 uses negative weights.
Proof: Define Wneg as in the proof of Lemma 10, except that the output layer has a bias of 1/5.
We claim that
lim JD (Wneg ) = 1/10.
n→∞

To see this, consider the joint input/label distribution under dropout:
Pr((0, 0), 0) = 1/2
Pr((0, 0), 1) = 1/8
Pr((2, 0), 1) = 1/8
Pr((0, 2), 1) = 1/8
Pr((2, 2), 1) = 1/8.
10

(6)

Due to the bias of 1/5 on the output, Wneg (0, 0) = 1/5. Thus, contribution to JD from examples with
x = (0, 0) in this joint distribution is 1/2 × (1/5)2 + 1/8 × (4/5)2 = 1/10.
Now, choose x 6= (0, 0). If, after dropout, the input is x, each node in the hidden layer closest to the
input computes 1. Arguing exactly as in the proof of Lemma 10, in such cases,
E((ŷ − 1)2 ) = 1 −

1+

2
n



1
1+


1 d−2
n

.

This proves (6).
Now, let W be an arbitrary network with non-negative weights.
For our distribution,


ER (D(W, (0, 0), R) − 0)2 + ER (D(W, (1, 1), R) − 1)2
JD (W) =
.
2
Let V00 = E(W(0, 0)), V22 = E(W(2, 2)), V20 = E(W(2, 0)), V02 = E(W(0, 2)) where the expectations are
taken with respect to the dropout patterns at the hidden nodes (with no dropout at the inputs). Since each
dropout pattern over the hidden nodes defines a particular network, and Lemma 12 holds for all of them,
the relationships also hold for the expectations, so
V22 ≥ V20 + V02 − V0 .
Using this V notation, handling the dropout at the input explicitly, and the bias-variance decomposition
keeping just the bias terms we get:

(V00 − 0)2 + (V00 − 1)2 + (V22 − 1)2 + (V20 − 1)2 + (V02 − 1)2 /4
2
8JD (W) ≥ 4(V00 − 0)2 + (V00 − 1)2 + (V22 − 1)2 + (V20 − 1)2 + (V02 − 1)2 .
JD (W) ≥

(7)
(8)

We will continue lower bounding the RHS. We can re-write V22 as V20 + V02 − V00 + ǫ where ǫ ≥ 0. This
is convex and symmetric in V02 and V20 so they both take the same value at the minimizer of the RHS, so
we proceed using V20 for this common minimizing value.
2
8JD (W) ≥ (2V20 − V00 + ǫ − 1)2 + 2(V20 − 1)2 + (V00 − 1)2 + 4V00
.

Differentiating with respect to V20 , we see that the RHS is minimized when V20 = (2 + V00 − ǫ)/3, giving
8JD (W) ≥

(V00 − ǫ − 1)2
2
+ (V00 − 1)2 + 4V00
.
3

If V00 ≥ 1, then JD ≥ 1/2 (just from the (0,0),0 example) and when V00 < 1 the RHS of the above is
minimized for non-negative ǫ when ǫ = 0. Using this substitution, the minimizing value of V00 is 1/4 giving
8JD (W) ≥ 1

JD (W) ≥ 1/8.

Combining this with (6) completes the proof.

11

4.3

More general distributions and implications

In the previous sub-section we analyzed the distribution P over the 2-feature examples (1, 1), 1 and (0, 0), 0.
However, these two examples can be embedded in a larger feature space by using any fixed vector of additional
feature values, creating, for instance, a distribution over (0, 1, 0, 0, 0, 1/2, 1), 0 and (0, 1, 1, 1, 0, 1/2, 1), 1 (with
the additional features underlined) The results of Section 4.2 still apply to distribution over these extended
examples after defining Wneg network to have zero weight on the additional features, and noticing that any
weight on the additional features in the positive-weight network W can be simulated using the biases at the
hidden nodes.
It is particularly interesting when the additional features all take the value 0, we call these zero-embeddings.
Every network W with non-negative weights has JD (W) ≥ 1/8 on each of these zero-embeddings of P . On
the other hand, a single Wneg network with n/K copies of the K-input first-one gadget has JD (Wneg ) ≈ 1/10
simultaneously for all of these zero-embeddings of P (when n >> K).
Any source distribution over {0, 1}K × {0, 1} that puts probability 1/2 on the the 0, 0 example and
distributes the other 1/2 probability over examples where exactly two inputs are one is a mixture of zeroembeddings of P , and thus JD (W) ≥ 1/8 while JD (Wneg ) ≈ 1/10 for this mixture and optimizing the
dropout criterion requires negative weights.
In our analysis the negative weights used by dropout are counterintuitive for fitting monotone behavior,
but are needed to control the variance due to dropout. This suggests that dropout may be less effective
when layers with sparse activation patterns are fed into wider layers, as dropout training can hijack part of
the expressiveness of the wide layer to control the artificial variance due to dropout rather than fitting the
underlying patterns in the data.

5
5.1

Properties of the dropout penalty
Growth of the dropout penalty as a function of d

Weight-decay penalizes large weights, while Theorem 5 shows that compensating rescaling of the weights
does not affect the dropout penalty or criterion. On the other hand, dropout can be more sensitive to the
calculation of large outputs than weight decay, and large outputs can be produced in deep networks using
only small weights. We make this observation concrete by exhibiting a family of networks where the depth
and desired output are linked while the size of individual weights remains constant. For this family, the
dropout penalty grows exponentially in the depth d (as opposed to linearly for weight-decay), suggesting
that dropout training is less willing to fit the data in this kind of situation.
Theorem 18 If x = (1, 1, ..., 1) and 0 ≤ y ≤ Knd−1 , for Px,y there are weights W for the standard
y2
,
architecture with R(W) = 0 such that (a) every weight has magnitude at most one, but (b) JD (W) ≥ K+1
whereas (c) J2 (W) ≤

λy 2/d
2 (Kn

+ n2 (d − 2) + n).

1/d

Proof: Let W be the network whose weights are all c = K 1/dyn(d−1)/d and biases are all 0, so that the L2
penalty is the number of weights times λc2 /2. It is a simple induction to show that, for these weights and
input (1, 1, ..., 1), the value computed at each hidden node on level j is cj Knj−1 , so the the network outputs
cd Knd−1 , and has zero square loss (since W(x) = cd Knd−1 = y).
Consider now dropout on this network. This is equivalent to changing all of the weights from c to 2c and,
independently with probability 1/2, replacing the value of each node with 0. For a fixed dropout pattern,
each node on a given layer has the same weights, and receives the same (kept) inputs. Thus, the value
computed at every node on the same layer is the same. For each j, let Hj be the value computed by the
units in the jth hidden layer.
If k0 is the number of input nodes kept under dropout, and, for each j ∈ {1, ..., d − 1}, kj is the number of
Qℓ−1
hidden nodes kept in layer j, a straightforward induction shows that, for all ℓ, we have Hℓ = (2c)ℓ j=0 kj ,
Qd−1
so that the output ŷ of the network is (2c)d j=0 kj .
12

Using a bias-variance decomposition, E((ŷ − y)2 ) = (E[ŷ] − y)2 + Var(ŷ). Since each kj is binomially
distributed, and k0 , ..., kd−1 are independent, we have E(ŷ) = (2c)d (K/2)(n/2)d−1 = cd Knd−1 = y, so
E((ŷ − y)2 ) = Var(ŷ). Since E(ŷ 2 ) = (2c)2d (K(K + 1)/4)(n(n + 1)/4)d−1 = y 2 (1 + 1/K)(1 + 1/n)d−1 , we
have Var(ŷ) = E(ŷ 2 ) − E(ŷ)2 = y 2 ((1 + 1/K)(1 + 1/n)d−1 − 1) ≥ y 2 /K, completing the proof.
If y = exp(Θ(d)), the dropout penalty grows exponentially in d, whereas the L2 penalty grows polynomially.

5.2

A necessary condition for negative dropout penalty

Section 2 contains an example where the dropout penalty is negative. The following theorem provides a
necessary condition.
Theorem 19 The dropout penalty can be negative. For all example distributions, a necessary condition for
this in rectified linear networks is that either a weight, input, or bias is negative.
Proof: [2] show that for networks of linear units (as opposed to the non-linear rectified linear units we
focus on) the network’s output without dropout equals the expected output over dropout patterns, so in
our notation: W(x) equals ER (D(W, x, R)). Assume for the moment that the network consists of linear
units and the example distribution is concentrated on the single example (x, y). Using the bias-variance
decomposition for square loss and this property of linear networks,

JD (W) = ER (D(W, x, R)−y)2 = (ER (D(W, x, R)−y)2 + VarR (D(W, x, R)) ≥ (W(x) − y)2

and the dropout penalty is again non-negative. Since the same calculations go through when averaging
over multiple examples, we see that the dropout penalty is always non-negative for networks of linear nodes.
When all the weights, biases and inputs in a network of rectified linear units are positive, then the rectified
linear units behave as linear units, so the dropout penalty will again be non-negative.

5.3

Multi-layer dropout penalty does depend on labels

In contrast with its behavior on a variety of linear models including logistic regression [28], the dropout
penalty can depend on the value of the response variable in deep networks with ReLUs and the quadratic
loss. Thus in a fundamental and important respect, dropout differs from traditional regularizers like weightdecay or an L1 penalty.
Theorem 20 There are joint distributions P and Q, and weights W such that, for all dropout probabilities
q ∈ (0, 1), (a) the marginals of P and Q on the input variables are equal, but (b) the dropout penalties of W
with respect to P and Q are different.
We will prove Theorem 20 by describing a general, somewhat technical, condition that implies that P
and Q are witnesses to Theorem 20.
For each input x and dropout pattern R, let H(W, x, R) be the values presented to the output node with
dropout. As before, let w ∈ Rn be those weights of W on connections directly into the output node and let
b be the bias at the output node. Let r ∈ {0, 1}n be the indicator variables for whether the various nodes
connecting to the output node are kept.
Proof (of Theorem 20): Suppose that P is concentrated on a single (x, y) pair. We will then get Q by
modifying y.
Let h be the values coming into the output node in the non-dropped out network. Therefore the output
of the non-dropout network is w · h + b while the output of the network with dropout is w · H(W, x, R) + b.
We now examine the dropout penalty, which is the expected dropout loss minus the non-dropout loss. We

13

will use δ as a shorthand for w · (H(W, x, R) − h).


dropout penalty = E (w · H(W, x, R) + b − y)2 − (w · h + b − y)2

= E (w · H(W, x, R) + b − w · h + w · h − y)2 − (w · h + b − y)2

= E δ 2 + 2(w · h + b − y)E(δ)

which depends on the label y unless E(δ) = 0.
Typically E(δ) 6= 0. To prove the theorem, consider the case where x = (1, −2) and there are two hidden
nodes with weights 1 on their connections to the output node. The value at the hidden nodes without
dropout is 0, but with dropout the hidden nodes never negative and computes positive values when only the
negative input is dropped, so the expectation of δ is positive.

6

Experiments

We did simulation experiments using Torch [25]. The code is accessible at
https://www.dropbox.com/sh/6s2lcfrq17zshmp/AAAQ06uDa4gOAuAnw2MAghEMa?dl=0

6.1

Negative Weights

We trained networks with the standard architecture with K = 5 inputs, depth 3, and width 50 on the training
data studied in Section 4: one input with x = (0, 0, ..., 0) and y = 0, and one input with x = (1, 1, ..., 1) and
y = 1. We used the nn.StochasticGradient function from Torch with a maximum of 10000 iterations, and
0.1
a learning rate of 1+0.1×t
on iteration t.
With the above parameters, we repeated the following experiment 1000 times.
• Initialize the parameters of a network WD .
• Clone this network, to produce a copy W with the same initialization.
• Train WD with dropout probability 1/2 at all nodes, and train W without dropout (without using
weight decay for either one).
• Compare the number of negative weights neg(WD ) in WD with neg(W).
Counts of the outcomes are shown in the following table.
neg(WD ) > neg(W)
584

neg(WD ) < neg(W)
338

neg(WD ) = neg(W)
78

Recall that Theorem 8 shows that a global optimizer of the dropout criterion definitely uses negative
weights when trained on data sources similar to P(1,1) , despite the fact that that they are consistent with a
monotone function. This experiment shows that even when optimization is done in a standard way, using
dropout tends to create models with more negative weights for P(1,1) , and we attribute this to the variance
reduction effects associated with Theorem 8.
The experiment also indicates that training with dropout sometimes produces fewer negative weights. Due
to the random initialization, a hidden ReLU unit with negative weights can evaluate to 0 on both inputs,
so its weights will never be updated without dropout. On the other hand, the extra variance from dropout
could cause updates to these negative weights. Another way the non-dropout training could produce more
negative weights is if a hidden node whose output is too large has many small weights that turn negative
with a standard gradient descent step. However, with dropout only about half the small weights will be
updated. Theorem 8 focusses on the effect of dropout at the global minimum, and abstracts away these
kinds of initialization and optimization effects.
14

1.1
Dropout
Weight Decay
1

Training error

0.9

0.8

0.7

0.6

0.5
0.4

0.6

0.8

1

1.2

1.4

1.6

Input Scale

Figure 2: Training error as a function of the scale of the inputs for Dropout and Weight Decay in the
experiment of Section 6.2.

6.2

Scale (in)sensitivity

Our experiments regarding the sensitivity with respect to the scale of the input used the standard architecture
with K = 5, d = 2, n = 5. We used stochastic gradient using the optim package for Torch, with learning
0.01
and momentum of 0.5, and a maximum of 100000 iterations.
rate 1+0.00001t
We performed 10 sets of training runs. In each run:
• Ten training examples were generated uniformly at random from [−1, 1]K .
Q
• Target outputs were assigned using y = i sign(xi ).

• Five training sets S1 , ..., S5 with ten examples each were obtained by rescaling the inputs by {0.5, 0.75, 1, 1.25, 1.5}
and leaving the outputs unchanged.

• The weights of a network Winit were initialized using the default initialization from Torch.
• For each Si :
– Winit was cloned three times to produce WD , W2 and Wnone with identical starting parameters.

– WD was trained with dropout probability 1/2 and no weight decay.

– W2 was trained with weight decay with λ = 1/2 and no dropout.

– Wnone was trained without any regularization.

The average training losses of WD and W2 , over the 10 runs, are shown in Figure 2. (The average training
loss of Wnone was less than 0.05 at all scales.)
The theoretical insensitivity of dropout to the scale of the inputs described in Theorem 4 is also seen
here, along with the contrast with weight decay analyzed in Theorem 7.
The scale of the inputs also affects the dynamics of stochastic gradient descent. With very small inputs,
convergence is very slow, and with very large inputs, SGD is unstable. The effects of the scale of the inputs
on inductive bias analyzed in this paper are visible at the scales where optimization can be done effectively.

7

Conclusions

The reasons behind dropout’s surprisingly good performance in training deep networks across a variety of
applications are somewhat mysterious and there is relatively little existing formal analysis. A variety of
15

explanations have been offered (e.g. [1, 2, 3, 11, 27]), including the possibility that dropout reduces the
amount of coadaptation in a network’s weights [16].
The dropout criterion is an expected loss over dropout patterns, and the variance in the output values
over dropout patterns contributes to this expected loss. Therefore dropout may co-adapt weights in order
to reduce this (artificial) variance. We prove that this happens even in very simple situations where nothing
in the training data justifies negative weights (Theorem 8). This indicates that the relationship between
dropout and co-adaption is not a simple one.
The effects of dropout in deep neural networks are rather complicated, and approximations can be
misleading since the dropout penalty is very non-convex even in 1-layer networks [14]. In Section 3 we show
that dropout does enjoy several scale-invariance properties that are not shared by weight-decay. A perhaps
surprising consequence of these invariances is that there are never isolated local minima when learning a
deep network with dropout. Further exploration of these scale invariance properties is warranted to see
if they are a contributor to dropout’s empirical success or can be exploited to facilitate training. While
contrasting dropout to weight-decay in simple situations, we found that a degenerate all-zero network results
(Theorem 7) when the L2 regularization parameter is above a threshold. This is in dramatic contrast to our
previous intuition from the 1-layer case.
In [28], dropout was viewed as a regularization method, adding a data dependent penalty to the empirical
loss of (presumably) undesirable solutions. Section 5 shows that, unlike the generalized linear models case
analyzed there, the dropout penalty in deeper networks can be negative and depends on the labels in the
training data, and thus behaves unlike most regularizers. On the other hand, the dropout penalty can grow
exponentially in the depth of the network, and thus may better reflect the complexity of the underlying
model space than L2 regularization.
This paper uncovers a number of dropout’s interesting fundamental properties using formal analysis of
simple cases. However, the effects of using dropout training in deep networks are subtle and complex, and
we hope that this paper lays a foundation to promote further formal analysis of dropout’s properties and
behavior.

Acknowledgments
We are very grateful to Peter Bartlett, Seshadhri Comandur, and anonymous reviewers for valuable communications.

References
[1] P. Bachman, O. Alsharif, and D. Precup. Learning with pseudo-ensembles. NIPS, 2014.
[2] P. Baldi and P. Sadowski. The dropout learning algorithm. Artificial intelligence, 210:78–122, 2014.
[3] Pierre Baldi and Peter J Sadowski. Understanding dropout. In Advances in Neural Information Processing
Systems, pages 2814–2822, 2013.
[4] P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the
American Statistical Association, 101(473):138–156, 2006.
[5] L. Breiman. Some infinity theory for predictor ensembles. Annals of Statistics, 32(1):1–11, 2004.
[6] Caffe, 2016. http://caffe.berkeleyvision.edu.
[7] Danqi Chen and Christopher D Manning. A fast and accurate dependency parser using neural networks. In
EMNLP, pages 740–750, 2014.
[8] G. E. Dahl. Deep learning how I did it: Merck 1st place interview, 2012. http://blog.kaggle.com.
[9] G. E. Dahl, T. N. Sainath, and G. E. Hinton. Improving deep neural networks for LVCSR using rectified linear
units and dropout. ICASSP, 2013.
[10] L. Deng, J. Li, J. Huang, K. Yao, D. Yu, F. Seide, M. L. Seltzer, G. Zweig, X. He, J. Williams, Y. Gong, and
A. Acero. Recent advances in deep learning for speech research at microsoft. ICASSP, 2013.

16

[11] Yarin Gal and Zoubin Ghahramani. Dropout as a Bayesian approximation: Representing model uncertainty in
deep learning. arXiv:1506.02142, 2015.
[12] Ian J. Goodfellow, David Warde-Farley, Mehdi Mirza, Aaron C. Courville, and Yoshua Bengio. Maxout networks.
In ICML, pages 1319–1327, 2013.
[13] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level
performance on imagenet classification. In ICCV, pages 1026–1034, 2015.
[14] D. P. Helmbold and P. M. Long. On the inductive bias of dropout. JMLR, 16:3403–3454, 2015.
[15] G. E. Hinton. Dropout: a simple and effective way to improve neural networks, 2012. videolectures.net.
[16] G. E. Hinton, N. Srivastava, A. Krizhevsky, I. Sutskever, and R. R. Salakhutdinov. Improving neural networks
by preventing co-adaptation of feature detectors, 2012. Arxiv, arXiv:1207.0580v1.
[17] Nal Kalchbrenner, Edward Grefenstette, and Phil Blunsom. A convolutional neural network for modelling
sentences. In ACL, pages 655–665, 2014.
[18] P. M. Long and R. A. Servedio. Random classification noise defeats all convex potential boosters. Machine
Learning, 78(3):287–304, 2010.
[19] Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In ICML,
pages 807–814, 2010.
[20] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In
COLT, pages 1376–1401, 2015.
[21] Jürgen Schmidhuber. Deep learning in neural networks: An overview. Neural Networks, 61:85–117, 2015.
[22] N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Dropout: A simple way to prevent
neural networks from overfitting. JMLR, 15:1929–1958, 2014.
[23] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan,
Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. CVPR, 2015.
[24] Tensorflow, 2016. https://www.tensorflow.org.
[25] Torch, 2016. http://torch.ch.
[26] T. Van Erven, W. Kotłowski, and M. K. Warmuth. Follow the leader with dropout perturbations. COLT, pages
949–974, 2014.
[27] S. Wager, W. Fithian, S. Wang, and P. S. Liang. Altitude training: Strong bounds for single-layer dropout.
NIPS, 2014.
[28] S. Wager, S. Wang, and P. Liang. Dropout training as adaptive regularization. NIPS, 2013.
[29] L. Wan, M. Zeiler, S. Zhang, Y. Le Cun, and R. Fergus. Regularization of neural networks using dropconnect.
In ICML, pages 1058–1066, 2013.
[30] T. Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization.
Annals of Statistics, 32(1):56–85, 2004.

17

A

Table of Notation

Notation
1set
(x, y)
σ(·)
W
w, v
W(x)
P
Px,y
RP (W)
q, p
R
r, s
D(W, x, R)
JD (W)
J2 (W)
λ
WD
WL2
n, d
K

B

Meaning
indicator function for “set”
an example with feature vector x and label y
the rectified linear unit computing max(0, ·)
an arbitrary weight setting for the network
specific weights, often subscripted
the output value produced by weight setting W on input x
an arrelbitrary source distribution over (x, y) pairs
the source distribution concentrated on the single example (x, y)
the risk (expected square loss) of W under source P
probabilities that a node is dropped out (q) or kept (p) by the dropout process
a dropout pattern, indicates the kept nodes
dropout patterns on subsets of the nodes
Output of dropout with network weights W, input x, and dropout pattern R
the dropout criterion
the L2 criterion
the L2 regularization strength parameter
an optimizer of the dropout criterion
an optimizer of the L2 criterion
the network width and depth
the number of input nodes

Proof of Theorem 7

Here we prove Theorem 7, showing that the weight-decay aversion depends on the values of the inputs and
the number of input nodes K. Furthermore, unlike the single-layer case, the L2 regularization strength has
a threshold where the minimizer of the L2 criterion degenerates to the all-zero network.
We will focus on the standard architecture with depth d = 2. Recall that we are analyzing the distribution
P(x,1) that assigns probability 1/2 to (x, 1) and probability 1/2 to (0, 0).
Also, recall that, for P(x,1) , the weight-decay aversion is the maximum risk incurred by a minimizer of
J2 . This motivates the following definition.
Definition 21 An aversion witness is a minimizer of J2 that is also a maximizer of the risk R, from among
minimizers of J2 .
The proof of Theorem 7 involves a series of lemmas.
We first show that there is a aversion witness WL2 with a special form, and then relate any hidden node’s
effect on the output to the regularization penalty on the weights in and out of that node. This will allow us
to treat optimizing the L2 criterion as a one-dimensional problem, whose solution yields the theorem.
For some minimizer WL2 of J2 , let v∗j denote the vector of weights into hidden node j and wj∗ denote the
weight from j to the output node. Let a∗j be the bias for hidden node j and let b∗ be the bias for the output
node. Let hj be the function computed by hidden node j.
Note that, if there is an aversion witness with a certain property, then we may assume without loss of
generality that WL2 has that property.
Lemma 22 We may assume without loss of generality that for each hidden node j, there is an input x̃ ∈
{0, x} such that hj (x̃) = 0.
Proof: Suppose neither of hj (0) or hj (x) was 0. If wj∗ = 0, then replacing both with 0 does not affect
the output of WL2 , and does not increase the penalty. If wj∗ 6= 0, then subtracting min{hj (0), hj (x)}
18

from a∗j and adding

min{hj (0),hj (x)}
wj∗

min{hj (0), hj (x)} = 0.

to b does not affect WL2 or the penalty, but, after this transformation,

Lemma 23 We may assume without loss of generality that for each hidden node j, we have |v∗j · x| =
max{hj (0), hj (x)}.
Proof: If hj (x) ≥ hj (0) = 0, then a∗j = 0, and hj (x) = v∗j · x.
If hj (0) > hj (x) = 0. Then, a∗j > 0, and v∗j · x ≤ −a∗j . If needed, the magnitude of v∗j can be decreased
to make v∗j · x = −a∗j . This decrease does not affect WL2 (x) or WL2 (0), and can only reduce the L2 penalty.
Lemma 24 We may assume without loss of generality that for each hidden node j, we have hj (0) = 0.
Proof: Suppose hj (0) > 0. Let z be this old value of hj (0). Then hj (x) = 0 and z = hj (0) = −v∗j · x. If
we negate v∗ and set aj = 0, then Lemma 23 implies that we swap the values of hj (x) and hj (0).
Then, by adding zwj∗ to b∗ and negating wj∗ , we correct for this swap at the output node and do not
affect the function computed by WL2 or the penalty.
Note that Lemma 24 implies that a∗1 = ... = a∗K = 0.

Lemma 25 For all j, v∗j · x ≥ 0.
Proof: Since a∗j = 0, if v∗j · x < 0, we could make WL2 compute the same function with a smaller penalty
by replacing v∗j with 0.
Lemma 25 implies that the optimal WL2 computes the linear function,
WL2 (x̃) = (w∗ )T V ∗ x̃ + b∗ .

(9)

Later we will call (w∗ )T V ∗ x̃ the activation at the output node.
Lemma 26 b∗ =

1−(w∗ )T V ∗ x
.
2

Proof: Minimize J2 (wrt distribution P(x,1) ) as a function of b using Calculus.
Now, we have
WL2 (x̃) =

1
+ (w∗ )T V ∗ (x̃ − x/2)
2

(10)

which immediately implies
WL2 (0) = 1 − WL2 (x).

(11)

Lemma 27 Each v∗j is a rescaling of x.
Proof: Projecting v∗j onto the span of x does not affect hj , and cannot increase the penalty.
Lemma 28 WL2 (x) ≤ 1.
Proof: By (11), if WL2 (x) > 1 then WL2 (0) < 0 and the loss and the penalty would both be reduced by
scaling down w∗ .
Lemma 29 WL2 maximizes W(x) over those weight vectors W that have the same penalty as WL2 and
compute a function of the form W(x̃) = 12 + (w)T V (x̃ − x/2) (i.e. Equation 10).

19

Proof: Let W maximize W(x) over the networks considered. If WL2 (x) < W(x) ≤ 1, then W would have
the same penalty as WL2 but smaller error, contradicting the optimality of WL2 .
f obtained by scaling down the weights in the output layer so that
If W(x) > 1, then the network W
f
W(x) = 1 has a smaller penalty than WL2 and smaller error, again contradicting WL2 ’s optimality.

Informally, Lemmas 28 and 29 engender a view of the learner straining against the yolk of the L2 penalty
to produce a large enough output on x. This motivates us to ask how large W(x) can be, for a given value
of ||W||22 (recall that Lemma 25 allows us to assume that the biases at the hidden nodes are all 0).

Definition 30 For each hidden node j, let αj be the constant such v∗j = αj x, so that hj (x) = αj x · x.
Recall that the activation at the output node on input x is the weighted sum of the hidden-node outputs,
(w∗ )T V ∗ x.
Definition 31 The contribution to the activation at the output due to hidden node j is wj∗ hj (x) = wj∗ αj x · x

and the contribution to the L2 penalty from these weights is λ2 (wj∗ )2 + α2j x · x .
We now bound the contribution to the activation in terms of the contribution to the L2 penalty. Note
that as the L2 “budget” increases, so does the the maximum possible contribution to the output node’s
activation.

Lemma 32 If B is hidden node j’s weight-decay contribution, (wj∗ )2 + α2j x · x, then hidden node k’s contriq
q
B
, where it achieves the
bution to the output node’s activation is maximized when wj∗ = B2 and αj = 2x·x
√
value B x · x/2
q
Proof: Since α2j x · x + (wj∗ )2 = B, we have wj∗ = B − α2j x · x, so the contribution to the activation
q
can be re-written as αj x · x B − α2j x · x. Taking the derivative with respect to αj , and solving, we get
q
q
B
B
αj = ± 2x·x
and we want the positive solution (otherwise the node outputs 0). When αj = 2x·x
we have
q
wj∗ = B2 and thus the node’s maximum contribution to the activation is
r

B
2

r

√
B x·x
B
(x · x) =
.
2x · x
2

Lemma 33 The minimum sum-squared weights for a network W (without biases at the hidden nodes) that
has an activation A at the output node on input x is √2A
.
x·x
√
Proof: When maximized, the contribution of each hidden node to the activation at the output is x · x/2
times the hidden node’s contribution to the sum of squared-weights. Since each weight in W is used in
exactly one hidden node’s contribution to the output node’s activation, this completes the proof.
Note that this bound is independent of n, the number of hidden units, but does depend on the input x.
Proof (of Theorem 7): Let A ≥ 0 be the activation at the output node for WL2 on input x. From
Lemma 26 we get that b∗ = 1−A
2 . Combining Lemmas 28 , 29 and 33, we can re-write the J2 criterion for
WL2 and distribution P(x,1) in terms of A as follows.
λ
1
1 ∗
2
2
(b − 0) + (WL2 (x) − 1) + ||W||22
2
2
2
!

2 
2
1−A
1
1+A
2A
+
=
− 1 + λ√
.
2
2
2
x·x

J2 (WL2 ) =

20

(12)

Differentiating with respect to A, we see that the criterion is minimized when
A=1− √

2λ
x·x

2λ
≤1
x·x
2λ
>1
when √
x·x

when √

A=0

since we assumed A ≥ 0; when A = 0 then WL2 has all zero weights with a bias of 1/2 at the output.
The risk part of (12) simplifies to
λ2
(1 − A)2
=
,
4
x·x


1 λ2
so the overall the risk of an aversion witness is min
.
,
4 x·x

21

