On the Inductive Bias of Dropout
David P. Helmbold

dph@soe.ucsc.edu

Department of Computer Science
University of California, Santa Cruz
Santa Cruz, CA 95064, USA

Philip M. Long

plong@microsoft.com

Microsoft
1020 Enterprise Way
Sunnyvale, CA 94089, USA

Editor: Samy Bengio

Abstract
Dropout is a simple but effective technique for learning in neural networks and other settings. A sound theoretical understanding of dropout is needed to determine when dropout
should be applied and how to use it most effectively. In this paper we continue the exploration of dropout as a regularizer pioneered by Wager et al. We focus on linear classification
where a convex proxy to the misclassification loss (i.e. the logistic loss used in logistic regression) is minimized. We show:• when the dropout-regularized criterion has a unique minimizer,• when the dropout-regularization penalty goes to infinity with the weights, and when it remains
bounded,• that the dropout regularization can be non-monotonic as individual weights increase from 0,
and• that the dropout regularization penalty may not be convex.
This last point is particularly surprising because the combination of dropout regularization
with any convex loss proxy is always a convex function.
In order to contrast dropout regularization with L2 regularization, we formalize thenotion of when different random sources of data are more compatible with different regularizers. We then exhibit distributions that are provably more compatible with dropout
regularization than L2 regularization, and vice versa. These sources provide additional
insight into how the inductive biases of dropout and L2 regularization differ. We provide
some similar results for L1 regularization.
Keywords: Dropout, Inductive Bias, Learning Theory, Regularization, Feature Noising

1. Introduction
Since its prominent role in a win of the ImageNet Large Scale Visual Recognition Challenge(Hinton, 2012; Hinton et al., 2012; Srivastava et al., 2014), there has been intense interestin dropout (see the work by Dahl, 2012; Deng et al., 2013; Dahl et al., 2013; Wan et al.,2013; Wager et al., 2013; Baldi and Sadowski, 2014; Van Erven et al., 2014). Dropout isa modification of stochastic gradient descent where each update is performed on a reduced1Helmbold and Long

network created by temporarily removing a random subset of the nodes. This paper studies
the inductive bias of dropout: when one chooses to train with dropout, what prior preference
over models results? We show that dropout training shapes the learner’s search space ina much different way than L1 or L2 regularization. Our results shed new insight into
why dropout prefers rare features, how the dropout probability affects the strength of
regularization, and how dropout restricts the co-adaptation of weights.
Our theoretical study will concern learning a linear classifier via convex optimization.
The learner wishes to find a parameter vector w so that, for a random feature-label pair(x, y) ∈ Rn ×{−1, 1} drawn from some joint distribution P , the probability that sign(w·x) 6=
y is small. It does this by using training data to try to minimize E(`(yw · x)), where`(z) = ln(1 + exp(−z)) is the loss function associated with logistic regression.
We have chosen to focus on this problem for several reasons. First, the inductive bias ofdropout is not well understood even in this simple setting. Second, linear classifiers remain
a popular choice for practical problems, especially in the case of very high-dimensional
data. Third, we view a thorough understanding of dropout in this setting as a mandatory
prerequisite to understanding the inductive bias of dropout when applied in a deep learning
architecture. This is especially true when the preference over deep learning models is
decomposed into preferences at each node. In any case, the setting that we are studying
faithfully describes the inductive bias of a deep learning system at its output nodes.
We will borrow the following clean and illuminating description of dropout as artificial
noise due to Wager et al. (2013). An algorithm for linear classification using loss ` anddropout updates its parameter vector w online, using stochastic gradient descent. Givenan example (x, y), the dropout algorithm independently perturbs each feature i of x: withprobability q, xi is replaced with 0, and, with probability p = 1 − q, xi is replaced with
xi /p. Equivalently, x is replaced by x + ν, where

νi =

−xi
with probability q(1/p − 1)xi with probability p = 1 − q

before performing the stochastic gradient update step. (Note that, while ν obviously depends on x, if we sample the components of b ∈ {−1, 1/p−1}n independently of one anotherand x, by choosing bi = −1 with the dropout probability q, then we may write νi = bi xi .)Stochastic gradient descent is known to converge under a broad variety of conditions(Kushner and Yin, 1997). Thus, if we abstract away sampling issues as done by Breiman(2004); Zhang (2004); Bartlett et al. (2006); Long and Servedio (2010), we are led to consider
defw∗ = argminw E(x,y)∼P,ν (`(yw · (x + ν)))as dropout can be viewed as a stochastic gradient update of this global objective function.
We call this objective the dropout criterion, and it can be viewed as a risk on the dropoutinduced distribution. (Abstracting away sampling issues is consistent with our goal ofconcentrating on the inductive bias of the algorithm. From the point of view of a biasvariance decomposition, we do not intend to focus on the large-sample-size case, where thevariance is small, but rather to focus on the contribution from the bias where P could bean empirical sample distribution.)2

On the Inductive Bias of Dropout

We start with the observation of Wager et al. (2013) that the dropout criterion may be
decomposed as
E(x,y)∼P,ν (`(yw · (x + ν))) = E(x,y)∼P (`(yw · x)) + regD,q (w),(1)

where regD,q (w) is non-negative, and depends only on the marginal distribution D overthe feature vectors x (along with the dropout probability q), and not on the labels. This
leads naturally to a view of dropout as a regularizer.
A popular style of learning algorithm minimizes an objective function like the RHS of(1), but where regD,q (w) is replaced by a norm of w. One motivation for algorithms inthis family is to first replace the training error with a convex proxy to make optimization
tractable, and then to regularize using a convex penalty such as a norm, so that the objectivefunction remains convex.
We show that regD,q (w) formalizes a preference for classifiers that assign a very large
weight to a single feature. This preference is stronger than what one gets from a penalty
proportional to ||w||1 . In fact, despite the convexity of the dropout risk, we show that
regD,q (w) is not convex. Therefore that dropout provides a way to realize the inductive
bias arising from a non-convex penalty while still enjoying the benefit of convexity in theoverall objective function (see the plots in Figures 1, 2 and 3). Figure 1 shows the evenmore surprising result that the dropout regularization penalty is not even monotonic in theabsolute values of the individual weights.
It is not hard to see that regD,q (0) = 0. Thus, if regD,q (w) is greater than the expected
loss incurred by 0 (which is ln 2), then it might as well be infinity, because dropout will
prefer 0 to w. However, in some cases, dropout never reaches this extreme—it remains
willing to use a models with arbitrarily large parameters, unlike methods that use a convex
penalty. In particular,
regD,q (w1 , 0, 0, 0, ..., 0) < ln 2
for all D, no matter how large w1 gets. On the other hand, except for some special cases(which are detailed in the body of the paper),
regD,q (cw1 , cw2 , 0, 0, ..., 0)goes to infinity with c. It follows that regD,q (w) cannot be approximated to within any
factor, constant or otherwise, by a convex function of w.
To get a sense of which sources dropout can be successfully applied to, we compare
dropout with an algorithm that regularizes using L2 , by minimizing the L2 criterion:
E(x,y)∼P (`(yw · x)) +λ||w||22 .
2(2)

Will will use “L2 ” as a shorthand to refer to an algorithm that minimizes (2). Note thatq, the probability of dropping out an input feature, plays a role in dropout analogous toλ. In particular, as q goes to zero the examples remain unperturbed and the dropout
regularization has no effect.
Informally, we say that joint probability distributions P and Q separate dropout from L2
if, when the same parameters λ and q are used for both P and Q, then using dropout leads
to a much more accurate hypothesis for P , and using L2 leads to a much more accurate3Helmbold and Long

hypothesis for Q. This enables us to illustrate the inductive biases of the algorithms throughcontrasting sources that either align or are incompatible with the algorithms’ inductive
bias. Comparing with another regularizer helps to restrict these illustrative examples to“reasonable” sources, which can be handled using the other regularizer. Ensuring that thesame values of the regularization parameter are used for both P and Q controls for theamount of regularization, and ensures that the difference is due to the model preferences of
the respective regularizers. This style of analysis is new, as far as we know, and may be auseful tool for studying the inductive biases of other algorithms and in other settings.
Related previous work. Our research builds on the work of Wager et al. (2013), whoanalyzed dropout for random (x, y) pairs where the distribution of y given x comes from amember of the exponential family, and the quality of a model is evaluated using the log-loss.
They pointed out that, in these cases, the dropout criterion can be decomposed into theoriginal loss and a term that does not depend on y, which therefore can be viewed as aregularizer. They then proposed an approximation to this dropout regularizer, discussed
its relationship with other regularizers and training algorithms, and evaluated it experimentally. Baldi and Sadowski (2014) exposed properties of dropout when viewed as an
ensemble method (see also Bachman et al., 2014). Van Erven et al. (2014) showed that
applying dropout for online learning in the experts setting leads to algorithms that adapt
to important properties of the input without requiring doubling or other parameter-tuning
techniques, and Abernethy et al. (2014) analyzed a class of methods including dropout byviewing these methods as smoothers. The impact of dropout on generalization (roughly,
how much dropout restricts the search space of the learner, or, from a bias-variance point ofview, its impact on variance) was studied by Wan et al. (2013) and Wager et al. (2014). The
latter paper considers a variant of dropout compatible with a poisson source, and showsthat under some assumptions this dropout variant converges more quickly to its infinite
sample limit than non-dropout training, and that the Bayes-optimal predictions are preserved under the modified dropout distribution. Our results complement theirs by focusing
on the effect of the original dropout on the algorithm’s bias.
Section 2 defines our notation and characterizes when the dropout criterion has a uniqueminimizer. Section 3 presents many additional properties of the dropout regularizer. Section 4 formally defines when two distributions separate two algorithms or regularizers. Sections 5 and 6 give sources over R2 that separate dropout and L2 ; these exploit the preferenceof dropout for hypotheses that concentrate weight on a single feature. Section 7 provides
plots demonstrating that the same distributions separate dropout from L1 regularization.
Section 8 gives a definition of co-adaptation and shows (using plots) that distributions exploiting dropout’s bias against co-adapted weights can also be used to separate dropout
from L2 and L1 regularization. Sections 9 and 10 give additional separation results using
distributions with many features.

2. Preliminaries
We use w∗ for the optimizer of the dropout criterion, q for the probability that a feature is
dropped out, and p = 1 − q for the probability that a feature is kept throughout the paper.
4

On the Inductive Bias of Dropout

As in the introduction, if X ⊆ Rn and P is a joint distribution over X × {−1, 1}, define
defw∗ (P, q) = argminw E(x,y)∼P,ν (`(yw · (x + ν)))(3)

where νi = bi xi for b1 , ..., bn sampled independently at random from {−1, 1/p − 1} with
Pr(bi = 1/p − 1) = p = 1 − q, and `(z) is the logistic loss function:`(z) = ln(1 + exp(−z)).
For some analyses, an alternative representation of w∗ (P, q) will be easier to work with.
Let r1 , ..., rn be sampled randomly from {0, 1}, independently of (x, y) and one another,with Pr(ri = 1) = p. Defining r x = (x1 r1 , ..., xn rn ), we have the equivalent definitionw∗ (P, q) = p argminw E(x,y)∼P,r (`(yw · (r

x))).

(4)

To see that they are equivalent, note that rE(`(yw · (x + ν))) = E ` yw ·

x



p

= E(`(y(w/p) · (rx))).

Although this paper focuses on the logistic loss, the above definitions can be used for any
loss function `(). Since the dropout criterion is an expectation of `(), we have the following
obvious consequence.
Proposition 1 If loss `(·) is convex, then the dropout criterion is also a convex functionof w.
The remainder of the paper focuses on the logistic loss, `(yw · x) = ln(1 + exp(−yw · x)).
We use v for the optimizer of the L2 regularized criterion:
defv(P, λ) = argminw E(x,y)∼P (`(yw · x)) +λ||w||2 .
2(5)

It is not hard to see that the λ2 ||w||2 term implies that v(P, λ) is always well-defined.
On the other hand, w∗ (P, q) is not always well-defined, as can be seen by considering any
distribution concentrated on a single example. This motivates the following definition.
Definition 2 Let P be a joint distribution with support contained in Rn × {−1, 1}. A
feature i is perfect modulo ties for P if either yxi ≥ 0 for all x in the support of P , oryxi ≤ 0 for all x in the support of P .
Put another way, i is perfect modulo ties if there is a linear classifier that only pays attention
to feature i and is perfect on the part of P where xi is nonzero.
Proposition 3 For all finite domains X ⊆ Rn , all distributions P with support in X, andall q ∈ (0, 1), we have that E(x,y)∼P,r (`(yw · (r x))) has a unique minimum in Rn if andonly if no feature is perfect modulo ties for P .
5Helmbold and Longx = (x1 , . . . , xn )yw = (w1 , . . . , wn )`(yw · x)
P, Q
D
q
p=1−q
λ
ν = (ν1 , . . . , νn )r = (r1 , . . . , rn )w∗ (P, q) and w∗
w~ = w∗ /pv(P, λ) and v
regD,q (w)J, Kg(w), gerP (w)feature vector in Rnlabel in {−1, +1}
weight vector in Rn
loss function, generally the logistic loss: ln(1 + exp(−yw · x))
source distributions over (x, y) pairs, varies by section
marginal distribution over x
feature dropout probability in (0, 1)
probability of keeping a feature
L2 regularization parameter
additive dropout noise, νi ∈ {−xi , xi /p − xi }multiplicative dropout noise, ri ∈ {0, 1}
component-wise product: r x = (r1 x1 , . . . , rn xn )minimizer of dropout criterion: E(`(y w · (x + ν)))minimizer of expected loss E(`(y w · (r x)))
minimizer of L2 -regularized loss
regularization due to dropout
criteria to be optimized, varies by sub-section
gradients of the current criterion
0-1 classification generalization error of sign(w · x)Table 1: Summary of notation used throughout the paper.

Proof: Assume for contradiction that feature i is perfect modulo ties for P and some w~
is the unique minimizer of E(x,y)∼P,r (`(yw · (r x))). Assume w.l.o.g. that yxi ≥ 0 for
all x in the support of P (the case where yxi ≤ 0 is analogous). Increasing wi~ keeps theloss unchanged on examples where xi = 0 and decreases the loss on the other examples
in the support of P , contradicting the assumption that w~ was a unique minimizer of the
expected loss.
Now, suppose then each feature i has both examples where yxi > 0 and examples where
yxi < 0 in the support of P . Since the support of P is finite, there is a positive lower
bound on the probability of any example in the support. With probability p(1 − p)n−1 ,component ri of random vector r is non-zero and the remaining n − 1 components are
all zero. Therefore as wi increases without bound in the positive or negative direction,
E(x,y)∼P,r (`(yw·(r x))) also increases without bound. Since E(x,y)∼P,r (`(y0·(r x))) = ln 2,
there is a value M depending only on distribution P and the dropout probability suchthat minimizing E(x,y)∼P,r (`(yw · (r x))) over w ∈ [−M, M ]n is equivalent to minimizing
E(x,y)∼P,r (`(yw·(r x))) over Rn . Since Pr(x,y) (xi = 0) 6= 1 for all i, {r x : r ∈ {0, 1}n , x ∈X} has full rank and therefore E(x,y)∼P,r (`(yw · (r x))) is strictly convex. Since a strictly
convex function defined on a compact set has a unique minimum, E(x,y)∼P,r (`(yw · (r x)))has a unique minimum on [−M, M ]n , and therefore on Rn .
See Table 1 for a summary of the notation used in the paper.
6

On the Inductive Bias of Dropout

3. Properties of the Dropout Regularizer
We start by rederiving the regularization function corresponding to dropout training previously presented in Wager et al. (2013), specialized to our context and using our notation.
The first step is to write `(yw · x) in an alternative way that exposes some symmetries:`(yw · x) = ln(1 + exp(−yw · x))
exp(y(w · x)/2) + exp(−y(w · x)/2)= ln
exp(y(w · x)/2)

exp((w · x)/2) + exp(−(w · x)/2)= ln.
exp(y(w · x)/2)(6)This then implies
regD,q (w)= E(`(yw · (x + ν))) − E(`(yw · x)) 
exp(y(w · x)/2)
exp((w · (x + ν))/2) + exp(−(w · (x + ν))/2)
×= E lnexp(y(w · (x + ν))/2)
exp((w · x)/2) + exp(−(w · x)/2)
exp((w · (x+ν))/2)+exp(−(w · (x+ν))/2)= E ln− y(w · ν)/2 .
exp((w · x)/2)+exp(−(w · x)/2)

Since E(ν) = 0, we get the following.
Proposition 4 (Wager et al., 2013)
regD,q (w) = E ln

exp(w · (x + ν)/2) + exp(−w · (x + ν)/2)
exp((w · x)/2) + exp(−(w · x)/2)


.

(7)

Using a Taylor expansion, Wager et al. (2013) arrived at the following approximation:


X
q
x2i
2
wi Ex
.
(8)
w·x
2(1 − q)
(1 + exp(− w·x2 ))(1 + exp( 2 )iThis approximation suggests two properties: the strength of the regularization penalty
decreases exponentially in the prediction confidence |w · x|, and that the regularization
penalty goes to infinity as the dropout probability q goes to 1. However, w · ν can bequite large, making a second-order Taylor expansion inaccurate.1 In fact, the analysis in
this section suggests that the regularization penalty does not decrease with the confidence
and that the regularization penalty increases linearly with q = 1 − p (Figure 1, Theorem 8,
Proposition 9).
The following propositions show that regD,q (w) satisfies at least some of the intuitive
properties of a regularizer.
Proposition 5 regD,q (0) = 0.
Proposition 6 (Wager et al., 2013) The contribution of each x to the dropout regularization penalty (7) is non-negative: for all x, exp((w · (x + ν))/2)+exp(−(w · (x + ν))/2)
Eν ln
≥ 0.
exp((w · x)/2) + exp(−(w · x)/2)
1. Wager et al. (2013) experimentally evaluated the accuracy of a related approximation in the case that,instead of using dropout, ν was distributed according to a zero-mean gaussian.

7Helmbold and Long

Proof: The proposition follows from Jensen’s Inequality.
The w∗ (P, q) vector learned by dropout training minimizes
E(x,y)∼P (`(yw · x)) + regD,q (w).
However, the 0 vector has `(y0 · x) = ln(2) and regD,q (0) = 0, implying:
Proposition 7 regD,q (w∗ ) ≤ ln(2).
Thus any regularization penalty greater than ln(2) is effectively equivalent to a regularization penalty of ∞.
We now present new results based on analyzing the exact regD,q (w). The next properties show that the dropout regularizer is emphatically not like other convex or norm-based
regularization penalties in that the dropout regularization penalty always remains bounded
when a single component of the weight vector goes to infinity (see also Figure 1).
Theorem 8 For all dropout probabilities 1 − p ∈ (0, 1), all n, all marginal distributions D
over n-feature vectors, and all indices 1 ≤ i ≤ n,
sup regD,q (0, . . . , 0, wi , 0, . . . , 0) ≤ PrD (xi 6= 0)(1 − p) ln(2) < ln 2.
| {z }| {z }wi
i−1n−i

Proof: Fix arbitrary n, p, i, and D. We have
regD,q (0, . . . , 0, wi , 0, . . . , 0)
| {z }| {z }
i−1

n−i

 

exp(−wi (xi +νi )/2)+exp(wi (xi +νi )/2)
= Ex,ν ln.
exp(−wi xi /2)+exp(wi xi /2)

Fix an arbitrary x in the support of D and examine the expectation over ν for that x.
Recall that xi + νi is 0 with probability 1 − p and is xi /p with probability p, and we will
use the substitution z = |wi xi |/2.
!!
exp( −wi (x2i +νi ) ) + exp( wi (x2i +νi ) )
Eν ln
(9)
exp( −w2i xi ) + exp( wi2xi )z−z) − ln (exp(z) + exp(−z)) .
(10)= (1 − p) ln(2) + p ln exp( ) + exp(pp
We now consider cases based on whether or not z is 0. When z = 0 (so either wi or xi is 0)
then (10) is also 0.
If z 6= 0 then consider the derivative of (10) w.r.t. z, which is
exp(z/p) − exp(−z/p) exp(z) − exp(−z)−.
exp(z/p) + exp(−z/p) exp(z) + exp(−z)
This derivative is positive since z > 0 and 0 < p < 1. Therefore (10) is bounded by its limit
as z → ∞, which is (1 − p) ln(2), in this case.
Since (9) is 0 when xi = 0 and is bounded by (1 − p) ln(2) otherwise, the expectation
over x of (9) is bounded PrD (xi 6= 0)(1 − p) ln(2), completing the proof.
Since line (10) is derived using a chain of equalities, the same proof ideas can be used
to show that Theorem 8 is tight.
8

On the Inductive Bias of Dropout

Figure 1: The p = 1/2 dropout regularization for x = (1, 1) as a function of wi when theother weights are 0 together with its approximation (8) (left) and as a functionof w1 for different values of the second weight (right).

Proposition 9 Under the conditions of Theorem 8,
lim regD,q (0, . . . , 0, wi , 0, . . . , 0) = PrD (xi 6= 0)(1 − p) ln(2).
| {z }| {z }

wi →∞

i−1

n−i

Note that this bound on the regularization penalty depends neither on the range nor
expectation of xi . In particular, it has a far different character than the approximation of
Equation (8).
In Theorem 8 the other weights are fixed at 0 as wi goes to infinity. An additional
assumption implies that the regularization penalty remains bounded even when the othercomponents are non-zero. Let w be a weight
P vector such that for all x in the support of
D and dropout
Pnoise vectors ν we have | j6=i wj (xj + νj )| ≤ M for some bound M (thisimplies that | j6=i wj xj | ≤ M also). Then!!
w·(x+ν)exp( w·(x+ν))+exp(−)
2
2
regD,q (w) = Ex,νw·xexp( w·x)+exp(−
2
2 )!!
exp( M −wi2(xi+νi ) +exp( M +wi2(xi+νi ) )≤ Exi ,νi log
i xi
i xi
exp(− M −w
+exp(− M +w)
22!!
exp(− wi x2i+νi )+exp( wi (x2i+νi ) )≤ M +Exi ,νi log.
(11)exp( −w2i xi )+exp( wi2xi )Using (11) instead of the first line in Theorem 8’s proof gives the following.
Proposition
10 Under the conditions of Theorem 8, if the weight vector w has the property
P
that | j6=i wj (xj + νj )| ≤ M for each x in the support of D and all of its corresponding
dropout noise vectors ν then
sup regD,q (w1 , w2 , . . . , wi−1 , ω, wi+1 , . . . , wn ) ≤ M + PrD (xi 6= 0)(1 − p) ln(2).
ω9Helmbold and Long

Proposition 10 shows that the regularization penalty starting from a non-zero initial weightvector remains bounded as any one of its components goes to infinity. On the other hand,unless M is small, the bound will be larger than the dropout criterion for the zero vector.
This is a natural consequence as the starting weight vector w could already have a large
regularization penalty.
The derivative of (10) in the proof of Theorem 8 implies that the dropout regularization
penalty is monotonic in |wi | when the other weights are zero. Surprisingly, this is does
not hold in general. The dropout regularization penalty due to a single example (as in
Proposition 6) can be written as −w·(x+ν)−w·x
Eν ln exp( w·(x+ν)
)
+
exp(
)
− ln exp( w·x222 ) + exp( 2 ) .
Therefore if increasing a weight makes the second logarithm increase faster than the expectation of the first, then the regularization penalty decreases even as the weight increases.
This happens when the wi xi products tend to have the same sign. The regularization
penalty as a function of w1 for the single example x = (1, 1), p = 1/2, and w2 set to various
values is plotted in Figure 1.2 This gives us the following.
Proposition 11 Unlike p-norm regularizers, the dropout regularization penalty regD,q (w)is not always monotonic in the individual weights.
In fact, the dropout regularization penalty can decrease as weights move up from 0.
Proposition 12 Fix p = 1/2, w2 > 0, and an arbitrary x ∈ (0, ∞)2 . Let D be the
distribution concentrated on x. Then regD,q (w1 , w2 ) locally decreases as w1 increases from
0.
Proposition 12 is proved in Appendix A.
We now turn to the dropout regularization’s behavior when two weights vary together.
If any features are always zero then their weights can go to ±∞ without affecting either thepredictions or regD,q (w). Two linearly dependent features might as well be one feature.
After ruling out degeneracies like these, we arrive at the following theorem, which is provedin Appendix B.
Theorem 13 Fix an arbitrary distribution D with support in R2 , weight vector w ∈ R2 ,and non-dropout probability p. If there is an x with positive probability under D such thatw1 x1 and w2 x2 are both non-zero and have different signs, then the regularization penalty
regD,q (ωw) goes to infinity as ω goes to ±∞.
The theorem can be straightforwardly generalized to the case n > 2; except in degenerate cases, sending two weights to infinity together will lead to a regularization penalty
approaching infinity.
Theorem 13 immediately leads to the following corollary.
2. Setting x = (1, 1) is in some sense without loss of generality as the prediction and dropout regularization
values for any w, x pair are identical to the values for w̃, 1 when each w̃i = wi xi .

10

On the Inductive Bias of Dropout

Corollary 14 For a distribution D with support in R2 , if there is an x with positive probability under D such that x1 6= 0 and x2 6= 0, then there is a w such that for any q ∈ (0, 1),
the regularization penalty regD,q (ωw) goes to infinity with ω.
For any w ∈ R2 with both components nonzero, there is a distribution D over R2 withbounded support such that the regularization penalty regD,q (ωw) goes to infinity with ω.
Together Theorems 8 and 13 demonstrate that regD,q (w) is not convex (see also Figure 1). In fact, regD,q (w) cannot be approximated to within any factor by a convex function,even if a dependence on n and p is allowed. For example, Theorem 8 shows that, for all
D with bounded support, both regD,q (0, ω) and regD,q (ω, 0) remain bounded as ω goes toinfinity, whereas Theorem 13 shows that there is such a D such that regD,q (ω/2, ω/2) is
unbounded as ω goes to infinity.
Theorem 13 relies on the wi xi products having different signs. The following showsthat regD,q (w) does remain bounded when multiple components of w go to infinity if thecorresponding features are compatible in the sense that the signs of wi xi are always inalignment.
Theorem 15 Let w be a weight vector and D be a discrete distribution such that wi xi ≥ 0
for each index i and all x in the support of D. The limit of regD,q (ωw) as ω goes to infinity
is bounded by ln(2)(1 − p)Px∼D (w · x 6= 0).
The proof of Theorem 15 (which is Appendix C) easily generalizes to alternative conditions where ω → −∞ and/or wi xi ≤ 0 for each i ≤ k and x in the support of D.
Taken together Theorems 15 and 13 give an almost complete characterization of when
multiple weights can go to infinity while maintaining a finite dropout regularization penalty.
3.1 Discussion
The bounds in the preceding theorems and propositions suggest several properties of thedropout regularizer. First, the 1 − p factors indicate that the strength of regularization
grows linearly with dropout probability q = 1 − p. Second, the Px∼D (xi 6= 0) factors
in several of the bounds suggest that weights for rare features are encouraged by being
penalized less strongly than weights for frequent features. This preference for rare features
is sometimes seen in algorithms like the Second-Order Perceptron (Cesa-Bianchi et al.,2002) and AdaGrad (Duchi et al., 2011). Wager et al. (2013) discussed the relationshipbetween dropout and these algorithms, based on approximation (8). Empirical results
indicate that dropout performs well in domains like document classification where rarefeatures can have high discriminative value (Wang and Manning, 2013). The theoremsof this section suggest that the exact dropout regularizer minimally penalizes the use ofrare features. Finally, Theorem 13 suggests that dropout limits co-adaptation by strongly
penalizing large weights if the wi xi products often have different signs. On the other hand,
if the wi xi products usually have the same sign, then Proposition 12 indicates that dropout
encourages increasing the smaller weights to help share the prediction responsibility. Thisintuition is reinforced by Figure 1, where the dropout penalty for two large weights is muchless then a single large weight when the features are highly correlated.
11

Helmbold and Long

4. A Definition of Separation
Now we turn to illustrating the inductive bias of dropout by contrasting it with L2 regularization. For this, we will use a definition of separation between pairs of regularizers.
Each regularizer has a regularization parameter that governs how strongly it regularizes.
If we want to describe qualitatively what is preferred by one regularizer over another, weneed to control for the amount of regularization.
Let erP (w) = Pr(x,y)∼P (sign(w · x) 6= y), and recall that w∗ and v are the minimizersof the dropout and L2 -regularized criteria respectively.
Say that sources P and Q C-separate L2 and dropout if there exist q and λ such that botherQ (v(Q,λ))erP (w∗ (P,q))erP (v(P,λ)) > C and erQ (w∗ (Q,q)) > C. Say that indexed families P = {Pα } and Q = {Qα }strongly separate L2 and dropout if pairs of distributions in the family C-separate them forarbitrarily large C. We provide strong separations, using both n = 2 and larger n.

5. A Source Preferred by L2
Consider the joint distribution P5 defined as follows3 :x1 x2 y Pr(x, y)
10 −1 11/3
1.1 −1 1
1/3−1 1.1 1
1/3(12)This distribution has weight vectors that classify examples perfectly (the green shaded
region in Figure 2). For this distribution, optimizing an L2 -regularized criterion leads
to a perfect hypothesis4 , while the weight vectors optimizing the dropout criterion makeprediction errors on one-third of the distribution.
The intuition behind this behavior for the distribution described in (12) is that weightvectors that are positive multiples of (1, 1) classify all of the data correctly. However,with dropout regularization the (10, −1) and (1.1, −1) data points encourage the second
weight to be negative when the first component is dropped out. This negative push on
the second weight is strong enough to prevent the minimizer of the dropout-regularized
criterion from correctly classifying the (−1, 1.1) data point. Figure 2 illustrates the loss,
dropout regularization, and dropout and L2 criterion for this data source.5
3. Although several of our sources have all positive instances, that is not essential for the construction.
The probability on each (x, y) example can be split evenly between the original (x, y) and its negativelylabeled counterpart (−x, −y). Note that for any w, both (x, y) and its counterpart (−x, −y) make thesame contribution to both the loss and dropout regularization. After splitting all of the examples, bothlabels will be equally represented in the distribution. Furthermore, with such paired examples, convexity
implies that the weight on any non-dropped out bias input will be 0 when the criterion is minimized.
4. Having the labels of this distribution be consistent with a linear threshold function eases discussion, but
is not essential. Adding a fourth inconsistent point with sufficiently small probability would preserve theproperty that the L2 -regularized criterion leads to a minimum error linear threshold hypothesis while
the error of dropout’s hypothesis is significantly larger.
5. The contours in this and the subsequent figures are not evenly spaced, but chosen to emphasize interesting
aspects of the surfaces while minimizing clutter.

12

On the Inductive Bias of Dropout

Figure 2: Using data favoring L2 in (12). The expected loss is plotted in the upper-left, thedropout regularizer in the upper-right, the L2 regularized criterion as in (5) in thelower-left and the dropout criterion as in (3) in the lower-right, all as functionsof the weight vector. The Bayes-optimal weight vectors are in the green region,and “×” marks show the optimizers of the criteria.

13Helmbold and Long

We first show that distribution P5 of (12) is compatible with mild enough L2 regularization. Recall that v(P5 , λ) is weight vector found by minimizing the L2 regularized
criterion (5).
Theorem 16 If 0 < λ ≤ 1/50, then erP5 (v(P5 , λ)) = 0 for the distribution P5 definedin (12).
In contrast, the w∗ (P5 , q) minimizing the dropout criterion (3) has error rate at least
1/3.
Theorem 17 If q ≥ 1/3 then erP5 (w∗ (P5 , q)) ≥ 1/3 for the distribution P5 defined in (12).
The proofs of Theorem 16 and 17 are in Appendices D and E.

6. A Source Preferred by Dropout
In this section, consider the joint distribution P6 defined by
x1
x2
1
0
−1/1000 1
1/10−1y Pr(x, y)
1
3/7
1
3/7
1
1/7

(13)

The intuition behind this distribution is that the (1, 0) data point encourages a large weighton the first feature. This means that the negative pressure on the second weight due tothe (1/10, −1) data point is much smaller (especially given its lower probability) than thepositive pressure on the second weight due to the (−1/1000, 1) example. The L2 regularized
criterion emphasizes short vectors, and prevents the first weight from growing large enough(relative to the second weight) to correctly classify the (1/10, −1) data point. On the other
hand, the first feature is nearly perfect; it only has the wrong sign on the second example
where it is − = −1/1000. This means that, in light of Theorem 8 and Proposition 10,
dropout will be much more willing to use a large weight for x1 , giving it an advantage forthis source over L2 . The plots in Figure 3 illustrate this intuition.
Theorem 18 If 1/100 ≤ λ ≤ 1, then erP6 (v(P6 , λ)) ≥ 1/7 for the distribution P6 definedin (13).
In contrast, the minimizer of the dropout criterion is able to generalize perfectly.
Theorem 19 If q ≤ 1/2, then erP6 (w∗ (P6 , q)) = 0. for the distribution P6 defined in (13).
Theorems 18 and 19 are proved in Appendices F and G.
The results in this and the previous section show that the distributions defined in (12)and (13) strongly separate dropout and L2 regularization. Theorem 19 shows that for
distribution P analyzed in this section erP (w∗ (P, q)) = 0 for all q ≤ 1/2 while Theorem 18shows that for the same distribution erP (v(P, λ) ≥ 1/7 whenever λ ≥ 1/100. In contrast,
when Q is the distribution defined in the previous section, Theorem 16 shows erQ (v(Q, λ)) =0 whenever λ ≤ 1/50. For this same distribution Q, Theorem 17 shows that erQ (w∗ (Q, q)) ≥1/3 whenever q ≥ 1/3.
14

On the Inductive Bias of Dropout

Figure 3: For the source from (13) favoring the dropout, the expected loss is plotted in theupper-left, the dropout regularizer in the upper-right, the expected loss plus L2
regularization as in (5) in the lower-left and the dropout criterion as in (3) inthe lower-right, all as functions of the weight vector. The Bayes-optimal weightvectors are in the green region, and “×” marks show the optimizers of the criteria.
Note that the minimizer of the dropout criterion lies outside the middle-right plot
and is shown on the bottom plot (which has a different range and scale than theothers.)15

Helmbold and Long

Figure 4: A plot of the L1 criterion with λ = 0.01 for distributions P5 defined in Section 5(left) and P6 defined in Section 6 (right). As before, the Bayes optimal classifiers
are denoted by the region shaded in green and the minimizer of the criterion isdenoted with an x.

7. L1 Regularization
In this section, we show that the same P5 and P6 distributions that separate dropout fromL2 regularization also separate dropout from L1 regularization: the algorithm the minimizes
E(x,y)∼P (`(yw · x)) + λ||w||1 .

(14)

As in Sections 5 and 6, we set λ = 1/100. Figure 4 plots the L1 criterion (14) for the
distributions P5 defined in (12) and P6 defined in (13). Like L2 regularization, L1 regularization produces a Bayes-optimal classifier on P5 , but not on P6 . Therefore the same argumentshows that these distributions also strongly separate dropout and L1 regularization.

8. Dropout and Co-adaptation
Hinton et al. (2012) and Srivastava et al. (2014) give evidence that dropout helps preventthe co-adaptation of units in neural networks, encouraging individual units to learn simpler
functions of their inputs. In this section we provide a definition of co-adaptation andillustrate how dropout training can restrict the co-adaptation of weights.
We say that two weights wi and wj are co-adapted in a weight vector w if either alone
increases the loss, but both together decrease the loss. More formally, let “w \ i” denote
vector w modified by replacing wi with 0, and “w \ i, j” denote the resulting vector whenboth wi and wj are replaced by 0. If all of:
1. The loss of w is less than the loss of w \ i, j,
2. The loss of w \ i, j is less than the loss of w \ i, and16

On the Inductive Bias of Dropout

3. The loss of w \ i, j is less than the loss of w \ j,then we say that weights wi and wj are co-adapted in w.
For example, consider the case when features x1 and x2 tend to have the same sign, but
x1 is usually a little bigger than x2 when the label is +, and x2 tends to be larger when thelabel is −. Then the difference x1 −x2 usually has the same sign as the label, and making w1
large and w2 negative with a similar-magnitude is likely to decrease the loss. This is similar
to constructing the new good feature x1 − x2 and giving it large weight. However, if neither
feature x1 nor feature x2 is strongly correlated with the label, then using a large magnitude
weight on just x1 or just x2 is likely to result in many badly misclassified examples, andgreater loss than if w1 and w2 were both set to zero. (Note that similar co-adaptation
situations arise when x1 and x2 have different signs, but their sum tends to have the same
sign, or tends to have the opposite sign, as the label.)
Theorem 13 shows that the dropout regularization penalty goes to infinity as the
opposite-signed weights given to x1 and x2 in the situation described. Furthermore, thedropout penalty for weight vector w includes terms for the loss of w \ i and w \ j, so ifthese grow too large, then w cannot be the minimizer of the dropout criterion. This suggests that dropout training minimizes co-adaptation. The following example gives a more
concrete illustration of this behavior.
Consider the joint distribution P8 defined as follows:x1x2
y Pr(x, y)
10
9
1
0.64
9
10
−1
0.32
1.0
−0.35 1
0.03
−0.35
1.0
−1
0.01

(15)

The loss and dropout regularization for P8 are plotted in Figure 5. To obtain small loss,
the hypothesis must give weights a similar large magnitude with w1 positive while w2 isnegative. On the other hand, almost all of the probability is on the first two examples, andgiving the weights different signs satisfies the conditions of Theorem 13 for them, and thedropout penalty quickly increases. The low probability points will also make the dropout
regularization for weight vectors w = (a, a) go to infinity as a goes to infinity, but the small
probabilities keeps the penalty small until a becomes very large (e.g. for w = (30, 30), thepenalty is still less than 0.4). Omitting these points has a nearly indistinguishable effect on
the first plots: their presence, as well as the different probabilities for the points, will be
more important later, when we introduce the alternative labeling P80 .
The “checkerboard” pattern of the regularization in Figure 5 shows that common patterns in the data can strongly shape the dropout regularizer, making it discriminate against
certain directions. In Figure 6 we plot the L1 , L2 , and dropout regularized criteria forsource P8 , illustrating that the dropout regularizer forces the weight vector away from theBayes optimal region. In fact, the regularization is so strong that both weights are positiveat the minimizer of the dropout criterion.
We can verify that the minimizing v ≈ (2.8, −2.75) for the L2 criterion exhibits coadaptation. The loss of v is about 0.06, the loss of v \ 1 ≈ 15, the loss of w \ 2 ≈ 8, and theloss of v \ 1, 2 = ln 2 ≈ 0.69. The co-adaptation is even more dramatic for the L1 criterion.
17

Helmbold and Long

Figure 5: Plots of the loss and p = 1/2 dropout regularization for distribution P8 . Notethat the regularization penalty increases quickly when the weights have opposite
signs, but much more slowly when they have the same sign. In the loss plot, thegreen region indicates the Bayes optimal classifiers.

On the other hand, the weight vector w∗ ≈ (0.035, 0.014) minimizing the dropout criterion
is not co-adapted. The losses of w∗ \ 1 and w∗ \ 2 are both greater than the loss of w∗ , butboth are also less than the loss of w∗ \ 1, 2.
Although minimizing the dropout criterion fails to yield a Bayes optimal weight vector
for P8 , the situation reverses when we consider the modified distribution P80 with the samefeature vectors and probabilities as P8 , but with all all labels set to 1. When all the labels
are positive, the heavier points on the right pull the weight vector in that direction. If it ispulled far enough, then the (-0.3, 1) point will be misclassified.
Since the dropout regularization penalty depends only on the instance probabilities andnot on the labels, P8 and P80 have the same regularization penalty function. The differenceis that P80 with its modified labels has low loss when both weights are large, a situationcompatible with the dropout regularization. See Figure 7 for plots of the loss and various
criteria for the modified P80 source.
The plots in Figures 6 and 7 show that distributions P8 and P80 also strongly separate
dropout from both L2 and L1 regularization. Since the two distributions have the same
marginal distribution over feature vectors (and thus use the same dropout regularization
penalty function), they provide vivid evidence of how dropout shapes the landscape, encouraging some directions while heavily penalizing others.

9. A High-Dimensional Source Preferred by L2
In this section we exhibit a source where L2 regularization leads to a perfect predictor while
dropout regularization creates a predictor with a constant error rate.
18

On the Inductive Bias of Dropout

Figure 6: Plots of the criteria and their minimizers for the source P8 . The L2 and L1 criteriawith λ = 1/100 are plotted on the right, and the p = 1/2 dropout criterion at thesame scale and “zoomed in” are shown on the left. As before, the green region
indicates the Bayes optimal classifiers.

19Helmbold and Long

Figure 7: Plots of the loss and various criteria and minimizers for the source P80 , the modification of P8 where all the labels are set to 1. As before, p = 1/2 for dropout,
λ = 1/100 for the other regularizers, and the green region indicates the Bayes
optimal classifiers.

20

On the Inductive Bias of Dropout

Consider the source P9 defined as follows. The number n of features is even. All examples
are labeled 1. A random example is drawn as follows: the first feature takes the value 1
with probability 9/10 and −1 otherwise, and a subset of exactly n/2 of the remaining n − 1features (chosen uniformly at random) takes the value 1, and the remaining n/2 − 1 of those
first n − 1 features take the value −1.
A majority vote over the last n − 1 features achieves perfect prediction accuracy. Thisis despite the first feature (which does not participate in the vote) being more strongly
correlated with the label than any of the voters in the optimal ensemble. Dropout, withits bias for single good features and discrimination against multiple disagreeing features,
puts too much weight on this first feature. In contrast, L2 regularization leads to the Bayes
optimal classifier by placing less weight on the first feature than on any of the others.
1
Theorem 20 If λ ≤ 30n
then the weight vector v(P9 , λ) optimizing the L2 criterion has
perfect prediction accuracy: erP9 (v(P9 , λ)) = 0.

When n > 125, dropout with q = 1/2 fails to find the Bayes optimal hypothesis. In
particular, we have the following theorem.
Theorem 21 If the dropout probability q = 1/2 and the number of features is an evenn > 125 then the weight vector w∗ (P9 , q) optimizing the dropout criterion has prediction
error rate erP9 (w∗ (P9 , q)) ≥ 1/10.
We conjecture that dropout fails on P9 for all n ≥ 4. As evidence, we analyze the n = 4
case.
Theorem 22 If dropout probability q = 1/2 and the number of features is n = 4 then theminimizer of the dropout criteria w∗ (P9 , q) has has prediction error rate erP9 (w∗ (P9 , q)) ≥1/10.
Theorems 20, 21 and 22 are proved in Appendices H, I and J.

10. A High-Dimensional Source Preferred by Dropout
Define the source P10 , which depends on (small) positive real parameters η, α, and β,
as follows. A random label y is generated first, with both of +1 and −1 equally likely.
The features x1 , ..., xn are conditionally independent given y. The first feature tends tobe accurate but small: x1 = αy with probability 1 − η, and is −αy with probability η.
The remaining features are larger but less accurate: for 2 ≤ i ≤ n, feature xi is y withprobability 1/2 + β, and −y otherwise.
When η is small enough relative to β, the Bayes’ optimal prediction is to predict with thefirst feature. When α is small, this requires concentrating the weight on w1 to outvote theother features. Dropout is capable of making this one weight large while L2 regularization
is not.
√1 √, thenTheorem 23 If q = 1/2, n ≥ 100, α > 0, β = 1/(10 n − 1), and η ≤ 2+exp(54n)∗
erP10 (w (P10 , q)) = η.
21Helmbold and Long√
1
Theorem 24 If β = 1/(10 n − 1), λ = 30n, α < βλ, and n is a large enough even number,then for any η ∈ [0, 1], erP10 (v(P10 , λ)) ≥ 3/10.
Theorems 23 and 24 are proved in Appendices K and L.
Let ñ be a large enough even number in the sense of Theorem 24. Let Pη be the√ distribution defined at the start of Section 10 with number of features n = ñ, β = 1/(10 n − 1),√√
α = 1/(300n n), and 0 < η < 1/(2 + exp(54 n)) is a free parameter. Theorem 23 showsthat erPη (w∗ (Pη , q)) = η when dropout probability q = 1/2. For this same distribution,
Theorem 24 shows erPη (v(Pη , λ)) ≥ 3/10 when λ = 1/30n. Therefore
erPη (w∗ (Pη , 1/2))
erPη (v(P, 1/30ñ))
goes to 0 as η → 0.
The distribution defined at the start of Section 9, which we call Q here, provides contrasting behavior when n = ñ. Theorem 21 shows that the error erQ (w∗ (Q, 1/2)) ≥ 1/10
while Theorem 20 shows that erQ (v(Q, 1/30ñ) = 0. Therefore the Pη and Q distributions
strongly separate dropout and L2 regularization for parameters q = 1/2 and λ = 1/30n.

11. Conclusions
We have built on the interpretation of dropout as a regularizer in Wager et al. (2013) to proveseveral interesting properties of the dropout regularizer. This interpretation decomposes thedropout criterion minimized by training into a loss term plus a regularization penalty that
depends on the feature vectors in the training set (but not the labels). We started witha characterization of when the dropout criterion has a unique minimum, and then turn toproperties of the dropout regularization penalty. We verified that the dropout regularization
penalty has some desirable properties of a regularizer: it is 0 at the zero vector, and thecontribution of each feature vector in the training set is non-negative.
On the other hand, the dropout regularization penalty does not behave like standard
regularizers. In particular, we have shown:
1. Although the dropout “loss plus regularization penalty” criterion is convex in theweights w, the regularization penalty imposed by dropout training is not convex.
2. Starting from an arbitrary weight vector, any single weight can go to infinity while
the dropout regularization penalty remains bounded.
3. In some cases, multiple weights can simultaneously go to infinity while the regularization penalty remains bounded.
4. The regularization penalty can decrease as weights increase from 0 when the features
are correlated.
These are in stark contrast to standard norm-based regularizers that always diverge as any
weight goes to infinity, and are non-decreasing in each individual weight.
22

On the Inductive Bias of Dropout

In most cases the dropout regularization penalty does diverge as multiple weights go toinfinity. We characterize when sending two weights to infinity causes the dropout regularization penalty to diverge, and when it will remain finite. In particular, dropout is willingto put a large weights on multiple features if the wi xi products tend to have the same sign.
The form of our analytical bounds suggest that the strength of the regularizer grows
linearly with the dropout probability q, and provide additional support for the claim (Wager
et al., 2013) that dropout favors rare features.
We found it important to check our intuition by working through small examples. To
make this more rigorous we needed a definition of when a source favored dropout regularization over a more standard regularizer like L2 . Such a definition needs to deal with thestrength of regularization, a difficulty complicated by the fact that dropout regularization isparameterized by the dropout probability q ∈ [0, 1] while L2 regularization is parameterizedby λ ∈ [0, ∞]. Our solution is to consider pairs of sources P and Q. We then say the pair
separates the dropout and L2 if dropout with a particular parameter q performs better thenL2 with a particular parameter λ on source P , while L2 (with the same λ) performs better
than dropout (with the same q) on source Q. Our definition uses generalization error as
the most natural interpretation of “performs better”.
Sections 5 through 10 are devoted to proving that dropout and L2 are strongly separated
by certain pairs of distributions. Section 7 shows that dropout and L1 regularization are
also strongly separated, and Section 8 describes a separation illustrating dropout’s bias
against co-adaptation of weights. Proving strong separation is non-trivial even after one
finds the right distributions. This is due to several factors: the minimizers of the criteria do
not have closed forms, we wish to prove separation for ranges of the regularization values,
and the binomial distributions induced by dropout are not amenable to exact analysis.
Despite these difficulties, the separation results reinforce the intuition that dropout is more
willing to use a large weight in order to better fit the training data than L2 regularization.
However, if two features often have both the same and different signs (as in Theorem 13)
then dropout is less willing to put even moderate weight on both features.
As a side benefit of these analyses, the plots in Figure 2 and Figure 3 provide a dramatic
illustration of the dropout regularizer’s non-convexity and its preference for making onlya single weight large, and the checkerboard pattern of the dropout regularizer in Figure 5
illustrates its bias against co-adaptation of weights. This is consistent with the insightprovided by Theorems 13 and 15.
Some feature transformations appear to have substantially different effects on dropout
and L2 . For example, suppose we replace a boolean feature xi with a batch of features
xi,1 , ..., xi,k , and,• when xi = 0, we set xi,1 = ... = xi,k = 0 and• when xi = 1, we set xi,j 0 = 1 for j 0 chosen uniformly at random from {1, ..., k}, andxi,j = 0 for j 6= j 0 .
We can think of xi,1 , ..., xi,k as a “partition” of xi . This kind of transformation can arise in
document classification when words have alternate spellings, or a single feature representing a set of synonyms is split into features for the individual words (assuming that eachdocument uses only one of the synonyms).
23Helmbold and Long

The inductive bias of dropout is apparently not affected by such feature partitioning.
For any weight vector w on the original features, the modified weight vector which copies wi
for each feature in the partition of xi makes the same predictions and has the same dropout
regularization penalty. On the other hand, the L2 regularization penalty increases. If analgorithm creates k copies of the weight wi to have the same behavior on the modified data,
this increases the penalty arising from this feature by a factor of k, providing an incentive
for the algorithm to use other features instead.
Dropout’s relative affinity with partitioned features could be another basis of separation
with L2 . It suggests that dropout might be able to more effectively exploit rare primitive
features, while L2 regularization benefits from having more frequent higher-level features.
This is a potential subject for future research.
Now suppose that, instead of partitioning xi , we set xi,1 , ..., xi,k to be k copies of xi .
In this case, an L2 -regularized algorithm could split weight wi into k parts, putting weight
wi /k on each copy of xi . This will classify the transformed data the same way as theoriginalPdata while reducing the L2 regularization cost of using the feature by a factor of k(since j (wi /k)2 = (1/k)wi2 ). Although such feature cloning can also reduce the dropout
regularization penalty (see Figure 1 and Proposition 12), we conjecture that the reduction
is at most an additive constant.
If this conjecture were true, then L2 -regularized algorithms make heavier use of duplicated features than dropout-regularized algorithms. This in turn suggest that dropout
confers resistance to paying undue attention to groups of mostly redundant features. Thispossibility is another potential subject for future research.
The aim of our analysis has been to aid general understanding of what kinds of problems are well-suited to dropout. A more authoritative idea of whether dropout confers anadvantage in a particular case can be gained experimentally.
Linear classifiers are often learned with a bias term, creating a classifier of the formsign(w · x − b). Here the bias b is also learned, but not regularized. We have focused on
the case b = 0 to keep the analysis simple, and our constructions can be easily modified sothat the optimal bias is 0 (see footnote 3). The effect of a non-zero bias term on the generalproperties in Section 3 can be more subtle, and is a potential subject for future research.
Our analysis is for the logistic regression case corresponding to a single output node. It
would be very interesting to have similar analysis for multi-layer neural networks. However,dealing with non-convex loss of such networks will be a major challenge. Another open
problem suggested by this work is how the definition of separation can be used to gain
insight about other regularizers and settings.

Acknowledgments
We thank the reviewers for their thoughtful comments and corrections.
24

On the Inductive Bias of Dropout

Appendix A. Proof of Proposition 12
Proposition 12. Fix p = 1/2, w2 > 0, and an arbitrary x ∈ (0, ∞)2 . Let D
be the distribution concentrated on x. Then regD,q (w1 , w2 ) locally decreases as
w1 increases from 0.
First, we show that assuming x = (2, 2) is without loss of generality. When D concentrates
all of its probability on a single x, let us denote regD,1/2 by regx,1/2 . Since anyplace w1
appears in the expression for regx,1/2 , it is multiplied by x1 , if we multiply w1 by someconstant c and divide x1 by c, we do not change w1 x1 , and therefore do not change regx,1/2 .
The same holds for w2 . Thusregx,1/2 (w) = reg(2,2),1/2 (w1 x1 /2, w2 x2 /2).
If we change variables and let w̃1 = w1 x1 /2 and w̃2 = w2 x2 /2, then since x1 and x2 are both
positive, w̃2 is positive iff w2 is, and regx,1/2 (w) is increasing with w1 iff reg(2,2),1/2 (w̃) is
increasing with w̃1 .
We continue assuming x = (2, 2). It suffices to show ∂regD,q (w1 , w2 )/∂w1 |w1 =0 < 0.
This derivative is
3ew2 + e−3w2 − 3e−w2 − e3w2.
(16)2(ew2 + e−w2 )(e2w2 + e−2w2 )The sign depends only on the numerator, which is 0 when w2 = 0. The derivative of thenumerator with respect to w2 is 3ew2 − 3e−3w2 + 3e−w2 − 3e3w2 , which is negative for w2 > 0,
since ez + e−z is an increasing function in z. Thus the numerator in (16) is decreasing in
w2 . Therefore (16) is negative when w2 > 0, and the regularization penalty is (locally)
decreasing as w1 increases from 0.
(Note: Proposition 12 may be generalized with slight modifications to apply wheneverx has two nonzero components. What is needed is that x1 w1 and x2 w2 have the same sign.
For example, if x1 is negative but x2 w2 is positive, then moving w1 from 0 in the negative
direction decreases regD,q (w).)

Appendix B. Proof of Theorem 13
Theorem 13. Fix an arbitrary distribution D with support in R2 , weight vectorw ∈ R2 , and non-dropout probability p. If there is an x with positive probability
under D such that w1 x1 and w2 x2 are both non-zero and have different signs,
then the regularization penalty regD,q (ωw) goes to infinity as ω goes to ±∞.
Fix an x satisfying the conditions of the theorem.
regD,q (ωw) ≥ D(x)Eνln> D(x)Eνln) + exp( ωw·(x+ν))
exp(− ωw·(x+ν)
2
2
−ωw·x
ωw·x
exp( 2 ) + exp( 2 )!!
exp( |ωw·(x+ν)|)2!!

2 exp( |ωw·x|
2 )|ωw · (x + ν)| |ωw · x|
= D(x)Eν − ln(2) +
−
.
2
2
25

(17)

Helmbold and Long

We now examine the expectation over ν of the term that depends on ν. We assume that|w1 x1 | ≥ |w2 x2 | so |w · x| = |w1 x1 | − |w2 x2 |; the other case is symmetrical.
Eν (|ωw · (x + ν)|) = |ω| p2 |w · x/p| + p(1 − p)|w1 x1 /p| + p(1 − p)|w2 x2 /p|= |ω| p|w · x| + (1 − p)(|w1 x1 | − |w2 x2 | + |w2 x2 |) + (1 − p)|w2 x2 |= |ω|(|w · x| + 2(1 − p)|w2 x2 |).
Plugging this into (17) gives:
regD,q (ωw) > D(x) (− ln 2 + (1 − p)|ω||w2 x2 |)which goes to infinity as ω goes to ±∞.

Appendix C. Proof of Theorem 15
Theorem 15. Let w be a weight vector and D be a discrete distribution suchthat wi xi ≥ 0 for each index i and all x in the support of D. The limit ofregD,q (ωw) as ω goes to infinity is bounded by ln(2)(1 − p)Px∼D (w · x 6= 0).
First note that If w and D are such that w · x = 0 for all x in the support of D, thenregD,q (w) = regD,q (ωw) = 0. We now analyze the general case.
regD,q (ωw) = Ex,ν= Ex,ν

lnexp( ωw·(x+ν)) + exp( −ωw·(x+ν)
)
2
2
ωw·x
−ωw·x
exp( 2 ) + exp( 2 )lnexp( ωw·(x+ν))(1 + exp(−ωw · (x + ν)))2
ωw·xexp( 2 )(1 + exp(−ωw · x))

!!

!!


= Ex,ν (ωw · (x + ν)/2) + ln (1 + exp (−ωw · (x + ν)))− (ωw · x/2) − ln (1 + exp (−ωwx)) .

(18)

Of the four terms inside the expectation in Equation (18), the first and third cancel
since the expectation of ν is 0. Therefore:
regD,q (ωw) = Ex Eν ln(1 + exp(−ωw · (x + ν))) − ln(1 + exp(−ωwx)) .

(19)

Define nez(w, x) to be the number of indices i where wi xi 6= 0. We now consider cases
based on nez(w, x).
Whenever nez(w, x) = 0 then both w · x = 0 and w · (x + ν) = 0. Therefore thecontribution of these x to the expectation in (19) is ln(2) − ln(2) = 0.
If nez(w, x) > 0 then w · x > 0 (since each wi xi ≥ 0), and the second term of (19)goes to zero as ω goes to infinity. The first term of (19) also goes to zero, unless all of thenez(w, x) components where wi xi > 0 are dropped out. If they are all dropped out, thenthe first term becomes ln(2). The probability that all nez(w, x) non-zero components are26

On the Inductive Bias of Dropout

simultaneously dropped out is (1 − p)nez(w,x) . With this reasoning we get from (19) that:
lim regD,q (ωw)

ω→∞
n
X

=

≤

k=1
n
X



Px∼D (nez(w, x) = k) ln(2)(1 − p)k(20)

Px∼D (nez(w, x) = k) (ln(2)(1 − p))k=1= ln(2)(1 − p)P(w · x 6= 0)
as desired.
(Note that Equation 20 gives a precise, but more complex expression for the limit.)

Appendix D. Proof of Theorem 16
Theorem 16. If 0 < λ ≤ 1/50, then erP5 (v(P5 , λ)) = 0 for the distribution P5
defined in (12).
To keep the notation clean let us abbreviate P5 as just P throughout this proof.
By scaling the L2 criterion we can obtain cancellation in the expectation. Let v beweight vector found by minimizing the following L2 regularized criterion J:J(w) = 3 E(x,y)∼P (`(y(w · x))) + (λ/2)||w||2 .

(21)

Note the factor of 3 is to simplify the expressions and doesn’t affect the minimizing v.
We will prove Theorem 16 with a series of lemmas.
But first, let’s take some partial derivatives:
−10
−1.1
1
∂J
=
+
+
+ 3λw1∂w1
1 + exp(10w1 − w2 ) 1 + exp(1.1w1 − w2 ) 1 + exp(−w1 + 1.1w2 )
(22)
∂J
1
1
−1.1
=
+
+
+ 3λw2 .
∂w2
1 + exp(10w1 − w2 ) 1 + exp(1.1w1 − w2 ) 1 + exp(−w1 + 1.1w2 )(23)
We will repeatedly use the following basic, well-known, lemma.
Lemma 25 For any convex, differentiable function ψ defined on Rn with a unique minimum w∗ , for any w ∈ Rn , if g(w) is the gradient of ψ at w then w∗ is contained in theclosed halfspace whose separating hyperplane goes through w, and whose normal vector is−g(w); i.e., w∗ · g(w) ≤ w · g(w). Furthermore, if g(w) 6= 0 then w∗ · g(w) < w · g(w).
Now we’re ready to start our analysis of P .
Lemma 26 If 0 ≤ λ, the optimizing v1 is positive.
27

Helmbold and Long∂J<
Proof: By Lemma 25, it suffices to show that there is a point (0, a2 ) where both ∂w
1 (0,a2 )∂J
0 and ∂w
= 0.
2 (0,a2 )From Equation (22):

∂J
∂w1

=
(0,a2 )

−11.1
1+
1 + exp(−a2 ) 1 + exp(1.1a2 )and each term is decreasing as a2 increases. Since it is negative when a2 = −2, we have∂J
< 0 for all a2 > −2. So, to prove the lemma, if suffices to show that there is a∂w1
(0,a2 )

∂Ja2 ∈ (−2, ∞) such that the other derivative ∂w
2(0,a2 )

= 0.

From equation (23):
∂J
−1.1
2
+
+ 3λa2=∂w2 (0,a2 ) 1 + exp(−a2 ) 1 + exp(1.1a2 )∂Jand each term is continuously increasing in a2 . When a2 = −2, ∂w
2(0,a2 )

is negative. On∂J∂J
is positive. Therefore for some a2 ∈ (−2, 0) we have ∂w=0
the other hand, ∂w
2 (0,0)2 (0,a2 )as desired.

Lemma 27 There is a real a > 0 such that
∂J(w)
∂w1

+
(a,a)

∂J(w)
∂w2

= 0.
(a,a)

Proof: Applying (22) and (23), we get
def ∂J(w)

b=

∂w1

+
(a,a)

∂J(w)
∂w2

=
(a,a)

−9
−0.2
+
+ 6λa.
1 + exp(9a) 1 + exp(a/10)

Since b is negative when a = 0 and is a continuous function of a, and lima→∞ b > ∞, thelemma holds.
Lemma 28 v1 ≥ v2 .
Proof: Let a be the value from Lemma 27, and let g = (g1 , g2 ) be the gradient of J at(a, a). Lemma 25 implies that v lies in the halfspace through (a, a) in the direction of −g.
Lemma 27 implies that
g1 =

∂J(w)
∂w1

=−
(a,a)

∂J(w)
∂w2

= −g2 .
(a,a)

Examination of the derivatives (22) and (23) at (a, a) shows that the first term of (22) isnegative and the first term of (23) is positive while the last three terms match (although28

On the Inductive Bias of Dropout

in a different order). Therefore g1 < 0 and g2 = −g1 is positive. Applying Lemma 25
completes the proof.
Lemma 28 implies that v correctly classifies (10, −1) and (11/10, −1). It remains toshow that v correctly classifies (−1, 11/10), that is, that v1 is not too much bigger than v2 .
Lemma 29 If v2 ≥ 0.6 and λ > 0 then v1 < 11v2 /10.
∂J
Proof: Combining ∂w
1

3λv1 =v= 0 with (22), we get

10
1.1
−1
+
+
1 + exp(10v1 − v2 ) 1 + exp(1.1v1 − v2 ) 1 + exp(−v1 + 1.1v2 )and, similarly,
3λv2 =

−1
−1
1.1
+
+
.
1 + exp(10v1 − v2 ) 1 + exp(1.1v1 − v2 ) 1 + exp(−v1 + 1.1v2 )Thus
3λ(10v1 − 11v2 ) =

111
22
22.1
+
−
. (24)
1 + exp(10v1 − v2 ) 1 + exp(1.1v1 − v2 ) 1 + exp(−v1 + 1.1v2 )Assume for contraction that v1 ≥ 11v2 /10. Then 10v1 − v2 ≥ 10v2 , 1.1v1 − v2 ≥ 0.21v2 , and−v1 + 1.1v2 ≤ 0, so
3λ(10v1 − 11v2 ) ≤

111
22
+
− 11.05.
1 + exp(10v2 ) 1 + exp(0.21v2 )However, 10v1 − 11v2 ≥ 0 and (since v2 ≥ 0.6) the RHS is negative, giving the desired
contradiction.
Lemma 30 If 0 < λ ≤ 1/50 then v2 ≥ 0.6.
Proof: It suffices to show that there is a point (x, 0.6) where the partial w.r.t. w1 is 0 andthe partial w.r.t w2 is negative.
−10
∂J
−1.1
1
=
+
+
+ 3λx
∂w1 (x,0.6) 1 + exp(10x − 0.6) 1 + exp(1.1x − 0.6) 1 + exp(−x + 0.66)
and is increasing in x and λ (assuming x > 0) and becomes positive as x goes to infinity. It
is negative when evaluated at x = 0.6 and λ = 1/50, so for all λ ≤ 1/50 there is an x > 0.6
such that ∂J/∂w+ (x,1) = 0.
∂J
1
1
−1.1
=
+
+
+ 1.8λ∂w2 (x,0.6) 1 + exp(10x − 0.6) 1 + exp(1.1x − 0.6) 1 + exp(−x + 0.66)
and is decreasing in x and increasing in λ. It is negative when x = 0.6 and λ = 1/50, so it
will remain negative for all x > 0.6 and 0 ≤ λ ≤ 1/50, as desired.
So, we have shown that, if λ ≤ 1/50, then all examples are classified correctly by v,
which proves Theorem 16.
29

Helmbold and Long

Appendix E. Proof of Theorem 17
Theorem 17. If q ≥ 1/3 then erP5 (w∗ (P5 , q)) ≥ 1/3 for the distribution P5
defined in (12).
Throughout this proof we also abbreviate P5 as just P .
For this subsection, let us define the scaled dropout criterion
J(w) = 3 E(x,y)∼P,r (`(y(w · (r

x))))

(25)

where the components of r are independent samples from a Bernoulli distribution withparameter p = 1 − q > 0. Again, the factor of 3 is to simplify the expectation and doesn’tchange the minimizing w. Let w~ be the minimizer of this J(w), so that Equation (4)implies that the optimizer w∗ of the dropout criterion is pw~ . Note that w∗ classifies anexample correctly if and only if w~ does.
Next, note that we may assume without loss of generality that both components of w~
are positive, since, if either is negative, one of (−1, 1.1) or (1.1, −1) is misclassified and weare done.
We will prove Theorem 17 by proving that, when q ≥ 1/3, w~ misclassifies (−1, 1.1),
or, equivalently, that w1~ > (11/10)w2~ .
First, let us evaluate some partial derivatives. (Note that, if xi is dropped out, the valueof wi does not matter.)


∂J
−10
−1.1
1
2
= (1 − q)++∂w1
1 + exp(10w1 − w2 ) 1 + exp(1.1w1 − w2 ) 1 + exp(−w1 + 1.1w2 )
(26)


−10
−1.1
1
+ (1 − q)q++
1 + exp(10w1 ) 1 + exp(1.1w1 ) 1 + exp(−w1 )


∂J
1
1
−1.1
2
= (1 − q)++∂w2
1 + exp(10w1 − w2 ) 1 + exp(1.1w1 − w2 ) 1 + exp(−w1 + 1.1w2 )
(27)


1
1
−1.1
+ q(1 − q)++.
1 + exp(−w2 ) 1 + exp(−w2 ) 1 + exp(1.1w2 )The following is the key lemma. As before, it is useful since, for any w, if g(w) isnonzero, then w~ lies in the open halfspace through w whose normal vector is the negative
gradient.
Lemma 31 For all a > 0 and q ≥ 1/3,
∂J
∂w2

> 0.

(28)

(a,10a/11)

Proof: We have
∂J
∂w2



1
1
−1.1
=(1 − q)++
1 + exp(100a/11) 1 + exp(21a/110)
2(a,10a/11)


2
−1.1
+ q(1 − q)+.
1 + exp(−10a/11) 1 + exp(a)
2

30



On the Inductive Bias of Dropout

Note that this derivative is positive if and only if
f (q, a)∂J
1=
1 − q ∂w2
(a,10a/11)


11
2
−1
−1
−11/10=q++++
20 1 + exp(−10a/11) 1 + exp(21a/110) 1 + exp(100a/11) 1 + exp(a)
1
1
−11
+
+
+
1 + exp(21a/110) 1 + exp(100a/11)
20
is positive, as 0 < q < 1. Note that the terms multiplying q are increasing in a and sum to0 when a = 0. On the other hand, the terms not multiplied by q are decreasing in a andturn negative when a is just over 1/4. Thus both parts are positive when a ≤ 1/4. Notethat f (q, a) can be underestimated by underestimating a on the q-terms and overestimating
a on the other terms.
For 1/4 ≤ a ≤ 2,
f (q, a)


11
2
−1
−1
−11/10≥q++++
20 1 + exp(−10/44) 1 + exp(21/440) 1 + exp(100/44) 1 + exp(1/4)
1
1
−11
+
+
+
1 + exp(42/110) 1 + exp(200/11)
20≥ 0.5q − 0.15
and is positive whenever q ≥ 1/3.
For a ≥ 2,
f (q, a)


11
2
−1
−1
−11/10
−11
≥q
+
+
+
+
+
20 1 + exp(−20/11) 1 + exp(42/110) 1 + exp(200/11) 1 + exp(2)20≥ 1.7q − 11/20
and is also positive whenever q ≥ 1/3.
Proof of Theorem 17: Let g = (g1 , g2 ) be the gradient of J at (w1~ , 10w1~ /11).
Lemma 31 shows g is not 0, so by convexity
w~ · g < (w1~ , 10w1~ /11) · g
which implies
w2~ g2 < (10w1~ /11) g2 .
Since g2 > 0 (Lemma 31), this implies
w2~ < (10w1~ /11)
and the (−1, 11/10) example is misclassified by w~ , and therefore by w∗ , completing theproof.
31

Helmbold and Long

Appendix F. Proof of Theorem 18
Theorem 18. If 1/100 ≤ λ ≤ 1, then erP6 (v(P6 , λ)) ≥ 1/7 for the distribution
P6 defined in (13).
To keep the notation clean, in this section let us abbreviate P6 simply as P .
As the reader might expect, we will prove Theorem 18 by proving that v fails to correctlyclassify (1/10, −1), that is, by proving that v1 < 10v2 .
We may assume that v1 > 0, since, otherwise, (1, 0) is misclassified.
To obtain cancellation in the expectation, we work with the scaled L2 criterion
J(w) = 7E(x,y)∼P (`(y(w · x))) + (7λ/2)||w||2 .

(29)

and let v(P, λ) be the vector minimizing this J, which we often abbreviate as simply v,
leaving it implicitly a function of λ. Note that this scaling of the criteria does not change
the minimizing v.
Taking derivatives,
∂J
−3
3
−0.1
=
+
+
+ 7λw1∂w1
1 + exp(w1 ) 1 + exp(−w1 + w2 ) 1 + exp(w1 /10 − w2 )
−3
1
∂J
=
+
+ 7λw2 .
∂w2
1 + exp(−w1 + w2 ) 1 + exp(w1 /10 − w2 )

(30)
(31)

Lemma 32 If either: λ ≥ 1/100 and a ≥ 1/3, or λ ≥ 1/4 and a ≥ 1/15 then
∂J(w)
> 0.
∂w1 (10a,a)Proof: We have
∂J(w)
∂w1

(10a,a)

−3
3
−1
+
+
+ 70λa(1 + exp(10a)) 1 + exp((1 − 10)a)
20
−3
−1
>
+
+ 70λa.
(1 + exp(10a))20=

Each term of the RHS is non-decreasing in a and λ, and the RHS is positive when either
λ = 1/100 and a = 1/3 or λ = 1/4 and a = 1/15.
To apply this, we want to show that v2 is large enough, which we do next.
Lemma 33 If λ ≤ 1/4 then v2 ≥ 1/3 and if λ ≤ 1 then v2 ≥ 1/15.
Proof: Assume to the contrary that λ ≤ 1/4 but v2 < 1/3. From (31), and using thatv1 > 0, we have
∂J
−3
1
<
+
+ 7λv2 ,(32)∂w2
1 + exp(v2 ) 1 + exp(−v2 )v

32

On the Inductive Bias of Dropout

Table 2: Seven times the dropout distribution. The three probability sub-columns correspond to the original examples (1,0), (-1/1000, 1), (1/10, -1), and the final column
is the over-estimate used in Lemma 36.
x1 r1
x2 r2
0
0
1
0
0
1
−1/10000−1/1000
1
0
−1
1/10
0
1/10
−1

y
seven times probability
w~ · (r
2
2
1
3q
+3q
+q
1 3(1 − q)1
3q(1 − q)1
3q(1 − q)13(1 − q)2
1
q(1 − q)1
q(1 − q)1
(1 − q)2∂J
a bound that is increasing in v2 and λ. Since ∂w
2vx) over-estimate
0
∞
w2
0
w2
∞
∞
∞

= 0, the bound must be positive.

However, when v2 ≤ 1/3 and λ ≤ 1/4, it is negative, giving the desired contradiction.
Since the bound (32) is also negative at v2 = 1/15 and λ = 1, a similar contradiction
proves the other half of the lemma.
Proof: (of Theorem 18): Lemmas 32 and 33 imply that (10v2 , v2 ) is not the minimizingv (when λ ≥ 1/100), so by convexity,J(10v2 , v1 ) + (v1 , v2 ) − (10v2 , v2 ) · ∇J(10v2 , v2 ) < J(v1 , v2 )(33)
(v1 − 10v2 )

∂J
∂w2

< 0.

(34)

(10v2 ,v2 )If 1/100 ≤ λ ≤ 1/4 then Lemma 33 shows that v2 ≥ 1/3 and if 1/4 ≤ λ ≤ 1 then it shows∂J> 0. Therefore,that v2 ≥ 1/15. In either case, Lemma 32 shows that that ∂w
2(10v2 ,v2 )v1 < 10v2
and (0.1, −1) is misclassified by v, completing the proof.

Appendix G. Proof of Theorem 19
Theorem 19. If q ≤ 1/2, then erP6 (w∗ (P6 , q)) = 0. for the distribution P6
defined in (13).
In this proof, let us abbreviate P6 with just P , and use  to denote 1/1000.
For this section, let us define the scaled dropout criterion
J(w) = 7E(x,y)∼P,r (`(y(w · (rx)))),(35)

where, as earlier, the components of r are independent samples from a Bernoulli distribution
with parameter p = 1−q = 1/2 > 0. (Note that, similarly to before, scaling up the objective
33

Helmbold and Long

function by 7 does not change the minimizer of J.) See Table 2 for a tabular representationof the distribution after dropout. Let w~ be the minimizer of J, so that w∗ = pw~ (seeEquation (4)).
First, let us evaluate some partial derivatives (note that 1 − q = (1 − q)2 + q(1 − q)).


−3
∂J
3
−0.1
2
= (1 − q)
(36)
+
+
∂w1
1 + exp(w1 ) 1 + exp(−w1 + w2 ) 1 + exp(0.1w1 − w2 )


−3
3
−0.1
+ (1 − q)q++
1 + exp(w1 ) 1 + exp(−w1 ) 1 + exp(0.1w1 )


∂J
−3
1
2
= (1 − q)
(37)
+
∂w2
1 + exp(−w1 + w2 ) 1 + exp(0.1w1 − w2 )


−3
1
.
+ q(1 − q)+
1 + exp(w2 ) 1 + exp(−w2 )Let’s get started by showing that w~ correctly classifies (1, 0).
Lemma 34 w1~ > 0.
∂J
Proof: As before, it suffices to show that there is a point (0, a2 ) where both ∂w<0
1 (0,a2 )∂Jand ∂w= 0.
2 (0,a2 )From Equation (36):∂J= (1 − q)2∂w1 (0,a2 )



−3
3
−0.1
+
+
2
1 + exp(a2 ) 1 + exp(−a2 )+(1 − q)q(−3.1 + 3)2which is decreasing in a2 , and negative even as a2 approaches −∞ (recalling  = 1/1000),∂Jso ∂w
is always negative.
1(0,a2 )

Equation (37) implies∂J∂w2 (0,a2 )= (1 − q)

2



−3
1
+
1 + exp(a2 ) 1 + exp(−a2 )+ q(1 − q)−3
1+
1 + exp(a2 ) 1 + exp(−a2 ).

This is negative when a2 = 0, approaches 1 − q as a2 goes to infinity, and is continuous, so∂J∂J= 0. Since ∂w< 0, this proves the lemma.
there is a a2 such that ∂w
2
1(0,a2 )

(0,a2 )

Next, we’ll start to work on showing that w~ correctly classifies (−, 1).
Lemma 35 For all a > 1/10,
∂J
∂w1

> 0.
(a/,a)Proof: From (36), we have



−3
3
−0.1
+
+
1 + exp(a/) 1 + exp(0) 1 + exp(0.1(a/) − a)


3
−0.1
−3
+ q(1 − q)++
1 + exp(a/) 1 + exp(−a) 1 + exp(a/10)∂J=(1 − q)2
∂w1 (a/,a)34

On the Inductive Bias of Dropout

which is positive if a > 1/10 as the positive terms (even with the  factors) dominate thenegative ones.
Lemma 36
w2~ > 1/4.
Proof: Assuming w1 ≥ 0, the estimates in Table 2 along with the facts that `(z) is positiveand decreasing show :J(w) ≥ 3(1 − q) ln(1 + exp(−w2 )) + 6q ln(2) + q 2 ln(2)(38)

which is decreasing in w2 . If w2~ ≤ 1/4, then bound (38) and the fact that w1~ > 0(Lemma 34) imply that
J(w~ ) ≥ 0.69q 2 + 2.4q + 1.7.
On the other hand,J(100, 2) ≤ −1.5q 2 + 6q + 0.42,
and the upper bound on J(100, 2) is less than the lower bound on J(w~ ) when 0 ≤ q ≤ 1/2,
giving the desired contradiction.
Now, we’re ready to show that w~ correctly classifies (−, 1).
Lemma 37 w1~ < w2~ .
Proof: Let g be the gradient of J evaluated at (w2~ /, w2~ ). Combining Lemmas 35 and36, g 6= (0, 0), so
w~ · g < (w2~ /, w2~ ) · g.
This implies
w1~∂J
w2~ ∂J<.
∂w1 (w2~ /,w2~ ) ∂w1 (w2~ /,w2~ )Since Lemmas 35 and 36 imply that g(w2~ /, w2~ )1 > 0, this completes the proof.
Finally, we are ready to work on showing that (1/10, −1) is correctly classified by w~ ,i.e. that w1~ > 10w2~ .
Lemma 38 For all a ∈ R,
∂J
< 0.
∂w1 (10a,a)Proof: Choose a ∈ R. From (36), we have


∂J
−3
3
−1
= q(1 − q)++
∂w1 (10a,a)
1 + exp(10a) 1 + exp(−10a) 10(1 + exp(a))


−3
3
−1
2
+ (1 − q)++
1 + exp(10a) 1 + exp(a − 10a)
20


−1
≤ (1 − q)2 6 +<0
20
using q ≤ 1/2 and  = 1/1000.
35

Helmbold and Long

Lemma 39 w1~ > 10w2~ .
Proof: Let g be the gradient of J evaluated at u = (10w2~ , w2~ ). Lemma 38 implies thatg 6= (0, 0), i.e. that w1~ 6= 10w2~ . Therefore,w~ · g < u · gwhich, since u2 = w2~ , implies
w1~

∂J
∂J
< 10w2~
.
∂w1 u
∂w1 u

Since Lemma 38 implies that ∂J/∂w1u< 0, this in turn implies

w1~ > 10w2~ ,completing the proof.
Now we have all the pieces to prove that dropout succeeds on P .
Proof (of Theorem 19): Lemma 34 implies that (1, 0) is classified correctly by w~ , andtherefore by w∗ = pw~ . Lemma 37 implies that (−, 1) is classified correctly. Lemma 39
implies that (1/10, −1) is classified correctly, completing the proof.

Appendix H. Proof of Theorem 20
1
Theorem 20. If λ ≤ 30n
then the weight vector v(P9 , λ) optimizing the L2
criterion has perfect prediction accuracy: erP9 (v(P9 , λ)) = 0.

In this proof, let us abbreviate P9 as just P .
By symmetry and convexity, the optimizing v is of the form (v1 , v2 , v2 , . . . , v2 ) with thelast n − 1 components being equal. Thus for this distribution minimizing the L2 criterion
is equivalent to minimizing the simpler criterion K(w1 , w2 ) defined by:K(w1 , w2 ) =


9
1
λ 2
ln (1 + exp(−w1 − w2 )) +ln (1 + exp(w1 − w2 )) +w1 + (n − 1)w22 .
10102

Let (v1 , v2 ) be the minimizing vector of K(), retaining an implicit dependence on n andλ. We will be making frequent use of the partial derivatives of K:
−9
1
∂K
=
+
+ λw1
∂w1
10(1 + exp(w1 + w2 )) 10(1 + exp(−w1 + w2 ))
∂K
−9
−1
=
+
+ (n − 1)λw2 .
∂w2
10(1 + exp(w1 + w2 )) 10(1 + exp(−w1 + w2 ))

(39)
(40)

It suffices to show that 0 ≤ v1 < v2 so that the first feature does not perturb the majority
vote of the others.
To see 0 ≤ v1 , notice that ∂K/∂w1 (0,w2 ) is negative for all w2 , including when w2 = v2 .
36

On the Inductive Bias of Dropout

To prove v1 < v2 we show the existence of a point (a, a) such that
∂K
∂w1

=−
(a,a)

∂K
∂w2

> 0,

(41)

(a,a)

so that Lemma 25 implies that the optimizing (v1 , v2 ) lies above the w1 = w2 diagonal.
−∇Kw2(a, a)
w1
We have

∂K
−9
1
=
+
+ λa
∂w1 (a,a) 10(1 + exp(2a)) 20

which is increasing in a, negative when a = 0 and goes to infinity with a. It turns positiveat some a < 1.5 (exactly where depends on λ).
On the other hand,
∂K
−9
−1
=
+
+ λ(n − 1)a∂w2 (a,a) 10(1 + exp(2a))
20
and is also increasing in a and goes to infinity. However, ∂K/∂w2(a,a)

is negative at a = 1.5

whenever 1.5λ(n − 1) ≤ 1/20, which is implied by the premise of the theorem.
Both partial derivatives are negative when a = 0, continuously go to infinity with a,and ∂K/∂w1
crosses zero first. From the point where ∂K/∂w1
crosses zero until(a,a)∂K/∂w2

(a,a)

(a,a)

does, the magnitude of ∂K/∂w1

magnitude of ∂K/∂w2

(a,a)

(a,a)

is increasing, starting at 0, and theis decreasing until it reaches 0. When they meet, Equation (41)holds, completing the proof.

Appendix I. Proof of Theorem 21
Theorem 21. If the dropout probability q = 1/2 and the number of features
is an even n > 125 then the weight vector w∗ (P9 , q) optimizing the dropout
criterion has prediction error rate erP9 (w∗ (P9 , q)) ≥ 1/10.
In this proof, we again abbreviate, using P for P9 .
The complicated form of the criterion optimized by dropout makes analyzing it difficult.
Here we make use of Jensen’s inequality. However, a straightforward application of it isfruitless, and a key step is to apply Jensen’s inequality on just half the distribution resulting
from dropout.
37

Helmbold and Long

Similarly to before, letJ(w) = E(x,y)∼P,r (`(y(w · (rx)))),(42)

and let w~ minimize J, so that w∗ = pw~ .
Again using symmetry and convexity, the last n − 1 components of the optimizing w~
are equal, so w~ is of the form (w1~ , w2~ , w2~ , . . . , w2~ ).
Lemma 40 The minimizing w1~ of (42) is positive.
gr be the marginal distribution of the last n−1 components after dropout and
Proof: Let P,x̃ denote these last n − 1 components of the dropped-out feature vector. Then, recalling yis always 1 in our distribution (and p is the probability that the first feature is not dropped
out),
∂J(w)
= E(r2 ,...,rn )
∂w1




p
9p
0
0
E f (` (w · (1, x̃))) − Ex̃∼P,rf (` (w · (−1, x̃)))
10 x̃∼P,r10

which is negative whenever w1 = 0, since `0 () is negative and the two inner expectations
become identical when w1 = 0. Therefore the optimizing w1~ is positive.
To show that dropout fails, we want to show that w1~ > w2~ , i.e. that w1~ ≤ w2~ leads toa contradiction, so we begin to explore the consequences of w1~ ≤ w2~ .
Lemma 41 If q = 1/2 and w1~ ≤ w2~ then w2~ > 4/9.
Proof: Assume to the contrary that w1~ ≤ w2~ ≤ 4/9.
Using Jensen’s inequality,
J(w~ ) ≥ `(E(x,y)∼P,r (y(w~ · x)))and the inner expectation is 8w1~ /20 + w2~ /2 ≤ 9w2~ /10 as w1~ ≤ w2~ . Therefore, sincew2~ ≤ 4/9,
J(w~ ) ≥ `(0.4) > 0.51.
However,J(2.1, 0, 0, . . . , 0) =ln(2) 9 ln(1 + e−2.1 ) ln(1 + e2.1 )++< 0.512
20
20contradicting the optimality of w~ .
Lemma 42 If q = 1/2 and w1~ ≤ w2~ then J(w~ ) ≥ Ek∼B(n,1/2) `(w2~ (k − (n/2) + 1)) where
B(n, 1/2) is the binomial distribution.
Proof: Consider the modified distribution P1 over (x, y) examples where y is always 1, x2 ,..., xn are uniformly distributed over the the vectors with n/2 ones and (n/2) − 1 negative38

On the Inductive Bias of Dropout

ones (as in P ), but x1 is always one. Since 0 < w1~ ≤ w2~ and the label y = 1 under P andP1 ,J(w~ ) = E(x,y)∼P,r (`(w~ · x))> E(x,y)∼P1 ,r (`(w~ · x))= E(x,y)∼P1 ,r ` w2~ (1 · (x r))
= E(x,y)∼P1 ,r ` w2~ (x · r) .

Every x in the support of P1 has exactly (n/2)+1 components that are 1, and the remaining(n/2) − 1 components are −1. Call a component a success if it is either −1 and dropped
out or 1 and not dropped out. Now, x · r is exactly 1 − (n/2) plus the number of successes.
Furthermore, the number of successes is distributed according to the binomial distribution
B(n, 1/2). ThereforeE(x,y)∼P1 ,r (w2~ (x · r)) = Ek∼B(n,1/2) (`(w2~ (k − (n/2) + 1)))
giving the desired bound.
√ 

w~ 2n
Lemma 43 For even n ≥ 6, Ek∼B(n,1/2) (`(w2~ (k − (n/2) + 1))) ≥ 13 ` w2~ − 2 4.

Proof: Let α =Pn/2−1 ni=0i, so α is slightly less than 2n−1 .

Ek∼B(n,1/2) (`(w2~ (k − (n/2) + 1))) =

 
1 X n
`(w2~ (k + 1 − (n/2)))
k
2n
k

n/2−1

 
α X 1 n`(w2~ (1 + k − (n/2)))
2n
α k
k=0


n/2−1  
X
α
1 n ~
> n`
w2 (1 + k − (n/2))
2
α k
>

k=0

where the last step uses Jenson’s inequality. Continuing,
Ek∼B(n,1/2) (`(w2~ (k − (n/2) + 1))) >n/2−1  
w2~ X nα  ~` w2 +
2n
α

k=0

k



(k − (n/2)) .

Equation (5.18) of Concrete Mathematics Graham et al. (1989) and the bound
n
√2
give
2n

√



n
−n n
− 2n 2n−1(k − (n/2)) =
≤
.
k
4 n/2
4

n/2−1 

X
k=0

39

n
n/2



≥

Helmbold and Long

Therefore, recalling that α < 2n−1 and noting α/2n > 1/3 when n ≥ 6,√ !
α
w2~ 2n−1 2n~~
Ek∼B(n,1/2) (`(w2 (k − (n/2) + 1))) > n ` w2 −
2
α
4
!
√
1
w2~ 2n~.
> ` w2 −3
4
We now have the necessary tools to prove Theorem 21.
Proof: (of Theorem 21) If w1~ > w2~ then the first feature will dominate the majority
vote of the others and the optimizing w~ has prediction error rate 1/10 . We now assume
to the contrary that w1~ ≤ w2~ . When n > 125 and w2~ ≥ 4/9 (from Lemma 41) we have√w2~ 2n~w2 −≤ −1.314√w~ 2n

and `(w2~ − 2 4 ) > 1.54.
Lemmas 42 and 43 now imply that J(w~ ) > 0.51, but (as in Lemma 41) J(2.1, 0, . . . 0) <0.51, contradicting the optimality of w~ .
Many of the approximations used to prove Theorem 21 are quite loose, resulting in large
values of n being needed to obtain the contradiction. For this class of distributions andq = 1/2 we conjecture that optimizing the dropout criterion fails to produce the Bayes
optimal hypothesis for every even n ≥ 4.

Appendix J. Proof of Theorem 22
Theorem 22. If dropout probability q = 1/2 and the number of features is
n = 4 then the minimizer of the dropout criteria w∗ (P9 , q) has has prediction
error rate erP9 (w∗ (P9 , q)) ≥ 1/10.
In this proof, let us also refer to P9 as just P and let w~ be the minimizer of (42).
As before, the optimizing w~ has the form (w1~ , w2~ , w2~ , w2~ ) by symmetry and convexity.
Recalling that the label y is always 1 under distribution P , we can use the equivalent
criterion!!
4
X
K(w1 , w2 ) = E(x,y)∼P,r (`(y(w · x))) = E(x,y)∼P,r ` w1 x1 r1 + w2
xi ri
.
i=2

This expectation can be written with
P4 12 terms, one for each pairing of the three possible
x1 r1 values with the four possible i=2 xi ri ∈ {−1, 0, 1, 2} values (see Table 3).
Taking them in order, we haveK(w1 , w2 ) =

9
27
27
9
` (w1 + 2w2 ) +` (w1 + w2 ) +` (w1 ) +` (w1 − w2 )
160
160
160
160
10
30
30
10
+
` (2w2 ) +` (w2 ) +` (0) +` (w2 )
160
160
160
160
1
3
3
1
+
` (−w1 + 2w2 ) +` (−w1 + w2 ) +` (−w1 ) +` (−w1 − w2 ) .
160
160
160
160
40

On the Inductive Bias of Dropout

x1 r1
1
0
-1

P4

i=2 xi ri values assuming dropout probability q = 1/2.
P4
probability
probability
i=2 xi ri

Table 3: Probabilities of x1 r1 and

9/20
1/2
1/20

2
1
0
-1

1/8
3/8
3/8
1/8

∇K = (−c, c)

w2(a, a)−∇K = (c, −c)w1Figure 8: If ∇K at some (a, a) is (−c, c) for some c > 0 then w1~ > w2~ .

So, when p = q = 1/2, the derivatives are:
∂K
∂w1
=

1
160

−9
−27
−27
−9
+
+
+
1 + exp(w1 + 2w2 ) 1 + exp(w1 + w2 ) 1 + exp(w1 ) 1 + exp(w1 − w2 )

!
1
3
3
1
+
+
+
,
+
1 + exp(−w1 + 2w2 ) 1 + exp(−w1 + w2 ) 1 + exp(−w1 ) 1 + exp(−w1 − w2 )
∂K
∂w2
=

1
160
+

−18
−27
9
+
+
1 + exp(w1 + 2w2 ) 1 + exp(w1 + w2 ) 1 + exp(w1 − w2 )

−20
−30
10
+
+
1 + exp(2w2 ) 1 + exp(w2 ) 1 + exp(−w2 )

!
−2
−3
1
+
+
+
.
1 + exp(−w1 + 2w2 ) 1 + exp(−w1 + w2 ) 1 + exp(−w1 − w2 )If w1~ > w2~ , then dropout will have prediction error rate 1/10 as w1~ will dominate thevote of the other three components. We show that w1~ > w2~ by proving that there is apoint (a, a) in weight space such that the gradient at (a, a) is of the form (−c, c) for somec > 0 (see Figure 8).
41Helmbold and Long

The derivatives when evaluated at (a, a) are:
∂K
∂w1

(a,a)

1
=
160

−9
−27
−26
3
1
+
+
−3+
+
1 + exp(3a) 1 + exp(2a) 1 + exp(a)1 + exp(−a) 1 + exp(−2a)

!

and
∂K
∂w2

(a,a)

1
=
160

!
−18
−47
−32
10
1
+
+
+3+
+
.
1 + exp(3a) 1 + exp(2a) 1 + exp(a)1 + exp(−a) 1 + exp(−2a)

Note that both of these derivatives are increasing in a, positive for large a, and negative
when a = 0. At a = 2 ln(2), derivative ∂K/∂w1 (a,a) is still negative, while ∂K/∂w1 (a,a)
has turned positive, so ∂K/∂w1 (a,a) crosses 0 first. The continuity of the partial derivatives
now implies the existence of an (a, a) where ∇K has the form (−c, c), completing the proof.

Appendix K. Proof of Theorem 23√
Theorem 23. If q = 1/2, n ≥ 100, α > 0, β = 1/(10 n − 1), and η ≤1 √, then erP10 (w∗ (P10 , q)) = η.
2+exp(54 n)
For this subsection, let P = P10 and define the scaled dropout criterion
J(w) = E(x,y)∼P,r (`(yw · (rx))),

where, as earlier, the components of r are independent samples from a Bernoulli distribution
with parameter p = 1 − q = 1/2 > 0. Let w~ be the minimizer of J, so that w∗ = pw~ .
Note that, by symmetry, the contribution to J from the cases where y is −1 and 1
respectively are the same, so the value of J is not affected if we clamp y at 1. Let us use
this form to express J, and let D be the marginal distribution of feature vector x conditionedon the label y = 1.
Let B = {2, ..., n}. By symmetry, wi~ is identical for all i ∈ B so w~ is the minimumof J over weight vectors satisfying this constraint. Let K(w1 , w2 ) = J(w1 , w2 , ..., w2 ); notethat w1~ , w2~ minimizes K defined by
X
K(w1 , w2 ) = Ex∼D,r (`(w1 r1 x1 + w2
ri xi )).
i∈B

To prove Theorem 23, it suffices to show that
w1~ > (n − 1)w2~ /α > 0,
42

(43)

On the Inductive Bias of Dropout

since when (43) holds, w~ always outputs x1 .
We have


∂K
1
−x1
P
= Ex∼D,r∂w1
2
1 + exp(w1 x1 + w2 i∈B ri xi )P− i∈B ri xi∂KP= Ex∼D,r.
∂w2
1 + exp(w1 r1 x1 + w2 i∈B ri xi )

(44)
(45)

(Note that, in (44), we have marginalized out r1 .)Lemma 44 w2~ > 0.
∂K
As before, it suffices to show that there is a point (a1 , 0) where both ∂w< 0 and
2 (a1 ,0)∂K
∂w1 (a1 ,0) = 0. From equation (45),∂K= Ex∼D,r∂w2 (a1 ,0)P− i∈B ri xi<0
1 + exp(a1 r1 x1 )for all real a1 .
Now, evaluating (44), dividing into cases based on x1 , we get∂K= (η/2)∂w1 (a1 ,0)α
1 + exp(−αa1 )+ ((1 − η)/2)−α
1 + exp(αa1 ).

This approaches −α((1 − η)/2) as a1 approaches −∞, and it approaches αη/2 as a1 approaches ∞. Since it is a continuous function of a1 , there must be a value of a1 such that∂K∂K
∂w1 (a1 ,0) = 0. Putting this together with ∂w2 (a1 ,0) < 0 completes the proof.
To show the sufficient inequalities (43), it will be useful to prove an upper bound on w2~ .
(This upper bound will make it easier to show, informally, that w1~ is needed.) In order
to bound the size of w2~ , we will prove a lower bound on K in terms of w2 . For this, wewant to show that, if w2 is too large, then the algorithm will pay too much when it makes
large-margin errors. For this, we need a lower bound on the probability of a large-margin
error. For this, we can adapt an analysis that provided a lower bound on the probability ofan error from Helmbold and Long (2012).
To simplify the proof, we will first provide a lower bound on the dropout risk in termsof the risk without dropout. We will actually prove something somewhat more general, forpossible future reference.
Lemma 45 Let r and x be independent, RN -valued random variables; let φ be convex
function of a scalar real variable. Then
!!
Er,x

φ

X

xi ri

!!
≥ Ex

i

φ

X
i

43

xi Er (ri ).

Helmbold and Long

Proof: Since x and r are independent,
XEr,x (φ(xi ri ))iX
= Ex (Er (φ(xi ri )))iX
≥ Ex (φ(Er (xi ri ))) (by Jensen’s Inequality)i

X= Ex (φ(xi Er (ri ))),
icompleting the proof.
Now, it is enough to lower bound the probability of a large-margin error with respect
to the original distribution. Recall B = {2, . . . , n}.

Lemma 46

Pr

1 X
xi < −2β
n−1

!
≥

i∈B

3
.
10

Proof: If Z is a standard normal random variable and R is a binomial (`, p) random variablewith p ≤ 1/2, then for `(1 − p) ≤ j ≤ `p, Slud’s inequality Slud (1977) (see also Lemma 23
of Helmbold and Long (2012)) givesj − `p

Pr(R ≥ j) ≥ Pr Z ≥ p`p(1 − p)

!
.

(46)

Now, we havePr

1 X
xi < −2β
n−1

!

!
= Pr

i∈B

X

xi /2 < −(n − 1)β

i∈B

!
= Pr

X

(xi + 1)/2 < (n − 1)/2 − (n − 1)β

i∈B

!
= Pr

X

zi < (n − 1)(1/2 − β)i∈Bwhere the P
zi ’s are independent {0, 1}-valued variables with Pr(zi = 1) = 1/2 + β. Let z̄i be
1 − zi , so i∈B z̄i is a Binomial (n − 1, 1/2 − β) random variable. Furthermore,!
PrX

zi < (n − 1)(1/2 − β)

!
= Pr

i∈B

X

z̄i > (n − 1) − (n − 1)(1/2 − β)

i∈B

!
= Pr

X
i∈B

44

z̄i > (n − 1)(1/2 + β) .

On the Inductive Bias of Dropout

Using (46) with j = (n − 1)(1/2 + β), ` = (n − 1), and p = 1/2 − β gives:!
!
X(n − 1)(1/2 + β) − (n − 1)(1/2 − β)pPrz̄i > (n − 1)(1/2 + β) ≥ Pr Z ≥(n − 1)(1/4 − β 2 )i∈B!
2(n − 1)β= Pr Z ≥ p.
(n − 1)(1/4 − β 2 )√Since β = 1/(10 n) and n ≥ 100, this implies!
1 X
Pr
xi < −2β ≥ Pr (Z ≥ 1/2) .
n−1
i∈B

√
Since the density of Z is always at most 1/ 2π, we have
!
1 X
1
1
xi < −2β ≥ Pr(Z ≥ 0) − Pr(Z ∈ (0, 1/2)) > − √ > 3/10,
Pr
n−1
2 2 2πi∈Bcompleting the proof.
Now we are ready for the lower bound on the dropout risk in terms of w2 .
Lemma 47 For all w1 ,√w2 n − 1K(w1 , w2 ) >.
67

Proof: Considering only the case in which x1 is dropped out (i.e. r1 = 0), we have!!
X
1
K(w1 , w2 ) ≥ E ` w2
ri xi
.
2
i

Applying Lemma 45, we get
X1
xi
K(w1 , w2 ) ≥ E ` (w2 /2)
2

!!
.

i∈B

Since ` is non-increasing and non-negative, we have1
K(w1 , w2 ) ≥ `(−w2 β(n − 1))Pr
2

1 X
xi < −2βn−1i∈Band applying Lemma 46 gives
K(w1 , w2 ) ≥3`(−w2 β(n − 1)).
20

Since `(z) > −z, we haveK(w1 , w2 ) ≥3w2 β(n − 1)
20

45

!
,

Helmbold and Long

and, using β = 10√1n−1 , we get√
3w2 n − 1,K(w1 , w2 ) ≥200completing the proof.
27.
Lemma 48 w2~ < √n−1

Proof: Note that
K(w, 0) = `(0)/2 + (1/2)(η`(−αw) + (1 − η)`(αw)),
is increasing in η so thatK(w1~ , w2~ ) ≤ K(5/α, 0) < `(0)/2 + 1/35

(47)

since η < 1/100.
On the other hand, Lemma 47 gives
w2
K(w1~ , w2~ ) >

√

n−1
.
67

Solving for w2~ completes the proof.
27
Lemma 49 For all 0 < u < √n−1
, we have∂K< 0.
∂w1 ((n−1)u/α,u)Proof: From (44), we have∂K
∂w1 (nu/α,u)


−x1
P
= Ex∼D,r
1 + exp((n − 1)ux1 /α + u i∈B ri xi )αP= ηEx∼D,r
1 + exp(−(n − 1)u + u i∈B ri xi )−αP+ (1 − η)Ex∼D,r
1 + exp((n − 1)u + u i∈B ri xi )−αP< ηα + (1 − η)Ex∼D,r
1 + exp((n − 1)u + u i∈B ri xi )P−(1 − η)<α η+(since i∈B ri xi ≤ n − 1)
1 + exp(2(n − 1)u)√−(1 − η)√<α η+(since u < 27/ n − 1)
1 + exp(54 n − 1<0√since η ≤ 1/(2 + exp(54 n)), completing the proof.
Recall that, to prove Theorem 23, since we already showed w2~ > 0, all we needed was
to show that αw1~ > (n − 1)w2~ . We do this next.
246

On the Inductive Bias of Dropout

Lemma 50 αw1~ > (n − 1)w2~ .
Proof: Let g be the gradient of J evaluated at u = ((n − 1)w2~ /α, w2~ ). Lemmas 48 and 49
implies that g 6= (0, 0). By convexity
w~ · g < u · gwhich, since u2 = w2~ , implies
w1~ g1 < (n − 1)w2~ g1 /α.
Since, by Lemmas 48 and 49, g1 < 0,
w1~ > (n − 1)w2~ /αcompleting the proof.

Appendix L. Proof of Theorem 24√
1
Theorem 24. If β = 1/(10 n − 1), λ = 30n, α < βλ, and n is a large enougheven number, then for any η ∈ [0, 1], erP10 (v(P10 , λ)) ≥ 3/10.
In this proof, let us also abbreviate P10 with P and use J to denote the L2 regularized
criterion in Equation (5) specialized for distribution this P .
As before, the contribution to the L2 criteron from the cases where y is −1 and 1
respectively are the same, so the value of the criterion is not affected if we clamp y at 1.
Furthermore, we leave the dependency on λ implicit and (since the source is fixed) use themore succinct v for v(P, λ).
Also, if, as before, we let B = {2, ..., n}, then by symmetry, vi is identical for all i ∈ B
so v is the minimum of J over weight vectors satisfying this constraint. Let K(w1 , w2 ) =J(w1 , w2 , ..., w2 ) so that (v1 , v2 ) minimizes K. Recall that D is the marginal distribution ofx under P conditioned on y = 1.
!!
X
λK(w1 , w2 ) = Ex∼D ` w1 x1 + w2
xi
+ (w12 + (n − 1)w22 ).
2i∈B

Lemma 46, together with the fact that |x1 | = α, implies that,
αv1 < 2β(n − 1)v2
suffices to prove Theorem 24, so we set this as our subtask.
We have


−x1
∂K
P
= Ex∼D+ λw1∂w1
1 + exp(w1 x1 + w2 i∈B xi )P− i∈B xi
∂K
P
= Ex∼D+ λ(n − 1)w2 .
∂w2
1 + exp(w1 x1 + w2 i∈B xi )First, we need a rough bound on v1 .
47

(48)

(49)
(50)

Helmbold and Long

Lemma 51 |v1 | ≤ αλ < β.
Proof: The second inequality follows from the constraint on α. From (49), we get


x1
1
P
|v1 | ≤ Ex∼D
λ1 + exp(v1 x1 + v2 i∈B xi )1 P
and the facts |x1 | ≤ α and 0 < 1+exp(v1 x1 +v
2i∈B xi )≤ 1 then imply |v1 | ≤ α/λ.

Lemma 52 For large enough n,!
PrXxi ∈ [β(n − 1), 3β(n − 1)]

i∈B

≥

1
.
13

Proof: Let Φ(z) = Pr(Z ≤ z) for a standard normal random variable Z and let S =P
23i∈B xi . Note that E(xi ) = 2β, var(xi ) = 1−4β , and the third moment E(|xi −E(xi )| ) =4
1 − 16β . The Berry-Esseen inequality (see Theorem 11.1 of DasGupta (2008)) relates
binomial distributions to the normal distribution using these moments, and directly implies
that
!
r
1
S
1 − 4β 2C(1 − 16β 4 )√<√sup Pr− 2β ≤× z − Φ(z) ≤
3/2
2
n
−
1
n
−
1
(1
−
4β
)
n
−
1
n
−1
z
where the last inequality follows from the facts that the Berry-Esseen global constant C ≤0.8 and β < 1/10.
p
Using the change of variable s = (1 − 4β 2 )(n − 1) z + 2β(n − 1) this can be restated:!
s − 2β(n − 1)
1
sup Pr (S ≤ s) − Φ p
,
≤√
2
n−1
s
(1 − 4β )(n − 1)so
Pr(S ∈ [β(n − 1), 3β(n − 1)])
r

 r

n−1
n−1
2
≥ Prz∈N (0,1) z ∈ −β
,β
−√
2
2
1 − 4β1 − 4β
n−1



−1 1
2
≥ Prz∈N (0,1) z ∈
,
−√
10 10
n−1
1
≥ ,
13
for large enough n.
Recent work
√ Berry-Esseen constant C is less then 1/2, this allows us to√ shows that the
replace the 2 n − 1 with 1/ n − 1, but it still requires n on the order of 150,000 to get
the 1/13 bound. Reducing the bound to 1/50 would make n as small as 300 sufficient.
Next, we need a rough bound on v2 .
1
Lemma 53 v2 ≥ n−1.

48

On the Inductive Bias of Dropout

Proof: From (50), we have
1
v2 =
Ex∼D
λ(n − 1)
If we denote

P





i∈B xi1 + exp(v1 x1 + v2

Pi∈B xi ).

Pi∈B xi by S, then

v2 =

1
Ex∼D
λ(n − 1)S
1 + exp(v1 x1 + v2 S).

Since, for all odd6 s > 0
Pr(S = s)=
Pr(S = −s)so Pr(S = −s) = Pr(S = s)
we have



1−2β
1+2β

s



1 + 2β1 − 2βs. Analyzing the contributions of s and −s togetherv2 λ(n − 1)
n−1
X

s
s
+η
1 + exp(v1 α + v2 s)
1 + exp(−v1 α + v2 s)
s=1



−s
−s
1 − 2β s + (1 − η)+η.
1 + exp(v1 α − v2 s)
1 + exp(−v1 α − v2 s)
1 + 2β=Pr(S = s) (1 − η)Recalling that |v1 | ≤ α/λ (Lemma 51), and using the minimizing value in this range foreach term givesv2 λ(n − 1)
n−1
X



 
s
−s
1 − 2β s≥Pr(S = s)+
1 + exp(α2 /λ + v2 s)
1 + exp(−α2 /λ − v2 s)
1 + 2β
s=1
s 


n−1
1 − exp(α2 /λ + v2 s) 1−2β
X
1+2β

=
Pr(S = s)s 
1 + exp(α2 /λ + v2 s)


s=1

≥

n−1
X
s=1


Pr(S = s)s

1 − exp(α2 /λ + v2 s − 4βs)
1 + exp(α2 /λ + v2 s)

.

6. S is the sum of an odd number of ±1’s, and thus cannot be even.

49Helmbold and Long

Assume for contradiction that v2 < 1/(n − 1). Then,v2 λ(n − 1)n−1X1 − exp(α2 /λ + s/(n − 1) − 4βs)≥Pr(S = s)s
1 + exp(α2 /λ + s/(n − 1))
s=1


n−1
X
1 − exp(s/(n − 1) − 3βs)≥Pr(S = s)s(since α ≤ βλ)
1 + exp(β 2 λ + s/(n − 1))
s=1


n−1
X
1 − exp(−2βs)≥(for large enough n)
Pr(S = s)s
1 + exp(β 2 λ + s/(n − 1))
s=1


X
1 − exp(−2βs)≥Pr(S = s)s,
1 + exp(β 2 λ + s/(n − 1))s∈[β(n−1),3β(n−1)]

since each term is positive. Taking the worst-case among [β(n − 1), 3β(n − 1)] for each
instance of s, and applying Lemma 52, we get11
1 − exp(−2β 2 (n − 1))v2 ≥×× β(n − 1)λ(n − 1) 13
1 + exp(β 2 λ + 3β)√
30 n − 1
1 − exp(−1/50)
√
=
.
(51)
130
1 + exp(3/(10 n − 1) + 1/(3000n(n − 1)))√Thus v2 = Ω( n − 1), which, for large enough n, contradicts our assumption that v2 <1/(n − 1), completing the proof.
Not that even with the many approximations made, Inequality (51) gives the desired
contradiction at n = 60. Even when the weaker bound of 1/50 discussed following Lemma 52
is used, n = 145 still suffices to give the desired contradiction.
Now we’re ready to put everything together.
Proof (of Theorem 24): Recall that, by Lemma 46, if v1 < 2β(n − 1)v2 , thenerP (v(P, λ)) ≥ 3/10.
Lemma 51 gives v1 < β. Lemma 53 implies (n − 1)v2 ≥ 1. Therefore v1 < β(n − 1)v2 ,completing the proof.
Using the 1/50 version of Lemma 52 leads to a proof of the theorem for all even n ≥ 300.

References
J. Abernethy, C. Lee, A. Sinha, and A. Tewari. Online linear optimization via smoothing.
COLT, pages 807–823, 2014.
P. Bachman, O. Alsharif, and D. Precup. Learning with pseudo-ensembles. NIPS, 2014.
P. Baldi and P. Sadowski. The dropout learning algorithm. Artificial intelligence, 210:
78–122, 2014.
50

On the Inductive Bias of Dropout

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.
L. Breiman. Some infinity theory for predictor ensembles. Annals of Statistics, 32(1):1–11,
2004.
N. Cesa-Bianchi, A. Conconi, and C. Gentile. A second-order perceptron algorithm. COLT,
2002.
G. E. Dahl.
Deep learning how I did it:
http://blog.kaggle.com.

Merck 1st place interview, 2012.

G. E. Dahl, T. N. Sainath, and G. E. Hinton. Improving deep neural networks for LVCSR
using rectified linear units and dropout. ICASSP, 2013.
A. DasGupta. Asymptotic theory of statistics and probability. Springer, 2008.
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.
J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning andstochastic optimization. JMLR, 12:2121–2159, 2011.
R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics. Addison-Wesley,
1989.
D. P. Helmbold and P. M. Long. On the necessity of irrelevant variables. JMLR, 13:2145–2170, 2012.
G. E. Hinton. Dropout: a simple and effective way to improve neural networks, 2012.
videolectures.net.
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.
H. J. Kushner and G. G. Yin.
Springer, 1997.

Stochastic approximation algorithms and applications.

P. M. Long and R. A. Servedio. Random classification noise defeats all convex potential
boosters. Machine Learning, 78(3):287–304, 2010.
E. Slud. Distribution inequalities for the binomial law. Annals of Probability, 5:404–412,
1977.
N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Dropout: A
simple way to prevent neural networks from overfitting. Journal of Machine Learning
Research, 15:1929–1958, 2014.
51

Helmbold and Long

T. Van Erven, W. Kotowski, and M. K. Warmuth. Follow the leader with dropout perturbations. Annual ACM Workshop on Computational Learning Theory, pages 949–974,
2014.
S. Wager, S. Wang, and P. Liang. Dropout training as adaptive regularization. NIPS, 2013.
S. Wager, W. Fithian, S. Wang, and P. S. Liang. Altitude training: Strong bounds for
single-layer dropout. NIPS, 2014.
L. Wan, M. Zeiler, S. Zhang, Y. Le Cun, and R. Fergus. Regularization of neural networks
using dropconnect. In ICML, pages 1058–1066, 2013.
S. Wang and C. Manning. Fast dropout training. In ICML, pages 118–126, 2013.
T. Zhang. Statistical behavior and consistency of classification methods based on convex
risk minimization. Annals of Statistics, 32(1):56–85, 2004.

52